ch

README

ch - Contraction Hierarchies

Contraction Hierarchies (with bidirectional version of Dijkstra's algorithm) for computing shortest path in graph

Table of Contents

• About
• Installation
  • Old
  • New
• Usage
• Support
• ToDo
• Thanks
• Theory

About

This package provides implemented next techniques and algorithms:

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

Installation

Old way

go get github.com/LdDl/ch

New way

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.1.0
go: downloading github.com/LdDl/ch v1.1.0

And then you are good to go

Usage

Please see this benchmark

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

Support

If you have troubles or questions please open an issue.

ToDo

• Import file of specific format Done as CSV
• Export file of specific format Done as CSV
• Thoughts and discussions about OSM graph and extensions
• Map matcher as another project WIP

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

Documentation

Index

• type Distance
  • func NewDistance() *Distance
• type Graph
  • func ImportFromFile(fname string) (*Graph, error)
  • func (graph *Graph) AddEdge(from, to int, weight float64)
  • func (graph *Graph) AddVertex(labelExternal, labelInternal int)
  • func (graph *Graph) ComputePath(middleID int, prevF, prevR map[int]int) []int
  • func (graph *Graph) CreateVertex(label int)
  • func (graph *Graph) ExportToFile(fname string) error
  • func (graph *Graph) PrepareContracts()
  • func (graph *Graph) Preprocess() []int
  • func (graph *Graph) ShortestPath(source, target int) (float64, []int)
  • func (graph *Graph) VanillaShortestPath(source, target int) (float64, []int)
• type Processed
  • func NewProcessed() *Processed
• type Vertex
  • func MakeVertex(label int) *Vertex
  • func NewVertex(vertexNum int) *Vertex
  • func (v *Vertex) PrintInOut()

Types

type Distance

type Distance struct {
	// contains filtered or unexported fields
}

func NewDistance

func NewDistance() *Distance

type Graph

type Graph struct {
	Vertices []*Vertex
	// contains filtered or unexported fields
}

Graph Graph object

pqImportance Heap to store importance of each vertex pqComparator Heap to store traveled distance mapping Internal map for 1:1 relation of internal IDs to user's IDs Vertices Slice of vertices of graph nodeOrdering Ordering of vertices contracts found and stored contraction hierarchies

func ImportFromFile

func ImportFromFile(fname string) (*Graph, error)

ImportFromFile Imports graph from file of CSV-format

Header of CSV-file: from_vertex_id;to_vertex_id;from_vertex_internal_id;to_vertex_internal_id;edge_weight;contract_id;contract_internal_id int;int;int;int;float64;-1 (no contract) else external ID of contracted vertex; -1 (no contract) else internal ID of contracted vertex

func (*Graph) AddEdge

func (graph *Graph) AddEdge(from, to int, weight float64)

AddEdge Adds new add between two vertices

from User's definied ID of first vertex of edge to User's definied ID of last vertex of edge weight User's definied weight of edge

func (*Graph) AddVertex

func (graph *Graph) AddVertex(labelExternal, labelInternal int)

AddVertex Adds vertex with provided internal ID

labelExternal User's definied ID of vertex labelInternal internal ID of vertex

func (*Graph) ComputePath

func (graph *Graph) ComputePath(middleID int, prevF, prevR map[int]int) []int

ComputePath Returns slice of IDs (user defined) of computed path

func (*Graph) CreateVertex

func (graph *Graph) CreateVertex(label int)

CreateVertex Creates new vertex and assign internal ID to it

label User's definied ID of vertex

func (*Graph) ExportToFile

func (graph *Graph) ExportToFile(fname string) error

ExportToFile Exports graph to file of CSV-format

Header of CSV-file: from_vertex_id;to_vertex_id;from_vertex_internal_id;to_vertex_internal_id;edge_weight;contract_id;contract_internal_id int;int;int;int;float64;-1 (no contract) else external ID of contracted vertex; -1 (no contract) else internal ID of contracted vertex

func (*Graph) PrepareContracts

func (graph *Graph) PrepareContracts()

PrepareContracts Compute contraction hierarchies

func (*Graph) Preprocess

func (graph *Graph) Preprocess() []int

Preprocess Computes contraction hierarchies and returns node ordering

func (*Graph) ShortestPath

func (graph *Graph) ShortestPath(source, target int) (float64, []int)

ShortestPath Computes and returns shortest path and it's cost (extended Dijkstra's algorithm)

If there are some errors then function returns '-1.0' as cost and nil as shortest path

source User's definied ID of source vertex target User's definied ID of target vertex

func (*Graph) VanillaShortestPath

func (graph *Graph) VanillaShortestPath(source, target int) (float64, []int)

VanillaShortestPath Computes and returns shortest path and it's cost (vanilla Dijkstra's algorithm)

If there are some errors then function returns '-1.0' as cost and nil as shortest path

source User's definied ID of source vertex target User's definied ID of target vertex

type Processed

type Processed struct {
	// contains filtered or unexported fields
}

func NewProcessed

func NewProcessed() *Processed

type Vertex

type Vertex struct {
	Label int
	// contains filtered or unexported fields
}

func MakeVertex

func MakeVertex(label int) *Vertex

func NewVertex

func NewVertex(vertexNum int) *Vertex

func (*Vertex) PrintInOut

func (v *Vertex) PrintInOut()