An Extended Experimental Evaluation of SCC (Gabows vs Kosarajus) based on Adjacency List
We present the results of a study comparing three strongly connected components algorithms. The goal of this work is to extend the understandings and to help practitioners choose appropriate options. During experiment, we compared and analysed strongly connected components algorithm by using dynamic graph representation (adjacency list). Mainly we focused on i. Experimental Comparison of strongly connected components algorithms. ii. Experimental Analysis of a particular algorithm. Our experiments consist large set of random directed graph with N number of vertices V and edges E to compute graph performance using dynamic graph representation. We implemented strongly connected graph algorithms, tested and optimized using efficient data structure. The article presents detailed results based on significant performance, preferences between SCC algorithms and provides practical recommendations on their use. During experimentation, we found some interesting results particularly efficiency of Cheriyan-Mehlhorn-Gabow’s as it is more efficient in computing strongly connected components then Kosaraju’s algorithm
