Class NaiveSccFinder

A simple implementation of ISccFinder, which builds a "reachability dictionary", by running a DFS on each vertex of the graph separately.

Inheritance
System.Object
NaiveSccFinder
Implements
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.Graphs.StronglyConnectedComponents
Assembly: MoreStructures.dll
Syntax
public class NaiveSccFinder : ISccFinder
Remarks

ADVANTAGES AND DISADVANTAGES
- This is the easiest, most straighforward implementation of ISccFinder.
- It has, however, a cubic runtime for dense graphs, which is less than ideal.

ALGORITHM
- First a dictionary R of reachable vertices is built, mapping each of the vertices of the graph to an of vertices reachable from it (including the vertex itself).
- The dictionary is populated by running DepthFirstSearchFromVertex(IGraph, Int32) on each vertex, via the VisitStrategy provided in the constructor.
- After that, all vertices of the graph are iterated over.
- A SCC array, of as many items as the number of vertices in the graph, is initialized. A current SCC counter is set to 0 and an P of already processed vertices is initialized to an empty set.
- For each vertex i, all reachable vertices j, except the ones in P, in R[i] are checked.
- Vertices j such that R[j] contains i (including i itself, given that i always belongs to R[i]) are all assigned the same SCC.
- When a vertex j is assigned a SCC, it is also added to P, so that it is not checked again in following iterations.
- After all vertices reachable from i have been checked, the current SCC counter is incremented and the current iteration finishes.
- Once all vertices have been processed, the resulting SCC array is returned as result.

COMPLEXITY
- This algorithm creates a dictionary of reachable vertices, pretty much like DfsOnEachVertexSinkBasedTopologicalSort.
- Similar considerations about the complexity of setting up the dictionary apply to this algorithm.
- The main nested loops of the algorithm check each couple of a vertex and a reachable vertex from it.
- The number of such couples is O(v^2), in graph where vertices are connected to O(v) other vertices.
- Checking whether a vertex has already been processed, or whether it is reachable/reached from another vertex are constant-time operations.
- Therefore Time Complexity is O(v * Tdfs + v^2) and Space Complexity is O(v^2 + Sdfs), where Tdfs and Sdfs are Time and Space Complexity of running a DFS from a vertex.
- Time Complexity is O(v^3) in graphs where every vertex is connected to every other vertex.

Constructors

| Improve this Doc View Source

NaiveSccFinder(IVisitStrategy)

Declaration
public NaiveSccFinder(IVisitStrategy visitStrategy)
Parameters
Type Name Description
IVisitStrategy visitStrategy

Remarks

Properties

| Improve this Doc View Source

VisitStrategy

The visitor to be used to find SCC, by running Depth First Searches on each vertex.

Declaration
public IVisitStrategy VisitStrategy { get; }
Property Value
Type Description
IVisitStrategy

Methods

| Improve this Doc View Source

Find(IGraph)

Declaration
public IList<int> Find(IGraph graph)
Parameters
Type Name Description
IGraph graph
Returns
Type Description
IList<System.Int32>
Remarks

Implements

Extension Methods