CODEWITHSUNDEEP
pythonoptimizationnetworkxigraphosmnx
DPM
DPM

Reputation: 945

Optimize shortest path calculation in an osmnx network

My question is rather simple. I have to calculate the shortest path between all nodes in an osmnx network. However this takes an enormous amount of time. I was wondering if there was anything that could speed up/optimize the process. Thank you in advance.

Here is the code:

import osmnx as ox
import igraph as ig
import matplotlib.pyplot as plt
import pandas as pd
import networkx as nx
import numpy as np
import matplotlib as mpl
import random as rd
from IPython.display import clear_output
ox.config(log_console=True, use_cache=True)


%%time
city = 'Portugal, Lisbon'
G = ox.graph_from_place(city, network_type='drive')

G_nx = nx.relabel.convert_node_labels_to_integers(G)

weight = 'length'

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

assert len(G_nx.nodes()) == G_ig.vcount()
assert len(G_nx.edges()) == G_ig.ecount()
nodes, edges = ox.graph_to_gdfs(G, nodes=True, edges=True) 

%%time
L_back_total = []
L_going_total =[]
i=1

for element in G_nx.nodes:

    clear_output(wait=True)
    L_going=[]
    L_back=[]
    
    for node in G_nx.nodes:
        
        length_going = G_ig.shortest_paths(source=element, target=node, weights=weight)[0][0]
        length_back = G_ig.shortest_paths(source=node, target=element, weights=weight)[0][0]
        
        L_going.append(length_going)
        L_back.append(length_back)

    L_back_total.append(length_back)
    L_going_total.append(length_going)
    print('Progress:', np.round(i/len(G_nx.nodes)*100, 5))
    i+=1

Upvotes: 0

Views: 1313

Answers (2)

David_grx
David_grx

Reputation: 28

In the examples provided with osmnx, there is a notebook about routing-speed-time that shows how to parallelize the calculations

Upvotes: 0

Freek de Haas
Freek de Haas

Reputation: 53

Consider using the Floyd-Warshall Algorithm.

Documentation: https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.shortest_paths.dense.floyd_warshall.html

Usage:

nx.floyd_warshall(G_ig)

Upvotes: 2

Related Questions