suanfaxiazai
suanfaxiazai
2017-12-21 10:10

最近在做一个课题,我需要找到多重图中两个节点之间的所有简单路径。每条路径权重和不一样。

5
  • python
  • 社交网络
  • 图论
  • 遍历
  • net

假如我建立一个简单的多重图代码如下:

>>> 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()
  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

3条回答