3 Union-find data structure. Based on Josiah Carlson's code,
4 http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
5 with significant additional changes by D. Eppstein.
11 """Union-find data structure.
13 Each unionFind instance X maintains a family of disjoint sets of
14 hashable objects, supporting the following two methods:
16 - X[item] returns a name for the set containing the given item.
17 Each set is named by an arbitrarily-chosen one of its members; as
18 long as the set remains unchanged it will keep the same name. If
19 the item is not yet part of a set in X, a new singleton set is
22 - X.union(item1, item2, ...) merges the sets containing each item
23 into a single larger set. If any item is not yet part of a set
24 in X, it is added to X as one of the members of the merged set.
28 """Create a new empty union-find structure."""
32 def __getitem__(self
, object):
33 """Find and return the name of the set containing the object."""
35 # check for previously unknown object
36 if object not in self
.parents
:
37 self
.parents
[object] = object
38 self
.weights
[object] = 1
41 # find path of objects leading to the root
43 root
= self
.parents
[object]
44 while root
!= path
[-1]:
46 root
= self
.parents
[root
]
48 # compress the path and return
50 self
.parents
[ancestor
] = root
54 """Iterate through all items ever found or unioned by this structure.
57 return iter(self
.parents
)
59 def union(self
, *objects
):
60 """Find the sets containing the objects and merge them all."""
61 roots
= [self
[x
] for x
in objects
]
62 heaviest
= max([(self
.weights
[r
], r
) for r
in roots
])[1]
65 self
.weights
[heaviest
] += self
.weights
[r
]
66 self
.parents
[r
] = heaviest