python - 使用 NetworkX 查找从一个到另一个的最短和最长权重

Question

我想计算特定源到目标的所有可能值(csv 中的列)。我能够使用以下代码创建图表:

import networkx as nx
import pandas as pd

df = pd.read_csv('Rates.csv')

Graphtype = nx.MultiDiGraph()

G = nx.from_pandas_edgelist(df, source='Source', target='Destination', edge_attr='value',create_using=Graphtype)   



# print all paths 

for path in nx.all_simple_paths(G, source='a', target='d'):
    print(path)

我正在正确获取特定源到目标的输出。

输出

 ['a', 'b', 'c', 'd']
    ['a', 'b', 'd']
    ['a', 'd']
    ['a', 'c', 'd']

既然我们也给图表分配了权重，我也想计算所有路径的权重。即对于 ['a', 'b', 'c', 'd'] 来说，权重将为 SUM(a->b,b->c,c->d) 并且所有路径都相同。

有什么方法可以使用 networkX 实现相同的目的吗？我能够查看文档

https://networkx.github.io/documentation/latest/_modules/networkx/algorithms/shortest_paths/weighted.html

但它只讨论特定源到目的地的最短路径。主要目的是计算从特定来源到目的地的最小重量和最大重量。有没有办法达到同样的效果。

我们可以通过创建函数来实现相同的目的，这要归功于

How to find path with highest sum in a weighted networkx graph?

heaviest_path = max((path for path in nx.all_simple_paths(G, source, dest)),
                    key=lambda path: get_weight(path))

任何人都可以建议我们如何构建 get_weight 函数。

编辑:

G.edges() 提供输出:

OutMultiEdgeDataView([('a', 'b', {'value': 0.7}), ('a', 'd', {'value': 0.52}), ('a', 'c', {'value': 0.33}), ('b', 'c', {'value': 0.58}), ('b', 'd', {'value': 0.66}), ('c', 'd', {'value': 0.4}), ('d', 'b', {'value': 0.3})])

其中 value 是权重。

谢谢

Answer 1

我不相信 Networkx 内置了任何东西。但我认为这是一个编写起来相当简单的函数。我假设权重存储在边缘属性'weight'中。

def get_weight(G, path):
    total = 0
    for u, v in zip(path[:-1], path[1:]):
        total += G.edges[u,v]['weight']
    return total

我使用了 zip ，它将接受两个列表并返回由其参数的第一个元素组成的对，然后是第二个元素，然后是第三个元素等。我传递到 zip 两个列表，第一个列表是 path，但没有最后一个元素。第二个列表是 path 但没有第一个元素。因此，如果 path = ['a', 'b', 'c', 'd']，那么 zip 返回的第一件事就是 ('a' ，'b')。接下来是 ('b', 'c') 等

您可以通过使用列表理解之类的东西来使其更加紧凑:

def get_weight(G, path):
    return sum(G.edges[u,v]['weight'] for u,v in zip(path[:-1], path[1:]))

我相信它也更快一点，但我可能是错的。除非您进行大量此类计算，否则不太可能产生重大影响。