On 20 Feb 2005 03:31:33 -0800, [EMAIL PROTECTED] wrote:
>John Machin:
>>FWIW, my offering is attached. <
>
>I'm sorry, I don't see the attach... (just the different title).
>
Here it is. I'll reply to the rest tomorrow. It's way past sleep-time
here.
!
!class _Stopper:
! pass
!
!def merge_JM(pairings):
! parent = {}
! link = {}
! size = {}
! # 1. x not in parent => x is unknown
! # 2. parent[x] -> root of cluster containing x
! # 3. As a consequence of (2), parent[root] is root
! # 4. link[x] chains the members of the cluster; 1st is root, 2nd
is link[root], ...
! # 5. link[last_member] is _stopper
! # 6. size[root] is the number of members of the cluster
! parentget = parent.get
! _stopper = _Stopper()
! for inxa, inxb in pairings:
! roota = parentget(inxa, _stopper)
! rootb = parentget(inxb, _stopper)
! if roota is not _stopper:
! if rootb is not _stopper:
! if roota is rootb:
! continue
! if size[rootb] > size[roota]:
! newroot = rootb
! joiner = roota
! else:
! newroot = roota
! joiner = rootb
! size[newroot] += size[joiner]
! del size[joiner]
! parent[joiner] = newroot
! tail = joiner
! while link[tail] is not _stopper:
! tail = link[tail]
! parent[tail] = newroot
! link[tail] = link[newroot]
! link[newroot] = joiner
! else:
! size[roota] += 1
! parent[inxb] = roota
! link[inxb] = link[roota]
! link[roota] = inxb
! else:
! if rootb is not _stopper:
! size[rootb] += 1
! parent[inxa] = rootb
! link[inxa] = link[rootb]
! link[rootb] = inxa
! elif inxa is inxb:
! parent[inxa] = inxa
! link[inxa] = _stopper
! size[inxa] = 1
! else:
! parent[inxa] = inxa
! parent[inxb] = inxa
! link[inxa] = inxb
! link[inxb] = _stopper
! size[inxa] = 2
! olist = []
! for root in size.iterkeys():
! family = [root]
! cousin = link[root]
! while cousin is not _stopper:
! family.append(cousin)
! cousin = link[cousin]
! olist.append(family)
! return olist
!
--
http://mail.python.org/mailman/listinfo/python-list
