Satsuma.BellmanFord Class Reference

Finds cheapest paths in a graph from a set of source nodes to all nodes, or a negative cycle reachable from the sources. More...

Public Member Functions
	BellmanFord (IGraph graph, Func< Arc, double > cost, IEnumerable< Node > sources)
	Runs the Bellman-Ford algorithm. More...
double	GetDistance (Node node)
	Gets the cost of the cheapest path from the source nodes to a given node. More...
Arc	GetParentArc (Node node)
	Gets the arc connecting a node with its parent in the forest of cheapest paths. More...
IPath	GetPath (Node node)
	Gets a cheapest path from the source nodes to a given node. More...
bool	Reached (Node node)
	Returns whether a node has been reached. More...

Properties
Func< Arc, double >	Cost [get, set]
	The arc cost function. More...
IGraph	Graph [get, set]
	The input graph. More...
IPath	NegativeCycle [get, set]
	A negative cycle reachable from the sources, or null if none exists. More...
IEnumerable< Node >	ReachedNodes [get]
	Returns the reached nodes. More...

Detailed Description

Finds cheapest paths in a graph from a set of source nodes to all nodes, or a negative cycle reachable from the sources.

Note

Edges count as 2-cycles.

There is no restriction on the cost function (as opposed to AStar and Dijkstra), but if a negative cycle is reachable from the sources, the algorithm terminates and does not calculate the distances.

If the cost function is non-negative, use Dijkstra, as it runs faster.

Querying the results:

• If a negative cycle has been reached, then NegativeCycle is not null and contains such a cycle.
  • In this case, GetDistance, GetParentArc and GetPath throw an exception.
• If no negative cycle could be reached, then NegativeCycle is null.
  • In this case, use GetDistance, GetParentArc and GetPath for querying the results.
  • For unreachable nodes, GetDistance, GetParentArc and GetPath return double.PositiveInfinity, Arc.Invalid and null respectively.

See Also

AStar, Bfs, Dijkstra

Definition at line 28 of file BellmanFord.cs.

Constructor & Destructor Documentation

Satsuma.BellmanFord.BellmanFord	(	IGraph	graph,
		Func< Arc, double >	cost,
		IEnumerable< Node >	sources
	)

Runs the Bellman-Ford algorithm.

Parameters

graph	See Graph.
cost	See Cost.
sources	The source nodes.

Definition at line 47 of file BellmanFord.cs.

Member Function Documentation

double Satsuma.BellmanFord.GetDistance

(

Node

node

)

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

Returns

The distance, or double.PositiveInfinity if the node is unreachable from the source nodes.

Exceptions

InvalidOperationException

A reachable negative cycle has been found (i.e. NegativeCycle is not null).

Definition at line 137 of file BellmanFord.cs.

Arc Satsuma.BellmanFord.GetParentArc

(

Node

node

)

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

Returns

The arc, or Arc.Invalid if the node is a source or is unreachable.

Exceptions

InvalidOperationException

A reachable negative cycle has been found (i.e. NegativeCycle is not null).

Definition at line 147 of file BellmanFord.cs.

IPath Satsuma.BellmanFord.GetPath

(

Node

node

)

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

Returns

A cheapest path, or null if the node is unreachable.

Exceptions

InvalidOperationException

A reachable negative cycle has been found (i.e. NegativeCycle is not null).

Definition at line 157 of file BellmanFord.cs.

bool Satsuma.BellmanFord.Reached

(

Node

node

)

Returns whether a node has been reached.

Definition at line 125 of file BellmanFord.cs.

Property Documentation

Func<Arc, double> Satsuma.BellmanFord.Cost

getset

The arc cost function.

Each value must be finite or positive infinity. double.PositiveInfinity means that an arc is impassable.

Definition at line 34 of file BellmanFord.cs.

IGraph Satsuma.BellmanFord.Graph

getset

The input graph.

Definition at line 31 of file BellmanFord.cs.

IPath Satsuma.BellmanFord.NegativeCycle

getset

A negative cycle reachable from the sources, or null if none exists.

Definition at line 37 of file BellmanFord.cs.

IEnumerable<Node> Satsuma.BellmanFord.ReachedNodes

get

Returns the reached nodes.

See Also

Reached

Definition at line 132 of file BellmanFord.cs.

---

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

• src/BellmanFord.cs