Class DisjointSet

Basic representation of a disjoint set data structure.

Inheritance
object
DisjointSet
Implements
Inherited Members
Namespace: GoRogue
Assembly: GoRogue.dll
Syntax
public class DisjointSet : IReadOnlyDisjointSet
Remarks

For reasons pertaining to optimization, this disjoint set implementation does not use generics, and instead holds integer values, which will 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

View Source

DisjointSet(int)

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

Declaration
public DisjointSet(int size)
Parameters
Type Name Description
int size

(Max) size of the disjoint set.

Properties

View Source

Count

Number of distinct sets.

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

Methods

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.
View Source

ExtendToString(Func<int, string>)

Returns a string representation of the DisjointSet, showing parents and all elements in their set. The given function is used to produce the string for each element.

Declaration
public string ExtendToString(Func<int, string> elementStringifier)
Parameters
Type Name Description
Func<int, string> elementStringifier
Returns
Type Description
string

A string representation of the DisjointSet.
View Source

Find(int)

Returns the ID for the parent of the set containing the set with ID objectID, performing path compression as search is completed.

Declaration
public int Find(int obj)
Parameters
Type Name Description
int obj
Returns
Type Description
int

The ID for the parent of the object given.
View Source

InSameSet(int, int)

Returns true if the objects specified by the given IDs are in the same set.

Declaration
public bool InSameSet(int obj1, int obj2)
Parameters
Type Name Description
int obj1
int obj2
Returns
Type Description
bool

True if the the objects specified by the given IDs are in the same set, false otherwise.
View Source

MakeUnion(int, int)

Performs a union of the sets containing the objects specified by the two IDs. 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
int obj1
int obj2
Remarks

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

View Source

ToString()

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

Declaration
public override string ToString()
Returns
Type Description
string

A string representation of the DisjointSet.
Overrides

Events

View Source

SetsJoined

Fired when two sets are joined into one. The arguments give the IDs of the two sets that were joined.

Declaration
public event EventHandler<JoinedEventArgs>? SetsJoined
Event Type
Type Description
EventHandler<JoinedEventArgs>

Implements

Extension Methods