Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/*
* Kruskal.cpp
*
* Created on: Mar 26, 2016
* Author: Jan Broz
*/
#include <unordered_map>
#include <graph/common/Node.h>
namespace graph {
/// class solving "Union-Find" problem
class Components {
protected:
/// wrapper over the node containing identification of parent and height of subtree
struct SetNode {
Node parent;
int height;
};
std::unordered_map< Node, SetNode > nodes;
public:
/// marks a node as a single-element component
void MakeSet( Node node )
{
nodes[ node ].parent = node;
nodes[ node ].height = 0;
}
/// returns a reprezentative of the component in which is the given node
Node Find( Node node )
{
if (node != nodes[ node ].parent)
nodes[ node ].parent = Find( nodes[ node ].parent ); // shorten the path to root for next use
return nodes[ node ].parent;
}
/// unifies 2 acyclic components
void Union( Node node1, Node node2 )
{
Link( Find( node1 ), Find( node2 ) );
}
protected:
void Link( Node root1, Node root2 )
{
// connect smaller into bigger to limit the final depth
if (nodes[ root1 ].height < nodes[ root2 ].height) {
nodes[ root1 ].parent = root2;
} else {
nodes[ root2 ].parent = root1;
// if the trees are equaly high, connecting them increases the height by 1
if (nodes[ root1 ].height == nodes[ root2 ].height)
nodes[ root1 ].height++;
}
}
};
/// class solving "Union-Find" problem (version indexed by integers)
class Components2 {
protected:
/// wrapper over the node containing identification of parent and height of subtree
struct SetNode {
uint parent;
int height;
};
SetNode * _nodes;
public:
Components2( uint nodeCount ) { _nodes = new SetNode [nodeCount]; }
~Components2() { delete [] _nodes; }
/// marks a node as a single-element component
void MakeSet( uint node )
{
_nodes[ node ].parent = node;
_nodes[ node ].height = 0;
}
/// returns a reprezentative of the component in which the given node is
uint Find( uint node )
{
if (node != _nodes[ node ].parent)
_nodes[ node ].parent = Find( _nodes[ node ].parent ); // shorten the path to root for next use
return _nodes[ node ].parent;
}
/// unifies 2 acyclic components
void Union( uint node1, uint node2 )
{
Link( Find( node1 ), Find( node2 ) );
}
protected:
void Link( uint root1, uint root2 )
{
// connect smaller into bigger to limit the final depth
if (_nodes[ root1 ].height < _nodes[ root2 ].height) {
_nodes[ root1 ].parent = root2;
} else {
_nodes[ root2 ].parent = root1;
// if the trees are equaly high, connecting them increases the height by 1
if (_nodes[ root1 ].height == _nodes[ root2 ].height)
_nodes[ root1 ].height++;
}
}
};
} // namespace graph