Skip to content

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

Notifications You must be signed in to change notification settings

edervishaj/strongly-connected-components

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

35 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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.

Releases

No releases published

Packages

No packages published