A Graphical Union-Find Implementation
by Rory L. P. McGuire
- Only works with the latest Sun Java plugin.
- Accepts string input with 1 or more characters.
- The first input field must be filled for "Make Set" and
"Find Set". Both fields must be filled for "Union".
- Intermediate steps are displayed with nodes of interest
highlighted in red.
- 100% speed will suppress display of intermediate steps.
- If "Union by Rank" is enabled, unifying two sets will result
in the shallowest set. That is, the shallower set will be
merged into the deeper set. Enabling this option will also
display each node's rank in green.
- If "Path Compression" is enabled, finding a the
representative for a set will result in all nodes along the find
path being set as direct children of the representative. When
unifying, this setting may cause "Union by Rank" to not work,
since ranks are not changed as part of path compression.
- "Extended Path Compression" will compress nodes found as
part of of a unification to direct children of the new
representative. Please note that this is not part of the
algorithm found in the text listed below.
- The algorithm (for "Disjoint Set" operations) can be found
in:
Cormen, Leiserson, Rivest, Stein: Introduction to
Algorithms, Second Edition
MIT Press, Cambridge,
Massachusetts / McGraw-Hill Books; 2002
ISBN: 0-07-013151-1
- Special thanks to Professor Cris Moore, who allowed me
to pursue this project as a part of an independent study.
- Thanks also to my 'beta' testers: Akita Bright-Holloway,
Marshall Daniels, Joseph Koprivnikar, Breanna Ammons, Ryan
Chapman, James Beck, Colin Green, Galen Shipman, Louis Vogel,
Marlow Weston, and Bobby Rossberg.
- To run as a standalone app, download and execute UnionFind.jar.
- Please report any bugs to: rlpm@cs.unm.edu
- Also take a look at my Graphical 2-3-4
Tree .
- Last updated: 2004-10-24 18:31
