Class BfsBasedShortestPathFinder

An implementation of IShortestPathFinder which performs a BFS traversal, starting from the start vertex, to find the shortest path to the end vertex.

Inheritance
System.Object
BfsBasedShortestPathFinder
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.ShortestPath
Assembly: MoreStructures.dll
Syntax
public class BfsBasedShortestPathFinder : IShortestPathFinder
Remarks

ALGORITHM
- A IVisitStrategy is instantiated via the VisitStrategyBuilder provided in the constructor.
- The IVisitStrategy instance is instrumented, by adding an event handler H to the VisitingVertex.
- The event handler H maps each visited vertex to its previous vertex (i.e. the vertex whose visit has trigger the visit of this vertex), as stored in PreviousVertex passed by the VisitingVertex event, into a D.
- A Breadth First Search from the start vertex is executed, running BreadthFirstSearchFromVertex(IGraph, Int32). The result of the visit is consumed (i.e. the visit is done) until either the end vertex is encountered, or when there are no more vertices reachable from the start vertex, which haven't been visited yet.
- If the end vertex hasn't been discovered during the visit, it is not reachable. Therefore, a length of path equal to System.Int32.MaxValue and an empty path are returned.
- If the end vertex has been reached, the end vertex has been visited and it is contained in D.
- D is traversed backwards, from the end to the start vertex, rebuilding the (reversed) path.
- Finally, the path is reversed and returned as result.
- Its length minus 1 represents the length of the path between start and end vertex.

COMPLEXITY
- While building the IVisitStrategy instance has a complexity that depends on the user-provided VisitStrategyBuilder, it doesn't generally depends on the size of the graph to be visited, and can be considered O(1) work.
- Instrumenting the IVisitStrategy instance and running the handler for every visited vertex are also constant-time operations.
- The complexity of the BFS visit depends on the actual IVisitStrategy implementation used.
- Rebuilding and reversing the path takes time and space proportional to the length of the path, which in the worst case can be O(v) where v is the number of vertices of the graph.
- Therefore, Time Complexity is O(Tbfs + v) and Space Complexity is O(Sbfs + v).
- If FullyIterativeHashSetBasedGraphVisit or FullyRecursiveHashSetBasedGraphVisit visits are used, with an IGraph retrieving neighbors in constant time, Time and Space Complexity become O(v + e).

Constructors

| Improve this Doc View Source

BfsBasedShortestPathFinder(Func<IVisitStrategy>)

Declaration
public BfsBasedShortestPathFinder(Func<IVisitStrategy> visitStrategyBuilder)
Parameters
Type Name Description
Func<IVisitStrategy> visitStrategyBuilder

Remarks

Properties

| Improve this Doc View Source

VisitStrategyBuilder

A building function able to instantiate the IVisitStrategy to be used to find the shortest path, by running a Breadth First Searches from the start vertex via BreadthFirstSearchFromVertex(IGraph, Int32).

Declaration
public Func<IVisitStrategy> VisitStrategyBuilder { get; }
Property Value
Type Description
Func<IVisitStrategy>

Methods

| Improve this Doc View Source

Find(IGraph, Int32, Int32)

Declaration
public (int, IList<int>) Find(IGraph graph, int start, int end)
Parameters
Type Name Description
IGraph graph
System.Int32 start
System.Int32 end
Returns
Type Description
System.ValueTuple<System.Int32, IList<System.Int32>>
Remarks

Implements

Extension Methods