Class ScyllaDisjointSet

A managed Union-Find (Disjoint Set Union) data structure backed by managed arrays, implementing both path compression and union-by-rank optimizations for near-constant-time amortized operations.

Inheritance
object
ScyllaDisjointSet
Implements
Inherited Members
Namespace: Scylla.Core.Structures
Assembly: ScyllaCore.dll
Syntax
public sealed class ScyllaDisjointSet : IScyllaCollection
Remarks

A disjoint set partitions a fixed set of N elements (identified by integer indices 0..N-1) into non-overlapping groups called components. The two fundamental operations are:

  • Find(int) Determines which component an element belongs to by returning the component's canonical representative (root).
  • Union(int, int) Merges two components into one, reducing ComponentCount by one if the elements were previously in distinct components.

Both operations run in O(alpha(n)) amortized time, where alpha is the inverse Ackermann function - effectively constant for any input size encountered in practice.

Path compression is applied during every Find(int) call: once the root is located, all nodes on the traversal path are rewired to point directly at the root. This flattens the internal tree so that future lookups on those elements require fewer hops.

Union-by-rank is applied during every Union(int, int) call: the root of the shallower tree is attached under the root of the deeper tree. When ranks are equal the rank of the surviving root is incremented by one. This keeps trees shallow and prevents the degenerate linked-list worst case.

The capacity (number of elements) is fixed at construction and cannot be changed afterwards. Calling Clear() resets all union information but preserves the allocated capacity.

This class is not thread-safe by default (ThreadSafety reports Unsynchronized). For concurrent access wrap the instance via AsSynchronized(object) or use the Synchronized(object) option on the fluent builder - both produce a ScyllaDisjointSet.SynchronizedScyllaDisjointSet that locks every operation on a shared monitor.

Common use-cases include connectivity queries in graphs, maze generation, Kruskal's minimum spanning tree algorithm, and clustering problems. 

// Direct construction - 100 singleton components.
var dsu = new ScyllaDisjointSet(100);
dsu.Union(0, 1);
dsu.Union(1, 2);
bool connected = dsu.Connected(0, 2); // true
int root = dsu.Find(2);               // same root for 0, 1, 2

// Fluent builder - synchronized variant.
var dsu = ScyllaDisjointSet.CreateBuilder()
.WithCapacity(256)
.Synchronized()
.Build();

Constructors

ScyllaDisjointSet(int)

Initializes a new ScyllaDisjointSet with the specified number of elements, placing each element in its own singleton component.

Declaration
public ScyllaDisjointSet(int capacity = 16)
Parameters
Type Name Description
int capacity

The total number of elements tracked by this set, addressed as integer indices 0..capacity-1. Values less than 0 are silently clamped to 0. When omitted, defaults to 16.
Remarks

After construction, ComponentCount equals capacity because no elements have been merged yet. The internal parent and rank arrays are allocated once and their size never changes; use Clear() to reset connectivity without re-allocating.

Properties

Capabilities

Gets the feature and capability flags advertised by this collection instance.

Declaration
public ScyllaCollectionCapabilities Capabilities { get; }
Property Value
Type Description
ScyllaCollectionCapabilities

Always HasCapacity for ScyllaDisjointSet, reflecting that it has a meaningful fixed-size capacity concept.

Capacity

Gets the total number of elements managed by this disjoint set.

Declaration
public int Capacity { get; }
Property Value
Type Description
int

The fixed element count established at construction. For this structure, Capacity always equals Count because the set operates over a dense, pre-allocated range of indices rather than a dynamically growing list. Returns 0 when constructed with capacity == 0.

ComponentCount

Gets the current number of disjoint connected components.

Declaration
public int ComponentCount { get; }
Property Value
Type Description
int

Starts at Capacity immediately after construction (every element is its own singleton component). Decreases by one each time Union(int, int) successfully merges two previously unconnected components. Resets to Capacity after Clear(). The minimum possible value is 1 (all elements in one component); the maximum is Capacity (no unions performed yet).

Count

Gets the number of elements tracked by this disjoint set.

Declaration
public int Count { get; }
Property Value
Type Description
int

Identical to Capacity for this fixed-size structure. The value never changes after construction; use Clear() to reset connectivity without changing the element count.

IsEmpty

Gets a value indicating whether this disjoint set contains no elements.

Declaration
public bool IsEmpty { get; }
Property Value
Type Description
bool

true when the set was constructed with capacity == 0; false otherwise. When true, all operations that accept an element index will throw ArgumentOutOfRangeException.

SyncRoot

Gets the synchronization root used to coordinate concurrent access.

Declaration
public object SyncRoot { get; }
Property Value
Type Description
object

Always null for the unsynchronized ScyllaDisjointSet instance. The ScyllaDisjointSet.SynchronizedScyllaDisjointSet wrapper returns a non-null stable object for use with lock statements.

