ch

package module
v1.3.4 Latest Latest
Warning

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

 Go to latest Published: Mar 10, 2020 License: Apache-2.0 Imports: 14 Imported by: 2

README

GoDoc Build Status Sourcegraph Go Report Card GitHub tag

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

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

And then you are good to go

Usage

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

  • 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. UPD: done with osm2ch
  • Thoughts and discussions about OSM graph and extensions Need some ideas about parsing and preparing. UPD: osm2ch
  • Map matcher as another project WIP (now it is in local git storage)
  • Bring interfaces{} Thoughts (do we really need it?)
  • Bring OSM parser WIP It's done in poor way. PRs are welcome
  • Bring OSM restrictions WIP It's done in poor way. 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
  • Separate benchmarks to BENCHMARK.md 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

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

This section is empty.

Variables

This section is empty.

Functions

func PrepareGeoJSONLinestring added in v1.3.4 

func PrepareGeoJSONLinestring(pts []geoPoint) string

PrepareGeoJSONLinestring Creates GeoJSON LineString from set of points

func PrepareWKTLinestring added in v1.3.3 

func PrepareWKTLinestring(pts []geoPoint) string

PrepareWKTLinestring Creates WKT LineString from set of points

Types

type Distance 

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

func NewDistance 

func NewDistance() *Distance

type ExpandedGraph added in v1.3.3 

type ExpandedGraph map[int64]map[int64]expandedEdge

ExpandedGraph Representation of edge expanded graph 

map[newSourceVertexID]map[newTargetVertexID]newExpandedEdge

func ImportFromOSMFile added in v1.3.0 

func ImportFromOSMFile(fileName string, cfg *OsmConfiguration) (*ExpandedGraph, 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

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 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 {
	EntityName string // Currrently we support 'highway' only
	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

Directories

Path Synopsis
cmd
osm2ch

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.