Shortest path methods


Modules
	Directed acyclic graphs
Enumerations
enum	abstractMixedGraph::TMethSPX { abstractMixedGraph::SPX_DEFAULT = -1, abstractMixedGraph::SPX_FIFO = 0, abstractMixedGraph::SPX_DIJKSTRA = 1, abstractMixedGraph::SPX_BELLMAN = 2, abstractMixedGraph::SPX_BFS = 3, abstractMixedGraph::SPX_DAG = 4, abstractMixedGraph::SPX_TJOIN = 5 }
enum	abstractMixedGraph::TOptSPX { abstractMixedGraph::SPX_ORIGINAL = 0, abstractMixedGraph::SPX_REDUCED = 1 }
Functions
bool	abstractMixedGraph::ShortestPath (TNode source, TNode target=NoNode) throw (ERRange,ERRejected)
bool	abstractMixedGraph::ShortestPath (TMethSPX method, TOptSPX characteristic, const indexSet< TArc > &EligibleArcs, TNode source, TNode target=NoNode) throw (ERRange,ERRejected)
TNode	abstractMixedGraph::VoronoiRegions (const indexSet< TNode > &Terminals) throw (ERRejected)
TNode	abstractMixedGraph::NegativeCycle (TOptSPX characteristic, const indexSet< TArc > &EligibleArcs, TNode source=NoNode, TFloat epsilon=0) throw (ERRange)
TNode	abstractMixedGraph::BFS (const indexSet< TArc > &EligibleArcs, const indexSet< TNode > &S, const indexSet< TNode > &T) throw ()
TNode	abstractMixedGraph::SPX_Dijkstra (TOptSPX characteristic, const indexSet< TArc > &EligibleArcs, const indexSet< TNode > &S, const indexSet< TNode > &T) throw (ERRange,ERRejected)
bool	abstractMixedGraph::SPX_FIFOLabelCorrecting (TOptSPX characteristic, const indexSet< TArc > &EligibleArcs, TNode s, TNode t=NoNode) throw (ERRange,ERCheck)
bool	abstractMixedGraph::SPX_BellmanFord (TOptSPX characteristic, const indexSet< TArc > &EligibleArcs, TNode s, TNode t=NoNode) throw (ERRange,ERCheck)

Enumeration Type Documentation

enum TMethSPX [inherited]

Alternative methods for shortest path solver.

Enumerator:

SPX_DEFAULT Apply the default method set in goblinController::methSPX.

SPX_FIFO Apply an improved label correcting method.

SPX_DIJKSTRA Apply the Dijkstra label setting method.

SPX_BELLMAN Apply the Bellman label correcting method.

SPX_BFS Apply breadth first search.

SPX_DAG Apply a method for directed acyclic graphs.

SPX_TJOIN Apply the T-join method for undirected graphs.

enum TOptSPX [inherited]

Options for implicit modification of the arc length labels.

Enumerator:

SPX_ORIGINAL Apply the original length labels.

SPX_REDUCED Apply the reduced length labels.

Function Documentation

TNode BFS ( const indexSet< TArc > & EligibleArcs,

const indexSet< TNode > & S,

const indexSet< TNode > & T

) throw () [inherited]

Perform a breadth first search.

Parameters:

EligibleArcs An index set of eligible arcs

S An index set of source nodes

T An index set of target nodes

Returns:
The first-reached target node index or NoNode
This determines a predecessor tree or forest - in case of multiple source nodes in S. If T is an empty set, every node is reached from an arbitrary source node on a path with a minimum number of eligible arcs. But the first time when a target node in T is reached, the procedure exits prematurely.

TNode NegativeCycle ( TOptSPX characteristic,

const indexSet< TArc > & EligibleArcs,

TNode source = NoNode,

TFloat epsilon = 0

) throw (ERRange) [inherited]

Solve Bellman's equations or return a negative length cycle.

Parameters:

characteristic A TOptSPX value

EligibleArcs An index set of eligible arcs

source An optional source node

epsilon A constant to be added on the length of each arc

