< Summary

Information
Class: MoreStructures.Graphs.ShortestDistance.BidirectionalDijkstraShortestDistanceFinder
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/Graphs/ShortestDistance/BidirectionalDijkstraShortestDistanceFinder.cs
Line coverage
100%
Covered lines: 72
Uncovered lines: 0
Coverable lines: 72
Total lines: 195
Line coverage: 100%
Branch coverage
100%
Covered branches: 20
Total branches: 20
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
get_PriorityQueueBuilder()100%1100%
.ctor(...)100%1100%
get_Graph()100%1100%
get_DistancesFunc()100%1100%
get_BestPreviouses()100%1100%
get_Added()100%1100%
get_Vertexes()100%1100%
get_LastAdded()100%1100%
get_IsFinished()100%1100%
.ctor(...)100%1100%
OverlapsWith(...)100%4100%
RunStep()100%4100%
FindMeetingPointVertexOnShortestPath(...)100%1100%
Find(...)100%12100%

File(s)

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

#LineLine coverage
 1using MoreStructures.PriorityQueues;
 2
 3namespace MoreStructures.Graphs.ShortestDistance;
 4
 5/// <summary>
 6/// A <see cref="IShortestDistanceFinder"/> implementation based on a refinement of the Dijkstra algorithm, running
 7/// search in two parallel inversed flows: from the start vertext to the end vertex and viceversa.
 8/// </summary>
 9/// <remarks>
 10///     <para id="requirements">
 11///     REQUIREMENTS
 12///     <br/>
 13///     - Same as <see cref="DijkstraShortestDistanceFinder"/>.
 14///     </para>
 15///     <para id="algorithm">
 16///     ALGORITHM
 17///     <br/>
 18///     - The algorithm runs in parallel two searches: one from the start vertex s and the other one from the end
 19///       vertex e.
 20///       <br/>
 21///     - The search from s is called <b>forward search</b> and is run on the provided directed graph, with the
 22///       provided distance function, as it is done in a normal Dijkstra's algorithm execution.
 23///       <br/>
 24///     - The search from e is called <b>backward search</b> and is run on the reversed graph, with a reversed distance
 25///       function: <c>reversedDistance(edgeStart, edgeEnd) = distance(edgeEnd, edgeStart)</c>.
 26///       <br/>
 27///     - Each search has its own dictionary BP, set A, priority queue PQ and last added vertex LA, which are described
 28///       in detail in <see cref="DijkstraShortestDistanceFinder"/>. Data structures for the forward search are called
 29///       here BPf, Af, PQf and LAf. Data structures for the backward search are called here BPb, Ab, PQb, LAb.
 30///       <br/>
 31///     - After standard initialization of the two searches (which is different since they have different starting
 32///       vertex, hence different A and BP initial content etc), the two searches are executed.
 33///       <br/>
 34///     - The "parallelism" is done by running a single step of one of the two searches at each iteration, and
 35///       alternating between the two searches: first a step forward, then a step backward, then a step forward, etc.
 36///       <br/>
 37///     - The iterations continue until either a meeting point vertex v has been processed and added to both Af and Ab,
 38///       or both searches are done (i.e. no more edges to explore).
 39///       <br/>
 40///     - If the meeting point vertex v hasn't been found before the two searches would run out of edges to explore,
 41///       it means that e is not reachable from s, and <see cref="int.MaxValue"/> and an empty path are returned as
 42///       result.
 43///       <br/>
 44///     - Otherwise, a path from s to e exists. However, such a path doesn't necessarily goes through v.
 45///       <br/>
 46///     - Therefore, the vertex u, of a shortest path from s to e and such that u is known to both BPf and BPb, with
 47///       the correct  shortest path estimates in both directions, has to be found.
 48///       <br/>
 49///     - It can be proven that such a vertex u exists, which also belongs to Af or Ab or to both.
 50///       <br/>
 51///     - Therefore, all vertices in both BPf and BPf are scanned, and the one minimizing the sum of estimates, from s
 52///       and e respectively, is taken.
 53///       <br/>
 54///     - The full shortest path from s to e is then reconstructed by joining the two subpaths, going from s to u and
 55///       from u to e respectively.
 56///       <br/>
 57///     - The shortest path distance is simply the sum of shortest distances for u in BPf and BPb.
 58///     </para>
 59///     <para id="complexity">
 60///     COMPLEXITY
 61///     <br/>
 62///     - The worst case analysis is the same as for <see cref="DijkstraShortestDistanceFinder"/>: in the worst
 63///       scenario, all vertices have to be explored, before finding the meeting point or concluding that there is no
 64///       path from s to e.
 65///       <br/>
 66///     - Rebuilding the final path doesn't change the overall complexity, since calculating the intersection between
 67///       Af and Ab and finding the vertex minimizing the sum of estimates in BP are both linear time operations.
 68///       <br/>
 69///     - Therefore, Time Complexity is O((v + e) * v), O((v + e) * log(v)) or O(e + v * log(v)), depending on the
 70///       <see cref="IUpdatablePriorityQueue{T}"/> implementation chosen, as described in the documentation of
 71///       <see cref="DijkstraShortestDistanceFinder"/>. Space Complexity remains O(v).
 72///       <br/>
 73///     - While it is true that running the search both from the start and from the end doesn't help asymptotic
 74///       complexity in the worst case, it does help in the average case, i.e. on the expected number of iterations
 75///       before the algorithm stops adding vertices.
 76///       <br/>
 77///     - Intuitively, while a single run of Dijkstra's algorithm from s to e, at distance d = 2 * r from each other,
 78///       has to explore an area of the graph proportional to Pi * d^2 = 4 * Pi * r^2, a bidirectional Dijkstra's
 79///       execution explores in average an area proportional to 2 * Pi * r^2. So, half of the area.
 80///     </para>
 81/// </remarks>
 82public class BidirectionalDijkstraShortestDistanceFinder : IShortestDistanceFinder
 83{
 108084    private Func<IUpdatablePriorityQueue<int>> PriorityQueueBuilder { get; }
 85
 86    /// <inheritdoc cref="BidirectionalDijkstraShortestDistanceFinder"/>.
 87    /// <param name="priorityQueueBuilder">
 88    /// A builder of a <see cref="IUpdatablePriorityQueue{T}"/> of <see cref="int"/> values, used by the algorithm to
 89    /// store edges with priority from the closest to the start, to the farthest.
 90    /// </param>
 5991    public BidirectionalDijkstraShortestDistanceFinder(Func<IUpdatablePriorityQueue<int>> priorityQueueBuilder)
 5992    {
 5993        PriorityQueueBuilder = priorityQueueBuilder;
 5994    }
 95
 96    private sealed class Direction
 97    {
 187698        public IGraph Graph { get; }
 187699        public Func<int, int, int> DistancesFunc { get; }
 5124100        public BestPreviouses BestPreviouses { get; }
 8522101        public HashSet<int> Added { get; }
 5184102        public IUpdatablePriorityQueue<int> Vertexes { get; }
 103
 11358104        public int LastAdded { get; private set; }
 5890105        public bool IsFinished { get; private set; }
 106
 107
 1080108        public Direction(
 1080109            IGraph graph, Func<int, int, int> distancesFunc, int endpoint,
 1080110            Func<IUpdatablePriorityQueue<int>> priorityQueueBuilder)
 1080111        {
 1080112            Graph = graph;
 1080113            DistancesFunc = distancesFunc;
 1080114            BestPreviouses = new BestPreviouses(new() { [endpoint] = new(0, -1) });
 1080115            Added = new HashSet<int> { endpoint };
 1080116            Vertexes = priorityQueueBuilder();
 1080117            LastAdded = endpoint;
 1080118        }
 119
 120        public int? OverlapsWith(Direction otherDirection)
 2762121        {
 2762122            if (Added.Contains(otherDirection.LastAdded))
 316123                return otherDirection.LastAdded;
 124
 2446125            if (otherDirection.Added.Contains(LastAdded))
 2126                return LastAdded;
 127
 2444128            return null;
 2762129        }
 130
 131        public void RunStep()
 2228132        {
 2228133            if (IsFinished)
 352134                return;
 135
 1876136            ShortestDistanceFinderHelper.RelaxOutgoingEdgesOfVertex(
 1876137                Graph, DistancesFunc, BestPreviouses, Added, Vertexes, LastAdded);
 138
 1870139            if (Vertexes.Count == 0)
 432140            {
 432141                IsFinished = true;
 432142                return;
 143            }
 144
 1438145            LastAdded = Vertexes.Pop().Item;
 1438146            Added.Add(LastAdded);
 2222147        }
 148
 149        public static int? FindMeetingPointVertexOnShortestPath(Direction first, Direction second) =>
 534150            first.BestPreviouses.Values.Keys
 534151                .Intersect(second.BestPreviouses.Values.Keys)
 534152                .Cast<int?>()
 534153                .MinBy(vertex =>
 988154                    first.BestPreviouses.Values[vertex!.Value].DistanceFromStart +
 988155                    second.BestPreviouses.Values[vertex!.Value].DistanceFromStart);
 156    }
 157
 158    /// <inheritdoc path="//*[not(self::remarks)]"/>
 159    /// <remarks>
 160    ///     <inheritdoc cref="BidirectionalDijkstraShortestDistanceFinder"/>
 161    /// </remarks>
 162    public (int, IList<int>) Find(IGraph graph, IGraphDistances distances, int start, int end)
 548163    {
 548164        ShortestDistanceFinderHelper.ValidateParameters(graph, start, end);
 165
 1502166        var distancesForwardFunc = (int edgeStart, int edgeEnd) => distances[(edgeStart, edgeEnd)];
 540167        var forward = new Direction(graph, distancesForwardFunc, start, PriorityQueueBuilder);
 168
 540169        var reversedGraph = graph.Reverse();
 1384170        var distancesBackwardFunc = (int edgeStart, int edgeEnd) => distances[(edgeEnd, edgeStart)];
 540171        var backward = new Direction(reversedGraph, distancesBackwardFunc, end, PriorityQueueBuilder);
 172
 540173        var forwardTurn = true;
 2762174        while (forward.OverlapsWith(backward) == null && !(forward.IsFinished && backward.IsFinished))
 2228175        {
 2228176            var direction = forwardTurn ? forward : backward;
 2228177            direction.RunStep();
 178
 2222179            forwardTurn = !forwardTurn;
 2222180        }
 181
 534182        if (Direction.FindMeetingPointVertexOnShortestPath(forward, backward) is not int overlappingVertex)
 216183            return (int.MaxValue, Array.Empty<int>());
 184
 318185        var forwardDistance = forward.BestPreviouses.Values[overlappingVertex].DistanceFromStart;
 318186        var forwardPath = ShortestDistanceFinderHelper.BuildShortestPath(
 318187            overlappingVertex, forward.BestPreviouses);
 188
 318189        var backwardDistance = backward.BestPreviouses.Values[overlappingVertex].DistanceFromStart;
 318190        var backwardPath = ShortestDistanceFinderHelper.BuildShortestPath(
 318191            overlappingVertex, backward.BestPreviouses, false);
 192
 318193        return (forwardDistance + backwardDistance, forwardPath.SkipLast(1).Concat(backwardPath).ToList());
 534194    }
 195}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_PriorityQueueBuilder()
.ctor(System.Func`1<MoreStructures.PriorityQueues.IUpdatablePriorityQueue`1<System.Int32>>)
get_Graph()
get_DistancesFunc()
get_BestPreviouses()
get_Added()
get_Vertexes()
get_LastAdded()
get_IsFinished()
.ctor(MoreStructures.Graphs.IGraph,System.Func`3<System.Int32,System.Int32,System.Int32>,System.Int32,System.Func`1<MoreStructures.PriorityQueues.IUpdatablePriorityQueue`1<System.Int32>>)
OverlapsWith(MoreStructures.Graphs.ShortestDistance.BidirectionalDijkstraShortestDistanceFinder/Direction)
RunStep()
FindMeetingPointVertexOnShortestPath(MoreStructures.Graphs.ShortestDistance.BidirectionalDijkstraShortestDistanceFinder/Direction,MoreStructures.Graphs.ShortestDistance.BidirectionalDijkstraShortestDistanceFinder/Direction)
Find(MoreStructures.Graphs.IGraph,MoreStructures.Graphs.IGraphDistances,System.Int32,System.Int32)