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.