The RIDE is a python library for accelerating Deikstra task on any graphs with hierarchical method involving solving a problem on simpler graphs with further combining solutions into a common one. The method is based on the division of the graph into clusters. By using this division, you can eliminate many sub optimal route constructions and achieve multiple-time acceleration without significant loss of accuracy. More information about method ine can find soon in corresponding article.
It is worth noting that this method works for both transport and abstract graphs.
to install via pip without listing on pipy do:
!pip install git+https://github.com/sb-ai-lab/Ride
from ride_pfa import graph_osm_loader
import ride_pfa.path_finding as pfa
import ride_pfa.clustering as cls
from ride_pfa.centroid_graph import centroids_graph_builder as cgb
id = graph_osm_loader.osm_cities_example['Paris']
g = graph_osm_loader.get_graph(id)
cms_resolver = cls.LouvainCommunityResolver(resolution=1)
# Exact path , but need more memory
exact_algorithm = pfa.MinClusterDistanceBuilder().build_astar(g, cms_resolver)
# Suboptimal paths, with low memory consumption
cg = cgb.CentroidGraphBuilder().build(g, cms_resolver)
suboptimal_algorithm = pfa.ExtractionPfa(
g=g,
upper=pfa.Dijkstra(cg.g),
down=pfa.Dijkstra(g)
)
nodes = list(g.nodes())
s, t = nodes[0], nodes[1]
length, path = exact_algorithm.find_path(s, t)
- Creation of a new graph based on centers of initial graph clusters
- Computation of shortes path on a new cluster-based graph (this contraction-hierarchy based approach is obviously faster hhan straight forward calcylation of shortest path, but less accurate)
- Comparison of obtained metric for error-speedup trade-off
The relationship between theoretical estimations and empirical cal- culations. Figure 1,3 – the relationship between the maximum of acceleration γmax and the number of vertices N0 in the graph. the relationship between the optimal value of the α∗parameter and the number of vertices N0. Figure 2 – the dependence of the maximum acceleration γmax on the graph density D (unscaled characteristic) along with the theoretical estimations, considering the equality given by D=2β0/N0.
Developed algorithm was applied for 600 cities and the following dependencies were obtained:
This project is licensed under the Apache License, Version 2.0. See the LICENSE file for details.
For more information, check out our documentation.
