A toolkit for working with phylogenetic data.
v0.19.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 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 node_count( Tree const& tree );
83 
87 size_t leaf_edge_count( Tree const& tree );
88 
92 size_t inner_edge_count( Tree const& tree );
93 
97 size_t edge_count( Tree const& tree );
98 
103 std::vector<size_t> inner_edge_indices( Tree const& tree );
104 
109 std::vector<size_t> leaf_edge_indices( Tree const& tree );
110 
115 std::vector<size_t> inner_node_indices( Tree const& tree );
116 
121 std::vector<size_t> leaf_node_indices( Tree const& tree );
122 
123 // =================================================================================================
124 // Tree Sides
125 // =================================================================================================
126 
144 utils::Matrix<signed char> edge_sides( Tree const& tree );
145 
154 utils::Matrix<signed char> node_root_direction_matrix( Tree const& tree );
155 
156 // TODO the naming convention of the above two functions is really off!
157 
158 // =================================================================================================
159 // Subtrees
160 // =================================================================================================
161 
165 size_t subtree_size( Tree const& tree, TreeLink const& link );
166 
183 std::vector<size_t> subtree_sizes( Tree const& tree, TreeNode const& node );
184 
191 std::vector<size_t> subtree_sizes( Tree const& tree );
192 
197 size_t subtree_max_path_height( Tree const& tree, TreeLink const& link );
198 
199 std::vector<size_t> subtree_max_path_heights( Tree const& tree, TreeNode const& node );
200 std::vector<size_t> subtree_max_path_heights( Tree const& tree );
201 
202 // =================================================================================================
203 // Misc
204 // =================================================================================================
205 
214 std::vector< TreeLink const* > path_to_root( TreeNode const& node );
215 
219 TreeNode const& lowest_common_ancestor( TreeNode const& node_a, TreeNode const& node_b );
220 
224 TreeNode& lowest_common_ancestor( TreeNode& node_a, TreeNode& node_b );
225 
236 utils::Matrix<size_t> lowest_common_ancestors( Tree const& tree );
237 
238 } // namespace tree
239 } // namespace genesis
240 
241 #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 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 > 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_bifurcating(Tree const &tree)
Return whether the Tree is bifurcating.
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().