Introduction
This webpage contains material related to the implementation of union-find
algorithms in CHR.
Publications
- T. Schrijvers and T. Frühwirth,
Implementing and Analysing Union-Find in CHR ,
K.U.Leuven, Department of Computer Science,
Report CW 389, July, 2004.
[report]
Programs
Here are several different implementations of the union-find algorithm in CHR:
| Program |
Description |
Source/Author |
| ufd_basic.chr |
classic union-find without optimisations |
Thom Frühwirth |
| ufd_rank.chr |
union-find with path compression and union-by-rank |
Thom Frühwirth |
| ufd_size.chr |
union-find with path compression and union-by-size |
Tom Schrijvers |
Tools and Data
Here are the tools used for analysing the programs together
with the obtained data.
| File |
Description |
Source/Author |
| confluence.pl |
confluence checker, for SICstus |
Thom Frühwirth |
| critical_pairs.pl |
critical pairs of ufd_basic.chr |
confluence.pl |
| ufd_rank_data |
example output of ufd_rank.chr |
ufd_rank.chr |
| ufd.gnuplot |
example gnuplot script to process benchmark output |
Tom Schrijvers |
Contact Information
If you want more info, contact: