ch - Contraction Hierarchies

Contraction Hierarchies - technique for for computing shortest path in graph.

This library provides Contraction Hierarchies preprocessing graph technique for Dijkstra's algorithm. Classic implementation of Dijkstra's algorithm and maneuver restrictions extension are included also.

Table of Contents

• About
• Installation
  • Go get
  • Go mod
• Usage
• Benchmark
• Support
• ToDo
• Thanks
• Theory
• Dependencies
• License

About

This package provides implemented next techniques and algorithms:

• Dijkstra's algorithm
• Contraction hierarchies
• Bidirectional extension of Dijkstra's algorithm with contracted nodes

Installation

Go get

go get github.com/LdDl/ch

Go mod

In your project folder execute next command (assuming you have GO111MODULE=on):

go mod init mod

Then import library into your code:

package main

import "github.com/LdDl/ch"

func main() {
	x := ch.Graph{}
	_ = x
}

and build

go build

You will see next output:

go: finding github.com/LdDl/ch v1.4.6
go: downloading github.com/LdDl/ch v1.4.6

And then you are good to go

Usage

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.PrepareContracts() // 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

If you want to import OSM (Open Street Map) file then follow instructions for osm2ch

Benchmark

You can check benchmarks here

Support

If you have troubles or questions please open an issue.

ToDo

Please see ROADMAP.md

Theory

Dijkstra's algorithm

Bidirectional search

Bidirectional Dijkstra's algorithm's stop condition

Contraction hierarchies

Video Lectures

Thanks

Thanks to this Java implementation of mentioned algorithms

Dependencies

Thanks to paulmach for his OSM-parser written in Go.

Paulmach's license is here (it's MIT)

License

You can check it here