Disjoint-Set

A disjoint-set data structure can be used to find connected and disconnected pieces in a graph efficiently. A typical use-case in Blender is to detect mesh islands.

Blender currently has two implementations of this data structure. AtomicDisjointSet (source) which is thread-safe and DisjointSet (source) which is not. There is a small overhead to using the atomic version when multi-threading is not used.

/* Create disjoint set. Initially, every vertex is disjoint from the others. */
DisjointSet<int> disjoint_set(verts_num);

/* Merge sets when there is an edge between them. */
for (const int2 edge : edges) {
  disjoint_set.join(edge[0], edge[1]);
}

/* Check if two vertices are in the same set. */
bool is_joined = disjoint_set.in_same_set(vert_1, vert_2);

/* Get representative element for all vertices in an island. */
int element = disjoint_set.find_root(vert_index);