Connected Components
Application Description
A connected component of an undirected graph is a subgraph in which there is a path between any two nodes. A node with no edges is itself a connected component. (Wikipedia)
Algorithms
Algorithms for connected components are based on either unionfind or labelpropagation.
 The UnionFind algorithm is based on pointer jumping. Each node has a pointer to its representative, initially set to itself. If two nodes a and b are connected by an edge e, then the union operation updates representatives of a and b to be the same. The find operation updates the representative of a node to be one of its ancestors in the representative relation.
 In Label Propagation, each node is given a unique label initially, and then labels are propagated through the graph until all the nodes in the same component have the same label.
An optimization for unionfind is called Afforest, an algorithm with subgraph sampling, where unionfind is first performed on a few samples of neighborhoods of all vertices (Vertex Neighbor Sampling) and then on the rest of neighborhoods of only those vertices not belonging to the largest component approximated by another sampling process (Largest Component Skipping).
M. Sutton, T. BenNun and A. Barak, "Optimizing Parallel Graph Connectivity Computation via Subgraph Sampling," 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS), Vancouver, BC, 2018, pp. 1221, doi: 10.1109/IPDPS.2018.00012.
The Connected Components application implements 7 algorithms: 19 are variants of unionfind, and 10 is label propagation.
 Serial: Serial pointerjumping implementation.
 Synchronous: Bulk synchronous datadriven implementation. Alternatively execute on two worklists.
 Async: asynchronous topologydriven implementation. Work unit is a node.
 BlockedAsync: asynchronous topologydriven implementation with NUMAaware optimization. Work unit is a node.
 EdgeAsync: asynchronous topologydriven. Work unit is an edge.
 EdgetiledAsync (default): asynchronous topologydriven. Work unit is an edge tile.

Afforest: datadriven implementation with Afforest subgraph sampling algorithm. Work unit is a node.
 EdgeAfforest: datadriven implementation with subgraph sampling. Work unit is an edge.
 EdgetiledAfforest: datadriven implementation with subgraph sampling. Work unit is an edge tile.
 LabelProp: Label propagation implementation.
Note that Connected Components only accepts a symmetric input graph.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  Graph g = /*input graph*/ foreach (Node src : g) { foreach (Node dst : src.getNeighbors()) { if(src.id > dst.id) continue; while(true) { src.findAndCompress(); //update representative to be one of its ancestors dst.findAndCompress(); if(src.representative == dst.representative) break; Union(src, dst); //update representative to be the same } } } 
Figure 1: Pseudocode for Pointer Jumping(16) algorithm.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17  Graph g = /*input graph*/ const int PARAM_VNS = /*number of sampled edges (per vertex) for Vertex Neighbors Sampling*/ const int PARAM_LCS = /*number of sampled vertices for Largest Component Skipping*/ foreach (Node src : g) { foreach (Node dst : src.getSampledNeighbors(PARAM_VNS)) { /*pointer jumping operations as demostrated in Figure 1*/ } } Node r = sampLgstComp(g, PARAM_LCS); //approximate the largest component via PARAM_LCS times sampling and return the representative of it foreach (Node src : g) { if (r == src.representative) break; //skipping foreach (Node dst : src.getUnsampledNeighbors()) { /*pointer jumping operations as demostrated in Figure 1*/ } } 
Figure 2: Pseudocode for Pointer Jumping with subgraph sampling(79) algorithm.
1 2 3 4 5 6 7 8 9 10 11 12 13 14  Graph g = /*input graph*/ do { updated = false; foreach (Node src : g) { if(src.old_label > src.curr_label){ src.old_label = src.curr_label; updated = true; foreach (Node dst : src.getNeighbors()){ atomicMin(dst.curr_label, src.curr_label); //atomicMin(A, B): atomic write B's value to A if A < B } } } } while(updated) 
Figure 3: Pseudocode for Label Propagation(10) algorithm.
Data Structures
There are two key data structures used in connected components:
 Graph
 An undirected graph.
 UnionFind
 A disjointset data structure used to maintain components of graph.
Performance
Figure 4 and Figure 5 show the execution time in seconds and selfrelative speedup (speedup with respect to the single thread performance), respectively, of this algorithm running on a graph generated using rmat model with 2^{25} nodes and 2^{29} edges.
Machine Description
Performance numbers are collected on a 4 package (14 cores per package) Intel(R) Xeon(R) Gold 5120 CPU machine at 2.20GHz from 1 thread to 56 threads in increments of 7 threads. The machine has 192GB of RAM. The operating system is CentOS Linux release 7.5.1804. All runs of the Galois benchmarks used gcc/g++ 7.2 to compile.