Pandas:大对节点之间的最短路径长度

Question

我有一个包含 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回答和我转换了 networkx graph至 igraph如下( https://github.com/gboeing/osmnx-examples/blob/master/notebooks/18-osmnx-to-igraph.ipynb ):

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值并替换 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 秒

每个循环 2.88 秒 ± 66.3 毫秒(平均值 ± 标准偏差，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 秒

每个循环 1.2 秒 ± 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 秒

每个循环 1.21 s ± 12 ms(平均值 ± 标准偏差，7 次运行，每次 1 次循环)

所以可以注意到第三个是最好的或者这个是 不是秤用于识别哪些正在运行 更快 .

Answer 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 所示。 .