Study, implementation and comparison of different algorithms for finding the Strongly Connected Components of a directed graph.
This project was developed by Asimina Mertzani and Constantinos Karouzos as part of the Politecnico di Milano Advanced Algorithms and Parallel Programming course, taught by Prof. Fabrizio Ferrandi in the spring semester of 2018.
During the project, the relevant algorithms were theoretically studied by the following papers:
-
Tarjan, R. E., "Depth-first search and linear graph algorithms", SIAM Journal on Computing, 1 (2): 146-160, (1972).
-
Nuutila, Esko. "On Finding the Strongly Connected Components in a Directed Graph". Information Processing Letters. pp. 9-14, (1993).
-
Pearce, David. "A Space Efficient Algorithm for Detecting Strongly Connected Components. Information Processing Letters. pp. 47-52, (2015).
The code was implemented by using Boost Graph Library for C++.