3.1 Create a rooted, 3-taxon tree

(Linux version)

< 3.0 | 3.1 | 3.2 >

The next step is to add a function that creates a 3-taxon rooted tree. We will call this function from the Tree constructor in order to have a way to generate a test tree.

This way of generating a tree is admittedly tedious, and we will soon abandon it for a more general method that automatically creates trees from newick tree descriptions

Additions to tree.hpp

Most of the code below is already in your tree.hpp file. Just add the bold, blue text. Note that the clear() function call has been commented out in the Tree constructor.

#pragma once	

#include &lt;memory&gt;
#include &lt;iostream&gt;
#include "node.hpp"

namespace strom {

    //class TreeManip;
    //class Likelihood;
    //class Updater;

    class Tree {

            //friend class TreeManip;
            //friend class Likelihood;
            //friend class Updater;

        public:

                                        Tree();
                                        ~Tree();

            bool                        isRooted() const;
            unsigned                    numLeaves() const;
            unsigned                    numInternals() const;
            unsigned                    numNodes() const;

            <span style="color:#0000ff"><strong>void                        createTestTree();</strong></span>

        private:

            void                        clear();

            bool                        _is_rooted;
            Node *                      _root;
            unsigned                    _nleaves;
            unsigned                    _ninternals;
            Node::PtrVector             _preorder;
            Node::PtrVector             _levelorder;
            Node::Vector                _nodes;

        public:

            typedef std::shared_ptr&lt;Tree&gt; SharedPtr;
    };

    inline Tree::Tree() {
        std::cout &lt;&lt; "Constructing a Tree" &lt;&lt; std::endl;
        <span style="color:#0000ff"><strong>//clear();</strong></span>
        <span style="color:#0000ff"><strong>createTestTree();</strong></span>
    }

    inline Tree::~Tree() {
        std::cout &lt;&lt; "Destroying a Tree" &lt;&lt; std::endl;
    }

    inline void Tree::clear() {
        _is_rooted = false;
        _root = 0;
        _nodes.clear();
        _preorder.clear();
        _levelorder.clear();
    }

    inline bool Tree::isRooted() const {
        return _is_rooted;
    }

    inline unsigned Tree::numLeaves() const {
        return _nleaves;
    }

    inline unsigned Tree::numInternals() const {
        return _ninternals;
    }

    inline unsigned Tree::numNodes() const {
        return (unsigned)_nodes.size();
    }

