Categorygithub.com/LdDl/ch
modulepackage
1.7.8
Repository: https://github.com/lddl/ch.git
Documentation: pkg.go.dev

# README

GoDoc Build Status Sourcegraph Go Report Card GitHub tag

ch - Contraction Hierarchies

Contraction Hierarchies - technique for speed up of computing shortest path in graph.

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.

Table of Contents

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

  • 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

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 visual explanation 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

# Functions

ImportFromFile Imports graph (prepared by ExportToFile(fname string) function) from file of CSV-format Header of CSV-file containing information about edges: from_vertex_id - int64, ID of source vertex to_vertex_id - int64, ID of arget vertex weight - float64, Weight of an edge Header of CSV-file containing information about vertices: vertex_id - int64, ID of vertex order_pos - int, Position of vertex in hierarchies (evaluted by library) importance - int, Importance of vertex in graph (evaluted by library) Header of CSV-file containing information about shortcuts between vertices: from_vertex_id - int64, ID of source vertex to_vertex_id - int64, ID of target vertex weight - float64, Weight of an shortcut via_vertex_id - int64, ID of vertex through which the shortcut exists.
MakeVertex Create vertex with label.
NewDistance Constructor for Distance.
NewGraph returns pointer to created Graph and does preallocations for processing purposes.

# Constants

No description provided by the author

# Variables

ErrGraphIsFrozen Graph is frozen, so it can not be modified.

# Structs

Distance Information about contraction between source vertex and contraction vertex distance - used in Dijkstra local searches previousOrderPos - previous contraction order (shortest path tree) previousSourceID - previously found source vertex (shortest path tree).
Graph Graph object mapping Internal map for 1:1 relation of internal IDs to user's IDs Vertices Slice of vertices of graph shortcuts Found and stored shortcuts based on contraction hierarchies .
ShortcutPath Representation of shortcut between vertices From - ID of source vertex To - ID of target vertex ViaVertex - ID of vertex through which the shortcut exists Cost - summary cost of path between two vertices .
Vertex All information about vertex.
No description provided by the author