ch

package module
v1.3.0 Latest Latest
Warning

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

 Go to latest Published: Dec 20, 2019 License: MIT Imports: 12 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.

For one-to-one query (ShortestPath):

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

For one-to-many query (ShortestPathOneToMany):

goos: linux
goarch: amd64
pkg: github.com/LdDl/ch
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/1/vertices-187853-20         	     160	   7175512 ns/op	 6773392 B/op	   14463 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/2/vertices-187853-20         	     176	   6847237 ns/op	 6773416 B/op	   14463 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/4/vertices-187853-20         	     172	   7101499 ns/op	 6773230 B/op	   14461 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/8/vertices-187853-20         	     181	   6706642 ns/op	 6773435 B/op	   14463 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/16/vertices-187853-20        	     170	   6915546 ns/op	 6773325 B/op	   14462 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/32/vertices-187853-20        	     174	   6887815 ns/op	 6773307 B/op	   14462 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/64/vertices-187853-20        	     174	   6964305 ns/op	 6773370 B/op	   14462 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/128/vertices-187853-20       	     168	   6916208 ns/op	 6773333 B/op	   14463 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/256/vertices-187853-20       	     170	   7161520 ns/op	 6773373 B/op	   14463 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/512/vertices-187853-20       	     172	   6710753 ns/op	 6773492 B/op	   14464 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/1024/vertices-187853-20      	     181	   6680762 ns/op	 6773273 B/op	   14462 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/2048/vertices-187853-20      	     171	   6695043 ns/op	 6773313 B/op	   14462 allocs/op
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/4096/vertices-187853-20      	     176	   6674091 ns/op	 6773373 B/op	   14462 allocs/op
PASS
ok  	github.com/LdDl/ch	33.806s

Also if you want to make comparison between OneToMany in term of ShortestPathOneToMany() and OneToMany in term of looping:

go test -benchmem -run=^$ github.com/LdDl/ch -bench BenchmarkOldWayShortestPathOneToMany > old.txt
go test -benchmem -run=^$ github.com/LdDl/ch -bench BenchmarkShortestPathOneToMany > new.txt
sed -i 's/BenchmarkOldWayShortestPathOneToMany/BenchmarkShortestPathOneToMany/g' old.txt

and then use benchcmp:

benchcmp old.txt new.txt

Output should be something like this:

benchmark                                                                                 old ns/op     new ns/op     delta
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/1/vertices-187853-20        10608955      7175512       -32.36%
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/2/vertices-187853-20        10813368      6847237       -36.68%
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/4/vertices-187853-20        10583636      7101499       -32.90%
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/8/vertices-187853-20        10500989      6706642       -36.13%
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/16/vertices-187853-20       10470206      6915546       -33.95%
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/32/vertices-187853-20       10421460      6887815       -33.91%
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/64/vertices-187853-20       10499903      6964305       -33.67%
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/128/vertices-187853-20      10735268      6916208       -35.57%
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/256/vertices-187853-20      10836504      7161520       -33.91%
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/512/vertices-187853-20      10544817      6710753       -36.36%
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/1024/vertices-187853-20     10619897      6680762       -37.09%
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/2048/vertices-187853-20     10772554      6695043       -37.85%
BenchmarkShortestPathOneToMany/CH_shortest_path_(one_to_many)/4096/vertices-187853-20     10257450      6674091       -34.93%

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 Propably not modify algorithm, but graph
  • Thoughts and discussions about OSM graph and extensions Need some ideas about parsing and preparing
  • Map matcher as another project WIP
  • Bring interfaces{} Thoughts
  • Bring OSM parser WIP It exists, now need restrictions handle
  • Bring OSM restrictions WIP PRs are welcome
  • OneTwoMany function (contraction hierarchies) Done, may be some bench comparisons
  • ManyToMany function (contraction hierarchies) Thoughts
  • Replace int with int64 (OSM purposes) Done

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

View Source 
const (
	EarthRadius = 6370.986884258304
)

Variables

This section is empty.

Functions

func DistanceBetweenPoints added in v1.3.0 

func DistanceBetweenPoints(p, q Coord) float64

Types

type Coord added in v1.3.0 

type Coord struct {
	Lat float64
	Lon float64
}

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

func ImportFromOSMFile(fileName string, cfg *OsmConfiguration) (*Graph, error)

ImportFromOSMFile Imports graph from file of PBF-format (in OSM terms) 

File should have PBF (Protocolbuffer Binary Format) extension according to https://github.com/paulmach/osm

func (*Graph) AddEdge 

func (graph *Graph) AddEdge(from, to int64, 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 int64)

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)

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)

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() []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 added in v1.2.8 

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

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

type OsmConfiguration struct {
	TagName string
	Tags    []string
}

OsmConfiguration Allows to filter ways by certain tags from OSM data

func (*OsmConfiguration) CheckTag added in v1.3.0 

func (cfg *OsmConfiguration) CheckTag(tag string) bool

CheckTag Checks if incoming tag is represented in configuration

type Vertex 

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

func MakeVertex 

func MakeVertex(label int64) *Vertex

func NewVertex 

func NewVertex(vertexNum int64) *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.