Interface IDisjointSet

A data structure modelling a collection of sets of non-negative consecutive integer values 0..k-1, where set can be easily merged together and values can be easily checked for membership to the same set.

Namespace: MoreStructures.DisjointSets
Assembly: MoreStructures.dll
Syntax
public interface IDisjointSet
Remarks

Disjoint sets are effective when dealing with equivalence relationships, i.e. relationships which are reflexive, symmetric and transitive.
It's not directly usable when relationships have direction (e.g. if A points to B, B doesn't necessarily points to A).

Properties

| Improve this Doc View Source

SetsCount

The number of distinct sets, the data structure is made of.

Declaration
int SetsCount { get; }
Property Value
Type Description
System.Int32

A non-negative System.Int32, non-bigger than ValuesCount.
| Improve this Doc View Source

ValuesCount

The number of integer values in the data structure.

Declaration
int ValuesCount { get; }
Property Value
Type Description
System.Int32

A non-negative System.Int32.

Methods

| Improve this Doc View Source

AreConnected(Int32, Int32)

Whether the two provided integer values belong to the same set, or two disjoint sets.

Declaration
bool AreConnected(int first, int second)
Parameters
Type Name Description
System.Int32 first

The value of the first integer. Must be non-negative and smaller than ValuesCount.
System.Int32 second

The value of the second integer. Must be non-negative and smaller than ValuesCount.
Returns
Type Description
System.Boolean

true if the values belong to the same set, false otherwise.
| Improve this Doc View Source

Find(Int32)

Returns the set identifier of the provided value.

Declaration
int Find(int value)
Parameters
Type Name Description
System.Int32 value

The value of the integer, to find the set of. Must be non-negative and smaller than ValuesCount.
Returns
Type Description
System.Int32

An System.Int32 identifing the set, value is member of.
| Improve this Doc View Source

Union(Int32, Int32)

Establishes a "union" relashionship between the integer values first and second, merging the sets of the two values into a single set.

Declaration
void Union(int first, int second)
Parameters
Type Name Description
System.Int32 first

The value of the first integer. Must be non-negative and smaller than ValuesCount.
System.Int32 second

The value of the second integer. Must be non-negative and smaller than ValuesCount.

Extension Methods