| | | 1 | | using MoreStructures.Graphs.Visitor; |
| | | 2 | | |
| | | 3 | | namespace MoreStructures.Graphs.StronglyConnectedComponents; |
| | | 4 | | |
| | | 5 | | /// <summary> |
| | | 6 | | /// A simple implementation of <see cref="ISccFinder"/>, which builds a "reachability dictionary", by running a DFS |
| | | 7 | | /// on each vertex of the graph separately. |
| | | 8 | | /// </summary> |
| | | 9 | | /// <remarks> |
| | | 10 | | /// <para id="advantages"> |
| | | 11 | | /// ADVANTAGES AND DISADVANTAGES |
| | | 12 | | /// <br/> |
| | | 13 | | /// - This is the easiest, most straighforward implementation of <see cref="ISccFinder"/>. |
| | | 14 | | /// <br/> |
| | | 15 | | /// - It has, however, a cubic runtime for dense graphs, which is less than ideal. |
| | | 16 | | /// </para> |
| | | 17 | | /// <para id="algorithm"> |
| | | 18 | | /// ALGORITHM |
| | | 19 | | /// <br/> |
| | | 20 | | /// - First a dictionary R of reachable vertices is built, mapping each of the vertices of the graph to an |
| | | 21 | | /// <see cref="HashSet{T}"/> of vertices reachable from it (including the vertex itself). |
| | | 22 | | /// <br/> |
| | | 23 | | /// - The dictionary is populated by running <see cref="IVisitStrategy.DepthFirstSearchFromVertex"/> on each |
| | | 24 | | /// vertex, via the <see cref="VisitStrategy"/> provided in the constructor. |
| | | 25 | | /// <br/> |
| | | 26 | | /// - After that, all vertices of the graph are iterated over. |
| | | 27 | | /// <br/> |
| | | 28 | | /// - A SCC array, of as many items as the number of vertices in the graph, is initialized. A current SCC counter |
| | | 29 | | /// is set to 0 and an <see cref="HashSet{T}"/> P of already processed vertices is initialized to an empty set. |
| | | 30 | | /// <br/> |
| | | 31 | | /// - For each vertex i, all reachable vertices j, except the ones in P, in R[i] are checked. |
| | | 32 | | /// <br/> |
| | | 33 | | /// - Vertices j such that R[j] contains i (including i itself, given that i always belongs to R[i]) are all |
| | | 34 | | /// assigned the same SCC. |
| | | 35 | | /// <br/> |
| | | 36 | | /// - When a vertex j is assigned a SCC, it is also added to P, so that it is not checked again in following |
| | | 37 | | /// iterations. |
| | | 38 | | /// <br/> |
| | | 39 | | /// - After all vertices reachable from i have been checked, the current SCC counter is incremented and the current |
| | | 40 | | /// iteration finishes. |
| | | 41 | | /// <br/> |
| | | 42 | | /// - Once all vertices have been processed, the resulting SCC array is returned as result. |
| | | 43 | | /// </para> |
| | | 44 | | /// <para id="complexity"> |
| | | 45 | | /// COMPLEXITY |
| | | 46 | | /// <br/> |
| | | 47 | | /// - This algorithm creates a dictionary of reachable vertices, pretty much like |
| | | 48 | | /// <see cref="Sorting.DfsOnEachVertexSinkBasedTopologicalSort"/>. |
| | | 49 | | /// <br/> |
| | | 50 | | /// - Similar considerations about the complexity of setting up the dictionary apply to this algorithm. |
| | | 51 | | /// <br/> |
| | | 52 | | /// - The main nested loops of the algorithm check each couple of a vertex and a reachable vertex from it. |
| | | 53 | | /// <br/> |
| | | 54 | | /// - The number of such couples is O(v^2), in graph where vertices are connected to O(v) other vertices. |
| | | 55 | | /// <br/> |
| | | 56 | | /// - Checking whether a vertex has already been processed, or whether it is reachable/reached from another vertex |
| | | 57 | | /// are constant-time operations. |
| | | 58 | | /// <br/> |
| | | 59 | | /// - Therefore Time Complexity is O(v * Tdfs + v^2) and Space Complexity is O(v^2 + Sdfs), where Tdfs and Sdfs |
| | | 60 | | /// are Time and Space Complexity of running a DFS from a vertex. |
| | | 61 | | /// <br/> |
| | | 62 | | /// - Time Complexity is O(v^3) in graphs where every vertex is connected to every other vertex. |
| | | 63 | | /// </para> |
| | | 64 | | /// </remarks> |
| | | 65 | | public class NaiveSccFinder : ISccFinder |
| | | 66 | | { |
| | | 67 | | /// <summary> |
| | | 68 | | /// The visitor to be used to find SCC, by running Depth First Searches on each vertex. |
| | | 69 | | /// </summary> |
| | 25 | 70 | | public IVisitStrategy VisitStrategy { get; } |
| | | 71 | | |
| | | 72 | | /// <summary> |
| | | 73 | | /// <inheritdoc cref="NaiveSccFinder"/> |
| | | 74 | | /// </summary> |
| | | 75 | | /// <param name="visitStrategy"> |
| | | 76 | | /// <inheritdoc cref="VisitStrategy" path="/summary"/> |
| | | 77 | | /// </param> |
| | | 78 | | /// <remarks> |
| | | 79 | | /// <inheritdoc cref="NaiveSccFinder"/> |
| | | 80 | | /// </remarks> |
| | 10 | 81 | | public NaiveSccFinder(IVisitStrategy visitStrategy) |
| | 10 | 82 | | { |
| | 10 | 83 | | VisitStrategy = visitStrategy; |
| | 10 | 84 | | } |
| | | 85 | | |
| | | 86 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 87 | | /// <remarks> |
| | | 88 | | /// <inheritdoc cref="NaiveSccFinder" path="/remarks"/> |
| | | 89 | | /// </remarks> |
| | | 90 | | public IList<int> Find(IGraph graph) |
| | 10 | 91 | | { |
| | 10 | 92 | | var numberOfVertices = graph.GetNumberOfVertices(); |
| | 10 | 93 | | var verticesReachableFromVertices = Enumerable |
| | 10 | 94 | | .Range(0, numberOfVertices) |
| | 25 | 95 | | .Select(vertex => VisitStrategy.DepthFirstSearchFromVertex(graph, vertex).ToHashSet()) |
| | 10 | 96 | | .ToList(); |
| | | 97 | | |
| | 10 | 98 | | var scc = new int[numberOfVertices]; |
| | 10 | 99 | | var currentScc = 0; |
| | 10 | 100 | | var processedVertices = new HashSet<int>(); |
| | 70 | 101 | | for (var i = 0; i < numberOfVertices; i++) |
| | 25 | 102 | | { |
| | 25 | 103 | | if (processedVertices.Contains(i)) |
| | 8 | 104 | | continue; |
| | | 105 | | |
| | 17 | 106 | | var verticesSameScc = verticesReachableFromVertices[i] |
| | 17 | 107 | | .Except(processedVertices) |
| | 46 | 108 | | .Where(j => verticesReachableFromVertices[j].Contains(i)); |
| | | 109 | | |
| | 101 | 110 | | foreach (var j in verticesSameScc) |
| | 25 | 111 | | { |
| | 25 | 112 | | scc[j] = currentScc; |
| | 25 | 113 | | processedVertices.Add(j); |
| | 25 | 114 | | } |
| | | 115 | | |
| | 17 | 116 | | currentScc++; |
| | 17 | 117 | | } |
| | | 118 | | |
| | 10 | 119 | | return scc; |
| | 10 | 120 | | } |
| | | 121 | | } |