Get possible paths

Question

I have a simple data structure showing nodes in a directed graph:

{
    'node1': [('V1', 'R1')],
    'node2': [('R1', 'R2'), ('R1', 'R3')],
    'node3': [('R2', 'R4'), ('R2', 'R5'), ('R3', 'R4'), ('R3', 'R5')],
    'node4': [('R4', 'Z1')],
    'node5': [('R5', 'Z1')]
}

I'd like to get all possible (directed) paths from V1 to Z. For example, a path might be:

[
    ('V1', 'R1'),
    ('R1', 'R2'),
    ('R2', 'R4'),
    ('R4', 'Z1')
]

Yet I'm having trouble with what seems like a basic algorithm, which I believe involves recursion.

for node, connections in nodes.items():
    for connection in connections:

I started with something like the above but I think that's the wrong approach. What would be the suggested way to do this, without using something like itertools ?

Answer 1

The following solution is much less elegant and more verbose than the other two solutions, but here is an example implementation expanding the various functions out:

def flatten_list(l, out=None):
    """
    Flatten to get a list of all edges:

    in:  [[('V1', 'R1')], [('R1', 'R2'), ('R1', 'R3')]
    out: [('V1', 'R1'), ('R1', 'R2'), ('R1', 'R3')]
    """
    if out is None: out=[]
    for li in l:
        if not isinstance(li, list):
            out.append(li)
        else:
            flatten_list(li, out)
    return out


def get_connected_nodes_from(list_of_edges, from_node):
    """
    Given an input node (string), and list of edges (tuple),
    Return a list of all nodes (list of strings) connected to the input node.
    Note: this is a directed graph. That is, we are only grabbing descendants
          and not all (undirected) edges.

    in:  from_node='R1', list_of_edges=[('V1', 'R1'), ('R1', 'R2'), ('R1', 'R3')]
    out: ['R2', 'R3']
    """
    out = []
    for edge in list_of_edges:
        if edge[0] == from_node:
            out.append(edge[1])
        elif from_node == edge[0]:
            out.append(edge[0])
    return out


def get_all_paths(list_of_edges, node=None, current_path=None, all_paths=None):
    """
    Given a list of edges, this will return all directed paths from start to finish.
    """
    # "Initialize" things on the first time through
    if all_paths is None: all_paths = []; node = list_of_edges[0][0]; current_path = [node,]
    node_descendants = get_connected_nodes_from(list_of_edges, node) 
    if len(node_descendants) == 0:
        all_paths.append(current_path) # append the path when it is a leaf with no descendants
    else:
        [get_all_paths(list_of_edges, node, current_path + [node,], all_paths) for node in node_descendants]
    return all_paths

And using it:

>>> graph = {
    'node1': [('V1', 'R1')],
    'node2': [('R1', 'R2'), ('R1', 'R3')],
    'node3': [('R2', 'R4'), ('R2', 'R5'), ('R3', 'R4'), ('R3', 'R5')],
    'node4': [('R4', 'Z1')],
    'node5': [('R5', 'Z1')],
}
>>> list_of_edges = flatten_list(graph.values())
>>> print (['-->'.join(path) for path in get_all_paths(list_of_edges)])
# ['V1-->R1-->R2-->R4-->Z1', 'V1-->R1-->R2-->R5-->Z1', 'V1-->R1-->R3-->R4-->Z1', 'V1-->R1-->R3-->R5-->Z1']

Answer 2

Given that the tuples in the data structure are the edges and the values in the tuples are the graph's nodes, it's possible to reorganise the data in a way that makes the algorithm simpler:

graph = [edge for es in source.values() for edge in es]

Since there might be loops in the graph, we need to keep track of nodes that have already been visited. A recursive function with that in mind, finding all paths from a start node to and end node, give the graph as a list of edges from node to node:

def find_path(start, end, edges, visited=None):
    if visited is None:
        visited = []
    for n1, n2, in edges:
        if n1 == start:
            if n2 == end:
                yield [n1, n2]
            elif n2 not in visited:
                for continuation in find_path(n2, end, edges, visited + [n1]):
                    yield [n1] + continuation

The whole thing:

source = {
    'node1': [('V1', 'R1')],
    'node2': [('R1', 'R2'), ('R1', 'R3')],
    'node3': [('R2', 'R4'), ('R2', 'R5'), ('R3', 'R4'), ('R3', 'R5')],
    'node4': [('R4', 'Z1')],
    'node5': [('R5', 'Z1')]
}

graph = [edge for es in source.values() for edge in es]


def find_path(start, end, edges, visited=None):
    if visited is None:
        visited = []
    for n1, n2, in edges:
        if n1 == start:
            if n2 == end:
                yield [n1, n2]
            elif n2 not in visited:
                for continuation in find_path(n2, end, edges, visited + [n1]):
                    yield [n1] + continuation


print(list(find_path('V1', 'Z1', graph)))

Output:

[['V1', 'R1', 'R2', 'R4', 'Z1'], ['V1', 'R1', 'R2', 'R5', 'Z1'], ['V1', 'R1', 'R3', 'R4', 'Z1'], ['V1', 'R1', 'R3', 'R5', 'Z1']]

Note that the result is cast to a list because the function is a generator, it yields solutions one at a time. The call to list() collects all the results in a single output.

Answer 3

You can use recursion with a generator:

data = {'node1': [('V1', 'R1')], 'node2': [('R1', 'R2'), ('R1', 'R3')], 'node3': [('R2', 'R4'), ('R2', 'R5'), ('R3', 'R4'), ('R3', 'R5')], 'node4': [('R4', 'Z1')], 'node5': [('R5', 'Z1')]}
new_data = [i for b in data.values() for i in b]
def lookup(start, end, seen=[], c = []):
   _r = [(a, b) for a, b in new_data if a == start and a not in seen]
   for a, b in _r:
      if b == end:
         yield c+[(a, b)]
      else:
         yield from lookup(b, end, seen=seen+[start], c=c+[(a, b)])

print(list(lookup('V1', 'Z1')))

Output:

[
  [('V1', 'R1'), 
   ('R1', 'R2'), 
   ('R2', 'R4'), 
   ('R4', 'Z1')], 
  [('V1', 'R1'),  
   ('R1', 'R2'), 
   ('R2', 'R5'), 
   ('R5', 'Z1')], 
  [('V1', 'R1'), 
   ('R1', 'R3'), 
   ('R3', 'R4'), 
   ('R4', 'Z1')], 
  [('V1', 'R1'), 
   ('R1', 'R3'), 
   ('R3', 'R5'), 
   ('R5', 'Z1')]
]