Class QuickUnionDisjointSet

An IDisjointSet implementation based on a simple conceptually storing a forest of trees, by defining the index of the parent node, for each value stored in the data structure.

Inheritance

System.Object

QuickUnionDisjointSet

WeightedQuickUnionDisjointSet

Implements

IDisjointSet

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)

System.Object.ToString()

Namespace: MoreStructures.DisjointSets

Assembly: MoreStructures.dll

Syntax

public class QuickUnionDisjointSet : IDisjointSet

Remarks

• This implementation optimizes the runtime of Union(Int32, Int32), which only requires navigating to the each root instead of a full linear scan of the list, at the cost of Find(Int32) and AreConnected(Int32, Int32), which also require to navigate to the root.
  
• Check QuickFindDisjointSet for an alternative implementation of IDisjointSet which does the opposite, in terms of optimization.

Constructors

QuickUnionDisjointSet(Int32)

Builds a Disjoint Set structure containing valuesCount disjoint values, each one into its own singleton tree.

Declaration

public QuickUnionDisjointSet(int valuesCount)

Parameters

Type	Name	Description
System.Int32	valuesCount

Remarks

Requires initializing all the valuesCount items of the underlying list, so that each item is conceptually in its own singleton tree.
Time and Space Complexity are O(n).

Properties

Parents

Maps the i-th item of the Disjoint Set to the parent in the tree structure, they belong to.
I-th items which are roots have parent equal to themselves (i.e. i).

Declaration

protected int[] Parents { get; }

Property Value

Type	Description
System.Int32[]

SetsCount

Declaration

public virtual int SetsCount { get; }

Property Value

Type	Description
System.Int32

Remarks

ALGORITHM
- Obtained as the number of distinct roots in the forest of trees.
- All items i from 0 to ValuesCount - 1 are iterated over.
- An item i is a root if it's parent of itself: Parents[i] == i.

COMPLEXITY
- Checking whether an item is parent of itself is a constant-time operation.
- Therefore, Time and Space Complexity are O(n), where n is ValuesCount.

ValuesCount

Declaration

public virtual int ValuesCount { get; }

Property Value

Type	Description
System.Int32

Remarks

Set at construction time, based on the constructor parameter.
Time and Space Complexity are O(1).

Methods

AreConnected(Int32, Int32)

Declaration

public virtual bool AreConnected(int first, int second)

Parameters

Type	Name	Description
System.Int32	first
System.Int32	second

Returns

Type	Description
System.Boolean

Remarks

ALGORITHM
- Finds the root of first and the root of second and compares them.
- Because the root of a tree is unique, if the two roots coincide, first and second belong to the same tree, and are connected.
- Otherwise they belong to two separate trees of the forest, and are not connected.

COMPLEXITY
- Find the two roots takes a time proportional to the height of the two trees.
- If no mechanism to keep trees flat is put in place by this data structure, the height of each is O(n) in the worst case.
- Therefore, Time Complexity is O(n). Space Complexity is O(1).
- If a sub-class of QuickUnionDisjointSet introduces mechanisms to keep trees flat, the complexity may become sub-linear. An example is WeightedQuickUnionDisjointSet.

Find(Int32)

Declaration

public virtual int Find(int value)

Parameters

Type	Name	Description
System.Int32	value

Returns

Type	Description
System.Int32

Remarks

ALGORITHM
- Finds the root of value, by iteratively traversing the tree upwards, until the root of the tree is reached.
- Because the root of a tree is unique and can be reached by every node of the tree navigating upwards, it represents a good identifier of the set of all items in the same tree of the forest.

COMPLEXITY
- Find the root takes a time proportional to the height of the tree, the item is in.
- If no mechanism to keep trees flat is put in place by this data structure, the height of the tree is O(n) in the worst case.
- Therefore, Time Complexity is O(n). Space Complexity is O(1).
- If a sub-class of QuickUnionDisjointSet introduces mechanisms to keep trees flat, the complexity may become sub-linear. An example is WeightedQuickUnionDisjointSet.

GetParents()

Returns a copy of the parents of all the values of the forest representing the Disjoint Set.

Declaration

public IList<int> GetParents()

Returns

Type	Description
IList<System.Int32>

Union(Int32, Int32)

Declaration

public virtual void Union(int first, int second)

Parameters

Type	Name	Description
System.Int32	first
System.Int32	second

Remarks

ALGORITHM
- It first finds the root R1 of first and the root R2 of second, by running Find(Int32) on each item.
- Then, it attaches R2 as immediate child of R1, by setting the parent of R2 to R1.
- This way the two three now are merged into a single one, which means that all items of the two trees, including first and second are now in the same set.

COMPLEXITY
- Find the two roots takes a time proportional to the height of the two trees.
- If no mechanism to keep trees flat is put in place by this data structure, the height of each tree is O(n) in the worst case.
- Attaching one root as child of the other is a constant-time operation, since it only requires setting the parent in the list of parents, which is O(1) work.
- Therefore, Time Complexity is O(n). Space Complexity is O(1).
- If a sub-class of QuickUnionDisjointSet introduces mechanisms to keep trees flat, the complexity may become sub-linear. An example is WeightedQuickUnionDisjointSet.

Implements

IDisjointSet

Extension Methods

SuffixStructureNodeExtensions.GetAllSuffixesFor<TEdge, TNode>(TNode, TextWithTerminator)