Satsuma.AStar Class Reference

Uses the A* search algorithm to find cheapest paths in a graph. More...

Public Member Functions
void	AddSource (Node node)
	Adds a new source node. More...
	AStar (IGraph graph, Func< Arc, double > cost, Func< Node, double > heuristic)
double	GetDistance (Node node)
	Gets the cost of the cheapest path from the source nodes to a given node (that is, its distance from the sources). More...
IPath	GetPath (Node node)
	Gets a cheapest path from the source nodes to a given node. More...
Node	RunUntilReached (Node target)
	Runs the algorithm until the given node is reached. More...
Node	RunUntilReached (Func< Node, bool > isTarget)
	Runs the algorithm until a node satisfying the given condition is reached. More...

Properties
Func< Arc, double >	Cost [get, set]
	A non-negative arc cost function. More...
IGraph	Graph [get, set]
	The input graph. More...
Func< Node, double >	Heuristic [get, set]
	The A* heuristic function. More...

Detailed Description

Uses the A* search algorithm to find cheapest paths in a graph.

AStar is essentially Dijkstra's algorithm with an optional heuristic which can speed up path search.

Usage:

• AddSource can be used to initialize the class by providing the source nodes.
• Then RunUntilReached can be called to obtain cheapest paths to a target set.

Note

A target node is reached if a cheapest path leading to it is known. Unlike Dijkstra, A* does not use the notion of fixed nodes.

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();
Node source = g.GetNode(0);
Node target = g.GetNode(1);
var astar = new AStar(g, arc => Math.Abs(pos[g.U(arc)] - pos[g.V(arc)]), node => Math.Abs(pos[node] - pos[target]));
astar.AddSource(source);
astar.RunUntilReached(target);
Console.WriteLine("Distance of target from source: "+astar.GetDistance(target));

See Also

BellmanFord, Bfs, Dijkstra

Definition at line 56 of file AStar.cs.

Constructor & Destructor Documentation

Satsuma.AStar.AStar	(	IGraph	graph,
		Func< Arc, double >	cost,
		Func< Node, double >	heuristic
	)

Parameters

graph	See Graph.
cost	See Cost.
heuristic	See Heuristic.

Definition at line 80 of file AStar.cs.

Member Function Documentation

void Satsuma.AStar.AddSource

(

Node

node

)

Adds a new source node.

Exceptions

InvalidOperationException

The node has already been reached.

Definition at line 99 of file AStar.cs.

double Satsuma.AStar.GetDistance

(

Node

node

)

Gets the cost of the 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.

Exceptions

ArgumentException

Heuristic(node) is not 0.

Definition at line 125 of file AStar.cs.

IPath Satsuma.AStar.GetPath

(

Node

node

)

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

Returns

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

Exceptions

ArgumentException

Heuristic(node) is not 0.

Definition at line 134 of file AStar.cs.

Node Satsuma.AStar.RunUntilReached

(

Node

target

)

Runs the algorithm until the given node is reached.

Parameters

target

The node to reach.

Returns

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

Exceptions

ArgumentException

Heuristic(target) is not 0.

Definition at line 108 of file AStar.cs.

Node Satsuma.AStar.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 all the targets are unreachable.

Exceptions

ArgumentException

Heuristic is not 0 for the returned node.

Definition at line 116 of file AStar.cs.

Property Documentation

Func<Arc, double> Satsuma.AStar.Cost

getset

A non-negative arc cost function.

Definition at line 61 of file AStar.cs.

IGraph Satsuma.AStar.Graph

getset

The input graph.

Definition at line 59 of file AStar.cs.

Func<Node, double> Satsuma.AStar.Heuristic

getset

The A* heuristic function.

Heuristic must be a function that is

• non-negative,
• admissible: it must assign for each node a lower bound on the cost of the cheapest path from the given node to the target node set,
• and consistent: for each uv arc, Heuristic(u) <= Cost(uv) + Heuristic(v).

From the above it follows that Heuristic must return 0 for all target nodes.

If Heuristic is the constant zero function, then the algorithm is equivalent to Dijkstra's algorithm.

Definition at line 73 of file AStar.cs.

---

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

• src/AStar.cs