获取可能的路径

Question

我有一个简单的数据结构，在有向图中显示节点：

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

我想获取从 V1 到 Z 的所有可能（有向）路径。例如，路径可能是：

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

然而，我在处理看似基本的算法时遇到了问题，我认为它涉及递归。

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

我从类似上面的方法开始，但我认为这是错误的方法。如果不使用 itertools 之类的东西，建议的方法是什么？

Answer 1

您可以对生成器使用递归：

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')))

输出：

[
  [('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')]
]

Answer 2

鉴于数据结构中的元组是边，元组中的值是图的节点，可以以一种使算法更简单的方式重新组织数据：

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

整个事情：

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)))

输出：

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

请注意，结果被转换为一个列表，因为该函数是一个生成器，它一次生成一个解决方案。调用 list() 将所有结果收集到一个输出中。

Answer 3

以下解决方案比其他两个解决方案更不优雅也更冗长，但这里是一个扩展各种功能的示例实现：

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

并使用它：

>>> 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']

获取可能的路径

Get possible paths

python

algorithm

graph-algorithm