Class BfsBasedShortestDistanceFinder

An IShortestDistanceFinder which runs a BFS on the provided graph from the start vertex, to find the shortest distance and a shortest path to the end vertex.

Inheritance
System.Object
BfsBasedShortestDistanceFinder
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 class BfsBasedShortestDistanceFinder : IShortestDistanceFinder
Remarks

ALGORITHM
- First, a IVisitStrategy is instantiated via the VisitStrategyBuilder provided in the constructor.
- The IVisitStrategy instance will be used to run BreadthFirstSearchFromVertex(IGraph, Int32) from the start vertex.
- Unlike the Dijkstra algorithm, the BFS visit will traverse all vertices reachable from the start vertex by breadth. Morever it never stops the BFS traversal, even when the current path can't possibly be shortest.
- The visitor is instrumented with an event handler H, attached to both VisitingVertex and AlreadyVisitedVertex.
- H updates a dictionary SPs mapping each vertex v to its currently known shortest path SP from the start vertex to v and the previous vertex of v in SP.
- H also keeps a dictionary DSs mapping each vertex v to the of its currently visited downstream vertices, i.e. all vertices u visited from v during the BFS.
- Every time H encounters a vertex v which is not yet in SPs (i.e. it doesn't have a registered shortest path yet), it just adds it to SPs.
- Every time H encounters a vertex v which is already is SPs (i.e. it has already a registered shortest path), it adds it to SPs and then updates recursively the entries of SPs of all downstream vertices, using DSs.
- After the BFS visit is concluded, there are two possible scenarios: either the end vertex has been discovered by the visit or not.
- If the end vertex has not been discovered, it means that there is no path at all from the start to the end vertex. In that case, System.Int32.MaxValue and an emtpy are returned as result.
- If the end vertex has been discovered, SPs[end] gives the shortest distance. SPs can be navigated backwards, until the start vertex, to find the path with the shortest distance.

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 is also a constant-time operation.
- Running the handler for every visited and already visited vertex, however, requires updating vertices downstream, every time an entry SPs is updated, i.e. when a smaller distance from the start is found. That affects the performance of the BFS execution, increasing its Time Complexity.
- Because the BFS doesn't stop when the end vertex is found (as there may be longer paths with shorter distance from the start vertex), the downstream vertices to be recursively updated can cover then entire graph (i.e. O(v) vertices).
- 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 + v) and Space Complexity is O(Sbfs + v^2).
- If FullyIterativeHashSetBasedGraphVisit or FullyRecursiveHashSetBasedGraphVisit visits are used, with an IGraph retrieving neighbors in constant time, Time Complexity becomes O((v + e) * v) and O(v^2 + e).
- On dense graphs, Time Complexity is O(v^3) and Space Complexity is O(v^2).

Constructors

| Improve this Doc View Source

BfsBasedShortestDistanceFinder(Func<IVisitStrategy>)

Declaration
public BfsBasedShortestDistanceFinder(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 distance, 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, IGraphDistances, Int32, Int32)

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

Implements

Extension Methods