< Summary

Information
Class: MoreStructures.Graphs.ShortestDistance.BellmanFordShortestDistanceFinder
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/Graphs/ShortestDistance/BellmanFordShortestDistanceFinder.cs
Line coverage
100%
Covered lines: 17
Uncovered lines: 0
Coverable lines: 17
Total lines: 147
Line coverage: 100%
Branch coverage
100%
Covered branches: 4
Total branches: 4
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%4100%

File(s)

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

#LineLine coverage
 1using MoreStructures.Graphs.Visitor;
 2
 3namespace MoreStructures.Graphs.ShortestDistance;
 4
 5/// <summary>
 6/// An <see cref="IShortestDistanceFinder"/> implementation based on the Bellman-Ford algorithm.
 7/// </summary>
 8/// <remarks>
 9///     <para id="advantages">
 10///     ADVANTAGES AND DISADVANTAGES
 11///     <br/>
 12///     - Unlike <see cref="DijkstraShortestDistanceFinder"/>, this implementation doesn't require distances to be
 13///       non-negative and it also works in presence of negative cycles.
 14///       <br/>
 15///     - Unlike <see cref="DijkstraShortestDistanceFinder"/>, this algorithm doesn't require any external data
 16///       structure (such as a <see cref="PriorityQueues.IPriorityQueue{T}"/> implementation: its runtime performance
 17///       solely depends on the algorithm itself.
 18///       <br/>
 19///     - However, due to the generality of conditions in which it operates, it can't leverage the same performance as
 20///       the Dijkstra algorithm. So, if the graph doesn't have negative distances, or it can be reduce not to have
 21///       them, consider using <see cref="DijkstraShortestDistanceFinder"/> instead, for better performance.
 22///       <br/>
 23///     - In particolar it has a quadratic performance, instead of the linearithmic Time Complexity of Dijkstra on
 24///       graphs with non-negative distances or the linear complexity of "edge relaxation in topological order" on
 25///       DAGs.
 26///     </para>
 27///     <para id="algorithm">
 28///     ALGORITHM
 29///     <br/>
 30///     - As in the Dijkstra Algorithm, a dictionary BP, mapping each vertex to its currently known shortest distance
 31///       from the start and the previous vertex in a path with such a distance is instantiated.
 32///       <br/>
 33///     - Then BP is initialized to only contains the start vertex s, which is a distance 0 from itself via an empty
 34///       path.
 35///       <br/>
 36///     - After that, the main loop of algorithm is executed v times, where v is the number of edges in the graph.
 37///       <br/>
 38///     - At each iteration, all the edges in the graph are visited and <b>relaxed</b>.
 39///       <br/>
 40///     - Edge (u, v) relation is done in the following way: if the distance of u from s in BP is not defined, it is to
 41///       be considered as +Infinity. Therefore, there is no viable path from s to v via u, and no relation is
 42///       possible via the edge (u, v).
 43///       <br/>
 44///     - If the distance BP[u].d of u from s in BP is defined instead, but the distance of v from s in BP is not,
 45///       the path going from s to v via u becomes the shortest knows, and is set into BP[v].
 46///       <br/>
 47///     - If both distances BP[u].d and BP[v].d of u and v from s in BP are defined, there are two possible cases.
 48///       <br/>
 49///     - Either BP[v].d is non-bigger than BP[u].d + the distance of (u, v), in which case the edge (u, v) won't
 50///       decrease the current estimate of the shortest path from s to v and won't be relaxed.
 51///       <br/>
 52///     - Or BP[v].d is strictly bigger, in which case the edge (u, v) does decrease the currently known shortest path
 53///       from s to v, and will be relaxed, updating BP[v].
 54///       <br/>
 55///     - After v - 1 iterations, all edges are fully relaxed if there are no negative cycles.
 56///       <br/>
 57///     - To check whether that's the case, a last, v-th iteration, is performed. If no edge is relaxed, there are no
 58///       negative cycles. Otherwise, there are. The set VR, of target vertices of edges relaxed at the v-th iteration,
 59///       is stored.
 60///       <br/>
 61///     - If there are negative cycles, each vertex v in VR, and each vertex reachable from v, has -Infinite distance
 62///       from the start. So a DFS is executed on the graph for each v in VR, and BP is updating, setting BP[v].d
 63///       to -Infinity and BP[v].previousVertex to null (since there is no actual finite shortest path).
 64///       <br/>
 65///     - If the end vertex is at a finite distance from the start, BP[e] contains such shortest distance, and the
 66///       shortest path can be found by backtracking on previous pointers via BP, from e all the way back to s.
 67///       <br/>
 68///     - Otherwise -Infinity or +Infinity is returned, with an empty path, because either no path exists from the
 69///       start to the end, or a path exists, but the shortest is infinitely long.
 70///     </para>
 71///     <para id="complexity">
 72///     COMPLEXITY
 73///     <br/>
 74///     - BP initialization is done in constant time.
 75///       <br/>
 76///     - The main loop of the algorithm is performed v times.
 77///       <br/>
 78///     - Each iteration checks and possibly relaxes all e edges of the graph. A single graph relation requires
 79///       checking values in BP and edge distances, which are all constant-time operations.
 80///       <br/>
 81///     - Retrieving all e edges has a complexity which is specific to the <see cref="IGraph"/> implementation: in a
 82///       <see cref="EdgeListGraph"/> it is a O(1) operation, since edges are stored as a flat list.
 83///       <br/>
 84///     - In a <see cref="AdjacencyListGraph"/> it is a O(v) operation, since edges are stored in neighborhoods of the
 85///       v vertices.
 86///       <br/>
 87///     - In a <see cref="AdjacencyMatrixGraph"/> it is a O(v^2) operation, as it requires going through the matrix.
 88///       <br/>
 89///     - In case the presence of negative cycles is detected, up to r DFS explorations are performed, where r is the
 90///       number of vertices in VR (i.e. target of edges relaxed during the v-th iteration of the main loop).
 91///       <br/>
 92///     - In the worst case that means work proportional to v * (v + e), when r = v and assuming linear cost for DFS.
 93///       <br/>
 94///     - In case there are no negative cycles, up to v more iterations are performed to find the shortest path from
 95///       s to e.
 96///       <br/>
 97///     - In conclusion Time Complexity is O(v * (v * Tn + e)), where Tn is the time to retrieve the neighborhood of
 98///       a single vertex. Space Complexity is O(v + Sn), since BP contain at most v items, of constant size.
 99///     </para>
 100/// </remarks>
 101public class BellmanFordShortestDistanceFinder : IShortestDistanceFinder
 102{
 103    /// <summary>
 104    /// A building function able to instantiate the <see cref="IVisitStrategy"/> to be used to find all reachable
 105    /// vertices of vertices relaxed in the last iteration of the main loop of the Bellman-Ford algorithm, by running
 106    /// a Depth First Searches from the start vertex via
 107    /// <see cref="IVisitStrategy.DepthFirstSearchFromVertex(IGraph, int)"/>.
 108    /// </summary>
 359109    public Func<IVisitStrategy> VisitStrategyBuilder { get; }
 110
 111    /// <summary>
 112    ///     <inheritdoc cref="BellmanFordShortestDistanceFinder"/>
 113    /// </summary>
 114    /// <param name="visitStrategyBuilder">
 115    ///     <inheritdoc cref="VisitStrategyBuilder" path="/summary"/>
 116    /// </param>
 117    /// <remarks>
 118    ///     <inheritdoc cref="BellmanFordShortestDistanceFinder"/>
 119    /// </remarks>
 59120    public BellmanFordShortestDistanceFinder(Func<IVisitStrategy> visitStrategyBuilder)
 59121    {
 59122        VisitStrategyBuilder = visitStrategyBuilder;
 59123    }
 124
 125    /// <inheritdoc path="//*[not(self::remarks)]"/>
 126    /// <remarks>
 127    ///     <inheritdoc cref="BellmanFordShortestDistanceFinder"/>
 128    /// </remarks>
 129    public (int, IList<int>) Find(IGraph graph, IGraphDistances distances, int start, int end)
 363130    {
 363131        ShortestDistanceFinderHelper.ValidateParameters(graph, start, end);
 132
 359133        var treeFinder = new ShortestDistanceTree.BellmanFordShortestDistanceTreeFinder(VisitStrategyBuilder);
 359134        var bestPreviouses = treeFinder.FindTree(graph, distances, start);
 135
 359136        if (!bestPreviouses.Values.ContainsKey(end))
 160137            return (int.MaxValue, Array.Empty<int>());
 138
 199139        var shortestDistance = bestPreviouses.Values[end].DistanceFromStart;
 199140        if (shortestDistance == int.MinValue)
 23141            return (int.MinValue, Array.Empty<int>());
 142
 176143        var shortestPath = ShortestDistanceFinderHelper.BuildShortestPath(end, bestPreviouses);
 144
 176145        return (shortestDistance, shortestPath);
 359146    }
 147}
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)