A toolkit for working with phylogenetic data.
v0.24.0
Tree Class Reference

#include <genesis/tree/tree.hpp>

Detailed Description

Class for representing phylogenetic trees.

A tree in this implementation consists of three types of elements: Links, Nodes and Edges. The topoloty of the tree is completely described by the links, while nodes and edges add the capability to store data on the tree.

Data in the Tree is not directly stored in the elements (Links, Nodes, Edges) of the Tree. Instead, data belonging to nodes and edges can be stored in their data pointers. For this, the data classes need to derive from BaseNodeData and BaseEdgeData, respectively.

Additional information concerning the whole tree, as well as special algorithms working on the tree and its data are also not direct members of the tree - for reasons of flexibility and extensibility: Instead of adding more and more data and algorithms to the tree, we create new classes that encapsulate a tree and all the other needed code to work with it. See the Sample class for an example.

Thus, the tree itself only contains the needed information to store and work with a topology.

This class has several redundant ways of representing the same information. On the one hand, this makes using a Tree easy, as one can chose the representaion of data that best fits a given task. On the other hand, maintaining all those invariants when changing the tree topology is tedious. Here is a (comprehensive?) list of invariants of this class:

  • The indices in all three arrays (nodes(), links() and edges()) have to match the index integers stored in those elements: node_at(i).index() == i.
  • The link that is stored in a node has to be the one pointing towards the root.
  • The primary link of an edge has to point towards the root, the secondary away from it.

Those invariants are established when the Tree is constructed.

Definition at line 97 of file tree/tree.hpp.

Public Member Functions

 Tree ()=default
 
 Tree (Tree const &other)
 Copy constructor. More...
 
 Tree (Tree &&)=default
 
 ~Tree ()=default
 
IteratorEdges begin_edges ()
 
ConstIteratorEdges begin_edges () const
 
IteratorLinks begin_links ()
 
ConstIteratorLinks begin_links () const
 
IteratorNodes begin_nodes ()
 
ConstIteratorNodes begin_nodes () const
 
void clear ()
 Deletes all data of the tree, including all links, nodes and edges. More...
 
Tree clone_topology () const
 Return a Tree with the same topology, but without any data. More...
 
TreeEdgeedge_at (size_t index)
 Return the TreeEdge at a certain index. More...
 
TreeEdge const & edge_at (size_t index) const
 Return the TreeEdge at a certain index. More...
 
size_t edge_count () const
 Return the number of TreeEdges of the Tree. More...
 
utils::Range< IteratorEdgesedges ()
 
utils::Range< ConstIteratorEdgesedges () const
 
bool empty () const
 Return whether the Tree is empty (i.e., has no nodes, edges and links). More...
 
IteratorEdges end_edges ()
 
ConstIteratorEdges end_edges () const
 
IteratorLinks end_links ()
 
ConstIteratorLinks end_links () const
 
IteratorNodes end_nodes ()
 
ConstIteratorNodes end_nodes () const
 
EdgeContainerTypeexpose_edge_container ()
 Get the container that stores all TreeEdges of the Tree. More...
 
LinkContainerTypeexpose_link_container ()
 Get the container that stores all TreeLinks of the Tree. More...
 
NodeContainerTypeexpose_node_container ()
 Get the container that stores all TreeNodes of the Tree. More...
 
TreeLinklink_at (size_t index)
 Return the TreeLink at a certain index. More...
 
TreeLink const & link_at (size_t index) const
 Return the TreeLink at a certain index. More...
 
size_t link_count () const
 Return the number of TreeLinks of the Tree. More...
 
utils::Range< IteratorLinkslinks ()
 
utils::Range< ConstIteratorLinkslinks () const
 
TreeNodenode_at (size_t index)
 Return the TreeNode at a certain index. More...
 
TreeNode const & node_at (size_t index) const
 Return the TreeNode at a certain index. More...
 
size_t node_count () const
 Return the number of TreeNodes of the Tree. More...
 
