Concurrent Wait-Free Graph Snapshots Using Multi-versioning

Graphs stand out as a paramount data structure for addressing real-world challenges. The binary relationships among entities or objects are vital in navigating intricate, real-time issues seen in areas like blockchain, social networks, scheduling, biological systems, and telecommunications. Unlike static graphs with immutable vertices and edges, dynamic graphs adapt to the ever-changing real-world scenarios by allowing modifications to both vertices and edges. In this context, we introduce a concurrent, lock-free dynamic graph that enables the addition, deletion, and retrieval of vertices and edges. Furthermore, we present the novel wait-free snapshot algorithm capable of both full and partial graph snapshots using multi-versioning. These snapshots pave the way for advanced graph analytics tasks, including SSSP, getpath, BFS, and more.