Utilitary methods working with TreeTemplate and Node objects. More...

#include <Bpp/Phyl/Tree/TreeTemplateTools.h>

Classes
struct	Element

struct	Moments_
	A structure recording, for a subtree, the sum of root-leaf distances, the sum of their squares, and the number of elements in these sums (ie. the number of leaves). More...

struct	OrderTreeData_

Public Member Functions
	TreeTemplateTools ()

virtual	~TreeTemplateTools ()

Static Public Member Functions
static std::vector< const Node * >	getRemainingNeighbors (const Node node1, const Node node2, const Node *node3)
	Get a subset of node neighbors. More...

static void	incrementAllIds (Node *node, int increment)
	This method will add a given value (possibly negative) to all identifiers in a (sub)tree. More...

static void	orderTree (Node &node, bool downward=true, bool orderLeaves=false)
	Swap nodes in the subtree so that they are ordered according to the underlying number of leaves. More...

static void	midRoot (TreeTemplate< Node > &tree, short criterion, bool forceBranchRoot)
	Midroot the tree by minimizing a given criterion ("variance" or "sum of squares") More...

static double	getRadius (TreeTemplate< Node > &tree)
	Get the characteristic radius of a tree (average distance to the root minimizing the sum of squared distances). More...

static void	unresolveUncertainNodes (Node &subtree, double threshold, const std::string &property=TreeTools::BOOTSTRAP)
	Unresolve nodes with low confidence value. More...

Retrieve topology information
template<class N >
static std::vector< N * >	getLeaves (N &node)
	Retrieve all leaves from a subtree. More...

template<class N >
static void	getLeaves (N &node, std::vector< N * > &leaves)
	Retrieve all leaves from a subtree. More...

static std::vector< int >	getLeavesId (const Node &node)
	Retrieve all leaves ids from a subtree. More...

static void	getLeavesId (const Node &node, std::vector< int > &ids)
	Retrieve all leaves ids from a subtree. More...

static std::vector< int >	getAncestorsId (const Node &node)
	Retrieve all nodes ids that are ancestors of a node. More...

static int	getLeafId (const Node &node, const std::string &name)
	Get the id of a leaf given its name in a subtree. More...

static void	searchLeaf (const Node &node, const std::string &name, int *&id)
	Get the id of a leaf given its name in a subtree. More...

template<class N >
static void	dropLeaf (TreeTemplate< N > &tree, const std::string &leafName)
	Remove a leaf node and its parent node, while correcting for branch lengths. More...

template<class N >
static void	dropSubtree (TreeTemplate< N > &tree, Node *subtree)
	Remove a subtree defined by its root node and its parent node, while correcting for branch lengths. More...

template<class N >
static void	sampleSubtree (TreeTemplate< N > &tree, const std::vector< std::string > &leaves, size_t size)
	Sample a subtree by removing leaves randomly. More...

template<class N >
static std::vector< N * >	getNodes (N &node)
	Retrieve all son nodes from a subtree. More...

template<class N >
static void	getNodes (N &node, std::vector< N * > &nodes)
	Retrieve all son nodes from a subtree. More...

static std::vector< int >	getNodesId (const Node &node)
	Retrieve all nodes ids from a subtree. More...

static void	getNodesId (const Node &node, std::vector< int > &ids)
	Retrieve all nodes ids from a subtree. More...

template<class N >
static std::vector< N * >	getInnerNodes (N &node)
	Retrieve all inner nodes from a subtree. More...

template<class N >
static void	getInnerNodes (N &node, std::vector< N * > &nodes)
	Retrieve all inner nodes from a subtree. More...

static std::vector< int >	getInnerNodesId (const Node &node)
	Retrieve all inner nodes ids from a subtree. More...

static void	getInnerNodesId (const Node &node, std::vector< int > &ids)
	Retrieve all inner nodes ids from a subtree. More...

template<class N >
static std::vector< N * >	searchNodeWithId (N &node, int id)

template<class N >
static void	searchNodeWithId (N &node, int id, std::vector< N * > &nodes)

static Node *	searchFirstNodeWithId (Node &node, int id)

static const Node *	searchFirstNodeWithId (const Node &node, int id)

template<class N >
static bool	hasNodeWithId (const N &node, int id)

template<class N >
static std::vector< N * >	searchNodeWithName (N &node, const std::string &name)

template<class N >
static void	searchNodeWithName (N &node, const std::string &name, std::vector< N * > &nodes)

template<class N >
static bool	hasNodeWithName (const N &node, const std::string &name)

static bool	isRoot (const Node &node)
	Tell if a particular node is the root of a tree i.e. if it has a father node. More...

static size_t	getNumberOfBranches (const Node &node)
	Get the number of branches of a subtree defined by a particular node. More...

static size_t	getNumberOfLeaves (const Node &node)
	Get the number of leaves of a subtree defined by a particular node. More...

static size_t	getNumberOfNodes (const Node &node)
	Get the number of nodes of a subtree defined by a particular node. More...

static std::vector< std::string >	getLeavesNames (const Node &node)
	Get the leaves names of a subtree defined by a particular node. More...

static unsigned int	getDepth (const Node &node)
	Get the depth of the subtree defined by node 'node', i.e. the maximum number of sons 'generations'. More...

static unsigned int	getDepths (const Node &node, std::map< const Node *, unsigned int > &depths)
	Get the depths for all nodes of the subtree defined by node 'node', i.e. the maximum number of sons 'generations'. More...

static double	getHeight (const Node &node)
	Get the height of the subtree defined by node 'node', i.e. the maximum distance between leaves and the root of the subtree. More...

static double	getHeights (const Node &node, std::map< const Node *, double > &heights)
	Get the heights of all nodes within a subtree defined by node 'node', i.e. the maximum distance between leaves and the root of the subtree. More...

static bool	isMultifurcating (const Node &node)
	Tell is a subtree is multifurcating. More...

static bool	haveSameOrderedTopology (const Node &n1, const Node &n2)
	Tells if two subtrees have the same topology. More...

static std::vector< Node * >	getPathBetweenAnyTwoNodes (Node &node1, Node &node2, bool includeAncestor=true, bool includeAncestorAtEndOfPath=true)

static std::vector< const Node * >	getPathBetweenAnyTwoNodes (const Node &node1, const Node &node2, bool includeAncestor=true, bool includeAncestorAtEndOfPath=true)

template<class N >
static N *	cloneSubtree (const Node &node)
	Recursively clone a subtree structure. More...

template<class N >
static void	deleteSubtree (N *node)
	Recursively delete a subtree structure. More...

template<class N >
static N *	cloneSubtree (const Tree &tree, int nodeId)

Conversion tools.
Convert from Newick standard tree description. The description is for a node, and hence is to be surrounded with parenthesis. ex: (A:0.001, (B:0.001, C:0.02)90:0.005)50:0.0005
static Element	getElement (const std::string &elt)

static Node *	parenthesisToNode (const std::string &description, unsigned int &nodeCounter, bool bootstrap=true, const std::string &propertyName=TreeTools::BOOTSTRAP, bool withId=false, bool verbose=true)
	Parse a string in the parenthesis format and convert it to a subtree. More...

static std::unique_ptr< TreeTemplate< Node > >	parenthesisToTree (const std::string &description, bool bootstrap=true, const std::string &propertyName=TreeTools::BOOTSTRAP, bool withId=false, bool verbose=true)
	Parse a string in the parenthesis format and convert it to a tree. More...

static std::string	nodeToParenthesis (const Node &node, bool writeId=false)
	Get the parenthesis description of a subtree. More...

static std::string	nodeToParenthesis (const Node &node, bool bootstrap, const std::string &propertyName)
	Get the parenthesis description of a subtree. More...

static std::string	treeToParenthesis (const TreeTemplate< Node > &tree, bool writeId=false)
	Get the parenthesis description of a tree. More...

static std::string	treeToParenthesis (const TreeTemplate< Node > &tree, bool bootstrap, const std::string &propertyName)
	Get the parenthesis description of a tree. More...

Random trees
static std::unique_ptr< TreeTemplate< Node > >	buildFromPhyloTree (const PhyloTree &treetemp)

static std::unique_ptr< TreeTemplate< Node > >	getRandomTree (std::vector< std::string > &leavesNames, bool rooted=true)
	Draw a random tree from a list of taxa, using a Yule process. More...