    <span style="color:#0000ff"><strong>inline void Tree::createTestTree() {</strong></span>
        <span style="color:#0000ff"><strong>clear();</strong></span>
        <span style="color:#0000ff"><strong>_nodes.resize(6);</strong></span>

<span style="color:#0000ff"><strong></strong></span>
        <span style="color:#0000ff"><strong>Node * root_node       = &_nodes[0];</strong></span>
        <span style="color:#0000ff"><strong>Node * first_internal  = &_nodes[1];</strong></span>
        <span style="color:#0000ff"><strong>Node * second_internal = &_nodes[2];</strong></span>
        <span style="color:#0000ff"><strong>Node * first_leaf      = &_nodes[3];</strong></span>
        <span style="color:#0000ff"><strong>Node * second_leaf     = &_nodes[4];</strong></span>
        <span style="color:#0000ff"><strong>Node * third_leaf      = &_nodes[5];</strong></span>

<span style="color:#0000ff"><strong></strong></span>
        <span style="color:#0000ff"><strong>// Here is the structure of the tree (numbers in</strong></span>
        <span style="color:#0000ff"><strong>// parentheses are node numbers, other numbers</strong></span>
        <span style="color:#0000ff"><strong>// are edge lengths):</strong></span>
        <span style="color:#0000ff"><strong>//</strong></span>
        <span style="color:#0000ff"><strong>// first_leaf (0)   second_leaf (1)   third_leaf (2)</strong></span>
        <span style="color:#0000ff"><strong>//      \              /                  /</strong></span>
        <span style="color:#0000ff"><strong>//       \ 0.1        / 0.1              /</strong></span>
        <span style="color:#0000ff"><strong>//        \          /                  /</strong></span>
        <span style="color:#0000ff"><strong>//     second_internal (3)             / 0.2</strong></span>
        <span style="color:#0000ff"><strong>//             \                      /</strong></span>
        <span style="color:#0000ff"><strong>//              \ 0.1                /</strong></span>
        <span style="color:#0000ff"><strong>//               \                  /</strong></span>
        <span style="color:#0000ff"><strong>//                first_internal (4)</strong></span>
        <span style="color:#0000ff"><strong>//                        |</strong></span>
        <span style="color:#0000ff"><strong>//                        | 0.1</strong></span>
        <span style="color:#0000ff"><strong>//                        |</strong></span>
        <span style="color:#0000ff"><strong>//                    root_node (5)</strong></span>
        <span style="color:#0000ff"><strong>//</strong></span>
        <span style="color:#0000ff"><strong>root_node-&gt;_parent            = 0;</strong></span>
        <span style="color:#0000ff"><strong>root_node-&gt;_left_child        = first_internal;</strong></span>
        <span style="color:#0000ff"><strong>root_node-&gt;_right_sib         = 0;</strong></span>
        <span style="color:#0000ff"><strong>root_node-&gt;_number            = 5;</strong></span>
        <span style="color:#0000ff"><strong>root_node-&gt;_name              = "root node";</strong></span>
        <span style="color:#0000ff"><strong>root_node-&gt;_edge_length       = 0.0;</strong></span>

<span style="color:#0000ff"><strong></strong></span>
        <span style="color:#0000ff"><strong>first_internal-&gt;_parent       = root_node;</strong></span>
        <span style="color:#0000ff"><strong>first_internal-&gt;_left_child   = second_internal;</strong></span>
        <span style="color:#0000ff"><strong>first_internal-&gt;_right_sib    = 0;</strong></span>
        <span style="color:#0000ff"><strong>first_internal-&gt;_number       = 4;</strong></span>
        <span style="color:#0000ff"><strong>first_internal-&gt;_name         = "first internal node";</strong></span>
        <span style="color:#0000ff"><strong>first_internal-&gt;_edge_length  = 0.1;</strong></span>

<span style="color:#0000ff"><strong></strong></span>
        <span style="color:#0000ff"><strong>second_internal-&gt;_parent      = first_internal;</strong></span>
        <span style="color:#0000ff"><strong>second_internal-&gt;_left_child  = first_leaf;</strong></span>
        <span style="color:#0000ff"><strong>second_internal-&gt;_right_sib   = third_leaf;</strong></span>
        <span style="color:#0000ff"><strong>second_internal-&gt;_number      = 3;</strong></span>
        <span style="color:#0000ff"><strong>second_internal-&gt;_name        = "second internal node";</strong></span>
        <span style="color:#0000ff"><strong>second_internal-&gt;_edge_length = 0.1;</strong></span>

<span style="color:#0000ff"><strong></strong></span>
        <span style="color:#0000ff"><strong>first_leaf-&gt;_parent           = second_internal;</strong></span>
        <span style="color:#0000ff"><strong>first_leaf-&gt;_left_child       = 0;</strong></span>
        <span style="color:#0000ff"><strong>first_leaf-&gt;_right_sib        = second_leaf;</strong></span>
        <span style="color:#0000ff"><strong>first_leaf-&gt;_number           = 0;</strong></span>
        <span style="color:#0000ff"><strong>first_leaf-&gt;_name             = "first leaf";</strong></span>
        <span style="color:#0000ff"><strong>first_leaf-&gt;_edge_length      = 0.1;</strong></span>

<span style="color:#0000ff"><strong></strong></span>
        <span style="color:#0000ff"><strong>second_leaf-&gt;_parent          = second_internal;</strong></span>
        <span style="color:#0000ff"><strong>second_leaf-&gt;_left_child      = 0;</strong></span>
        <span style="color:#0000ff"><strong>second_leaf-&gt;_right_sib       = 0;</strong></span>
        <span style="color:#0000ff"><strong>second_leaf-&gt;_number          = 1;</strong></span>
        <span style="color:#0000ff"><strong>second_leaf-&gt;_name            = "second leaf";</strong></span>
        <span style="color:#0000ff"><strong>second_leaf-&gt;_edge_length     = 0.1;</strong></span>

<span style="color:#0000ff"><strong></strong></span>
        <span style="color:#0000ff"><strong>third_leaf-&gt;_parent           = first_internal;</strong></span>
        <span style="color:#0000ff"><strong>third_leaf-&gt;_left_child       = 0;</strong></span>
        <span style="color:#0000ff"><strong>third_leaf-&gt;_right_sib        = 0;</strong></span>
        <span style="color:#0000ff"><strong>third_leaf-&gt;_number           = 2;</strong></span>
        <span style="color:#0000ff"><strong>third_leaf-&gt;_name             = "third leaf";</strong></span>
        <span style="color:#0000ff"><strong>third_leaf-&gt;_edge_length      = 0.2;</strong></span>

<span style="color:#0000ff"><strong></strong></span>
        <span style="color:#0000ff"><strong>_is_rooted             = true;</strong></span>
        <span style="color:#0000ff"><strong>_root                  = root_node;</strong></span>
        <span style="color:#0000ff"><strong>_nleaves               = 3;</strong></span>

<span style="color:#0000ff"><strong></strong></span>
        <span style="color:#0000ff"><strong>// Note that root node is not included in _preorder</strong></span>
        <span style="color:#0000ff"><strong>_preorder.push_back(first_internal);</strong></span>
        <span style="color:#0000ff"><strong>_preorder.push_back(second_internal);</strong></span>
        <span style="color:#0000ff"><strong>_preorder.push_back(first_leaf);</strong></span>
        <span style="color:#0000ff"><strong>_preorder.push_back(second_leaf);</strong></span>
        <span style="color:#0000ff"><strong>_preorder.push_back(third_leaf);</strong></span>

<span style="color:#0000ff"><strong></strong></span>
        <span style="color:#0000ff"><strong>_levelorder.push_back(first_internal);</strong></span>
        <span style="color:#0000ff"><strong>_levelorder.push_back(second_internal);</strong></span>
        <span style="color:#0000ff"><strong>_levelorder.push_back(third_leaf);</strong></span>
        <span style="color:#0000ff"><strong>_levelorder.push_back(first_leaf);</strong></span>
        <span style="color:#0000ff"><strong>_levelorder.push_back(second_leaf);</strong></span>
    <span style="color:#0000ff"><strong>}</strong></span>
    
}

