#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 &&)=default

	Tree (Tree const &other)
	Copy constructor. More...

	~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...

TreeEdge &	edge_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< IteratorEdges >	edges ()

utils::Range< ConstIteratorEdges >	edges () 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

EdgeContainerType &	expose_edge_container ()
	Get the container that stores all TreeEdges of the Tree. More...

LinkContainerType &	expose_link_container ()
	Get the container that stores all TreeLinks of the Tree. More...

NodeContainerType &	expose_node_container ()
	Get the container that stores all TreeNodes of the Tree. More...

TreeLink &	link_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< IteratorLinks >	links ()

utils::Range< ConstIteratorLinks >	links () const

TreeNode &	node_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< IteratorNodes >	nodes ()

utils::Range< ConstIteratorNodes >	nodes () const

Tree &	operator= (Tree &&)=default

Tree &	operator= (Tree const &other)
	Assignment operator. More...

Tree &	reset_root_link (TreeLink *root_link)
	Reset the link that is considered to be the root of the Tree. More...

TreeLink &	root_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...

TreeNode &	root_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 && )

default

◆ operator=() [2/2]

Tree & operator= ( Tree const & other )

Assignment operator.

See Tree copy constructor for more information.

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

◆ 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 332 of file tree/function/operators.cpp.

Member Typedef Documentation

◆ ConstIteratorEdges

using ConstIteratorEdges = utils::DereferenceIterator< ContainerType<TreeEdge>::const_iterator >

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

◆ ConstIteratorLinks

using ConstIteratorLinks = utils::DereferenceIterator< ContainerType<TreeLink>::const_iterator >

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

◆ ConstIteratorNodes

using ConstIteratorNodes = utils::DereferenceIterator< ContainerType<TreeNode>::const_iterator >

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

using EdgeContainerType = ContainerType< TreeEdge >

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

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

◆ IteratorEdges

using IteratorEdges = utils::DereferenceIterator< ContainerType<TreeEdge>::iterator >

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

◆ IteratorLinks

using IteratorLinks = utils::DereferenceIterator< ContainerType<TreeLink>::iterator >

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

◆ IteratorNodes

using IteratorNodes = utils::DereferenceIterator< ContainerType<TreeNode>::iterator >

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

◆ LinkContainerType

using LinkContainerType = ContainerType< TreeLink >

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

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

◆ NodeContainerType

using NodeContainerType = ContainerType< TreeNode >

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:

Detailed Description

Public Member Functions

Public Types

Friends

Constructor & Destructor Documentation

◆ Tree() [1/3]

◆ ~Tree()

◆ Tree() [2/3]

◆ Tree() [3/3]

Member Function Documentation

◆ begin_edges() [1/2]

◆ begin_edges() [2/2]

◆ begin_links() [1/2]

◆ begin_links() [2/2]

◆ begin_nodes() [1/2]

◆ begin_nodes() [2/2]

◆ clear()

◆ clone_topology()

◆ edge_at() [1/2]

◆ edge_at() [2/2]

◆ edge_count()

◆ edges() [1/2]

◆ edges() [2/2]

◆ empty()

◆ end_edges() [1/2]

◆ end_edges() [2/2]

◆ end_links() [1/2]

◆ end_links() [2/2]

◆ end_nodes() [1/2]

◆ end_nodes() [2/2]

◆ expose_edge_container()

◆ expose_link_container()

◆ expose_node_container()

◆ link_at() [1/2]

◆ link_at() [2/2]

◆ link_count()

◆ links() [1/2]

◆ links() [2/2]

◆ node_at() [1/2]

◆ node_at() [2/2]

◆ node_count()

◆ nodes() [1/2]

◆ nodes() [2/2]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ reset_root_link()

◆ root_link() [1/2]

◆ root_link() [2/2]

◆ root_node() [1/2]

◆ root_node() [2/2]

◆ swap()

Friends And Related Function Documentation

◆ validate_topology

Member Typedef Documentation

◆ ConstIteratorEdges

◆ ConstIteratorLinks

◆ ConstIteratorNodes

◆ ContainerType

◆ EdgeContainerType

◆ IteratorEdges

◆ IteratorLinks

◆ IteratorNodes

◆ LinkContainerType

◆ NodeContainerType