A toolkit for working with phylogenetic data.
v0.24.0
tree/function/operators.cpp
Go to the documentation of this file.
1 /*
2  Genesis - A toolkit for working with phylogenetic data.
3  Copyright (C) 2014-2019 Lucas Czech and HITS gGmbH
4 
5  This program is free software: you can redistribute it and/or modify
6  it under the terms of the GNU General Public License as published by
7  the Free Software Foundation, either version 3 of the License, or
8  (at your option) any later version.
9 
10  This program is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  GNU General Public License for more details.
14 
15  You should have received a copy of the GNU General Public License
16  along with this program. If not, see <http://www.gnu.org/licenses/>.
17 
18  Contact:
19  Lucas Czech <lucas.czech@h-its.org>
20  Exelixis Lab, Heidelberg Institute for Theoretical Studies
21  Schloss-Wolfsbrunnenweg 35, D-69118 Heidelberg, Germany
22 */
23 
32 
40 
41 #include <ostream>
42 
43 #ifdef GENESIS_OPENMP
44 # include <omp.h>
45 #endif
46 
47 namespace genesis {
48 namespace tree {
49 
50 // =================================================================================================
51 // Conversion
52 // =================================================================================================
53 
55  Tree const& source,
56  std::function< std::unique_ptr<BaseNodeData>( BaseNodeData const& node_data )> node_data_converter,
57  std::function< std::unique_ptr<BaseEdgeData>( BaseEdgeData const& edge_data )> edge_data_converter
58 ) {
59  // Copy the topology. All data pointers of the new tree are nullptrs.
60  auto res = source.clone_topology();
61 
62  // Convert data where there is data.
63  for( size_t i = 0; i < res.node_count(); ++i ) {
64  if( source.node_at(i).has_data() ) {
65  res.node_at(i).reset_data( node_data_converter( *source.node_at(i).data_ptr() ));
66  }
67  }
68  for( size_t i = 0; i < res.edge_count(); ++i ) {
69  if( source.edge_at(i).has_data() ) {
70  res.edge_at(i).reset_data( edge_data_converter( *source.edge_at(i).data_ptr() ));
71  }
72  }
73 
74  return res;
75 }
76 
77 // =================================================================================================
78 // Equality and Identity
79 // =================================================================================================
80 
81 bool equal(
82  Tree const& lhs,
83  Tree const& rhs,
84  std::function<bool ( TreeNode const&, TreeNode const&) > node_comparator,
85  std::function<bool ( TreeEdge const&, TreeEdge const&) > edge_comparator
86 ) {
87  // Check array sizes.
88  if (lhs.link_count() != rhs.link_count() ||
89  lhs.node_count() != rhs.node_count() ||
90  lhs.edge_count() != rhs.edge_count()
91  ) {
92  return false;
93  }
94 
95  // do a preorder traversal on both trees in parallel
96  auto it_l = preorder(lhs).begin();
97  auto it_r = preorder(rhs).begin();
98  for (
99  ;
100  it_l != preorder(lhs).end() && it_r != preorder(rhs).end();
101  ++it_l, ++it_r
102  ) {
103  if( degree( it_l.node() ) != degree( it_r.node() ) ||
104  !node_comparator( it_l.node(), it_r.node() ) ||
105  !edge_comparator( it_l.edge(), it_r.edge() )
106  ) {
107  return false;
108  }
109  }
110 
111  // check whether we are done with both trees
112  if( it_l != preorder(lhs).end() || it_r != preorder(rhs).end() ) {
113  return false;
114  }
115 
116  return true;
117 }
118 
119 bool equal(
120  std::vector<Tree> const& trees,
121  std::function<bool ( TreeNode const&, TreeNode const&) > node_comparator,
122  std::function<bool ( TreeEdge const&, TreeEdge const&) > edge_comparator
123 ) {
124  // If all pairs of two adjacent trees are equal, all of them are.
125  // Thus, we do not need a complete pairwise comparision.
126  // In order to also accelarate via OpenMP, we need a flag instead of immediately
127  // returning on finding a false. We cannot break in OpenMP, but we can skip (which is fast),
128  // if we already know the result.
129 
130  bool result = true;
131  #pragma omp parallel for
132  for (size_t i = 1; i < trees.size(); i++) {
133  if( ! result ) {
134  continue;
135  }
136 
137  if( ! equal( trees[i-1], trees[i], node_comparator, edge_comparator )) {
138  result = false;
139  }
140  }
141  return result;
142 }
143 
144 /* *
145  * @brief Compares two trees for equality using the respective comparision operators for their nodes
146  * and edges.
147  *
148  * This method is mainly a shortcut for the other equal function, where the comparator functionals
149  * are instanciated using the default comparision operators of the tree's data.
150  */
151 // bool equal( Tree const& lhs, Tree const& rhs)
152 // {
153 // auto node_comparator = [] (
154 // TreeNode const& node_l,
155 // TreeNode const& node_r
156 // ) {
157 // return node_l == node_r;
158 // };
159 //
160 // auto edge_comparator = [] (
161 // TreeEdge const& edge_l,
162 // TreeEdge const& edge_r
163 // ) {
164 // return edge_l == edge_r;
165 // };
166 //
167 // return equal<TreeTypeL, TreeTypeR>(lhs, rhs, node_comparator, edge_comparator);
168 // }
169 
170 bool identical_topology( Tree const& lhs, Tree const& rhs, bool identical_indices )
171 {
172  auto node_comparator = [ &identical_indices ] (
173  TreeNode const& node_l,
174  TreeNode const& node_r
175  ) {
176  if( identical_indices && node_l.index() != node_r.index() ) {
177  return false;
178  }
179  return true;
180  };
181 
182  auto edge_comparator = [ &identical_indices ] (
183  TreeEdge const& edge_l,
184  TreeEdge const& edge_r
185  ) {
186  if( identical_indices && edge_l.index() != edge_r.index() ) {
187  return false;
188  }
189  return true;
190  };
191 
192  return equal( lhs, rhs, node_comparator, edge_comparator );
193 }
194 
195 bool identical_topology( std::vector<Tree> const& trees, bool identical_indices )
196 {
197  // If all pairs of two adjacent trees have same the topology, all of them have.
198  // Thus, we do not need a complete pairwise comparision.
199  // In order to also accelarate via OpenMP, we need a flag instead of immediately
200  // returning on finding a false. We cannot break in OpenMP, but we can skip (which is fast),
201  // if we already know the result.
202 
203  bool result = true;
204  #pragma omp parallel for
205  for (size_t i = 1; i < trees.size(); i++) {
206  if( ! result ) {
207  continue;
208  }
209 
210  if( ! identical_topology( trees[i-1], trees[i], identical_indices )) {
211  result = false;
212  }
213  }
214  return result;
215 }
216 
217 // =================================================================================================
218 // Element Ownership Checks
219 // =================================================================================================
220 
221 bool belongs_to( Tree const& tree, TreeNode const& node )
222 {
223  return node.index() < tree.node_count() && &tree.node_at( node.index() ) == &node;
224 }
225 
226 bool belongs_to( TreeNode const& node, Tree const& tree )
227 {
228  return node.index() < tree.node_count() && &tree.node_at( node.index() ) == &node;
229 }
230 
231 bool belongs_to( Tree const& tree, TreeEdge const& edge )
232 {
233  return edge.index() < tree.edge_count() && &tree.edge_at( edge.index() ) == &edge;
234 }
235 
236 bool belongs_to( TreeEdge const& edge, Tree const& tree )
237 {
238  return edge.index() < tree.edge_count() && &tree.edge_at( edge.index() ) == &edge;
239 }
240 
241 bool belongs_to( Tree const& tree, TreeLink const& link )
242 {
243  return link.index() < tree.link_count() && &tree.link_at( link.index() ) == &link;
244 }
245 
246 bool belongs_to( TreeLink const& link, Tree const& tree )
247 {
248  return link.index() < tree.link_count() && &tree.link_at( link.index() ) == &link;
249 }
250 
251 bool belongs_to( Tree const& tree, Subtree const& subt )
252 {
253  return belongs_to( subt.link(), tree );
254 }
255 
256 bool belongs_to( Subtree const& subt, Tree const& tree )
257 {
258  return belongs_to( subt.link(), tree );
259 }
260 
262 {
263  // No need to check whether the two nodes belong to the same tree.
264  // If they don't, this loop will simply exit without success, so that a nullptr is returend.
265  for( auto it : node_links( lhs ) ) {
266  if( &it.link().outer().node() == &rhs ) {
267  return &it.link().edge();
268  }
269  }
270  return nullptr;
271 }
272 
273 TreeEdge const* edge_between( TreeNode const& lhs, TreeNode const& rhs )
274 {
275  // No need to check whether the two nodes belong to the same tree.
276  // If they don't, this loop will simply exit without success, so that a nullptr is returend.
277  for( auto it : node_links( lhs ) ) {
278  if( &it.link().outer().node() == &rhs ) {
279  return &it.link().edge();
280  }
281  }
282  return nullptr;
283 }
284 
285 // =================================================================================================
286 // Output Printing
287 // =================================================================================================
288 
289 std::string print_info( Tree const& tree )
290 {
291  return "<genesis::tree::Tree"
292  " node_count=" + std::to_string( tree.node_count() ) +
293  " edge_count=" + std::to_string( tree.edge_count() ) +
294  " link_count=" + std::to_string( tree.link_count() ) +
295  ">";
296 }
297 
298 std::string print_info( TreeEdge const& edge )
299 {
300  return "<genesis::tree::TreeEdge"
301  " index=" + std::to_string( edge.index() ) +
302  " has_data=" + ( edge.has_data() ? "true" : "false" ) +
303  ">";
304 }
305 
306 std::string print_info( TreeLink const& link )
307 {
308  return "<genesis::tree::TreeLink"
309  " index=" + std::to_string( link.index() ) +
310  // " has_data=" + ( edge.has_data() ? "true" : "false" ) +
311  ">";
312 }
313 
314 std::string print_info( TreeNode const& node )
315 {
316  return "<genesis::tree::TreeNode"
317  " index=" + std::to_string( node.index() ) +
318  " has_data=" + ( node.has_data() ? "true" : "false" ) +
319  ">";
320 }
321 
322 std::string print_gist( Tree const& tree, long items )
323 {
324  auto pc = PrinterCompact();
325  pc.limit( items );
326  return pc.print( tree );
327 }
328 
329 std::ostream& operator << ( std::ostream& out, Tree const& tree )
330 {
331  if( utils::Options::get().print_object_infos() ) {
332  out << print_info( tree );
333  }
334  out << print_gist( tree, utils::Options::get().print_object_gists() );
335  return out;
336 }
337 
338 std::ostream& operator << ( std::ostream& out, TreeEdge const& edge )
339 {
340  if( utils::Options::get().print_object_infos() ) {
341  out << print_info( edge );
342  }
343  return out;
344 }
345 
346 std::ostream& operator << ( std::ostream& out, TreeLink const& link )
347 {
348  if( utils::Options::get().print_object_infos() ) {
349  out << print_info( link );
350  }
351  return out;
352 }
353 
354 std::ostream& operator << ( std::ostream& out, TreeNode const& node )
355 {
356  if( utils::Options::get().print_object_infos() ) {
357  out << print_info( node );
358  }
359  return out;
360 }
361 
362 // =================================================================================================
363 // Validate
364 // =================================================================================================
365 
366 bool validate_topology( Tree const& tree )
367 {
368  // -----------------------------------------------------
369  // Empty Tree
370  // -----------------------------------------------------
371 
372  // check that the member arrays are valid: if at least one of them is empty, the tree is not
373  // fully initialized, so either it is a new tree without any data (all arrays empty, valid),
374  // or some are empty, but others not (not valid).
375  if (tree.links_.empty() || tree.nodes_.empty() || tree.edges_.empty()) {
376  bool empty = tree.links_.empty() && tree.nodes_.empty() && tree.edges_.empty();
377  if( !empty ) {
378  LOG_INFO << "Tree is not empty, but one of its data members is.";
379  }
380  return empty;
381  }
382 
383  // -----------------------------------------------------
384  // Links
385  // -----------------------------------------------------
386 
387  // Check Links.
388  std::vector<size_t> links_to_edges(tree.edges_.size(), 0);
389  std::vector<size_t> links_to_nodes(tree.nodes_.size(), 0);
390  for (size_t i = 0; i < tree.links_.size(); ++i) {
391  // Check indices.
392  if( i != tree.link_at(i).index() ) {
393  LOG_INFO << "Link at index " << i << " has wrong index ("
394  << tree.link_at(i).index() << ").";
395  return false;
396  }
397 
398  // Check next cycle and node.
399  auto nl = tree.links_[i].get();
400  do {
401  if( &nl->node() != &tree.links_[i]->node() ) {
402  LOG_INFO << "Link at index " << nl->index() << " points to wrong node.";
403  return false;
404  }
405  nl = &nl->next();
406  } while(nl != tree.links_[i].get());
407  ++links_to_nodes[tree.links_[i]->node().index()];
408 
409  // Check outer cycle.
410  if( &tree.links_[i]->outer().outer() != tree.links_[i].get() ) {
411  LOG_INFO << "Link at index " << i << " has wrong outer link.";
412  return false;
413  }
414 
415  // Check edge.
416  auto edge = &tree.links_[i]->edge();
417  if(
418  &edge->primary_link() != tree.links_[i].get() &&
419  &edge->secondary_link() != tree.links_[i].get()
420  ) {
421  LOG_INFO << "Link at index " << i << " has wrong edge pointer.";
422  return false;
423  }
424  ++links_to_edges[tree.links_[i]->edge().index()];
425  }
426 
427  // Check if all edges have been hit twice.
428  for (size_t i = 0; i < tree.edges_.size(); ++i) {
429  if (links_to_edges[i] != 2) {
430  LOG_INFO << "Edge at index " << i << " is not visited twice but " << links_to_edges[i]
431  << " times when traversing the links.";
432  return false;
433  }
434  }
435 
436  // Check if all nodes have been hit as many times as their degree is.
437  for (size_t i = 0; i < tree.nodes_.size(); ++i) {
438  if (links_to_nodes[i] != degree( *tree.nodes_[i] ) ) {
439  LOG_INFO << "Node at index " << i << " is not visited its degree ("
440  << degree( *tree.nodes_[i] )
441  << ") times, but " << links_to_nodes[i] << " times when "
442  << "traversing the links.";
443  return false;
444  }
445  }
446 
447  // -----------------------------------------------------
448  // Nodes
449  // -----------------------------------------------------
450 
451  // Check Nodes.
452  for (size_t i = 0; i < tree.nodes_.size(); ++i) {
453  // Check indices.
454  if( i != tree.node_at(i).index() ) {
455  LOG_INFO << "Node at index " << i << " has wrong index ("
456  << tree.node_at(i).index() << ").";
457  return false;
458  }
459 
460  // Check link.
461  if( &tree.nodes_[i]->link().node() != tree.nodes_[i].get() ) {
462  LOG_INFO << "Node at index " << i << " has wrong link.";
463  return false;
464  }
465 
466  // If a node claims to be the root, it better be the root.
467  if( is_root( tree.node_at(i) ) && i != tree.root_node().index() ) {
468  LOG_INFO << "Node at index " << i << " has is_root(), but it is not tree.root_node().";
469  return false;
470  }
471 
472  // Except for the root, all nodes must have a primary link that is the secondary link
473  // of its edge.
474  if( ! is_root( tree.node_at(i) ) &&
475  &tree.node_at(i).primary_link() != &tree.node_at(i).primary_link().edge().secondary_link()
476  ) {
477  LOG_INFO << "Node at " << i << " (not the root node) has a primary link which is not "
478  << "the secondary link of its edge.";
479  return false;
480  }
481 
482  // All (primary) links must point towards the root.
483  size_t root_c = 0;
484  auto root_l = &( tree.node_at(i).primary_link() );
485  while( root_l != &( tree.root_node().link() )) {
486  root_l = &( root_l->outer().node().primary_link() );
487  ++root_c;
488 
489  // We need to avoid infinite loops in case of wrong trees, so that this function
490  // correctly termines. We cannot need more hops than nodes in the tree!
491  if( root_c > tree.node_count() ) {
492  LOG_INFO << "Node at " << i << " and the nodes towards the root contain "
493  << "a primary link which is not pointing towards the root.";
494  return false;
495  }
496  }
497  }
498 
499  // -----------------------------------------------------
500  // Edges
501  // -----------------------------------------------------
502 
503  // Check Edges.
504  for (size_t i = 0; i < tree.edges_.size(); ++i) {
505  // Check indices.
506  if( i != tree.edge_at(i).index() ) {
507  LOG_INFO << "Edge at index " << i << " has wrong index ("
508  << tree.edge_at(i).index() << ").";
509  return false;
510  }
511 
512  // Check links.
513  if( &tree.edges_[i]->primary_link().edge() != tree.edges_[i].get() ) {
514  LOG_INFO << "Edge at index " << i << " has wrong primary link.";
515  return false;
516  }
517  if( &tree.edges_[i]->secondary_link().edge() != tree.edges_[i].get() ) {
518  LOG_INFO << "Edge at index " << i << " has wrong secondary link.";
519  return false;
520  }
521 
522  // Check outer links.
523  if( &tree.edges_[i]->primary_link().outer() != &tree.edges_[i]->secondary_link() ) {
524  LOG_INFO << "Edge at index " << i << " has a primary link that does not "
525  << "connect to its secondary link.";
526  return false;
527  }
528  if( &tree.edges_[i]->secondary_link().outer() != &tree.edges_[i]->primary_link() ) {
529  LOG_INFO << "Edge at index " << i << " has a secondary link that does not "
530  << "connect to its primary link.";
531  return false;
532  }
533 
534  // Check primary node, except for root.
535  if( ! is_root( tree.edge_at(i).primary_node() ) &&
536  &tree.edge_at(i).primary_node().primary_link() == &tree.edge_at(i).primary_link()
537  ) {
538  LOG_INFO << "Edge at " << i << " has a primary node that does not "
539  << "point towards the root.";
540  return false;
541  }
542 
543  // Check secondary node.
544  if( &tree.edge_at(i).secondary_node().primary_link() != &tree.edge_at(i).secondary_link() ) {
545  LOG_INFO << "Edge at " << i << " has a secondary node that does not "
546  << "point towards the root.";
547  return false;
548  }
549 
550  // All primary links must point towards the root.
551  size_t root_c = 0;
552  auto root_l = &( tree.edge_at(i).primary_link() );
553  while( root_l != &( tree.root_node().link() )) {
554  root_l = &( root_l->node().primary_link().edge().primary_link() );
555  ++root_c;
556 
557  // We need to avoid infinite loops in case of wrong trees, so that this function
558  // correctly termines. We cannot need more hops than nodes in the tree!
559  if( root_c > tree.node_count() ) {
560  LOG_INFO << "Edge at " << i << " and the nodes towards the root contain "
561  << "a primary link which is not pointing towards the root.";
562  return false;
563  }
564  }
565  }
566 
567  // -----------------------------------------------------
568  // Eulertour
569  // -----------------------------------------------------
570 
571  // If we are here, all three arrays (links, nodes, edges) contain data, so we can start a full
572  // traversal along all links.
573 
574  // Count, how many times the elements are hit while traversing.
575  std::vector<size_t> it_links(tree.links_.size(), 0);
576  std::vector<size_t> it_edges(tree.edges_.size(), 0);
577  std::vector<size_t> it_nodes(tree.nodes_.size(), 0);
578 
579  // Do the traversal. We do not use the iterator here, to keep it simple when testing.
580  // (We want to validate the tree here, not the iterator.)
581  auto link = tree.links_.front().get();
582  do {
583  ++it_links[ link->index() ];
584  ++it_edges[ link->edge().index() ];
585  ++it_nodes[ link->node().index() ];
586  link = &link->next().outer();
587 
588  // Check if we have a loop. Baaad.
589  if( it_links[ link->index() ] > 1 ) {
590  LOG_INFO << "Loop or other kind of wrong link chain in Tree.";
591  return false;
592  }
593  } while (link != tree.links_.front().get());
594 
595  // Check if all links have been hit once.
596  for (size_t i = 0; i < tree.links_.size(); i++) {
597  if (it_links[i] != 1) {
598  LOG_INFO << "Link at index " << i << " is not visited 1 but " << it_links[i]
599  << " times when iterating the tree.";
600  return false;
601  }
602  }
603 
604  // Check if all edges have been hit twice.
605  for (size_t i = 0; i < tree.edges_.size(); ++i) {
606  if (it_edges[i] != 2) {
607  LOG_INFO << "Edge at index " << i << " is not visited 2 but " << it_edges[i]
608  << " times when iterating the tree.";
609  return false;
610  }
611  }
612 
613  // Check if all nodes have been hit as many times as their degree is.
614  for (size_t i = 0; i < tree.nodes_.size(); ++i) {
615  if (it_nodes[i] != degree( *tree.nodes_[i] ) ) {
616  LOG_INFO << "Node at index " << i << " is not visited "
617  << degree( *tree.nodes_[i] )
618  << " times, but " << it_nodes[i] << " times when iterating the "
619  << "tree.";
620  return false;
621  }
622  }
623 
624  // -----------------------------------------------------
625  // Root
626  // -----------------------------------------------------
627 
628  // All edges of the root node need to have this node as their primary node.
629  auto rl = &( tree.root_link().next());
630  while( rl != &( tree.root_link()) ) {
631  if( &( rl->edge().primary_link() ) != rl ) {
632  LOG_INFO << "Root node of the tree is not root in the topology.";
633  return false;
634  }
635  rl = &( rl->next() );
636  }
637 
638  // Check root link and node.
639  if( &tree.root_link() != &tree.root_link().node().primary_link() ) {
640  LOG_INFO << "Tree root link is not the primary link of its node.";
641  return false;
642  }
643 
644  // Further check the root.
645  if( ! is_root( tree.root_node() ) ) {
646  LOG_INFO << "Root node is not true in is_root().";
647  return false;
648  }
649 
650  return true;
651 }
652 
653 } // namespace tree
654 } // namespace genesis
std::string print_info(Tree const &tree)
utils::Range< IteratorNodeLinks< true > > node_links(ElementType const &element)
Definition: node_links.hpp:186
TreeLink & secondary_link()
Return the TreeLink of this TreeEdge that points away from the root.
Definition: edge.hpp:130
bool has_data() const
Return true if the TreeEdge has a data object assigned to it.
Definition: edge.hpp:182
bool is_root(TreeLink const &link)
Return whether the link belongs to the root node of its Tree.
Base class for storing data on Nodes of a Tree.
Definition: node_data.hpp:66
Tree operator functions.
Print a Tree in a compact form, i.e., each node and edge on one line.
Definition: compact.hpp:82
TreeLink & primary_link()
Return the TreeLink that points towards the root.
Definition: node.hpp:110
size_t edge_count() const
Return the number of TreeEdges of the Tree.
Definition: tree/tree.hpp:272
size_t index() const
Return the index of this Edge.
Definition: edge.hpp:106
TreeNode & secondary_node()
Return the TreeNode of this TreeEdge that points away from the root.
Definition: edge.hpp:162
Container namespace for all symbols of genesis in order to keep them separate when used as a library...
Reference to a subtree of a Tree.
Definition: subtree.hpp:69
TreeEdge * edge_between(TreeNode &lhs, TreeNode &rhs)
Return the TreeEdge between two TreeNode&s, if they are neighbours, or nullptr otherwise.
Tree clone_topology() const
Return a Tree with the same topology, but without any data.
Definition: tree/tree.cpp:109
TreeNode & primary_node()
Return the TreeNode of this TreeEdge that points towards the root.
Definition: edge.hpp:146
BaseEdgeData * data_ptr()
Return a pointer to the data.
Definition: edge.hpp:246
Class for representing phylogenetic trees.
Definition: tree/tree.hpp:97
bool has_data() const
Return true if the TreeNode has a data object assigned to it.
Definition: node.hpp:168
size_t link_count() const
Return the number of TreeLinks of the Tree.
Definition: tree/tree.hpp:256
TreeLink & link()
Return the TreeLink that points towards the root.
Definition: node.hpp:129
TreeNode & node_at(size_t index)
Return the TreeNode at a certain index.
Definition: tree/tree.hpp:220
TreeLink & root_link()
Return the TreeLink at the current root of the Tree.
Definition: tree/tree.hpp:284
TreeEdge & edge_at(size_t index)
Return the TreeEdge at a certain index.
Definition: tree/tree.hpp:238
bool belongs_to(Tree const &tree, TreeNode const &node)
Return whether the TreeNode belongs to the Tree, i.e., whether it is owned by the Tree...
TreeLink const & link() const
Get the TreeLink that separates the subtree from the rest of the tree.
Definition: subtree.hpp:125
Provides easy and fast logging functionality.
size_t node_count() const
Return the number of TreeNodes of the Tree.
Definition: tree/tree.hpp:264
bool identical_topology(Tree const &lhs, Tree const &rhs, bool identical_indices)
Return whether both trees have an identical topology.
bool validate_topology(Tree const &tree)
Validate that all internal pointers of the Tree elements (TreeLinks, TreeNodes, TreeEdges) to each ot...
utils::Range< IteratorPreorder< true > > preorder(ElementType const &element)
TreeLink & link_at(size_t index)
Return the TreeLink at a certain index.
Definition: tree/tree.hpp:202
TreeNode & root_node()
Return the TreeNode at the current root of the Tree.
Definition: tree/tree.hpp:300
std::shared_ptr< BaseOutputTarget > to_string(std::string &target_string)
Obtain an output target for writing to a string.
size_t index() const
Return the index of this Node.
Definition: node.hpp:102
TreeLink & primary_link()
Return the TreeLink of this TreeEdge that points towards the root.
Definition: edge.hpp:114
TreeNode & reset_data(std::unique_ptr< BaseNodeData > data)
Reset the data pointer of this TreeNode.
Definition: node.hpp:290
Base class for storing data on Edges of a Tree.
Definition: edge_data.hpp:66
size_t degree(TreeLink const &link)
Return the degree of the node for a given TreeLink, i.e. how many neighbouring nodes it has...
std::ostream & operator<<(std::ostream &out, Tree const &tree)
static Options & get()
Returns a single instance of this class.
Definition: options.hpp:60
std::string print_gist(Tree const &tree, long items)
bool equal(Tree const &lhs, Tree const &rhs, std::function< bool(TreeNode const &, TreeNode const &) > node_comparator, std::function< bool(TreeEdge const &, TreeEdge const &) > edge_comparator)
Compare two trees for equality given binary comparator functionals for their nodes and edges...
BaseNodeData * data_ptr()
Return a pointer to the data.
Definition: node.hpp:232
Tree convert(Tree const &source, std::function< std::unique_ptr< BaseNodeData >(BaseNodeData const &node_data)> node_data_converter, std::function< std::unique_ptr< BaseEdgeData >(BaseEdgeData const &edge_data)> edge_data_converter)
Create a tree with the same topology as the source tree, while converting its data.
#define LOG_INFO
Log an info message. See genesis::utils::LoggingLevel.
Definition: logging.hpp:99