A toolkit for working with phylogenetic data.
v0.20.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
tree/function/functions.hpp
Go to the documentation of this file.
1 #ifndef GENESIS_TREE_FUNCTION_FUNCTIONS_H_
2 #define GENESIS_TREE_FUNCTION_FUNCTIONS_H_
3 
4 /*
5  Genesis - A toolkit for working with phylogenetic data.
6  Copyright (C) 2014-2018 Lucas Czech and HITS gGmbH
7 
8  This program is free software: you can redistribute it and/or modify
9  it under the terms of the GNU General Public License as published by
10  the Free Software Foundation, either version 3 of the License, or
11  (at your option) any later version.
12 
13  This program is distributed in the hope that it will be useful,
14  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  GNU General Public License for more details.
17 
18  You should have received a copy of the GNU General Public License
19  along with this program. If not, see <http://www.gnu.org/licenses/>.
20 
21  Contact:
22  Lucas Czech <lucas.czech@h-its.org>
23  Exelixis Lab, Heidelberg Institute for Theoretical Studies
24  Schloss-Wolfsbrunnenweg 35, D-69118 Heidelberg, Germany
25 */
26 
35 
36 #include <cstddef> // size_t
37 #include <vector>
38 
39 namespace genesis {
40 namespace tree {
41 
42 // =================================================================================================
43 // Forward Declarations
44 // =================================================================================================
45 
46 class Tree;
47 class TreeNode;
48 class TreeEdge;
49 class TreeLink;
50 
51 // =================================================================================================
52 // Node Properties
53 // =================================================================================================
54 
58 bool is_leaf( TreeLink const& link );
59 
63 bool is_inner( TreeLink const& link );
64 
68 bool is_leaf( TreeEdge const& edge );
69 
73 bool is_inner( TreeEdge const& edge );
74 
78 size_t degree( TreeNode const& node );
79 
83 bool is_leaf( TreeNode const& node );
84 
88 bool is_inner( TreeNode const& node );
89 
93 bool is_root( TreeNode const& node );
94 
95 // =================================================================================================
96 // Node Count Properties
97 // =================================================================================================
98 
99 // TODO add other interesting member functions: http://en.wikipedia.org/wiki/Tree_%28data_structure%29
100 
106 size_t max_degree( Tree const& tree );
107 
115 bool is_bifurcating( Tree const& tree, bool strict = false );
116 
120 bool is_rooted( Tree const& tree );
121 
125 size_t leaf_node_count( Tree const& tree );
126 
130 size_t inner_node_count( Tree const& tree );
131 
135 size_t node_count( Tree const& tree );
136 
140 size_t leaf_edge_count( Tree const& tree );
141 
145 size_t inner_edge_count( Tree const& tree );
146 
150 size_t edge_count( Tree const& tree );
151 
156 std::vector<size_t> inner_edge_indices( Tree const& tree );
157 
162 std::vector<size_t> leaf_edge_indices( Tree const& tree );
163 
168 std::vector<size_t> inner_node_indices( Tree const& tree );
169 
174 std::vector<size_t> leaf_node_indices( Tree const& tree );
175 
176 // =================================================================================================
177 // Tree Sides
178 // =================================================================================================
179 
197 utils::Matrix<signed char> edge_sides( Tree const& tree );
198 
207 utils::Matrix<signed char> node_root_direction_matrix( Tree const& tree );
208 
209 // TODO the naming convention of the above two functions is really off!
210 
211 // =================================================================================================
212 // Subtrees
213 // =================================================================================================
214 
218 size_t subtree_size( Tree const& tree, TreeLink const& link );
219 
236 std::vector<size_t> subtree_sizes( Tree const& tree, TreeNode const& node );
237 
244 std::vector<size_t> subtree_sizes( Tree const& tree );
245 
250 size_t subtree_max_path_height( Tree const& tree, TreeLink const& link );
251 
252 std::vector<size_t> subtree_max_path_heights( Tree const& tree, TreeNode const& node );
253 std::vector<size_t> subtree_max_path_heights( Tree const& tree );
254 
255 // =================================================================================================
256 // Misc
257 // =================================================================================================
258 
267 std::vector< TreeLink const* > path_to_root( TreeNode const& node );
268 
272 TreeNode const& lowest_common_ancestor( TreeNode const& node_a, TreeNode const& node_b );
273 
277 TreeNode& lowest_common_ancestor( TreeNode& node_a, TreeNode& node_b );
278 
289 utils::Matrix<size_t> lowest_common_ancestors( Tree const& tree );
290 
291 } // namespace tree
292 } // namespace genesis
293 
294 #endif // include guard
std::vector< size_t > inner_node_indices(Tree const &tree)
Get a list of the node indices of all inner TreeNodes.
size_t inner_node_count(Tree const &tree)
Count the number of inner Nodes.
TreeNode const & lowest_common_ancestor(TreeNode const &node_a, TreeNode const &node_b)
Return the lowest common ancestor of two TreeNodes.
std::vector< size_t > leaf_node_indices(Tree const &tree)
Get a list of the node indices of all leaf TreeNodes.
size_t inner_edge_count(Tree const &tree)
Return the number of Edges of a Tree that do not lead to a leaf Node.
size_t degree(TreeNode const &node)
Return the degree of the node, i.e. how many neighbouring nodes it has.
bool is_bifurcating(Tree const &tree, bool strict)
Return whether the Tree is bifurcating.
utils::Matrix< signed char > node_root_direction_matrix(Tree const &tree)
Calculate a Matrix that indicates the nodes on the root side of a given node.
size_t subtree_max_path_height(Tree const &tree, TreeLink const &link)
Calculate the height of a subtree, that is, the maximum path length to a leaf of that subtree...
bool is_root(TreeNode const &node)
Return whether the node is the root of its Tree.
size_t leaf_node_count(Tree const &tree)
Count the number of leaf Nodes of a Tree.
utils::Matrix< signed char > edge_sides(Tree const &tree)
Create a Matrix that indiciaces the relative position of the Edges of a Tree, i.e., whether they are on the root side or non-root side.
bool is_leaf(TreeLink const &link)
Return true iff the node of the given link is a leaf node.
std::vector< size_t > subtree_sizes(Tree const &tree, TreeNode const &node)
Calculate the sizes of all subtrees as seen from the given TreeNode.
size_t subtree_size(Tree const &tree, TreeLink const &link)
Return the size of the subtree defined by the given TreeLink, measured in number of nodes...
utils::Matrix< size_t > lowest_common_ancestors(Tree const &tree)
Return the lowest common ancestor of each pair of TreeNodes for a given tree, in form of a Matrix of ...
size_t max_degree(Tree const &tree)
Return the highest degree of the Nodes of a Tree.
bool is_inner(TreeLink const &link)
Return true iff the node of the given link is an inner node.
std::vector< size_t > leaf_edge_indices(Tree const &tree)
Get a list of the edge indices of all leaf edges, that is, all TreeEdges that lead to a leaf TreeNode...
std::vector< size_t > subtree_max_path_heights(Tree const &tree, TreeNode const &node)
size_t leaf_edge_count(Tree const &tree)
Return the number of Edges of a Tree that lead to a leaf Node.
size_t node_count(Tree const &tree)
Return the number of Nodes of a Tree. Same as Tree::node_count().
bool is_rooted(Tree const &tree)
Return whether the Tree is rooted, that is, whether the root node has two neighbors.
std::vector< size_t > inner_edge_indices(Tree const &tree)
Get a list of the edge indices of all inner edges, that is, all TreeEdges that do not lead to a leaf ...
std::vector< TreeLink const * > path_to_root(TreeNode const &node)
Helper function that finds all TreeLinks between a given TreeNode and the root of the Tree...
size_t edge_count(Tree const &tree)
Return the number of Edges of a Tree. Same as Tree::edge_count().