Parallel Connected Components

This tutorial explains how to compute connected components in a graph using parallel_connected_components

Overview

Connected components identify groups of nodes such that each node in a group is reachable from every other node.

PARAGON uses a parallel Shiloach Vishkin style algorithm based on pointer jumping and hooking.

Function Signature

from paragon.algorithms import parallel_connected_components
parallel_connected_components(graph: Graph, threads: int = -1)

Parameters

graph : Graph

The input graph.

Must be an instance of Graph
Should be undirected for meaningful components

threads : int, optional

Number of threads to use.

-1 → use all CPU cores
>= 1 → manual control

NUM_THREADS = 4

Note

The algorithm uses thread-level parallelism to update component labels.

Warning

threads = 0 is invalid
threads < -1 is invalid
Invalid graph type raises TypeError

Return Value

List[int]

Where:

comp[i] = component identifier (representative node) of vertex i

Basic Example

from paragon import Graph
from paragon.algorithms import parallel_connected_components

NUM_THREADS = 4

g = Graph(vertices=6)

g.add_edges(edges=[
    (0, 1),
    (1, 2),
    (3, 4)
])

comp = parallel_connected_components(
    graph=g,
    threads=NUM_THREADS
)

print(comp)

Output:

[0, 0, 0, 3, 3, 5]

Explanation:

Component 1 → {0, 1, 2}
Component 2 → {3, 4}
Component 3 → {5}

Advanced Example

from paragon import Graph
from paragon.algorithms import parallel_connected_components

NUM_THREADS = 4

g = Graph(vertices=8)

g.add_edges(edges=[
    (0, 1),
    (1, 2),
    (2, 3),
    (4, 5),
    (6, 7)
])

comp = parallel_connected_components(
    graph=g,
    threads=NUM_THREADS
)

print(comp)

Output:

[0, 0, 0, 0, 4, 4, 6, 6]

Algorithm Details

The algorithm uses a label propagation approach based on pointer jumping.

Technique

Hooking: merge smaller component into larger one
Pointer jumping: compress paths to speed up convergence
Parallel updates across all vertices

Pseudocode

\[\begin{split}\textbf{Initialize:} \\ \quad parent[v] \gets v \ \forall v \in V\end{split}\]

\[\textbf{repeat until convergence:}\]

\[\begin{split}\quad \textbf{parallel for each } u \in V: \\ \qquad \textbf{for each } v \in Adj(u): \\ \qquad\quad \textbf{if } parent[u] \neq parent[v]: \\ \qquad\quad\quad parent[\max(parent[u], parent[v])] \gets \min(parent[u], parent[v])\end{split}\]

\[\begin{split}\quad \textbf{parallel for each } u \in V: \\ \qquad \textbf{while } parent[u] \neq parent[parent[u]]: \\ \qquad\quad parent[u] \gets parent[parent[u]]\end{split}\]

Note

Pointer jumping rapidly reduces tree height, enabling fast convergence.

Time Complexity

O((V + E) log V)  (parallelized)

Best Practices

Use on undirected graphs
Use sufficient threads for faster convergence
Works well for large sparse graphs

Tip

This algorithm is widely used in parallel graph processing systems due to its scalability.

Warning

Results depend on internal merging order but always produce correct component groupings.