Class DisjointSets
- java.lang.Object
-
- org.locationtech.jts.operation.union.DisjointSets
-
public class DisjointSets extends java.lang.Object
A data structure that represents a partition of a set into disjoint subsets, and allows merging subsets. Set items are represented by integer indices (which will typically be an index into an array of the objects actually being partitioned). Initially each item is in its own subset. Client code can merge subsets of items as required for the algorithm being performed (e.g. set partitioning or clustering). The current partitioning can be computed at any time, and subset items accessed using theDisjointSets.Subsets
accessor.See the Wikipedia article on disjoint set data structures.
- Author:
- Martin Davis
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description class
DisjointSets.Subsets
A representation of a partition of a set of items into disjoint subsets.
-
Constructor Summary
Constructors Constructor Description DisjointSets(int size)
Creates a new set containing a given number of items.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
isInSameSubset(int i, int j)
Tests if two items are in the same subset.void
merge(int i, int j)
Merges two subsets containing the given items.DisjointSets.Subsets
subsets()
Gets a representation of the current partitioning.
-
-
-
Method Detail
-
isInSameSubset
public boolean isInSameSubset(int i, int j)
Tests if two items are in the same subset.- Parameters:
i
- an item indexj
- another item index- Returns:
- true if items are in the same subset
-
merge
public void merge(int i, int j)
Merges two subsets containing the given items. Note that the items do not have to be the roots of their respective subsets. If the items are in the same subset the partitioning does not change.- Parameters:
i
- an item indexj
- another item index
-
subsets
public DisjointSets.Subsets subsets()
Gets a representation of the current partitioning. This creates a snapshot of the partitioning; the set can be merged further after this call.- Returns:
- an representation of the current subset partitioning.
-
-