Description Both std::set and std::map are underpinned by red-black trees (RBT). RBTs are self-balancing binary trees, albeit not perfectly balanced. In this structure, it’s ensured that the values (for std::set) or keys (for std::map) adhere to the following condition: node→left < node < node→right. Consequently, the RBT are considered ordered, so std::set and std::map are called ordered containers. RBT are characterized as follows: Property A node is either red or black....
count how many triangles can be formed inside the graph undirected graph, and each triangle would be counted for three times, once per node. $O(n^3)$ #include <iostream> #include <vector> // Reference: https://github.com/georgegito/vertexwise-triangle-counting/blob/master/src/v3/v3_seq.cpp // allow for parallelism auto bfs_tc(const std::vector<int>& rowPtr, const std::vector<int>& colIdx) { int numTriangles = 0; const auto numVertices = rowPtr.size() - 1; // check if two nodes have an edge between them with binary search (require sorted colIdx) auto intersect = [&](int first, int second) -> bool { // std::find is O(N), assuming the iterator is a forward iterator // auto first_begin = colIdx....
The betweenness centrality for each vertex is the number of these shortest paths that pass through the vertex. perform BFS (or SSSP if weighted graphs) for each vertex keep a stack of path for backtracking, i.e., traversing the graph in reverse BFS order #include <iostream> #include <queue> #include <stack> #include <vector> auto brandes(const std::vector<int>& rowPtr, const std::vector<int>& colIdx) { const auto numVertices = rowPtr.size() - 1; std::vector<float> betweenness(numVertices, 0.0f); //For each vertex s, perform a BFS to establish levels and predecessors //!...
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....
Description STL indeed offers std::list and std::forward_list, which are essentially double-linked list and single-linked list, respectively. std::list provides operations like push_back/front, pop_back/front with a time complexity of O(1), and supports bidirectional iterators. On the other hand, std::forward_list only allows fronting operations with O(1) and insert/erase_after for backing operations, which have a time complexity of O(n); also, it only supports forward iterators. A valuable feature of lists is that they prohibit iterator invalidation compared to some other data structures....
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....
Description std::deque extends the interfaces of std::vector with push_front, pop_front, etc., such that elements can be inserted or removed at the end or beginning at constant time. I’ve hardly ever incorporated std::deque in my own coding projects, and it’s a rarity in other people’s work as well. Code std::deque is essentially a sequence of individually allocated fixed-size arrays. The real challenge lies in the bookkeeping. Four variables are relied on to keep track of data:...
Array is allocated in stack memory Vector is allocated in heap memory. Its capacity is “pre-allocated”. #include <iostream> template<typename T> class Vector { private: T* data_; size_t size_; size_t capacity_; public: Vector(): data_(nullptr), size_(0), capacity_(0) {} Vector(size_t n_): size_(n_), capacity_(n_) { data_ = new T[n_]; } ~Vector() { delete [] data_; }; T& operator[] (size_t index) { return data_[index]; } const T& operator[] (size_t index) const { return data_[index]; } size_t size() const { return size_; } void push_back(const T& value) { if(size_ == capacity_) { capacity_ = size_ == 0?...
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)