path

package
v0.0.0-...-d8ed7c5 Latest Latest
Warning

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

 Go to latest Published: Apr 2, 2023 License: MIT Imports: 14 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func ConvertToNodeOrdering 

func ConvertToNodeOrdering(nodeOrderingString string) [][]int

Parse a string to a lsit which specifies the node order

func ReadNodeOrderingFile 

func ReadNodeOrderingFile(filename string) [][]int

Read a node ordering file and return the node order

Types

type BidirectionalConnection 

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

Describes the connection of a bidirectional search

func (*BidirectionalConnection) Reset 

func (con *BidirectionalConnection) Reset()

Reset/invalidate the connection

type ContractionHierarchies 

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

Provides the precomputation and query for shortest paths with the use of Contraction Hierarchies. Implements the Navigator Interface.

func NewContractionHierarchies 

func NewContractionHierarchies(g graph.Graph, dijkstra *UniversalDijkstra, options ContractionOptions) *ContractionHierarchies

Create a new Contraction Hierarchy. Before a query can get executed, the Precomputation has to be done

func NewContractionHierarchiesInitialized 

func NewContractionHierarchiesInitialized(g graph.Graph, dijkstra *UniversalDijkstra, shortcuts []Shortcut, nodeOrdering [][]int, pathFindingOptions PathFindingOptions) *ContractionHierarchies

Create a new Contraction Hierarchy which is already initialized with the shortcuts and node ordering. This can directly start a new query

func (*ContractionHierarchies) ComputeShortestPath 

func (ch *ContractionHierarchies) ComputeShortestPath(origin, destination graph.NodeId) int

Compute the shortest path for the given query (from origin to destination node). It returns the length of the path. If no path was found, -1 is returned

func (*ContractionHierarchies) GetEdgeRelaxations 

func (ch *ContractionHierarchies) GetEdgeRelaxations() int

Get the number of relaxed edges

func (*ContractionHierarchies) GetGraph 

func (ch *ContractionHierarchies) GetGraph() graph.Graph

get the used graph

func (*ContractionHierarchies) GetPath 

func (ch *ContractionHierarchies) GetPath(origin, destination graph.NodeId) []int

Get the computed path. A slice is returned which contains the node IDs in order from source to target

func (*ContractionHierarchies) GetPqPops 

func (ch *ContractionHierarchies) GetPqPops() int

Get the number of pq pops (from the priority queue)

func (*ContractionHierarchies) GetPqUpdates 

func (ch *ContractionHierarchies) GetPqUpdates() int

Get the number of the pq updates

func (*ContractionHierarchies) GetRelaxationAttempts 

func (ch *ContractionHierarchies) GetRelaxationAttempts() int

Get the number for how many edges the relaxation was tested (but maybe early terminated)

func (*ContractionHierarchies) GetSearchSpace 

func (ch *ContractionHierarchies) GetSearchSpace() []*DijkstraItem

Get the search space of the path finding query S slice is returned which contains all settled nodes of the query (containing the search information, e.g. distance to source node, which search direction was used for this item, ...)

func (*ContractionHierarchies) GetShortcuts 

func (ch *ContractionHierarchies) GetShortcuts() []Shortcut

Get the calculated shortcuts.

func (*ContractionHierarchies) GetStalledNodesCount 

func (ch *ContractionHierarchies) GetStalledNodesCount() int

Get the number of stalled nodes (invocations)

func (*ContractionHierarchies) GetUnstalledNodesCount 

func (ch *ContractionHierarchies) GetUnstalledNodesCount() int

Get the number of unstalled nodes (invocations)

func (*ContractionHierarchies) Precompute 

func (ch *ContractionHierarchies) Precompute(givenNodeOrder []int, oo OrderOptions)

Do the precomputation of the Contraction Hierarchies. This adds new Edges in the graph by adding shortcuts. The result will be a modified graph, a collection of shortcuts and the calculated node ordering. If givenNodeOrder is not nil, the OrderOption oo are ignored. givenNodeOrder predefines the order of the nodes. oo defines how the node ordering will be calculated.

func (*ContractionHierarchies) SetDebugLevel 

func (ch *ContractionHierarchies) SetDebugLevel(level int)

Set the debug level

func (*ContractionHierarchies) SetNodeOrdering 

func (ch *ContractionHierarchies) SetNodeOrdering(nodeOrdering [][]int)

Set the node ordering by an already available list. This is used when one has already a contracted graph and one need to define in which order the nodes were contracted. the index of the list reflects to the node id, the value to the level/position, when the node was contracted.

