# harmony-dev mailing list archives

##### Site index · List index
Message view
Top
From "daizi sheng" <daizish...@gmail.com>
Subject [drlvm][jitrino] Problem on the implementation of UnionFind class
Date Thu, 08 Nov 2007 07:16:57 GMT
```The file is: working_vm\vm\jitrino\src\shared\unionfind.h .

In this file, one data structure is implemented to support
the following 3 operations:

MAKE_SET, FIND_SET, UNION_SET

To achieve high efficiency, there are two heuristics--"union by rank"
and "path compression" to improve the performance.

1. find () function implements two version of "path compression"

2. link () function try to implement the "union by rank" algorithm, but
unfortunately, it does not implement it correctly.

Here is the original code snippet

assert(other);

UnionFind *aroot = find();
UnionFind *broot = other->find();

if (aroot->rank < broot->rank) {
aroot->parent = broot;
} else {
if (aroot->rank == broot->rank) {
broot->rank += 1;
}
broot->parent = aroot;
}
};

And you can check the original algorithm on the following page for more
details if
you want: section 22.3 in page

http://acm2.ustc.edu.cn/~daizisheng/algorithm/clrs/clrs_1st/book6/chap22.htm

Generally, the algorithm try to link the node with lower rank to the node
with higher
rank (rank is the height of the sub-tree rooted at current node, e.g.
height of
one-node-tree is 1), If both tree owns same rank (the if statement), we
break the
tie arbitrarily, here we set broot to be a child of aroot, and SO,

rank of node aroot should be increased by 1, not rank of node broot.

What we need to do to fix it is just changing the statement

broot->rank += 1;
into

aroot->rank += 1;

ANYWAY, such error does not lead to any invalidation, but it do lead an
efficiency problem.

Not sure whether it is a real bug, but at least, it

does not work as what the author expected.

```
Mime
• Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message