[MINC-development] beta mincmorph

[Andrew Janke]

On Wed, 4 Dec 2002, Steve ROBBINS wrote:

> No, more like http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic24/
>
> Cormen, Leiserson & Rivest have a fantastic discussion about this topic in the
> chapter "Data Structures for Disjoint Sets".

ah, I see.  This would appear to be the bee's knees.

> > At then end I assume this tree would be then traversed (depth first) and the
> > top value assigned to each value in the tree?
>
> Each group is represented by a tree in the forest.  You find out which group
> you are in by traversing parent pointers until you get to the root.  The
> root's parent points to itself.
>
> When you use path compression and union-by-rank, the set operations ("union"
> and "find-set") become really really fast: amortized constant time,
> essentially.

If you can manage to read the code this is essentially what I do (without
knowwing it).  I assume this approach also attempts to always assign the lowest
label to a new element?

ie:  this sequence of equivalences is not only possible but common in CCL.

  3 -> 1

  4 -> 3

  4 -> 1

  3 -> 4

  3 -> 1

In which case I think the rule should be to only point larger elments to smaller
ones. Of course if you strike a new equivalence for a node in which a
equivalence already exists you must traverse this equivalence to it's lowest
common denomiator yes?

This is essentially what I do.  Perhaps the code would be more readable if I
implemented such a library though.. :)

However it get's a little more complex as during the re-labelling process
counters of group sizes must also be aggregated and then groups re-labelled
(again) WRT size.  Hrm, as I said before I'm sure there is a more efficient (and
memory stable) way of doing such things than my current implementation but my
brain was beginning to bend so I got lazy at the expense of a few CPU cycles.
:)



--
Andrew Janke   ( rotor@cmr.uq.edu.au || www.cmr.uq.edu.au/~rotor )
Australia->University of Queensland->Centre for Magnetic Resonance
Work: +61 7 3365 4100 || Home: +61 7 3800 4042