ch

package module
v1.7.8 Latest Latest
Warning

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

 Go to latest Published: Jun 6, 2023 License: Apache-2.0 Imports: 11 Imported by: 2

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

Documentation

Index

Constants

View Source 
const (
	Infinity = float64(^uint(0) >> 1)
)

Variables

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

Functions

This section is empty.

Types

type Distance 

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

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)

func NewDistance 

func NewDistance() Distance

NewDistance Constructor for Distance

type Graph 

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

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

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

func NewGraph added in v1.7.8 

func NewGraph() *Graph

NewGraph returns pointer to created Graph and does preallocations for processing purposes

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

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

AddShortcut Adds new shortcut between two vertices

from - User's definied ID of first vertex of shortcut to - User's definied ID of last vertex of shortcut via - User's defined ID of vertex through which the shortcut exists weight - User's definied weight of shortcut

func (*Graph) AddTurnRestriction added in v1.2.0 

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

func (graph *Graph) ComputePath(middleID int64, forwardPrev, backwardPrev 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) ExportEdgesToFile added in v1.7.5 

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

ExportVerticesToFile Exports edges information to CSV-file with header: 

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

func (*Graph) ExportShortcutsToFile added in v1.7.5 

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

ExportShortcutsToFile Exports shortcuts information to CSV-file with header: 

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

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
weight - float64, Weight of an edge

Header of vertices CSV-file: 

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

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

func (*Graph) ExportVerticesToFile added in v1.7.5 

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

ExportVerticesToFile Exports vertices information to CSV-file with header: 

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)

func (*Graph) FindVertex added in v1.7.3 

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

func (graph *Graph) Freeze()

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

func (*Graph) GetEdgesNum added in v1.7.7 

func (graph *Graph) GetEdgesNum() int64

GetEdgesNum Returns number of edges in graph

func (*Graph) GetShortcutsNum added in v1.7.7 

func (graph *Graph) GetShortcutsNum() int64

GetShortcutsNum Returns number of shortcuts in graph

func (*Graph) GetVerticesNum added in v1.7.7 

func (graph *Graph) GetVerticesNum() int64

GetVerticesNum Returns number of vertices in graph

func (*Graph) ImportRestrictionsFromFile added in v1.2.1 

func (graph *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) Isochrones added in v1.6.0 

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

func (graph *Graph) PrepareContractionHierarchies()

PrepareContractionHierarchies Compute contraction hierarchies

func (*Graph) Preprocess 

func (graph *Graph) Preprocess(pqImportance *importanceHeap)

Preprocess Computes contraction hierarchies and returns node ordering

func (*Graph) SetVerbose added in v1.7.8 

func (graph *Graph) SetVerbose(flag bool)

SetVerbose sets verbose parameter for debugging purposes

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

func (graph *Graph) ShortestPathManyToMany(sources, targets []int64) ([][]float64, [][][]int64)

ShortestPathManyToMany computes and returns shortest paths and theirs's costs (extended Dijkstra's algorithm) between multiple sources and targets

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

sources - set of user's definied IDs of source vertices targets - set of user's definied IDs of target vertices

func (*Graph) ShortestPathManyToManyWithAlternatives added in v1.7.8 

func (graph *Graph) ShortestPathManyToManyWithAlternatives(sourcesAlternatives, targetsAlternatives [][]VertexAlternative) ([][]float64, [][][]int64)

ShortestPathManyToManyWithAlternatives Computes and returns shortest paths and their cost (extended Dijkstra's algorithm), with multiple alternatives for source and target vertices with additional distances to reach the vertices (useful if source and target are outside of the graph)

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

sourcesAlternatives - set of user's definied IDs of source vertices with additional penalty targetsAlternatives - set of user's definied IDs of target vertices with additional penalty

func (*Graph) ShortestPathOneToMany added in v1.2.8 

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

ShortestPathOneToMany computes and returns shortest paths and theirs's costs (extended Dijkstra's algorithm) between single source and multiple targets

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 - set of user's definied IDs of target vertices

func (*Graph) ShortestPathOneToManyWithAlternatives added in v1.7.8 

func (graph *Graph) ShortestPathOneToManyWithAlternatives(sourceAlternatives []VertexAlternative, targetsAlternatives [][]VertexAlternative) ([]float64, [][]int64)

ShortestPathOneToManyWithAlternatives Computes and returns shortest path and it's cost (extended Dijkstra's algorithm) between single source and multiple targets with multiple alternatives for source and target vertices with additional distances to reach the vertices (useful if source and target are outside of the graph)

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

sourceAlternatives - user's definied ID of source vertex with additional penalty targetsAlternatives - set of user's definied IDs of target vertices with additional penalty

func (*Graph) ShortestPathWithAlternatives added in v1.7.8 

func (graph *Graph) ShortestPathWithAlternatives(sources, targets []VertexAlternative) (float64, []int64)

ShortestPathWithAlternatives Computes and returns shortest path and it's cost (extended Dijkstra's algorithm), with multiple alternatives for source and target vertices with additional distances to reach the vertices (useful if source and target are outside of the graph)

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

sources - user's definied ID of source vertex with additional penalty targets - user's definied ID of target vertex with additional penalty

func (*Graph) Unfreeze added in v1.5.0 

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

type ShortcutPath struct {
	From int64
	To   int64
	Via  int64
	Cost float64
}

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

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 (*Vertex) Importance added in v1.7.0 

func (vertex *Vertex) Importance() int

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

func (*Vertex) OrderPos added in v1.7.0 

func (vertex *Vertex) OrderPos() int64

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

func (*Vertex) SetImportance added in v1.7.0 

func (vertex *Vertex) SetImportance(importance int)

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

func (*Vertex) SetOrderPos added in v1.7.0 

func (vertex *Vertex) SetOrderPos(orderPos int64)

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

type VertexAlternative added in v1.7.8 

type VertexAlternative struct {
	Label              int64
	AdditionalDistance float64
}

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.