utils::Range< IteratorNodesnodes ()
 
utils::Range< ConstIteratorNodesnodes () const
 
Treeoperator= (Tree const &other)
 Assignment operator. More...
 
Treeoperator= (Tree &&)=default
 
Treereset_root_link (TreeLink *root_link)
 Reset the link that is considered to be the root of the Tree. More...
 
TreeLinkroot_link ()
 Return the TreeLink at the current root of the Tree. More...
 
TreeLink const & root_link () const
 Return the TreeLink at the current root of the Tree. More...
 
TreeNoderoot_node ()
 Return the TreeNode at the current root of the Tree. More...
 
TreeNode const & root_node () const
 Return the TreeNode at the current root of the Tree. More...
 
void swap (Tree &other)
 Swap. More...
 

Public Types

using ConstIteratorEdges = utils::DereferenceIterator< ContainerType< TreeEdge >::const_iterator >
 
using ConstIteratorLinks = utils::DereferenceIterator< ContainerType< TreeLink >::const_iterator >
 
using ConstIteratorNodes = utils::DereferenceIterator< ContainerType< TreeNode >::const_iterator >
 
template<class T >
using ContainerType = std::vector< std::unique_ptr< T > >
 Alias for the container type that is used to store TreeLinks, TreeNodes and TreeEdges. More...
 
using EdgeContainerType = ContainerType< TreeEdge >
 Alias for the container type that is used to store TreeEdges. More...
 
using IteratorEdges = utils::DereferenceIterator< ContainerType< TreeEdge >::iterator >
 
using IteratorLinks = utils::DereferenceIterator< ContainerType< TreeLink >::iterator >
 
using IteratorNodes = utils::DereferenceIterator< ContainerType< TreeNode >::iterator >
 
using LinkContainerType = ContainerType< TreeLink >
 Alias for the container type that is used to store TreeLinks. More...
 
using NodeContainerType = ContainerType< TreeNode >
 Alias for the container type that is used to store TreeNodes. More...
 

Friends

bool validate_topology (Tree const &tree)
 Validate the correctness of all Tree pointers etc. More...
 

Constructor & Destructor Documentation

◆ Tree() [1/3]

Tree ( )
default

◆ ~Tree()

~Tree ( )
default

◆ Tree() [2/3]

Tree ( Tree const &  other)

Copy constructor.

This function creates all links, nodes and edges new, and shapes them so that the final Tree has the same topology as the input Tree.

The data belonging to the edges and nodes is copied using the clone function of the respective data classes for the nodes and edges. As this data might contain pointers and other structures that need a deep copy, it is the responsibility of the clone function of those data classes to make sure its own data is copied correctly.

This function internally uses clone_topology() first, and then uses the clone functions of the data for all nodes and edges.

Definition at line 50 of file tree/tree.cpp.

◆ Tree() [3/3]

Tree ( Tree &&  )
default

Member Function Documentation

◆ begin_edges() [1/2]

IteratorEdges begin_edges ( )
inline

Definition at line 432 of file tree/tree.hpp.

◆ begin_edges() [2/2]

ConstIteratorEdges begin_edges ( ) const
inline

Definition at line 437 of file tree/tree.hpp.

◆ begin_links() [1/2]

IteratorLinks begin_links ( )
inline

Definition at line 364 of file tree/tree.hpp.

◆ begin_links() [2/2]

ConstIteratorLinks begin_links ( ) const
inline

Definition at line 369 of file tree/tree.hpp.

◆ begin_nodes() [1/2]

IteratorNodes begin_nodes ( )
inline

Definition at line 398 of file tree/tree.hpp.

◆ begin_nodes() [2/2]

ConstIteratorNodes begin_nodes ( ) const
inline

Definition at line 403 of file tree/tree.hpp.

◆ clear()

void clear ( )

Deletes all data of the tree, including all links, nodes and edges.

This functions results in an empty tree.

Definition at line 172 of file tree/tree.cpp.

◆ clone_topology()

Tree clone_topology ( ) const

Return a Tree with the same topology, but without any data.

All data pointers of the nodes and edges of the returned tree are nullptr.

Definition at line 109 of file tree/tree.cpp.

◆ edge_at() [1/2]

TreeEdge& edge_at ( size_t  index)
inline

Return the TreeEdge at a certain index.

Definition at line 238 of file tree/tree.hpp.

◆ edge_at() [2/2]

TreeEdge const& edge_at ( size_t  index) const
inline

Return the TreeEdge at a certain index.

Definition at line 247 of file tree/tree.hpp.

◆ edge_count()

size_t edge_count ( ) const
inline

Return the number of TreeEdges of the Tree.

Definition at line 272 of file tree/tree.hpp.

◆ edges() [1/2]

utils::Range<IteratorEdges> edges ( )
inline

Definition at line 452 of file tree/tree.hpp.

◆ edges() [2/2]

utils::Range<ConstIteratorEdges> edges ( ) const
inline

Definition at line 457 of file tree/tree.hpp.

◆ empty()

bool empty ( ) const
inline

Return whether the Tree is empty (i.e., has no nodes, edges and links).

Definition at line 194 of file tree/tree.hpp.

◆ end_edges() [1/2]

IteratorEdges end_edges ( )
inline

Definition at line 442 of file tree/tree.hpp.

◆ end_edges() [2/2]

ConstIteratorEdges end_edges ( ) const
inline

Definition at line 447 of file tree/tree.hpp.

◆ end_links() [1/2]

IteratorLinks end_links ( )
inline

Definition at line 374 of file tree/tree.hpp.

◆ end_links() [2/2]

ConstIteratorLinks end_links ( ) const
inline

Definition at line 379 of file tree/tree.hpp.

◆ end_nodes() [1/2]

IteratorNodes end_nodes ( )
inline

Definition at line 408 of file tree/tree.hpp.

◆ end_nodes() [2/2]

ConstIteratorNodes end_nodes ( ) const
inline

Definition at line 413 of file tree/tree.hpp.

◆ expose_edge_container()

Tree::EdgeContainerType & expose_edge_container ( )

Get the container that stores all TreeEdges of the Tree.

This function gives direct access to the underlying container for the Links. It is meant to be used by external functions that need to manupulate the Tree, e.g., for reading or re-rooting the tree, or for adding elements to it. Use with care!

Definition at line 202 of file tree/tree.cpp.

◆ expose_link_container()

Tree::LinkContainerType & expose_link_container ( )

Get the container that stores all TreeLinks of the Tree.

This function gives direct access to the underlying container for the Links. It is meant to be used by external functions that need to manupulate the Tree, e.g., for reading or re-rooting the tree, or for adding elements to it. Use with care!

Definition at line 192 of file tree/tree.cpp.

◆ expose_node_container()

Tree::NodeContainerType & expose_node_container ( )

Get the container that stores all TreeNodes of the Tree.

This function gives direct access to the underlying container for the Links. It is meant to be used by external functions that need to manupulate the Tree, e.g., for reading or re-rooting the tree, or for adding elements to it. Use with care!

Definition at line 197 of file tree/tree.cpp.

◆ link_at() [1/2]

TreeLink& link_at ( size_t  index)
inline

Return the TreeLink at a certain index.

Definition at line 202 of file tree/tree.hpp.

◆ link_at() [2/2]

TreeLink const& link_at ( size_t  index) const
inline

Return the TreeLink at a certain index.

Definition at line 211 of file tree/tree.hpp.

◆ link_count()

size_t link_count ( ) const
inline

Return the number of TreeLinks of the Tree.

Definition at line 256 of file tree/tree.hpp.

◆ links() [1/2]

utils::Range<IteratorLinks> links ( )
inline

Definition at line 384 of file tree/tree.hpp.

◆ links() [2/2]

utils::Range<ConstIteratorLinks> links ( ) const
inline

Definition at line 389 of file tree/tree.hpp.

◆ node_at() [1/2]

TreeNode& node_at ( size_t  index)
inline

Return the TreeNode at a certain index.

Definition at line 220 of file tree/tree.hpp.

◆ node_at() [2/2]

TreeNode const& node_at ( size_t  index) const
inline

Return the TreeNode at a certain index.

Definition at line 229 of file tree/tree.hpp.

◆ node_count()

size_t node_count ( ) const
inline

Return the number of TreeNodes of the Tree.

Definition at line 264 of file tree/tree.hpp.

◆ nodes() [1/2]

utils::Range<IteratorNodes> nodes ( )
inline

Definition at line 418 of file tree/tree.hpp.

◆ nodes() [2/2]

utils::Range<ConstIteratorNodes> nodes ( ) const
inline

Definition at line 423 of file tree/tree.hpp.

◆ operator=() [1/2]

Tree & operator= ( Tree const &  other)

Assignment operator.

See Tree copy constructor for more information.

Definition at line 96 of file tree/tree.cpp.

◆ operator=() [2/2]

Tree& operator= ( Tree &&  )
default

◆ reset_root_link()

Tree & reset_root_link ( TreeLink root_link)

Reset the link that is considered to be the root of the Tree.

This function is meant for tree manipulation functions. Use with care!

Caveat: This function simply sets the link, but does not change any other properties of the tree. Particularly the correct primary/secondary order of TreeEdges and primary links of TreeNodes needs to be maintained manually when using this function! Otherwise, we end up with an invalid Tree that breaks its invariants!

Definition at line 184 of file tree/tree.cpp.

◆ root_link() [1/2]

TreeLink& root_link ( )
inline

Return the TreeLink at the current root of the Tree.

Definition at line 284 of file tree/tree.hpp.

◆ root_link() [2/2]

TreeLink const& root_link ( ) const
inline

Return the TreeLink at the current root of the Tree.

Definition at line 292 of file tree/tree.hpp.

◆ root_node() [1/2]

TreeNode& root_node ( )
inline

Return the TreeNode at the current root of the Tree.

Definition at line 300 of file tree/tree.hpp.

◆ root_node() [2/2]

TreeNode const& root_node ( ) const
inline

Return the TreeNode at the current root of the Tree.

Definition at line 308 of file tree/tree.hpp.

◆ swap()

void swap ( Tree other)

Swap.

Definition at line 161 of file tree/tree.cpp.

Friends And Related Function Documentation

◆ validate_topology

bool validate_topology ( Tree const &  tree)
friend

Validate the correctness of all Tree pointers etc.

This function is defined in tree/functions/operators.hpp

This check is a bit pedantic, but better safe than sorry.

Definition at line 366 of file tree/function/operators.cpp.

Member Typedef Documentation

◆ ConstIteratorEdges

Definition at line 134 of file tree/tree.hpp.

◆ ConstIteratorLinks

Definition at line 128 of file tree/tree.hpp.

◆ ConstIteratorNodes

Definition at line 131 of file tree/tree.hpp.

◆ ContainerType

using ContainerType = std::vector< std::unique_ptr< T > >

Alias for the container type that is used to store TreeLinks, TreeNodes and TreeEdges.

Definition at line 110 of file tree/tree.hpp.

◆ EdgeContainerType

Alias for the container type that is used to store TreeEdges.

Definition at line 125 of file tree/tree.hpp.

◆ IteratorEdges

Definition at line 133 of file tree/tree.hpp.

◆ IteratorLinks

Definition at line 127 of file tree/tree.hpp.

◆ IteratorNodes

Definition at line 130 of file tree/tree.hpp.

◆ LinkContainerType

Alias for the container type that is used to store TreeLinks.

Definition at line 115 of file tree/tree.hpp.

◆ NodeContainerType

Alias for the container type that is used to store TreeNodes.

Definition at line 120 of file tree/tree.hpp.


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