ride_pfa 0.1.0

fast pathfinding lib

RIDE

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.

Telergam support

Installing

to install via pip without listing on pipy do:

!pip install git+https://github.com/sb-ai-lab/Ride

Quick start

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

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:

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