How to build and work with cluster trees

Table of Contents

• Introduction
• Building a Cluster Tree
  • The Tree Type
  • The nodal locations
  • Building the tree
  • Source and receiver nodes
  • Building the tree from NiHu meshes
• Traversing cluster trees
  • Simple traversing
  • Level by level traversing
  • Leaf traversing
  • Depth first search traversing

Introduction

Cluster trees are hierarchical oc-trees built up based on a sequence of nodal locations. Cluster trees provide the interface for various tree traversal methods, needed for implementing Fast Multipole Methods. This tutorial demonstrates the usage of cluster trees in NiHu's fast multipole module.

Building a Cluster Tree

The Tree Type

Cluster trees are a hierarchical collections of clusters, therefore, the cluster type needs to be defined first. In our simplest example, we work with a cluster tree containing three-dimensional empty clusters (see NiHu::fmm::empty_cluster).

static size_t const dimension = 3;
typedef NiHu::fmm::empty_cluster<dimension> cluster_t;
typedef NiHu::fmm::cluster_tree<cluster_t> cluster_tree_t;

The nodal locations

We create an array of random nodal locations.

    typedef cluster_t::location_t location_t;
    size_t N = 5000;    // number of nodes
    location_t *begin = new location_t[N];
    for (size_t i = 0; i < N; ++i)
        begin[i].setRandom();

Building the tree

The cluster tree is built with its constructor. In the simplest case the constructor needs three parameters:

• the two iterators defining the range of nodal locations,
• and a cluster division functor. The functor receives a cluster as argument, and returns if the cluster needs to be divided into children or not. As an example, we apply the built_in functor NiHu::fmm::divide_num_nodes that divides a cluster if the number of nodes in a cluster is larger than its parameter.

    cluster_tree_t tree(begin, begin + N, NiHu::fmm::divide_num_nodes(10));

Alternatively, NiHu contains built in dividing functors for building balanced trees of specified depth or prescribed leaf level cluster diameter:

    cluster_tree_t tree_depth(begin, begin + N, NiHu::fmm::divide_depth(6));
    cluster_tree_t tree_diam(begin, begin + N, NiHu::fmm::divide_diameter(1e-1));

Source and receiver nodes

In the above trees, each node is both source and receiver. In order to define source and receiver nodes separately, the alternative constructor can be used that takes two ranges as input:

    size_t N_src = 1000;
    location_t *src_begin = new location_t[N_src];
    for (size_t i = 0; i < N_src; ++i)
        src_begin[i].setRandom();
 
    size_t N_rec = 200;
    location_t *rec_begin = new location_t[N_rec];
    for (size_t i = 0; i < N_rec; ++i)
        rec_begin[i].setRandom();
 
    cluster_tree_t src_rec_tree(src_begin, src_begin + N_src,
        rec_begin, rec_begin + N_rec,
        NiHu::fmm::divide_num_nodes(10));

Building the tree from NiHu meshes

In most boundary element applications, the cluster tree is not built based on a sequence of nodal locations, rather based on elements of a boundary element mesh. NiHu provides built-in iterators NiHu::fmm::elem_center_iterator that traverse mesh elements but return the element center when dereferenced:

    auto mesh = NiHu::read_off_mesh("mesh.off", NiHu::tria_1_tag());
    cluster_tree_t tree_mesh(
        NiHu::fmm::create_elem_center_iterator(mesh.template begin<NiHu::tria_1_elem>()),
        NiHu::fmm::create_elem_center_iterator(mesh.template end<NiHu::tria_1_elem>()),
        NiHu::fmm::divide_num_nodes(10));

Traversing cluster trees

Simple traversing

The cluster tree (see NiHu::fmm::cluster_tree) is a vector container of clusters, and clusters can be accessed by indexing. The following snippet, for example, traverses each cluster of a tree:

    for (size_t i = 0; i < tree.get_n_clusters(); ++i)
    {
        size_t level = tree[i].get_level();
        location_t loc = tree[i].get_bounding_box().get_center();
    }

Level by level traversing

The clusters are stored in a level-contiguous way that makes level-by-level traversing possible by getting the begin and end index of clusters within a specified level:

    for (size_t i = tree.level_begin(2); i < tree.level_end(2); ++i)
        cluster_t const &c = tree[i];

Leaf traversing

In an unbalanced tree, the leaf clusters are not stored continuously. Therefore, NiHu cluster trees provide an index vector to traverse leaf clusters:

    for (auto i : tree.get_leaf_src_indices())
        cluster_t const &c = tree[i];

Similarly, source and receiver leaf clusters can be traveresed by getting their index vectors:

    for (auto i : tree.get_leaf_src_indices())
        cluster_t const &c = tree[i];

Depth first search traversing

Depth first search (DFS) traverse of the tree is provided by the cluster class that contains indices of its children in the tree.

void dfs(cluster_tree_t const &tree, size_t idx)
{
    for (auto c : tree[idx].get_children())
        dfs(tree, c);
}