Class PotentialBasedShortestDistanceFinder

An IPotentialBasedShortestDistanceFinder implementation, wrapping a IShortestDistanceFinder algorithm and using a potential function as a heuristic to enhance graph exploration.

Inheritance
System.Object
PotentialBasedShortestDistanceFinder
AStarShortestDistanceFinder
BidirectionalAStarShortestDistanceFinder
Implements
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.Graphs.ShortestDistance
Assembly: MoreStructures.dll
Syntax
public abstract class PotentialBasedShortestDistanceFinder : IPotentialBasedShortestDistanceFinder, IShortestDistanceFinder
Remarks

Common ground for all A* variants, such as AStarShortestDistanceFinder and BidirectionalAStarShortestDistanceFinder.
Check IPotentialBasedShortestDistanceFinder general documentation for the requirements and desired properties for the heuristic.

Constructors

| Improve this Doc View Source

PotentialBasedShortestDistanceFinder(IShortestDistanceFinder)

Declaration
protected PotentialBasedShortestDistanceFinder(IShortestDistanceFinder finder)
Parameters
Type Name Description
IShortestDistanceFinder finder

Properties

| Improve this Doc View Source

Finder

A IShortestDistanceFinder instance, used to run the shortest distance algorithm on the provided graph.

Declaration
protected IShortestDistanceFinder Finder { get; }
Property Value
Type Description
IShortestDistanceFinder

Methods

| Improve this Doc View Source

Find(IGraph, IGraphDistances, Func<Int32, Int32>, Int32, Int32)

Finds the shortest distance and path in the provided graph from the start vertex to the end vertex, i.e. a path such that the sum of distances of all the edges on the path is non-bigger than the one of any other path from the provided start and end vertices

Declaration
public (int, IList<int>) Find(IGraph graph, IGraphDistances distances, Func<int, int> potentials, int start, int end)
Parameters
Type Name Description
IGraph graph

IGraphDistances distances

Func<System.Int32, System.Int32> potentials

A function mapping each vertex of the provided graph to a System.Int32, providing an heuristic for "how far" the vertex is from the end vertex, to drive the IPotentialBasedShortestDistanceFinder towards an earlier, rather than late, discovery of the end vertex.
Check the general documentation of IPotentialBasedShortestDistanceFinder for further information about how to define a correct and good potential function.
System.Int32 start

System.Int32 end

Returns
Type Description
System.ValueTuple<System.Int32, IList<System.Int32>>

A couple. The first item of the couple is the shortest distance, as the sum of the distance of each edge of the shortest path between start and end.
The second item of the couple is the sequence of vertices of the graph, identifying the shortest path.
| Improve this Doc View Source

Find(IGraph, IGraphDistances, Int32, Int32)

Finds the shortest distance and path in the provided graph from the start vertex to the end vertex, i.e. a path such that the sum of distances of all the edges on the path is non-bigger than the one of any other path from the provided start and end vertices

Declaration
public (int, IList<int>) Find(IGraph graph, IGraphDistances distances, int start, int end)
Parameters
Type Name Description
IGraph graph

The graph to traverse.
IGraphDistances distances

A map between each edge of graph and its distance.
System.Int32 start

The id of the vertex, to start traversal from.
System.Int32 end

The id of the vertex, to end traversal at.
Returns
Type Description
System.ValueTuple<System.Int32, IList<System.Int32>>

A couple. The first item of the couple is the shortest distance, as the sum of the distance of each edge of the shortest path between start and end.
The second item of the couple is the sequence of vertices of the graph, identifying the shortest path.

Implements

Extension Methods