I have a UNION-FIND data structure and implementation for disjoint
sets operations ready to be inserted in the CLOCC. However, I am not
that happy about the API I came up with.
The implementation follows the description in Cormen Leiserson and
Rivest (ppgg. 446). The interface I came up with is
o MAKE-SET x
creates a singleton "set" with only X in it.
o UNION x y
this is the union operation between two "sets".
o FIND-SET-REP x
this finds the "set" which contains the "set" X (set
containment is the result of UNIONs).
o FIND-SET x
finds the "set" of which X is a member.
o COLLECT-SET x
collects into a list the items in "set" X.
o PRINT-SET x
collects into a list the items in "set" X and then prints it.
I am not sure this is the best interface and would like some feedback.
In particular, right now, MAKE-SET actually stashes everything in a
large hash-table. How about adding a new layer to the API by
introducing the notion of "domain" where the disjoint sets are
actually maintained? The interface of MAKE-SET would become
MAKE-SET domain x
Operations like CLEAR-DOMAIN could then be introduced more easily.
Note that UNION-FIND structures are very useful for a large number of
Marco Antoniotti =============================================================
NYU Bioinformatics Group tel. +1 - 212 - 998 3488
719 Broadway 12th Floor fax +1 - 212 - 995 4122
New York, NY 10003, USA http://galt.mrl.nyu.edu/valis
Like DNA, such a language [Lisp] does not go out of style.
Paul Graham, ANSI Common Lisp