SDSL 3.0.2
Succinct Data Structure Library
Loading...
Searching...
No Matches
k2_tree.hpp
Go to the documentation of this file.
1// Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2// Please see the AUTHORS file for details. Use of this source code is governed
3// by a BSD license that can be found in the LICENSE file.
8#ifndef INCLUDED_SDSL_K2_TREE
9#define INCLUDED_SDSL_K2_TREE
10
11#include <algorithm>
12#include <assert.h>
13#include <cmath>
14#include <cstdint>
15#include <deque>
16#include <iosfwd>
17#include <memory>
18#include <queue>
19#include <stdexcept>
20#include <string>
21#include <tuple>
22#include <type_traits>
23#include <vector>
24
25#include <sdsl/cereal.hpp>
26#include <sdsl/int_vector.hpp>
28#include <sdsl/io.hpp>
31#include <sdsl/util.hpp>
32
34namespace sdsl
35{
37
48template <uint8_t k, typename t_bv = bit_vector, typename t_rank = typename t_bv::rank_1_type>
50{
51public:
54
55private:
58 t_bv k_t;
60 t_bv k_l;
61
62 t_rank k_t_rank;
63
64 uint8_t k_k;
65 uint16_t k_height;
66
67protected:
68 void build_from_matrix(std::vector<std::vector<int>> const & matrix)
69 {
70 // Makes the size a power of k.
71 int simulated_size = std::pow(k, k_height);
72 std::vector<std::deque<bit_vector>> acc(k_height + 1);
73
74 k2_tree_ns::_build_from_matrix<bit_vector>(matrix, k, simulated_size, k_height, 1, 0, 0, acc);
75
76 size_type t_size = 0;
77 size_type l_size = 0;
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();
81
82 for (auto it = acc[k_height].begin(); it != acc[k_height].end(); it++)
83 l_size += (*it).size();
84
85 bit_vector k_t_(t_size, 0);
86 bit_vector k_l_(l_size, 0);
87
88 int n = 0;
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++)
92 {
93 // TODO there should be a better way to do this
94 k_t_.set_int(n, (*it).get_int(i, 1), 1);
95 n++;
96 }
97 n = 0;
98 for (auto it = acc[k_height].begin(); it != acc[k_height].end(); it++)
99 for (unsigned i = 0; i < (*it).size(); i++)
100 {
101 // TODO there should be a better way to do this
102 k_l_.set_int(n * 1, (*it).get_int(i, 1), 1);
103 n++;
104 }
105
106 k2_tree_ns::build_template_vector<t_bv>(k_t_, k_l_, k_t, k_l);
107 }
108
120 void _neigh(size_type n, idx_type row, idx_type col, size_type level, std::vector<idx_type> & acc) const
121 {
122 if (level >= k_t.size())
123 { // Last level
124 if (k_l[level - k_t.size()] == 1)
125 acc.push_back(col);
126 return;
127 }
128
129 if (k_t[level] == 1)
130 {
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);
134 }
135 }
136
148 void _reverse_neigh(size_type n, idx_type row, idx_type col, size_type level, std::vector<idx_type> & acc) const
149 {
150 if (level >= k_t.size())
151 { // Last level
152 if (k_l[level - k_t.size()] == 1)
153 {
154 acc.push_back(row);
155 }
156 return;
157 }
158
159 if (k_t[level] == 1)
160 {
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++)
163 _reverse_neigh(n / k_k, row + n * j, col % n, y + j * k_k, acc);
164 }
165 }
166
168
176 void build_from_edges(std::vector<std::tuple<idx_type, idx_type>> & edges, const size_type size)
177 {
178
179 typedef std::tuple<idx_type, idx_type, size_type, idx_type, idx_type> t_part_tuple;
180
181 k_k = k;
182 k_height = std::ceil(std::log(size) / std::log(k_k));
183 k_height = k_height > 1 ? k_height : 1; // If size == 0
184 size_type k_2 = std::pow(k_k, 2);
185 bit_vector k_t_ = bit_vector(k_2 * k_height * edges.size(), 0);
186 bit_vector k_l_;
187
188 std::queue<t_part_tuple> q;
189 idx_type t = 0, last_level = 0;
190 idx_type i, j, r_0, c_0, it, c, r;
191 size_type l = std::pow(k_k, k_height - 1);
192 std::vector<idx_type> pos_by_chunk(k_2 + 1, 0);
193
194 q.push(t_part_tuple(0, edges.size(), l, 0, 0));
195
196 while (!q.empty())
197 {
198 std::vector<idx_type> amount_by_chunk(k_2, 0);
199 std::tie(i, j, l, r_0, c_0) = q.front();
200 q.pop();
201 // Get size for each chunk
202 for (it = i; it < j; it++)
203 amount_by_chunk
204 [k2_tree_ns::get_chunk_idx(std::get<0>(edges[it]), std::get<1>(edges[it]), c_0, r_0, l, k_k)] += 1;
205 if (l == 1)
206 {
207 if (last_level == 0)
208 {
209 last_level = t;
210 k_l_ = bit_vector(k_t_.size() - last_level, 0);
211 k_t_.resize(last_level);
212 k_t_.shrink_to_fit();
213 last_level = 1; // if t was 0
214 t = 0; // Restart counter as we're storing at k_l_ now.
215 }
216 for (it = 0; it < k_2; it++, t++)
217 if (amount_by_chunk[it] != 0)
218 k_l_[t] = 1;
219 // At l == 1 we do not put new elements at the queue.
220 continue;
221 }
222
223 // Set starting position in the vector for each chunk
224 pos_by_chunk[0] = i;
225 for (it = 1; it < k_2; it++)
226 pos_by_chunk[it] = pos_by_chunk[it - 1] + amount_by_chunk[it - 1];
227 // To handle the last case when it = k_2 - 1
228 pos_by_chunk[k_2] = j;
229 // Push to the queue every non zero elements chunk
230 for (it = 0; it < k_2; it++, t++)
231 // If not empty chunk, set bit to 1
232 if (amount_by_chunk[it] != 0)
233 {
234 r = it / k_k;
235 c = it % k_k;
236 k_t_[t] = 1;
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));
238 }
239 idx_type chunk;
240
241 // Sort edges' vector
242 for (unsigned ch = 0; ch < k_2; ch++)
243 {
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];)
246 {
247 chunk = k2_tree_ns::get_chunk_idx(std::get<0>(edges[it]), std::get<1>(edges[it]), c_0, r_0, l, k_k);
248
249 if (pos_by_chunk[chunk] != it)
250 std::iter_swap(edges.begin() + it, edges.begin() + pos_by_chunk[chunk]);
251 else
252 it++;
253 pos_by_chunk[chunk]++;
254 }
255 }
256 }
257 k_l_.resize(t);
258 k_l_.shrink_to_fit();
259 k2_tree_ns::build_template_vector<t_bv>(k_t_, k_l_, k_t, k_l);
260
261 k_t_rank = t_rank(&k_t);
262 }
263
264public:
265 k2_tree() = default;
266
268
274 k2_tree(std::vector<std::vector<int>> & matrix)
275 {
276 if (matrix.size() < 1)
277 {
278 throw std::logic_error("Matrix has no elements");
279 }
280 std::vector<bit_vector> t;
281 k_k = k;
282 if (matrix.size() < k_k)
283 k_height = 1;
284 else // height = log_k n
285 k_height = std::ceil(std::log(matrix.size()) / std::log(k_k));
286
287 build_from_matrix(matrix);
288
289 k_t_rank = t_rank(&k_t);
290 }
291
293
301 k2_tree(std::vector<std::tuple<idx_type, idx_type>> & edges, const size_type size)
302 {
303 assert(size > 0);
304 assert(edges.size() > 0);
305
306 build_from_edges(edges, size);
307 }
308
310
322 k2_tree(std::string filename, size_type size = 0)
323 {
324 int_vector_buffer<> buf_x(filename + ".x", std::ios::in);
325 int_vector_buffer<> buf_y(filename + ".y", std::ios::in);
326
327 assert(buf_x.size() == buf_y.size());
328 assert(buf_x.size() > 0);
329
330 std::vector<std::tuple<idx_type, idx_type>> edges;
331 edges.reserve(buf_x.size());
332
333 if (size == 0)
334 {
335 size_type max = 0;
336 for (auto v : buf_x)
337 max = std::max(static_cast<size_type>(v), max);
338 for (auto v : buf_y)
339 max = std::max(static_cast<size_type>(v), max);
340 size = max + 1;
341 }
342
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]});
345
346 build_from_edges(edges, size);
347 }
348
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)
350 {
351 k_t_rank.set_vector(&k_t);
352 }
353
355 {
356 *this = std::move(tr);
357 }
358
361 {
362 if (this != &tr)
363 {
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);
370 }
371 return *this;
372 }
373
376 {
377 if (this != &tr)
378 {
379 k2_tree tmp(tr);
380 *this = std::move(tmp);
381 }
382 return *this;
383 }
384
386 bool operator==(k2_tree const & tr) const
387 {
388 // TODO check the rank support equality?
389 if (k_k != tr.k_k || k_height != tr.k_height)
390 return false;
391 if (k_t.size() != tr.k_t.size() || k_l.size() != tr.k_l.size())
392 return false;
393 for (unsigned i = 0; i < k_t.size(); i++)
394 if (k_t[i] != tr.k_t[i])
395 return false;
396 for (unsigned i = 0; i < k_l.size(); i++)
397 if (k_l[i] != tr.k_l[i])
398 return false;
399 return true;
400 }
401
402 t_bv get_t()
403 {
404 return k_t;
405 }
406
407 t_bv get_l()
408 {
409 return k_l;
410 }
411
413
419 bool adj(idx_type i, idx_type j) const
420 {
421 if (k_t.size() == 0 && k_l.size() == 0)
422 return false;
423 size_type n = std::pow(k_k, k_height - 1);
424 size_type k_2 = std::pow(k_k, 2);
425 idx_type col, row;
426
427 // This is duplicated to avoid an extra if at the loop. As idx_type
428 // is unsigned and rank has an offset of one, is not possible to run
429 // k_t_rank with zero as parameter at the first iteration.
430 row = std::floor(i / static_cast<double>(n));
431 col = std::floor(j / static_cast<double>(n));
432 i = i % n;
433 j = j % n;
434 idx_type level = k_k * row + col;
435 n = n / k_k;
436
437 while (level < k_t.size())
438 {
439 if (k_t[level] == 0)
440 return false;
441 row = std::floor(i / static_cast<double>(n));
442 col = std::floor(j / static_cast<double>(n));
443 i = i % n;
444 j = j % n;
445 level = k_t_rank(level + 1) * k_2 + k_k * row + col;
446 n = n / k_k;
447 }
448
449 return k_l[level - k_t.size()] == 1;
450 }
451
453
457 std::vector<idx_type> neigh(idx_type i) const
458 {
459 std::vector<idx_type> acc{};
460 if (k_l.size() == 0 && k_t.size() == 0)
461 return acc;
462 size_type n = static_cast<size_type>(std::pow(k_k, k_height)) / k_k;
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);
466 return acc;
467 }
468
470
474 std::vector<idx_type> reverse_neigh(idx_type i) const
475 {
476 std::vector<idx_type> acc{};
477 if (k_l.size() == 0 && k_t.size() == 0)
478 return acc;
479 // Size of the first square division
480 size_type n = static_cast<size_type>(std::pow(k_k, k_height)) / k_k;
481 idx_type y = std::floor(i / static_cast<double>(n));
482 for (unsigned j = 0; j < k_k; j++)
483 _reverse_neigh(n / k_k, n * j, i % n, y + j * k_k, acc);
484
485 return acc;
486 }
487
489
495 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
496 {
497 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
498 size_type written_bytes = 0;
499
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");
503 written_bytes += write_member(k_k, out, child, "k");
504 written_bytes += write_member(k_height, out, child, "height");
505 structure_tree::add_size(child, written_bytes);
506 return written_bytes;
507 }
508
510
513 void load(std::istream & in)
514 {
515 k_t.load(in);
516 k_l.load(in);
517 k_t_rank.load(in);
518 k_t_rank.set_vector(&k_t);
519 read_member(k_k, in);
520 read_member(k_height, in);
521 }
522
524 template <typename archive_t>
525 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
526 {
527 ar(CEREAL_NVP(k_k));
528 ar(CEREAL_NVP(k_height));
529 ar(CEREAL_NVP(k_t));
530 ar(CEREAL_NVP(k_l));
531 ar(CEREAL_NVP(k_t_rank));
532 }
533
535 template <typename archive_t>
536 typename std::enable_if<cereal::traits::is_output_serializable<k2_tree, archive_t>::value, void>::type
538 {
539 ar(CEREAL_NVP(k_k));
540 ar(CEREAL_NVP(k_height));
541 ar(CEREAL_NVP(k_t));
542 ar(CEREAL_NVP(k_l));
543 ar(CEREAL_NVP(k_t_rank));
544 k_t_rank.set_vector(&k_t);
545 }
546};
547} // namespace sdsl
548
549#endif
cereal.hpp offers cereal support
#define CEREAL_NVP(X)
Definition cereal.hpp:31
uint64_t size() const
Returns the number of elements currently stored.
void shrink_to_fit()
Free unused allocated memory.
size_type size() const noexcept
The number of elements in the int_vector.
void push_back(value_type value)
Insert element at the end.
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.
A k^2-tree.
Definition k2_tree.hpp:50
bool adj(idx_type i, idx_type j) const
Indicates wheter node j is adjacent to node i or not.
Definition k2_tree.hpp:419
void load(std::istream &in)
Load from istream.
Definition k2_tree.hpp:513
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.
Definition k2_tree.hpp:120
void build_from_edges(std::vector< std::tuple< idx_type, idx_type > > &edges, const size_type size)
Build a tree from an edges collection.
Definition k2_tree.hpp:176
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
Definition k2_tree.hpp:525
k2_tree & operator=(k2_tree &&tr)
Move assignment operator.
Definition k2_tree.hpp:360
k2_tree_ns::idx_type idx_type
Definition k2_tree.hpp:52
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.
Definition k2_tree.hpp:148
k2_tree(std::vector< std::tuple< idx_type, idx_type > > &edges, const size_type size)
Constructor.
Definition k2_tree.hpp:301
std::vector< idx_type > neigh(idx_type i) const
Returns a list of neighbors of node i.
Definition k2_tree.hpp:457
std::vector< idx_type > reverse_neigh(idx_type i) const
Returns a list of reverse neighbors of node i.
Definition k2_tree.hpp:474
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.
Definition k2_tree.hpp:537
k2_tree & operator=(k2_tree &tr)
Assignment operator.
Definition k2_tree.hpp:375
k2_tree_ns::size_type size_type
Definition k2_tree.hpp:53
k2_tree(k2_tree &&tr)
Definition k2_tree.hpp:354
k2_tree(std::vector< std::vector< int > > &matrix)
Constructor.
Definition k2_tree.hpp:274
k2_tree()=default
k2_tree(std::string filename, size_type size=0)
Constructor.
Definition k2_tree.hpp:322
k2_tree(k2_tree const &tr)
Definition k2_tree.hpp:349
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize to a stream.
Definition k2_tree.hpp:495
bool operator==(k2_tree const &tr) const
Equal operator.
Definition k2_tree.hpp:386
void build_from_matrix(std::vector< std::vector< int > > const &matrix)
Definition k2_tree.hpp:68
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_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="")
Definition io.hpp:94
void read_member(T &t, std::istream &in)
Definition io.hpp:119
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.