Class DisjointSet

Basic representation of a disjoint set data structure.

Inheritance
System.Object
DisjointSet
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
Namespace: GoRogue
Assembly: GoRogue.dll
Syntax
[Serializable]
public class DisjointSet : IReadOnlyDisjointSet
Remarks

For reasons pertaining to optimization, this disjoint set implementation does not use generics, and instead holds integer values, which MUST be exactly all integer values in range [0, num_items_in_set - 1]. Thus, you will need to assign appropriate IDs to objects you intend to add and map them appropriately.

Constructors

| Improve this Doc View Source

DisjointSet(Int32)

Constructor. The disjoint set will contain all values in range [0, size - 1].

Declaration
public DisjointSet(int size)
Parameters
Type Name Description
System.Int32 size

(Max) size of the disjoint set.

Properties

| Improve this Doc View Source

Count

Number of distinct sets.

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

Methods

| Improve this Doc View Source

AsReadOnly()

Returns a read-only representation of the disjoint set.

Declaration
public IReadOnlyDisjointSet AsReadOnly()
Returns
Type Description
IReadOnlyDisjointSet

A read-only representation of the disjoint set.
| Improve this Doc View Source

Find(Int32)

Returns the parent of the set containing obj, performing path compression as the search is completed.

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

Object to search for.
Returns
Type Description
System.Int32

The parent of the object given.
| Improve this Doc View Source

InSameSet(Int32, Int32)

Returns true if the two objects specified are in the same set.

Declaration
public bool InSameSet(int obj1, int obj2)
Parameters
Type Name Description
System.Int32 obj1
System.Int32 obj2
Returns
Type Description
System.Boolean

True if the two objects are in the same set, false otherwise.
| Improve this Doc View Source

MakeUnion(Int32, Int32)

Performs a union of the sets containing the two objects specified. After this operation, every element in the sets containing the two objects specified will be part of one larger set.

Declaration
public void MakeUnion(int obj1, int obj2)
Parameters
Type Name Description
System.Int32 obj1
System.Int32 obj2
Remarks

If the two elements are already in the same set, nothing is done.

| Improve this Doc View Source

ToString()

Returns a string representation of the DisjointSet, showing parents and all elements in their set.

Declaration
public override string ToString()
Returns
Type Description
System.String

A string representation of the DisjointSet.
Overrides
System.Object.ToString()

Implements

Extension Methods