A toolkit for working with phylogenetic data.
v0.18.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-2017 Lucas Czech
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 Count Properties
53 // =================================================================================================
54 
55 // TODO add other interesting member functions: http://en.wikipedia.org/wiki/Tree_%28data_structure%29
56 
62 size_t max_rank( Tree const& tree );
63 
67 bool is_bifurcating( Tree const& tree );
68 
72 size_t leaf_node_count( Tree const& tree );
73 
77 size_t inner_node_count( Tree const& tree );
78 
82 size_t leaf_edge_count( Tree const& tree );
83 
87 size_t inner_edge_count( Tree const& tree );
88 
89 // =================================================================================================
90 // Tree Sides
91 // =================================================================================================
92 
110 utils::Matrix<signed char> edge_sides( Tree const& tree );
111 
120 utils::Matrix<signed char> node_root_direction_matrix( Tree const& tree );
121 
122 // TODO the naming convention of the above two functions is really off!
123 
124 // =================================================================================================
125 // Subtrees
126 // =================================================================================================
127 
131 size_t subtree_size( Tree const& tree, TreeLink const& link );
132 
149 std::vector<size_t> subtree_sizes( Tree const& tree, TreeNode const& node );
150 
157 std::vector<size_t> subtree_sizes( Tree const& tree );
158 
163 size_t subtree_max_path_height( Tree const& tree, TreeLink const& link );
164 
165 std::vector<size_t> subtree_max_path_heights( Tree const& tree, TreeNode const& node );
166 std::vector<size_t> subtree_max_path_heights( Tree const& tree );
167 
168 // =================================================================================================
169 // Misc
170 // =================================================================================================
171 
180 std::vector< TreeLink const* > path_to_root( TreeNode const& node );
181 
185 TreeNode const& lowest_common_ancestor( TreeNode const& node_a, TreeNode const& node_b );
186 
190 TreeNode& lowest_common_ancestor( TreeNode& node_a, TreeNode& node_b );
191 
202 utils::Matrix<size_t> lowest_common_ancestors( Tree const& tree );
203 
204 } // namespace tree
205 } // namespace genesis
206 
207 #endif // include guard
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.
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 max_rank(Tree const &tree)
Return the highest rank of the Nodes of a Tree.
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...
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.
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 ...
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.
bool is_bifurcating(Tree const &tree)
Return whether the Tree is bifurcating.
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...