Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm

If you are unfamiliar with graphs, check out some of my earlier posts on them.

Resources:

1. Video explanation
2. Article explanation
3. Implementation

Takeaways:

• A strongly connected component in a directed graph is a partition or sub-graph where each vertex of the component is reachable from every other vertex in the component.
• Strongly connected components are always the maximal sub-graph, meaning none of their vertices are part of another strongly connected component.
• Finding strongly connected components is very similar to finding articulation points & bridges. Many of the solutions for finding them involve depth-first search (DFS).
• One way to find strongly connected components is using Tarjan's Algorithm.
• Tarjan's Algorithm uses DFS and a stack to find strongly connected components.
• The algorithm overview is:
  • For every unvisited vertex v in the graph, perform DFS.
  • At the start of each DFS routine, mark the current vertex v as visited, push v onto the stack, and assign v an ID and low-link value.
  • Initially, like with articulation points & bridges, the ID and low-link values of v will be the same.
  • Increment the integer value we are using as the ID/low-link seed. So the next vertex w to enter our DFS routine will get a higher value for both (compared to v).
  • For every adjacent vertex u of v, if u is unvisited, perform DFS (recursive call).
  • On exit of the recursive DFS call, or if u had already been visited, check if u is on the stack.
  • If u is on the stack, update the low-link value of v to be smallest between low-link[v] and low-link[u]
    • low-link represents the earliest ancestor of a vertex (a lower value means the vertex entered DFS earlier). In other words, low-link is the ID of the earliest vertex y vertex v is connected to.
  • After exploring all adjacent vertices of v check if the ID of v is the same as it's low-link value
  • If they are the same, then v is the root of a strongly connected component.
  • If they are the same, pop all vertices off the stack up to and including v. All of these vertices represent a single strongly connected component
  • Complete the above steps for the entire graph, and all strongly connected components will be discovered.
• Time complexity of Tarjan's Algorithm is O(v + e) - where v is the number of vertices, and e the number of edges, in a graph.
• Space is O(v)

