Graph

Description Three different variants of Connected Component (CC) algorithms are implemented, and the comparisons are provided as follows: Algorithm Time Complexity Parallelism Techniques DFS $(O(V + E))$ Poor Recursive Traversal Union-Find $(O(V + E \alpha(V)))$ Poor Path Compression, Union by Rank Shiloach-Vishkin $(O(\log^* V))$ Highly Parallel Pointer Jumping Here, $( \log^* )$ is the iterated logarithm, which is extremely slow-growing, making the algorithm very fast. $( \alpha(V) )$ is the inverse Ackermann function, practically a constant for all feasible input sizes....

Two variants of Single-Source Shortest Path (SSSP) have been implemented as follows. Bellman-Ford is the one that is widely implemented in parallel graph frameworks. This is because the use of a heap in Dijkstra’s algorithm can limit the parallelism of the code. Criteria Dijkstra’s Algorithm Bellman-Ford Algorithm Type Greedy Dynamic Programming Usage Positive weights Negative weights OK Time Complexity O((V + E) * log(V)) O(V * E) Negative Cycles No Yes (Detectable) Data Structures Priority Queue None (Arrays) Initialization Start node: 0, rest ∞ Start node: 0, rest ∞ Relaxation Decrease Key Relaxation BellmanFord BellmanFord: Perform numVertices - 1 iterations of graph traversal to find the shortest path an additional iteration checks if negative cycles exist $O(|V| * |E|)$ time complexity Code #include <iostream> #include <queue> #include <vector> std::vector<int> bellmanFord(const int root, const std::vector<int>& rowPtr, const std::vector<int>& colIdx, const std::vector<float>& weight) { const auto numVertices = rowPtr....

Iterative BFS Despite its apparent simplicity, this approach relies heavily on the utilization of various STL containers. std::unordered_map records the parent of each node std::unordered_set checks if a node has been visited std::queue allows the nodes be accessed in the width-first flow; using std::stack for depth-first flow std::stack reverses the parents, so the path can be printed in root-to-target order. #include <iostream> #include <vector> #include <unordered_map> #include <unordered_set> #include <queue> #include <stack> std::stack<int> BFS(const int root, const int target, const std::vector<int>& rowPtr, const std::vector<int>& colIdx) { std::unordered_map<int, int> parent; std::unordered_set<int> visited; std::queue<int> nodeQue; // std::stack<int> nodeStk for DFS std::stack<int> path; bool hasFound = false; nodeQue....

Considering myself a researcher in graph algorithms, I’ve come to the surprising realization that my grasp of these algorithms is not as solid as I thought. Hence, this blog series aims to document my exploration of various graph algorithms I’ve encountered thus far, regardless of their complexity. The algorithms are selected from the parallel graph frameworks GAP and GBBS, focusing on their single-threaded versions to assess their complexity. Breadth-First Search (BFS) Single-Source Shortest Paths (SSSP) Connected Components (CC) Betweenness Centrality (BC) Triangle Counting (TC) Minimum Spanning Tree (MST) Strongly Connected Components (SCC) SCAN Clustering (SCAN) Low Diameter Decomposition (LDD) Biconnected-Components (BC) Graph Coloring (COLOR) Maximal Matching (MM) Maximal Independent Set (MIS)