我有一个包含orgin_nodes和Distination_nodes的数据框,如下所示:
我需要通过应用下一个函数,使用networkx
库计算这些节点之间的short_path_length:
def short_path_length (node1,node2):
return nx.shortest_path_length(G, node1, nod2,weight='length')
df['short_path_length']=np.vectorize(short_length_nodes)(df['Orgin_nodes'],df['Destination_nodes'])
其中
G
是从osmnx
库派生的网络图:我将此代码应用于数据帧示例,结果如下:
当我将其应用于具有约3000000行的原始数据帧时,需要花费更多时间吗?
有没有办法使运行速度更快?
更新1:
我遵循了
@gboeing
的答案,并按如下所示(https://github.com/gboeing/osmnx-examples/blob/master/notebooks/18-osmnx-to-igraph.ipynb)将networkx graph
转换为igraph
:ox.config(use_cache=True, log_console=True)
weight = 'length'
G_nx = nx.relabel.convert_node_labels_to_integers(G)
# convert networkx graph to igraph
G_ig = ig.Graph(directed=True)
G_ig.add_vertices(list(G_nx.nodes()))
G_ig.add_edges(list(G_nx.edges()))
G_ig.vs['osmid'] = list(nx.get_node_attributes(G_nx, 'osmid').values())
G_ig.es[weight] = list(nx.get_edge_attributes(G_nx, weight).values())
def short_path_length(node1,node2):
return G_ig.shortest_paths(source=node1,target=node2, weights=weight)[0][0]
df['short_path_length'] = df.apply(short_path_length(df['Orgin_nodes'],df['Destination_nodes']), axis=1)
我收到此错误:
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
<timed exec> in <module>()
<timed exec> in short_path_length(node1, node2)
ValueError: vertex IDs must be positive, got: -1
导致此错误的原因是
df['Orgin_nodes'],df['Destination_nodes']
中的节点号与G_ig
顶点名称不匹配。我该怎么解决?
更新2
我通过创建包含
G_nx.nodes
及其对应的OSMid
值的datframe并用Orgin_nodes
替换Destination_nodes
和G_nx.nodes
的方式解决了上述问题,如下所示:df_indices_osmid_Orgin=pd.DataFrame.from_dict({'Orgin_nodes':list(nx.get_node_attributes(G_nx, 'osmid').values()),'Indecise_Nodes_Orgin':list(G_nx.nodes())})
df=pd.merge(df,df_indices_osmid_Orgin,how='inner',on='Orgin_nodes')
df_indices_osmid_Dest=pd.DataFrame.from_dict({'Destination_nodes':list(nx.get_node_attributes(G_nx, 'osmid').values()),'Indecise_Nodes_Dest':list(G_nx.nodes())})
df=pd.merge(df,df_indices_osmid_Dest,how='inner',on='Destination_nodes')
并应用以下df函数样本来测量最短距离:
sampl_df=df.head()
def short_path_length(row):
return G_ig.shortest_paths(source=row['Indecise_Nodes_Orgin'], target=row['Indecise_Nodes_Dest'], weights=weight)[0][0]
sampl_df['short_path_length_1'] = sampl_df.apply(short_path_length, axis=1)
尽管它运行没有错误,但与之前的试用版相比,它花费了更长的时间:
sampl_df=df.head()
%%time
def short_path_length(row):
return G_ig.shortest_paths(source=row['Indecise_Nodes_Orgin'], target=row['Indecise_Nodes_Dest'], weights=weight)[0][0]
sampl_df['short_path_length_1'] = sampl_df.apply(short_path_length, axis=1)
壁挂时间:2.89 s
每个循环2.88 s±66.3 ms(平均±标准偏差,共7次运行,每个循环1次)
%%time
def short_path_length(row):
return nx.shortest_path_length(G, row['Orgin_nodes'], row['Destination_nodes'], weight='length')
sampl_df['short_path_length_2'] = sampl_df.apply(short_path_length, axis=1)
挂墙时间:1.24 s
每个循环1.2 s±15.7毫秒(平均±标准偏差,共7次运行,每个循环1次)
%%time
def short_path_length (node1,node2):
return nx.shortest_path_length(G, node1, node2,weight='length')
sampl_df['short_path_length_intr3']=np.vectorize(short_path_length)(sampl_df['Orgin_nodes'],sampl_df['Destination_nodes'])
挂墙时间:1.2 s
每个循环1.21 s±12 ms(平均±标准偏差,共7次运行,每个循环1次)
因此可以注意到,第三个是最好的,或者这不是识别其中哪个运行速度更快的尺度。
最佳答案
这是固有的不可向量化的问题,因为您要传递节点标签并使用图形对象通过算法计算它们之间的最短路径。您可以通过简化代码来稍微提高速度:
def short_path_length(row):
return nx.shortest_path_length(G, row['Orgin_nodes'], row['Destination_nodes'], weight='length')
df['short_path_length'] = df.apply(short_path_length, axis=1)
为了提高速度,请将OSMnx图形导出到igraph以在C中快速计算最短路径,如OSMnx examples中的笔记本18所示。