Disjoint sets data type: applications

Disjoint sets data type: applications 29
OscarTucker Profile Pic
OscarTucker,Singapore,Professional
Published Date:19-07-2017
Your Website URL(Optional)
Comment
UNION-FIND union by size ‣ link-by-rank ‣ path compression ‣ link-by-rank with path compression ‣ context ‣ Lecture slides by Kevin Wayne Copyright © 2005 Pearson-Addison Wesley Copyright © 2013 Kevin Wayne http://www.cs.princeton.edu/wayne/kleinberg-tardos Last updated on Sep 8, 2013 7:01 AMDisjoint sets data type Goal. Support two operations on a set of elements: MAKE-SET(x). Create a new set containing only element x. FIND(x). Return a canonical element in the set containing x. UNION(x, y). Merge the sets containing x and y. Dynamic connectivity. Given an initial empty graph G on n nodes, support the following queries: 1 union operation ADD-EDGE(u, v). Add an edge between nodes u and v. IS-CONNECTED(u, v). Is there a path between u and v? 2 find operations 2Disjoint sets data type: applications Original motivation. Compiling EQUIVALENCE, DIMENSION, and COMMON statements in Fortran. other EQUIVALENCE declaration). We must exhibit An Improved Equivalence an algorithm which will result in a storage assignment for each variable and array occurring in any EQUIVALENCE Algorithm statement. Of course, the groups may be highly linked, such as in the BERNARD A. GALLER AND MICHAEL J. FISHER following statement. University of Michigan, Ann Arbor, Michigan EQUIVALENCE (X, Y2 ), (Q, J, K), (Y3, Z1 ), (U, V), (Y, Q), (U3, M10, N) (2) An algorithm for assigning storage on the basis of EQUIV- ALENCE, DIMENSION and COMMON declarations is pre- We shall use this example to illustrate the algorithm sented. The algorithm is based on a tree structure, and has presented here. Assume that K has been assigned to loca- reduced computation time by 40 percent over a previously tion 100 by some other declaration and that the dimensions published algorithm by identifying all equivalence classes of Y, Z, M and U are 10, 4, 12 and 5, respectively. (In with one scan of the EQUIVALENCE declarations. The method other words, since the zero subscript is allowed here, is applicable in any problem in which it is necessary to identify the highest subscripts occurring for Y, Z, M and U are equivalence classes, given the element pairs defining the 9, 3, 11 and 4, respectively.) There is no loss in generality equivalence relation. if we assume (and we do) that every other variable is also an array of dimension 1. An algorithm for the assignment of storage on the basis The algorithm has as input a collection of n groups of the EQUIVALENCE declaration found in such lan- of subscripted array names. We shall call the groups guages as FORTRAN and MAD was presented in 1. The G1, "", Gn, and for the group Gi, we shall label the algorithm given here, which uses a tree structure, is a mi array names gil, gi2, • • • , gimi • Associated with each considerable improvement over the previous one, and array name glj will be its subscript s(gii) and its dimen- the two algorithms furnish a clear-cut example of the sion d(gii). It will be convenient to use five auxiliary ben:fits which can be realized through the use of such Note. This 1964 paper also introduced key data structure for problem. vectors, called the E, R, S, H, and H' vectors, respectively. metkods. (Comparison tests have shown that the new These vectors must be large enough to hold all distinct method reduces the execution time of the algorithm by as array names appearing in the EQUIVALENCE state- 3 much as 40 percent.) The notation and statement of the ments. The number of entries in the E-vector will be problem have been made as similar to that of 1 as possible to facilitate comparison, and is reviewed here for com- • " = • pleteness. Figure 1 shows a general equivalence algorithm, suitable for identification of equivalence classes in any context. Figures 2 and 3 use this same algorithm for the address assignment problem considered in 1, retaining additional information (D, d, do, R, H and H') during the con- F struction of the trees to facilitate the address assignment at the end. The problem may then be stated as follows: In some t = i T algebraic (or any other) languages, one may write EQUIV- ALEIXCE declarations of the form: EQUIVALENCE (X, Y, Zi), (Z, Ws), (V, V) (1) where the entries consist of names of variables, subscripted array names or unsubscripted array names (which are assumed to represent the element of the array which has subscript zero). Some of the variables or arrays which occur here may have already been assigned to specific locations in storage; others have not yet been assigned. The entries are grouped by means of parentheses, the groups being separated by commas. For example, state- ment (1) would assign X, Y and Z1 to the same location, then Z( Z0) and W5 to another location, and U and V to yet another location (unless either U or V is made ¢5 equivalent to one of the other variables or arrays by some Presented at the ACM National Conference, Denver, Colorado, 1963. Fm. 1 Volume 7 / Number 5 / May, 1964 Communications of the ACM 301 Disjoint sets data type: applications Applications. Percolation. Kruskal's algorithm. Connected components. Computing LCAs in trees. Computing dominators in digraphs. Equivalence of finite state automata. Checking flow graphs for reducibility. Hoshen-Kopelman algorithm in physics. Hinley-Milner polymorphic type inference. Morphological attribute openings and closings. Matlab's BW-LABEL() function for image processing. Compiling EQUIVALENCE, DIMENSION and COMMON statements in Fortran. ... 4UNION-FIND link-by-size ‣ link-by-rank ‣ path compression ‣ link-by-rank with path compression ‣ context ‣ SECTION 4.6Disjoint-sets data structure Representation. Represent each set as a tree of elements. Each element has a parent pointer in the tree. The root serves as the canonical element. FIND(x). Find the root of the tree containing x. UNION(x, y). Make the root of one tree point to root of other tree. root 4 6 3 8 9 0 2 5 1 7 parent of 1 is 2 Note. For brevity, we suppress arrows and self loops in figures. 6Link-by-size Link-by-size. Maintain a subtree count for each node, initially 1. Link root of smaller tree to root of larger tree (breaking ties arbitrarily). union(7, 3) size = 4 size = 6 4 6 3 8 9 0 2 5 1 7Link-by-size Link-by-size. Maintain a subtree count for each node, initially 1. Link root of smaller tree to root of larger tree (breaking ties arbitrarily). union(7, 3) size = 10 6 4 0 2 5 3 8 9 1 7Link-by-size Link-by-size. Maintain a subtree count for each node, initially 1. Link root of smaller tree to root of larger tree (breaking ties arbitrarily). UNION-BY-SIZE (x, y) ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ MAKE-SET (x) r ← FIND (x). ___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ s ← FIND (y). parent(x) ← x. size(x) ← 1. IF (r = s) RETURN. ___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ ELSE IF (size(r) size(s)) parent(s) ← r. FIND (x) size(r) ← size(r) + size(s). ___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ ELSE WHILE (x ≠ parent(x)) x ← parent(x). parent(r) ← s. size(s) ← size(r) + size(s). RETURN x. ___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ 9Link-by-size: analysis height(r) Property. Using link-by-size, for every root node r, size(r) ≥ 2 . Pf. by induction on number of links Base case: singleton tree has size 1 and height 0. Inductive hypothesis: assume true after first i links. Tree rooted at r changes only when a smaller tree rooted at s is linked into r. size'(r) ≥ size(r) Case 1. height(r) height(s) height(r) inductive hypothesis ≥ 2 height'(r) 2 . = size = 8 (height = 2) r size = 3 (height = 1) s 10Link-by-size: analysis height(r) Property. Using link-by-size, for every root node r, size(r) ≥ 2 . Pf. by induction on number of links Base case: singleton tree has size 1 and height 0. Inductive hypothesis: assume true after first i links. Tree rooted at r changes only when a smaller tree rooted at s is linked into r. size'(r) size(r) + size(s) Case 2. height(r) ≤ height(s) = link-by-size ≥ 2 size(s) height(s) inductive hypothesis 2 ⋅ 2 ≥ size = 6 height(s) + 1 2 (height = 1) = r height'(r) size = 3 2 . ▪ = (height = 2) s 11Link-by-size: analysis Theorem. Using link-by-size, any UNION or FIND operations takes O(log n) time in the worst case, where n is the number of elements. Pf. The running time of each operation is bounded by the tree height. By the previous property, the height is ≤ ⎣lg n⎦. ▪ lg n = log n 2 12A matching lower bound Theorem. Using link-by-size, a tree with n nodes can have height = lg n. Pf. k Arrange 2 – 1 calls to UNION to form a binomial tree of order k. k An order-k binomial tree has 2 nodes and height k. ▪ B B B B B 0 1 2 3 4 13UNION-FIND link-by-size ‣ link-by-rank ‣ path compression ‣ link-by-rank with path compression ‣ context ‣ SECTION 5.1.4Link-by-rank Link-by-rank. Maintain an integer rank for each node, initially 0. Link root of smaller rank to root of larger rank; if tie, increase rank of new root by 1. union(7, 3) rank = 1 rank = 2 4 6 3 8 9 0 2 5 1 7 Note. For now, rank = height.Link-by-rank Link-by-rank. Maintain an integer rank for each node, initially 0. Link root of smaller rank to root of larger rank; if tie, increase rank of new root by 1. rank = 2 6 4 0 2 5 3 8 9 1 7 Note. For now, rank = height.Link-by-rank Link-by-rank. Maintain an integer rank for each node, initially 0. Link root of smaller rank to root of larger rank; if tie, increase rank of new root by 1. MAKE-SET (x) UNION-BY-RANK (x, y) ___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ parent(x) ← x. r ← FIND (x). rank(x) ← 0. s ← FIND (y). ___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ IF (r = s) RETURN. ELSE IF rank(r) rank(s) parent(s) ← r. ELSE IF rank(r) rank(s) FIND (x) parent(r) ← s. ___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ WHILE x ≠ parent(x) ELSE x ← parent(x). parent(r) ← s. RETURN x. rank(s) ← rank(s) + 1. ___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ 17Link-by-rank: properties Property 1. If x is not a root node, then rank(x) rank(parent(x)). Pf. A node of rank k is created only by merging two roots of rank k – 1. ▪ Property 2. If x is not a root, then rank(x) will never change again. Pf. Rank changes only for roots; a nonroot never becomes a root. ▪ Property 3. If parent(x) changes, then rank(parent(x)) strictly increases. Pf. The parent can change only for a root, so before linking parent(x) = x ; After x is linked-by-rank to new root r we have rank(r) rank(x). ▪ rank = 3 rank = 2 rank = 1 rank = 0 18Link-by-rank: properties k Property 4. Any root node of rank k has ≥ 2 nodes in its tree. Pf. by induction on k Base case: true for k = 0. Inductive hypothesis: assume true for k – 1. A node of rank k is created only by merging two roots of rank k – 1. k – 1 By inductive hypothesis, each subtree has ≥ 2 nodes k ⇒ resulting tree has ≥ 2 nodes. ▪ Property 5. The highest rank of a node is ≤ ⎣lg n⎦. Pf. Immediate from PROPERTY 1 and PROPERTY 4. ▪ rank = 2 (8 nodes) rank = 2 (4 nodes) 19Link-by-rank: properties r Property 6. For any integer r ≥ 0, there are ≤ n / 2 nodes with rank r. Pf. k Any root node of rank k has ≥ 2 descendants. PROPERTY 4 k Any nonroot node of rank k has ≥ 2 descendants because: it had this property just before it became a nonroot PROPERTY 4 its rank doesn't change once it becomes a nonroot PROPERTY 2 its set of descendants doesn't change once it became a nonroot Different nodes of rank k can't have common descendants. PROPERTY 1 ▪ rank = 4 (1 node) rank = 3 (1 node) rank = 2 (2 nodes) rank = 1 (5 nodes) rank = 0 (11 nodes) 20