| | | 1 | | namespace MoreStructures.Graphs.Sorting; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// An <see cref="ITopologicalSort"/> implementation which assigns topological order to vertices by identifing a sink |
| | | 5 | | /// vertex at each iteration <b>in a non-deterministic way</b>, picking some start vertex and following some path to a |
| | | 6 | | /// sink. |
| | | 7 | | /// </summary> |
| | | 8 | | /// <remarks> |
| | | 9 | | /// <para id="advantages"> |
| | | 10 | | /// ADVANTAGES AND DISADVANTAGES |
| | | 11 | | /// <br/> |
| | | 12 | | /// - Compared to <see cref="DfsOnEachVertexSinkBasedTopologicalSort"/>, it has better runtime (quadratic, rather |
| | | 13 | | /// than cubic, over the number of vertices on the graph). |
| | | 14 | | /// <br/> |
| | | 15 | | /// - However, the algorithm picks a vertex and follows a path at random (using the LINQ method |
| | | 16 | | /// <see cref="Enumerable.FirstOrDefault{TSource}(IEnumerable{TSource})"/> on a <see cref="HashSet{T}"/>, which |
| | | 17 | | /// is not sorted and doesn't provide any guarantee about ordering). |
| | | 18 | | /// <br/> |
| | | 19 | | /// - Therefore, unlike <see cref="DfsOnEachVertexSinkBasedTopologicalSort"/>, the topological order produced when |
| | | 20 | | /// multiple results are possible, is not defined. |
| | | 21 | | /// </para> |
| | | 22 | | /// <para id="algorithm"> |
| | | 23 | | /// ALGORITHM |
| | | 24 | | /// <br/> |
| | | 25 | | /// - The number of vertices v in the DAG is computed via <see cref="IGraph.GetNumberOfVertices"/>. |
| | | 26 | | /// <br/> |
| | | 27 | | /// - Then, a set of the integers from 0 to v-1 is instantiated, keeping the remaining vertices not sorted yet, |
| | | 28 | | /// together with an array TS of v integers, to accomodate the topological sort value for each of the vertices. |
| | | 29 | | /// <br/> |
| | | 30 | | /// - Then, the main loop of the algorithm is executed, while there are still unsorted vertices. |
| | | 31 | | /// <br/> |
| | | 32 | | /// - Any of the sorted vertices v is taken, and a directed path v is followed until a sink vertex s is found. |
| | | 33 | | /// <br/> |
| | | 34 | | /// - If, while following a path, a loop is detected (i.e. a vertex is visited again), an exception is thrown. |
| | | 35 | | /// <br/> |
| | | 36 | | /// - Otherwise, the found sink can be assigned the highest unassigned sort value (v-1 down to 0), and the loop |
| | | 37 | | /// repeats. |
| | | 38 | | /// <br/> |
| | | 39 | | /// - When all vertices have been sorted, TS can be returned as result. |
| | | 40 | | /// </para> |
| | | 41 | | /// <para id="complexity"> |
| | | 42 | | /// COMPLEXITY |
| | | 43 | | /// <br/> |
| | | 44 | | /// - Getting the number of vertices is a constant-time operation in most <see cref="IGraph"/> implementations. |
| | | 45 | | /// <br/> |
| | | 46 | | /// - Instantiating the set of unsorted vertices, instantiating the output array, and getting the first available |
| | | 47 | | /// vertex from the set of unsorted vertices are all O(v) operations, both in time and space. |
| | | 48 | | /// <br/> |
| | | 49 | | /// - The main loop of the algorithm is executed v times. |
| | | 50 | | /// <br/> |
| | | 51 | | /// - Each iteration can potentially explore the entire graph, so a path of O(v) vertices and O(v) edges. |
| | | 52 | | /// <br/> |
| | | 53 | | /// - Therefore, Time Complexity is O(v^2) and Space Complexity is O(v). |
| | | 54 | | /// </para> |
| | | 55 | | /// </remarks> |
| | | 56 | | public class AnyPathToSinkBasedTopologicalSort : ITopologicalSort |
| | | 57 | | { |
| | | 58 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 59 | | /// <remarks> |
| | | 60 | | /// <inheritdoc cref="AnyPathToSinkBasedTopologicalSort"/> |
| | | 61 | | /// </remarks> |
| | | 62 | | public IList<int> Sort(IGraph dag) |
| | 18 | 63 | | { |
| | 18 | 64 | | var numberOfVertices = dag.GetNumberOfVertices(); |
| | 18 | 65 | | var remainingVertices = Enumerable.Range(0, numberOfVertices).ToHashSet(); |
| | | 66 | | |
| | 18 | 67 | | var topologicalSort = new int[numberOfVertices]; |
| | 57 | 68 | | while (remainingVertices.FirstOrDefault(-1) is int vertex && vertex >= 0) |
| | 46 | 69 | | { |
| | | 70 | | // Follow a path until the end to find a sink |
| | 46 | 71 | | var verticesOnPath = new HashSet<int> { vertex }; |
| | | 72 | | |
| | 46 | 73 | | var currentVertex = vertex; |
| | 99 | 74 | | while (currentVertex >= 0) |
| | 99 | 75 | | { |
| | 99 | 76 | | var nextVertex = dag |
| | 99 | 77 | | .GetAdjacentVerticesAndEdges(currentVertex, true) |
| | 100 | 78 | | .Select(a => a.Vertex) |
| | 100 | 79 | | .Where(v => remainingVertices.Contains(v)) |
| | 99 | 80 | | .FirstOrDefault(-1); |
| | | 81 | | |
| | 99 | 82 | | if (nextVertex < 0) |
| | 39 | 83 | | break; // currentVertex is a sink |
| | | 84 | | |
| | 60 | 85 | | if (verticesOnPath.Contains(nextVertex)) |
| | 7 | 86 | | throw new InvalidOperationException($"The provided {nameof(dag)} is not a Direct Acyclic Graph"); |
| | | 87 | | |
| | 53 | 88 | | verticesOnPath.Add(nextVertex); |
| | 53 | 89 | | currentVertex = nextVertex; |
| | 53 | 90 | | } |
| | | 91 | | |
| | 39 | 92 | | topologicalSort[currentVertex] = remainingVertices.Count - 1; |
| | 39 | 93 | | remainingVertices.Remove(currentVertex); |
| | 39 | 94 | | } |
| | | 95 | | |
| | 11 | 96 | | return topologicalSort; |
| | 11 | 97 | | } |
| | | 98 | | } |