Data Structure for Faster Graph Processing
Mikhail Chernoskutov · 2021 Ural Symposium on Biomedical Engineering, Radioelectronics and Information Technology (USBEREIT) · 2021
The performance of graph algorithms can vary greatly depending on the data structure used to store the graph. This is happen due to the fact that the graph is an inherently irregular data structure, which makes it hard to deal with. In particular, such operations like checking nodes connectivity and adding or deleting nodes and edges, in some cases, can be computationally expensive and require iterating over most of the structure elements in the graph. This paper proposes a new data structure that allows many of such operations to be performed with approximately linear computational complexity. The new data structure is based on hash maps and linked list which makes it operates better when need to arbitrary navigates through the graph and modify it. Performance comparison of max flow algorithm and construction of random graph when using the proposed data structure, as well as using general data structures such as compressed sparse rows and adjacency matrix is presented. The new data structure in both cases shows better performance over its counterparts.