This project implements a parallel algorithm to update single-source shortest paths (SSSP) in large-scale dynamic graphs, based on the research paper:
"A Parallel Algorithm Template for Updating Single-Source Shortest Paths in Large-Scale Dynamic Networks"
Authors: Khanda, Srinivasan, Bhowmick, Norris, Das (IEEE TPDS, 2022)
To design and implement a scalable parallel algorithm using OpenMP that efficiently updates SSSP trees in dynamic graphs where edge insertions and deletions occur — without recomputing everything from scratch.
- C++ – Language used for implementation
- OpenMP – For shared-memory, intra-node parallelism
- Dynamic Scheduling – For workload balancing during updates
- CSR Format – For graph representation
- Real-world Datasets – From Network Repository and synthetic R-MAT graphs
- GitHub – For collaboration and progress tracking
- Graph Input: Read static graph in CSR or adjacency list format
- Edge Updates: Load batch of inserted/deleted edges
- Subgraph Detection: Mark affected vertices
- Parallel Updates: Relax distances using OpenMP threads
- Asynchronous Rounds: Optionally control level of synchronization
- Final Output: Updated SSSP tree and performance stats
- Dynamic Graphs: Graphs where edges are frequently inserted or deleted
- SSSP Tree Representation: Uses a rooted tree storing distance and parent per vertex
- Affected Subgraph Identification: Only vertices impacted by changes are processed
- Iterative Updates Without Locks: Convergence via repeated distance checks instead of synchronization
- Parallelism:
- Intra-node using OpenMP
- Dynamic scheduling for load balancing
- Avoid Cycle Formation: During insertions, maintain acyclic SSSP tree
- Asynchronous Updates: Reduces synchronization cost by processing neighbors multiple levels deep
- Batch Processing: Handles massive edge changes in manageable chunks for performance
- Could be used for distributing graph partitions (using METIS) across different nodes.
- Each node can independently update its subgraph’s SSSP tree.
- After local updates, MPI_Gather or MPI_Allreduce could be used to sync global distances.
- Already used in shared-memory version (OpenMP).
- Enables parallel processing of:
- Edge deletions/insertions
- Affected vertex updates
Dynamic scheduling in OpenMP helps in load balancing during updates of uneven subtrees.
- Can pre-process large graphs to partition them into smaller subgraphs.
- Each subgraph can be assigned to a thread (OpenMP) or node (MPI).
- Reduces cross-node communication and optimizes memory locality.
- Hammad Shabbir
- Haider Zia
- Muhammad Iqrash Qureshi