A toolkit for working with phylogenetic data.
v0.20.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
lca_lookup.hpp
Go to the documentation of this file.
1 #ifndef GENESIS_TREE_FUNCTION_LCA_LOOKUP_H_
2 #define GENESIS_TREE_FUNCTION_LCA_LOOKUP_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 
34 #include "genesis/utils/math/range_minimum_query.hpp"
35 
36 #include <vector>
37 
38 namespace genesis {
39 namespace tree {
40 
41 // =================================================================================================
42 // Forward Declarations
43 // =================================================================================================
44 
45 class Tree;
46 class TreeNode;
47 
48 // =================================================================================================
49 // LCA Lookup
50 // =================================================================================================
51 
66 class LcaLookup
67 {
68 public:
69 
70  // -------------------------------------------------------------------------
71  // Construction and Rule of Five
72  // -------------------------------------------------------------------------
73 
74  LcaLookup() = default;
75  explicit LcaLookup( Tree const& tree );
76 
77  ~LcaLookup() = default;
78 
79  LcaLookup( LcaLookup const& other ) = default;
80  LcaLookup( LcaLookup&& ) = default;
81 
82  LcaLookup& operator= ( LcaLookup const& other ) = default;
83  LcaLookup& operator= ( LcaLookup&& ) = default;
84 
85  // -------------------------------------------------------------------------
86  // Lookup
87  // -------------------------------------------------------------------------
88 
89  std::size_t operator()( size_t node_index_a, size_t node_index_b, size_t root_index ) const;
90  TreeNode const& operator()( TreeNode const& node_a, TreeNode const& node_b, TreeNode const& root_node ) const;
91 
92  size_t operator()( size_t node_index_a, size_t node_index_b ) const;
93  TreeNode const& operator()( TreeNode const& node_a, TreeNode const& node_b ) const;
94 
95  // -------------------------------------------------------------------------
96  // Internal Helper Functions
97  // -------------------------------------------------------------------------
98 
99 private:
100 
101  void init_( Tree const& tree );
102 
110  size_t eulertour_query_( size_t i, size_t j ) const;
111 
116  size_t lookup_( size_t node_index_a, size_t node_index_b, size_t root_index ) const;
117 
118  // -------------------------------------------------------------------------
119  // Data Members
120  // -------------------------------------------------------------------------
121 
122 private:
123 
128  utils::RangeMinimumQuery eulertour_rmq_;
129 
133  std::vector<size_t> eulertour_order_;
134 
138  std::vector<size_t> eulertour_first_occurrence_;
139 
140  Tree const& tree_;
141  size_t root_idx_;
142 };
143 
144 } // namespace tree
145 } // namespace genesis
146 
147 #endif // include guard
genesis::utils::RangeMinimumQuery
Class that allows to efficiently find the index of the minimum element within an interval of an array...
Definition: range_minimum_query.hpp:61
genesis::tree::LcaLookup
Fast lookup of the lowest common ancestor (LCA) of two TreeNodes, relative to an arbitrary root node...
Definition: lca_lookup.hpp:66
genesis::tree::LcaLookup::operator=
LcaLookup & operator=(LcaLookup const &other)=default
genesis::tree::Tree
Class for representing phylogenetic trees.
Definition: tree/tree.hpp:95
genesis::tree::LcaLookup::operator()
std::size_t operator()(size_t node_index_a, size_t node_index_b, size_t root_index) const
Definition: lca_lookup.cpp:60
range_minimum_query.hpp