Так что это способ сделать это в networkx. Это примерно основано на решении, которое я дал здесь< /а>. Я предполагаю, что a->b
и a<-b
- это два разных пути, которые вам нужны. Я собираюсь вернуть это как список списков. Каждый подсписок представляет собой (упорядоченные) ребра пути.
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)]]
Я ожидаю, что, изменив алгоритм dijkstra в networkx, вы получите более эффективный алгоритм (обратите внимание, что алгоритм dijkstra имеет отсечку, но по умолчанию он будет возвращать только кратчайший путь и будет следовать направлению края) .
Вот альтернативная версия всего paths.extend: paths.extend( [[edge] + путь для (neighbor,edge) в Neighbor_iter, если сосед не в excludeSet для пути в getPaths(G,neighbor,target,maxLength-1, excludeSet), если len(path)>0 ] )
person
Joel
schedule
31.01.2015