Disjoint Set ADT (Abstract Data Type)

Introduction

We call two sets disjoint, if they have nothing in common. Intersection of those sets result null set. Disjoint set ADT is a data structure that stores disjoint subsets of elements. In this article, we’ll discuss its introduction, examples and later the ways of its implementation.

Uses of Disjoint Set ADT?

Suppose we’ve a database of people. We want to find who is related to whom. Consider, we’ve a list of names of all people in a locality but we’re unaware of their relationships to each other. We’ll obtain this relation information gradually using the concept of disjoint set. Example: We’ve only following information “Haaris is the cousin of Saad and Saad is the cousin of Ahmad” then we’ll learn that the “Haaris is related to Ahmad”.

Robotics

Other use of disjoint set is in the robotics. How robots perform their task efficiently similar to humans? Here comes the concept of blob coloring _This is the well-known computer vision problem for black and white images, where we put all the picture elements (pixels) that belong to the same “blobs”, and give each pixel in each different blob an identical label. In short, we partition the pixels into disjoint sets, one set per blob.

Look at the Figure-1. We partitioned it into five non-overlapping black colored regions of different shapes, called blobs. Robot identify this image if we partition the pixels into disjoint sets, one set per blob.

Computer Vision

Not finished yet, disjoint sets play their role in computer vision, image segmentation problem. See the Figure-2, on the left of an old ship in gray scales.

We want to find regions of different colors in this picture e.g. all regions in the picture of color black and all regions in the image of color gray. The image on the right represents the resultant image.

Scanning Processes in Hospitals

Hospitals use applications of disjoint set ADT in processes like MRI (Magnetic Resonance Imaging), CAT Scan, or CT Scan to view the inner parts of the human body. These scanned images in gray scales represent organs of the human body.

Let’s discuss equivalence relationship to solve the problem of people’s relationship.

Equivalence Relations

A binary relation R over a set S is called an equivalence relation if it has following properties.

• Reflexivity: for all element x ∈ S, x R x
• Symmetry: for all elements x and y, x R y if and only if y R x
• Transitivity: for all elements x, y and z, if x R y and y R z then x R z

For the relation to be equivalent, it’s important for both sets to have all the properties of reflexivity, symmetry, and transitivity satisfied.

Examples for Equivalence Relations

≤ Relationship

The ≤ relationship is not an equivalence relation.

• Reflexivity: It is reflexive, since x ≤ x, as x is not less than x but surely is equal to x.
• Transitivity: Since x ≤ y and y ≤ z implies x ≤ z. it’s also true.
• Symmetric: it is not symmetric as x ≤ y does not imply y ≤ x.

Conclusion: Two rules are satisfied but symmetric rule does not. Therefore ≤ is not an equivalence relation.

Electrical connectivity

Electrical connectivity, where all connections are by metal wires, is an equivalence relation.

• Reflexivity: Component is connected to itself (Transistor is connected to itself).
• Symmetric: Component “a” is connected to component “b”, then “b” must be electrically connected to “a”.
• Transitivity: If component “a” is connected to component “b” and “b” is connected to “c”, then “a” is connected to “c”.

Conclusion: All rules are satisfied. Therefore, this is equivalent relationship.

Now, let’s come to our task of disjoint set ADT. We’ll build the strategy to implement this data structure.

Disjoint Sets

An equivalence relation R over a set S can be viewed as a partitioning of S into disjoint sets. Each set of the partition is called an equivalence class of R (all elements that are related).

See the below diagram, we’ve a set in the shape of an ellipse. This set has been partitioned into multiple sets. All these parts are disjoint sets and belong to an equivalence class.

Suppose there are lot of people around you. How would you find out the relationship between them. These people divide into small groups, with each group consisting of members who are related to one another but have no relation with members of other groups. So, we can make disjoint sets in this way.

What happens if a person from one group marries someone from another group? This makes relation between these groups. The main thing so to get idea of solving the relation problem. Through this method, we’ll find out that who is related to whom.

Main points to consider in the problem: –

• Every member of S appears in exactly one equivalence class.
• The second thing is to decide if a R b. For this purpose, we need only to check whether a and b are in the same equivalence class.

In example of pixels, if pixel p1 is in a region and want to know the relation of pixel p2 with it, there is only need to confirm that these two pixels are in the same region.

Conclusion

Disjoint set ADT provides the strategy to solve the equivalence problem. In this article, you learned introductory level of disjoint set ADT and got little idea about its use in real life. Especially, the first use of finding relationship of people with one another. We didn’t go deep to this problem of finding relation, just built an idea of solve it.

REFERENCE: CS301 Handouts (page 383 to 388)