RIDE is a Python library designed to accelerate Dijkstra's algorithm on diverse graph structures using a hierarchical approach. This method involves solving problems on simplified graphs and subsequently combining solutions into a comprehensive result. The technique is rooted in graph partitioning, dividing the original graph into clusters. By leveraging this division, RIDE eliminates numerous suboptimal route constructions, achieving significant speedup without compromising accuracy. The library offers multiple-fold acceleration compared to traditional methods. Detailed information about the underlying methodology will be available in a forthcoming academic article, providing in-depth insights into the algorithm's mechanics and performance.
It is worth noting that this method works for both transport and abstract graphs.
to install via pip without listing on pypi do:
!pip install git+https://github.com/sb-ai-lab/Ride
to install via pip witр pypi do:
!pip install ride-pfa
You can find Ride usage in GoogleColab
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
Theoretical estimations and empirical calculations are compared through graphical representations. Figure 1 illustrates the correlation between the maximum acceleration γmax and the number of vertices N0 in the graph. Figure 3 depicts the relationship between the optimal value of the α* parameter and N0. Figure 2 demonstrates the dependence of γmax on graph density D, an unscaled characteristic, alongside theoretical estimations. This comparison considers the equality D=2β0/N0, where β0 represents the average degree of vertices. These visualizations provide insights into the algorithm's performance across various graph configurations, enabling a comprehensive understanding of its efficiency and scalability.
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.
