ch

package module
v1.10.0 Latest Latest
Warning

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

 Go to latest Published: Nov 29, 2025 License: Apache-2.0 Imports: 12 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
  • Dynamic edge weight updates (lightweight recustomization)

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

And then you are good to go

Usage

  • Shortest path (single-threaded)

    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

  • Shortest path (thread-safe for concurrent use)

    Please see this test file

    If you need to execute shortest path queries from multiple goroutines concurrently, use the QueryPool API:

    g := Graph{} // Prepare variable for storing graph
graphFromCSV(&g, "data/pgrouting_osm.csv") // Import CSV-file file into programm
g.PrepareContractionHierarchies() // Compute contraction hierarchies

pool := g.NewQueryPool() // Create a query pool for concurrent access

// Now you can safely call from multiple goroutines:
ans, path := pool.ShortestPath(u, v)

// One-to-many queries are also supported:
costs, paths := pool.ShortestPathOneToMany(source, targets)

    Important: The default Graph.ShortestPath() method is NOT thread-safe. If you call it from multiple goroutines without synchronization, you may get incorrect results. Use QueryPool for concurrent scenarios.

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

  • Dynamic edge weight updates (Recustomization)

    Please see this test file

    This feature allows you to update edge weights without rebuilding the entire contraction hierarchy. Useful for:

    • Traffic updates (congestion, accidents and other events)
    • Time-dependent routing
    g := Graph{}
graphFromCSV(&g, "data/pgrouting_osm.csv")
g.PrepareContractionHierarchies()

// Single update with immediate recustomization
err := g.UpdateEdgeWeight(fromVertex, toVertex, newWeight, true)

// Batch updates (more efficient for multiple changes)
g.UpdateEdgeWeight(edge1From, edge1To, weight1, false)
g.UpdateEdgeWeight(edge2From, edge2To, weight2, false)
g.UpdateEdgeWeight(edge3From, edge3To, weight3, false)
g.Recustomize() // Apply all changes at once

    When to use single vs batch updates:

    Scenario Method Why
    One edge changed UpdateEdgeWeight(..., true) Simple, immediate
    Multiple edges changed Batch + Recustomize() Faster, single pass
    Real-time traffic feed Batch + periodic Recustomize() Amortize cost

    How it works:

    flowchart TB
subgraph Preprocessing["Preprocessing (one-time)"]
    P1[Build CH with importance ordering] --> P2[Store contractionOrder array]
    P2 --> P3[Index shortcuts by Via vertex<br/>shortcutsByVia map]
end

subgraph Update["UpdateEdgeWeight call"]
    U1[Convert user labels to internal IDs] --> U2[Update edge weight in<br/>outIncidentEdges & inIncidentEdges]
    U2 --> U3{needRecustom?}
    U3 -->|Yes| R1
    U3 -->|No| U4[Return - batch mode]
end

subgraph Recustomize["Recustomize call"]
    R1[For each vertex V in contractionOrder] --> R2[Get shortcuts via V<br/>from shortcutsByVia]
    R2 --> R3[For each shortcut A => C via V]
    R3 --> R4["newCost = cost(A => V) + cost(V => C)"]
    R4 --> R5[Update shortcut.Cost]
    R5 --> R6[Update incident edges]
    R6 --> R3
end

P3 --> U1
R6 -.->|next vertex| R1

    Processing in contraction order ensures that when updating shortcut A => C via V, the edges A => V and V => C (which might themselves be shortcuts) have already been updated.

    Note: This is a lightweight recustomization inspired by Customizable Contraction Hierarchies (Dibbelt, Strasser, Wagner), but uses the existing importance-based ordering instead of nested dissection. It's simpler and requires no external dependencies, while still providing efficient metric updates.

    In future may be added full CCH support with nested dissection ordering (need to investigate METIS or similar libraries for graph partitioning).

If you want to import OSM (Open Street Map) file then follow instructions for osm2ch
Custom import with pre-computed CH

If you have your own import logic (e.g., reading additional data like GeoJSON coordinates alongside the graph), you need to call FinalizeImport() after loading all vertices, edges, and shortcuts:

graph := ch.NewGraph()

// Your custom import logic:
// - CreateVertex() for each vertex
// - AddEdge() for each edge
// - SetOrderPos() and SetImportance() for each vertex
// - AddShortcut() for each shortcut

graph.FinalizeImport() // Required for recustomization support

// Now graph is ready for queries and UpdateEdgeWeight/Recustomize

This is required because FinalizeImport() builds internal data structures (contractionOrder, shortcutsByVia) needed for dynamic edge weight updates.

If you use the built-in ImportFromFile() function, this is called automatically.

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

Customizable Contraction Hierarchies - Dibbelt, Strasser, Wagner (2014). The recustomization feature in this library is inspired by CCH concepts.

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")
	// ErrCHNotPrepared Contraction hierarchies have not been prepared yet.
	ErrCHNotPrepared = fmt.Errorf("Contraction hierarchies have not been prepared")
	// ErrVertexNotFound Vertex with given label was not found in graph.
	ErrVertexNotFound = fmt.Errorf("Vertex not found")
	// ErrEdgeNotFound Edge between given vertices was not found.
	ErrEdgeNotFound = fmt.Errorf("Edge not found")
)
View Source 
var (
	ErrNotEnoughColumns = fmt.Errorf("not enough columns")
	ErrColumnNotFound   = fmt.Errorf("column not found")
)

