struct::disjointset(3tcl) | Tcl Data Structures | struct::disjointset(3tcl) |
struct::disjointset - Disjoint set data structure
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
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.
The package exports a single command, ::struct::disjointset. All functionality provided here can be reached through a subcommand of this command.
The result of this method is the empty string.
This method runs in constant time.
The result of the command is the empty string.
This method runs in time proportional to the size of elements].
This method runs in time O(N*alpha(N)), where N is the number of elements in the disjoint set and alpha is the inverse Ackermann function.
This method runs in constant time.
An error will be thrown if either a or b are not elements of the disjoint set.
This method runs in amortized time O(alpha(N)), where N is the number of elements in the larger partition and alpha is the inverse Ackermann function.
The result of the method is the empty string.
This method runs in amortized time O(alpha(N)), where N is the number of items in the larger of the partitions being merged. The worst case time is O(N).
This method runs in O(N*alpha(N)) time, where N is the total number of items in the disjoint set and alpha is the inverse Ackermann function, See find-exemplar for a faster method, if all that is needed is a unique identifier for the partition, rather than an enumeration of all its elements.
This method runs in O(N*alpha(N)) time, where N is the total number of items in the disjoint set and alpha is the inverse Ackermann function.
This method runs in O(alpha(N)) time, where N is the number of items in the partition containing E, and alpha is the inverse Ackermann function.
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 [http://core.tcl.tk/tcllib/reportlist]. 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.
disjoint set, equivalence class, find, merge find, partition, partitioned set, union
Data structures
1.1 | tcllib |