Python combinations of elements in dict

user_17781851 0
Viewed 118

I have a bunch of dicts like the one below (some can be quite large):

V = {
    0: [823, 832, 1151, 1752, 2548, 3036],
    823: [832, 1151, 1752, 2548, 3036, 3551],
    832: [1151, 1752, 2548, 3036, 3551],
    1151: [1752, 2548, 3036, 3551],
    1752: [2548, 3036, 3551, 4622],
    2548: [3036, 3551, 4622],
    3036: [3551, 4622, 5936, 6440],
    3551: [4622, 5936, 6440],
    4622: [5936, 6440, 9001],
    5936: [6440, 9001],
    6440: [9001],
    9001: []
}

The dict represents basic rules to help derive all possible paths (they are routes). A path is a sequence of the above ints.

Every value in the list of dict values is also a key.

How do I determine all possible paths knowing that for example:

[3036, 4622, 9001] is a valid path,

But [3036, 9001] is not, and the reason, is that 3036 must be followed by one of the elements in V[3036]. And every combination must contain a compatible sequence, and every sequence must end with 9001, which says, that to get to 9001, one must go via 6440, or 5936 or 4622.

Every sequence must also start with one the points in V[0].

Two things I tried:

  1. I first used itertools.product to derive all paths and then filter out invalid ones, but for most dicts, the number of itertools.product combinations is just too large.
  2. Monte Carlo sims but the number of loops is in the millions with no guarantee to capture all paths.
combinations itertools python
3 Answers

Seems like a simple DFS. Since the graph appears to be directed (each node has successors whose numbers are greater than that of the node), you don't even need to be careful to avoid cycles.

>>> def dfs(graph, start, end):
...     if start == end:
...         return [[end]]
...     return [[start] + result for s in graph[start] for result in dfs(graph, s, end)]
...
>>> dfs(V, 0, 9001)
[[0, 823, 832, 1151, 1752, 2548, 3036, 3551, 4622, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 3551, 4622, 5936, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 3551, 4622, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 3551, 4622, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 3551, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 3551, 5936, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 3551, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 4622, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 4622, 5936, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 4622, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 4622, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 5936, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3551, 4622, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3551, 4622, 5936, 9001], [0, 823, 832, 1151, 1752, 2548, 3551, 4622, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3551, 4622, 9001], [0, 823, 832, 1151, 1752, 2548, 3551, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3551, 5936, 9001], [0, 823, 832, 1151, 1752, 2548, 3551, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 4622, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 4622, 5936, 9001], [0, 823, 832, 1151, 1752, 2548, 4622, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 4622, 9001], [0, 823, 832, 1151, 1752, 3036, 3551, 4622, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 3036, 3551, 4622, 5936, 9001], [0, 823, 832, 1151, 1752, 3036, 3551, 4622, 6440, 9001], [0, 823, 832, 1151, 1752, 3036, 3551, 4622, 9001], [0, 823, 832, 1151, 1752, 3036, 3551, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 3036, 3551, 5936, 9001], [0, 823, 832, 1151, 1752, 3036, 3551, 6440, 9001], [0, 823, 832, 1151, 1752, 3036, 4622, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 3036, 4622, 5936, 9001], [0, 823, 832, 1151, 1752, 3036, 4622, 6440, 9001], [0, 823, 832, 1151, 1752, 3036, 4622, 9001], [0, 823, 832, 1151, 1752, 3036, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 3036, 5936, 9001], [0, 823, 832, 1151, 1752, 3036, 6440, 9001], [0, 823, 832, 1151, 1752, 3551, 4622, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 3551, 4622, 5936, 9001], [0, 823, 832, 1151, 1752, 3551, 4622, 6440, 9001], [0, 823, 832, 1151, 1752, 3551, 4622, 9001], [0, 823, 832, 1151, 1752, 3551, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 3551, 5936, 9001], [0, 823, 832, 1151, 1752, 3551, 6440, 9001], [0, 823, 832, 1151, 1752, 4622, 5936, 6440, 9001], [0, 823, 832, 1151, 1752, 4622, 5936, 9001], [0, 823, 832, 1151, 1752, 4622, 6440, 9001], [0, 823, 832, 1151, 1752, 4622, 9001], [0, 823, 832, 1151, 2548, 3036, 3551, 4622, 5936, 6440, 9001], [0, 823, 832, 1151, 2548, 3036, 3551, 4622, 5936, 9001], [0, 823, 832, 1151, 2548, 3036, 3551, 4622, 6440, 9001], [0, 823, 832, 1151, 2548, 3036, 3551, 4622, 9001], [0, 823, 832, 1151, 2548, 3036, 3551, 5936, 6440, 9001], [0, 823, 832, 1151, 2548, 3036, 3551, 5936, 9001], [0, 823, 832, 1151, 2548, 3036, 3551, 6440, 9001], [0, 823, 832, 1151, 2548, 3036, 4622, 5936, 6440, 9001], [0, 823, 832, 1151, 2548, 3036, 4622, 5936, 9001], [0, 823, 832, 1151, 2548, 3036, 4622, 6440, 9001], [0, 823, 832, 1151, 2548, 3036, 4622, 9001], [0, 823, 832, 1151, 2548, 3036, 5936, 6440, 9001], [0, 823, 832, 1151, 2548, 3036, 5936, 9001], [0, 823, 832, 1151, 2548, 3036, 6440, 9001], [0, 823, 832, 1151, 2548, 3551, 4622, 5936, 6440, 9001], [0, 823, 832, 1151, 2548, 3551, 4622, 5936, 9001], ...]

