Link to the presentation in Google Drive.
This repository contains implementations for 3 different algorithms used to identify strongly connected components in directed graphs:
- Tarjan, Robert. "Depth-first search and linear graph algorithms." SIAM journal on computing 1.2 (1972): 146-160.
- Nuutila, Esko, and Eljas Soisalon-Soininen. "On finding the strongly connected components in a directed graph." Inf. Process. Lett. 49.1 (1994): 9-14.
- 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.