Celdir
commented
7 months ago +1 to this, I have a different use case. I'm implementing graph contractions for the Stoer-Wagner algorithm and I'm using DisjointSet to represent graph nodes that are merged. Knowing the root for a given node is necessary for me to be able to merge edges of nodes that have been contracted.
jogru0
Currently, there is no way to get the "index" of a group. That is, given two elements in the disjoint sets, there is no way to give an ambiguous index to the whole group. Of course internally, we know that there is an unambiguous index for a group -
root_of. This is only "unambiguous" provided that no union occurs involving any elements of the group.My use case
I have a triangulation of a polygon (with holes). I want to merge these triangles together into convex polygons (to make a navigation mesh). To do this I'm using something like the Hertel-Mehlhorn Algorithm.
Essentially: 1) Sort all shared edges by their length (longest-first). 2) for each edge, check if merging the polygons on either side would be convex. If so, merge those polygons. 3) Repeat until no more edges left.
The way I'm doing this is I represent each triangle as an element in the disjoint sets. Whenever I merge two polygons, I union them in the disjoint sets. However, I still need to refer to the same polygon if I try to "dissolve" a different edge. So I need a way for the triangles that have been merged into a polygon to "refer" to the polygon itself. I can do this by always re-associating the polygon with the
root_ofafter union-ing.