This library provides Contraction Hierarchies preprocessing graph technique for Dijkstra's algorithm. Classic implementation of Dijkstra's algorithm, maneuver restrictions extension and isochrones estimation are included also.
This package provides implemented next techniques and algorithms:
- Dijkstra's algorithm
- Contraction hierarchies
- Bidirectional extension of Dijkstra's algorithm with contracted nodes
go get github.com/LdDl/chIn your project folder execute next command (assuming you have GO111MODULE=on):
go mod init modThen import library into your code:
package main
import "github.com/LdDl/ch"
func main() {
x := ch.Graph{}
_ = x
}and build
go buildYou will see next output:
go: finding github.com/LdDl/ch v1.4.6
go: downloading github.com/LdDl/ch v1.4.6And then you are good to go
-
Shortest path
Please see this test file
I hope it's pretty clear, but here is little explanation:
g := Graph{} // Prepare variable for storing graph graphFromCSV(&g, "data/pgrouting_osm.csv") // Import CSV-file file into programm g.PrepareContractionHierarchies() // Compute contraction hierarchies u := 144031 // Define source vertex v := 452090 // Define target vertex ans, path := g.ShortestPath(u, v) // Get shortest path and it's cost between source and target vertex
-
Isochrones
Please see this test file
g := Graph{} // Prepare variable for storing graph // ... // Fill graph with data (vertices and edges) // ... isochrones, err := graph.Isochrones(sourceVertex, maxCost) // Evaluate isochrones via bread-first search if err != nil { t.Error(err) return }
If you want to import OSM (Open Street Map) file then follow instructions for osm2ch
You can check benchmarks here
If you have troubles or questions please open an issue.
Please see ROADMAP.md
Bidirectional Dijkstra's algorithm's stop condition
Thanks to this visual explanation Thanks to this Java implementation of mentioned algorithms
Thanks to paulmach for his OSM-parser written in Go.
Paulmach's license is here (it's MIT)
You can check it here