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.

Telergam support

Installing

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

Quick start

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)

How it works:

1. Creation of a new graph based on centers of initial graph clusters

2. 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)

3. Comparison of obtained metric for error-speedup trade-off

Findings

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:

License

This project is licensed under the Apache License, Version 2.0. See the LICENSE file for details.

Acknowledgments

• Dijkstra's Algorithm
• Open Street Maps

For more information, check out our documentation.

In collaboration with