Functions

This section is empty.

Types

type CSVHeaderImportEdges added in v1.8.0 

type CSVHeaderImportEdges struct {
	SourceExternal int
	TargetExternal int
	Weight         int
}

CSVHeaderImportEdges is just an helper structure to evaluate CSV columns for edges file

type CSVHeaderImportShortcuts added in v1.8.0 

type CSVHeaderImportShortcuts struct {
	SourceExternal int
	TargetExternal int
	ViaExternal    int
	Weight         int
}

CSVHeaderImportShortcuts is just an helper structure to evaluate CSV columns for shortcuts file

type CSVHeaderImportVertices added in v1.8.0 

type CSVHeaderImportVertices struct {
	ID         int
	OrderPos   int
	Importance int
}

CSVHeaderImportVertices is just an helper structure to evaluate CSV columns for vertices file

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

func (graph *Graph) FinalizeImport()

FinalizeImport should be called after manually importing a pre-computed CH graph. It builds the contractionOrder from vertices' orderPos values, sets up recustomization support structures, marks CH as prepared, and freezes the graph.

Use this when you have your own import logic (e.g., reading additional data like GeoJSON coordinates) instead of using ImportFromFile().

Example: 

graph := ch.NewGraph()
// ... your custom import logic: CreateVertex, AddEdge, SetOrderPos, SetImportance, AddShortcut ...
graph.FinalizeImport()
// Now graph is ready for queries and recustomization

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

func (graph *Graph) NewQueryPool() *QueryPool

NewQueryPool creates a new QueryPool for concurrent query execution. The pool lazily initializes QueryState objects as needed.

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

func (graph *Graph) Recustomize() error

Recustomize Recomputes all shortcut costs based on current edge weights. This is useful after edge weights have been modified (e.g., traffic updates). The contraction order is preserved - only the metric (costs) is updated.

Returns error if CH has not been prepared yet.

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

func (graph *Graph) UpdateEdgeWeight(from, to int64, weight float64, needRecustom bool) error

UpdateEdgeWeight Updates the weight of an existing edge in the graph. This function works with user-defined vertex labels.

from - User's defined ID of source vertex to - User's defined ID of target vertex weight - New weight for the edge needRecustom - If true, Recustomize() is called automatically after update

Returns error if edge is not found or if recustomization fails.

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

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

QueryPool provides thread-safe access to pooled QueryState objects. Use this when you need to call shortest path queries from multiple goroutines.

func (*QueryPool) ShortestPath added in v1.8.0 

func (qp *QueryPool) ShortestPath(source, target int64) (float64, []int64)

ShortestPath computes shortest path using a pooled QueryState (thread-safe). This method can be safely called from multiple goroutines concurrently.

source - user's defined ID of source vertex target - user's defined ID of target vertex

func (*QueryPool) ShortestPathManyToMany added in v1.10.0 

func (qp *QueryPool) ShortestPathManyToMany(sources, targets []int64) ([][]float64, [][][]int64)

ShortestPathManyToMany computes shortest paths between multiple sources and targets (thread-safe). This method can be safely called from multiple goroutines concurrently.

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

func (*QueryPool) ShortestPathManyToManyWithAlternatives added in v1.10.0 

func (qp *QueryPool) ShortestPathManyToManyWithAlternatives(sourcesAlternatives, targetsAlternatives [][]VertexAlternative) ([][]float64, [][][]int64)

ShortestPathManyToManyWithAlternatives computes shortest paths with alternatives (thread-safe). This method can be safely called from multiple goroutines concurrently.

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

func (*QueryPool) ShortestPathOneToMany added in v1.8.0 

func (qp *QueryPool) ShortestPathOneToMany(source int64, targets []int64) ([]float64, [][]int64)

ShortestPathOneToMany computes shortest paths from single source to multiple targets (thread-safe). This method can be safely called from multiple goroutines concurrently.

source - user's defined ID of source vertex targets - set of user's defined IDs of target vertices

func (*QueryPool) ShortestPathOneToManyWithAlternatives added in v1.8.0 

func (qp *QueryPool) ShortestPathOneToManyWithAlternatives(sourceAlternatives []VertexAlternative, targetsAlternatives [][]VertexAlternative) ([]float64, [][]int64)

ShortestPathOneToManyWithAlternatives computes shortest paths with alternatives (thread-safe). This method can be safely called from multiple goroutines concurrently.

func (*QueryPool) ShortestPathWithAlternatives added in v1.8.0 

func (qp *QueryPool) ShortestPathWithAlternatives(sources, targets []VertexAlternative) (float64, []int64)

ShortestPathWithAlternatives computes shortest path with multiple source/target alternatives (thread-safe). This method can be safely called from multiple goroutines concurrently.

sources - user's defined source vertices with additional penalties targets - user's defined target vertices with additional penalties

type QueryState added in v1.8.0 

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

QueryState holds all the buffers needed for a single shortest path query. This is used by the thread-safe query methods to avoid sharing state between goroutines.

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.