33#ifndef CLUSTER_TREE_HPP
34#define CLUSTER_TREE_HPP
37#include <unordered_map>
41#include "StrumpackConfig.hpp"
42#if defined(STRUMPACK_USE_MPI)
47 namespace structured {
80 std::vector<ClusterTree>
c;
106 if (
size >= 2*leaf_size) {
109 c[0].refine(leaf_size);
111 c[1].refine(leaf_size);
120 for (
auto& ch :
c) ch.print();
121 std::cout <<
size <<
" ";
133 nr_nodes += ch.nodes();
145 lvls = std::max(lvls, ch.levels());
158 truncate_complete_rec(1, min_levels());
177 expand_complete_rec(1,
levels(), allow_zero_nodes);
188 expand_complete_levels_rec(1, lvls);
219 t.de_serialize_rec(buf+1, buf+n+1, buf+2*n+1, pid);
234 int n =
nodes(), pid = 0;
235 std::vector<int> buf(3*n+1);
237 serialize_rec(buf.data()+1, buf.data()+n+1, buf.data()+2*n+1, pid);
241#if defined(STRUMPACK_USE_MPI)
242 void broadcast(
const MPIComm& comm) {
245 auto vsize = v.size();
246 comm.broadcast(vsize);
249 std::size_t vsize = 0;
250 comm.broadcast(vsize);
251 std::vector<int> v(vsize);
265 if (
c.empty())
return true;
266 else return c[0].levels() ==
c[1].levels();
274 template<
typename integer_t>
276 std::vector<integer_t> lf;
288 std::pair<std::vector<int>,std::vector<int>>
290 int n = (1 << lvls) - 1;
291 std::vector<int> map0(n, -1), map1(n, -1);
293 complete_to_orig_rec(1, map0, map1, leaf);
294 for (
int i=0; i<n; i++) {
295 if (map0[i] == -1) map0[i] = map0[(i+1)/2-1];
296 if (map1[i] == -1) map1[i] = map1[(i+1)/2-1];
307 int min_levels()
const {
310 lvls = std::min(lvls, 1 + ch.min_levels());
313 void truncate_complete_rec(
int lvl,
int lvls) {
314 if (lvl == lvls)
c.clear();
317 ch.truncate_complete_rec(lvl+1, lvls);
319 void expand_complete_rec(
int lvl,
int lvls,
bool allow_zero_nodes) {
323 if (allow_zero_nodes) {
327 int l1 = 1 << (lvls - lvl - 1);
328 c[0].size =
size - l1;
331 c[0].expand_complete_rec(lvl+1, lvls, allow_zero_nodes);
332 c[1].expand_complete_rec(lvl+1, lvls, allow_zero_nodes);
336 ch.expand_complete_rec(lvl+1, lvls, allow_zero_nodes);
339 void complete_to_orig_rec
340 (
int id, std::vector<int>& map0, std::vector<int>& map1,
342 if (
c.empty()) map0[
id-1] = map1[
id-1] = leaf++;
344 c[0].complete_to_orig_rec(
id*2, map0, map1, leaf);
345 c[1].complete_to_orig_rec(
id*2+1, map0, map1, leaf);
346 map0[
id-1] = map0[
id*2-1];
347 map1[
id-1] = map1[
id*2];
351 void expand_complete_levels_rec(
int lvl,
int lvls) {
355 c[0].size =
size / 2;
357 c[0].expand_complete_levels_rec(lvl+1, lvls);
358 c[1].expand_complete_levels_rec(lvl+1, lvls);
362 ch.expand_complete_levels_rec(lvl+1, lvls);
364 template<
typename integer_t>
365 void leaf_sizes_rec(std::vector<integer_t>& lf)
const {
367 ch.leaf_sizes_rec(lf);
371 void serialize_rec(
int* sizes,
int* lchild,
int* rchild,
int& pid)
const {
373 c[0].serialize_rec(sizes, lchild, rchild, pid);
375 c[1].serialize_rec(sizes, lchild, rchild, pid);
376 lchild[pid] = lroot-1;
378 }
else lchild[pid] = rchild[pid] = -1;
382 template<
typename integer_t>
void de_serialize_rec
383 (
const integer_t* sizes,
const integer_t* lchild,
384 const integer_t* rchild,
int& pid) {
386 if (rchild[pid+1] != -1) {
388 c[1].de_serialize_rec(sizes, lchild, rchild, pid);
389 c[0].de_serialize_rec(sizes, lchild, rchild, pid);
Contains some simple C++ MPI wrapper utilities.
Wrapper class around an MPI_Comm object.
Definition: MPIWrapper.hpp:194
bool is_root() const
Definition: MPIWrapper.hpp:293
The cluster tree, or partition tree that represents the partitioning of the rows or columns of a hier...
Definition: ClusterTree.hpp:67
bool is_complete() const
Definition: ClusterTree.hpp:264
const ClusterTree & refine(int leaf_size)
Definition: ClusterTree.hpp:104
void expand_complete(bool allow_zero_nodes)
Definition: ClusterTree.hpp:176
std::pair< std::vector< int >, std::vector< int > > map_from_complete_to_leafs(int lvls) const
Definition: ClusterTree.hpp:289
void print() const
Definition: ClusterTree.hpp:119
void truncate_complete()
Definition: ClusterTree.hpp:157
static ClusterTree deserialize(const integer_t *buf)
Definition: ClusterTree.hpp:215
std::vector< integer_t > leaf_sizes() const
Definition: ClusterTree.hpp:275
std::vector< int > serialize() const
Definition: ClusterTree.hpp:233
int levels() const
Definition: ClusterTree.hpp:142
ClusterTree()
Definition: ClusterTree.hpp:85
static ClusterTree deserialize(const std::vector< integer_t > &buf)
Definition: ClusterTree.hpp:201
int size
Definition: ClusterTree.hpp:73
ClusterTree(int n)
Definition: ClusterTree.hpp:94
int nodes() const
Definition: ClusterTree.hpp:130
std::vector< ClusterTree > c
Definition: ClusterTree.hpp:80
void expand_complete_levels(int lvls)
Definition: ClusterTree.hpp:187
Definition: StrumpackOptions.hpp:43