Union Find data structure (Python recipe) by Josiah Carlson

ActiveState Code (http://code.activestate.com/recipes/215912/)

For the actual data structure application, it is faster. When counting the number of dictionary lookups (access and insertion), the union-find structure completely annhilliates the straightforward approach when we end up joining every individual set to the one larger set, as is appropriate for kruskal's minimum spanning tree algorithm.

This is because while each operation on the union-find structure is known to be O(inverse_ackerman(n)), each operation using the straightforward approach is O(n).

Even with the C dict.update(), using the union-find structure is FAR faster.

Looks useful. I need a union-find structure for Edmonds' blossom-contraction algorithm for maximum matching in general graphs (unfortunately the graphs I need this for are not bipartite so I can't use my previous recipe) and this looks like a good implementation. I like the way you set up the API to allow arbitrary hashables to take part in the structure.

A few comments, though:

• What is the point of converting objects to numbers and back again? Does the performance gain really outweigh the added code complexity? And if you're going to do that, why do you use the numbers to index into a dict instead of into a list?

• Maybe it would be more pythonic to use __getitem__ instead of find? That is, instead of calling UF.find(x), simply write UF[x] to find the set associated with x, just like other data structures (e.g. dict) use the same notation for other values associated with x? I can't think of a similar neat and understandable syntax for union, though.

• You appear to have mixed up log* and alpha. log*(n) is the minimum height of a tower of powers of 2, 2^(2^(...)) that is at least n. alpha is the inverse of the Ackermann function, which can be defined by several recurrences but not the one you give -- a typical one is

  A(1,x) = 2x A(x,1) = 2 A(x,y) = A(x-1,A(x,y-1))

Although both alpha and log* are incredibly slowly growing, alpha is much slower than log*.

Why convert? More pythonic? - You make a good point about conversions between objects and integers. I used dictionaries purely out of personal preference. While parent pointers make little sense in using dictionaries, keeping a dictionary of child pointers end up helping considerably when I went about implementing the 'delete' operation for the Blossom Contraction algorithm you emailed me about (which is included below). In using dictionaries for child pointers, delete can be ammortized to O(1) per deletion, paid for by earlier union and find operations.

• In terms of being more pythonic, certainly using __getitem__ would be significantly more pythonic, no arguments here. I wrote them in terms of the operations performed on the structure (union, find) because it is explicit. It doesn't make sense to me to make something more pythonic, when it doesn't make sense to UF[x] = y. The addition of delete below, could also has a python equivalent __delitem__, but again, I shy away from using too many accessors when the structure is so different from what is offered in standard python, and doesn't help with understanding the use of the structure.

• My mistake.

  class BlossomContraction: def __init__(self): '''\ Create an empty blossom contraction data structure.''' self.num_weights = {} self.parent_pointers = {} self.num_to_objects = {} self.objects_to_num = {} self.child_pointers = {} self.next = -1 self.setcount = 0 self.__repr__ = self.__str__ def insert_objects(self, objects): '''\ Insert a sequence of objects into the structure. All must be Python hashable.''' for object in objects: self.find(object); def find(self, object): '''\ Find the root of the set that an object is in. If the object was not known, will make it known, and it becomes its own set. Object must be Python hashable.''' if not object in self.objects_to_num: self.next += 1 obj_num = self.next self.num_weights[obj_num] = 1 self.objects_to_num[object] = obj_num self.num_to_objects[obj_num] = object self.parent_pointers[obj_num] = obj_num self.child_pointers[obj_num] = {} self.setcount += 1 return object stk = [self.objects_to_num[object]] par = self.parent_pointers[stk[-1]] while par != stk[-1]: del self.child_pointers[par][stk[-1]] stk.append(par) par = self.parent_pointers[par] for i in xrange(1,len(stk)-1): self.num_weights[stk[i]] -= i par = stk.pop() for i in stk:

(comment continued...)

(...continued from previous comment)

 self.parent_pointers[i] = par self.child_pointers[par][i] = None return self.num_to_objects[par] def union(self, object1, object2): '''\ Combine the sets that contain the two objects given. Both objects must be Python hashable. If either or both objects are unknown, will make them known, and combine them.''' o1p = self.find(object1) o2p = self.find(object2) if o1p != o2p: on1 = self.objects_to_num[o1p] on2 = self.objects_to_num[o2p] w1 = self.num_weights[on1] w2 = self.num_weights[on2] if w2 > w1: o1p, o2p, on1, on2, w1, w2 = o2p, o1p, on2, on1, w2, w1 self.num_weights[on1] = w1+w2 self.parent_pointers[on2] = on1 self.child_pointers[on1][on2] = None self.setcount -= 1 def delete(self, object): '''\ Remove an object from the Blossom Contraction structure. Object does not necessarily need to be a root.''' if not object in self.objects_to_num: return rootn = self.objects_to_num[self.find(object)] objectn = self.objects_to_num[object] #uncomment the following line to require object to be a root. #assert objectn == rootn self.num_weights[rootn] -= self.num_weights[objectn] for child in self.child_pointers[objectn]: self.parent_pointers[child] = child self.setcount += len(self.child_pointers[objectn])-1 del self.parent_pointers[objectn] del self.child_pointers[objectn] del self.num_weights[objectn] del self.num_to_objects[objectn] del self.objects_to_num[object] def __str__(self): '''\ Included for testing purposes only. All information needed from the union find data structure can be attained using find.''' sets = {} for i in self.parent_pointers: if i == self.parent_pointers[i]: sets[i] = [] for i in self.objects_to_num: sets[self.objects_to_num[self.find(i)]].append(i) out = [] for i in sets.itervalues(): out.append(repr(i)) return ', '.join(out) 

Note on blossom contraction... This doesn't actually implement blossom contraction. It implements a related algorithm and structure, but it isn't really useful.

help the needy ;-). All well and fine... but where is the useful recipe, i mean the kruskal algorithm ?

straightforward method buggy. so, i could be wrong here, but i think i'm not, so i thought i'd share... feel free to correct.

hey, maybe the reason the straightforward method wins in timings is that it is fundamentally broken. you have to reset all members of the list to point to the new, larger list, which you don't do...

self.objects[b].update(self.objects[a]) self.objects[a] = self.objects[b] 

these lines are the problem. well, the first is okay, but the second one needs to iterate through the old members of self.objects[a] and set them all to point to the new bigger list.

straightforward method. I have had erroneous results with the straightforward method. It is better to use the original method.