Tcl Library Source Code

Documentation
Login


[ Main Table Of Contents | Table Of Contents | Keyword Index | Categories | Modules | Applications ]

NAME

struct::disjointset - Disjoint set data structure

Table Of Contents

SYNOPSIS

package require Tcl 8.6
package require struct::disjointset ?1.1?

::struct::disjointset disjointsetName
disjointsetName option ?arg arg ...?
disjointsetName add-element item
disjointsetName add-partition elements
disjointsetName partitions
disjointsetName num-partitions
disjointsetName equal a b
disjointsetName merge a b
disjointsetName find e
disjointsetName exemplars
disjointsetName find-exemplar e
disjointsetName destroy

DESCRIPTION

This package provides disjoint sets. An alternative name for this kind of structure is merge-find.

Normally when dealing with sets and their elements the question is "Is this element E contained in this set S?", with both E and S known.

Here the question is "Which of several sets contains the element E?". I.e. while the element is known, the set is not, and we wish to find it quickly. It is not quite the inverse of the original question, but close. Another operation which is often wanted is that of quickly merging two sets into one, with the result still fast for finding elements. Hence the alternative term merge-find for this.

Why now is this named a disjoint-set ? Because another way of describing the whole situation is that we have

Here is a pictorial representation of the concepts listed above:

+-----------------+ The outer lines are the boundaries of the set S.
|           /     | The inner regions delineated by the skewed lines
|  *       /   *  | are the partitions P. The *'s denote the elements
|      *  / \     | E in the set, each in a single partition, their
|*       /   \    | equivalence class.
|       /  *  \   |
|      / *   /    |
| *   /\  * /     |
|    /  \  /      |
|   /    \/  *    |
|  / *    \       |
| /     *  \      |
+-----------------+

For more information see http://en.wikipedia.org/wiki/Disjoint_set_data_structure.

API

The package exports a single command, ::struct::disjointset. All functionality provided here can be reached through a subcommand of this command.

Bugs, Ideas, Feedback

This document, and the package it describes, will undoubtedly contain bugs and other problems. Please report such in the category struct :: disjointset of the Tcllib Trackers. Please also report any ideas for enhancements you may have for either package and/or documentation.

When proposing code changes, please provide unified diffs, i.e the output of diff -u.

Note further that attachments are strongly preferred over inlined patches. Attachments can be made by going to the Edit form of the ticket immediately after its creation, and then using the left-most button in the secondary navigation bar.

KEYWORDS

disjoint set, equivalence class, find, merge find, partition, partitioned set, union

CATEGORY

Data structures