Strongly Connected Components

A strongly connected component of a graph is a set of vertices such that for each pair u,v of vertices in the component, there exists a path from u to v and v to u.

This algorithm sorts the vertices in the different strongly connected components of the graph. It is implemented by the StronglyConnectedComponentsAlgorithm which uses the DepthFirstSearchVertexAlgorithm internally. Again, AlgorithmExtensions contains extension methods that hides these implementation details for you.

The concept of strong connectivity is very important in many algorithms because it means there is always “a way back”. For example, one expects that the directed graph that represent the different states of a dialog window is strongly connected, i.e. the user can always go back or undo.

This sample shows how to compute and display the component information from a directed graph:
IVertexListGraph<Vertex,Edge> g=…;
IDictionary<Vertex,int> components=new Dictionary<Vertex,int>();

int componentCount = g.StronglyConnectedComponents(components);
if (componentCount!=0)
{
    Console.WriteLine(“Warning the graph is not strongly connected”);
    foreach(KeyValuePair<Vertex,int> kv in components)
        Console.WriteLine(“{0}-{1}”,kv.Value,kv.Key);
}

Last edited Mar 30, 2009 at 7:05 AM by pelikhan, version 3

Comments

KvL Nov 14, 2012 at 10:54 AM 
The example is wrong.

IDictionary<string, int> components = new Dictionary<string, int>(); //Key: vertex, Value: subgraph index, 0-based.
int componentCount = graph.StronglyConnectedComponents<string, Edge<string>>(out components);
if (componentCount != 1) // this graph has multiple components
{
Console.WriteLine("Graph is not strongly connected");
Console.WriteLine("Graph contains {0} strongly connected components", componentCount);
foreach (var kv in components)
{
Console.WriteLine("Vertex {0} is connected to subgraph {1}", kv.Key, kv.Value);
}
}

seanosr Mar 17, 2010 at 10:07 PM 
To update and add to the documentation:

IDictionary<string, int> components = new Dictionary<string, int>();
int componentCount = graph.StronglyConnectedComponents<string, Edge<string>>(out components);
if (componentCount != 0)
{
Console.WriteLine("Graph is not strongly connected");
Console.WriteLine("Graph contains {0} strongly connected components", componentCount);
foreach (var kv in components)
{

Console.WriteLine("Vertex {0} is connected to {1} other strongly connected components", kv.Key, kv.Value);
}
}