The cluster tree, or partition tree that represents the partitioning of the rows or columns of a hierarchical matrix.
More...
#include <ClusterTree.hpp>
The cluster tree, or partition tree that represents the partitioning of the rows or columns of a hierarchical matrix.
This uses a recursive representation, a child in the tree is also an ClusterTree. A node in this tree should always have 0 or 2 children, and the size of the tree should always be the sum of the sizes of its children.
To build a whole tree use the constructor ClusterTree(int n) and then refine it, either evenly using refine(int leaf_size), or manualy by adding nodes to the child vector ClusterTree::c.
Or you can use one of the clustering algorithms, see binary_tree_clustering()
◆ ClusterTree() [1/2]
strumpack::structured::ClusterTree::ClusterTree |
( |
| ) |
|
|
inline |
Constructor, initializes to an empty tree, with size 0.
◆ ClusterTree() [2/2]
strumpack::structured::ClusterTree::ClusterTree |
( |
int |
n | ) |
|
|
inline |
Constructor, initializes to a matrix with size n, only 1 node (1 level), so no refinement.
- Parameters
-
n | Size of the corresponding matrix. |
- See also
- n, c, refine
◆ deserialize() [1/2]
template<typename integer_t >
static ClusterTree strumpack::structured::ClusterTree::deserialize |
( |
const integer_t * |
buf | ) |
|
|
inlinestatic |
Constructor, taking a vector desribing an entire tree. This is used for deserialization. The constructor argument buf should be one obtained from calling serialize on an ClusterTree object.
- Parameters
-
- See also
- serialize
◆ deserialize() [2/2]
template<typename integer_t >
static ClusterTree strumpack::structured::ClusterTree::deserialize |
( |
const std::vector< integer_t > & |
buf | ) |
|
|
inlinestatic |
Constructor, taking a vector desribing an entire tree. This is used for deserialization. The constructor argument buf should be one obtained from calling serialize on an ClusterTree object.
- Parameters
-
- See also
- serialize
◆ expand_complete()
void strumpack::structured::ClusterTree::expand_complete |
( |
bool |
allow_zero_nodes | ) |
|
|
inline |
Further refine the tree to make it complete. This will add zero or size 1 leaf nodes at the lowest level.
- Parameters
-
allow_zero_nodes | If True, then the leaf nodes which are not at the lowest level, are split into two nodes with sizes (size,0), recursively until the tree is complete. If False, a leaf node which is not at the lowest level, will be split into 2 children with sizes (size-x,x) where x is such that all leafs in the final tree have at least size 1 (this might fail in certain cases, if too many levels are required). |
- See also
- truncate_complete
◆ expand_complete_levels()
void strumpack::structured::ClusterTree::expand_complete_levels |
( |
int |
lvls | ) |
|
|
inline |
Further refine the tree to make it a complete tree with a specified number of levels.
- Parameters
-
lvls | The requested number of levels. Should be >= this->levels. |
◆ is_complete()
bool strumpack::structured::ClusterTree::is_complete |
( |
| ) |
const |
|
inline |
◆ leaf_sizes()
template<typename integer_t >
std::vector<integer_t> strumpack::structured::ClusterTree::leaf_sizes |
( |
| ) |
const |
|
inline |
Return a vector with leaf sizes.
- Returns
- vector with the sizes of the leafs.
◆ levels()
int strumpack::structured::ClusterTree::levels |
( |
| ) |
const |
|
inline |
Return the number of levels in this tree.
- Returns
- Number of levels in the tree (>= 1).
◆ map_from_complete_to_leafs()
std::pair<std::vector<int>,std::vector<int> > strumpack::structured::ClusterTree::map_from_complete_to_leafs |
( |
int |
lvls | ) |
const |
|
inline |
Return a map from nodes in a complete tree, with lvls levels, numbered by level, with the root being 1, to leafs of the original tree before it was made complete. Note that in the level by level ordering, a node with number id has children 2*id and 2*id+1.
◆ nodes()
int strumpack::structured::ClusterTree::nodes |
( |
| ) |
const |
|
inline |
Return the total number of nodes in this tree.
- Returns
- Total number of nodes, 1 for a tree with only 1 level, ..
◆ print()
void strumpack::structured::ClusterTree::print |
( |
| ) |
const |
|
inline |
Print the sizes of the nodes in the tree, in postorder.
◆ refine()
const ClusterTree& strumpack::structured::ClusterTree::refine |
( |
int |
leaf_size | ) |
|
|
inline |
Refine the tree to a given leaf size. This just splits the nodes into equal parts (+/- 1) as long as a node is larger than 2*leaf_size.
- Parameters
-
leaf_size | Leaf size, leafs in the resulting tree will be smaller or equal to this leaf_size. |
◆ serialize()
std::vector<int> strumpack::structured::ClusterTree::serialize |
( |
| ) |
const |
|
inline |
Serialize the entire tree to a single vector storing size and child/parent info. This can be used to communicate the tree with MPI for instance. A new tree can be constructed at the receiving side with the apporiate constructor.
- Returns
- Serialized tree. Do not rely on the meaning of the elements in the vector, only use with the corresponding constructor.
◆ truncate_complete()
void strumpack::structured::ClusterTree::truncate_complete |
( |
| ) |
|
|
inline |
Truncate this tree to a complete tree. This routine will first find the leaf node with the least number of ancestors, then remove all nodes which have more ancestors. The resulting tree will be complete and binary.
- See also
- expand_complete
std::vector<ClusterTree> strumpack::structured::ClusterTree::c |
Vector with children. This should always have c.size() == 0 or c.size() == 2, for a leaf and an internal node of the tree respectively.
◆ size
int strumpack::structured::ClusterTree::size |
Size of the corresponing matrix. This should always be >= 0 and should be equal to the sum of the sizes of the children.
The documentation for this class was generated from the following file: