A toolkit for working with phylogenetic data.
v0.19.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
layout_base.cpp
Go to the documentation of this file.
1 /*
2  Genesis - A toolkit for working with phylogenetic data.
3  Copyright (C) 2014-2018 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 
42 
43 #include <cassert>
44 
45 namespace genesis {
46 namespace tree {
47 
48 // =================================================================================================
49 // Tree
50 // =================================================================================================
51 
52 void LayoutBase::tree( Tree const& orig_tree, bool ladderize_tree )
53 {
54  // We first copy the tree, then ladderize it before init, so that all positions
55  // are initialized correlty. This is possible because ladderize() only changes link pointers
56  // of the tree, but not and indices or node array positions.
57  tree_ = orig_tree.clone_topology();
58  if( ladderize_tree ) {
59  ladderize( tree_ );
60  }
61  init_tree_( orig_tree );
62 }
63 
65 {
66  return tree_;
67 }
68 
69 Tree const& LayoutBase::tree() const
70 {
71  return tree_;
72 }
73 
75 {
77  set_edge_distance_strokes( stroke );
78 }
79 
80 void LayoutBase::set_edge_strokes( std::vector< utils::SvgStroke > const& strokes )
81 {
82  set_edge_spreading_strokes( strokes );
83  set_edge_distance_strokes( strokes );
84 }
85 
87 {
88  for( size_t i = 0; i < tree_.edge_count(); ++i ) {
89  tree_.edge_at(i).data<LayoutEdgeData>().spreading_stroke = stroke;
90  }
91 }
92 
93 void LayoutBase::set_edge_spreading_strokes( std::vector< utils::SvgStroke > const& strokes )
94 {
95  // Empty: Reset to default.
96  if( strokes.empty() ) {
98  return;
99  }
100 
101  // Non-empty case.
102  if( strokes.size() != tree_.edge_count() ) {
103  throw std::runtime_error( "Edge stroke vector has wrong size." );
104  }
105  for( size_t i = 0; i < tree_.edge_count(); ++i ) {
106  tree_.edge_at(i).data<LayoutEdgeData>().spreading_stroke = strokes[ i ];
107  }
108 }
109 
111 {
112  for( size_t i = 0; i < tree_.edge_count(); ++i ) {
113  tree_.edge_at(i).data<LayoutEdgeData>().distance_stroke = stroke;
114  }
115 }
116 
117 void LayoutBase::set_edge_distance_strokes( std::vector< utils::SvgStroke > const& strokes )
118 {
119  // Empty: Reset to default.
120  if( strokes.empty() ) {
122  return;
123  }
124 
125  // Non-empty case.
126  if( strokes.size() != tree_.edge_count() ) {
127  throw std::runtime_error( "Edge stroke vector has wrong size." );
128  }
129  for( size_t i = 0; i < tree_.edge_count(); ++i ) {
130  tree_.edge_at(i).data<LayoutEdgeData>().distance_stroke = strokes[ i ];
131  }
132 }
133 
135 {
136  for( size_t i = 0; i < tree_.edge_count(); ++i ) {
137  tree_.edge_at(i).data<LayoutEdgeData>().shape = shape;
138  }
139 }
140 
141 void LayoutBase::set_edge_shapes( std::vector< utils::SvgGroup> const& shapes )
142 {
143  // Empty: Reset to default.
144  if( shapes.empty() ) {
146  return;
147  }
148 
149  // Non-empty case.
150  if( shapes.size() != tree_.edge_count() ) {
151  throw std::runtime_error( "Edge shape vector has wrong size." );
152  }
153  for( size_t i = 0; i < tree_.edge_count(); ++i ) {
154  tree_.edge_at(i).data<LayoutEdgeData>().shape = shapes[ i ];
155  }
156 }
157 
159 {
160  for( size_t i = 0; i < tree_.node_count(); ++i ) {
161  tree_.node_at(i).data<LayoutNodeData>().shape = shape;
162  }
163 }
164 
165 void LayoutBase::set_node_shapes( std::vector< utils::SvgGroup> const& shapes )
166 {
167  // Empty: Reset to default.
168  if( shapes.empty() ) {
170  return;
171  }
172 
173  // Non-empty case.
174  if( shapes.size() != tree_.node_count() ) {
175  throw std::runtime_error( "Node shape vector has wrong size." );
176  }
177  for( size_t i = 0; i < tree_.node_count(); ++i ) {
178  tree_.node_at(i).data<LayoutNodeData>().shape = shapes[ i ];
179  }
180 }
181 
182 // =================================================================================================
183 // Init
184 // =================================================================================================
185 
186 void LayoutBase::init_tree_( Tree const& orig_tree )
187 {
188  // Init nodes.
189  for( size_t i = 0; i < tree().node_count(); ++i ) {
190  auto& node = tree().node_at(i);
191  auto const& orig_node = orig_tree.node_at(i);
192 
193  // Safety: correct indices.
194  assert( node.index() == i && orig_node.index() == i );
195 
196  // Set the tree node data.
198 
199  // If the original tree has node names, use them.
200  auto orig_node_data_ptr = orig_node.data_cast<DefaultNodeData>();
201  if( orig_node_data_ptr ) {
202  node.data<DefaultNodeData>().name = orig_node_data_ptr->name;
203  }
204  }
205 
206  // Init edges.
207  for( size_t i = 0; i < tree().edge_count(); ++i ) {
208  auto& edge = tree().edge_at(i);
209  auto const& orig_edge = orig_tree.edge_at(i);
210 
211  // Safety: correct indices.
212  assert( edge.index() == i && orig_edge.index() == i );
213 
214  // Set the tree edge data.
216 
217  // If the original tree has edge branch lengths, use them.
218  auto orig_edge_data_ptr = orig_edge.data_cast<DefaultEdgeData>();
219  if( orig_edge_data_ptr ) {
220  edge.data<DefaultEdgeData>().branch_length = orig_edge_data_ptr->branch_length;
221  }
222  }
223 
224  // Layout
225  init_layout_();
226 }
227 
228 void LayoutBase::init_layout_()
229 {
230  if( tree().empty() ) {
231  return;
232  }
233 
234  // Set distances of nodes.
235  if( type() == LayoutType::kCladogram ) {
236  set_node_distances_cladogram_();
237  } else if( type() == LayoutType::kPhylogram ) {
238  set_node_distances_phylogram_();
239  } else {
240  assert( false );
241  }
242 
243  // Set spreadings of nodes.
244  set_node_spreadings_();
245 }
246 
247 void LayoutBase::set_node_spreadings_()
248 {
249  auto const num_leaves = static_cast<double>( leaf_node_count( tree() ));
250 
251  // Set node parents and spreading of leaves.
252  size_t leaf_count = 0;
253  size_t parent = 0;
254  for( auto it : eulertour( tree() )) {
255  auto& node_data = tree().node_at( it.node().index() ).data<LayoutNodeData>();
256 
257  if( node_data.parent_index == -1 ) {
258  node_data.parent_index = parent;
259  }
260  if( it.node().is_leaf() ) {
261  node_data.spreading = static_cast<double>(leaf_count) / num_leaves;
262  leaf_count++;
263  }
264 
265  parent = it.node().index();
266  }
267  assert( leaf_count == static_cast<size_t>( num_leaves ));
268 
269  // Min and max spreading of the children of each node.
270  // Init to -1.0 so that we can check which ones are done already.
271  auto chrn_min_s = std::vector<double>( tree().node_count(), -1.0 );
272  auto chrn_max_s = std::vector<double>( tree().node_count(), -1.0 );
273 
274  // Set remaining spreading of inner nodes to mid-points of their children.
275  for( auto it : postorder( tree() )) {
276  auto const node_index = it.node().index();
277  auto& node_data = tree().node_at( node_index ).data<LayoutNodeData>();
278  auto const prnt_index = node_data.parent_index;
279 
280  if( node_data.spreading < 0.0 ) {
281  // We already have done those nodes because of the postorder.
282  assert( chrn_min_s[ node_index ] > -1.0 );
283  assert( chrn_max_s[ node_index ] > -1.0 );
284 
285  auto min_max_diff = chrn_max_s[ node_index ] - chrn_min_s[ node_index ];
286  node_data.spreading = chrn_min_s[ node_index ] + min_max_diff / 2.0;
287  }
288 
289  if( chrn_min_s[ prnt_index ] < 0.0 || chrn_min_s[ prnt_index ] > node_data.spreading ) {
290  chrn_min_s[ prnt_index ] = node_data.spreading;
291  }
292  if( chrn_max_s[ prnt_index ] < 0.0 || chrn_max_s[ prnt_index ] < node_data.spreading ) {
293  chrn_max_s[ prnt_index ] = node_data.spreading;
294  }
295  }
296 }
297 
298 void LayoutBase::set_node_distances_phylogram_()
299 {
300  // Get distnace from root to every node.
301  auto node_dists = node_branch_length_distance_vector( tree() );
302 
303  // We already check the size in init_layout_()
304  assert( ! node_dists.empty() );
305  auto const max_d = *std::max_element( node_dists.begin(), node_dists.end() );
306 
307  for( size_t i = 0; i < node_dists.size(); ++i ) {
308  tree().node_at(i).data<LayoutNodeData>().distance = node_dists[i] / max_d;
309  }
310 }
311 
312 void LayoutBase::set_node_distances_cladogram_()
313 {
314  // Set root distance to 0.
315  tree().root_node().data<LayoutNodeData>().distance = 0.0;
316 
317  // Get the heights of all subtrees starting from the root.
318  auto const heights = subtree_max_path_heights( tree() );
319 
320  // Get the height of the tree, i.e. longest path from root to any leaf.
321  auto const root_height = static_cast<double>( heights[ tree().root_node().index() ] );
322 
323  for( auto it : preorder( tree() )) {
324  // The subtree height calculation does not work for the root, so skip it.
325  // Also, we already set the leaf.
326  if( it.is_first_iteration() ) {
327  continue;
328  }
329 
330  // Get the height of the subtree starting at the current node.
331  auto const height = static_cast<double>( heights[ it.node().index() ]);
332  assert( height <= root_height );
333 
334  // Set the distance.
335  auto const distance = ( root_height - height ) / root_height;
336  tree().node_at( it.node().index() ).data<LayoutNodeData>().distance = distance;
337  }
338 }
339 
340 // =================================================================================================
341 // Options
342 // =================================================================================================
343 
345 {
346  text_template_ = tt;
347 }
348 
350 {
351  return text_template_;
352 }
353 
355 {
356  return text_template_;
357 }
358 
359 void LayoutBase::type( LayoutType const drawing_type )
360 {
361  type_ = drawing_type;
362  if( ! tree_.empty() ) {
363  init_layout_();
364  }
365 }
366 
368 {
369  return type_;
370 }
371 
372 } // namespace tree
373 } // namespace genesis
void set_node_shapes(utils::SvgGroup const &shape)
LayoutType type() const
double height(Tree const &tree)
Get the height of the tree, i.e., the longest distance from the root to a leaf, measured using the br...
static std::unique_ptr< LayoutNodeData > create()
TreeNode & node_at(size_t index)
Return the TreeNode at a certain index.
Definition: tree/tree.cpp:304
Tree operator functions.
static std::unique_ptr< LayoutEdgeData > create()
Default class containing the commonly needed data for tree nodes.
size_t leaf_node_count(Tree const &tree)
Count the number of leaf Nodes of a Tree.
TreeEdge & reset_data(std::unique_ptr< BaseEdgeData > data)
Reset the data pointer of this TreeEdge.
Definition: edge.cpp:200
size_t index() const
Return the index of this Node.
Definition: node.cpp:48
utils::Range< IteratorPreorder< TreeLink const, TreeNode const, TreeEdge const > > preorder(ElementType const &element)
void set_edge_shapes(utils::SvgGroup const &shape)
TreeNode & root_node()
Return the TreeNode at the current root of the Tree.
Definition: tree/tree.cpp:258
size_t node_count() const
Return the number of TreeNodes of the Tree.
Definition: tree/tree.cpp:350
Data class for LayoutTreeEdges.
Tree const & tree() const
Definition: layout_base.cpp:69
void set_edge_distance_strokes(utils::SvgStroke const &stroke)
utils::Range< IteratorEulertour< TreeLink const, TreeNode const, TreeEdge const > > eulertour(ElementType const &element)
Definition: eulertour.hpp:190
Class for representing phylogenetic trees.
Definition: tree/tree.hpp:95
bool empty() const
Return whether the Tree is empty (i.e., has no nodes, edges and links).
Definition: tree/tree.cpp:222
Tree clone_topology() const
Return a Tree with the same topology, but without any data.
Definition: tree/tree.cpp:137
std::vector< size_t > subtree_max_path_heights(Tree const &tree, TreeNode const &node)
void ladderize(Tree &tree, LadderizeOrder order)
Header of Default Tree distance methods.
void set_edge_strokes(utils::SvgStroke const &stroke)
Definition: layout_base.cpp:74
size_t edge_count() const
Return the number of TreeEdges of the Tree.
Definition: tree/tree.cpp:358
TreeNode & reset_data(std::unique_ptr< BaseNodeData > data)
Reset the data pointer of this TreeNode.
Definition: node.cpp:163
TreeEdge & edge_at(size_t index)
Return the TreeEdge at a certain index.
Definition: tree/tree.cpp:324
std::string name
Name of the node.
NodeDataType & data()
Definition: node.hpp:108
Data class for LayoutTreeNodes.
Definition: layout_tree.hpp:80
std::vector< double > node_branch_length_distance_vector(Tree const &tree, TreeNode const *node)
Return a vector containing the distance of all nodes with respect to the given start node...
Header of Tree distance methods.
utils::Range< IteratorPostorder< TreeLink const, TreeNode const, TreeEdge const > > postorder(ElementType const &element)
EdgeDataType & data()
Definition: edge.hpp:118
void set_edge_spreading_strokes(utils::SvgStroke const &stroke)
Definition: layout_base.cpp:86
EdgeDataType * data_cast()
Definition: edge.hpp:130
utils::SvgText & text_template()
NodeDataType * data_cast()
Definition: node.hpp:120