ThreadSafety

Gets the thread-safety level of this collection instance.

Declaration
public ScyllaCollectionThreadSafety ThreadSafety { get; }
Property Value
Type Description
ScyllaCollectionThreadSafety

Always Unsynchronized for the base ScyllaDisjointSet class. Use AsSynchronized(object) or the Synchronized(object) builder option to obtain a wrapper that reports Synchronized.

Methods

AsSynchronized(object)

Returns a ScyllaDisjointSet.SynchronizedScyllaDisjointSet that wraps this instance and makes every operation thread-safe by acquiring a lock before delegating to the inner set.

Declaration
public ScyllaDisjointSet.SynchronizedScyllaDisjointSet AsSynchronized(object syncRoot = null)
Parameters
Type Name Description
object syncRoot

An optional external object to use as the monitor lock. When null a private object is allocated internally. Supplying a shared syncRoot allows the caller to coordinate this set with other operations under the same lock.
Returns
Type Description
ScyllaDisjointSet.SynchronizedScyllaDisjointSet

A new ScyllaDisjointSet.SynchronizedScyllaDisjointSet that delegates all reads and writes to this ScyllaDisjointSet instance while holding the specified lock.
Remarks

The wrapper does not copy or snapshot the underlying data. Both the wrapper and the original instance share the same parent and rank arrays, so callers must not access the original unsynchronized instance concurrently with the wrapper.

Clear()

Resets every element to its own singleton component, restoring the structure to its post-construction state.

Declaration
public void Clear()
Remarks

After this call, ComponentCount equals Capacity and every element is its own root. All rank information is cleared to zero. The allocated arrays are reused, so no heap allocation occurs.

Connected(int, int)

Determines whether elements x and y belong to the same component.

Declaration
public bool Connected(int x, int y)
Parameters
Type Name Description
int x

The zero-based index of the first element. Must satisfy 0 <= x < Capacity.
int y

The zero-based index of the second element. Must satisfy 0 <= y < Capacity.
Returns
Type Description
bool

true if x and y are in the same component (i.e., have the same root); false otherwise. Returns true when both arguments are the same index.
Remarks

Internally calls Find(int) twice and compares roots. Path compression is applied as a side effect, so repeated connectivity queries are progressively faster.

Exceptions
Type Condition
ArgumentOutOfRangeException

Thrown when x or y is out of the valid index range, or when the set is empty.

CreateBuilder()

Creates and returns a new fluent ScyllaDisjointSet.Builder for configuring and constructing a ScyllaDisjointSet instance.

Declaration
public static ScyllaDisjointSet.Builder CreateBuilder()
Returns
Type Description
ScyllaDisjointSet.Builder

A fresh ScyllaDisjointSet.Builder pre-configured with the default capacity of 16 and no synchronization. Call WithCapacity(int), Synchronized(object), and finally Build() or BuildConcrete() to obtain the finished instance.

Find(int)

Returns the canonical representative (root) of the component that contains element x, applying path compression as a side effect.

Declaration
public int Find(int x)
Parameters
Type Name Description
int x

The zero-based index of the element whose component root is to be found. Must satisfy 0 <= x < Capacity.
Returns
Type Description
int

The root index of the component containing x. Two elements a and b belong to the same component if and only if Find(a) == Find(b). The root is stable across calls as long as no Union(int, int) operation merges the component with another.
Remarks

Path compression rewires every node on the traversal path to point directly at the root. This does not change the logical grouping of elements but flattens the internal tree so that subsequent calls on the same elements are faster. The amortized complexity is O(alpha(n)), where alpha is the inverse Ackermann function.

Exceptions
Type Condition
ArgumentOutOfRangeException

Thrown when x is negative, greater than or equal to Capacity, or when the set is empty (IsEmpty is true).

Union(int, int)

Merges the components that contain elements x and y into a single component, using union-by-rank to keep the internal trees shallow.

Declaration
public bool Union(int x, int y)
Parameters
Type Name Description
int x

The zero-based index of the first element. Must satisfy 0 <= x < Capacity.
int y

The zero-based index of the second element. Must satisfy 0 <= y < Capacity.
Returns
Type Description
bool

true if x and y were in distinct components and were successfully merged, reducing ComponentCount by one. false if they already belonged to the same component, in which case the structure is unchanged.
Remarks

Union-by-rank attaches the root of the tree with the lower rank under the root of the tree with the higher rank. When both roots have equal rank, the root of y's component is attached under the root of x's component, and that root's rank is incremented by one.

Both x and y may be the same index; in that case the call returns false immediately without modifying state.

Exceptions
Type Condition
ArgumentOutOfRangeException

Thrown when x or y is out of the valid index range, or when the set is empty.

Implements

Extension Methods

See Also