A Linear Algebraic Toolbox for Analyzing Strongly Connected Components

A strongly connected component of a directed graph is a group of vertices in which each vertex (source) has a path to the other vertices, and the path leads back to the source vertex. When a directed graph possesses two or more strongly connected components, injecting one or more edges makes the components merge into one component. On the other hand, by removing an inner edge, a strongly connected component can be split into multiple components. Traditionally, graph algorithms provide traversal algorithms for analyzing connected components in a graph. Though these traversal algorithms are usually efficient, taking polynomial running times (linear or quadratic), these were developed before parallel computing and linear algebraic techniques. This paper presents a linear algebraic toolbox (a set of functions developed on MATLAB) for analyzing strongly connected components. These functions are efficient, easy to understand, and simple enough to implement and extend. Also, these functions are added to the GPenSIM tool so that distributed cyber layers can be developed for the hardware of real-life industrial discrete systems.