时间戳

首页 > 解决方案 > Networkx 在图中查找不同最短路径之间的公共节点 - 是否有替代解决方案？

python - Networkx 在图中查找不同最短路径之间的公共节点 - 是否有替代解决方案？

问题描述

我正在编写一个工具，用于识别网络中的节点，当给定一组两个或多个源和目的地遇到网络问题或延迟时，这些节点会导致延迟。我正在使用 networkx python 库来构建网络图。考虑这张图 -

a -- b -- c -- d  
     |    |
     e -- f

比如说，这些是面临网络问题的源和目标集。这意味着 a 和 d 之间的流量正在经历延迟，而 e 和 d 之间的流量正在经历延迟，依此类推。

| source | destination |
|--------|-------------|
| a      | d           |
| e      | d           |
| f      | a           |

Shortest path host a to host d: 
     ['a', 'b', 'c', 'd']
Shortest path host e to host d: 
     ['e', 'b', 'c', 'd']
Shortest path host f to host a: 
     ['f', 'c', 'b', 'a']

^^ 公共节点是“c”和“b”，因此请检查它们是否有错误。

标签： pythonnetworkingnetworkxgraph-theory

解决方案

我认为您正在寻找的是最大度数的节点，它们的每条边的平均权重最低。我们可以获得排序节点所需的信息，如下所示：

def avg_weight(graph, node):
    all_edges = graph.edges(data=True)
    edges = list(filter(lambda e: node in e, all_edges))
    avg = 0
    for e in edges:
        avg += e[2]['weight'] / len(edges)
    return avg

def weight_and_degree(graph):
    degrees = dict(G.degree)
    weights = dict(map(lambda n: (n, avg_weight(graph, n)), G.nodes))
    return dict(map(lambda p: (p[0], (p[1], weights[p[0]])), degrees.items()))

现在这是一个（加权）图，它具有与您在上面指定的相同的属性。权重代表延迟时间。

import networkx as nx

G = nx.Graph()
G.add_edge('a','b', weight=0.1)
G.add_edge('b','c', weight=0.1)
G.add_edge('d','c', weight=0.1)
G.add_edge('b','e', weight=0.1)
G.add_edge('f','e', weight=0.3)
G.add_edge('f','c', weight=0.2)

如果我们在图上运行上述函数，我们可以像这样一次按度数和平均权重排序：

s = dict(sorted(weight_and_degree(G).items(), key=lambda x: (-x[1][0], x[1][1])))
print(' '.join(s.keys())) # b c e f a d

然后你可以根据你可用的资源查看这个列表的topn结果，或者你可以修改代码只返回最大度数节点等。

参考：

推荐阅读