func (*ContractionHierarchies) SetPrecomputationMilestones 

func (ch *ContractionHierarchies) SetPrecomputationMilestones(milestones []float64)

Set the precomputation milestones (which are worth a log message)

func (*ContractionHierarchies) SetShortcuts 

func (ch *ContractionHierarchies) SetShortcuts(shortcuts []Shortcut)

Set the shortcuts by an already available list. This is used when one has already a contracted graph and one need to define which arcs are shortcuts.

func (*ContractionHierarchies) SetSortArcs 

func (ch *ContractionHierarchies) SetSortArcs(sort bool)

Set if the arcs should be sorted flag indicating if the arcs are sorted according if they are enabled or not (list will contain enabled arcs, then disabled arcs)

func (*ContractionHierarchies) ShortestPathSetup 

func (ch *ContractionHierarchies) ShortestPathSetup(options PathFindingOptions)

Setup ch to compute the shortest path

func (*ContractionHierarchies) WriteContractionResult 

func (ch *ContractionHierarchies) WriteContractionResult()

Write the contraciotn resutl (graph, shortcuts, node ordering) to a file

func (*ContractionHierarchies) WriteGraph 

func (ch *ContractionHierarchies) WriteGraph()

Write the graph to a file

func (*ContractionHierarchies) WriteNodeOrdering 

func (ch *ContractionHierarchies) WriteNodeOrdering()

Write the node ordering to a file

func (*ContractionHierarchies) WriteShortcuts 

func (ch *ContractionHierarchies) WriteShortcuts()

Write the shortcuts to a file

type ContractionOptions 

type ContractionOptions struct {
	Bidirectional      bool    // use bidirectional search
	UseHeuristic       bool    // use astar
	HotStart           bool    // use hot start
	MaxNumSettledNodes int     // limit the number of settled nodes. If this is reached a shortcut is added
	ContractionLimit   float64 // upper bound (in %) until which limit the nodes are contracted. If this is 99, only the contraction from level 0 to 99 is calculated
	ContractionWorkers int     // set the number of contraction workers who parallely compute the contraction
	UseCache           bool    // use a cache to store already known shortcuts for uncontracted nodes
}

Colleciton/Options how to contract the nodes. can be used as tuning options

func MakeDefaultContractionOptions 

func MakeDefaultContractionOptions() ContractionOptions

Make default contraction options

type ContractionProgress 

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

Contains the contraction progress information

type ContractionResult 

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

Contrains the result of a (computed, virtual) node contraction

type Dijkstra 

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

func NewDijkstra 

func NewDijkstra(g graph.Graph) *Dijkstra

func (*Dijkstra) ComputeShortestPath 

func (d *Dijkstra) ComputeShortestPath(origin, destination int) int

func (*Dijkstra) GetEdgeRelaxations 

func (d *Dijkstra) GetEdgeRelaxations() int

func (*Dijkstra) GetGraph 

func (d *Dijkstra) GetGraph() graph.Graph

func (*Dijkstra) GetPath 

func (d *Dijkstra) GetPath(origin, destination graph.NodeId) []graph.NodeId

func (*Dijkstra) GetPqPops 

func (d *Dijkstra) GetPqPops() int

func (*Dijkstra) GetPqUpdates 

func (d *Dijkstra) GetPqUpdates() int

func (*Dijkstra) GetRelaxationAttempts 

func (d *Dijkstra) GetRelaxationAttempts() int

func (*Dijkstra) GetSearchSpace 

func (d *Dijkstra) GetSearchSpace() []*DijkstraItem

func (*Dijkstra) GetStalledNodesCount 

func (d *Dijkstra) GetStalledNodesCount() int

func (*Dijkstra) GetUnstalledNodesCount 

func (d *Dijkstra) GetUnstalledNodesCount() int

type DijkstraItem 

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

implements queue.Priorizable

func NewDijkstraItem 

func NewDijkstraItem(nodeId graph.NodeId, distance int, predecessor graph.NodeId, heuristic int, searchDirection Direction) *DijkstraItem

func (*DijkstraItem) Index 

func (item *DijkstraItem) Index() int

func (*DijkstraItem) NodeId 

func (item *DijkstraItem) NodeId() graph.NodeId

func (*DijkstraItem) Priority 

func (item *DijkstraItem) Priority() int

func (*DijkstraItem) SetIndex 

func (item *DijkstraItem) SetIndex(index int)

func (*DijkstraItem) String 

func (item *DijkstraItem) String() string

type Direction 

type Direction bool
const (
	FORWARD  Direction = false
	BACKWARD Direction = true
)

