Class SinkSccBasedSccFinder
An efficient implementation of ISccFinder, which runs a single DFS on the inverted graph to calculate post orders, and then uses the post orders to identify sink SCC.
Inheritance
Implements
Inherited Members
Namespace: MoreStructures.Graphs.StronglyConnectedComponents
Assembly: MoreStructures.dll
Syntax
public class SinkSccBasedSccFinder : ISccFinderRemarks
ADVANTANGES AND DISADVANTAGES
- Compared to the simple approach of NaiveSccFinder, this implementation requires more complex
operations, such as reversing the graph, generating and storing post order values.
- However, it has better runtime, approaching optimality, since it runs DFS only once, and not for every vertex
of the graph.
ALGORITHM
- The algorithm is based on the observation that the DFS on any vertex of a sink SCC is the sink SCC itself.
- So the goal at each iteration is to efficiently find a vertex which belongs to a sink SCC and run DFS on it.
- Such a vertex v can be found by running a single DFS on the reverse graph (graph with the same vertices and
reversed orientation of edges) and taking the vertex with the highest post order value.
- After having identified v, DFS is run on v to find the sink SCC S, v is in.
- All found vertices are assigned the same SCC S: a list of v items SCCs is initialized to store the result and
SCCs[i] is set to S to indicate the vertex i is in the SCC with label S.
- Then the operation is repeated, identifing the vertex v with the highest post order value, among the vertices
of the graph which haven't been assigned a SCC yet.
- When there are no vertices left, the SCCs list is returned as result.
COMPLEXITY
- Reverse() performance depends on the specific implementation of the graph.
- Building and instrumenting the required IVisitStrategy instances and storing the post order
do not depend on the side of the input.
- The output has size equal to the number of vertices in the graph.
- DFS, which is at the core of this algorithm, is run in two stages.
- In the first stage it is executed just once, on the entire graph, calling
DepthFirstSearchOfGraph(IGraph).
- In the second stage it is executed iteratively, on vertices not assigned an SCC yet, this time calling
DepthFirstSearchFromVertex(IGraph, Int32).
- Because at each iteration chosen vertex belongs to a sink SCC (due to the fact that the vertex with the
highest remaining post order is selected), each vertex of the graph is explored at most once thoughout the
entire second stage.
- Therefore, Time Complexity is O(Trvs + Tdfs) and Space Complexity is O(Srvs + Sdfs), where Trvs and Srvs are
the time and space required to reverse the provided IGraph and Tdfs and Sdfs are the time and
space required to run DFS via the IVisitStrategy provided by
VisitStrategyBuilder.
- In typical implementations of IGraph and IVisitStrategy, Tdfs >= Trvs, and Tdfs
is O(v + e), which makes Time Complexity equals to O(v * Ta + e).
- Space Complexity is generally at least O(v + e + Sa), if Reverse() just builds a proxy of
the provided graph, but can be O(v^2) for example if IGraph builds a separated transposed copy
of the adjacency matrix when reversing, and v^2 > v + e (very sparse graph).
Constructors
| Improve this Doc View SourceSinkSccBasedSccFinder(Func<IVisitStrategy>)
Declaration
public SinkSccBasedSccFinder(Func<IVisitStrategy> visitStrategyBuilder)Parameters
| Type | Name | Description |
|---|---|---|
| Func<IVisitStrategy> | visitStrategyBuilder |
Remarks
Properties
| Improve this Doc View SourceVisitStrategyBuilder
A building function able to instantiate the IVisitStrategy to be used to run Depth First Searches of the entire graph and from vertex, via DepthFirstSearchOfGraph(IGraph) and DepthFirstSearchFromVertex(IGraph, Int32) respectively.
Declaration
public Func<IVisitStrategy> VisitStrategyBuilder { get; }Property Value
| Type | Description |
|---|---|
| Func<IVisitStrategy> |
Methods
| Improve this Doc View SourceFind(IGraph)
Declaration
public IList<int> Find(IGraph graph)Parameters
| Type | Name | Description |
|---|---|---|
| IGraph | graph |
Returns
| Type | Description |
|---|---|
| IList<System.Int32> |