ch

README

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, maneuver restrictions extension and isochrones estimation 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

• 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 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

Documentation

Index

• Constants
• Variables
• type ContractionPath
• type Distance
  • func NewDistance() *Distance
• type Graph
  • func ImportFromFile(edgesFname, verticesFname, contractionsFname string) (*Graph, error)
  • func (graph *Graph) AddEdge(from, to int64, weight float64) error
  • func (graph *Graph) AddTurnRestriction(from, via, to int64) error
  • func (graph *Graph) AddVertex(labelExternal, labelInternal int64) error
  • func (graph *Graph) ComputePath(middleID int64, prevF, prevR map[int64]int64) []int64
  • func (graph *Graph) CreateVertex(label int64) error
  • func (graph *Graph) ExportToFile(fname string) error
  • func (graph *Graph) FindVertex(labelExternal int64) (idx int64, ok bool)
  • func (graph *Graph) Freeze()
  • func (g *Graph) ImportRestrictionsFromFile(fname string) error
  • func (graph *Graph) IsShortcut(labelFromVertex, labelToVertex int64) (ok bool)
  • func (graph *Graph) Isochrones(source int64, maxCost float64) (map[int64]float64, error)
  • func (graph *Graph) PrepareContractionHierarchies()
  • func (graph *Graph) Preprocess() []int64
  • func (graph *Graph) ShortestPath(source, target int64) (float64, []int64)
  • func (graph *Graph) ShortestPathOneToMany(source int64, targets []int64) ([]float64, [][]int64)
  • func (graph *Graph) Unfreeze()
  • func (graph *Graph) VanillaShortestPath(source, target int64) (float64, []int64)
  • func (graph *Graph) VanillaTurnRestrictedShortestPath(source, target int64) (float64, []int64)
• type Vertex
  • func MakeVertex(label int64) *Vertex
  • func NewVertex(vertexNum int64) *Vertex
  • func (vertex *Vertex) Importance() int
  • func (vertex *Vertex) OrderPos() int
  • func (vertex *Vertex) SetImportance(importance int)
  • func (vertex *Vertex) SetOrderPos(orderPos int)

Constants

const DEBUG_PREPROCESSING = false

Variables

var (
	// ErrGraphIsFrozen Graph is frozen, so it can not be modified.
	ErrGraphIsFrozen = fmt.Errorf("Graph has been frozen")
)

Types

type ContractionPath

type ContractionPath struct {
	ViaVertex int64
	Cost      float64
}

ContractionPath

ViaVertex - ID of vertex through which the contraction exists Cost - summary cost of path between two vertices

type Distance

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

Distance Information about contraction between source vertex and contraction vertex

func NewDistance

func NewDistance() *Distance

NewDistance Constructor for 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 shortcuts Found and stored shortcuts based on contraction hierarchies

func ImportFromFile

func ImportFromFile(edgesFname, verticesFname, contractionsFname string) (*Graph, error)

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
f_internal - int64, Internal ID of source vertex
t_internal - int64, Internal ID of target vertex
weight - float64, Weight of an edge

Header of CSV-file containing information about vertices:

vertex_id - int64, ID of vertex
internal_id - int64, internal ID of target 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 contractios between vertices:

from_vertex_id - int64, ID of source vertex
to_vertex_id - int64, ID of arget vertex
f_internal - int64, Internal ID of source vertex
t_internal - int64, Internal ID of target vertex
weight - float64, Weight of an edge
via_vertex_id - int64, ID of vertex through which the contraction exists
v_internal - int64, Internal ID of vertex through which the contraction exists

func (*Graph) AddEdge

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

AddEdge Adds new edge 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) AddTurnRestriction

func (graph *Graph) AddTurnRestriction(from, via, to int64) error

AddTurnRestriction Adds new turn restriction between two vertices via some other vertex

from User's definied ID of source vertex via User's definied ID of prohibited vertex (between source and target) to User's definied ID of target vertex

func (*Graph) AddVertex

func (graph *Graph) AddVertex(labelExternal, labelInternal int64) error

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 int64, prevF, prevR map[int64]int64) []int64

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

func (*Graph) CreateVertex

func (graph *Graph) CreateVertex(label int64) error

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 edges CSV-file:

from_vertex_id - int64, ID of source vertex
to_vertex_id - int64, ID of target vertex
f_internal - int64, Internal ID of source vertex
t_internal - int64, Internal ID of target vertex
weight - float64, Weight of an edge

Header of vertices CSV-file:

vertex_id - int64, ID of vertex
internal_id - int64, Internal 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 contractios CSV-file:

from_vertex_id - int64, ID of source vertex
to_vertex_id - int64, ID of arget vertex
f_internal - int64, Internal ID of source vertex
t_internal - int64, Internal ID of target vertex
weight - float64, Weight of an edge
via_vertex_id - int64, ID of vertex through which the contraction exists
v_internal - int64, Internal ID of vertex through which the contraction exists

func (*Graph) FindVertex

func (graph *Graph) FindVertex(labelExternal int64) (idx int64, ok bool)

FindVertex Returns index of vertex in graph

labelExternal - User defined ID of vertex If vertex is not found then returns (-1; false)

func (*Graph) Freeze

func (graph *Graph) Freeze()

Freeze Freeze graph. Should be called after contraction hierarchies had been prepared.

func (*Graph) ImportRestrictionsFromFile

func (g *Graph) ImportRestrictionsFromFile(fname string) error

ImportRestrictionsFromFile Imports turn restrictions from file of CSV-format into graph

Header of CSV-file: from_vertex_id;via_vertex_id;to_vertex_id; int;int;int

func (*Graph) IsShortcut

func (graph *Graph) IsShortcut(labelFromVertex, labelToVertex int64) (ok bool)

IsShortcut Returns true if edge is a shortcut (edge defined as two vertices)

func (*Graph) Isochrones

func (graph *Graph) Isochrones(source int64, maxCost float64) (map[int64]float64, error)

Isochrones Returns set of vertices and corresponding distances restricted by maximum travel cost for source vertex source - source vertex (user defined label) maxCost - restriction on travel cost for breadth search See ref. https://wiki.openstreetmap.org/wiki/Isochrone and https://en.wikipedia.org/wiki/Isochrone_map Note: implemented breadth-first searching path algorithm does not guarantee shortest pathes to reachable vertices (until all edges have cost 1.0). See ref: https://en.wikipedia.org/wiki/Breadth-first_search Note: result for estimated costs could be also inconsistent due nature of data structure

func (*Graph) PrepareContractionHierarchies

func (graph *Graph) PrepareContractionHierarchies()

PrepareContractionHierarchies Compute contraction hierarchies

func (*Graph) Preprocess

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

Preprocess Computes contraction hierarchies and returns node ordering

func (*Graph) ShortestPath

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

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) ShortestPathOneToMany

func (graph *Graph) ShortestPathOneToMany(source int64, targets []int64) ([]float64, [][]int64)

ShortestPathOneToMany Computes and returns shortest path and it's cost (extended Dijkstra's algorithm) for one-to-many relation

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 targets User's definied IDs for target vertetices

func (*Graph) Unfreeze

func (graph *Graph) Unfreeze()

Unfreeze Freeze graph. Should be called if graph modification is needed.

func (*Graph) VanillaShortestPath

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

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

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

func (*Graph) VanillaTurnRestrictedShortestPath

func (graph *Graph) VanillaTurnRestrictedShortestPath(source, target int64) (float64, []int64)

VanillaTurnRestrictedShortestPath Computes and returns turns restricted 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

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

type Vertex

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

Vertex All information about vertex

func MakeVertex

func MakeVertex(label int64) *Vertex

MakeVertex Create vertex with label

func NewVertex

func NewVertex(vertexNum int64) *Vertex

NewVertex Create vertex with vertex number

func (*Vertex) Importance

func (vertex *Vertex) Importance() int

Importance Returns importance (in terms of contraction hierarchies) of vertex

func (*Vertex) OrderPos

func (vertex *Vertex) OrderPos() int

OrderPos Returns order position (in terms of contraction hierarchies) of vertex

func (*Vertex) SetImportance

func (vertex *Vertex) SetImportance(importance int)

SetImportance Sets order position (in terms of contraction hierarchies) for vertex

func (*Vertex) SetOrderPos

func (vertex *Vertex) SetOrderPos(orderPos int)

SetOrderPos Sets order position (in terms of contraction hierarchies) for vertex