func (Direction) String 

func (d Direction) String() string

type Milestone 

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

Contains information for a milestone. Helpful for debugging/storing progress 

type Navigator interface {
	GetPath(origin, destination int) []int           // Get the path of a previous computation. This contains the nodeIds which lie on the path from source to destination
	ComputeShortestPath(origin, destination int) int // Compute the shortest path from the origin to the destination
	GetSearchSpace() []*DijkstraItem                 // Returns the search space of a previous computation. This contains all items which were settled.
	GetPqPops() int                                  // Returns the amount of priority queue/heap pops which werer performed during the search
	GetPqUpdates() int                               // Get the number of pq updates
	GetEdgeRelaxations() int                         // Get the number of relaxed edges
	GetRelaxationAttempts() int                      // Get the number of attempted edge relaxations (some may early terminated)
	GetGraph() graph.Graph                           // Get the used graph
	GetStalledNodesCount() int                       // Get the number of stalled nodes (invocations)
	GetUnstalledNodesCount() int                     // Get the number of unstalled nodes (invocations)
}

type OrderItem 

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

implement queue.Priorizable

func NewOrderItem 

func NewOrderItem(nodeId graph.NodeId) *OrderItem

func (*OrderItem) Index 

func (o *OrderItem) Index() int

func (*OrderItem) NodeId 

func (o *OrderItem) NodeId() graph.NodeId

func (*OrderItem) Priority 

func (o *OrderItem) Priority() int

func (*OrderItem) SetIndex 

func (o *OrderItem) SetIndex(i int)

func (*OrderItem) String 

func (o *OrderItem) String() string

type OrderOptions 

type OrderOptions byte

Provides different options how the NodeOrder can get computed

func MakeOrderOptions 

func MakeOrderOptions() OrderOptions

Create a new OrderOptions (which in initially empty)

func (OrderOptions) ConsiderEdgeDifference 

func (oo OrderOptions) ConsiderEdgeDifference() bool

func (OrderOptions) ConsiderProcessedNeighbors 

func (oo OrderOptions) ConsiderProcessedNeighbors() bool

func (OrderOptions) IsLazyUpdate 

func (oo OrderOptions) IsLazyUpdate() bool

func (OrderOptions) IsPeriodic 

func (oo OrderOptions) IsPeriodic() bool

func (OrderOptions) IsRandom 

func (oo OrderOptions) IsRandom() bool

func (OrderOptions) IsValid 

func (oo OrderOptions) IsValid() bool

func (OrderOptions) Reset 

func (oo OrderOptions) Reset(o OrderOptions) OrderOptions

Reset the defined options and return a new OrderOptions

func (OrderOptions) Set 

func (oo OrderOptions) Set(o OrderOptions) OrderOptions

Set the defined options and return a new OrderOptions

func (OrderOptions) SetEdgeDifference 

func (oo OrderOptions) SetEdgeDifference(flag bool) OrderOptions

func (OrderOptions) SetLazyUpdate 

func (oo OrderOptions) SetLazyUpdate(flag bool) OrderOptions

Set the dynamic option and return a new OrderOptions

func (OrderOptions) SetPeriodic 

func (oo OrderOptions) SetPeriodic(flag bool) OrderOptions

func (OrderOptions) SetProcessedNeighbors 

func (oo OrderOptions) SetProcessedNeighbors(flag bool) OrderOptions

func (OrderOptions) SetRandom 

func (oo OrderOptions) SetRandom(flag bool) OrderOptions

func (OrderOptions) SetUpdateNeighbors 

func (oo OrderOptions) SetUpdateNeighbors(flag bool) OrderOptions

func (OrderOptions) UpdateNeighbors 

func (oo OrderOptions) UpdateNeighbors() bool

type PathFindingOptions 

type PathFindingOptions struct {
	Manual        bool // do an independent forward and backward search and check the connection manually
	UseHeuristic  bool // TODO use astar
	StallOnDemand int  // define the level for stall on demand (See UniversalDijkstra for more information)
	SortArcs      bool // sort the arcs to only consider the active edges
}

Collection/Options how to search for the path. Can be used as tuning parameters

func MakeDefaultPathFindingOptions 

func MakeDefaultPathFindingOptions() PathFindingOptions

Make default path finding options

type SearchKPIs 

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

func (*SearchKPIs) Reset 

func (kpi *SearchKPIs) Reset()

Reset the kpi

type SearchOptions 

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

type SearchStats 

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

func (*SearchStats) Reset 

func (stats *SearchStats) Reset(size int, stallLevel int)

Reset the search stats

type Shortcut 

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

Describes a shortcut. It contains the information of the source and target node and via which node this shortcut is spanned

func ConvertToShortcuts 

func ConvertToShortcuts(shortcutsString string) []Shortcut

Parse a string to a list of shortcuts

func ReadShortcutFile 

func ReadShortcutFile(filename string) []Shortcut

Read a shortcuts file and return the list of shortcuts

type UniversalDijkstra 

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

UniversalDijkstra implements various path finding algorithms which all are based on Dijkstra. it can be used for plain Dijsktra, Bidirectional search, A* (and maybe more will come). Implements the Navigator Interface.

func NewUniversalDijkstra 

func NewUniversalDijkstra(g graph.Graph) *UniversalDijkstra

Create a new Dijkstra instance with the given graph g

func (*UniversalDijkstra) ComputeShortestPath 

func (d *UniversalDijkstra) ComputeShortestPath(origin, destination graph.NodeId) int

Compute the shortest path from the origin to the destination. It returns the length of the found path If no path was found, it returns -1 If the path to all possible target is calculated (set target to -1), it returns 0

func (*UniversalDijkstra) GetEdgeRelaxations 

func (d *UniversalDijkstra) GetEdgeRelaxations() int

Get the number of relaxed edges

func (*UniversalDijkstra) GetGraph 

func (d *UniversalDijkstra) GetGraph() graph.Graph

Get the used graph

func (*UniversalDijkstra) GetPath 

func (d *UniversalDijkstra) GetPath(origin, destination int) []int

Get the path of a previous computation. This contains the nodeIds which lie on the path from source to destination

func (*UniversalDijkstra) GetPqPops 

func (d *UniversalDijkstra) GetPqPops() int

Returns the amount of priority queue/heap pops which werer performed during the search

func (*UniversalDijkstra) GetPqUpdates 

func (d *UniversalDijkstra) GetPqUpdates() int

Get the number of pq updates

func (*UniversalDijkstra) GetRelaxationAttempts 

func (d *UniversalDijkstra) GetRelaxationAttempts() int

Get the number of attempted edge relaxations (some may early terminated)

func (*UniversalDijkstra) GetSearchSpace 

func (d *UniversalDijkstra) GetSearchSpace() []*DijkstraItem

Returns the search space of a previous computation. This contains all items which were settled.

func (*UniversalDijkstra) GetStalledNodesCount 

func (d *UniversalDijkstra) GetStalledNodesCount() int

Get the number of stalling invocations

func (*UniversalDijkstra) GetUnstalledNodesCount 

func (d *UniversalDijkstra) GetUnstalledNodesCount() int

Get the number of unstall invocations

func (*UniversalDijkstra) SetBidirectional 

func (d *UniversalDijkstra) SetBidirectional(bidirectional bool)

Specify wheter the search should be done in both directions

func (*UniversalDijkstra) SetConsiderArcFlags 

func (d *UniversalDijkstra) SetConsiderArcFlags(considerArcFlags bool)

SPecify if the arc flags of the Arcs should be considered. If set to false, Arcs with a negative flag will be ignored by the path finding

func (*UniversalDijkstra) SetCostUpperBound 

func (d *UniversalDijkstra) SetCostUpperBound(costUpperBound int)

Set the upper cost for a valid path from source to target

func (*UniversalDijkstra) SetDebugLevel 

func (d *UniversalDijkstra) SetDebugLevel(level int)

Set the debug level to show different debug messages. If it is 0, no debug messages are printed

func (*UniversalDijkstra) SetHotStart 

func (d *UniversalDijkstra) SetHotStart(useHotStart bool)

Use a hot start

func (*UniversalDijkstra) SetIgnoreNodes 

func (d *UniversalDijkstra) SetIgnoreNodes(nodes []bool)

Set the nodes which are ignored in the search

func (*UniversalDijkstra) SetMaxNumSettledNodes 

func (d *UniversalDijkstra) SetMaxNumSettledNodes(maxNumSettledNodes int)

Set the maximum number of nodes that can get settled before the search is terminated

func (*UniversalDijkstra) SetStallOnDemand 

func (d *UniversalDijkstra) SetStallOnDemand(level int)

Use stall on demand

func (*UniversalDijkstra) SetUseHeuristic 

func (d *UniversalDijkstra) SetUseHeuristic(useHeuristic bool)

Specify whether a heuristic for path finding (AStar) should be used

func (*UniversalDijkstra) SortedArcs 

func (d *UniversalDijkstra) SortedArcs(sorted bool)

use sorted arcs (for early termination)

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.