A toolkit for working with phylogenetic data.
v0.18.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
NewickBroker Class Reference

#include <genesis/tree/formats/newick/broker.hpp>

Detailed Description

Stores a Newick tree in an intermediate format that can be further processed into a Tree.

The NewickBroker is a transitional format between the Newick formatted tree and a Tree object. It is neccessary to have this intermediate step, because the ordering of nodes in the Newick format differs from our requirements. Newick trees starts with leaf nodes, while our internal representation is build up from the root.

The NewickBroker is organized as a stack, where the root of the tree is at the top/front. Then follow the nodes in a preorder manner, where each node is of type NewickBrokerElement.

The topology of the tree is represented via a depth attribute of each node: Two subsequent nodes are siblings (belong to the same parent node), if they have the same depth. If the second node has a depth that is one higher than the first ones, it is it's child (depth thus cannot increase more than one between two nodes). Lastly, if the depth of the second node is smaller than the first ones, it belongs to a different subtree.

For example, the following tree in Newick format:

((A,((B,C,D)E,F)G)H,((I,J,K)L,M,N)O,P,Q)R;

would be stored as the following stack:

R Rank(4)
    Q (Leaf)
    P (Leaf)
    O Rank(3)
        N (Leaf)
        M (Leaf)
        L Rank(3)
            K (Leaf)
            J (Leaf)
            I (Leaf)
    H Rank(2)
        G Rank(2)
            F (Leaf)
            E Rank(3)
                D (Leaf)
                C (Leaf)
                B (Leaf)
        A (Leaf)

Here, the rank represents the number of immediate children of this node. Leaf nodes have no children and thus rank zero.

Every function modifiying the content of the broker is required to leave it in a valid state, meaning:

  • The top node has to be the root of the tree, which is equivalent to having depth zero. This is also true for trees rooted on a leaf.
  • The nesting of the nodes has to be correct, so the depth cannot increase more than one per node when going down the tree.
  • The attribute NewickBrokerElement::is_leaf of the NewickBrokerElements can be set (for exmaple when parsing a Newick tree) and then be used to validate the integrity of the tree using validate(). However, the attribute is not further used – see its description for more on this. %

Definition at line 106 of file broker.hpp.

Public Member Functions

 NewickBroker ()=default
 
 NewickBroker (NewickBroker const &)=default
 
 NewickBroker (NewickBroker &&)=default
 
 ~NewickBroker ()=default
 
void assign_ranks () const
 Iterate over the tree and assign ranks (= number of immediate children) to all nodes. More...
 
NewickBrokerElementat (std::size_t index)
 Provides index based array access to the nodes, doing a boundary check first. More...
 
NewickBrokerElement const & at (std::size_t index) const
 
iterator begin ()
 Returns an iterator to the top of the stack. More...
 
const_iterator begin () const
 Returns an iterator to the top of the stack for const objects. More...
 
NewickBrokerElementbottom ()
 Returns a reference to the bottom node of the tree stack. More...
 
NewickBrokerElement const & bottom () const
 
const_iterator cbegin () const
 Const version of begin(). More...
 
const_iterator cend () const
 Const version of end(). More...
 
void clear ()
 Deletes all nodes from the broker. More...
 
const_reverse_iterator crbegin ()
 Const version of rbegin(). More...
 
const_reverse_iterator crend ()
 Const version of rend(). More...
 
std::string dump () const
 Return a readable string representation of the elements of the NewickBroker. More...
 
bool empty () const
 Returns whether the stack is empty. More...
 
iterator end ()
 Returns an iterator to the end of the token list. More...
 
const_iterator end () const
 Returns an iterator to the end of the token list for const objects. More...
 
int inner_count () const
 
bool is_bifurcating () const
 
int leaf_count () const
 Returns the number of leaf nodes in the tree. assign_ranks() has to be called first. More...
 
int max_rank () const
 Returns the highest rank of the nodes in the tree. assign_ranks() has to be called first. More...
 
int node_count () const
 Alias for size(). More...
 
NewickBrokeroperator= (NewickBroker const &)=default
 
NewickBrokeroperator= (NewickBroker &&)=default
 
NewickBrokerElementoperator[] (std::size_t index)
 Provides index based array access to the nodes. More...
 
NewickBrokerElement const & operator[] (std::size_t index) const
 
void pop_bottom ()
 
void pop_top ()
 
void push_bottom (NewickBrokerElement const &node)
 
void push_bottom (NewickBrokerElement &&node)
 
void push_top (NewickBrokerElement const &node)
 
void push_top (NewickBrokerElement &&node)
 
reverse_iterator rbegin ()
 Returns a reverse iterator to the nodes on the stack. More...
 
const_reverse_iterator rbegin () const
 Returns a reverse iterator to the nodes on the stack for const objects. More...
 
reverse_iterator rend ()
 Reverse version of end(). More...
 
const_reverse_iterator rend () const
 Reverse version of end() for const objects. More...
 
size_t size () const
 Returns the size of the stack, i.e. the number of nodes stored in the broker. More...
 
NewickBrokerElementtop ()
 Returns a reference to the top node of the tree stack. More...
 
NewickBrokerElement const & top () const
 
bool validate () const
 Returns true iff the tree is valid. assign_ranks() has to be called first. More...
 

Public Types

typedef std::deque
< NewickBrokerElement >
::const_iterator 
const_iterator
 
typedef std::deque
< NewickBrokerElement >
::const_reverse_iterator 
const_reverse_iterator
 
typedef std::deque
< NewickBrokerElement >
::iterator 
iterator
 
typedef std::deque
< NewickBrokerElement >
::reverse_iterator 
reverse_iterator
 

