Satsuma.Bfs Class Reference

Performs a breadth-first search (BFS) to find shortest paths from a set of source nodes to all nodes. More...

Public Member Functions
void	AddSource (Node node)
	Adds a new source node. More...
	Bfs (IGraph graph)
int	GetLevel (Node node)
	Gets the current distance from the set of source nodes (that is, its level in the Bfs forest). More...
Arc	GetParentArc (Node node)
	Gets the arc connecting a node with its parent in the Bfs forest. More...
IPath	GetPath (Node node)
	Gets a shortest path from the sources to a node. More...
bool	Reached (Node x)
	Returns whether a node has been reached. More...
void	Run ()
	Runs the algorithm until finished. More...
Node	RunUntilReached (Node target)
	Runs the algorithm until a specific target node is reached. More...
Node	RunUntilReached (Func< Node, bool > isTarget)
	Runs the algorithm until a node satisfying the given condition is reached. More...
bool	Step (Func< Node, bool > isTarget, out Node reachedTargetNode)
	Performs an iteration which involves dequeueing a node. More...

Properties
IGraph	Graph [get, set]
	The input graph. More...
IEnumerable< Node >	ReachedNodes [get]
	Returns the reached nodes. More...

Detailed Description

Performs a breadth-first search (BFS) to find shortest paths from a set of source nodes to all nodes.

In other words, Bfs finds cheapest paths for the constant 1 cost function. The advantage of Bfs over Dijkstra is its faster execution.

Usage:

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

The algorithm reaches nodes one after the other (see Reached for definition).

Querying the results:

• For reached nodes, use GetLevel, GetParentArc and GetPath.
• For currently unreached nodes, GetLevel, GetParentArc and GetPath return -1, Arc.Invalid and null respectively.

See Also

AStar, BellmanFord, Dijkstra

Definition at line 49 of file Bfs.cs.

Constructor & Destructor Documentation

Satsuma.Bfs.Bfs

(

IGraph

graph

)

Definition at line 58 of file Bfs.cs.

Member Function Documentation

void Satsuma.Bfs.AddSource

(

Node

node

)

Adds a new source node.

Exceptions

InvalidOperationException

The node has already been reached.

Definition at line 69 of file Bfs.cs.

int Satsuma.Bfs.GetLevel

(

Node

node

)

Gets the current distance from the set of source nodes (that is, its level in the Bfs forest).

Returns

The distance, or -1 if the node has not been reached yet.

Definition at line 157 of file Bfs.cs.

Arc Satsuma.Bfs.GetParentArc

(

Node

node

)

Gets the arc connecting a node with its parent in the Bfs forest.

Returns

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

Definition at line 165 of file Bfs.cs.

IPath Satsuma.Bfs.GetPath

(

Node

node

)

Gets a shortest path from the sources to a node.

Returns

A shortest path, or null if the node has not been reached yet.

Definition at line 173 of file Bfs.cs.

bool Satsuma.Bfs.Reached

(

Node

x

)

Returns whether a node has been reached.

• A node is called reached if it belongs to the current Bfs forest.
• Each reached node is either a source, or has a parent arc. (see GetParentArc)
• At the beginning, only the source nodes are reached. (see AddSource)

  See Also

  ReachedNodes

Definition at line 145 of file Bfs.cs.

void Satsuma.Bfs.Run

(

)

Runs the algorithm until finished.

Definition at line 113 of file Bfs.cs.

Node Satsuma.Bfs.RunUntilReached

(

Node

target

)

Runs the algorithm until a specific target node is reached.

Parameters

target

The node to reach.

Returns

target if it was successfully reached, or Node.Invalid.

Definition at line 122 of file Bfs.cs.

Node Satsuma.Bfs.RunUntilReached

(

Func< Node, bool >

isTarget

)

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

Returns

A target node if one was successfully reached, or Node.Invalid if it is unreachable.

Definition at line 132 of file Bfs.cs.

bool Satsuma.Bfs.Step	(	Func< Node, bool >	isTarget,
		out Node	reachedTargetNode
	)

Performs an iteration which involves dequeueing a node.

The unreached neighbors of the dequeued node are enqueued, and isTarget (which can be null) is called for each of them to find out if they belong to the target node set. If a target node is found among them, then the function returns immediately.

Parameters

isTarget	Returns true for target nodes. Can be null.
reachedTargetNode	The target node that has been newly reached, or Node.Invalid.

Returns

true if no target node has been reached in this step, and there is at least one yet unreached node.

Definition at line 87 of file Bfs.cs.

Property Documentation

IGraph Satsuma.Bfs.Graph

getset

The input graph.

Definition at line 52 of file Bfs.cs.

IEnumerable<Node> Satsuma.Bfs.ReachedNodes

get

Returns the reached nodes.

See Also

Reached

Definition at line 152 of file Bfs.cs.

---

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

• src/Bfs.cs