Python - 从字典创建图形

Question

所以我有一个具有以下格式的 csv 文件:

start_city，end_city，长度，时间

所以我已经能够从那里提取数据并将其转换成如下所示的字典列表，

map_dict = [
  {'start': 'a', 'end': 'b', 'length': 5, 'time': 55},
  {'start': 'a', 'end': 'c', 'length': 8, 'time': 125},
....]

我需要知道如何将其转换成图形，以便我可以执行诸如从一个城市到另一个城市的最短路径、从一个城市到另一个城市的最小边等操作。

谁能告诉我如何将我的听写列表转换为它们之间有边的连通图？

如上例所示，a -> b 和 a -> c 之间应该有一条边。

如果您能提供可靠的阅读资源，那也会很有帮助。谢谢。

Answer 1

查看 NetworkX library .

在 GitHub 上:https://github.com/networkx/networkx

使用你的例子加上一些额外的点并将时间设置为权重:

import numpy as np
import matplotlib.pyplot as plt

G = nx.Graph()
map_dict = [
            {'start': 'a', 'end': 'b', 'length': 5, 'time': 55},
            {'start': 'a', 'end': 'c', 'length': 8, 'time': 125},
            {'start': 'b', 'end': 'c', 'length': 22, 'time': 275},
            {'start': 'c', 'end': 'd', 'length': 16, 'time': 210},
            {'start': 'b', 'end': 'e', 'length': 22, 'time': 14},
            {'start': 'd', 'end': 'e', 'length': 7, 'time': 6}  ]

for pts in map_dict:
    G.add_edge(pts['start'], pts['end'], weight=pts['time'])

# Show the shortest path between points 'a' and 'e'.
path = nx.shortest_path(G, source='a',target='e')
print(path)

path_edges = zip(path, path[1:])
path_edges = set(path_edges)
pos = nx.spring_layout(G)
nx.draw(G, pos, node_color='lawngreen', with_labels = True)
nx.draw_networkx_nodes(G, pos, nodelist=path, node_color='mediumseagreen')
nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='r', width=10)
plt.axis('equal')
plt.show()    

输出:['a', 'b', 'e']