Uses Dijkstra's algorithm to find cheapest paths in a graph. More...

Public Member Functions
void	AddSource (Node node)
	Adds a new source node. More...

void	AddSource (Node node, double nodeCost)
	Adds a new source node and sets its initial distance to nodeCost. More...

	Dijkstra (IGraph graph, Func< Arc, double > cost, DijkstraMode mode)

bool	Fixed (Node node)
	Returns whether a node has been fixed. More...

double	GetDistance (Node node)
	Gets the cost of the current cheapest path from the source nodes to a given node (that is, its distance from the sources). More...

Arc	GetParentArc (Node node)
	Gets the arc connecting a node with its parent in the current forest of cheapest paths. More...

IPath	GetPath (Node node)
	Gets the current cheapest path from the source nodes to a given node. More...

bool	Reached (Node node)
	Returns whether a node has been reached. More...

void	Run ()
	Runs the algorithm until all possible nodes are fixed. More...

Node	RunUntilFixed (Node target)
	Runs the algorithm until a specific target node is fixed. More...

Node	RunUntilFixed (Func< Node, bool > isTarget)
	Runs the algorithm until a node satisfying the given condition is fixed. More...

Node	Step ()
	Performs a step in the algorithm and fixes a node. More...

Properties
Func< Arc, double >	Cost `[get, set]`
	The arc cost function. More...

IEnumerable< Node >	FixedNodes `[get]`
	Returns the fixed nodes. More...

IGraph	Graph `[get, set]`
	The input graph. More...

DijkstraMode	Mode `[get, set]`
	The path cost calculation mode. More...

double	NullCost `[get, set]`
	The lowest possible cost value. More...

IEnumerable< Node >	ReachedNodes `[get]`
	Returns the reached nodes. More...

Detailed Description

Uses Dijkstra's algorithm to find cheapest paths in a graph.

Warning: See DijkstraMode for constraints on the cost function.

Usage:

AddSource can be used to initialize the class by providing the source nodes.
Then Run or RunUntilFixed may be called to obtain a forest of cheapest paths to a given set of nodes.
Alternatively, Step can be called several times.

The algorithm reaches and fixes nodes one after the other (see Reached and Fixed).

Querying the results:

For fixed nodes, use GetDistance, GetParentArc and GetPath.
For reached but unfixed nodes, these methods return valid but not yet optimal values.
For currently unreached nodes, GetDistance, GetParentArc and GetPath return double.PositiveInfinity, Arc.Invalid and null respectively.

Example (finding a shortest path between two nodes):

var g = new CompleteGraph(50);
var pos = new Dictionary<Node, double>();
var r = new Random();
foreach (var node in g.Nodes())
    pos[node] = r.NextDouble();
var dijkstra = new Dijkstra(g, arc => Math.Abs(pos[g.U(arc)] - pos[g.V(arc)]), DijkstraMode.Sum);
Node a = g.GetNode(0), b = g.GetNode(1);
dijkstra.AddSource(a);
dijkstra.RunUntilFixed(b);
Console.WriteLine("Distance of b from a: "+dijkstra.GetDistance(b));

See Also: AStar, BellmanFord, Bfs

Definition at line 52 of file Dijsktra.cs.

Constructor & Destructor Documentation

Satsuma.Dijkstra.Dijkstra	(	IGraph	graph,
		Func< Arc, double >	cost,
		DijkstraMode	mode
	)

Parameters

graph	See Graph.
cost	See Cost.
mode	See Mode.

Definition at line 75 of file Dijsktra.cs.

Member Function Documentation

void Satsuma.Dijkstra.AddSource ( Node node )

Adds a new source node.

Exceptions

InvalidOperationException The node has already been reached.

Definition at line 95 of file Dijsktra.cs.

void Satsuma.Dijkstra.AddSource	(	Node	node,
		double	nodeCost
	)

Adds a new source node and sets its initial distance to nodeCost.

Use this method only if you know what you are doing.

Note: Equivalent to deleting all arcs entering node, and adding a new source node s with a new arc from s to node whose cost equals to nodeCost.

Exceptions

