Create a Newick tree description

Newick's Lobster House, Dover, New Hampshire
Newick’s Restaurant

Newick’s Lobster House was the site of an historic 1986 meeting (see Joe Felsenstein’s account) at which a standard was devised for storing descriptions of phylogenetic trees as strings. These newick tree descriptions (also called the "New Hampshire" format) became part of the NEXUS file format (described in Maddison, Swofford, and Maddison, 1997), which is a standard file format for storing systematic data that is still widely used despite the advent of NexML.

Our next goal is to create a newick string for the tree currently stored in a TreeManip object. Add the function declaration in the public area of the TreeManip class declaration:

std::string  makeNewick(unsigned precision) const;

Now add the function body just above the terminating curly bracket of the namespace (i.e. just before the end of the file):

template <class T>
inline std::string TreeManip<T>::makeNewick(unsigned precision) const
	{
    std::string newick;
    const boost::format tip_node_format( boost::str(boost::format("%%d:%%.%df") % precision) );
    const boost::format internal_node_format( boost::str(boost::format("):%%.%df") % precision) );
    std::stack<T *> node_stack;
    
    T * root_tip = (_tree->_is_rooted ? 0 : _tree->getRoot());
    typename std::vector<T *>::const_iterator it = _tree->_preorder.begin();
    for (; it != _tree->_preorder.end(); ++it)
        {
        T * nd = *it;
        if (nd->_left_child)
            {
            newick += "(";
            node_stack.push(nd);
            if (root_tip)
                {
                newick += boost::str(boost::format(tip_node_format) % (root_tip->_number + 1) % nd->_edge_length);
                newick += ",";
                root_tip = 0;
                }
            }
        else
            {
            newick += boost::str(boost::format(tip_node_format) % (nd->_number + 1) % nd->_edge_length);
            if (nd->_right_sib)
                newick += ",";
            else
                {
                T * popped = (node_stack.empty() ? 0 : node_stack.top());
                while (!node_stack.empty() && !popped->_right_sib)
                    {
                    node_stack.pop();
                    if (node_stack.empty())
                        {
                        newick += ")";
                        popped = 0;
                        }
                    else
                        {
                        newick += boost::str(boost::format(internal_node_format) % popped->_edge_length);
                        popped = node_stack.top();
                        }
                    }
                if (popped && popped->_right_sib)
                    {
                    node_stack.pop();
                    newick += boost::str(boost::format(internal_node_format) % popped->_edge_length);
                    newick += ",";
                    }
                }
            }
        }
    
    return newick;
    }

To test the new function, add the following line to main.cpp (after createTestTree() is called):

std::cout << tm.makeNewick(3) << std::endl;

You should see the following additional line appear in the output when the program is run:

(((4:0.100,5:0.100):0.100,6:0.100):0.100)

Note that 3 decimal places are used in outputting edge lengths because you supplied 3 as an argument to the makeNewick function.

References

Maddison D., Swofford D.L., Maddison W. 1997. NEXUS: An extensible file format for systematic information. Systematic Biology. 46:590–617. DOI: 10.1093/sysbio/46.4.590