< Summary

Information
Class: MoreStructures.Graphs.ShortestDistance.BfsBasedShortestDistanceFinder
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/Graphs/ShortestDistance/BfsBasedShortestDistanceFinder.cs
Line coverage
100%
Covered lines: 47
Uncovered lines: 0
Coverable lines: 47
Total lines: 164
Line coverage: 100%
Branch coverage
100%
Covered branches: 16
Total branches: 16
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
get_VisitStrategyBuilder()100%1100%
.ctor(...)100%1100%
Find(...)100%2100%
UpdateBestPreviousAndDownstreamVertices(...)100%14100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/Graphs/ShortestDistance/BfsBasedShortestDistanceFinder.cs

#LineLine coverage
 1using MoreLinq.Extensions;
 2using MoreStructures.Graphs.Visitor;
 3
 4namespace MoreStructures.Graphs.ShortestDistance;
 5
 6/// <summary>
 7/// An <see cref="IShortestDistanceFinder"/> which runs a BFS on the provided graph from the start vertex, to find the
 8/// shortest distance and a shortest path to the end vertex.
 9/// </summary>
 10/// <remarks>
 11///     <para id="algorithm">
 12///     ALGORITHM
 13///     <br/>
 14///     - First, a <see cref="IVisitStrategy"/> is instantiated via the <see cref="VisitStrategyBuilder"/> provided in
 15///       the constructor.
 16///       <br/>
 17///     - The <see cref="IVisitStrategy"/> instance will be used to run
 18///       <see cref="IVisitStrategy.BreadthFirstSearchFromVertex"/> from the start vertex.
 19///       <br/>
 20///     - Unlike the Dijkstra algorithm, the BFS visit will traverse all vertices reachable from the start vertex by
 21///       breadth. Morever it never stops the BFS traversal, even when the current path can't possibly be shortest.
 22///       <br/>
 23///     - The visitor is instrumented with an event handler H, attached to both
 24///       <see cref="IVisitStrategy.VisitingVertex"/> and <see cref="IVisitStrategy.AlreadyVisitedVertex"/>.
 25///       <br/>
 26///     - H updates a dictionary SPs mapping each vertex v to its currently known shortest path SP from the start
 27///       vertex to v and the previous vertex of v in SP.
 28///       <br/>
 29///     - H also keeps a dictionary DSs mapping each vertex v to the <see cref="HashSet{T}"/> of its currently visited
 30///       downstream vertices, i.e. all vertices u visited from v during the BFS.
 31///       <br/>
 32///     - Every time H encounters a vertex v which is not yet in SPs (i.e. it doesn't have a registered shortest path
 33///       yet), it just adds it to SPs.
 34///       <br/>
 35///     - Every time H encounters a vertex v which is already is SPs (i.e. it has already a registered shortest path),
 36///       it adds it to SPs and then updates recursively the entries of SPs of all downstream vertices, using DSs.
 37///       <br/>
 38///     - After the BFS visit is concluded, there are two possible scenarios: either the end vertex has been discovered
 39///       by the visit or not.
 40///       <br/>
 41///     - If the end vertex has not been discovered, it means that there is no path at all from the start to the end
 42///       vertex. In that case, <see cref="int.MaxValue"/> and an emtpy <see cref="IList{T}"/> are returned as result.
 43///       <br/>
 44///     - If the end vertex has been discovered, <c>SPs[end]</c> gives the shortest distance. SPs can be navigated
 45///       backwards, until the start vertex, to find the path with the shortest distance.
 46///     </para>
 47///     <para id="complexity">
 48///     COMPLEXITY
 49///     <br/>
 50///     - While building the <see cref="IVisitStrategy"/> instance has a complexity that depends on the user-provided
 51///       <see cref="VisitStrategyBuilder"/>, it doesn't generally depends on the size of the graph to be visited, and
 52///       can be considered O(1) work.
 53///       <br/>
 54///     - Instrumenting the <see cref="IVisitStrategy"/> instance is also a constant-time operation.
 55///       <br/>
 56///     - Running the handler for every visited and already visited vertex, however, requires updating vertices
 57///       downstream, every time an entry SPs is updated, i.e. when a smaller distance from the start is found. That
 58///       affects the performance of the BFS execution, increasing its Time Complexity.
 59///       <br/>
 60///     - Because the BFS doesn't stop when the end vertex is found (as there may be longer paths with shorter distance
 61///       from the start vertex), the downstream vertices to be recursively updated can cover then entire graph (i.e.
 62///       O(v) vertices).
 63///       <br/>
 64///     - The complexity of the BFS visit depends on the actual <see cref="IVisitStrategy"/> implementation used.
 65///       <br/>
 66///     - Rebuilding and reversing the path takes time and space proportional to the length of the path, which in the
 67///       worst case can be O(v) where v is the number of vertices of the graph.
 68///       <br/>
 69///     - Therefore, Time Complexity is O(Tbfs * v + v) and Space Complexity is O(Sbfs + v^2).
 70///       <br/>
 71///     - If <see cref="FullyIterativeHashSetBasedGraphVisit"/> or <see cref="FullyRecursiveHashSetBasedGraphVisit"/>
 72///       visits are used, with an <see cref="IGraph"/> retrieving neighbors in constant time, Time Complexity becomes
 73///       O((v + e) * v) and O(v^2 + e).
 74///       <br/>
 75///     - On dense graphs, Time Complexity is O(v^3) and Space Complexity is O(v^2).
 76///     </para>
 77/// </remarks>
 78public class BfsBasedShortestDistanceFinder : IShortestDistanceFinder
 79{
 80    /// <summary>
 81    /// A building function able to instantiate the <see cref="IVisitStrategy"/> to be used to find the shortest
 82    /// distance, by running a Breadth First Searches from the start vertex via
 83    /// <see cref="IVisitStrategy.BreadthFirstSearchFromVertex(IGraph, int)"/>.
 84    /// </summary>
 2285    public Func<IVisitStrategy> VisitStrategyBuilder { get; }
 86
 87    /// <summary>
 88    ///     <inheritdoc cref="BfsBasedShortestDistanceFinder"/>
 89    /// </summary>
 90    /// <param name="visitStrategyBuilder">
 91    ///     <inheritdoc cref="VisitStrategyBuilder" path="/summary"/>
 92    /// </param>
 93    /// <remarks>
 94    ///     <inheritdoc cref="BfsBasedShortestDistanceFinder"/>
 95    /// </remarks>
 2696    public BfsBasedShortestDistanceFinder(Func<IVisitStrategy> visitStrategyBuilder)
 2697    {
 2698        VisitStrategyBuilder = visitStrategyBuilder;
 2699    }
 100
 101    /// <inheritdoc path="//*[not(self::remarks)]"/>
 102    /// <remarks>
 103    ///     <inheritdoc cref="BfsBasedShortestDistanceFinder"/>
 104    /// </remarks>
 105    public (int, IList<int>) Find(IGraph graph, IGraphDistances distances, int start, int end)
 26106    {
 26107        ShortestDistanceFinderHelper.ValidateParameters(graph, start, end);
 108
 22109        var bestPreviouses = new BestPreviouses(new() { [start] = new(0, -1) });
 22110        var downstreamVertices = new Dictionary<int, HashSet<int>>();
 111
 22112        var visitor = VisitStrategyBuilder();
 22113        visitor.VisitingVertex +=
 135114            (o, e) => UpdateBestPreviousAndDownstreamVertices(o, e, distances, bestPreviouses, downstreamVertices);
 22115        visitor.AlreadyVisitedVertex +=
 54116            (o, e) => UpdateBestPreviousAndDownstreamVertices(o, e, distances, bestPreviouses, downstreamVertices);
 117
 22118        visitor
 22119            .BreadthFirstSearchFromVertex(graph, start)
 22120            .Consume();
 121
 22122        if (!bestPreviouses.Values.ContainsKey(end))
 3123            return (int.MaxValue, Array.Empty<int>());
 124
 19125        var shortestDistance = bestPreviouses.Values[end].DistanceFromStart;
 19126        var shortestPath = ShortestDistanceFinderHelper.BuildShortestPath(end, bestPreviouses);
 127
 19128        return (shortestDistance, shortestPath);
 22129    }
 130
 131    private static void UpdateBestPreviousAndDownstreamVertices(
 132        object? sender, VisitEventArgs eventArgs,
 133        IGraphDistances distances, BestPreviouses bestPreviouses, Dictionary<int, HashSet<int>> downstreamVertices)
 164134    {
 164135        var current = eventArgs.Vertex;
 164136        if (eventArgs.PreviousVertex is not int previous)
 22137            return;
 138
 142139        if (!downstreamVertices.ContainsKey(previous))
 92140            downstreamVertices[previous] = new HashSet<int> { current };
 141        else
 50142            downstreamVertices[previous].Add(current);
 143
 142144        var distanceFromStartToPrevious = bestPreviouses.Values[previous].DistanceFromStart;
 142145        var distanceFromPreviousToCurrent = distances[(previous, current)];
 142146        var distanceFromStartToCurrent = distanceFromStartToPrevious + distanceFromPreviousToCurrent;
 147
 142148        if (!bestPreviouses.Values.ContainsKey(current))
 91149        {
 91150            bestPreviouses.Values[current] = new(distanceFromStartToCurrent, previous);
 91151        }
 51152        else if (bestPreviouses.Values[current].DistanceFromStart > distanceFromStartToCurrent)
 31153        {
 31154            bestPreviouses.Values[current] = new(distanceFromStartToCurrent, previous);
 155
 156            // Update all vertices downstream (if any), which have already entries in bestPreviouses
 31157            if (downstreamVertices.ContainsKey(current))
 83158                foreach (var downstreamVertex in downstreamVertices[current])
 19159                    UpdateBestPreviousAndDownstreamVertices(
 19160                        sender, new(downstreamVertex, eventArgs.ConnectedComponent, current),
 19161                        distances, bestPreviouses, downstreamVertices);
 31162        }
 164163    }
 164}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_VisitStrategyBuilder()
.ctor(System.Func`1<MoreStructures.Graphs.Visitor.IVisitStrategy>)
Find(MoreStructures.Graphs.IGraph,MoreStructures.Graphs.IGraphDistances,System.Int32,System.Int32)
UpdateBestPreviousAndDownstreamVertices(System.Object,MoreStructures.Graphs.Visitor.VisitEventArgs,MoreStructures.Graphs.IGraphDistances,MoreStructures.Graphs.ShortestDistance.BestPreviouses,System.Collections.Generic.Dictionary`2<System.Int32,System.Collections.Generic.HashSet`1<System.Int32>>)