1struct::disjointset(n) Tcl Data Structures struct::disjointset(n)
2______________________________________________________________________________
6
8 struct::disjointset - Disjoint set data structure
9
11 package require Tcl 8.6
12 package require struct::disjointset ?1.1?
14 ::struct::disjointset disjointsetName
16 disjointsetName option ?arg arg ...?
18 disjointsetName add-element item
20 disjointsetName add-partition elements
22 disjointsetName partitions
24 disjointsetName num-partitions
26 disjointsetName equal a b
28 disjointsetName merge a b
30 disjointsetName find e
32 disjointsetName exemplars
34 disjointsetName find-exemplar e
36 disjointsetName destroy
38______________________________________________________________________________
40
42 This package provides disjoint sets. An alternative name for this kind
43 of structure is merge-find.
44 Normally when dealing with sets and their elements the question is "Is
46 this element E contained in this set S?", with both E and S known.
47 Here the question is "Which of several sets contains the element E?".
49 I.e. while the element is known, the set is not, and we wish to find it
50 quickly. It is not quite the inverse of the original question, but
51 close. Another operation which is often wanted is that of quickly
52 merging two sets into one, with the result still fast for finding ele‐
53 ments. Hence the alternative term merge-find for this.
54 Why now is this named a disjoint-set ? Because another way of describ‐
56 ing the whole situation is that we have
57 • a finite set S, containing
59 • a number of elements E, split into
61 • a set of partitions P. The latter term applies, because the in‐
63 tersection of each pair P, P' of partitions is empty, with the
64 union of all partitions covering the whole set.
65 • An alternative name for the partitions would be equvalence
67 classes, and all elements in the same class are considered as
68 equal.
69 Here is a pictorial representation of the concepts listed above:
71 +-----------------+ The outer lines are the boundaries of the set S.
74 | / | The inner regions delineated by the skewed lines
75 | * / * | are the partitions P. The *'s denote the elements
76 | * / \ | E in the set, each in a single partition, their
77 |* / \ | equivalence class.
78 | / * \ |
79 | / * / |
80 | * /\ * / |
81 | / \ / |
82 | / \/ * |
83 | / * \ |
84 | / * \ |
85 +-----------------+
86 For more information see http://en.wikipedia.org/wiki/Dis‐
89 joint_set_data_structure.
90
92 The package exports a single command, ::struct::disjointset. All func‐
93 tionality provided here can be reached through a subcommand of this
94 command.
95 ::struct::disjointset disjointsetName
97 Creates a new disjoint set object with an associated global Tcl
98 command whose name is disjointsetName. This command may be used
99 to invoke various operations on the disjointset. It has the fol‐
100 lowing general form:
101 disjointsetName option ?arg arg ...?
103 The option and the args determine the exact behavior of
104 the command. The following commands are possible for dis‐
105 jointset objects:
106 disjointsetName add-element item
108 Creates a new partition in the specified disjoint set, and fills
109 it with the single item item. The command maintains the integ‐
110 rity of the disjoint set, i.e. it verifies that none of the ele‐
111 ments are already part of the disjoint set and throws an error
112 otherwise.
113 The result of this method is the empty string.
115 This method runs in constant time.
117 disjointsetName add-partition elements
119 Creates a new partition in specified disjoint set, and fills it
120 with the values found in the set of elements. The command main‐
121 tains the integrity of the disjoint set, i.e. it verifies that
122 none of the elements are already part of the disjoint set and
123 throws an error otherwise.
124 The result of the command is the empty string.
126 This method runs in time proportional to the size of elements].
128 disjointsetName partitions
130 Returns the set of partitions the named disjoint set currently
131 consists of. The form of the result is a list of lists; the in‐
132 ner lists contain the elements of the partitions.
133 This method runs in time O(N*alpha(N)), where N is the number of
135 elements in the disjoint set and alpha is the inverse Ackermann
136 function.
137 disjointsetName num-partitions
139 Returns the number of partitions the named disjoint set cur‐
140 rently consists of.
141 This method runs in constant time.
143 disjointsetName equal a b
145 Determines if the two elements a and b of the disjoint set be‐
146 long to the same partition. The result of the method is a bool‐
147 ean value, True if the two elements are contained in the same
148 partition, and False otherwise.
149 An error will be thrown if either a or b are not elements of the
151 disjoint set.
152 This method runs in amortized time O(alpha(N)), where N is the
154 number of elements in the larger partition and alpha is the in‐
155 verse Ackermann function.
156 disjointsetName merge a b
158 Determines the partitions the elements a and b are contained in
159 and merges them into a single partition. If the two elements
160 were already contained in the same partition nothing will
161 change.
162 The result of the method is the empty string.
164 This method runs in amortized time O(alpha(N)), where N is the
166 number of items in the larger of the partitions being merged.
167 The worst case time is O(N).
168 disjointsetName find e
170 Returns a list of the members of the partition of the disjoint
171 set which contains the element e.
172 This method runs in O(N*alpha(N)) time, where N is the total
174 number of items in the disjoint set and alpha is the inverse
175 Ackermann function, See find-exemplar for a faster method, if
176 all that is needed is a unique identifier for the partition,
177 rather than an enumeration of all its elements.
178 disjointsetName exemplars
180 Returns a list containing an exemplar of each partition in the
181 disjoint set. The exemplar is a member of the partition, chosen
182 arbitrarily.
183 This method runs in O(N*alpha(N)) time, where N is the total
185 number of items in the disjoint set and alpha is the inverse
186 Ackermann function.
187 disjointsetName find-exemplar e
189 Returns the exemplar of the partition of the disjoint set con‐
190 taining the element e. Throws an error if e is not found in the
191 disjoint set. The exemplar is an arbitrarily chosen member of
192 the partition. The only operation that will change the exemplar
193 of any partition is merge.
194 This method runs in O(alpha(N)) time, where N is the number of
196 items in the partition containing E, and alpha is the inverse
197 Ackermann function.
198 disjointsetName destroy
200 Destroys the disjoint set object and all associated memory.
201
203 This document, and the package it describes, will undoubtedly contain
204 bugs and other problems. Please report such in the category struct ::
205 disjointset of the Tcllib Trackers [http://core.tcl.tk/tcllib/re‐
206 portlist]. Please also report any ideas for enhancements you may have
207 for either package and/or documentation.
208 When proposing code changes, please provide unified diffs, i.e the out‐
210 put of diff -u.
211 Note further that attachments are strongly preferred over inlined
213 patches. Attachments can be made by going to the Edit form of the
214 ticket immediately after its creation, and then using the left-most
215 button in the secondary navigation bar.
216
218 disjoint set, equivalence class, find, merge find, partition, parti‐
219 tioned set, union
220
222 Data structures
223tcllib 1.1 struct::disjointset(n)