coco
142 lines
3.7 KiB
C++
142 lines
3.7 KiB
C++
// 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_
|