Returns:
A node on the negative-length cycle or NoNode
If the graph contains a negative length eligible cycle, such a cycle is exported by the predecessor labels, and one of the nodes on this cycle is returned. If s is defined, the negative length cycle must consist of nodes which can be reached from s.
If no such cycle is found, for every node u (reachable from s), Bellman's equation Dist(u) == min{Dist(v)+Length(v,u) : vu is an eligible arc} is solved. Supposed that the graph is strongly connected, one degree of freedom is left. If s is defined, this is fixed by setting Dist(s) := 0, and a predecessor tree rooted at s is returned.

bool ShortestPath ( TMethSPX method,

TOptSPX characteristic,

const indexSet< TArc > & EligibleArcs,

TNode source,

TNode target = NoNode

) throw (ERRange,ERRejected) [inherited]

Compute a shortest path or a shortest path tree using a specified method.

Parameters:

method A TMethSPX value specifying the applied method

characteristic A TOptSPX value for modifying the searched graph

EligibleArcs An index set of eligible arcs

source The node where the search tree is rooted at

target An optional target node

Return values:

true The target node could be reached

Depending on the selected algorithm and whether a target node is specified, this method generates a shortest path between two nodes or a tree rooted at a given node.

bool ShortestPath ( TNode source,

TNode target = NoNode

) throw (ERRange,ERRejected) [inherited]

Compute a shortest path or a shortest path tree by using the default method.

Parameters:

source The node where the search tree is rooted at

target An optional target node

Return values:

true The target node could be reached

Depending on the selected algorithm and whether a target node is specified, this method generates a shortest path between two nodes or a tree rooted at a given node.

bool SPX_BellmanFord ( TOptSPX characteristic,

const indexSet< TArc > & EligibleArcs,

TNode s,

TNode t = NoNode

) throw (ERRange,ERCheck) [protected, inherited]

Perform the Bellman-Ford label correcting shortest-path search.

Parameters:

characteristic A TOptSPX value

EligibleArcs An index set of eligible arcs

s A source node

t A target node

Return values:

true If t is reachable from s

This implements the original Bellman-Ford label correcting algorithm. The procedure is similar but less efficient than SPX_FIFOLabelCorrecting().

TNode SPX_Dijkstra ( TOptSPX characteristic,

const indexSet< TArc > & EligibleArcs,

const indexSet< TNode > & S,

const indexSet< TNode > & T

) throw (ERRange,ERRejected) [protected, inherited]

Perform the Dijstra shortest-path search.

Parameters:

characteristic A TOptSPX value

EligibleArcs An index set of eligible arcs

S An index set of source nodes

T An index set of target nodes

Returns:
The first-reached target node index or NoNode
This is an implementation of the famous Dikstra algorithm which has been somewhat modified to allow for multiple source nodes. Non-negative arc lengths are required. The first time when a target node is reached, this node is reached by a shortest path, and the procedure is exited prematurely.

bool SPX_FIFOLabelCorrecting ( TOptSPX characteristic,

const indexSet< TArc > & EligibleArcs,

TNode s,

TNode t = NoNode

) throw (ERRange,ERCheck) [protected, inherited]

Perform the FIFO label correcting shortest-path search.

Parameters:

characteristic A TOptSPX value

EligibleArcs An index set of eligible arcs

s A source node

t A target node

Return values:

true If t is reachable from s

This is only a wrapper for NegativeCycle().

TNode VoronoiRegions ( const indexSet< TNode > & Terminals ) throw (ERRejected) [inherited]

Determine the discrete Voronoi regions.

Parameters:

Terminals The index set of terminal nodes

Returns:
The number of terminal node
This requires a connected graph with non-negative edge lengths. The node set is partitioned such that every node set contains a single terminal node. The other nodes a put into the set of the terminal, from which the minimum distance is achieved (with some arbitrary tie-braking). The partition data structure is exported, and predecessor labels encoding a minimum distance path from a terminal node.

Shortest path methods

Modules

Enumerations

Functions

Enumeration Type Documentation

Function Documentation