| | | 1 | | using MoreStructures.Graphs.ShortestDistance; |
| | | 2 | | using MoreStructures.Graphs.Visitor; |
| | | 3 | | |
| | | 4 | | namespace MoreStructures.Graphs.ShortestDistanceTree; |
| | | 5 | | |
| | | 6 | | /// <summary> |
| | | 7 | | /// A <see cref="IShortestDistanceFinder"/> implementation based on the Bellman-Ford algorithm. |
| | | 8 | | /// </summary> |
| | | 9 | | /// <remarks> |
| | | 10 | | /// <para id="requirements"> |
| | | 11 | | /// REQUIREMENTS |
| | | 12 | | /// <br/> |
| | | 13 | | /// - Same as <see cref="BellmanFordShortestDistanceFinder"/>. |
| | | 14 | | /// </para> |
| | | 15 | | /// <para id="algorithm"> |
| | | 16 | | /// ALGORITHM |
| | | 17 | | /// <br/> |
| | | 18 | | /// - The algorithm closely resembles the one used in <see cref="BellmanFordShortestDistanceFinder"/>, with the |
| | | 19 | | /// only main difference that paths from the start vertex are reconstructed, since that would need to be done |
| | | 20 | | /// for each of the vertices of the graph, resulting in a worst case O(v^2) Space Complexity. |
| | | 21 | | /// <br/> |
| | | 22 | | /// - Unlike <see cref="DijkstraShortestDistanceTreeFinder"/>, which can improve w.r.t. |
| | | 23 | | /// <see cref="DijkstraShortestDistanceFinder"/> on the average runtime, while the worst case is still bound to |
| | | 24 | | /// the total number of vertices in the graph, <see cref="BellmanFordShortestDistanceTreeFinder"/> cannot provide |
| | | 25 | | /// the same average running time improvement over <see cref="BellmanFordShortestDistanceFinder"/>, since the |
| | | 26 | | /// Bellman-Ford algorithm still requires v - 1 iterations to find optimal distances from the start vertex, and |
| | | 27 | | /// one iteration more, to be able to identify negative cycles and set shortest distance to minus infinity, for |
| | | 28 | | /// all vertices reachable from a negative cycle. |
| | | 29 | | /// </para> |
| | | 30 | | /// <para id="complexity"> |
| | | 31 | | /// COMPLEXITY |
| | | 32 | | /// <br/> |
| | | 33 | | /// - Same analysis as in <see cref="BellmanFordShortestDistanceFinder"/>. |
| | | 34 | | /// <br/> |
| | | 35 | | /// - The fact that the algorithm doesn't reconstruct shortest paths doesn't reduce the overall complexity, which |
| | | 36 | | /// is bound to the v iterations of the main loop of the algorithm, each one relaxing at most e edges. |
| | | 37 | | /// <br/> |
| | | 38 | | /// - Therefore, as in single path Bellman-Ford's algorithm variant, Time Complexity is O(v * (v * Tn + e)) and |
| | | 39 | | /// Space Complexity is O(v + Sn), where Tn and Sn are the time and space to retrieve the neighborhood of a |
| | | 40 | | /// single vertex. |
| | | 41 | | /// </para> |
| | | 42 | | /// </remarks> |
| | | 43 | | public class BellmanFordShortestDistanceTreeFinder : IShortestDistanceTreeFinder |
| | | 44 | | { |
| | | 45 | | /// <summary> |
| | | 46 | | /// A building function able to instantiate the <see cref="IVisitStrategy"/> to be used to find all reachable |
| | | 47 | | /// vertices of vertices relaxed in the last iteration of the main loop of the Bellman-Ford algorithm, by running |
| | | 48 | | /// a Depth First Searches from the start vertex via |
| | | 49 | | /// <see cref="IVisitStrategy.DepthFirstSearchFromVertex(IGraph, int)"/>. |
| | | 50 | | /// </summary> |
| | 379 | 51 | | public Func<IVisitStrategy> VisitStrategyBuilder { get; } |
| | | 52 | | |
| | | 53 | | /// <summary> |
| | | 54 | | /// <inheritdoc cref="BellmanFordShortestDistanceTreeFinder"/> |
| | | 55 | | /// </summary> |
| | | 56 | | /// <param name="visitStrategyBuilder"> |
| | | 57 | | /// <inheritdoc cref="VisitStrategyBuilder" path="/summary"/> |
| | | 58 | | /// </param> |
| | | 59 | | /// <remarks> |
| | | 60 | | /// <inheritdoc cref="BellmanFordShortestDistanceFinder"/> |
| | | 61 | | /// </remarks> |
| | 379 | 62 | | public BellmanFordShortestDistanceTreeFinder(Func<IVisitStrategy> visitStrategyBuilder) |
| | 379 | 63 | | { |
| | 379 | 64 | | VisitStrategyBuilder = visitStrategyBuilder; |
| | 379 | 65 | | } |
| | | 66 | | |
| | | 67 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 68 | | /// <remarks> |
| | | 69 | | /// <inheritdoc cref="BellmanFordShortestDistanceFinder"/> |
| | | 70 | | /// </remarks> |
| | | 71 | | public BestPreviouses FindTree(IGraph graph, IGraphDistances distances, int start) |
| | 379 | 72 | | { |
| | 379 | 73 | | ShortestDistanceFinderHelper.ValidateParameters(graph, start, null); |
| | | 74 | | |
| | 379 | 75 | | var numberOfVertices = graph.GetNumberOfVertices(); |
| | 379 | 76 | | var bestPreviouses = new BestPreviouses(new() { [start] = new(0, -1) }); |
| | | 77 | | |
| | 379 | 78 | | var verticesRelaxedInLastIteration = new HashSet<int>(); |
| | 7478 | 79 | | for (var iteration = 1; iteration <= numberOfVertices; iteration++) |
| | 3360 | 80 | | RelaxEdges(graph, distances, numberOfVertices, bestPreviouses, iteration, verticesRelaxedInLastIteration); |
| | | 81 | | |
| | 379 | 82 | | SetToMinusInfinity(graph, bestPreviouses, verticesRelaxedInLastIteration, VisitStrategyBuilder); |
| | 379 | 83 | | return bestPreviouses; |
| | 379 | 84 | | } |
| | | 85 | | |
| | | 86 | | private static void RelaxEdges( |
| | | 87 | | IGraph graph, IGraphDistances distances, int numberOfVertices, |
| | | 88 | | BestPreviouses bestPreviouses, int iteration, HashSet<int> verticesRelaxedInLastIteration) |
| | 3360 | 89 | | { |
| | 73712 | 90 | | for (var source = 0; source < numberOfVertices; source++) |
| | 33496 | 91 | | { |
| | 186348 | 92 | | foreach (var (target, edgeStart, edgeEnd) in graph.GetAdjacentVerticesAndEdges(source, true)) |
| | 42930 | 93 | | { |
| | 42930 | 94 | | if (!bestPreviouses.Values.TryGetValue(source, out var sourceBest)) |
| | 26781 | 95 | | continue; |
| | | 96 | | |
| | 16149 | 97 | | var newTargetDistance = sourceBest.DistanceFromStart + distances[(edgeStart, edgeEnd)]; |
| | 16149 | 98 | | if (!bestPreviouses.Values.TryGetValue(target, out var targetBest) || |
| | 16149 | 99 | | targetBest.DistanceFromStart > newTargetDistance) |
| | 2149 | 100 | | { |
| | 2149 | 101 | | if (iteration == numberOfVertices) |
| | 33 | 102 | | verticesRelaxedInLastIteration.Add(target); |
| | | 103 | | else |
| | 2116 | 104 | | bestPreviouses.Values[target] = new(newTargetDistance, source); |
| | 2149 | 105 | | } |
| | 16149 | 106 | | } |
| | 33496 | 107 | | } |
| | 3360 | 108 | | } |
| | | 109 | | |
| | | 110 | | private static void SetToMinusInfinity(IGraph graph, BestPreviouses bestPreviouses, |
| | | 111 | | HashSet<int> verticesRelaxedInLastIteration, Func<IVisitStrategy> visitStrategyBuilder) |
| | 379 | 112 | | { |
| | 379 | 113 | | if (verticesRelaxedInLastIteration.Count == 0) |
| | 346 | 114 | | return; |
| | | 115 | | |
| | 33 | 116 | | var visitor = visitStrategyBuilder(); |
| | 287 | 117 | | foreach (var reachableVertex in visitor.BreadthFirstSearchFromVertices(graph, verticesRelaxedInLastIteration)) |
| | 94 | 118 | | bestPreviouses.Values[reachableVertex] = new(int.MinValue, -1); |
| | 379 | 119 | | } |
| | | 120 | | } |