1/* vim:set shiftwidth=4 ts=4: */
2
3#include <spinehdr.h>
4#include <union_find.h>
5#include <assert.h>
6
7typedef Agnode_t node_t;
8
9/* union-find */
10node_t *UF_find(node_t * n)
11{
12 while (ND_UF_parent(n) && (ND_UF_parent(n) != n)) {
13 if (ND_UF_parent(ND_UF_parent(n)))
14 ND_UF_parent(n) = ND_UF_parent(ND_UF_parent(n));
15 n = ND_UF_parent(n);
16 }
17 return n;
18}
19
20node_t *UF_union(node_t * u, node_t * v)
21{
22 if (u == v)
23 return u;
24 if (ND_UF_parent(u) == NULL) {
25 ND_UF_parent(u) = u;
26 ND_UF_size(u) = 1;
27 } else
28 u = UF_find(u);
29 if (ND_UF_parent(v) == NULL) {
30 ND_UF_parent(v) = v;
31 ND_UF_size(v) = 1;
32 } else
33 v = UF_find(v);
34 if (u == v)
35 return u;
36 if (ND_UF_size(u) < ND_UF_size(v)) {
37 ND_UF_parent(u) = v;
38 ND_UF_size(v) += ND_UF_size(u);
39 } else {
40 ND_UF_parent(v) = u;
41 ND_UF_size(u) += ND_UF_size(v);
42 v = u;
43 }
44 return v;
45}
46
47void UF_remove(node_t * u, node_t * v)
48{
49 assert(ND_UF_size(u) == 1);
50 ND_UF_parent(u) = u;
51 ND_UF_size(v) -= ND_UF_size(u);
52}
53
54void UF_singleton(node_t * u)
55{
56 ND_UF_size(u) = 1;
57 ND_UF_parent(u) = NULL;
58}
59
60void UF_setname(node_t * u, node_t * v)
61{
62 assert(u == UF_find(u));
63 ND_UF_parent(u) = v;
64 ND_UF_size(v) += ND_UF_size(u);
65}
66