Retrieve/Edit properties from a (sub)tree.
static void	getNodePropertyNames (const Node &node, std::vector< std::string > &propertyNames)
	Retrieve the names of all available node properties in the tree. More...

static void	getNodeProperties (const Node &node, const std::string &propertyName, std::map< int, const Clonable * > &properties)
	Retrieve all node property objects with a given name over a (sub) tree (const version). More...

static void	getNodeProperties (Node &node, const std::string &propertyName, std::map< int, Clonable * > &properties)
	Retrieve all node property objects with a given name over a (sub) tree. More...

static void	deleteNodeProperties (Node &node, const std::vector< std::string > &propertyNames)
	Delete the given properties in the tree. More...

static void	getBranchPropertyNames (const Node &node, std::vector< std::string > &propertyNames)
	Retrieve the names of all available branch properties in the tree. More...

static void	getBranchProperties (const Node &node, const std::string &propertyName, std::map< int, const Clonable * > &properties)
	Retrieve all branch property objects with a given name over a (sub) tree (const version). More...

static void	getBranchProperties (Node &node, const std::string &propertyName, std::map< int, Clonable * > &properties)
	Retrieve all branch property objects with a given name over a (sub) tree. More...

static void	deleteBranchProperties (Node &node, const std::vector< std::string > &propertyNames)
	Delete the given properties in the tree. More...

Static Public Attributes
static const short	MIDROOT_VARIANCE = 0

static const short	MIDROOT_SUM_OF_SQUARES = 1

Static Private Member Functions
static OrderTreeData_	orderTree_ (Node &node, bool downward, bool orderLeaves)

static Moments_	getSubtreeMoments_ (const Node *node)
	Computes the moment of a subtree. More...

static void	getBestRootInSubtree_ (bpp::TreeTemplate< bpp::Node > &tree, short criterion, bpp::Node node, std::pair< bpp::Node , std::map< std::string, double >> &bestRoot)
	Find, in the branches of a subtree, the root that minimizes a criterion over the tree. More...

Act on branch lengths.
static Vdouble	getBranchLengths (const Node &node)
	Get all the branch lengths of a subtree. More...

static double	getTotalLength (const Node &node, bool includeAncestor=true)
	Get the total length (sum of all branch lengths) of a subtree. More...

static void	setBranchLengths (Node &node, double brLen)
	Set all the branch lengths of a subtree. More...

static void	deleteBranchLengths (Node &node)
	Remove all the branch lengths of a subtree. More...

static void	setVoidBranchLengths (Node &node, double brLen)
	Give a length to branches that don't have one in a subtree. More...

static void	scaleTree (Node &node, double factor)
	Scale a given tree. More...

static double	getDistanceBetweenAnyTwoNodes (const Node &node1, const Node &node2)
	Get the total distance between to nodes. More...

static std::unique_ptr< DistanceMatrix >	getDistanceMatrix (const TreeTemplate< Node > &tree)
	Compute a distance matrix from a tree. More...

static void	processDistsInSubtree_ (const Node *node, DistanceMatrix &matrix, std::vector< std::pair< std::string, double >> &distsToNodeFather)
	Inner function used by getDistanceMatrix. More...

Detailed Description

Utilitary methods working with TreeTemplate and Node objects.

See also: TreeTools for more generic methods.

Definition at line 29 of file TreeTemplateTools.h.

Constructor & Destructor Documentation

◆ TreeTemplateTools()

bpp::TreeTemplateTools::TreeTemplateTools ( )

inline

Definition at line 32 of file TreeTemplateTools.h.

◆ ~TreeTemplateTools()

virtual bpp::TreeTemplateTools::~TreeTemplateTools ( )

inlinevirtual

Definition at line 33 of file TreeTemplateTools.h.

Member Function Documentation

◆ buildFromPhyloTree()

unique_ptr< TreeTemplate< Node > > TreeTemplateTools::buildFromPhyloTree ( const PhyloTree & treetemp )

static

Definition at line 581 of file TreeTemplateTools.cpp.

References bpp::Node::addSubTree(), and bpp::AssociationTreeGraphImplObserver< class, class, class >::getRoot().

Referenced by bpp::OptimizationTools::buildDistanceTree().

◆ cloneSubtree() [1/2]

template<class N >

static N* bpp::TreeTemplateTools::cloneSubtree ( const Node & node )

inlinestatic

Recursively clone a subtree structure.

This is a template function allowing to specify the class of the copy. The template class has to have a constructor accepting const Node& as single argument.

Parameters

node	The basal node of the subtree.

Returns: The basal node of the new copy.

Definition at line 688 of file TreeTemplateTools.h.

References bpp::Node::getNumberOfSons().

◆ cloneSubtree() [2/2]

template<class N >

static N* bpp::TreeTemplateTools::cloneSubtree	(	const Tree &	tree,
		int	nodeId
	)

inlinestatic

Definition at line 721 of file TreeTemplateTools.h.

References bpp::Tree::getBranchProperty(), bpp::Tree::getBranchPropertyNames(), bpp::Tree::getDistanceToFather(), bpp::Tree::getNodeName(), bpp::Tree::getNodeProperty(), bpp::Tree::getNodePropertyNames(), bpp::Tree::getSonsId(), bpp::Tree::hasDistanceToFather(), and bpp::Tree::hasNodeName().

◆ deleteBranchLengths()

void TreeTemplateTools::deleteBranchLengths ( Node & node )

static

Remove all the branch lengths of a subtree.

Parameters

node	The root node of the subtree.

Definition at line 544 of file TreeTemplateTools.cpp.

References bpp::Node::deleteDistanceToFather(), bpp::Node::getNumberOfSons(), and bpp::Node::getSon().

Referenced by bpp::AbstractTreeParsimonyScore::init_().

◆ deleteBranchProperties()

void TreeTemplateTools::deleteBranchProperties	(	Node &	node,
		const std::vector< std::string > &	propertyNames
	)

static

Delete the given properties in the tree.

Parameters

node	[in] The root node of the (sub)tree to use.
propertyNames	[int] a vector of property names to be deleted.

Definition at line 979 of file TreeTemplateTools.cpp.

References bpp::Node::deleteBranchProperty(), bpp::Node::getNumberOfSons(), and bpp::Node::getSon().

◆ deleteNodeProperties()

void TreeTemplateTools::deleteNodeProperties	(	Node &	node,
		const std::vector< std::string > &	propertyNames
	)

static

Delete the given properties in the tree.

Parameters

node	[in] The root node of the (sub)tree to use.
propertyNames	[int] a vector of property names to be deleted.

Definition at line 931 of file TreeTemplateTools.cpp.

References bpp::Node::deleteNodeProperty(), bpp::Node::getNumberOfSons(), and bpp::Node::getSon().

◆ deleteSubtree()

template<class N >

static void bpp::TreeTemplateTools::deleteSubtree ( N * node )

inlinestatic

Recursively delete a subtree structure.

Parameters

node	The basal node of the subtree.

Definition at line 709 of file TreeTemplateTools.h.

Referenced by dropSubtree(), bpp::TreeTemplate< N >::operator=(), and bpp::TreeTemplate< N >::~TreeTemplate().

◆ dropLeaf()

template<class N >

static void bpp::TreeTemplateTools::dropLeaf	(	TreeTemplate< N > &	tree,
		const std::string &	leafName
	)

inlinestatic

Remove a leaf node and its parent node, while correcting for branch lengths.

Parameters

tree	The tree to edit.
leafName	The name of the leaf node.

Exceptions

NodeNotFoundException If the node is not found.

Definition at line 144 of file TreeTemplateTools.h.

References bpp::TreeTemplate< N >::getNode(), and bpp::TreeTemplate< N >::setRootNode().

Referenced by sampleSubtree().

◆ dropSubtree()

template<class N >

static void bpp::TreeTemplateTools::dropSubtree	(	TreeTemplate< N > &	tree,
		Node *	subtree
	)

inlinestatic

Remove a subtree defined by its root node and its parent node, while correcting for branch lengths.

Parameters

tree	The tree to edit.
subtree	The subtree to remove, defined by its root node.

Exceptions

Exception If something unexpected happens :s

Definition at line 201 of file TreeTemplateTools.h.

