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 add(self
, object, weight
):
33 if object not in self
.parents
:
34 self
.parents
[object] = object
35 self
.weights
[object] = weight
37 def __contains__(self
, object):
38 return object in self
.parents
40 def __getitem__(self
, object):
41 """Find and return the name of the set containing the object."""
43 # check for previously unknown object
44 if object not in self
.parents
:
46 self
.parents
[object] = object
47 self
.weights
[object] = 1
50 # find path of objects leading to the root
52 root
= self
.parents
[object]
53 while root
!= path
[-1]:
55 root
= self
.parents
[root
]
57 # compress the path and return
59 self
.parents
[ancestor
] = root
63 """Iterate through all items ever found or unioned by this structure.
66 return iter(self
.parents
)
68 def union(self
, *objects
):
69 """Find the sets containing the objects and merge them all."""
70 roots
= [self
[x
] for x
in objects
]
71 heaviest
= max([(self
.weights
[r
], r
) for r
in roots
])[1]
74 self
.parents
[r
] = heaviest