Graph Image Graph Connectivity

One of the most commonly used graph problems is that of finding the connected components of an undirected graph. Given a graph G = (V,E), where V is a set of vertices (of size n) and E is a set of edges (of size m), the connected components of G are the sets of vertices such that all vertices in each set are mutually connected (reachable by some path), and no two vertices in different sets are connected. Finding connected components is used in many diverse fields such as computer vision [1, 20, 21, 34], where pixels in a two- or three-dimensional image are grouped into regions representing objects or faces of objects; spin models in physics [7, 9, 30]; VLSI circuit design [4, 13, 28]; communication networks [2]; program analysis and implementation [19, 22, 33]; neural nets; and economics [18].

In our work we are interested in the pragmatic aspects of parallel algorithms for finding connected components. In our work we have implemented and compared several parallel algorithms. The results of the work is described in the paper A Comparison of Data-Parallel Algorithms for Connected Components (also see the talk notes). The algorithms we have considered are

The Shiloach-Vishkin algorithm [29].
Based on forming trees by hooking using edges and then shortcutting using pointer jumping. The interesting aspect is how the hooking is implemented so as to avoid forming cycles. It runs in O(log n) steps, each of which take at most O(m) work. The NESL code.
Awerbuch-Shiloach algorithm [3].
A variant of Shiloach-Vishkin algorithm. It simplifies the decisions of how to do the hooking. The NESL code.
Random-mate algorithm [26, 10].
Based on randomly flipping a coin on each node such that each node is labeled as a child or parent and then hooking from children to parents. The children are then contracted into the parents. With high probability, after O(log n) rounds, each component is contracted down to a single node. The NESL code.
Hybrid algorithm.
A hybrid of the Awerbuch-Shiloach and Random-Mate algorithms. From our experimentation it seems to be the most practical of the algorithms. The NESL code.
In addition to implementing the original algorithms, we made many improvement.

An interactive animation of three of these algorithms is available.

Related Work (online)

Up to the Irregular Algorithms page, the NESL page, the Scandal page, or John Greiner's research.