References deleteSubtree(), bpp::Node::getDistanceToFather(), bpp::Node::getFather(), bpp::Node::hasDistanceToFather(), bpp::Node::hasFather(), bpp::Node::removeSon(), and bpp::TreeTemplate< N >::setRootNode().

◆ getAncestorsId()

std::vector< int > TreeTemplateTools::getAncestorsId ( const Node & node )

static

Retrieve all nodes ids that are ancestors of a node.

Parameters

node The node

Returns: A vector of ids.

Definition at line 90 of file TreeTemplateTools.cpp.

References bpp::Node::getFather(), bpp::Node::getId(), and bpp::Node::hasFather().

Referenced by bpp::TreeTemplate< N >::getAncestorsId().

◆ getBestRootInSubtree_()

void TreeTemplateTools::getBestRootInSubtree_	(	bpp::TreeTemplate< bpp::Node > &	tree,
		short	criterion,
		bpp::Node *	node,
		std::pair< bpp::Node *, std::map< std::string, double >> &	bestRoot
	)

staticprivate

Find, in the branches of a subtree, the root that minimizes a criterion over the tree.

The branches are explored recursively. For each branch leaving the input node, the method computes the best root position, possibly updates the bestRoot parameter, then recurses.

Parameters

tree	The tree to which the subtree belongs. (The root is moved.)
criterion	The criterion to minimize. Legal values are TreeTemplateTools::MIDROOT_VARIANCE and TreeTemplateTools::MIDROOT_SUM_OF_SQUARES.
node	The root of the subtree.
bestRoot	The object storing the best root found, if it is better than the initial one, or otherwise left unchanged.

Author: Nicolas Rochette, Manolo Gouy

Definition at line 1238 of file TreeTemplateTools.cpp.

References bpp::Node::getSons(), bpp::TreeTemplateTools::Moments_::numberOfLeaves, bpp::TreeTemplate< N >::rootAt(), bpp::TreeTemplateTools::Moments_::squaresSum, and bpp::TreeTemplateTools::Moments_::sum.

◆ getBranchLengths()

Vdouble TreeTemplateTools::getBranchLengths ( const Node & node )

static

Get all the branch lengths of a subtree.

Parameters

node	The root node of the subtree.

Returns: A vector with all branch lengths.

Exceptions

NodePException If a branch length is lacking.

Definition at line 502 of file TreeTemplateTools.cpp.

References bpp::Node::getDistanceToFather(), bpp::Node::getNumberOfSons(), and bpp::Node::getSon().

Referenced by bpp::TreeTemplate< N >::getBranchLengths().

◆ getBranchProperties() [1/2]

void TreeTemplateTools::getBranchProperties	(	const Node &	node,
		const std::string &	propertyName,
		std::map< int, const Clonable * > &	properties
	)

static

Retrieve all branch property objects with a given name over a (sub) tree (const version).

Parameters

node	[in] The root node of the (sub)tree to use.
propertyName	[in] The name of the property to retrieve.
properties	[out] A map with pointers toward the properties as values, and node ids as key. If a node does not contain the given property, then no entry in the map is created. If an entry already exists in the map, it will be replaced, but the underlying property will not be destroyed. Property objects are not cloned when added to the map, but passed as pointers.

Definition at line 959 of file TreeTemplateTools.cpp.

References bpp::Node::getBranchProperty(), bpp::Node::getId(), bpp::Node::getNumberOfSons(), bpp::Node::getSon(), and bpp::Node::hasBranchProperty().

◆ getBranchProperties() [2/2]

void TreeTemplateTools::getBranchProperties	(	Node &	node,
		const std::string &	propertyName,
		std::map< int, Clonable * > &	properties
	)

static

Retrieve all branch property objects with a given name over a (sub) tree.

Parameters

node	[in] The root node of the (sub)tree to use.
propertyName	[in] The name of the property to retrieve.
properties	[out] A map with pointers toward the properties as values, and node ids as key. If a node does not contain the given property, then no entry in the map is created. If an entry already exists in the map, it will be replaced, but the underlying property will not be destroyed. Property objects are not cloned when added to the map, but passed as pointers.

Definition at line 969 of file TreeTemplateTools.cpp.

References bpp::Node::getBranchProperty(), bpp::Node::getId(), bpp::Node::getNumberOfSons(), bpp::Node::getSon(), and bpp::Node::hasBranchProperty().

◆ getBranchPropertyNames()

void TreeTemplateTools::getBranchPropertyNames	(	const Node &	node,
		std::vector< std::string > &	propertyNames
	)

static

Retrieve the names of all available branch properties in the tree.

Parameters

node	[in] The root node of the (sub)tree to use.
propertyNames	[out] a vector where names will be added.

Definition at line 950 of file TreeTemplateTools.cpp.

References bpp::VectorTools::extend(), bpp::Node::getBranchPropertyNames(), bpp::Node::getNumberOfSons(), and bpp::Node::getSon().

◆ getDepth()

unsigned int TreeTemplateTools::getDepth ( const Node & node )

static

Get the depth of the subtree defined by node 'node', i.e. the maximum number of sons 'generations'.

ex:

*    +----------A
*    |
* ---+ N1     +-------B
*    |        |
*    +--------+ N2
*             |
*             +------C
*

Depth of node 'N1' id 2, depth of node 'N2' is 1, depth of leaves is 0.

Parameters

node	The node defining the subtree to check.

Returns: The depth of the subtree.

Definition at line 121 of file TreeTemplateTools.cpp.

References bpp::Node::getNumberOfSons().

Referenced by bpp::CladogramPlot::recursivePlot_(), bpp::CladogramPlot::setTree(), and bpp::CladogramPlot::treeHasChanged().

◆ getDepths()

unsigned int TreeTemplateTools::getDepths	(	const Node &	node,
		std::map< const Node *, unsigned int > &	depths
	)

static

Get the depths for all nodes of the subtree defined by node 'node', i.e. the maximum number of sons 'generations'.

ex:

*    +----------A
*    |
* ---+ N1     +-------B
*    |        |
*    +--------+ N2
*             |
*             +------C
*

Depth of node 'N1' id 2, depth of node 'N2' is 1, depth of leaves is 0.

Parameters

node	The node defining the subtree to check.
depths	The map that will contain all the depths of the nodes, with node pointers as keys.

Returns: The depth of the subtree.

Definition at line 135 of file TreeTemplateTools.cpp.

References bpp::Node::getNumberOfSons().

◆ getDistanceBetweenAnyTwoNodes()

double TreeTemplateTools::getDistanceBetweenAnyTwoNodes	(	const Node &	node1,
		const Node &	node2
	)

static

Get the total distance between to nodes.

Sum all branch lengths between two nodes.

Parameters

node1	The first node.
node2	The second node.

Returns: The sum of all branch lengths between the two nodes.

Definition at line 778 of file TreeTemplateTools.cpp.

◆ getDistanceMatrix()

unique_ptr< DistanceMatrix > TreeTemplateTools::getDistanceMatrix ( const TreeTemplate< Node > & tree )

static

Compute a distance matrix from a tree.

Compute all distances between each leaves and store them in a matrix. A new DistanceMatrix object is created, and a pointer toward it is returned. The destruction of this matrix is left up to the user.

From version 1.9 of Bio++, this function has been rewritten in a more efficient way and does not use getDistanceBetweenAnyTwoNodes anymore, but makes use of a more clever pass on the tree. The new function now works well on trees with thousands of leaves.

See also: getDistanceBetweenAnyTwoNodes

Author: Nicolas Rochette

Parameters

tree	The tree to use.

Returns: The distance matrix computed from tree.

Definition at line 866 of file TreeTemplateTools.cpp.

References bpp::TreeTemplate< N >::getLeavesNames(), and bpp::TreeTemplate< N >::getRootNode().

◆ getElement()

TreeTemplateTools::Element TreeTemplateTools::getElement ( const std::string & elt )

static

Definition at line 183 of file TreeTemplateTools.cpp.

References element, bpp::TextTools::isEmpty(), and bpp::TextTools::removeSurroundingWhiteSpaces().

◆ getHeight()

double TreeTemplateTools::getHeight ( const Node & node )

static

Get the height of the subtree defined by node 'node', i.e. the maximum distance between leaves and the root of the subtree.

The distance do not include the branch length of the subtree root node. The height of a leaf is hence 0.

