A Comparative Study of Algorithm for Computing Strongly Connected Components
D. Frank Hsu, Xiaojie Lan, Gabriel Miller, David Baird · 2017
Software systems or programs and their properties are often represented by directed or undirected graphs. However, for these systems to be dependable and trusted, special directed acyclic graphs (DAG) without any directed cycle (or strongly connected component) are needed. Several algorithms to compute strongly connected components (SCC) (directed cycles) of a directed graph have been proposed. Although most of these algorithms have similar overall time complexity of O(n+q), for n nodes and q arcs, they vary in algorithm implementations and data structures. Hence each of these algorithms is used better in some specific systems and domain applications. In this paper, we conducted a comparative study of three SCC algorithms: Tarjan, Kosaraju and Sharir, and Gabow with respect to time, memory, and data structure across different classes of graphs: sparse, dense, and complete digraphs implemented in C++ and Java. Results of our study will be useful for practical use cases in software system design and development, software verification, and compiler design as well as other design and implementation of large and heterogeneous relational datasets.