ch

package module
v1.2.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Oct 14, 2019 License: MIT Imports: 9 Imported by: 2

README

GoDoc Build Status

ch - Contraction Hierarchies

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

This library provides classic implementation of Dijkstra's algorithm and turn restrictions extension also.

Table of Contents

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

Benchmark

My PC is:

Processor: Intel(R) Core(TM) i9-7900X CPU @ 3.30GHz x 10
Memory: 46.8GiB
Linux Kernel: 4.15.0-20-generic
OS: Linux Mint 19.1 Cinnamon

I have used graph with ~187k vertices for benchmark.

goos: linux
goarch: amd64
pkg: github.com/LdDl/ch
BenchmarkShortestPath/CH_shortest_path/1/vertices-187853-20         	     500	   2801587 ns/op	 3532241 B/op	    2225 allocs/op
BenchmarkShortestPath/CH_shortest_path/2/vertices-187853-20         	    1000	   2639499 ns/op	 3532225 B/op	    2225 allocs/op
BenchmarkShortestPath/CH_shortest_path/4/vertices-187853-20         	    1000	   2730468 ns/op	 3532239 B/op	    2225 allocs/op
BenchmarkShortestPath/CH_shortest_path/8/vertices-187853-20         	     500	   2887250 ns/op	 3532254 B/op	    2225 allocs/op
BenchmarkShortestPath/CH_shortest_path/16/vertices-187853-20        	     500	   2292956 ns/op	 3532251 B/op	    2225 allocs/op
BenchmarkShortestPath/CH_shortest_path/32/vertices-187853-20        	     500	   2837590 ns/op	 3532247 B/op	    2225 allocs/op
BenchmarkShortestPath/CH_shortest_path/64/vertices-187853-20        	     500	   2649959 ns/op	 3532233 B/op	    2225 allocs/op
BenchmarkShortestPath/CH_shortest_path/128/vertices-187853-20       	     500	   2790797 ns/op	 3532215 B/op	    2225 allocs/op
BenchmarkShortestPath/CH_shortest_path/256/vertices-187853-20       	     500	   2640733 ns/op	 3532231 B/op	    2225 allocs/op
BenchmarkShortestPath/CH_shortest_path/512/vertices-187853-20       	     500	   2381726 ns/op	 3532224 B/op	    2225 allocs/op
BenchmarkShortestPath/CH_shortest_path/1024/vertices-187853-20      	     500	   2810581 ns/op	 3532223 B/op	    2225 allocs/op
BenchmarkShortestPath/CH_shortest_path/2048/vertices-187853-20      	     500	   2770308 ns/op	 3532203 B/op	    2225 allocs/op
BenchmarkShortestPath/CH_shortest_path/4096/vertices-187853-20      	     500	   2592263 ns/op	 3532234 B/op	    2225 allocs/op
PASS
ok  	github.com/LdDl/ch	34.153s

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
  • Turn Restricted Shortest Path extension for CH-algorithm
  • Turn restrictions import (probably as CSV again)
  • Thoughts and discussions about OSM graph and extensions Need some ideas about parsing and preparing
  • Map matcher as another project WIP
  • Bring interfaces{} WIP
  • Bring OSM parser 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

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

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 main 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 (-1 if no contraction)
v_internal - int64, Internal ID of vertex through which the contraction exists (-1 if no contraction)

func (*Graph) AddEdge 

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

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 added in v1.2.0 

func (graph *Graph) AddTurnRestriction(from, via, to int)

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 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 main 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 (-1 if no contraction)
v_internal - int64, Internal ID of vertex through which the contraction exists (-1 if no contraction)

func (*Graph) ImportRestrictionsFromFile added in v1.2.1 

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

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

func (*Graph) VanillaTurnRestrictedShortestPath added in v1.2.0 

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

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

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.