That is, disjoint sets

Steven Curtis

Nov 23, 2020·5 min read

Before we start

Difficulty: Beginner | Easy | Normal | Challenging
This article has been developed using Xcode 12.1, and Swift 5.3

Prerequisites

* You will be expected to be aware how to either make a Single View Application in Swift or use a Playground
* It would be useful to have some knowledge of Sets in Swift
* A dictionary is used to store the nodes

Keywords and Terminology

Data Structure: A way of formatting data Disjoint: (of two or more sets) having no elements in common

Union-find data structure: A data structure that sorts a collection of disjoint sets

The Union-Find Data

The background

Disjoint-set data structures play a key role in an efficient version of Kruskal’s algorithm for finding the minimal spanning tree of a graph, and the data structure form the basis of a wide variety of algorithms including cycle detection.

More than that, they are have applications in Data Science and are even commonly used for LeetCode questions.

Depending on your needs, they can be a big deal.

Disjoint sets

If we have two sets that do not share elements we have a situation like that shown in the diagram above.

In Swift this might be represented as the following sets, p and q.

That is, the sets p and q are disjoint because they have no members in common. The example works with any type of set you would like to implement in Swift.

Transitive Property of Equality

Equality is transitive. This means:

if a = b and b = c, then a = c

Approach to relevant problems

We can perform a BFS from any two nodes — if one node can be reached from the other they are by definition in the same set.

By adopting this approach, a BFS would have to be performed for each query (that is, each pair you wish to test whether they are in the same set) leaving the time complexity as O(N * M) where N is the set size and M is total number of queries to be tested.

An alternative is to use the Union-Find Data Structure where elements in the same set are kept in a single group. It is this approach that this article will focus on.

My Node Class

This node must be a class type as the node references itself. The class also confoms to the Hashable protocol

The Union-Find Data Structure

Main operations There are three basic operations that are used in such a data structure:

• find: Determine which subset an element is within
• union: Join two subsets into a single set
• addSet: Create a new set with an element

Therefore to create a tree (which effectively the set is) we will need to combine addSet and union since every time we wish to add a new element we must first call addSet to add it, before using union to join it into an existing set.

This means we might have the set {“a”, “b”} and then add a set {“c”}.<br<

We then can call union on two elements for example

So each subset is represented by a tree.

The UnionFind class

The UnionFind class Here we conform to the Hashable protocol and the Comparable protocol, and store an index of nodes and a set number for each one.

As a result the class is defined as follows:

with, of course, the following functions are declared below:

addSet

Here we create a new tree for each element, and the index is taken from the number of nodes:

find

We can check the index dictionary

union

We take the root for the tree from the firstElement, and the root from the secondElement. Then we put the secondNode onto the firstNode, for example:

sameSet (additional)

If the index for the firstElement is the same as the index for the secondElement, they are in the same set.

Improvements

These improvements come under the banner of heuristics, and enable performance improvesment

Union by Rank

When performing a union, if one tree has a shorter depth then ithe algorithm should favour keeping the tree as short as possible. This can be accomplished by moving the longer tree to the shorter one. This can reduce the time to find the root of any particular tree.

Path Compression

All nodes on a tree should have a single parent, which is the root.

Something approaching this has been implemented in my version of the Union-find structure described above, and is shown in the Repo.

Conclusion

The Repo has all of the code so you can see how this all works in a working Swift Playground.

If you’ve any questions, comments or suggestions please hit me up on Twitter