ʻOhana
Population structure, admixture history, and selection using learning methods.
jade.tree_controller.hpp
1 /* -------------------------------------------------------------------------
2  Ohana
3  Copyright (c) 2015-2020 Jade Cheng (\___/)
4  Jade Cheng <info@jade-cheng.com> (='.'=)
5  ------------------------------------------------------------------------- */
6 
7 #ifndef JADE_TREE_CONTROLLER_HPP__
8 #define JADE_TREE_CONTROLLER_HPP__
9 
10 #include "jade.controller.hpp"
11 #include "jade.rerooted_tree.hpp"
12 
13 namespace jade
14 {
15  ///
16  /// A template for a class that encodes and decodes parameters for the
17  /// Nelder-Mead algorithm. This class uses a user-specified Newick tree.
18  ///
19  template <typename TValue>
21  : public basic_controller<TValue>
22  {
23  public:
24  /// The value type.
25  typedef TValue value_type;
26 
27  /// The matrix type.
29 
30  /// The options type.
32 
33  /// The settings type.
35 
36  /// The path type.
38 
39  /// The simplex type.
41 
42  /// The rerooted tree type.
44 
45  /// The unrooted tree type.
47 
48  /// The pointer to an unrooted tree type.
49  typedef std::unique_ptr<unrooted_tree_type> unrooted_tree_ptr_type;
50 
51  /// The container type for the simplex.
53 
54  /// The exit condition type for the simplex.
56 
57  ///
58  /// Initializes a new instance of the class based on the specified
59  /// program settings.
60  ///
62  const settings_type & settings) ///< The program settings.
63  : basic_controller<TValue> (settings)
64  , _settings (settings)
65  , _table ()
66  , _unrooted_tree_ptr ()
67  , _rerooted_tree ()
68  {
69  const auto rk = this->get_rk();
70 
71  //
72  // Parse the Newick-formatted file into a tree structure.
73  //
74  _unrooted_tree_ptr.reset(
76  settings.get_options().get_tin()));
77 
78  //
79  // Initialize the rerooted tree.
80  //
81  _rerooted_tree.reset(*_unrooted_tree_ptr);
82 
83  //
84  // Loop over the rows and columns of the lower triangle, and for
85  // each cell in the covariance matrix, create a corresponding
86  // table entry.
87  //
88  for (size_t r = 0; r < rk; r++)
89  for (size_t c = 0; c <= r; c++)
90  _table.emplace_back(_rerooted_tree, r, c);
91  }
92 
93  ///
94  /// Writes results to standard output and files.
95  ///
96  virtual void emit_results(
97  const options_type & opts, ///< The options.
98  const simplex_type & simplex, ///< The simplex.
99  const exit_condition_type & condition) ///< The context.
100  override
101  {
102  //
103  // The base class emits the C matrix; this also has the effect of
104  // updating the tree with the optimized lengths.
105  //
106  basic_controller<TValue>::emit_results(opts, simplex, condition);
107 
108  //
109  // Copy values back to the original tree. First reroot the tree to
110  // its original structure so the order of the children is
111  // consistent with the file specified by the user.
112  //
113  const auto root_id = _unrooted_tree_ptr->get_id();
114  unrooted_tree_ptr_type source_root (
115  _rerooted_tree.get_tree().find_id(root_id)->reroot());
116  _unrooted_tree_ptr->for_each([&](node_type * const target) -> void
117  {
118  const auto id = target->get_id();
119  const auto source = source_root->find_id(id);
120  if (source->has_length())
121  target->set_length(source->get_length());
122  else
123  target->erase_length();
124  });
125 
126  if (opts.is_tout_specified())
127  {
128  const auto & tout = opts.get_tout();
129  std::cout << "Writing tree to " << tout << std::endl;
130  _unrooted_tree_ptr->write(tout);
131  }
132  else
133  {
134  std::cout << "\n[Tree]\n" << *_unrooted_tree_ptr << std::endl;
135  }
136  }
137 
138  // --------------------------------------------------------------------
139  virtual container_type init_parameters() override
140  {
141  container_type container;
142  _copy_tree_to_container(container, _rerooted_tree.get_tree());
143  return container;
144  }
145 
146  protected:
147  ///
148  /// Decodes the specified Nelder-Mead container and stores the result
149  /// into the lower triangle, including the diagonal, of the covariance
150  /// matrix.
151  /// \return True to indicate this method is successful.
152  ///
153  virtual bool _decode_lower(
154  matrix_type & dst, ///< The covariance matrix.
155  const container_type & src) ///< The Nelder-Mead container.
156  override
157  {
158  //
159  // Copy the container values into the tree, which will be used to
160  // build the covariance matrix.
161  //
162  auto iterator = src.begin();
163  _copy_container_to_tree(_rerooted_tree.get_tree(), iterator);
164 
165  //
166  // Loop over every table entry, which corresponds to the lower
167  // triangle of the covariance matrix; compute and store the sum
168  // of the lengths from the nodes that contribute to its value.
169  //
170  for (const auto & entry : _table)
171  dst[entry.i] = entry.p.get_length();
172 
173  //
174  // This method is always successful.
175  //
176  return true;
177  }
178 
179  private:
180  //
181  // An entry in the table holding the index in the covariance matrix
182  // and the set of nodes that contributes to the cell's value.
183  //
184  struct table_entry
185  {
186  size_t i; // The index in the matrix.
187  path_type p; // The overlapping tree path.
188 
189  inline table_entry(
190  const rerooted_tree_type & rerooted_tree,
191  const size_t row,
192  const size_t column)
193  : i (row * rerooted_tree.get_rk() + column)
194  , p (rerooted_tree.get_overlap(row, column))
195  {
196  }
197  };
198 
199  //
200  // The type for the vector of table entries used to populate the values
201  // of the covariance matrix based on the lengths in the tree.
202  //
203  typedef std::vector<table_entry> table_type;
204  typedef basic_newick_node<value_type> node_type;
205 
206  //
207  // Recursively copies the values from the specified Nelder-Mead
208  // container into the nodes of the tree. The length of the parent is not
209  // affected by the call to this method.
210  //
211  // \param parent The parent of the nodes to assign.
212  // \param iterator The container iterator providing lengths.
213  //
214  void _copy_container_to_tree(
215  const node_type & parent,
216  typename container_type::const_iterator & iterator)
217  const
218  {
219  for (auto child : parent.get_children())
220  {
221  child->set_length(*iterator++);
222  _copy_container_to_tree(*child, iterator);
223  }
224  }
225 
226  //
227  // Recursively adds the lengths of the children of the specified node to
228  // the Nelder-Mead container. The length of the parent is not used by
229  // the call to this method.
230  //
231  // \param container The Nelder-Mead container receiving the lengths.
232  // \param parent The parent of the nodes to copy.
233  //
234  void _copy_tree_to_container(
235  container_type & container,
236  const node_type & parent)
237  const
238  {
239  for (auto child : parent.get_children())
240  {
241  container.push_back(child->get_length());
242  _copy_tree_to_container(container, *child);
243  }
244  }
245 
246  const settings_type & _settings;
247  table_type _table;
248  unrooted_tree_ptr_type _unrooted_tree_ptr;
249  rerooted_tree_type _rerooted_tree;
250  };
251 }
252 
253 #endif // JADE_TREE_CONTROLLER_HPP__
jade::basic_controller
A template for a class that performs the Nelder-Mead optimization. This class implements shared featu...
Definition: jade.controller.hpp:24
jade::basic_options< value_type >
jade::basic_settings::get_options
const options_type & get_options() const
Definition: cpax/jade.settings.hpp:174
jade::basic_tree_controller::container_type
simplex_type::container_type container_type
The container type for the simplex.
Definition: jade.tree_controller.hpp:52
jade::basic_newick_node::reroot
pointer_type reroot() const
Creates a new tree based on the tree associated with this node; in the tree returned,...
Definition: jade.newick.hpp:433
jade::basic_matrix::get_length
size_t get_length() const
Definition: jade.matrix.hpp:624
jade::basic_newick_node::erase_length
void erase_length()
Erases the length.
Definition: jade.newick.hpp:91
jade::basic_tree_controller::rerooted_tree_type
basic_rerooted_tree< value_type > rerooted_tree_type
The rerooted tree type.
Definition: jade.tree_controller.hpp:43
jade::basic_tree_controller::options_type
basic_options< value_type > options_type
The options type.
Definition: jade.tree_controller.hpp:31
jade::basic_rerooted_tree::reset
void reset(const node_type &node)
Resets the tree maintained by this instance.
Definition: jade.rerooted_tree.hpp:123
jade::basic_tree_controller::exit_condition_type
simplex_type::exit_condition_type exit_condition_type
The exit condition type for the simplex.
Definition: jade.tree_controller.hpp:55
jade::basic_newick_node::get_id
int get_id() const
Definition: jade.newick.hpp:357
jade::basic_tree_controller::_decode_lower
virtual bool _decode_lower(matrix_type &dst, const container_type &src) override
Decodes the specified Nelder-Mead container and stores the result into the lower triangle,...
Definition: jade.tree_controller.hpp:153
jade::basic_newick_node
A template class representing a node from a Newick tree.
Definition: jade.newick.hpp:19
jade::basic_simplex
A template for a class that implements the Nelder-Mead Simplex Method, which attempts to minimize an ...
Definition: jade.simplex.hpp:21
jade::basic_options::get_tout
const std::string & get_tout() const
Definition: nemeco/jade.options.hpp:157
jade::basic_controller::get_rk
size_t get_rk() const
Definition: jade.controller.hpp:164
jade::basic_tree_controller::basic_tree_controller
basic_tree_controller(const settings_type &settings)
Initializes a new instance of the class based on the specified program settings.
Definition: jade.tree_controller.hpp:61
jade::basic_newick_node::set_length
void set_length(const value_type length)
Assigns the length.
Definition: jade.newick.hpp:456
jade::basic_simplex::container_type
std::vector< value_type > container_type
The container type.
Definition: jade.simplex.hpp:27
jade::basic_tree_path< value_type >
jade::basic_tree_controller::path_type
basic_tree_path< value_type > path_type
The path type.
Definition: jade.tree_controller.hpp:37
jade::basic_controller::container_type
simplex_type::container_type container_type
The container type for the simplex.
Definition: jade.controller.hpp:45
jade::basic_options::is_tout_specified
bool is_tout_specified() const
Definition: nemeco/jade.options.hpp:222
jade::basic_controller::emit_results
virtual void emit_results(const options_type &opts, const simplex_type &simplex, const exit_condition_type &)
Writes results to standard output and files.
Definition: jade.controller.hpp:110
jade::basic_rerooted_tree::get_tree
node_type & get_tree()
Definition: jade.rerooted_tree.hpp:107
jade::basic_options::get_tin
const std::string & get_tin() const
Definition: nemeco/jade.options.hpp:148
jade::basic_settings
A template for a class encapsulating the settings provided to the optimizer.
Definition: cpax/jade.settings.hpp:22
jade::basic_newick_node::find_id
const_pointer_type find_id(const int id) const
Definition: jade.newick.hpp:206
jade::basic_tree_controller::init_parameters
virtual container_type init_parameters() override
Creates and returns the initial set of parameters for the Nelder- Mead algorithm.
Definition: jade.tree_controller.hpp:139
jade::basic_simplex::exit_condition::type
type
The exit condition.
Definition: jade.simplex.hpp:38
jade::basic_tree_controller::matrix_type
basic_matrix< value_type > matrix_type
The matrix type.
Definition: jade.tree_controller.hpp:28
jade::basic_tree_controller
A template for a class that encodes and decodes parameters for the Nelder-Mead algorithm....
Definition: jade.tree_controller.hpp:22
jade::basic_tree_controller::emit_results
virtual void emit_results(const options_type &opts, const simplex_type &simplex, const exit_condition_type &condition) override
Writes results to standard output and files.
Definition: jade.tree_controller.hpp:96
jade::basic_tree_controller::value_type
TValue value_type
The value type.
Definition: jade.tree_controller.hpp:25
jade::basic_newick_node::from_file
static pointer_type from_file(char const *const path)
Definition: jade.newick.hpp:327
jade::basic_tree_controller::simplex_type
basic_simplex< value_type > simplex_type
The simplex type.
Definition: jade.tree_controller.hpp:40
jade::basic_rerooted_tree< value_type >
jade::basic_tree_controller::settings_type
basic_settings< value_type > settings_type
The settings type.
Definition: jade.tree_controller.hpp:34
jade::basic_matrix< value_type >
jade::basic_tree_controller::unrooted_tree_type
basic_newick_node< value_type > unrooted_tree_type
The unrooted tree type.
Definition: jade.tree_controller.hpp:46
jade::basic_tree_controller::unrooted_tree_ptr_type
std::unique_ptr< unrooted_tree_type > unrooted_tree_ptr_type
The pointer to an unrooted tree type.
Definition: jade.tree_controller.hpp:49