Parameters

node	The node defining the subtree to check.

Returns: The height of the subtree.

Exceptions

NodePException If a branch length is lacking.

Definition at line 150 of file TreeTemplateTools.cpp.

References bpp::Node::getDistanceToFather(), and bpp::Node::getNumberOfSons().

Referenced by bpp::PhylogramPlot::treeHasChanged().

◆ getHeights()

double TreeTemplateTools::getHeights	(	const Node &	node,
		std::map< const Node *, double > &	heights
	)

static

Get the heights of all nodes within a subtree defined by node 'node', i.e. the maximum distance between leaves and the root of the subtree.

The height of a leaf is 0.

Parameters

node	The node defining the subtree to check.
heights	The map that will contain all the heights of the nodes, with node pointers as keys.

Returns: The height of the subtree.

Exceptions

NodePException If a branch length is lacking.

Definition at line 166 of file TreeTemplateTools.cpp.

References bpp::Node::getDistanceToFather(), and bpp::Node::getNumberOfSons().

Referenced by bpp::GlobalClockTreeLikelihoodFunctionWrapper::initParameters_().

◆ getInnerNodes() [1/2]

template<class N >

static std::vector<N*> bpp::TreeTemplateTools::getInnerNodes ( N & node )

inlinestatic

Retrieve all inner nodes from a subtree.

Parameters

node	The node that defines the subtree.

Returns: A vector of pointers toward each inner node in the subtree.

Definition at line 332 of file TreeTemplateTools.h.

Referenced by bpp::TreeTemplate< N >::getInnerNodes().

◆ getInnerNodes() [2/2]

template<class N >

static void bpp::TreeTemplateTools::getInnerNodes	(	N &	node,
		std::vector< N * > &	nodes
	)

inlinestatic

Retrieve all inner nodes from a subtree.

A inner node is a node with degree > 1, that is, all nodes but the leaves, be they terminal or not.

Parameters

node	The node that defines the subtree.
nodes	A vector to be filled with pointers toward each inner node in the subtree.

Definition at line 348 of file TreeTemplateTools.h.

◆ getInnerNodesId() [1/2]

static std::vector<int> bpp::TreeTemplateTools::getInnerNodesId ( const Node & node )

inlinestatic

Retrieve all inner nodes ids from a subtree.

A inner node is a node with degree > 1, that is, all nodes but the leaves, be they terminal or not.

Parameters

node	The node that defines the subtree.

Returns: A vector of ids.

Definition at line 366 of file TreeTemplateTools.h.

Referenced by bpp::TreeTemplate< N >::getInnerNodesId(), and getInnerNodesId().

◆ getInnerNodesId() [2/2]

static void bpp::TreeTemplateTools::getInnerNodesId	(	const Node &	node,
		std::vector< int > &	ids
	)

inlinestatic

Retrieve all inner nodes ids from a subtree.

Parameters

node	The node that defines the subtree.
ids	A vector to be filled with the resulting ids.

Definition at line 379 of file TreeTemplateTools.h.

References bpp::Node::getId(), getInnerNodesId(), bpp::Node::getNumberOfSons(), bpp::Node::getSon(), and bpp::Node::isLeaf().

◆ getLeafId()

static int bpp::TreeTemplateTools::getLeafId	(	const Node &	node,
		const std::string &	name
	)

inlinestatic

Get the id of a leaf given its name in a subtree.

Parameters

node	The node defining the subtree to search.
name	The name of the node.

Returns: The id of the node.

Exceptions

NodeNotFoundException If the node is not found.

Definition at line 112 of file TreeTemplateTools.h.

References searchLeaf().

Referenced by bpp::TreeTemplate< N >::getLeafId().

◆ getLeaves() [1/2]

template<class N >

static std::vector<N*> bpp::TreeTemplateTools::getLeaves ( N & node )

inlinestatic

Retrieve all leaves from a subtree.

Parameters

node	The node that defines the subtree.

Returns: A vector of pointers toward each leaf in the subtree.

Definition at line 49 of file TreeTemplateTools.h.

Referenced by bpp::TreeTemplate< N >::getLeaves(), bpp::PatternTools::getSequenceSubset(), and bpp::DRASRTreeLikelihoodData::initLikelihoodsWithPatterns().

◆ getLeaves() [2/2]

template<class N >

static void bpp::TreeTemplateTools::getLeaves	(	N &	node,
		std::vector< N * > &	leaves
	)

inlinestatic

Retrieve all leaves from a subtree.

Parameters

node	The node that defines the subtree.
leaves	A vector of pointers toward each leaf in the subtree.

Definition at line 63 of file TreeTemplateTools.h.

◆ getLeavesId() [1/2]

static std::vector<int> bpp::TreeTemplateTools::getLeavesId ( const Node & node )

inlinestatic

Retrieve all leaves ids from a subtree.

Parameters

node	The node that defines the subtree.

Returns: A vector of ids.

Definition at line 81 of file TreeTemplateTools.h.

Referenced by bpp::TreeTemplate< N >::getLeavesId().

◆ getLeavesId() [2/2]

void TreeTemplateTools::getLeavesId	(	const Node &	node,
		std::vector< int > &	ids
	)

static

Retrieve all leaves ids from a subtree.

Parameters

node	The node that defines the subtree.
ids	A vector of ids.

Definition at line 78 of file TreeTemplateTools.cpp.

References bpp::Node::getId(), bpp::Node::getNumberOfSons(), bpp::Node::getSon(), and bpp::Node::isLeaf().

◆ getLeavesNames()

vector< string > TreeTemplateTools::getLeavesNames ( const Node & node )

static

Get the leaves names of a subtree defined by a particular node.

Parameters

node	The node defining the subtree to check.

Returns: The list of all leaves names.

Definition at line 60 of file TreeTemplateTools.cpp.

References bpp::Node::getName(), bpp::Node::getNumberOfSons(), bpp::Node::getSon(), and bpp::Node::hasNoSon().

Referenced by bpp::TreeTemplate< N >::getLeavesNames().

◆ getNodeProperties() [1/2]

void TreeTemplateTools::getNodeProperties	(	const Node &	node,
		const std::string &	propertyName,
		std::map< int, const Clonable * > &	properties
	)

static

Retrieve all node property objects with a given name over a (sub) tree (const version).

Parameters

node	[in] The root node of the (sub)tree to use.
propertyName	[in] The name of the property to retrieve.
properties	[out] A map with pointers toward the properties as values, and node ids as key. If a node does not contain the given property, then no entry in the map is created. If an entry already exists in the map, it will be replaced, but the underlying property will not be destroyed. Property objects are not cloned when added to the map, but passed as pointers.

Definition at line 911 of file TreeTemplateTools.cpp.

References bpp::Node::getId(), bpp::Node::getNodeProperty(), bpp::Node::getNumberOfSons(), bpp::Node::getSon(), and bpp::Node::hasNodeProperty().

◆ getNodeProperties() [2/2]

void TreeTemplateTools::getNodeProperties	(	Node &	node,
		const std::string &	propertyName,
		std::map< int, Clonable * > &	properties
	)

static

Retrieve all node property objects with a given name over a (sub) tree.

Parameters

node	[in] The root node of the (sub)tree to use.
propertyName	[in] The name of the property to retrieve.
properties	[out] A map with pointers toward the properties as values, and node ids as key. If a node does not contain the given property, then no entry in the map is created. If an entry already exists in the map, it will be replaced, but the underlying property will not be destroyed. Property objects are not cloned when added to the map, but passed as pointers.

Definition at line 921 of file TreeTemplateTools.cpp.

References bpp::Node::getId(), bpp::Node::getNodeProperty(), bpp::Node::getNumberOfSons(), bpp::Node::getSon(), and bpp::Node::hasNodeProperty().

◆ getNodePropertyNames()

void TreeTemplateTools::getNodePropertyNames	(	const Node &	node,
		std::vector< std::string > &	propertyNames
	)

static

Retrieve the names of all available node properties in the tree.

Parameters

node	[in] The root node of the (sub)tree to use.
propertyNames	[out] a vector where names will be added.

Definition at line 902 of file TreeTemplateTools.cpp.

References bpp::VectorTools::extend(), bpp::Node::getNodePropertyNames(), bpp::Node::getNumberOfSons(), and bpp::Node::getSon().

