A library for working with phylogenetic and population genetic data.
v0.27.0
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_leaf( TreeNode const& node );
64 
68 bool is_leaf( TreeEdge const& edge );
69 
73 bool is_inner( TreeLink const& link );
74 
78 bool is_inner( TreeNode const& node );
79 
83 bool is_inner( TreeEdge const& edge );
84 
88 bool is_root( TreeLink const& link );
89 
93 bool is_root( TreeNode const& node );
94 
99 size_t degree( TreeLink const& link );
100 
104 size_t degree( TreeNode const& node );
105 
106 // =================================================================================================
107 // Node Count Properties
108 // =================================================================================================
109 
110 // TODO add other interesting member functions: http://en.wikipedia.org/wiki/Tree_%28data_structure%29
111 
117 size_t max_degree( Tree const& tree );
118 
133 bool is_bifurcating( Tree const& tree, bool loose = false );
134 
138 bool is_binary( Tree const& tree, bool loose = false );
139 
143 bool is_rooted( Tree const& tree );
144 
148 size_t leaf_node_count( Tree const& tree );
149 
153 size_t inner_node_count( Tree const& tree );
154 
158 size_t node_count( Tree const& tree );
159 
163 size_t leaf_edge_count( Tree const& tree );
164 
168 size_t inner_edge_count( Tree const& tree );
169 
173 size_t edge_count( Tree const& tree );
174 
179 std::vector<size_t> inner_edge_indices( Tree const& tree );
180 
185 std::vector<size_t> leaf_edge_indices( Tree const& tree );
186 
191 std::vector<size_t> inner_node_indices( Tree const& tree );
192 
197 std::vector<size_t> leaf_node_indices( Tree const& tree );
198 
199 // =================================================================================================
200 // Tree Sides
201 // =================================================================================================
202 
220 utils::Matrix<signed char> edge_sides( Tree const& tree );
221 
230 utils::Matrix<signed char> node_root_direction_matrix( Tree const& tree );
231 
232 // TODO the naming convention of the above two functions is really off!
233 
234 // =================================================================================================
235 // Subtrees
236 // =================================================================================================
237 
241 size_t subtree_size( Tree const& tree, TreeLink const& link );
242 
259 std::vector<size_t> subtree_sizes( Tree const& tree, TreeNode const& node );
260 
267 std::vector<size_t> subtree_sizes( Tree const& tree );
268 
273 size_t subtree_max_path_height( Tree const& tree, TreeLink const& link );
274 
275 std::vector<size_t> subtree_max_path_heights( Tree const& tree, TreeNode const& node );
276 std::vector<size_t> subtree_max_path_heights( Tree const& tree );
277 
325 utils::Matrix<signed char> sign_matrix( Tree const& tree, bool compressed = false );
326 
327 // =================================================================================================
328 // Misc
329 // =================================================================================================
330 
339 std::vector< TreeLink const* > path_to_root( TreeNode const& node );
340 
344 TreeNode const& lowest_common_ancestor( TreeNode const& node_a, TreeNode const& node_b );
345 
349 TreeNode& lowest_common_ancestor( TreeNode& node_a, TreeNode& node_b );
350 
361 utils::Matrix<size_t> lowest_common_ancestors( Tree const& tree );
362 
363 } // namespace tree
364 } // namespace genesis
365 
366 #endif // include guard
genesis::tree::leaf_node_count
size_t leaf_node_count(Tree const &tree)
Count the number of leaf Nodes of a Tree.
Definition: tree/function/functions.cpp:168
genesis::tree::subtree_max_path_heights
std::vector< size_t > subtree_max_path_heights(Tree const &tree, TreeNode const &node)
Definition: tree/function/functions.cpp:461
genesis::tree::inner_node_count
size_t inner_node_count(Tree const &tree)
Count the number of inner Nodes.
Definition: tree/function/functions.cpp:180
genesis::tree::sign_matrix
utils::Matrix< signed char > sign_matrix(Tree const &tree, bool compressed)
Compute the sign matrix or Sequential Binary Partition (SBP) of a Tree.
Definition: tree/function/functions.cpp:505
genesis::tree::is_inner
bool is_inner(TreeLink const &link)
Return true iff the node of the given link is an inner node.
Definition: tree/function/functions.cpp:74
genesis::tree::is_binary
bool is_binary(Tree const &tree, bool loose)
Alias for is_bifurcating().
Definition: tree/function/functions.cpp:158
genesis::tree::lowest_common_ancestor
TreeNode const & lowest_common_ancestor(TreeNode const &node_a, TreeNode const &node_b)
Return the lowest common ancestor of two TreeNodes.
Definition: tree/function/functions.cpp:613
genesis::tree::subtree_max_path_height
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,...
Definition: tree/function/functions.cpp:440
genesis::tree::inner_edge_indices
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 ...
Definition: tree/function/functions.cpp:217
genesis::tree::degree
size_t degree(TreeLink const &link)
Return the degree of the node for a given TreeLink, i.e. how many neighbouring nodes it has.
Definition: tree/function/functions.cpp:103
genesis::tree::max_degree
size_t max_degree(Tree const &tree)
Return the highest degree of the Nodes of a Tree.
Definition: tree/function/functions.cpp:125
genesis::tree::path_to_root
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.
Definition: tree/function/functions.cpp:580
genesis::tree::leaf_edge_count
size_t leaf_edge_count(Tree const &tree)
Return the number of Edges of a Tree that lead to a leaf Node.
Definition: tree/function/functions.cpp:190
genesis::tree::node_count
size_t node_count(Tree const &tree)
Return the number of Nodes of a Tree. Same as Tree::node_count().
Definition: tree/function/functions.cpp:185
genesis::tree::is_root
bool is_root(TreeLink const &link)
Return whether the link belongs to the root node of its Tree.
Definition: tree/function/functions.cpp:89
matrix.hpp
genesis
Container namespace for all symbols of genesis in order to keep them separate when used as a library.
Definition: placement/formats/edge_color.cpp:42
genesis::tree::inner_edge_count
size_t inner_edge_count(Tree const &tree)
Return the number of Edges of a Tree that do not lead to a leaf Node.
Definition: tree/function/functions.cpp:201
genesis::tree::is_bifurcating
bool is_bifurcating(Tree const &tree, bool loose)
Return whether the Tree is bifurcating.
Definition: tree/function/functions.cpp:134
genesis::tree::subtree_sizes
std::vector< size_t > subtree_sizes(Tree const &tree, TreeNode const &node)
Calculate the sizes of all subtrees as seen from the given TreeNode.
Definition: tree/function/functions.cpp:367
genesis::tree::leaf_edge_indices
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...
Definition: tree/function/functions.cpp:228
genesis::tree::leaf_node_indices
std::vector< size_t > leaf_node_indices(Tree const &tree)
Get a list of the node indices of all leaf TreeNodes.
Definition: tree/function/functions.cpp:250
genesis::tree::is_rooted
bool is_rooted(Tree const &tree)
Return whether the Tree is rooted, that is, whether the root node has two neighbors.
Definition: tree/function/functions.cpp:163
genesis::tree::lowest_common_ancestors
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 ...
Definition: tree/function/functions.cpp:656
genesis::tree::edge_sides
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....
Definition: tree/function/functions.cpp:265
genesis::tree::inner_node_indices
std::vector< size_t > inner_node_indices(Tree const &tree)
Get a list of the node indices of all inner TreeNodes.
Definition: tree/function/functions.cpp:239
genesis::tree::subtree_size
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.
Definition: tree/function/functions.cpp:345
genesis::tree::is_leaf
bool is_leaf(TreeLink const &link)
Return true iff the node of the given link is a leaf node.
Definition: tree/function/functions.cpp:59
genesis::tree::edge_count
size_t edge_count(Tree const &tree)
Return the number of Edges of a Tree. Same as Tree::edge_count().
Definition: tree/function/functions.cpp:212
genesis::tree::node_root_direction_matrix
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.
Definition: tree/function/functions.cpp:292