| | | 1 | | using MoreStructures.Graphs.Visitor; |
| | | 2 | | |
| | | 3 | | namespace MoreStructures.Graphs.Sorting; |
| | | 4 | | |
| | | 5 | | /// <summary> |
| | | 6 | | /// An <see cref="ITopologicalSort"/> implementation which assigns topological order to vertices by identifing a sink |
| | | 7 | | /// vertex at each iteration <b>in a deterministic way</b>, by running DFS once on the entire graph and storing the |
| | | 8 | | /// post order. |
| | | 9 | | /// </summary> |
| | | 10 | | /// <remarks> |
| | | 11 | | /// <para id="advantages"> |
| | | 12 | | /// ADVANTAGES AND DISADVANTAGES |
| | | 13 | | /// <br/> |
| | | 14 | | /// - This implementation is a conceptual improvement over both <see cref="AnyPathToSinkBasedTopologicalSort"/> and |
| | | 15 | | /// <see cref="DfsOnEachVertexSinkBasedTopologicalSort"/>. |
| | | 16 | | /// <br/> |
| | | 17 | | /// - The optimization is based on the observation that a lot of the DFS traversal, done by |
| | | 18 | | /// <see cref="DfsOnEachVertexSinkBasedTopologicalSort"/> to populate its "reachability dictionary", is shared |
| | | 19 | | /// between many of the vertices connected together, and doesn't need to be repeated every time. |
| | | 20 | | /// <br/> |
| | | 21 | | /// - For example, in a simple graph <c>A1 -> A2 -> ... -> An</c>, the DFS on A1 and the DFS on A2 share the path |
| | | 22 | | /// <c>A2 -> ... -> An</c>, the DFS on A1 and A3 share the path <c>A3 -> ... -> An</c>, etc. |
| | | 23 | | /// <br/> |
| | | 24 | | /// - While <see cref="AnyPathToSinkBasedTopologicalSort"/> doesn't explicitely use a |
| | | 25 | | /// <see cref="IVisitStrategy.DepthFirstSearchFromVertex"/>, its strategy can be seen as a DFS traversal if |
| | | 26 | | /// the initial vertex and the path followed at each iteration are taken consistently. |
| | | 27 | | /// <br/> |
| | | 28 | | /// - Therefore, this implementation is an improvement of both previously mentioned implementations. |
| | | 29 | | /// <br/> |
| | | 30 | | /// - Moreover, if the DFS traversal is deterministic, this algorithm also is. |
| | | 31 | | /// </para> |
| | | 32 | | /// <para id="algorithm"> |
| | | 33 | | /// ALGORITHM |
| | | 34 | | /// <br/> |
| | | 35 | | /// - A full DFS traversal of the entire DAG is performed via |
| | | 36 | | /// <see cref="IVisitStrategy.DepthFirstSearchOfGraph(IGraph)"/> on a <see cref="IVisitStrategy"/> built by the |
| | | 37 | | /// <see cref="VisitStrategyBuilder"/> provided in the constructor. |
| | | 38 | | /// <br/> |
| | | 39 | | /// - Before running the DFS traversal, a post-visit event handler is attached to |
| | | 40 | | /// <see cref="IVisitStrategy.VisitedVertex"/>, running a post-order counter which is incremented at every visit. |
| | | 41 | | /// <br/> |
| | | 42 | | /// - The value of the post-order counter is stored in an array TS of v integers, where v is the number of vertices |
| | | 43 | | /// in the graph, at a position defined by the id of the vertex. |
| | | 44 | | /// <br/> |
| | | 45 | | /// - Finally, the array TS is returned. |
| | | 46 | | /// </para> |
| | | 47 | | /// <para id="complexity"> |
| | | 48 | | /// COMPLEXITY |
| | | 49 | | /// <br/> |
| | | 50 | | /// - Running DFS for the entire graph via <see cref="IVisitStrategy.DepthFirstSearchFromVertex"/> is a |
| | | 51 | | /// generally expensive operation, which has a Time and Space Complexity which depends on the specific |
| | | 52 | | /// <see cref="IVisitStrategy"/> used. |
| | | 53 | | /// <br/> |
| | | 54 | | /// - However, unlike in <see cref="DfsOnEachVertexSinkBasedTopologicalSort"/>, it is performed once, and not for |
| | | 55 | | /// each vertex. |
| | | 56 | | /// <br/> |
| | | 57 | | /// - Instantiating the TS array is a O(v) operation, both in time and space. |
| | | 58 | | /// <br/> |
| | | 59 | | /// - Storing, updating and assigning the post-order counter to the right item of TS are all constant-time |
| | | 60 | | /// operations. |
| | | 61 | | /// <br/> |
| | | 62 | | /// - Therefore Time Complexity is O(Tdfs + v) and Space Complexity is O(Sdfs + v). |
| | | 63 | | /// <br/> |
| | | 64 | | /// - Using <see cref="FullyIterativeHashSetBasedGraphVisit"/> as <see cref="IVisitStrategy"/> and assuming |
| | | 65 | | /// <see cref="IGraph.GetAdjacentVerticesAndEdges(int, bool)"/> can be computed in constant time, Tdfs and Sdfs |
| | | 66 | | /// becomes linear in v and e. |
| | | 67 | | /// <br/> |
| | | 68 | | /// - In this case, Time Complexity becomes O(v + e) and Space Complexity becomes O(v). |
| | | 69 | | /// </para> |
| | | 70 | | /// </remarks> |
| | | 71 | | public class SingleDfsSinkBasedTopologicalSort : ITopologicalSort |
| | | 72 | | { |
| | | 73 | | /// <summary> |
| | | 74 | | /// A visitor builder, to be used to build the <see cref="IVisitStrategy"/> instance needed to identify sink |
| | | 75 | | /// vertices, by running a Depth First Search on the graph. |
| | | 76 | | /// </summary> |
| | 18 | 77 | | public Func<IVisitStrategy> VisitStrategyBuilder { get; } |
| | | 78 | | |
| | | 79 | | /// <summary> |
| | | 80 | | /// <inheritdoc cref="SingleDfsSinkBasedTopologicalSort"/> |
| | | 81 | | /// </summary> |
| | | 82 | | /// <param name="visitStrategyBuilder"> |
| | | 83 | | /// <inheritdoc cref="VisitStrategyBuilder" path="/summary"/> |
| | | 84 | | /// </param> |
| | | 85 | | /// <remarks> |
| | | 86 | | /// <inheritdoc cref="SingleDfsSinkBasedTopologicalSort"/> |
| | | 87 | | /// </remarks> |
| | 18 | 88 | | public SingleDfsSinkBasedTopologicalSort(Func<IVisitStrategy> visitStrategyBuilder) |
| | 18 | 89 | | { |
| | 18 | 90 | | VisitStrategyBuilder = visitStrategyBuilder; |
| | 18 | 91 | | } |
| | | 92 | | |
| | | 93 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 94 | | /// <remarks> |
| | | 95 | | /// <inheritdoc cref="SingleDfsSinkBasedTopologicalSort"/> |
| | | 96 | | /// </remarks> |
| | | 97 | | public IList<int> Sort(IGraph dag) |
| | 18 | 98 | | { |
| | | 99 | | // Find reachable nodes for each vertex |
| | 18 | 100 | | var numberOfVertices = dag.GetNumberOfVertices(); |
| | | 101 | | |
| | 18 | 102 | | var topologicalSort = new int[numberOfVertices]; |
| | 18 | 103 | | var postOrder = numberOfVertices - 1; |
| | 18 | 104 | | var visitStrategy = VisitStrategyBuilder(); |
| | | 105 | | |
| | 57 | 106 | | visitStrategy.VisitedVertex += (o, e) => topologicalSort[e.Vertex] = postOrder--; |
| | | 107 | | |
| | | 108 | | // Loop detection |
| | 18 | 109 | | var currentPath = new HashSet<int>(); |
| | 77 | 110 | | visitStrategy.VisitingVertex += (o, e) => currentPath.Add(e.Vertex); |
| | 57 | 111 | | visitStrategy.VisitedVertex += (o, e) => currentPath.Remove(e.Vertex); |
| | 18 | 112 | | visitStrategy.AlreadyVisitedVertex += (o, e) => |
| | 22 | 113 | | { |
| | 22 | 114 | | if (currentPath.Contains(e.Vertex)) |
| | 7 | 115 | | throw new InvalidOperationException($"The provided {nameof(dag)} is not a Direct Acyclic Graph"); |
| | 33 | 116 | | }; |
| | | 117 | | |
| | 18 | 118 | | MoreLinq.MoreEnumerable.Consume(visitStrategy.DepthFirstSearchOfGraph(dag)); |
| | | 119 | | |
| | 11 | 120 | | return topologicalSort; |
| | 11 | 121 | | } |
| | | 122 | | } |