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);