Explanation of createtesttree()

We’ve added a member function to the Tree class named createTestTree(), and this function is now called, instead of clear(), in the Tree constructor. Let’s go through this function to see how it creates a tree.

        _nodes.resize(6);

This line sets the size of the _nodes vector to 6. The Node constructor will be called 6 times when this line is executed because 6 Node objects are created, one for each of the first 6 elements of the _nodes vector.

        Node * root_node       = &_nodes[0];	
        Node * first_internal  = &_nodes[1];
        Node * second_internal = &_nodes[2];
        Node * first_leaf      = &_nodes[3];
        Node * second_leaf     = &_nodes[4];
        Node * third_leaf      = &_nodes[5];

These 6 lines create pointers to each of the 6 node objects stored in the _nodes vector. This will make it easier (and less error-prone) to hook up each node to its parent and children. Note the ampersand symbol (&): in your mind, replace the & symbol with the words memory address of. The asterisk symbol (*) means pointer, and Node * means pointer to an object of type Node. A pointer stores the memory address of an object. Thus, the pointer named root_node stores the memory address of the first element (element 0) of the _nodes vector.

        root_node-&gt;_parent            = 0;					
        root_node-&gt;_left_child        = first_internal;
        root_node-&gt;_right_sib         = 0;
        root_node-&gt;_number            = 5;
        root_node-&gt;_name              = "root node";
        root_node-&gt;_edge_length       = 0.0;

The lines above provide values for all the data members of the Node object pointed to by the root_node pointer. The arrow symbol (->) is used to specify a data member or method of an object when a pointer is used to refer to the object, while a dot (.) would be used if attributes are being set for the object directly. The root node has no parent and no right sibling, so we set these pointers to the value 0. The left child of the root node should point to the first internal node, and first_internal is a pointer to that node.

The other nodes are set up similarly according to the tree diagram given in the comments.

        _is_rooted             = true;		
        _root                  = root_node;
        _nleaves               = 3;

The above 3 lines set data members of the Tree class. We specify true for _is_rooted because we want this tree to be interpreted as a rooted tree (setting this to false would imply that the root node is really a leaf and observed data is associated with the root node).

        _preorder.push_back(first_internal);	
        _preorder.push_back(second_internal);
        _preorder.push_back(first_leaf);
        _preorder.push_back(second_leaf);
        _preorder.push_back(third_leaf);

The 5 lines above build up the _preorder vector one element at a time. Each element is a pointer to a Node object already stored in the _nodes vector. The order in which we push pointers onto _preorder is important. It is called _preorder because it stores nodes in preorder sequence (ancestral nodes visited before their children). One could walk through all the nodes of the tree in preorder sequence by simply iterating through this vector. Iterating through _preorder in reverse would walk the tree in postorder sequence (child nodes visited before their parents).

Important: note that the root node is not included in the _preorder vector. There are two reasons for this. First, we already have a pointer (_root) to the root node. Second, in most situations the root node either is ignored (rooted trees) or is treated specially (unrooted trees), so you will soon see that we almost always start iterating through nodes with the first (and only) child of the root node anyway: starting at the root node would only cause us to add extra lines to skip the root node.

        _levelorder.push_back(first_internal);	
        _levelorder.push_back(second_internal);
        _levelorder.push_back(third_leaf);
        _levelorder.push_back(first_leaf);
        _levelorder.push_back(second_leaf);

The _levelorder vector also stores a list of node pointers, but this time in level-order sequence rather than preorder sequence. Level-order sequence involves visiting all children of the current level before moving closer to the root in the tree. The reason why this sequence needs to be stored will be explained later when likelihoods are calculated.

< 3.0 | 3.1 | 3.2 >