Below are implementations for finding strongly connected components in undirected adjacency list & adjacency matrix representations of graphs:

	using System;
	using System.Collections.Generic;
	public class Program
	{
	public class Edge
	{
	public Edge(Vertex source, Vertex destination)
	{
	Source = source;
	Destination = destination;
	}
	public Vertex Source { get; set; }
	public Vertex Destination { get; set; }
	}
	public class Vertex
	{
	public Vertex(int key)
	{
	Key = key;
	}
	public int Key { get; set; }
	}
	public class Graph
	{
	private Dictionary<Vertex, List<Edge>> adjList;
	public Graph()
	{
	adjList = new Dictionary<Vertex, List<Edge>>();
	}
	public Dictionary<Vertex, List<Edge>> AdjList
	{
	get
	{
	return adjList;
	}
	}
	public void AddEdge(Vertex source, Vertex destination)
	{
	if (adjList.ContainsKey(source))
	{
	adjList[source].Add(new Edge(source, destination));
	}
	else
	{
	adjList.Add(source,
	new List<Edge> { new Edge(source, destination) });
	}
	}
	}
	public static HashSet<List<Vertex>> StronglyConnectedComponents(Graph graph)
	{
	var visited = new HashSet<Vertex>();
	var isOnStack = new HashSet<Vertex>();
	var scc = new HashSet<List<Vertex>>();
	var ids = new Dictionary<Vertex, int>();
	var lowLinkValues = new Dictionary<Vertex, int>();
	var stack = new Stack<Vertex>();
	var id = 0;
	foreach (var vertex in graph.AdjList.Keys)
	{
	if (visited.Contains(vertex))
	{
	continue;
	}
	Dfs(vertex,
	stack,
	id,
	scc,
	ids,
	lowLinkValues,
	visited,
	isOnStack,
	graph.AdjList);
	}
	return scc;
	}
	// Yes, lots of parameters is bad - or at least annoying to code and unwieldy to look at.
	// Probably look cleaner/more readable moving many of these to class fields.
	// _However_ when learning something new, and reading other peoples implementations of algorithms
	// I like to be able to _easily_ identify where a variable is coming from/defined
	// So all parameters it is...
	private static void Dfs(
	Vertex vertex,
	Stack<Vertex> stack,
	int id,
	HashSet<List<Vertex>> scc,
	Dictionary<Vertex, int> ids,
	Dictionary<Vertex, int> lowLinkValues,
	HashSet<Vertex> visited,
	HashSet<Vertex> isOnStack,
	Dictionary<Vertex, List<Edge>> adjList)
	{
	stack.Push(vertex);
	isOnStack.Add(vertex);
	visited.Add(vertex);
	ids.Add(vertex, id);
	lowLinkValues.Add(vertex, id);
	id++;
	foreach (var edge in adjList[vertex])
	{
	var adj = edge.Destination;
	if (!visited.Contains(adj))
	{
	Dfs(adj,
	stack,
	id,
	scc,
	ids,
	lowLinkValues,
	visited,
	isOnStack,
	adjList);
	}
	if (isOnStack.Contains(adj))
	{
	lowLinkValues[vertex] = Math.Min(
	lowLinkValues[vertex],
	lowLinkValues[adj]);
	}
	}
	if (ids[vertex] == lowLinkValues[vertex])
	{
	var newScc = new List<Vertex>();
	while (stack.Count > 0)
	{
	var v = stack.Pop();
	isOnStack.Remove(v);
	lowLinkValues[v] = ids[vertex];
	newScc.Add(v);
	if (v.Equals(vertex))
	{
	break;
	}
	}
	scc.Add(newScc);
	}
	}
	public class Graph2
	{
	private int[,] adjMatrix;
	public Graph2(int vertices)
	{
	adjMatrix = new int[vertices, vertices];
	}
	public int[,] AdjMatrix
	{
	get
	{
	return adjMatrix;
	}
	}
	public void AddEdge(int source, int destination)
	{
	adjMatrix[source, destination] = 1;
	}
	}
	public static HashSet<List<int>> StronglyConnectedComponents(Graph2 graph)
	{
	var visited = new HashSet<int>();
	var scc = new HashSet<List<int>>();
	var stack = new Stack<int>();
	var isOnStack = new HashSet<int>();
	var ids = new Dictionary<int, int>();
	var lowLinkValues = new Dictionary<int, int>();
	var id = 0;
	for (int i = 0; i < graph.AdjMatrix.GetLength(0); i++)
	{
	if (visited.Contains(i))
	{
	continue;
	}
	Dfs(i,
	stack,
	isOnStack,
	id,
	scc,
	ids,
	lowLinkValues,
	visited,
	graph.AdjMatrix);
	}
	return scc;
	}
	private static void Dfs(int vertex,
	Stack<int> stack,
	HashSet<int> isOnStack,
	int id,
	HashSet<List<int>> scc,
	Dictionary<int, int> ids,
	Dictionary<int, int> lowLinkValues,
	HashSet<int> visited,
	int[,] adjMatrix)
	{
	stack.Push(vertex);
	visited.Add(vertex);
	isOnStack.Add(vertex);
	ids.Add(vertex, id);
	lowLinkValues.Add(vertex, id);
	id++;
	for (int i = 0; i < adjMatrix.GetLength(0); i++)
	{
	if (adjMatrix[vertex, i] < 1)
	{
	continue;
	}
	if (!visited.Contains(i))
	{
	Dfs(i,
	stack,
	isOnStack,
	id,
	scc,
	ids,
	lowLinkValues,
	visited,
	adjMatrix);
	}
	if (isOnStack.Contains(i))
	{
	lowLinkValues[vertex] = Math.Min(lowLinkValues[vertex], lowLinkValues[i]);
	}
	}
	if (ids[vertex] == lowLinkValues[vertex])
	{
	var newScc = new List<int>();
	while (stack.Count > 0)
	{
	var v = stack.Pop();
	isOnStack.Remove(v);
	newScc.Add(v);
	lowLinkValues[v] = ids[vertex];
	if (v == vertex)
	{
	break;
	}
	}
	scc.Add(newScc);
	}
	}
	public static void Main()
	{
	// Adjacency List:
	var directedAL = new Graph();
	var zero = new Vertex(0);
	var one = new Vertex(1);
	var two = new Vertex(2);
	var three = new Vertex(3);
	var four = new Vertex(4);
	var five = new Vertex(5);
	var six = new Vertex(6);
	var seven = new Vertex(7);
	var eight = new Vertex(8);
	var nine = new Vertex(9);
	var ten = new Vertex(10);
	directedAL.AddEdge(six, two);
	directedAL.AddEdge(three, four);
	directedAL.AddEdge(six, four);
	directedAL.AddEdge(two, zero);
	directedAL.AddEdge(zero, one);
	directedAL.AddEdge(four, five);
	directedAL.AddEdge(five, six);
	directedAL.AddEdge(three, seven);
	directedAL.AddEdge(seven, five);
	directedAL.AddEdge(one, two);
	directedAL.AddEdge(seven, three);
	directedAL.AddEdge(five, zero);
	var scc1 = StronglyConnectedComponents(directedAL);
	// Adjacency Matrix:
	var directedAM = new Graph2(11);
	directedAM.AddEdge(6, 2);
	directedAM.AddEdge(3, 4);
	directedAM.AddEdge(6, 4);
	directedAM.AddEdge(2, 0);
	directedAM.AddEdge(0, 1);
	directedAM.AddEdge(4, 5);
	directedAM.AddEdge(5, 6);
	directedAM.AddEdge(3, 7);
	directedAM.AddEdge(7, 5);
	directedAM.AddEdge(1, 2);
	directedAM.AddEdge(7, 3);
	directedAM.AddEdge(5, 0);
	var scc2 = StronglyConnectedComponents(directedAM);
	}
	}

view raw TarjanStronglyConnectedComponents.cs hosted with ❤ by GitHub

As always, if you found any errors in this post please let me know!