InvalidOperationException The node has already been reached, or nodeCost is invalid as an arc cost.

Definition at line 106 of file Dijsktra.cs.

bool Satsuma.Dijkstra.Fixed ( Node node )

Returns whether a node has been fixed.

A node is called reached if it belongs to the current forest of cheapest paths. (see Reached)
Each reached node is either a source, or has a parent arc. (see GetParentArc)
A node is called fixed if it is reached and its distance will not change in the future.
At the beginning, only the source nodes are reached and none are fixed. (see AddSource)
In each step, the algorithm fixes a node and reaches some (maybe zero) other nodes.
The algorithm terminates if there is no node which is reached but not fixed.
See Also
FixedNodes

Definition at line 204 of file Dijsktra.cs.

double Satsuma.Dijkstra.GetDistance ( Node node )

Gets the cost of the current cheapest path from the source nodes to a given node (that is, its distance from the sources).

Returns: The distance, or double.PositiveInfinity if the node has not been reached yet.

Definition at line 216 of file Dijsktra.cs.

Arc Satsuma.Dijkstra.GetParentArc ( Node node )

Gets the arc connecting a node with its parent in the current forest of cheapest paths.

Returns: The arc, or Arc.Invalid if the node is a source or has not been reached yet.

Definition at line 224 of file Dijsktra.cs.

IPath Satsuma.Dijkstra.GetPath ( Node node )

Gets the current cheapest path from the source nodes to a given node.

Returns: A current cheapest path, or null if the node has not been reached yet.

Definition at line 232 of file Dijsktra.cs.

bool Satsuma.Dijkstra.Reached ( Node node )

Returns whether a node has been reached.

See Fixed for more information.

See Also: ReachedNodes

Definition at line 187 of file Dijsktra.cs.

void Satsuma.Dijkstra.Run ( )

Runs the algorithm until all possible nodes are fixed.

Definition at line 154 of file Dijsktra.cs.

Node Satsuma.Dijkstra.RunUntilFixed ( Node target )

Runs the algorithm until a specific target node is fixed.

(see Fixed)

Parameters

target The node to fix.

Returns: target if it was successfully fixed, or Node.Invalid if it is unreachable.

Definition at line 162 of file Dijsktra.cs.

Node Satsuma.Dijkstra.RunUntilFixed ( Func< Node, bool > isTarget )

Runs the algorithm until a node satisfying the given condition is fixed.

Returns: a target node if one was successfully fixed, or Node.Invalid if all the targets are unreachable.

Definition at line 174 of file Dijsktra.cs.

Node Satsuma.Dijkstra.Step ( )

Performs a step in the algorithm and fixes a node.

Returns: The newly fixed node, or Node.Invalid if there was no reached but unfixed node.

See Also: Reached, Fixed

Definition at line 118 of file Dijsktra.cs.

Property Documentation

Func<Arc, double> Satsuma.Dijkstra.Cost

getset

The arc cost function.

double.PositiveInfinity means that an arc is impassable. See DijkstraMode for restrictions on cost functions.

Definition at line 59 of file Dijsktra.cs.

IEnumerable<Node> Satsuma.Dijkstra.FixedNodes

get

Returns the fixed nodes.

See Also: Fixed

Definition at line 211 of file Dijsktra.cs.

IGraph Satsuma.Dijkstra.Graph

getset

The input graph.

Definition at line 55 of file Dijsktra.cs.

DijkstraMode Satsuma.Dijkstra.Mode

getset

The path cost calculation mode.

Definition at line 62 of file Dijsktra.cs.

double Satsuma.Dijkstra.NullCost

getset

The lowest possible cost value.

0 if Mode == DijkstraMode.Sum
double.NegativeInfinity if Mode == DijkstraMode.Maximum

Definition at line 66 of file Dijsktra.cs.

IEnumerable<Node> Satsuma.Dijkstra.ReachedNodes

get

Returns the reached nodes.

See Also: Reached

Definition at line 194 of file Dijsktra.cs.

The documentation for this class was generated from the following file:

src/Dijsktra.cs

Public Member Functions

Properties

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Property Documentation