8#ifndef INCLUDED_SDSL_K2_TREE
9#define INCLUDED_SDSL_K2_TREE
48template <u
int8_t k,
typename t_bv = bit_vector,
typename t_rank =
typename t_bv::rank_1_type>
71 int simulated_size = std::pow(k, k_height);
72 std::vector<std::deque<bit_vector>> acc(k_height + 1);
78 for (
int i = 1; i < k_height; i++)
79 for (
auto it = acc[i].begin(); it != acc[i].end(); it++)
80 t_size += (*it).size();
82 for (
auto it = acc[k_height].begin(); it != acc[k_height].end(); it++)
83 l_size += (*it).size();
89 for (
int j = 1; j < k_height; j++)
90 for (
auto it = acc[j].begin(); it != acc[j].end(); it++)
91 for (
unsigned i = 0; i < (*it).size(); i++)
94 k_t_.
set_int(n, (*it).get_int(i, 1), 1);
98 for (
auto it = acc[k_height].begin(); it != acc[k_height].end(); it++)
99 for (
unsigned i = 0; i < (*it).size(); i++)
102 k_l_.
set_int(n * 1, (*it).get_int(i, 1), 1);
122 if (level >= k_t.size())
124 if (k_l[level - k_t.size()] == 1)
131 idx_type y = k_t_rank(level + 1) * std::pow(k_k, 2) + k_k * std::floor(row /
static_cast<double>(n));
132 for (
unsigned j = 0; j < k_k; j++)
133 _neigh(n / k_k, row % n, col + n * j, y + j, acc);
150 if (level >= k_t.size())
152 if (k_l[level - k_t.size()] == 1)
161 idx_type y = k_t_rank(level + 1) * std::pow(k_k, 2) + std::floor(col /
static_cast<double>(n));
162 for (
unsigned j = 0; j < k_k; j++)
179 typedef std::tuple<idx_type, idx_type, size_type, idx_type, idx_type> t_part_tuple;
182 k_height = std::ceil(std::log(
size) / std::log(k_k));
183 k_height = k_height > 1 ? k_height : 1;
188 std::queue<t_part_tuple> q;
191 size_type l = std::pow(k_k, k_height - 1);
192 std::vector<idx_type> pos_by_chunk(k_2 + 1, 0);
194 q.push(t_part_tuple(0, edges.size(), l, 0, 0));
198 std::vector<idx_type> amount_by_chunk(k_2, 0);
199 std::tie(i, j, l, r_0, c_0) = q.front();
202 for (it = i; it < j; it++)
216 for (it = 0; it < k_2; it++, t++)
217 if (amount_by_chunk[it] != 0)
225 for (it = 1; it < k_2; it++)
226 pos_by_chunk[it] = pos_by_chunk[it - 1] + amount_by_chunk[it - 1];
228 pos_by_chunk[k_2] = j;
230 for (it = 0; it < k_2; it++, t++)
232 if (amount_by_chunk[it] != 0)
237 q.push(t_part_tuple(pos_by_chunk[it], pos_by_chunk[it + 1], l / k_k, r_0 + r * l, c_0 + c * l));
242 for (
unsigned ch = 0; ch < k_2; ch++)
244 idx_type be = ch == 0 ? i : pos_by_chunk[ch - 1];
245 for (it = pos_by_chunk[ch]; it < be + amount_by_chunk[ch];)
249 if (pos_by_chunk[chunk] != it)
250 std::iter_swap(edges.begin() + it, edges.begin() + pos_by_chunk[chunk]);
253 pos_by_chunk[chunk]++;
261 k_t_rank = t_rank(&k_t);
274 k2_tree(std::vector<std::vector<int>> & matrix)
276 if (matrix.size() < 1)
278 throw std::logic_error(
"Matrix has no elements");
280 std::vector<bit_vector> t;
282 if (matrix.size() < k_k)
285 k_height = std::ceil(std::log(matrix.size()) / std::log(k_k));
289 k_t_rank = t_rank(&k_t);
304 assert(edges.size() > 0);
327 assert(buf_x.
size() == buf_y.
size());
328 assert(buf_x.
size() > 0);
330 std::vector<std::tuple<idx_type, idx_type>> edges;
331 edges.reserve(buf_x.
size());
337 max = std::max(
static_cast<size_type>(v), max);
339 max = std::max(
static_cast<size_type>(v), max);
343 for (uint64_t i = 0; i < buf_x.
size(); i++)
344 edges.push_back(std::tuple<idx_type, idx_type>{buf_x[i], buf_y[i]});
349 k2_tree(
k2_tree const & tr) : k_t(tr.k_t), k_l(tr.k_l), k_k(tr.k_k), k_height(tr.k_height), k_t_rank(tr.k_t_rank)
351 k_t_rank.set_vector(&k_t);
356 *
this = std::move(tr);
364 k_t = std::move(tr.k_t);
365 k_l = std::move(tr.k_l);
366 k_k = std::move(tr.k_k);
367 k_height = std::move(tr.k_height);
368 k_t_rank = std::move(tr.k_t_rank);
369 k_t_rank.set_vector(&k_t);
380 *
this = std::move(tmp);
389 if (k_k != tr.k_k || k_height != tr.k_height)
391 if (k_t.size() != tr.k_t.size() || k_l.size() != tr.k_l.size())
393 for (
unsigned i = 0; i < k_t.size(); i++)
394 if (k_t[i] != tr.k_t[i])
396 for (
unsigned i = 0; i < k_l.size(); i++)
397 if (k_l[i] != tr.k_l[i])
421 if (k_t.size() == 0 && k_l.size() == 0)
423 size_type n = std::pow(k_k, k_height - 1);
430 row = std::floor(i /
static_cast<double>(n));
431 col = std::floor(j /
static_cast<double>(n));
437 while (level < k_t.size())
441 row = std::floor(i /
static_cast<double>(n));
442 col = std::floor(j /
static_cast<double>(n));
445 level = k_t_rank(level + 1) * k_2 + k_k * row + col;
449 return k_l[level - k_t.size()] == 1;
459 std::vector<idx_type> acc{};
460 if (k_l.size() == 0 && k_t.size() == 0)
463 idx_type y = k_k * std::floor(i /
static_cast<double>(n));
464 for (
unsigned j = 0; j < k_k; j++)
465 _neigh(n / k_k, i % n, n * j, y + j, acc);
476 std::vector<idx_type> acc{};
477 if (k_l.size() == 0 && k_t.size() == 0)
481 idx_type y = std::floor(i /
static_cast<double>(n));
482 for (
unsigned j = 0; j < k_k; j++)
500 written_bytes += k_t.serialize(out, child,
"t");
501 written_bytes += k_l.serialize(out, child,
"l");
502 written_bytes += k_t_rank.serialize(out, child,
"t_rank");
504 written_bytes +=
write_member(k_height, out, child,
"height");
506 return written_bytes;
518 k_t_rank.set_vector(&k_t);
524 template <
typename archive_t>
535 template <
typename archive_t>
536 typename std::enable_if<cereal::traits::is_output_serializable<k2_tree, archive_t>::value,
void>::type
544 k_t_rank.set_vector(&k_t);
cereal.hpp offers cereal support
uint64_t size() const
Returns the number of elements currently stored.
size_type size() const noexcept
The number of elements in the int_vector.
void shrink_to_fit()
Free unused allocated memory.
void resize(const size_type size)
Resize the int_vector in terms of elements.
void set_int(size_type idx, value_type x, const uint8_t len=64)
Set the bits from position idx to idx+len-1 to the binary representation of integer x.
bool adj(idx_type i, idx_type j) const
Indicates wheter node j is adjacent to node i or not.
k2_tree_ns::idx_type idx_type
void load(std::istream &in)
Load from istream.
void _neigh(size_type n, idx_type row, idx_type col, size_type level, std::vector< idx_type > &acc) const
Recursive function to retrieve list of neighbors.
void build_from_edges(std::vector< std::tuple< idx_type, idx_type > > &edges, const size_type size)
Build a tree from an edges collection.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
k2_tree & operator=(k2_tree &&tr)
Move assignment operator.
void _reverse_neigh(size_type n, idx_type row, idx_type col, size_type level, std::vector< idx_type > &acc) const
Recursive function to retrieve list of reverse neighbors.
k2_tree(std::vector< std::tuple< idx_type, idx_type > > &edges, const size_type size)
Constructor.
std::vector< idx_type > neigh(idx_type i) const
Returns a list of neighbors of node i.
std::vector< idx_type > reverse_neigh(idx_type i) const
Returns a list of reverse neighbors of node i.
std::enable_if< cereal::traits::is_output_serializable< k2_tree, archive_t >::value, void >::type CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Load via cereal.
k2_tree_ns::size_type size_type
k2_tree & operator=(k2_tree &tr)
Assignment operator.
k2_tree(std::vector< std::vector< int > > &matrix)
Constructor.
k2_tree(std::string filename, size_type size=0)
Constructor.
k2_tree(k2_tree const &tr)
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize to a stream.
bool operator==(k2_tree const &tr) const
Equal operator.
void build_from_matrix(std::vector< std::vector< int > > const &matrix)
static structure_tree_node * add_child(structure_tree_node *v, std::string const &name, std::string const &type)
static void add_size(structure_tree_node *v, uint64_t value)
int_vector.hpp contains the sdsl::int_vector class.
int_vector_buffer.hpp contains the sdsl::int_vector_buffer class.
io.hpp contains some methods for reading/writing sdsl structures.
k2_tree_helper.hpp contains helper functions and definitions for a k^2-tree implementation.
uint16_t get_chunk_idx(idx_type v, idx_type u, idx_type c_0, idx_type r_0, size_type l, uint8_t k)
Get the chunk index ([0, k^2[) of a submatrix point.
int _build_from_matrix(std::vector< std::vector< int > > const &matrix, const uint8_t k, int n, int const height, int l, int p, int q, std::vector< std::deque< t_bv > > &acc)
void build_template_vector(bit_vector &k_t_, bit_vector &k_l_, t_bv &k_t, t_bv &k_l)
int_vector ::size_type size_type
int_vector ::size_type idx_type
Namespace for the succinct data structure library.
size_t write_member(T const &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
void read_member(T &t, std::istream &in)
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
int_vector ::size_type size(range_type const &r)
Size of a range.
structure_tree.hpp contains a helper class which can represent the memory structure of a class.
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.