Networkx:获取节点之间的距离 [英] Networkx: Get the distance between nodes

问题描述

我是使用NetworkX的初学者，我试图找到一种方法来检测哪些节点彼此之间的距离为x. 我首先使用此算法来获取所有对

path=nx.all_pairs_dijkstra_path(G)

但是我仍然不确定如何使用for循环来检测节点之间的距离.

我将不胜感激.谢谢

解决方案

NetworkX具有自动计算加权图和非加权图的最短路径(或仅路径长度)的方法.确保针对用例使用正确的方法.

>>> import networkx as nx
>>> G = nx.Graph()
>>> G.add_nodes_from(["A", "B", "C", "D", "E"])
>>> G.add_edges_from([("A", "B"), ("B", "C"), ("C", "D"), ("D", "E")])
>>> sp = nx.all_pairs_shortest_path(G)
>>> sp["A"]["E"]
['A', 'B', 'C', 'D', 'E']
>>> spl = nx.all_pairs_shortest_path_length(G)
>>> spl["A"]["E"]
4

如您所见，我生成了一个包含五个节点的图形，并通过一条边将每个节点链接到下一个节点.我在sp中存储了最短路径的矩阵，并在spl中存储了最短路径的矩阵.当我需要知道两个节点之间的最短路径时节点"A"和节点"E"，我只是像矩阵一样访问sp，或字典词典:sp["A"]["E"].然后它将返回两个节点之间的最短路径.最短路径长度的方法以类似的方式工作，但是它只会返回任意两个给定节点之间的边数.

下一个代码片段可能会使我对字典矩阵的含义更加清楚.如果我请求节点"A"在sp中的所有条目，它将返回另一个词典，其中包含每个其他节点的条目:

>>> sp["A"]
{'B': ['A', 'B'], 'A': ['A'], 'E': ['A', 'B', 'C', 'D', 'E'], 'C': ['A', 'B', 'C
'], 'D': ['A', 'B', 'C', 'D']}

如果要使用for循环检查所有节点之间的距离，可以仅遍历矩阵的第一个字典的键，然后遍历该字典内的字典.比听起来容易:

>>> for node1 in spl:
...   for node2 in spl[node1]:
...     print("Length between", node1, "and", node2, "is", spl[node1][node2])
...
Length between B and B is 0
Length between B and A is 1
Length between B and E is 3
Length between B and C is 1
Length between B and D is 2
Length between A and B is 1
... (and so on!)

如果您有任何疑问，请告诉我.

I'm a beginner at using NetworkX and I'm trying to find a way to detect which nodes have distance x from each other. I've started by using this algorithm to get all pairs

path=nx.all_pairs_dijkstra_path(G)

But I'm still unsure on how to detect the distance between nodes using a for loop.

I'd appreciate any help. Thank you

解决方案

NetworkX has methods for automatically calculating the shortest paths (or just the path lengths) for weighted and unweighted graphs. Make sure that you use the correct method for your use case.

networkx.all_pairs_shortest_path - calculates the shortest paths between all nodes in an unweighted graph

networkx.all_pairs_shortest_path_length - calculates the lengths of the shortest paths between all nodes in an unweighted graph

networkx.all_pairs_dijkstra_path - calculates the shortest paths between all nodes in a weighted graph

networkx.all_pairs_dijkstra_path_length - calculates the lengths of the shortest paths between all nodes in a weighted graph

Every one of these methods, when executed on a graph, will calculate a dictionary matrix (a "dictionary of dictionaries") of nodes with either the respective shortest path or length of the shortest path as values. I'll demonstrate this with an example:

>>> import networkx as nx
>>> G = nx.Graph()
>>> G.add_nodes_from(["A", "B", "C", "D", "E"])
>>> G.add_edges_from([("A", "B"), ("B", "C"), ("C", "D"), ("D", "E")])
>>> sp = nx.all_pairs_shortest_path(G)
>>> sp["A"]["E"]
['A', 'B', 'C', 'D', 'E']
>>> spl = nx.all_pairs_shortest_path_length(G)
>>> spl["A"]["E"]
4

As you can see, I generated a graph with five nodes and linked every node to the next one with an edge. I stored a matrix of the shortest paths in sp and a matrix of the shortest path lengths in spl. When I need to know the shortest path between two nodes, e.g. node "A" and node "E", I just access sp like a matrix, or a dictionary of dictionaries: sp["A"]["E"]. It will then return the whole shortest path between the two nodes. The method for the shortest path length works in a similar fashion, but it will return only the number of edges between any two given nodes.

The next code snippet might make it clearer what I mean with a dictionary matrix. If I request all entries in sp for node "A", it returns another dictionary with entries for every other node:

>>> sp["A"]
{'B': ['A', 'B'], 'A': ['A'], 'E': ['A', 'B', 'C', 'D', 'E'], 'C': ['A', 'B', 'C
'], 'D': ['A', 'B', 'C', 'D']}

If you want to check out the distance between all nodes by using for loops, you could just iterate over the keys of the first dictionary of the matrix and then over the dictionaries inside of that dictionary. It's easier than it sounds:

>>> for node1 in spl:
...   for node2 in spl[node1]:
...     print("Length between", node1, "and", node2, "is", spl[node1][node2])
...
Length between B and B is 0
Length between B and A is 1
Length between B and E is 3
Length between B and C is 1
Length between B and D is 2
Length between A and B is 1
... (and so on!)

Please let me know if you have any questions.

这篇关于Networkx:获取节点之间的距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！