假如我建立一个简单的多重图代码如下:
>>> H=nx.MultiDiGraph() '''建立多重图'''
>>> H.add_edges_from([(0, 1), (0, 1),(1,2),(1,2)]) '''添加边'''
[0, 1, 0, 1]
>>> H[0][1][0]['weight']=0.1 '''为每条边添加权值'''
>>> H[0][1][1]['weight']=0.2
>>> H[1][2][0]['weight']=0.3
>>> H[1][2][1]['weight']=0.4
然后我用networkx中的all_simple_path()函数求0到2的简单路径如下:
>>> for n in nx.all_simple_paths(H,0,2):
print n
[0, 1, 2]
[0, 1, 2]
[0, 1, 2]
[0, 1, 2]
>>>
我现在有个问题,0到2之间有4条路径,我怎么才能知道上面四个结果分别对应的是哪一条路径?我应该如何修改all_simple_paths()函数
all_simple_path()函数的python代码如下:
def all_simple_paths(G, source, target, cutoff=None):
if source not in G:
raise nx.NodeNotFound('source node %s not in graph' % source)
if target not in G:
raise nx.NodeNotFound('target node %s not in graph' % target)
if cutoff is None:
cutoff = len(G) - 1
if G.is_multigraph():
return _all_simple_paths_multigraph(G, source, target, cutoff=cutoff)
else:
return _all_simple_paths_graph(G, source, target, cutoff=cutoff)
def _all_simple_paths_multigraph(G, source, target, cutoff=None):
if cutoff < 1:
return
visited = [source]
stack = [(v for u, v in G.edges(source))]
while stack:
children = stack[-1]
child = next(children, None)
if child is None:
stack.pop()
visited.pop()
elif len(visited) < cutoff:
if child == target:
yield visited + [target]
elif child not in visited:
visited.append(child)
stack.append((v for u, v in G.edges(child)))
else: # len(visited) == cutoff:
count = ([child] + list(children)).count(target)
for i in range(count):
yield visited + [target]
stack.pop()
visited.pop()