喜欢天晴 2017-12-21 10:10 采纳率: 72.7%
浏览 2508
已结题

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

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

>>> 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条回答 默认 最新

  • 菜园小杜 2017-12-21 11:07
    关注

    试一下权值可以量化,比如说 3 4 5 6量化为3X1,4X1,5X1,6X1,然后相当于在两点之间花了一张图,用图论的方法解决这个问题就可以了。希望采纳~

    评论

报告相同问题?

悬赏问题

  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 ubuntu系统下挂载磁盘上执行./提示权限不够
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)