| | | 1 | | using MoreLinq.Extensions; |
| | | 2 | | using MoreStructures.Graphs.Visitor; |
| | | 3 | | |
| | | 4 | | namespace MoreStructures.Graphs.ShortestPath; |
| | | 5 | | |
| | | 6 | | /// <summary> |
| | | 7 | | /// An implementation of <see cref="IShortestPathFinder"/> which performs a BFS traversal, starting from the start |
| | | 8 | | /// vertex, to find the shortest path to the end vertex. |
| | | 9 | | /// </summary> |
| | | 10 | | /// <remarks> |
| | | 11 | | /// <para id="algorithm"> |
| | | 12 | | /// ALGORITHM |
| | | 13 | | /// <br/> |
| | | 14 | | /// - A <see cref="IVisitStrategy"/> is instantiated via the <see cref="VisitStrategyBuilder"/> provided in the |
| | | 15 | | /// constructor. |
| | | 16 | | /// <br/> |
| | | 17 | | /// - The <see cref="IVisitStrategy"/> instance is instrumented, by adding an event handler H to the |
| | | 18 | | /// <see cref="IVisitStrategy.VisitingVertex"/>. |
| | | 19 | | /// <br/> |
| | | 20 | | /// - The event handler H maps each visited vertex to its previous vertex (i.e. the vertex whose visit has trigger |
| | | 21 | | /// the visit of this vertex), as stored in <see cref="VisitEventArgs.PreviousVertex"/> passed by the |
| | | 22 | | /// <see cref="IVisitStrategy.VisitingVertex"/> event, into a <see cref="IDictionary{TKey, TValue}"/> D. |
| | | 23 | | /// <br/> |
| | | 24 | | /// - A Breadth First Search from the start vertex is executed, running |
| | | 25 | | /// <see cref="IVisitStrategy.BreadthFirstSearchFromVertex"/>. The result of the visit is consumed (i.e. the |
| | | 26 | | /// visit is done) until either the end vertex is encountered, or when there are no more vertices reachable from |
| | | 27 | | /// the start vertex, which haven't been visited yet. |
| | | 28 | | /// <br/> |
| | | 29 | | /// - If the end vertex hasn't been discovered during the visit, it is not reachable. Therefore, a length of path |
| | | 30 | | /// equal to <see cref="int.MaxValue"/> and an empty path are returned. |
| | | 31 | | /// <br/> |
| | | 32 | | /// - If the end vertex has been reached, the end vertex has been visited and it is contained in D. |
| | | 33 | | /// <br/> |
| | | 34 | | /// - D is traversed backwards, from the end to the start vertex, rebuilding the (reversed) path. |
| | | 35 | | /// <br/> |
| | | 36 | | /// - Finally, the path is reversed and returned as result. |
| | | 37 | | /// <br/> |
| | | 38 | | /// - Its length minus 1 represents the length of the path between start and end vertex. |
| | | 39 | | /// </para> |
| | | 40 | | /// <para id="complexity"> |
| | | 41 | | /// COMPLEXITY |
| | | 42 | | /// <br/> |
| | | 43 | | /// - While building the <see cref="IVisitStrategy"/> instance has a complexity that depends on the user-provided |
| | | 44 | | /// <see cref="VisitStrategyBuilder"/>, it doesn't generally depends on the size of the graph to be visited, and |
| | | 45 | | /// can be considered O(1) work. |
| | | 46 | | /// <br/> |
| | | 47 | | /// - Instrumenting the <see cref="IVisitStrategy"/> instance and running the handler for every visited vertex are |
| | | 48 | | /// also constant-time operations. |
| | | 49 | | /// <br/> |
| | | 50 | | /// - The complexity of the BFS visit depends on the actual <see cref="IVisitStrategy"/> implementation used. |
| | | 51 | | /// <br/> |
| | | 52 | | /// - Rebuilding and reversing the path takes time and space proportional to the length of the path, which in the |
| | | 53 | | /// worst case can be O(v) where v is the number of vertices of the graph. |
| | | 54 | | /// <br/> |
| | | 55 | | /// - Therefore, Time Complexity is O(Tbfs + v) and Space Complexity is O(Sbfs + v). |
| | | 56 | | /// <br/> |
| | | 57 | | /// - If <see cref="FullyIterativeHashSetBasedGraphVisit"/> or <see cref="FullyRecursiveHashSetBasedGraphVisit"/> |
| | | 58 | | /// visits are used, with an <see cref="IGraph"/> retrieving neighbors in constant time, Time and Space |
| | | 59 | | /// Complexity become O(v + e). |
| | | 60 | | /// </para> |
| | | 61 | | /// </remarks> |
| | | 62 | | public class BfsBasedShortestPathFinder : IShortestPathFinder |
| | | 63 | | { |
| | | 64 | | /// <summary> |
| | | 65 | | /// A building function able to instantiate the <see cref="IVisitStrategy"/> to be used to find the shortest path, |
| | | 66 | | /// by running a Breadth First Searches from the start vertex via |
| | | 67 | | /// <see cref="IVisitStrategy.BreadthFirstSearchFromVertex(IGraph, int)"/>. |
| | | 68 | | /// </summary> |
| | 8 | 69 | | public Func<IVisitStrategy> VisitStrategyBuilder { get; } |
| | | 70 | | |
| | | 71 | | /// <summary> |
| | | 72 | | /// <inheritdoc cref="BfsBasedShortestPathFinder"/> |
| | | 73 | | /// </summary> |
| | | 74 | | /// <param name="visitStrategyBuilder"> |
| | | 75 | | /// <inheritdoc cref="VisitStrategyBuilder" path="/summary"/> |
| | | 76 | | /// </param> |
| | | 77 | | /// <remarks> |
| | | 78 | | /// <inheritdoc cref="BfsBasedShortestPathFinder"/> |
| | | 79 | | /// </remarks> |
| | 8 | 80 | | public BfsBasedShortestPathFinder(Func<IVisitStrategy> visitStrategyBuilder) |
| | 8 | 81 | | { |
| | 8 | 82 | | VisitStrategyBuilder = visitStrategyBuilder; |
| | 8 | 83 | | } |
| | | 84 | | |
| | | 85 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 86 | | /// <remarks> |
| | | 87 | | /// <inheritdoc cref="BfsBasedShortestPathFinder"/> |
| | | 88 | | /// </remarks> |
| | | 89 | | public (int, IList<int>) Find(IGraph graph, int start, int end) |
| | 8 | 90 | | { |
| | 8 | 91 | | var visitor = VisitStrategyBuilder(); |
| | | 92 | | |
| | 8 | 93 | | var previousVertices = new Dictionary<int, int?>(); |
| | 32 | 94 | | visitor.VisitingVertex += (o, e) => previousVertices[e.Vertex] = e.PreviousVertex; |
| | | 95 | | |
| | 8 | 96 | | visitor |
| | 8 | 97 | | .BreadthFirstSearchFromVertex(graph, start) |
| | 24 | 98 | | .TakeWhile(vertex => vertex != end) |
| | 8 | 99 | | .Consume(); |
| | | 100 | | |
| | 8 | 101 | | if (!previousVertices.ContainsKey(end)) |
| | 2 | 102 | | return (int.MaxValue, new List<int> { }); |
| | | 103 | | |
| | 6 | 104 | | var path = BuildShortestPath(end, previousVertices); |
| | | 105 | | |
| | 6 | 106 | | return (path.Count - 1, path); |
| | 8 | 107 | | } |
| | | 108 | | |
| | | 109 | | private static IList<int> BuildShortestPath(int end, Dictionary<int, int?> previousVertices) |
| | 6 | 110 | | { |
| | 6 | 111 | | var path = new List<int>(); |
| | 6 | 112 | | int? maybeCurrentVertex = end; |
| | 21 | 113 | | while (maybeCurrentVertex is int currentVertex) |
| | 15 | 114 | | { |
| | 15 | 115 | | path.Add(currentVertex); |
| | 15 | 116 | | maybeCurrentVertex = previousVertices[currentVertex]; |
| | 15 | 117 | | } |
| | 6 | 118 | | path.Reverse(); |
| | 6 | 119 | | return path; |
| | 6 | 120 | | } |
| | | 121 | | } |