有向无环图中从源到汇的所有路径列表

Question

有向无环图中从源到汇的所有路径列表

pythonnetworkxdirected-acyclic-graphs

5

可能是重复问题：
[python]: 两个节点之间的路径

有人能指导我如何做吗？我正在使用 networkx 作为我的Python库。

谢谢！

- Tyler

你能保证只有一个源头，所有节点的更改最终都会回到这个源头，并且只有一个汇点，所有节点链最终都会通向这个汇点吗？还是说源头和汇点是更大图形的一部分，延伸到从源头引出或通向汇点的其他事物？ - Omnifarious

嗯，我不完全知道你所说的节点变化是什么意思，但有限数量的X个不同源和非常有限数量的Y个不同的汇点。 - Tyler

@Tyler - 目标是给定一个不同的源，找到通往不同汇点的所有路径？ - Omnifarious

@Tyler - 我提供了一个应该可以工作的算法，尽管我还没有测试过。我认为它比Alex的更明确正确，并且有一个相当简单的优化可以进行。 - Omnifarious

@Tyler - 我发布了一个我已经测试过的版本。 - Omnifarious

3个回答

2

这个实际上可以使用networkx，而且它是非递归的，这对于大型图形可能很好。

def find_all_paths(graph, start, end):
    path  = []
    paths = []
    queue = [(start, end, path)]
    while queue:
        start, end, path = queue.pop()
        print 'PATH', path

        path = path + [start]
        if start == end:
            paths.append(path)
        for node in set(graph[start]).difference(path):
            queue.append((node, end, path))
    return paths

- bukzor

1

我不确定是否有特殊的优化可用 - 在寻找它们之前，我会做一个简单的递归解决方案，例如（仅使用networkx中将图通过节点索引的功能给出其邻居节点的迭代器[[在networkx的情况下为字典，但我没有特别利用它]]) ...：

def allpaths(G, source_nodes, set_of_sink_nodes, path_prefix=()):
  set_of_result_paths = set()
  for n in source_nodes:
    next_from_n = []
    for an in G[n]:
      if an in set_of_sink_nodes:
        set_of_result_paths.add(path_prefix + (n, an))
      else:
        next_from_n.append(an)
    if next_from_n:
      set_of_result_paths.update(
          allpaths(G, next_from_n, set_of_sink_nodes, path_prefix + (n,)))
  return set_of_result_paths

这应该是可以证明正确的（但我不会去证明，因为现在已经很晚了，而且我感到很累和头脑混乱;-) 并且可用于验证任何进一步的优化;-)。

我首先尝试的优化是某种简单的记忆化：如果我已经计算出从某个节点N到任何目标节点（无论我在进行该计算时前缀是什么）的路径集合，我可以将其存储在字典中的键N下，并避免在以后通过不同的路线再次到达N时进行进一步的重新计算;-)。

- Alex Martelli

我会为你的帖子点赞，因为它很酷，但我感到有义务先验证其正确性。 - Eric Walker

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Omnifarious · Accepted Answer

这是基于Alex Martelli的答案，但它应该能够工作。它依赖于表达式source_node.children产生一个可迭代对象，该对象将遍历source_node的所有子节点。它还依赖于有一种有效的方法，用于比较两个节点以查看它们是否相同，并且使用is可能更好。显然，在您使用的库中，获取包含所有子项的可迭代对象的语法是graph[source_node]，因此您需要相应地调整代码。

def allpaths(source_node, sink_node):
    if source_node == sink_node: # Handle trivial case
        return frozenset([(source_node,)])
    else:
        result = set()
        for new_source in source_node.children:
            paths = allpaths(new_source, sink_node, memo_dict)
            for path in paths:
                path = (source_node,) + path
                result.add(path)
        result = frozenset(result)
        return result

我的主要关注点是它使用了深度优先搜索，当从源节点到一个不一定是汇点的孙子、曾孙等多个节点存在多条路径时，会浪费很多努力。如果对于给定的源节点和汇节点记忆答案，就可以避免额外的努力。

以下是一个示例，说明如何实现这一点：

def allpaths(source_node, sink_node, memo_dict = None):
    if memo_dict is None:
        # putting {}, or any other mutable object
        # as the default argument is wrong 
        memo_dict = dict()

    if source_node == sink_node: # Don't memoize trivial case
        return frozenset([(source_node,)])
    else:
        pair = (source_node, sink_node)
        if pair in memo_dict: # Is answer memoized already?
            return memo_dict[pair]
        else:
            result = set()
            for new_source in source_node.children:
                paths = allpaths(new_source, sink_node, memo_dict)
                for path in paths:
                    path = (source_node,) + path
                    result.add(path)
            result = frozenset(result)
            # Memoize answer
            memo_dict[(source_node, sink_node)] = result
            return result

这还可以让您在调用之间保存记忆化字典，因此，如果您需要计算多个源和汇节点的答案，则可以避免大量额外的工作。