◆ getNodes() [1/2]

template<class N >

static std::vector<N*> bpp::TreeTemplateTools::getNodes ( N & node )

inlinestatic

Retrieve all son nodes from a subtree.

Parameters

node	The node that defines the subtree.

Returns: A vector of pointers toward each son node in the subtree.

Definition at line 274 of file TreeTemplateTools.h.

Referenced by bpp::TreeTemplate< N >::getNodes().

◆ getNodes() [2/2]

template<class N >

static void bpp::TreeTemplateTools::getNodes	(	N &	node,
		std::vector< N * > &	nodes
	)

inlinestatic

Retrieve all son nodes from a subtree.

Parameters

node	The node that defines the subtree.
nodes	A vector of pointers toward each son node in the subtree.

Definition at line 288 of file TreeTemplateTools.h.

◆ getNodesId() [1/2]

static std::vector<int> bpp::TreeTemplateTools::getNodesId ( const Node & node )

inlinestatic

Retrieve all nodes ids from a subtree.

Parameters

node	The node that defines the subtree.

Returns: A vector of ids.

Definition at line 303 of file TreeTemplateTools.h.

Referenced by bpp::TreeTemplate< N >::getBranchesId(), bpp::TreeTemplate< N >::getNodesId(), and getNodesId().

◆ getNodesId() [2/2]

static void bpp::TreeTemplateTools::getNodesId	(	const Node &	node,
		std::vector< int > &	ids
	)

inlinestatic

Retrieve all nodes ids from a subtree.

Parameters

node	The node that defines the subtree.
ids	A vector of ids.

Definition at line 316 of file TreeTemplateTools.h.

References bpp::Node::getId(), getNodesId(), bpp::Node::getNumberOfSons(), and bpp::Node::getSon().

◆ getNumberOfBranches()

static size_t bpp::TreeTemplateTools::getNumberOfBranches ( const Node & node )

inlinestatic

Get the number of branches of a subtree defined by a particular node.

Parameters

node	The node defining the subtree to check.

Returns: The number of branches.

Definition at line 540 of file TreeTemplateTools.h.

References getNumberOfNodes(), and bpp::Node::getNumberOfSons().

Referenced by bpp::TreeTemplate< N >::getNumberOfBranches().

◆ getNumberOfLeaves()

size_t TreeTemplateTools::getNumberOfLeaves ( const Node & node )

static

Get the number of leaves of a subtree defined by a particular node.

Parameters

node	The node defining the subtree to check.

Returns: The number of leaves.

Definition at line 44 of file TreeTemplateTools.cpp.

References bpp::Node::getNumberOfSons(), and bpp::Node::isLeaf().

Referenced by bpp::TreeTemplate< N >::getNumberOfLeaves().

◆ getNumberOfNodes()

static size_t bpp::TreeTemplateTools::getNumberOfNodes ( const Node & node )

inlinestatic

Get the number of nodes of a subtree defined by a particular node.

Parameters

node	The node defining the subtree to check.

Returns: The number of nodes.

Definition at line 564 of file TreeTemplateTools.h.

References bpp::Node::getNumberOfSons().

Referenced by getNumberOfBranches(), and bpp::TreeTemplate< N >::getNumberOfNodes().

◆ getPathBetweenAnyTwoNodes() [1/2]

vector< const Node * > TreeTemplateTools::getPathBetweenAnyTwoNodes	(	const Node &	node1,
		const Node &	node2,
		bool	includeAncestor = `true`,
		bool	includeAncestorAtEndOfPath = `true`
	)

static

Definition at line 705 of file TreeTemplateTools.cpp.

References bpp::Node::getFather(), and bpp::Node::hasFather().

◆ getPathBetweenAnyTwoNodes() [2/2]

vector< Node * > TreeTemplateTools::getPathBetweenAnyTwoNodes	(	Node &	node1,
		Node &	node2,
		bool	includeAncestor = `true`,
		bool	includeAncestorAtEndOfPath = `true`
	)

static

Definition at line 633 of file TreeTemplateTools.cpp.

References bpp::Node::getFather(), and bpp::Node::hasFather().

Referenced by bpp::TreeTemplate< N >::rootAt().

◆ getRadius()

double TreeTemplateTools::getRadius ( TreeTemplate< Node > & tree )

static

Get the characteristic radius of a tree (average distance to the root minimizing the sum of squared distances).

Parameters

tree	The tree (which is rerooted in the process).

Definition at line 1197 of file TreeTemplateTools.cpp.

References bpp::TreeTemplate< N >::getRootNode(), midRoot(), bpp::TreeTemplateTools::Moments_::numberOfLeaves, and bpp::TreeTemplateTools::Moments_::sum.

◆ getRandomTree()

unique_ptr< TreeTemplate< Node > > TreeTemplateTools::getRandomTree	(	std::vector< std::string > &	leavesNames,
		bool	rooted = `true`
	)

static

Draw a random tree from a list of taxa, using a Yule process.

Parameters

leavesNames	A list of taxa.
rooted	Tell is the output tree should be rooted.

Returns: A random tree with all corresponding taxa.

Definition at line 591 of file TreeTemplateTools.cpp.

References bpp::Node::addSon().

Referenced by bpp::PhylogeneticsApplicationTools::getPhyloTrees(), and bpp::LegacyPhylogeneticsApplicationTools::getTrees().

◆ getRemainingNeighbors()

std::vector< const Node * > TreeTemplateTools::getRemainingNeighbors	(	const Node *	node1,
		const Node *	node2,
		const Node *	node3
	)

static

Get a subset of node neighbors.

Get all neighbors of node node1 that are neither node1 nor node2. This method is useful for topology manipulations, like NNI.

Parameters

node1	The node whose neighbors must be retrieved.
node2	One neighbor to exclude.
node3	Another neighbor to exclude.

Returns: A vector of neighbors.

Definition at line 876 of file TreeTemplateTools.cpp.

References bpp::Node::getNeighbors().

Referenced by bpp::NNIHomogeneousTreeLikelihood::testNNI(), and bpp::DRTreeParsimonyScore::testNNI().

◆ getSubtreeMoments_()

TreeTemplateTools::Moments_ TreeTemplateTools::getSubtreeMoments_ ( const Node * node )

staticprivate

Computes the moment of a subtree.

Parameters

node	The root of the subtree

Returns: A Moments_ structure

Definition at line 1323 of file TreeTemplateTools.cpp.

References bpp::Node::getDistanceToFather(), bpp::Node::getNumberOfSons(), bpp::Node::getSon(), bpp::Node::isLeaf(), bpp::TreeTemplateTools::Moments_::numberOfLeaves, bpp::TreeTemplateTools::Moments_::squaresSum, and bpp::TreeTemplateTools::Moments_::sum.

◆ getTotalLength()

double TreeTemplateTools::getTotalLength	(	const Node &	node,
		bool	includeAncestor = `true`
	)

static

Get the total length (sum of all branch lengths) of a subtree.

Parameters

node	The root node of the subtree.
includeAncestor	Tell if the branch length of the most ancient node should be included in the counting. (this should be set to false if this node is the root of the tree for instance).

Returns: The total length of the subtree.

Exceptions

NodePException If a branch length is lacking.

Definition at line 519 of file TreeTemplateTools.cpp.

References bpp::Node::getDistanceToFather(), bpp::Node::getNumberOfSons(), bpp::Node::getSon(), and bpp::Node::hasDistanceToFather().

Referenced by bpp::TreeTemplate< N >::getTotalLength().

◆ hasNodeWithId()

template<class N >

static bool bpp::TreeTemplateTools::hasNodeWithId	(	const N &	node,
		int	id
	)

inlinestatic

Parameters

node	The node defining the subtree to be searched.
id	The id to search for.

Returns: True if the subtree contains a node with the specified id.

Definition at line 465 of file TreeTemplateTools.h.

Referenced by bpp::TreeTemplate< N >::hasNode().

◆ hasNodeWithName()

template<class N >

static bool bpp::TreeTemplateTools::hasNodeWithName	(	const N &	node,
		const std::string &	name
	)

inlinestatic

Parameters

node	The node defining the subtree to be searched.
name	The name to search for.

Returns: True if the subtree contains a node with the specified name.

Definition at line 512 of file TreeTemplateTools.h.

