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

Question

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

谁能指点我一些如何做到这一点的资源？我正在使用networkx我的python库.

谢谢!

Answer 1

这是基于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

这也允许您在调用之间保存memoization字典,因此如果您需要为多个源节点和汇聚节点计算答案,则可以避免大量额外工作.