Data.DisjointSet

Persistent disjoint-sets. Disjoint-sets are a set of elements with equivalence relations defined between elements, i.e. two elements may be members of the same equivalence set. This library provides the fundamental operations classically known as union, find, and makeSet. It also offers novelties like a Monoid instance for disjoint sets and conversion functions for interoperating with lists. See the tutorial at the bottom of this page for an example of how to use this library.

Documentation

data DisjointSet a

Instances

Ord a => Eq (DisjointSet a)

Methods

(==) :: DisjointSet a -> DisjointSet a -> Bool

(/=) :: DisjointSet a -> DisjointSet a -> Bool

Ord a => Ord (DisjointSet a)

Methods

compare :: DisjointSet a -> DisjointSet a -> Ordering

(<) :: DisjointSet a -> DisjointSet a -> Bool

(<=) :: DisjointSet a -> DisjointSet a -> Bool

(>) :: DisjointSet a -> DisjointSet a -> Bool

(>=) :: DisjointSet a -> DisjointSet a -> Bool

max :: DisjointSet a -> DisjointSet a -> DisjointSet a

min :: DisjointSet a -> DisjointSet a -> DisjointSet a

(Show a, Ord a) => Show (DisjointSet a)

Methods

showsPrec :: Int -> DisjointSet a -> ShowS

show :: DisjointSet a -> String

showList :: [DisjointSet a] -> ShowS

Ord a => Semigroup (DisjointSet a)

Methods

(<>) :: DisjointSet a -> DisjointSet a -> DisjointSet a

sconcat :: NonEmpty (DisjointSet a) -> DisjointSet a

stimes :: Integral b => b -> DisjointSet a -> DisjointSet a

Ord a => Monoid (DisjointSet a)

Methods

mempty :: DisjointSet a

mappend :: DisjointSet a -> DisjointSet a -> DisjointSet a

mconcat :: [DisjointSet a] -> DisjointSet a

Construction

empty :: DisjointSet a

The empty set of disjoint sets.

singleton :: a -> DisjointSet a

Create a disjoint set with one member. O(1).

singletons :: Eq a => Set a -> DisjointSet a

Create a disjoint set where all members are equal.

doubleton :: Ord a => a -> a -> DisjointSet a

Create a disjoint set with a single set containing two members

insert :: Ord a => a -> DisjointSet a -> DisjointSet a

Insert x into the disjoint set. If it is already a member, then do nothing, otherwise x has no equivalence relations. O(logn).

union :: Ord a => a -> a -> DisjointSet a -> DisjointSet a

Create an equivalence relation between x and y. If either x or y are not already is the disjoint set, they are first created as singletons.

Query

equivalent :: Ord a => a -> a -> DisjointSet a -> Bool

Decides whether the two values belong to the same set

sets :: DisjointSet a -> Int

Count the number of disjoint sets

values :: DisjointSet a -> Int

Count the total number of values contained by the disjoint sets

representative :: Ord a => a -> DisjointSet a -> Maybe a

Find the set representative for this input.

representative' :: Ord a => a -> DisjointSet a -> (Maybe a, DisjointSet a)

Find the set representative for this input. Returns a new disjoint set in which the path has been compressed.

Conversion

toLists :: Ord a => DisjointSet a -> [[a]]

pretty :: (Ord a, Show a) => DisjointSet a -> String

Tutorial

The disjoint set data structure represents sets that are disjoint. Each set in the data structure can be interpreted as an equivalance class. For example, let us consider a scenario in which we are investigating spies who each use one or more aliases. There are three actions we may repeated take:

1. we learn an alias is in use by someone (make set)
2. we learn two aliases refer to the same individual (union)
3. we check our notes to figure out if two aliases refer to the same individual (find)

We initially learn of the existence of several aliases:

>>> import Data.Function ((&))
>>> import Data.Monoid ((<>))
>>> import Data.Foldable (fold,foldMap)
>>> let s0 = empty
>>> let s1 = s0 & insert "Scar" & insert "Carene" & insert "Barth" & insert "Coral"
>>> let s2 = s1 & insert "Boris" & insert "Esma" & insert "Mayra"
>>> putStr (pretty s2)
{{"Barth"},{"Boris"},{"Carene"},{"Coral"},{"Esma"},{"Mayra"},{"Scar"}}

Note that the Monoid instance gives us a way to construct this more succintly:

>>> s2 == foldMap singleton ["Barth","Boris","Carene","Coral","Esma","Mayra","Scar"]
True

After some preliminary research, we learn that Barth and Esma are the same person. We also learn that Carene and Mayra are the same:

>>> let s3 = s2 & union "Barth" "Esma" & union "Carene" "Mayra"
>>> putStr (pretty s3)
{{"Boris"},{"Coral"},{"Barth","Esma"},{"Carene","Mayra"},{"Scar"}}

Another informant comes forward who tells us they have worked for someone that went by the names Mayra and Esma. Going through old letters, we learn that Boris is a pen name used by Scar:

>>> let s4 = s3 & union "Mayra" "Esma" & union "Boris" "Scar"
>>> putStr (pretty s4)
{{"Coral"},{"Barth","Carene","Esma","Mayra"},{"Boris","Scar"}}

At this point, Detective Laura from another department drops by with questions about a case she is working on. She asks if Boris the same person as Barth and if Carene is the same person as Esma. We answer:

>>> equivalent "Boris" "Barth" s4
False
>>> equivalent "Carene" "Esma" s4
True

The correct way to interpret this is that False means something more along the lines of unknown, but we definitely know that Carene is Esma. Finally, before the detective leaves, she gives us some of her case notes to synthesize with our information. Notice that there are some aliases she encountered that we did not and vice versa:

>>> let laura = union "Scar" "Coral" $ union "Esma" "Henri" $ foldMap singleton ["Carene","Boris","Barth"]
>>> putStr (pretty laura)
{{"Barth"},{"Boris"},{"Carene"},{"Coral","Scar"},{"Esma","Henri"}}
>>> putStr (pretty (laura <> s4))
{{"Barth","Carene","Esma","Henri","Mayra"},{"Boris","Coral","Scar"}}

With Laura's shared findings, we now see that there are really only (at most) two spies that we are dealing with.