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.
67 | / | The inner regions delineated by the skewed lines
68 | * / * | are the partitions P. The *'s denote the elements
69 | * / \ | E in the set, each in a single partition, their
70 |* / \ | equivalence class.
71 | / * \ |
72 | / * / |
73 | * /\ * / |
74 | / \ / |
75 | / \/ * |
76 | / * \ |
77 | / * \ |
78 +-----------------+
79 For more information see http://en.wikipedia.org/wiki/Dis‐
82 joint_set_data_structure.
83
85 The package exports a single command, ::struct::disjointset. All func‐
86 tionality provided here can be reached through a subcommand of this
87 command.
88 ::struct::disjointset disjointsetName
90 Creates a new disjoint set object with an associated global Tcl
91 command whose name is disjointsetName. This command may be used
92 to invoke various operations on the disjointset. It has the fol‐
93 lowing general form:
94 disjointsetName option ?arg arg ...?
96 The option and the args determine the exact behavior of
97 the command. The following commands are possible for dis‐
98 jointset objects:
99 disjointsetName add-partition elements
101 Creates a new partition in specified disjoint set, and fills it
102 with the values found in the set of elements. The command main‐
103 tains the integrity of the disjoint set, i.e. it verifies that
104 none of the elements are already part of the disjoint set and
105 throws an error otherwise.
106 The result of the command is the empty string.
108 disjointsetName partitions
110 Returns the set of partitions the named disjoint set currently
111 consists of.
112 disjointsetName num-partitions
114 Returns the number of partitions the named disjoint set cur‐
115 rently consists of.
116 disjointsetName equal a b
118 Determines if the two elements a and b of the disjoint set
119 belong to the same partition. The result of the method is a
120 boolean value, True if the two elements are contained in the
121 same partition, and False otherwise.
122 An error will be thrown if either a or b are not elements of the
124 disjoint set.
125 disjointsetName merge a b
127 Determines the partitions the elements a and b are contained in
128 and merges them into a single partition. If the two elements
129 were already contained in the same partition nothing will
130 change.
131 The result of the method is the empty string.
133 disjointsetName find e
135 Returns the partition of the disjoint set which contains the
136 element e.
137 disjointsetName destroy
139 Destroys the disjoint set object and all associated memory.
140
142 This document, and the package it describes, will undoubtedly contain
143 bugs and other problems. Please report such in the category struct ::
144 disjointset of the Tcllib SF Trackers [http://source‐
145 forge.net/tracker/?group_id=12883]. Please also report any ideas for
146 enhancements you may have for either package and/or documentation.
147
149 disjoint set, equivalence class, find, merge find, partition, parti‐
150 tioned set, union
151struct 1.0 struct::disjointset(n)