akshayachella/strongly-connected-components

Implementation of Tarjan, Nuutila and Pearce algorithms for strongly connected components using Boost Library.

Identifying Strongly Connected Components

Link to the presentation in Google Drive.

This repository contains implementations for 3 different algorithms used to identify strongly connected components in directed graphs:

1. Tarjan, Robert. "Depth-first search and linear graph algorithms." SIAM journal on computing 1.2 (1972): 146-160.
2. Nuutila, Esko, and Eljas Soisalon-Soininen. "On finding the strongly connected components in a directed graph." Inf. Process. Lett. 49.1 (1994): 9-14.
3. Pearce, David J. "A space-efficient algorithm for finding strongly connected components." Information Processing Letters 116.1 (2016): 47-52.

To generate graphs to test the algorithms 4 different approaches are used:

• G(n,p) : generates a graph G with n vertices and adds edges between any pair of vertices with probability p.
• G(n,m) : generates a graph G with n vertices and adds m edges to randomly sampled start and end vertices.
• In order to have a predetermined minimum number of strongly connected components in the generated graph, cycles (a cycle is an SCC) with fixed/random number of vertices are created and added to the graph (the cycles are disconnected -- downside).
• From the above generated cycles, edges are added using G(n,p) starting from a graph g.