If the above function spins forever on one of your dicts, then it's time to revise the assumption about the graph being directed.

user_37997590

You can treat the dictionary as an adjacency list. You could use vanilla Python (as in Samwise's answer), but their answer won't work if the graph has cycles.

networkx exposes a method for finding the desired paths, so we can use that. This function returns a generator, meaning that it doesn't load all of the paths into memory at once (although you can if you want to using list() -- but you might run out of memory if the graph is large):

import networkx as nx

graph = nx.DiGraph(V)
for path in nx.all_simple_paths(graph, 0, 9001):
    print(path)

The first and last three lines of the output:

[0, 823, 832, 1151, 1752, 2548, 3036, 3551, 4622, 5936, 6440, 9001]
[0, 823, 832, 1151, 1752, 2548, 3036, 3551, 4622, 5936, 9001]
[0, 823, 832, 1151, 1752, 2548, 3036, 3551, 4622, 6440, 9001]
... [755 more lines]
[0, 3036, 5936, 6440, 9001]
[0, 3036, 5936, 9001]
[0, 3036, 6440, 9001]
user_177698150

Non-Recursive Depth First Search Generator Function

  • solution faster than the other two solutions (i.e. networkx, dfs)
  • updated with an observation by KellyBundy in comments which made code slightly faster.

Code

def dfs_stack(graph, start, goal):
    '''
        Depth First Search for all paths from start to goal
    '''
    # Init stack to path with just starting vertex
    stack = [[start]]
    
    while stack:
        # Expand path at end of stack
        path = stack.pop()
        
        if path[-1] == goal:
            yield path                # reached goal
        else:
            # Add all paths of vertex to stack
            for start in graph[path[-1]]:
                stack.append(path + [start])

Usage

# Use list on generator to obtain all paths
paths = list(dfs_stack(V, 0, 9001))

print(paths [:3])    # First 3 paths
# Output: [0, 3036, 6440, 9001], [0, 3036, 5936, 9001], [0, 3036, 5936, 6440, 9001]]

print(paths [-3:])    # Last 3 paths
# Output: [[0, 823, 832, 1151, 1752, 2548, 3036, 3551, 4622, 6440, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 3551, 4622, 5936, 9001], [0, 823, 832, 1151, 1752, 2548, 3036, 3551, 4622, 5936, 6440, 9001]]

Timing Comparison

The current approach is over twice as fast as the other two posted solutions on the OP data.

Current Approach
    %timeit list(dfs_stack(V, 0, 9001))
    Result: 874 µs ± 42.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

DFS function from Samwise solution
    %timeit dfs(V, 0, 9001)
    Result: 2.1 ms ± 91.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Networkx solution from BrokenBenchmark solution
    %%timeit 
    graph = nx.DiGraph(V)
    list(nx.all_simple_paths(graph, 0, 9001))
    Result: 4.83 ms ± 113 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Timing from OP (see comments): this solution produces 12 Million paths in less than 20s, 
                               networkx takes in excess of 48s

Modification to Avoid Cycles

Although the current graph does not have cycles, a simple modification can be made to avoid them.

def dfs_stack_no_cycles(graph, start, goal):
    '''
        Depth First Search for all paths from start to goal
    '''
    graph = {k:set(v) for k, v in graph.items()}
    # Init stack to path with just starting vertex
    stack = [[start]]
    
    while stack:
        # Expand path at end of stack
        path = stack.pop()
        
        if path[-1] == goal:
            yield path                # reached goal
        else:
            # Add all paths of vertex to stack
            for start in graph[path[-1]] - set(path):
                stack.append(path + [start])
user_30660770
Related