Path between two nodes

问题:

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: path can contain each node only once.

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 =(

回答1:

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.

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...]

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]]

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.

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

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, [])

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

回答2:

This one actually works with networkx, and it's non-recursive, which may be nice for large graphs.

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

回答3:

Dijkstra's algorithm will find the shortest path in a manner similar to a breadth first search (it substitutes a priority queue weighted by depth into the graph for the naive queue of a BFS). You could fairly trivially extend it to produce the 'N' shortest paths if you need some number of alternatives, although if you need the paths to be substantially different (e.g. scheduling the routes of security vans) you might need to be more clever about selecting paths that are significantly different from each other.