< Summary

Information
Class: MoreStructures.Graphs.StronglyConnectedComponents.SinkSccBasedSccFinder
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/Graphs/StronglyConnectedComponents/SinkSccBasedSccFinder.cs
Line coverage
100%
Covered lines: 29
Uncovered lines: 0
Coverable lines: 29
Total lines: 134
Line coverage: 100%
Branch coverage
100%
Covered branches: 8
Total branches: 8
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
get_VisitStrategyBuilder()100%1100%
.ctor(...)100%1100%
Find(...)100%8100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/Graphs/StronglyConnectedComponents/SinkSccBasedSccFinder.cs

#LineLine coverage
 1using MoreStructures.Graphs.Visitor;
 2
 3namespace MoreStructures.Graphs.StronglyConnectedComponents;
 4
 5/// <summary>
 6/// An efficient implementation of <see cref="ISccFinder"/>, which runs a single DFS on the inverted graph to calculate
 7/// post orders, and then uses the post orders to identify sink SCC.
 8/// </summary>
 9/// <remarks>
 10///     <para id="advantages">
 11///     ADVANTANGES AND DISADVANTAGES
 12///     <br/>
 13///     - Compared to the simple approach of <see cref="NaiveSccFinder"/>, this implementation requires more complex
 14///       operations, such as reversing the graph, generating and storing post order values.
 15///       <br/>
 16///     - However, it has better runtime, approaching optimality, since it runs DFS only once, and not for every vertex
 17///       of the graph.
 18///     </para>
 19///     <para id="algorithm">
 20///     ALGORITHM
 21///     <br/>
 22///     - The algorithm is based on the observation that the DFS on any vertex of a sink SCC is the sink SCC itself.
 23///       <br/>
 24///     - So the goal at each iteration is to efficiently find a vertex which belongs to a sink SCC and run DFS on it.
 25///       <br/>
 26///     - Such a vertex v can be found by running a single DFS on the reverse graph (graph with the same vertices and
 27///       reversed orientation of edges) and taking the vertex with the highest post order value.
 28///       <br/>
 29///     - After having identified v, DFS is run on v to find the sink SCC S, v is in.
 30///       <br/>
 31///     - All found vertices are assigned the same SCC S: a list of v items SCCs is initialized to store the result and
 32///       SCCs[i] is set to S to indicate the vertex i is in the SCC with label S.
 33///       <br/>
 34///     - Then the operation is repeated, identifing the vertex v with the highest post order value, among the vertices
 35///       of the graph which haven't been assigned a SCC yet.
 36///       <br/>
 37///     - When there are no vertices left, the SCCs list is returned as result.
 38///     </para>
 39///     <para id="complexity">
 40///     COMPLEXITY
 41///     <br/>
 42///     - <see cref="IGraph.Reverse"/> performance depends on the specific implementation of the graph.
 43///       <br/>
 44///     - Building and instrumenting the required <see cref="IVisitStrategy"/> instances and storing the post order
 45///       do not depend on the side of the input.
 46///       <br/>
 47///     - The output has size equal to the number of vertices in the graph.
 48///       <br/>
 49///     - DFS, which is at the core of this algorithm, is run in two stages.
 50///       <br/>
 51///     - In the first stage it is executed just once, on the entire graph, calling
 52///       <see cref="IVisitStrategy.DepthFirstSearchOfGraph"/>.
 53///       <br/>
 54///     - In the second stage it is executed iteratively, on vertices not assigned an SCC yet, this time calling
 55///       <see cref="IVisitStrategy.DepthFirstSearchFromVertex"/>.
 56///       <br/>
 57///     - Because at each iteration chosen vertex belongs to a sink SCC (due to the fact that the vertex with the
 58///       highest remaining post order is selected), each vertex of the graph is explored at most once thoughout the
 59///       entire second stage.
 60///       <br/>
 61///     - Therefore, Time Complexity is O(Trvs + Tdfs) and Space Complexity is O(Srvs + Sdfs), where Trvs and Srvs are
 62///       the time and space required to reverse the provided <see cref="IGraph"/> and Tdfs and Sdfs are the time and
 63///       space required to run DFS via the <see cref="IVisitStrategy"/> provided by
 64///       <see cref="VisitStrategyBuilder"/>.
 65///       <br/>
 66///     - In typical implementations of <see cref="IGraph"/> and <see cref="IVisitStrategy"/>, Tdfs >= Trvs, and Tdfs
 67///       is O(v + e), which makes Time Complexity equals to O(v * Ta + e).
 68///       <br/>
 69///     - Space Complexity is generally at least O(v + e + Sa), if <see cref="IGraph.Reverse"/> just builds a proxy of
 70///       the provided graph, but can be O(v^2) for example if <see cref="IGraph"/> builds a separated transposed copy
 71///       of the adjacency matrix when reversing, and v^2 > v + e (very sparse graph).
 72///     </para>
 73/// </remarks>
 74public class SinkSccBasedSccFinder : ISccFinder
 75{
 76    /// <summary>
 77    /// A building function able to instantiate the <see cref="IVisitStrategy"/> to be used to run Depth First Searches
 78    /// of the entire graph and from vertex, via <see cref="IVisitStrategy.DepthFirstSearchOfGraph(IGraph)"/> and
 79    /// <see cref="IVisitStrategy.DepthFirstSearchFromVertex(IGraph, int)"/> respectively.
 80    /// </summary>
 2081    public Func<IVisitStrategy> VisitStrategyBuilder { get; }
 82
 83    /// <summary>
 84    ///     <inheritdoc cref="SinkSccBasedSccFinder"/>
 85    /// </summary>
 86    /// <param name="visitStrategyBuilder">
 87    ///     <inheritdoc cref="VisitStrategyBuilder" path="/summary"/>
 88    /// </param>
 89    /// <remarks>
 90    ///     <inheritdoc cref="SinkSccBasedSccFinder"/>
 91    /// </remarks>
 1092    public SinkSccBasedSccFinder(Func<IVisitStrategy> visitStrategyBuilder)
 1093    {
 1094        VisitStrategyBuilder = visitStrategyBuilder;
 1095    }
 96
 97    /// <inheritdoc path="//*[not(self::remarks)]"/>
 98    /// <remarks>
 99    ///     <inheritdoc cref="SinkSccBasedSccFinder"/>
 100    /// </remarks>
 101    public IList<int> Find(IGraph graph)
 10102    {
 10103        var reverseGraph = graph.Reverse();
 10104        var reverseVisitStrategy = VisitStrategyBuilder();
 105
 10106        var numberOfVertices = graph.GetNumberOfVertices();
 10107        var verticesInPostOrder = new int[numberOfVertices];
 10108        var postOrderValue = 0;
 35109        reverseVisitStrategy.VisitedVertex += (o, e) => verticesInPostOrder[postOrderValue++] = e.Vertex;
 10110        MoreLinq.MoreEnumerable.Consume(reverseVisitStrategy.DepthFirstSearchOfGraph(reverseGraph));
 111
 10112        var directVisitStrategy = VisitStrategyBuilder();
 113
 10114        var scc = new int[numberOfVertices];
 70115        for (int i = 0; i < numberOfVertices; i++)
 25116            scc[i] = -1;
 117
 10118        var currentScc = 0;
 70119        for (var i = numberOfVertices - 1; i >= 0; i--)
 25120        {
 25121            var vertex = verticesInPostOrder[i];
 122
 25123            if (scc[vertex] >= 0)
 8124                continue;
 125
 109126            foreach (var reachableVertex in directVisitStrategy.DepthFirstSearchFromVertex(graph, vertex))
 29127                scc[reachableVertex] = currentScc;
 128
 17129            currentScc++;
 17130        }
 131
 10132        return scc;
 10133    }
 134}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_VisitStrategyBuilder()
.ctor(System.Func`1<MoreStructures.Graphs.Visitor.IVisitStrategy>)
Find(MoreStructures.Graphs.IGraph)