Pandas : Longueur du plus court chemin entre de grandes paires de nœuds

Question

J'ai un cadre de données contenant des nœuds d'origine et des nœuds de destination comme suit :

J'ai besoin de calculer la longueur du chemin court entre ces noeuds en utilisant la méthode suivante networkx en appliquant la fonction suivante :

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'])

Dónde G est le graphe du réseau dérivé de osmnx bibliothèque : J'ai appliqué ce code à un échantillon de Dataframes, le résultat est le suivant :

Lorsque je l'ai appliqué à un cadre de données original d'environ 3000000 lignes, cela a pris plus de temps ?

Existe-t-il un moyen de rendre le fonctionnement plus rapide ?

mise à jour1 :

J'ai suivi @gboeing réponse et j'ai converti la networkx graph à igraph comme suit ( 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)

J'ai obtenu cette erreur :

---------------------------------------------------------------------------
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 

la cause de cette erreur est que le numéro des nœuds dans le fichier df['Orgin_nodes'],df['Destination_nodes'] ne correspondait pas avec G_ig noms des sommets. Que dois-je faire pour le résoudre ?

actualisation2

J'ai résolu le problème ci-dessus en créant un datframe contenant G_nx.nodes et son correspondant OSMid et remplacé les valeurs Orgin_nodes y Destination_nodes par le G_nx.nodes comme suit :

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')

et appliquer la fonction suivante échantillon de df pour mesurer la distance la plus courte :

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)

Bien qu'il fonctionne sans erreur Il a fallu plus de temps que pour l'essai précédent :

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)

Durée du mur : 2,89 s

2,88 s ± 66,3 ms par boucle (moyenne ± écart-type de 7 passages, 1 boucle chacun)

%%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)

Durée de la paroi : 1,24 s

1,2 s ± 15,7 ms par boucle (moyenne ± écart-type de 7 passages, 1 boucle chacun)

%%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'])

Durée de la paroi : 1,2 s

1,21 s ± 12 ms par boucle (moyenne ± écart-type de 7 passages, 1 boucle chacun)

On peut donc noter que le troisième est le meilleur ou que c'est pas l'échelle pour identifier lequel d'entre eux fonctionne plus rapide .

Answer 1

Il s'agit d'un problème intrinsèquement non vectorisable, car vous transmettez des étiquettes de nœuds et calculez les plus courts chemins entre eux de manière algorithmique avec un objet graphique. Vous pourriez obtenir une accélération mineure en simplifiant votre code :

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)

Pour une plus grande rapidité, exportez votre graphe OSMnx vers igraph afin de calculer rapidement les plus courts chemins en C, comme le démontre le cahier 18 de l'ouvrage Exemples d'OSMnx .