A library for working with phylogenetic and population genetic data.
v0.27.0
compact.cpp
Go to the documentation of this file.
1 /*
2  Genesis - A toolkit for working with phylogenetic data.
3  Copyright (C) 2014-2020 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 
36 #include "genesis/tree/tree.hpp"
38 
39 #include <cassert>
40 #include <sstream>
41 #include <vector>
42 
43 namespace genesis {
44 namespace tree {
45 
46 // =================================================================================================
47 // Print Compact
48 // =================================================================================================
49 
51  std::ostream& out,
52  Tree const& tree,
53  std::function<std::string (
54  TreeNode const& node,
55  TreeEdge const& edge
56  )> const print_line
57 ) {
58  // Edge case: print nothing
59  if( limit_ == 0 ) {
60  return;
61  }
62 
63  // Stores a count of how many child nodes each node has left for viewing.
64  auto ranks = std::vector<size_t>( tree.node_count(), 0 );
65 
66  // Store the current stack of parents while traversing.
67  auto parents = std::vector<size_t>();
68 
69  // How many lines have been printed yet.
70  // If this reaches the limit_, we print one for line for the ellipsis, then stop.
71  long count = 0;
72 
73  for( auto it : preorder(tree) ) {
74  if( limit_ > 0 && count > limit_ ) {
75  break;
76  }
77 
78  // Index of current and its parent node.
79  size_t cur_idx = it.node().index();
80  size_t par_idx = it.link().outer().node().index();
81 
82  // Set parent stack correctly (including current node), and store current rank.
83  while (!parents.empty() && parents.back() != par_idx) {
84  parents.pop_back();
85  }
86  parents.push_back(cur_idx);
87  ranks[cur_idx] = degree( it.node() ) - 1;
88 
89  // The root node is special: We have to account for one more child, as it does not have a
90  // parent. Also, we do not draw any lines or indention for the root.
91  if (it.is_first_iteration()) {
92  ++ranks[cur_idx];
93  out << print_line( it.node(), it.edge() ) << "\n";
94  ++count;
95  continue;
96  }
97 
98  // This point in code is reached for all nodes but the root. Thus, we already have at least
99  // the root and the current node added to the parents stack. Also, the second but last
100  // element will be the parent of the current node, and the last one the node itself.
101  assert( parents.size() >= 2 );
102  assert( parents[ parents.size() - 2 ] == par_idx );
103  assert( parents[ parents.size() - 1 ] == cur_idx );
104 
105  // Draw indention lines for all non-immediate parents of the current node. If their rank
106  // is zero, there will no other children follow, so do not draw a line then.
107  for (size_t i = 0; i < parents.size() - 2; ++i) {
108  if (ranks[parents[i]] > 0) {
109  if( limit_ > 0 && count == limit_ ) {
110  out << "¦ ";
111  } else {
112  out << "│ ";
113  }
114  } else {
115  out << " ";
116  }
117  }
118 
119  // We are about to draw a child of the parent. Prior to drawing, we need to reduce the
120  // parents rank counter. If it then is zero, the current node is the last child of its
121  // parent (which is drawn differently).
122  // Also assert that it is not zero already, because this would mean that we are currently
123  // processing more children of the parent than its rank indicated.
124  assert(ranks[par_idx] > 0);
125  --ranks[par_idx];
126 
127  if( limit_ > 0 && count == limit_ ) {
128 
129  // If this is the "extra" line to be printed after the main part,
130  // use a broken bar to indicate ellipsis.
131  out << "¦ ";
132  } else {
133 
134  // Draw the lines down from the immediate parent of the current node.
135  if (ranks[par_idx] > 0) {
136  out << "├── ";
137  } else {
138  out << "└── ";
139  }
140 
141  // Print the actual information about the current node.
142  out << print_line( it.node(), it.edge() ) << "\n";
143  }
144 
145  ++count;
146  }
147 }
148 
150  Tree const& tree,
151  std::function<std::string (
152  TreeNode const& node,
153  TreeEdge const& edge
154  )> const print_line
155 ) {
156  std::ostringstream res;
157  print( res, tree, print_line );
158  return res.str();
159 }
160 
161 std::string PrinterCompact::print( Tree const& tree )
162 {
163  auto print_line = [] ( TreeNode const& node, TreeEdge const& edge )
164  {
165  std::string result;
166  if( edge.has_data() ) {
167  result += utils::to_string_nice( edge.data<CommonEdgeData>().branch_length );
168  }
169  if( edge.has_data() && node.has_data() && ! node.data<CommonNodeData>().name.empty() ) {
170  result += " ";
171  }
172  if( node.has_data() ) {
173  result += node.data<CommonNodeData>().name;
174  }
175  return result;
176  };
177  return print(tree, print_line);
178 }
179 
180 } // namespace tree
181 } // namespace genesis
genesis::tree::Tree::node_count
size_t node_count() const
Return the number of TreeNodes of the Tree.
Definition: tree/tree.hpp:264
tree.hpp
Header of Tree class.
functions.hpp
genesis::tree::preorder
utils::Range< IteratorPreorder< true > > preorder(ElementType const &element)
Definition: tree/iterator/preorder.hpp:264
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
string.hpp
Provides some commonly used string utility functions.
genesis::tree::Tree
Class for representing phylogenetic trees.
Definition: tree/tree.hpp:97
compact.hpp
genesis::tree::TreeNode::has_data
bool has_data() const
Return true if the TreeNode has a data object assigned to it.
Definition: tree/tree/node.hpp:168
genesis::tree::CommonEdgeData::branch_length
double branch_length
Branch length of the edge.
Definition: tree/common_tree/tree.hpp:193
genesis::tree::CommonNodeData::name
std::string name
Name of the node.
Definition: tree/common_tree/tree.hpp:127
genesis::tree::TreeEdge
Definition: edge.hpp:60
genesis::tree::TreeNode
Definition: tree/tree/node.hpp:58
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
tree.hpp
genesis::utils::to_string_nice
std::string to_string_nice(T const &v)
Return a string representation of a given value.
Definition: string.hpp:412
genesis::tree::CommonEdgeData
Common class containing the commonly needed data for tree edges.
Definition: tree/common_tree/tree.hpp:144
genesis::tree::CommonNodeData
Common class containing the commonly needed data for tree nodes.
Definition: tree/common_tree/tree.hpp:79
genesis::tree::TreeNode::data
NodeDataType & data()
Definition: tree/tree/node.hpp:203
genesis::tree::PrinterCompact::print
void print(std::ostream &out, Tree const &tree, std::function< std::string(TreeNode const &node, TreeEdge const &edge)> const print_line)
Print a compact representation of a Tree to an output stream, using a given function for output of th...
Definition: compact.cpp:50
preorder.hpp