◆ haveSameOrderedTopology()

bool TreeTemplateTools::haveSameOrderedTopology	(	const Node &	n1,
		const Node &	n2
	)

static

Tells if two subtrees have the same topology.

The comparison is based on parental relationships and leaf names only, node ids and all branch/node properties are ignored. The ordering of son nodes is taken into account so that ((A,B),C) will be considered different from ((B,A),C). Considerer ordering the trees first if you want to perform a strict topological comparison.

Parameters

n1	Root node of the first subtree.
n2	Root node of the second subtree.

Returns: true if the two subtrees have the same topology.

Definition at line 998 of file TreeTemplateTools.cpp.

References bpp::Node::getName(), bpp::Node::getNumberOfSons(), bpp::Node::getSon(), and bpp::Node::hasNoSon().

Referenced by bpp::TreeTemplate< N >::hasSameTopologyAs().

◆ incrementAllIds()

void TreeTemplateTools::incrementAllIds	(	Node *	node,
		int	increment
	)

static

This method will add a given value (possibly negative) to all identifiers in a (sub)tree.

Parameters

node	The root node of the (sub)tree to use.
increment	The value to add.

Definition at line 891 of file TreeTemplateTools.cpp.

References bpp::Node::getId(), bpp::Node::getNumberOfSons(), bpp::Node::getSon(), and bpp::Node::setId().

◆ isMultifurcating()

bool TreeTemplateTools::isMultifurcating ( const Node & node )

static

Tell is a subtree is multifurcating.

Parameters

node	The root node of the subtree.

Returns: True is the subtree contains at least one multifurcating node (including the root node).

Definition at line 27 of file TreeTemplateTools.cpp.

References bpp::Node::getNumberOfSons(), and bpp::Node::getSon().

Referenced by bpp::GlobalClockTreeLikelihoodFunctionWrapper::initParameters_(), and bpp::TreeTemplate< N >::isMultifurcating().

◆ isRoot()

static bool bpp::TreeTemplateTools::isRoot ( const Node & node )

inlinestatic

Tell if a particular node is the root of a tree i.e. if it has a father node.

Parameters

node	The node to check.

Returns: True if node does not have a father.

Definition at line 532 of file TreeTemplateTools.h.

References bpp::Node::hasFather().

Referenced by bpp::TreeTemplate< N >::isRoot().

◆ midRoot()

void TreeTemplateTools::midRoot	(	TreeTemplate< Node > &	tree,
		short	criterion,
		bool	forceBranchRoot
	)

static

Midroot the tree by minimizing a given criterion ("variance" or "sum of squares")

For each branch, the best root position, according to the given criterion, is computed analytically.

For the 'variance' criterion :

$(n_1+n_2)^2 V(x) = (n_1+n_2) \left[ \sum_{F_1} (d_i + x \delta )^2 + \sum_{F_2} (d_i + (1-x) \delta )^2 \right] - \left[ \sum_{F_1} (d_i + x \delta) + \sum_{F_2} (d_i + (1-x) \delta) \right]^2 = A x^2 + B x + C$

With

$\begin{array}{rcl} A &=& 4 n_1 n_2 \delta^2 \\ B &=& 4 \delta ( n_2 S_1 - n_1 S_2 - n_1 n_2 \delta ) \\ C &=& (n_1+n_2) (C_1+C_2) + n_1 n_2 \delta^2 + 2 n_1 S_2 \delta - 2 n_2 S_1 \delta - (S_1+S_2)^2 \\ \end{array}$

Where and are the sets of leaves on either side of the root branch, is the distance of leaf to the nearest end of the root branch, $\delta$ is the length of the root branch, and and are respectively $\sum_{F_k} d_i$ and $\sum_{F_k} d_i^2$

~

If force_branch_root==true, then the function will always root the tree on a branch. To do so, in cases where the root is placed on a node, a new node new_root is created between the root and its nearest child. If force_branch_root==false, it may be placed on a node.

Parameters

tree
criterion	The criterion upon which to reroot. Legal values : TreeTemplateTools::MIDROOT_VARIANCE to minimize root-leaf distance variance (molecular clock assumption) or TreeTemplateTools::MIDROOT_SUM_OF_SQUARES to minimize the sum of root-leaf distance squares.
forceBranchRoot	If true, the root must be placed on a branch, otherwise it may also be placed on a node.

Author: Nicolas Rochette

Definition at line 1109 of file TreeTemplateTools.cpp.

References bpp::Node::addSon(), bpp::Node::getBranchProperty(), bpp::Node::getBranchPropertyNames(), bpp::Node::getDistanceToFather(), bpp::Node::getFather(), bpp::TreeTools::getMPNUId(), bpp::TreeTemplate< N >::getRootId(), bpp::TreeTemplate< N >::getRootNode(), bpp::Node::getSons(), bpp::TreeTemplate< N >::isRooted(), bpp::Node::removeSon(), bpp::TreeTemplate< N >::rootAt(), bpp::Node::setBranchProperty(), bpp::Node::setDistanceToFather(), bpp::Node::setId(), bpp::TextTools::toString(), and bpp::TreeTemplate< N >::unroot().

Referenced by getRadius().

◆ nodeToParenthesis() [1/2]

string TreeTemplateTools::nodeToParenthesis	(	const Node &	node,
		bool	bootstrap,
		const std::string &	propertyName
	)

static

Get the parenthesis description of a subtree.

Parameters

node	The node defining the subtree.
bootstrap	Tell is bootstrap values must be written. If so, the content of the property with name TreeTools::BOOTSTRAP will be written as bootstrap value. The property should be a Number<double> object. Otherwise, the content of the property with name 'propertyName' will be written. In this later case, the property should be a String object.
propertyName	The name of the property to use. Only used if bootstrap = false.

Returns: A string in the parenthesis format.

Definition at line 387 of file TreeTemplateTools.cpp.

References bpp::TreeTools::BOOTSTRAP, bpp::Node::getBranchProperty(), bpp::Node::getDistanceToFather(), bpp::Node::getName(), bpp::Node::getNumberOfSons(), bpp::Node::hasBranchProperty(), bpp::Node::hasDistanceToFather(), and bpp::Node::hasNoSon().

◆ nodeToParenthesis() [2/2]

string TreeTemplateTools::nodeToParenthesis	(	const Node &	node,
		bool	writeId = `false`
	)

static

Get the parenthesis description of a subtree.

Parameters

node	The node defining the subtree.
writeId	Tells if node ids must be printed. This will overwrite bootstrap values if there are ones. Leaves id will be added to the leave names, separated by a '_' character.

Returns: A string in the parenthesis format.

Definition at line 352 of file TreeTemplateTools.cpp.

References bpp::TreeTools::BOOTSTRAP, bpp::Node::getBranchProperty(), bpp::Node::getDistanceToFather(), bpp::Node::getId(), bpp::Node::getName(), bpp::Node::getNumberOfSons(), bpp::Node::hasBranchProperty(), bpp::Node::hasDistanceToFather(), and bpp::Node::hasNoSon().

◆ orderTree()

static void bpp::TreeTemplateTools::orderTree	(	Node &	node,
		bool	downward = `true`,
		bool	orderLeaves = `false`
	)

inlinestatic

Swap nodes in the subtree so that they are ordered according to the underlying number of leaves.

Parameters

node	The root node of the (sub)tree to use.
downward	If yes, biggest subtrees (in terms of number of leaves) will come first. Otherwise, the smallest subtrees will come first.
orderLeaves	Tell if leaves have to be ordered alphabetically. This ensures that two identical topology will always have the same ordered tree, whatever the initial ordering of nodes.

Definition at line 1104 of file TreeTemplateTools.h.

References orderTree_().

Referenced by bpp::TreeTemplate< N >::hasSameTopologyAs().

◆ orderTree_()

TreeTemplateTools::OrderTreeData_ TreeTemplateTools::orderTree_	(	Node &	node,
		bool	downward,
		bool	orderLeaves
	)

staticprivate

Definition at line 1017 of file TreeTemplateTools.cpp.

References bpp::TreeTemplateTools::OrderTreeData_::firstLeaf, bpp::Node::getName(), bpp::Node::getNumberOfSons(), bpp::Node::getSon(), bpp::Node::hasFather(), bpp::Node::hasNoSon(), bpp::TreeTemplateTools::OrderTreeData_::size, bpp::VectorTools::sum(), bpp::Node::swap(), bpp::VectorTools::whichMax(), bpp::VectorTools::whichMaxAll(), bpp::VectorTools::whichMin(), and bpp::VectorTools::whichMinAll().

Referenced by orderTree().

◆ parenthesisToNode()

Node * TreeTemplateTools::parenthesisToNode	(	const std::string &	description,
		unsigned int &	nodeCounter,
		bool	bootstrap = `true`,
		const std::string &	propertyName = `TreeTools::BOOTSTRAP`,
		bool	withId = `false`,
		bool	verbose = `true`
	)

static

Parse a string in the parenthesis format and convert it to a subtree.

Parameters

description	the string to parse;
nodeCounter	[Output] Count all created nodes.
bootstrap	Tell is real bootstrap values are expected. If so, a property with name TreeTools::BOOTSTRAP will be created and stored at the corresponding node. The property value will be of type Number<double>. Otherwise, an object of type String will be created and stored with the property name propertyName.
propertyName	The name of the property to store. Only used if bootstrap = false.
withId	Tells if node ids have been stored in the tree. If set at "true", no bootstrap or property values can be read. Node ids are positioned as bootstrap values for internal nodes, and are concatenated to leaf names after a "_" sign.
verbose	Tell if some information should be displayed, like progress bars for large trees.

Returns: A pointer toward a dynamically created subtree.

Definition at line 247 of file TreeTemplateTools.cpp.

References bpp::Node::addSon(), bpp::TreeTemplateTools::Element::bootstrap, bpp::TreeTools::BOOTSTRAP, bpp::TreeTemplateTools::Element::content, bpp::ApplicationTools::displayUnlimitedGauge(), bpp::StringTokenizer::getToken(), bpp::NestedStringTokenizer::hasMoreToken(), bpp::TextTools::isEmpty(), bpp::TreeTemplateTools::Element::isLeaf, bpp::TreeTemplateTools::Element::length, bpp::NestedStringTokenizer::nextToken(), bpp::StringTokenizer::numberOfRemainingTokens(), bpp::TextTools::removeSurroundingWhiteSpaces(), bpp::Node::setBranchProperty(), bpp::Node::setDistanceToFather(), bpp::Node::setId(), bpp::Node::setName(), bpp::TextTools::toDouble(), and bpp::TextTools::toInt().

◆ parenthesisToTree()

unique_ptr< TreeTemplate< Node > > TreeTemplateTools::parenthesisToTree	(	const std::string &	description,
		bool	bootstrap = `true`,
		const std::string &	propertyName = `TreeTools::BOOTSTRAP`,
		bool	withId = `false`,
		bool	verbose = `true`
	)

static

Parse a string in the parenthesis format and convert it to a tree.

Parameters

description	the string to parse;
bootstrap	Tells if real bootstrap values are expected. If so, a property with name TreeTools::BOOTSTRAP will be created and stored at the corresponding node. The property value will be of type Number<double>. Otherwise, an object of type String will be created and stored with the property name propertyName.
propertyName	The name of the property to store. Only used if bootstrap = false.
withId	Tells if node ids have been stored in the tree. If set at "true", no bootstrap or property values can be read. Node ids are positioned as bootstrap values for internal nodes, and are concatenated to leaf names after a "_" sign.
verbose	Tell if some information should be displayed, like progress bars for large trees.

Returns: A pointer toward a dynamically created tree.

Exceptions

Exception in case of bad format.

Definition at line 328 of file TreeTemplateTools.cpp.

References bpp::ApplicationTools::message.

Referenced by bpp::Newick::readTrees(), bpp::NexusIOTree::readTrees(), and bpp::Newick::readTreeTemplate().

◆ processDistsInSubtree_()

void TreeTemplateTools::processDistsInSubtree_	(	const Node *	node,
		DistanceMatrix &	matrix,
		std::vector< std::pair< std::string, double >> &	distsToNodeFather
	)

staticprivate

Inner function used by getDistanceMatrix.

(1) Retrieves leaf-leaf distances in node's subtree and writes them in the distance matrix. (2) Returns distances from node's father to those leaves.

Parameters

node	The current node in the recursion.
matrix	The output matrix which will be filled.
distsToNodeFather	Intermediate computations containing the distances of the node to the leaves.

Definition at line 791 of file TreeTemplateTools.cpp.

References bpp::Node::getDistanceToFather(), bpp::Node::getName(), bpp::Node::getNumberOfSons(), bpp::Node::getSon(), bpp::Node::hasFather(), and bpp::Node::hasNoSon().

◆ sampleSubtree()

template<class N >

static void bpp::TreeTemplateTools::sampleSubtree	(	TreeTemplate< N > &	tree,
		const std::vector< std::string > &	leaves,
		size_t	size
	)

inlinestatic

Sample a subtree by removing leaves randomly.

Parameters

tree	The tree to edit.
leaves	The leafs names that should be sampled. They must be found in the tree otherwise an exception will be thrown.
size	The number of leaves in the final sample. If greater or equal to the number of leaf names, the function returns without doing anything.

Definition at line 256 of file TreeTemplateTools.h.

References dropLeaf(), and bpp::RandomTools::giveIntRandomNumberBetweenZeroAndEntry().

◆ scaleTree()

void TreeTemplateTools::scaleTree	(	Node &	node,
		double	factor
	)

static

Scale a given tree.

Multiply all branch lengths by a given factor.

Parameters

node	The root node of the subtree to scale.
factor	The factor to multiply all branch lengths with.

Exceptions

NodePException If a branch length is lacking.

Definition at line 567 of file TreeTemplateTools.cpp.

References bpp::Node::getDistanceToFather(), bpp::Node::getNumberOfSons(), bpp::Node::getSon(), bpp::Node::hasFather(), and bpp::Node::setDistanceToFather().

Referenced by bpp::TreeTemplate< N >::scaleTree().

◆ searchFirstNodeWithId() [1/2]

static const Node* bpp::TreeTemplateTools::searchFirstNodeWithId	(	const Node &	node,
		int	id
	)

inlinestatic

Parameters

node	The node defining the subtree to be searched.
id	The id to search for.

Returns: The first node encountered with the given id, or 0 if no node with the given id is found.

Definition at line 443 of file TreeTemplateTools.h.

References bpp::Node::getId(), bpp::Node::getNumberOfSons(), bpp::Node::getSon(), and searchFirstNodeWithId().

◆ searchFirstNodeWithId() [2/2]

static Node* bpp::TreeTemplateTools::searchFirstNodeWithId	(	Node &	node,
		int	id
	)

inlinestatic

Parameters

node	The node defining the subtree to be searched.
id	The id to search for.

Returns: The first node encountered with the given id, or 0 if no node with the given id is found.

Definition at line 422 of file TreeTemplateTools.h.

References bpp::Node::getId(), bpp::Node::getNumberOfSons(), and bpp::Node::getSon().

Referenced by bpp::TreeTemplate< N >::getNode(), and searchFirstNodeWithId().

◆ searchLeaf()

void TreeTemplateTools::searchLeaf	(	const Node &	node,
		const std::string &	name,
		int *&	id
	)

static

Get the id of a leaf given its name in a subtree.

Parameters

node	The node defining the subtree to search.
name	The name of the node.
id	The id of the node.

Exceptions

NodeNotFoundException If the node is not found.

Definition at line 102 of file TreeTemplateTools.cpp.

References bpp::Node::getId(), bpp::Node::getName(), bpp::Node::getNumberOfSons(), bpp::Node::getSon(), and bpp::Node::hasNoSon().

Referenced by getLeafId().

◆ searchNodeWithId() [1/2]

template<class N >

static std::vector<N*> bpp::TreeTemplateTools::searchNodeWithId	(	N &	node,
		int	id
	)

inlinestatic

Parameters

node	The node defining the subtree to be searched.
id	The id to search for.

Returns: Nodes with the specified id.

Definition at line 395 of file TreeTemplateTools.h.

◆ searchNodeWithId() [2/2]

template<class N >

static void bpp::TreeTemplateTools::searchNodeWithId	(	N &	node,
		int	id,
		std::vector< N * > &	nodes
	)

inlinestatic

Parameters

node	The node defining the subtree to be searched.
id	The id to search for.
nodes	A vector to be filled with the matching nodes.

