问大型图上的简单路径查询

EN

import networkx as nx
import itertools

def getPaths(G,source,target, maxLength, excludeSet=None):
    #print source, target, maxLength, excludeSet
    if excludeSet== None:
        excludeSet = set([source])
    else:
        excludeSet.add(source)# won't allow a path starting at source to go through source again.
    if maxLength == 0:
        excludeSet.remove(source)
        return []
    else:
        if G.has_edge(source,target):
            paths=[[(source,target)]]
        else:
            paths = []
        if G.has_edge(target,source):
            paths.append([(target,source)])
        #neighbors_iter is a big iterator that will give (neighbor,edge) for each successor of source and then for each predecessor of source.

        neighbors_iter = itertools.chain(((neighbor,(source,neighbor)) for neighbor in G.successors_iter(source) if neighbor != target),((neighbor,(neighbor,source)) for neighbor in G.predecessors_iter(source) if neighbor != target))

        #note that if a neighbor is both a predecessor and a successor, it shows up twice in this iteration.  

        paths.extend( [[edge] + path for (neighbor,edge) in neighbors_iter if neighbor not in excludeSet for path in getPaths(G,neighbor,target,maxLength-1,excludeSet)] )

        excludeSet.remove(source) #when we move back up the recursion, don't want to exclude this source any more

        return paths

G=nx.DiGraph()
G.add_edges_from([(1,2),(2,3),(1,3),(1,4),(3,4),(4,3)])

print getPaths(G,1,3,2)

>[[(1, 3)], [(1, 2), (2, 3)], [(1, 4), (4, 3)], [(1, 4), (3, 4)]]