Example 3: Trees

These examples demonstrate the usage of the class Tree. The class Tree is the representation of a tree graph. It contains nodes (and edges) of a tree and manages connectivity between those. In addition, it stores TensorShape objects corresponding to every node. Objects of class Tree are used to create TensorTree objects and therefore Tree has a similar purpose for TensorTrees as the TensorShape class is for Tensor.

Tree Construction

There are two common ways of generating trees: from text files or automatically by providing some superparameters. Close-to-balenced trees can be generated automatically

size_t number_leaves = 7;
size_t dim_leaves = 3;
size_t dim_nodes = 2;
Tree tree = TreeFactory::BalancedTree(num_leaves, dim_leaves, dim_nodes);

Here num_leaves provides the number of leaves of the tree, dim_leaves is used to generate TensorShapes at bottomlayer of the tree and dim_nodes affects the Tensorshape at every node. The tree generated by this input reads @TODO: include graphic

A tree can also be generated from string or file via

1   -2
    2   -2
        2   -2
            2   -1
                3   0   0
            2   -1
                3   0   1
        2   -2
            2   -1
                3   0   2
            2   -1
                3   0   3
    2   -2
        2   -2
            2   -1
                3   0   4
            2   -1
                3   0   5
        2   -1
            3   0   6
1.  0.  0.  1.
1.  0.  0.  1.
1.  0.  0.  1.
1.  0.  0.  1.
1.  0.  0.  1.
1.  0.  0.  1.
1.  0.  0.  1.

A positive number followed by a negative one indicates a non-leaf node in the tree. The positive number equals the dim_node value (if they are all the same) and the negative number tells how many children are under this node. The definition starts at the root node. Three positive integers encode a leaf, the first number if the dimension at the leaf, the second is a type specifier for a basis set that corresponds to the leafs and the third is a leaf-index. The block of doubles at the end of the definition encodes parameters for the basis set of the leaf.

The Tree can be inspected via

tree.info();

Tree Handling

The most common way of accessing nodes in the tree is via so-called bottom-up or top-down swipes through the tree. In this notation the root node is considered the topnode and bottomlayer nodes are the ones over a leaf. A bottom-up swipe is performed by

for (const Node& node : tree) {
    // Do something, here just print some info
    node.info();
}
// or alternatively
for (size_t i = 0; i < tree.nLeaves(); ++i) {
    const Node& node = tree.getLeaf(i);
}

A top-down swipe is performed using the backwards iterator

for (const auto& it = tree.rbegin(); it != tree.rend(); ++it) {
    const Node& node = *it;
}
// or alternatively
for (int i = tree.nLeaves() - 1; i >= 0; --i) {
    const Node& node = tree.getLeaf(i);
}

Node that in the last example we use an integer, since i can become negative.

The location of the nodes in the tree can be accessed by

for (const Node& node : tree) {
    if (node.isToplayer()) {
        // do something for the root-node
    } else if (node.isBottomlayer()) {
        // do something for the bottomlayer nodes
    } else {
        // do something for "middlelayer" nodes, i.e. all other ones
    }
}

Parents and children of a node can be accessed via

for (const Node& node : tree) {
    if (!node.isToplayer()) {
        const Node& parent = node.parent();
        // do something for node's parent
    }

    if (!node.isBottomlayer()) {
        for (size_t k = 0; k < node.nChildren(); ++k) {
            const Node& child = node.child(k);
            // do something for node's k-th child
        }
    }
}

Leaf Interfaces

LeafInterfaces are used to map the library to a specific problem’s implemenmtation. Typical examples for LeafInterface are primitive basis functions like Harmonic Oscillator or Legendre polynomials or FFT-grids, spin basis sets and so on. Bottomlayer nodes can grant access to the underlying Leaf and the LeafInterface can grant access to the LeafInterface

for (const Node& node : tree) {
    if (!node.isBottomlayer()) {
        const Leaf& leaf = node.getLeaf();
        const LeafInterface& interface = leaf.PrimitiveGrid();
        // do something with the interface..
        // For example, check whether its a DVR and if so: get the grid points
        if (interface.HasDVR()) {
            const Vectord& x = interface.getX();
            node.info();
            x.print();
        }
    }
}

Other relevant application examples of the leaf interface include fundamental operators (x, x^2 , p, kinetic energy, …) of the specific basis sets. If you want to design your own basis, you can create a new class in which inherits from LeafInterface or one of the already existing basis sets and define how operators are applied and so on.

There is obviously much more that can be done with these interfaces, but we will not go into more detail here.

Further Information

The above examples cover the most important functionality of the Tree. These examples should provide an introduction to the classes defined in include/Treeshape directory. If you want more information or see some details, please take a look at the headers and implementations.