Definition at line 408 of file TreeTemplateTools.h.

◆ searchNodeWithName() [1/2]

template<class N >

static std::vector<N*> bpp::TreeTemplateTools::searchNodeWithName	(	N &	node,
		const std::string &	name
	)

inlinestatic

Parameters

node	The node defining the subtree to be searched.
name	The name to search for.

Returns: Nodes with the specified name.

Definition at line 484 of file TreeTemplateTools.h.

Referenced by bpp::TreeTemplate< N >::getNode().

◆ searchNodeWithName() [2/2]

template<class N >

static void bpp::TreeTemplateTools::searchNodeWithName	(	N &	node,
		const std::string &	name,
		std::vector< N * > &	nodes
	)

inlinestatic

Parameters

node	The node defining the subtree to be searched.
name	The name to search for.
nodes	A vector to be filled with the matching nodes.

Definition at line 497 of file TreeTemplateTools.h.

◆ setBranchLengths()

void TreeTemplateTools::setBranchLengths	(	Node &	node,
		double	brLen
	)

static

Set all the branch lengths of a subtree.

Parameters

node	The root node of the subtree.
brLen	The branch length to apply.

Definition at line 533 of file TreeTemplateTools.cpp.

References bpp::Node::getNumberOfSons(), bpp::Node::getSon(), and bpp::Node::setDistanceToFather().

Referenced by bpp::TreeTemplate< N >::setBranchLengths().

◆ setVoidBranchLengths()

void TreeTemplateTools::setVoidBranchLengths	(	Node &	node,
		double	brLen
	)

static

Give a length to branches that don't have one in a subtree.

Parameters

node	The root node of the subtree.
brLen	The branch length to apply.

Definition at line 555 of file TreeTemplateTools.cpp.

References bpp::Node::getNumberOfSons(), bpp::Node::getSon(), bpp::Node::hasDistanceToFather(), and bpp::Node::setDistanceToFather().

Referenced by bpp::TreeTemplate< N >::setVoidBranchLengths().

◆ treeToParenthesis() [1/2]

string TreeTemplateTools::treeToParenthesis	(	const TreeTemplate< Node > &	tree,
		bool	bootstrap,
		const std::string &	propertyName
	)

static

Get the parenthesis description of a tree.

Parameters

tree	The tree to convert.
bootstrap	Tell is bootstrap values must be written. If so, the content of the property with name TreeTools::BOOTSTRAP will be written as bootstrap value. The property should be a Number<double> object. Otherwise, the content of the property with name 'propertyName' will be written. In this later case, the property should be a String object.
propertyName	The name of the property to use. Only used if bootstrap = false.

Returns: A string in the parenthesis format.

Definition at line 458 of file TreeTemplateTools.cpp.

References bpp::TreeTools::BOOTSTRAP, bpp::Node::getBranchProperty(), bpp::Node::getName(), bpp::Node::getNumberOfSons(), bpp::TreeTemplate< N >::getRootNode(), bpp::Node::getSon(), bpp::Node::hasBranchProperty(), and bpp::Node::hasNoSon().

◆ treeToParenthesis() [2/2]

string TreeTemplateTools::treeToParenthesis	(	const TreeTemplate< Node > &	tree,
		bool	writeId = `false`
	)

static

Get the parenthesis description of a tree.

Parameters

tree	The tree to convert.
writeId	Tells if node ids must be printed. This will overwrite bootstrap values if there are ones. Leaves id will be added to the leave names, separated by a '_' character.

Returns: A string in the parenthesis format.

Definition at line 428 of file TreeTemplateTools.cpp.

References bpp::Node::getDistanceToFather(), bpp::Node::getName(), bpp::Node::getNumberOfSons(), bpp::TreeTemplate< N >::getRootNode(), bpp::Node::getSon(), bpp::Node::hasDistanceToFather(), and bpp::Node::hasNoSon().

Referenced by bpp::NexusIOTree::write_(), and bpp::Newick::write_().

◆ unresolveUncertainNodes()

void TreeTemplateTools::unresolveUncertainNodes	(	Node &	subtree,
		double	threshold,
		const std::string &	property = `TreeTools::BOOTSTRAP`
	)

static

Unresolve nodes with low confidence value.

The underlying branches will be removed, resulting in a multifurcation. the branch length of the removed node is added to the length of its son nodes, so that pairwise phylogenetic distances are conserved along the tree. Leaves are not checked. Node with missing values are ignored.

Author: Julien Dutheil.

Parameters

subtree	The node defining the subtree where nodes should be collapsed.
threshold	The minimum value for which a node is considered to be confident.
property	The branch property to be considered as a confidence value (bootstrap values by default).

Definition at line 1207 of file TreeTemplateTools.cpp.

References bpp::Node::addSon(), bpp::Node::getBranchProperty(), bpp::Node::getDistanceToFather(), bpp::Node::getNumberOfSons(), bpp::Node::getSon(), bpp::Node::hasBranchProperty(), bpp::Node::removeSon(), and bpp::Node::setDistanceToFather().

Member Data Documentation

◆ MIDROOT_SUM_OF_SQUARES

const short TreeTemplateTools::MIDROOT_SUM_OF_SQUARES = 1

static

Definition at line 1231 of file TreeTemplateTools.h.

◆ MIDROOT_VARIANCE

const short TreeTemplateTools::MIDROOT_VARIANCE = 0

static

Definition at line 1230 of file TreeTemplateTools.h.

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

Bpp/Phyl/Tree/TreeTemplateTools.h
Bpp/Phyl/Tree/TreeTemplateTools.cpp

Classes

Public Member Functions

Static Public Member Functions

Static Public Attributes

Static Private Member Functions

Act on branch lengths.

Detailed Description

Constructor & Destructor Documentation

◆ TreeTemplateTools()

◆ ~TreeTemplateTools()

Member Function Documentation

◆ buildFromPhyloTree()

◆ cloneSubtree() [1/2]

◆ cloneSubtree() [2/2]

◆ deleteBranchLengths()

◆ deleteBranchProperties()

◆ deleteNodeProperties()

◆ deleteSubtree()

◆ dropLeaf()

◆ dropSubtree()

◆ getAncestorsId()

◆ getBestRootInSubtree_()

◆ getBranchLengths()

◆ getBranchProperties() [1/2]

◆ getBranchProperties() [2/2]

◆ getBranchPropertyNames()

◆ getDepth()

◆ getDepths()

◆ getDistanceBetweenAnyTwoNodes()

◆ getDistanceMatrix()

◆ getElement()

◆ getHeight()

◆ getHeights()

◆ getInnerNodes() [1/2]

◆ getInnerNodes() [2/2]

◆ getInnerNodesId() [1/2]

◆ getInnerNodesId() [2/2]

◆ getLeafId()

◆ getLeaves() [1/2]

◆ getLeaves() [2/2]

◆ getLeavesId() [1/2]

◆ getLeavesId() [2/2]

◆ getLeavesNames()

◆ getNodeProperties() [1/2]

◆ getNodeProperties() [2/2]

◆ getNodePropertyNames()

◆ getNodes() [1/2]

◆ getNodes() [2/2]

◆ getNodesId() [1/2]

◆ getNodesId() [2/2]

◆ getNumberOfBranches()

◆ getNumberOfLeaves()

◆ getNumberOfNodes()

◆ getPathBetweenAnyTwoNodes() [1/2]

◆ getPathBetweenAnyTwoNodes() [2/2]

◆ getRadius()

◆ getRandomTree()

◆ getRemainingNeighbors()

◆ getSubtreeMoments_()

◆ getTotalLength()

◆ hasNodeWithId()

◆ hasNodeWithName()

◆ haveSameOrderedTopology()

◆ incrementAllIds()

◆ isMultifurcating()

◆ isRoot()

◆ midRoot()

◆ nodeToParenthesis() [1/2]

◆ nodeToParenthesis() [2/2]

◆ orderTree()

◆ orderTree_()

◆ parenthesisToNode()

◆ parenthesisToTree()

◆ processDistsInSubtree_()

◆ sampleSubtree()

◆ scaleTree()

◆ searchFirstNodeWithId() [1/2]

◆ searchFirstNodeWithId() [2/2]

◆ searchLeaf()

◆ searchNodeWithId() [1/2]