两个节点之间的路径 [英] Path between two nodes

问题描述

我正在使用networkx来处理图形.我有一个很大的图(其中有近200个节点)，我试图找到两个节点之间的所有可能路径.但是，据我了解，networkx只能找到最短的路径.如何不仅获得最短路径，还获得所有可能路径?

I'm using networkx to work with graphs. I have pretty large graph (it's near 200 nodes in it) and I try to find all possible paths between two nodes. But, as I understand, networkx can find only shortest path. How can I get not just shortest path, but all possible paths?

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

UPD: path can contain each node only once.

UPD2:我需要类似find_all_paths()函数的功能，在这里进行描述:python.org/doc/essays/graphs.html但是此函数不适用于大量节点和带有边的=(

UPD2: I need something like find_all_paths() function, described here: python.org/doc/essays/graphs.html But this function doesn't work well with large number of nodes and edged =(

推荐答案

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

igraph, another graph module for Python can calculate all the shortest paths between a given pair of nodes. Calculating all the paths does not make sense as you have infinitely many such paths.

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

An example for calculating all the shortest paths from vertex 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的结果限制为给定的最终顶点:

If you have igraph 0.6 or later (this is the development version at the time of writing), you can restrict the result of get_all_shortest_paths to a given end vertex as well:

>>> 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的网格图(可以通过igraph中的Graph.Lattice([100, 100], circular=False)轻松生成).从左上角节点到右下角节点的最短路径数等于从200个元素中选择100个元素的可能性的数量(证明:最短路径的长度有200条边，其中100条会水平"走)在网格中，其中100个将垂直"移动).这可能不适合您的内存，因此，即使在这两个节点之间计算所有最短路径也不是真正可行的.

Of course you have to be careful; for instance, assume that you have a 100 x 100 grid graph (that can easily be generated by Graph.Lattice([100, 100], circular=False) in igraph). The number of shortest paths leading from the top left node to the bottom right node equals the number of possibilities to choose 100 elements out of 200 (proof: the length of the shortest path there has 200 edges, 100 of which will go "horizontally" in the grid and 100 of which will go "vertically"). This probably does not fit into your memory, therefore even calculating all the shortest paths between these two nodes is not really feasible here.

如果确实需要两个节点之间的所有路径，则可以使用igraph重写提到的网页上给出的功能，这可能比纯Python解决方案要快，因为igraph的核心是在C语言中实现的:

If you really need all the paths between two nodes, you can rewrite the function given on the webpage you mentioned using igraph, which will probably be faster than a pure Python solution as igraph's core is implemented in 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:

It can be optimized more by converting the graph to an adjacency list representation first as it would spare repeated calls to 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.

Edit: fixed first example to work in igraph 0.5.3 as well, not only in igraph 0.6.

这篇关于两个节点之间的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！