Linear search algorithm for strongly connected components in directed graphs based on the analysis of the matrixs transitive closure of binary relations

Abstract

Context. The relevance of the article is due to the need for further development of simple algorithms for analyzing the structural connectivity of network objects, in reducing the computational complexity and increasing the functional capabilities of such algorithms. The linear algorithm proposed in the article can be applied: in urban and rural transport route planning systems; in solving various types of problems related to carrying out restoration work on network objects after their destruction and the loss of certain connections between the elements of such objects (power supply systems, communication systems, transport networks, etc.); in developing options for effectively destroying key objects of the enemy’s critical infrastructure; in analyzing social networks for grouping individuals into groups by interest, etc. Objective. The goal of the work is to develop a linear algorithm for searching for strongly connected components in the structure of network objects, which is resistant to changes in the structure of objects and has a polynomial computational complexity. Method. The physical object to be studied is modeled by a connected directed graph. To determine the structure of the model graph components of strong connectivity, the idea of analyzing the presence of direct and reverse transitive closures between all pairs of vertices of the model graph was applied. Since there is a route (or arc) connecting them between all pairs of vertices included in any component of strong connectivity, then in the matrix of transitive closures of binary relations of such a graph there will always be unit blocks (transitivity compactions). Individual elements of these blocks in the matrix of transitive closures are scattered in a certain way. By analyzing the matrix for the presence of identical rows and identical columns, it is possible to establish their belonging to certain unit blocks. After such analysis and grouping the corresponding rows and columns into unit blocks, it is possible to determine the number of components of strong connectivity, as well as the index (vertex) composition of each component. To construct a matrix of transitive closures of binary relations, any of the known algorithms can be used, as discussed in the article. Therefore, the linear algorithm proposed in this article is conventionally divided into two main stages: the first is the search for transitive closures of binary relations of a model directed graph; the second is the determination of the matrix of inversereachability of the graph, the determination of the matrix of mutual reachability, and the search for unit blocks in the latter by lining them up on the main diagonal of the matrix. Results. 1) A theoretical basis for analyzing the matrix of transitive closures of binary relations of a model directed graph has been developed in order to determine the quantitative and index composition of strongly connected components in its composition; 2) In terms of graph theory, the search for strongly connected components in the structure of a network object is formalized; 3) The developed algorithm was verified for its ability to determine strongly connected components in the structure of a directed graph. Conclusions. Theoretical studies and a number of experiments confirm the possibility of using the proposed algorithm in the tasks of structural analysis of network objects. Since the well-known provisions of graph theory were used in the theoretical studies, which are interpreted unambiguously in this theory, the absence of any probabilistic processes allows us to consider the developed algorithm accurate. Polynomial estimates of its computational complexity allow it to be used in real-time scale.