blob: 7fab9eba3bcd7ec744265b1ed2a803a259a4f5c0 (
plain)
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
// Copyright (C) 2011 Davis E. King (davis@dlib.net)
// License: Boost Software License See LICENSE.txt for the full license.
#ifndef DLIB_DISJOINT_SUBsETS_Hh_
#define DLIB_DISJOINT_SUBsETS_Hh_
#include "disjoint_subsets_abstract.h"
#include <vector>
#include "../algs.h"
namespace dlib
{
// ----------------------------------------------------------------------------------------
class disjoint_subsets
{
public:
void clear (
) noexcept
{
items.clear();
}
void set_size (
unsigned long new_size
)
{
items.resize(new_size);
for (unsigned long i = 0; i < items.size(); ++i)
{
items[i].parent = i;
items[i].rank = 0;
}
}
size_t size (
) const noexcept
{
return items.size();
}
unsigned long find_set (
unsigned long item
) const
{
// make sure requires clause is not broken
DLIB_ASSERT(item < size(),
"\t unsigned long disjoint_subsets::find_set()"
<< "\n\t item must be less than size()"
<< "\n\t item: " << item
<< "\n\t size(): " << size()
<< "\n\t this: " << this
);
if (items[item].parent == item)
{
return item;
}
else
{
// find root of item
unsigned long x = item;
do
{
x = items[x].parent;
} while (items[x].parent != x);
// do path compression
const unsigned long root = x;
x = item;
while (items[x].parent != x)
{
const unsigned long prev = x;
x = items[x].parent;
items[prev].parent = root;
}
return root;
}
}
unsigned long merge_sets (
unsigned long a,
unsigned long b
)
{
// make sure requires clause is not broken
DLIB_ASSERT(a != b &&
a < size() &&
b < size() &&
find_set(a) == a &&
find_set(b) == b,
"\t unsigned long disjoint_subsets::merge_sets(a,b)"
<< "\n\t invalid arguments were given to this function"
<< "\n\t a: " << a
<< "\n\t b: " << b
<< "\n\t size(): " << size()
<< "\n\t find_set(a): " << find_set(a)
<< "\n\t find_set(b): " << find_set(b)
<< "\n\t this: " << this
);
if (items[a].rank > items[b].rank)
{
items[b].parent = a;
return a;
}
else
{
items[a].parent = b;
if (items[a].rank == items[b].rank)
{
items[b].rank = items[b].rank + 1;
}
return b;
}
}
private:
/*
See the book Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein
for a discussion of how this algorithm works.
*/
struct data
{
unsigned long rank;
unsigned long parent;
};
mutable std::vector<data> items;
};
// ----------------------------------------------------------------------------------------
}
#endif // DLIB_DISJOINT_SUBsETS_Hh_
|