Constructor & Destructor Documentation

NewickBroker ( )
default
~NewickBroker ( )
default
NewickBroker ( NewickBroker const &  )
default
NewickBroker ( NewickBroker &&  )
default

Member Function Documentation

void assign_ranks ( ) const

Iterate over the tree and assign ranks (= number of immediate children) to all nodes.

This function is for example needed to check whether it is a bifurcating/binary tree, or to check how many leaves and inner nodes the tree has. Thus, it is usually called after the broker is filled with data.

Definition at line 85 of file broker.cpp.

NewickBrokerElement & at ( std::size_t  index)

Provides index based array access to the nodes, doing a boundary check first.

In out of bounds cases, an exception is thrown.

Definition at line 194 of file broker.cpp.

NewickBrokerElement const & at ( std::size_t  index) const

Definition at line 202 of file broker.cpp.

Returns an iterator to the top of the stack.

Definition at line 234 of file broker.cpp.

Returns an iterator to the top of the stack for const objects.

Definition at line 239 of file broker.cpp.

NewickBrokerElement & bottom ( )

Returns a reference to the bottom node of the tree stack.

Calling this function on an empty() broker causes undefined behavior.

Definition at line 220 of file broker.cpp.

NewickBrokerElement const & bottom ( ) const

Definition at line 225 of file broker.cpp.

NewickBroker::const_iterator cbegin ( ) const

Const version of begin().

Definition at line 254 of file broker.cpp.

Const version of end().

Definition at line 259 of file broker.cpp.

void clear ( )

Deletes all nodes from the broker.

Definition at line 46 of file broker.cpp.

Const version of rbegin().

Definition at line 284 of file broker.cpp.

Const version of rend().

Definition at line 289 of file broker.cpp.

std::string dump ( ) const

Return a readable string representation of the elements of the NewickBroker.

Definition at line 324 of file broker.cpp.

bool empty ( ) const

Returns whether the stack is empty.

Definition at line 170 of file broker.cpp.

Returns an iterator to the end of the token list.

Definition at line 244 of file broker.cpp.

Returns an iterator to the end of the token list for const objects.

Definition at line 249 of file broker.cpp.

int inner_count ( ) const

Definition at line 136 of file broker.cpp.

bool is_bifurcating ( ) const

Definition at line 161 of file broker.cpp.

int leaf_count ( ) const

Returns the number of leaf nodes in the tree. assign_ranks() has to be called first.

Definition at line 122 of file broker.cpp.

int max_rank ( ) const

Returns the highest rank of the nodes in the tree. assign_ranks() has to be called first.

Definition at line 146 of file broker.cpp.

int node_count ( ) const

Alias for size().

Definition at line 141 of file broker.cpp.

NewickBroker& operator= ( NewickBroker const &  )
default
NewickBroker& operator= ( NewickBroker &&  )
default
NewickBrokerElement & operator[] ( std::size_t  index)

Provides index based array access to the nodes.

This also allows to iterate over them using:

NewickBroker tb;
for (size_t i = 0; i < tb.size(); ++i) {
   NewickBrokerElement* tn = tb[i];
   std::cout << tn.name << std::endl;
}

Caveat: this operator does no boundary check. If you need this check, use at() instead.

Definition at line 184 of file broker.cpp.

NewickBrokerElement const & operator[] ( std::size_t  index) const

Definition at line 189 of file broker.cpp.

void pop_bottom ( )

Definition at line 76 of file broker.cpp.

void pop_top ( )

Definition at line 71 of file broker.cpp.

void push_bottom ( NewickBrokerElement const &  node)

Definition at line 61 of file broker.cpp.

void push_bottom ( NewickBrokerElement &&  node)

Definition at line 66 of file broker.cpp.

void push_top ( NewickBrokerElement const &  node)

Definition at line 51 of file broker.cpp.

void push_top ( NewickBrokerElement &&  node)

Definition at line 56 of file broker.cpp.

Returns a reverse iterator to the nodes on the stack.

Definition at line 264 of file broker.cpp.

Returns a reverse iterator to the nodes on the stack for const objects.

Definition at line 269 of file broker.cpp.

Reverse version of end().

Definition at line 274 of file broker.cpp.

Reverse version of end() for const objects.

Definition at line 279 of file broker.cpp.

size_t size ( ) const

Returns the size of the stack, i.e. the number of nodes stored in the broker.

Definition at line 175 of file broker.cpp.

Returns a reference to the top node of the tree stack.

Usually, the top element is the root of the tree (i.e., it has depth zero). Only when called during the broker is being filled with nodes (for example, while parsing a Newick tree), the top element is not the root.

Calling this function on an empty() broker causes undefined behavior.

Definition at line 210 of file broker.cpp.

NewickBrokerElement const & top ( ) const

Definition at line 215 of file broker.cpp.

bool validate ( ) const

Returns true iff the tree is valid. assign_ranks() has to be called first.

A valid tree in a NewickBroker has to fullfill those criteria:

  • The depth (nesting level) of the nodes cannot increase more than one level between nodes, as this would imply a non-existing node with a depth in between. However, it can arbitrarily decrease, as this simply means the end of a subtree.
  • Furthermore, rank 1 is not valid, as this represents a node that is not furcating in any way. %

Definition at line 299 of file broker.cpp.

Member Typedef Documentation

Definition at line 115 of file broker.hpp.

Definition at line 117 of file broker.hpp.

typedef std::deque<NewickBrokerElement>::iterator iterator

Definition at line 114 of file broker.hpp.

Definition at line 116 of file broker.hpp.


The documentation for this class was generated from the following files: