有向无环图中从源到接收器的所有路径的列表 [英] list of all paths from source to sink in directed acyclic graph

查看:111
本文介绍了有向无环图中从源到接收器的所有路径的列表的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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

Possible Duplicate:
[python]: path between two nodes

任何人都可以向我指出一些有关如何执行此操作的资源吗?我正在使用networkx作为我的python库.

Can anyone point me to some resources on how to do this? I'm using networkx as my python library.

谢谢!

推荐答案

这是基于Alex Martelli的回答,但应该可以.它取决于表达式source_node.children产生的可迭代对象,该可迭代对象将遍历source_node的所有子代.它还依赖==运算符的一种工作方式来比较两个节点以查看它们是否相同.使用is可能是一个更好的选择.显然,在您使用的库中,对所有子项进行迭代的语法为graph[source_node],因此您需要相应地调整代码.

This is based on Alex Martelli's answer, but it should work. It depends on the expression source_node.children yielding an iterable that will iterate over all the children of source_node. It also relies on there being a working way for the == operator to compare two nodes to see if they are the same. Using is may be a better choice. Apparently, in the library you're using, the syntax for getting an iterable over all the children is graph[source_node], so you will need to adjust the code accordingly.

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

我主要担心的是,这会进行深度优先搜索,当从源到节点的路径有多个路径时,这将是所有源的孙子,曾孙等,但不一定是宿的父级,这会浪费精力.如果它为给定的源节点和宿节点记住了答案,则有可能避免额外的努力.

My main concern is that this does a depth first search, it will waste effort when there are several paths from the source to a node that's a grandchild, great grandchild, etc all of source, but not necessarily a parent of sink. If it memoized the answer for a given source and sink node it would be possible to avoid the extra effort.

这是一个如何工作的示例:

Here is an example of how that would work:

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

这还使您可以在两次调用之间保存备忘录字典,因此,如果您需要计算多个源节点和宿节点的答案,则可以避免很多额外的工作.

This also allows you to save the memoization dictionary between invocations so if you need to compute the answer for multiple source and sink nodes you can avoid a lot of extra effort.

这篇关于有向无环图中从源到接收器的所有路径的列表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