英语网站建设公司,石家庄建站工具,免费的网站关键词查询工具,网站制作案例效果文章目录 1 前言2 导包导入数据集3 创建多路图#xff0c;导入节点和边信息3 绘制线路图4 计算最短路径 1 前言
最近正在学习图神经网络#xff0c;先pick up了一些最基础的图论知识并学习了一些好玩的应用。
本文启发于B站视频#xff08;BV1LY411R7HJ#xff09;#… 文章目录 1 前言2 导包导入数据集3 创建多路图导入节点和边信息3 绘制线路图4 计算最短路径 1 前言
最近正在学习图神经网络先pick up了一些最基础的图论知识并学习了一些好玩的应用。
本文启发于B站视频BV1LY411R7HJ其对于上海地铁站点图使用了无向图也就是nx.Graph()进行建模的Python的NetworkX库。但是由于上海地铁存在两个站点之间可有多条线路相通的情况如3号线和4号线共享了“虹桥路 ”、“延安西路”、“中山公园”、“金沙江路”、“曹杨路”等多个站点所以单纯的无向图严格来说不能充分解决该问题。
所以准确来讲应该建立一个多路图multigraph即节点与节点之间应可以创建多条边。下图是多路图(左)与普通图(右)之间的区别。 在NetworkX库中nx.Graph()的add_edges_from()方法是无法添加多条边的文档里是这样记载的 Notes-----Adding the same edge twice has no effect but any edge datawill be updated when each duplicate edge is added. 下面解决这个问题
2 导包导入数据集
import networkx as nx
import pandas as pd
import matplotlib.pyplot as plt
import matplotlib.colors as mcolors
%matplotlib inlineplt.rcParams[font.sans-serif][SimHei] # 用来正常显示中文标签
plt.rcParams[axes.unicode_minus]False # 用来正常显示负号# 上海地铁站点连接表
df pd.read_csv(shanghai_subway.csv)
df.head()3 创建多路图导入节点和边信息
# 创建多路图
G nx.MultiGraph()for idx, row in df.iterrows(): # 遍历表格的每一行添加节点G.add_edges_from([(row[前一站], row[后一站])], linerow[地铁线], timerow[时间分钟])print(f节点个数{len(G)}连接个数{len(G.edges)})# 查看连接属性特征
print(G.edges(dataTrue))# 查看连接属性特征(multigraph)
# 最后一个维度为边的index可能为 012...
print(G.edges[(同济大学, 四平路, 0)])# 查看两个节点之间的边
print(G[上海火车站][中潭路])可以看到查看 G[‘上海火车站’][‘中潭路’] 可以看到所有连接两节点之间的边信息
3 绘制线路图
# 节点排版布局-默认弹簧布局
pos nx.spring_layout(G, seed123)# 设置其它可视化样式
options {font_size: 6,node_size: 300,node_color: white,edgecolors: black,linewidths: 1, # 节点线宽width: 2, # edge线宽
}
plt.figure(figsize(15,15))
nx.draw_networkx(G, pos, **options)4 计算最短路径
下面计算昌吉东路到同济大学的最短路径
# 任意两节点之间是否存在路径
print(nx.has_path(G, source昌吉东路, target同济大学))# 任意两节点之间的最短路径
print(nx.shortest_path(G, source昌吉东路, target同济大学, weighttime))# 任意两节点之间的最短路径长度
print(nx.shortest_path_length(G, source昌吉东路, target同济大学, weighttime))# 指定起始站和终点站
A_station 昌吉东路
B_station 同济大学# 计算最短路径的节点序列
shortest_path nx.shortest_path(G, sourceA_station, targetB_station, weighttime)# 计算最短路径长度
shortest_path_length nx.shortest_path_length(G, sourceA_station, targetB_station, weighttime)# 找出最短路径经过的边
edges_in_path []
for i in range(len(shortest_path) - 1):u shortest_path[i]v shortest_path[i 1]# 找到具有最小权重的边min_weight float(inf)min_edge Nonefor key, data in G[u][v].items():if data[time] min_weight:min_weight data[time]line_id data[line] # 地铁线编号min_edge (u, v, line_id, data[time])edges_in_path.append(min_edge)print(fShortest path from {A_station} to {B_station}: {shortest_path})
print(fShortest path length from {A_station} to {B_station}: {shortest_path_length})print(Edges in the shortest path: )
for i in edges_in_path:print(f{i[0]}---{i[1]} {i[2]}号线 {i[3]}分钟)到此解决
我们还可以看到这里算出的从昌吉东路到同济大学的所用时间为58分钟但原视频是59分钟。这是因为从“上海火车站”到“宝山路”两个节点的两条边所用 time 不同 所以如果直接使用Graph的add_edges_from方法会把3号线的信息被覆盖成4号线就会失去3号线那段共享路线的信息导致路径计算出现差错。 本文代码https://github.com/aquamarineaqua/D2L-My-Note/blob/main/Graph-Neural-Network/C5_topost.ipynb
