Data.DisjointSet.Int

This module contains non-monadic functions for querying disjoint int sets. See Data.DisjointSet.Int.Monadic for information about how to create and modify disjoint int sets.

There are two other disjoint int set packages on hackage, namely:

• "disjoint-set"
• "disjoint-sets-st"

The first is a pure disjoint int set implementation, so as it doesn't do in place array updates in ST it will presumably be somewhat slower, with the data structure used likely taking more space and having log(n) access speed.

This package does not include a pure implementation, you're better off using "disjoint-set" for that.

"disjoint-sets-st" does offer an implementation in IO, however, it's missing two features:

1) The ability to "freeze" a disjoint set, and then query it in a pure way. 2) Maintaining a circular linked list of each set so one can quickly discover all the elements of one set without quering through the entire structure.

This package implements both of the above features.

Documentation

find :: DisjointIntSet -> Int -> Int

Finds the representative set for that element.

count :: DisjointIntSet -> Int -> Int

Gives how many elements in this element's set.

findAndCount :: DisjointIntSet -> Int -> (Int, Int)

Both find and count, but in one operation, so in theory faster than running them separately.

numSets :: DisjointIntSet -> Int

How many distinct sets.

size :: DisjointIntSet -> Int

How many elements in this disjoint set.

nextInSet :: DisjointIntSet -> Int -> Int

Gets the next element in the current set. This is a circular list, so if you iterate on this you'll get back to the element you started with in the end.

setToList :: DisjointIntSet -> Int -> [Int]

Returns a list of the elements in the selected set.