两个节点之间的路径

Question

我正在使用networkx来处理图形.我有一个非常大的图形(它接近200个节点),我试图找到两个节点之间的所有可能的路径.但是,据我所知,networkx只能找到最短的路径.我怎样才能获得最短路径,而不是所有可能的路径？

UPD:path只能包含每个节点一次.

UPD2:我需要类似于find_all_paths()函数的内容,如下所述:python.org/doc/essays/graphs.html但是这个函数不适用于大量节点和edged =(

Answer 1

igraph,Python的另一个图形模块可以计算给定节点对之间的所有最短路径.计算所有路径没有意义,因为你有无数的这样的路径.

从顶点0计算所有最短路径的示例:

>>> from igraph import Graph
>>> g = Graph.Lattice([10, 10], circular=False)
>>> g.get_all_shortest_paths(0)
[...a list of 3669 shortest paths starting from vertex 0...]

如果您有igraph 0.6或更高版本(这是编写时的开发版本),您也可以将结果限制get_all_shortest_paths为给定的结束顶点:

>>> g.get_all_shortest_paths(0, 15)
[[0, 1, 2, 3, 4, 14, 15],
 [0, 1, 2, 12, 13, 14, 15],
 [0, 10, 11, 12, 13, 14, 15],
 [0, 1, 11, 12, 13, 14, 15],
 [0, 1, 2, 3, 13, 14, 15],
 [0, 1, 2, 3, 4, 5, 15]]

当然你要小心; 例如,假设您有一个100 x 100网格图(可以很容易地通过Graph.Lattice([100, 100], circular=False)igraph 生成).从左上方节点到右下方节点的最短路径数等于200中选择100个元素的可能性数量(证明:最短路径的长度有200个边缘,其中100个将"水平"在网格中,其中100个将"垂直").这可能不适合你的记忆,因此即使计算这两个节点之间的所有最短路径也不可行.

如果你真的需要两个节点之间的所有路径,你可以重写你在使用igraph提到的网页上给出的函数,这可能比纯Python解决方案更快,因为igraph的核心在C中实现:

def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    paths = []
    for node in set(graph.neighbors(start)) - set(path):
        paths.extend(find_all_paths(graph, node, end, path))
    return paths

它可以通过首先将图形转换为邻接列表表示来进行优化,因为它可以节省重复的调用graph.neighbors:

def find_all_paths(graph, start, end):
    def find_all_paths_aux(adjlist, start, end, path):
        path = path + [start]
        if start == end:
            return [path]
        paths = []
        for node in adjlist[start] - set(path):
            paths.extend(find_all_paths_aux(adjlist, node, end, path))
        return paths

    adjlist = [set(graph.neighbors(node)) for node in xrange(graph.vcount())]
    return find_all_paths_aux(adjlist, start, end, [])

编辑:修复了第一个例子,以便在igraph 0.5.3中工作,不仅仅是在igraph 0.6中.

Answer 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