1struct::disjointset(n) Tcl Data Structures struct::disjointset(n)
2______________________________________________________________________________
6
8 struct::disjointset - Disjoint set data structure
9
11 package require Tcl 8.4
12 package require struct::disjointset ?1.0?
14 ::struct::disjointset disjointsetName
16 disjointsetName option ?arg arg ...?
18 disjointsetName add-partition elements
20 disjointsetName partitions
22 disjointsetName num-partitions
24 disjointsetName equal a b
26 disjointsetName merge a b
28 disjointsetName find e
30 disjointsetName destroy
32______________________________________________________________________________
34
36 This package provides disjoint sets. An alternative name for this kind
37 of structure is merge-find.
38 Normally when dealing with sets and their elements the question is "Is
40 this element E contained in this set S?", with both E and S known.
41 Here the question is "Which of several sets contains the element E?".
43 I.e. while the element is known, the set is not, and we wish to find it
44 quickly. It is not quite the inverse of the original question, but
45 close. Another operation which is often wanted is that of quickly
46 merging two sets into one, with the result still fast for finding ele‐
47 ments. Hence the alternative term merge-find for this.
48 Why now is this named a disjoint-set ? Because another way of describ‐
50 ing the whole situation is that we have
51 · a finite set S, containing
53 · a number of elements E, split into
55 · a set of partitions P. The latter term applies, because the
57 intersection of each pair P, P' of partitions is empty, with the
58 union of all partitions covering the whole set.
59 · An alternative name for the partitions would be equvalence
61 classes, and all elements in the same class are considered as
62 equal.
63 Here is a pictorial representation of the concepts listed above:
65 +-----------------+ The outer lines are the boundaries of the set S.
68 | / | The inner regions delineated by the skewed lines
69 | * / * | are the partitions P. The *'s denote the elements
70 | * / \ | E in the set, each in a single partition, their
71 |* / \ | equivalence class.
72 | / * \ |
73 | / * / |
74 | * /\ * / |
75 | / \ / |
76 | / \/ * |
77 | / * \ |
78 | / * \ |
79 +-----------------+
80 For more information see http://en.wikipedia.org/wiki/Dis‐
83 joint_set_data_structure.
84
86 The package exports a single command, ::struct::disjointset. All func‐
87 tionality provided here can be reached through a subcommand of this
88 command.
89 ::struct::disjointset disjointsetName
91 Creates a new disjoint set object with an associated global Tcl
92 command whose name is disjointsetName. This command may be used
93 to invoke various operations on the disjointset. It has the fol‐
94 lowing general form:
95 disjointsetName option ?arg arg ...?
97 The option and the args determine the exact behavior of
98 the command. The following commands are possible for dis‐
99 jointset objects:
100 disjointsetName add-partition elements
102 Creates a new partition in specified disjoint set, and fills it
103 with the values found in the set of elements. The command main‐
104 tains the integrity of the disjoint set, i.e. it verifies that
105 none of the elements are already part of the disjoint set and
106 throws an error otherwise.
107 The result of the command is the empty string.
109 disjointsetName partitions
111 Returns the set of partitions the named disjoint set currently
112 consists of.
113 disjointsetName num-partitions
115 Returns the number of partitions the named disjoint set cur‐
116 rently consists of.
117 disjointsetName equal a b
119 Determines if the two elements a and b of the disjoint set
120 belong to the same partition. The result of the method is a
121 boolean value, True if the two elements are contained in the
122 same partition, and False otherwise.
123 An error will be thrown if either a or b are not elements of the
125 disjoint set.
126 disjointsetName merge a b
128 Determines the partitions the elements a and b are contained in
129 and merges them into a single partition. If the two elements
130 were already contained in the same partition nothing will
131 change.
132 The result of the method is the empty string.
134 disjointsetName find e
136 Returns the partition of the disjoint set which contains the
137 element e.
138 disjointsetName destroy
140 Destroys the disjoint set object and all associated memory.
141
143 This document, and the package it describes, will undoubtedly contain
144 bugs and other problems. Please report such in the category struct ::
145 disjointset of the Tcllib Trackers
146 [http://core.tcl.tk/tcllib/reportlist]. Please also report any ideas
147 for enhancements you may have for either package and/or documentation.
148 When proposing code changes, please provide unified diffs, i.e the out‐
150 put of diff -u.
151 Note further that attachments are strongly preferred over inlined
153 patches. Attachments can be made by going to the Edit form of the
154 ticket immediately after its creation, and then using the left-most
155 button in the secondary navigation bar.
156
158 disjoint set, equivalence class, find, merge find, partition, parti‐
159 tioned set, union
160
162 Data structures
163tcllib 1.0 struct::disjointset(n)