A toolkit for working with phylogenetic data.
v0.18.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
rectangular_layout.cpp
Go to the documentation of this file.
1 /*
2  Genesis - A toolkit for working with phylogenetic data.
3  Copyright (C) 2014-2017 Lucas Czech
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 
41 
43 
44 #include <algorithm>
45 #include <assert.h>
46 #include <stdexcept>
47 
48 namespace genesis {
49 namespace tree {
50 
51 // =================================================================================================
52 // Constructors
53 // =================================================================================================
54 
55 RectangularLayout::RectangularLayout( Tree const& orig_tree, Type const drawing_type )
56 {
57  // Need to set drawing type first, so that init_tree_() can use it.
58  type( drawing_type );
59  tree( orig_tree );
60 }
61 
62 // =================================================================================================
63 // Options
64 // =================================================================================================
65 
67 {
68  scaler_x_ = sx;
69  return *this;
70 }
71 
73 {
74  return scaler_x_;
75 }
76 
78 {
79  scaler_y_ = sy;
80  return *this;
81 }
82 
84 {
85  return scaler_y_;
86 }
87 
88 // =================================================================================================
89 // Virtual Functions
90 // =================================================================================================
91 
92 void RectangularLayout::init_tree_( Tree const& orig_tree )
93 {
94  if( tree().empty() ) {
95  return;
96  }
97 
98  // Init with proper data types.
99  init_nodes_( orig_tree );
100  init_edges_( orig_tree );
101 
102  // Set node x-coords according to branch lengths (distance from root).
103  if( type() == Type::kCladogram ) {
104  set_node_x_cladogram_();
105  } else if( type() == Type::kPhylogram ) {
106  set_node_x_phylogram_();
107  } else {
108  assert( false );
109  }
110 
111  // Set node y-coords.
112  set_node_y_();
113 }
114 
115 utils::SvgDocument RectangularLayout::to_svg_document_() const
116 {
117  using namespace utils;
118  SvgDocument doc;
119  SvgGroup tree_lines;
120  SvgGroup taxa_names;
121  SvgGroup node_shapes;
122 
123  for( auto const& node_it : tree().nodes() ) {
124  auto const& node = *node_it;
125 
126  auto const& node_data = node.data<RectangularNodeData>();
127  auto const& parent_data = tree().node_at( node_data.parent_index ).data<RectangularNodeData>();
128 
129  // Get the edge between the node and its parent.
130  auto edge_data_ptr = edge_between( node, tree().node_at( node_data.parent_index ) );
131 
132  // If there is an edge (i.e., we are not at the root), draw lines between the nodes.
133  if( edge_data_ptr ) {
134  auto stroke = edge_data_ptr->data<RectangularEdgeData>().stroke;
135  // stroke.line_cap = utils::SvgStroke::LineCap::kRound;
136 
137  tree_lines << SvgLine(
138  node_data.x, node_data.y,
139  parent_data.x, node_data.y,
140  stroke
141  );
142  tree_lines << SvgLine(
143  parent_data.x, node_data.y,
144  parent_data.x, parent_data.y,
145  stroke
146  );
147  } else {
148 
149  // If there is no edge, it must be the root.
150  assert( node.is_root() );
151  }
152 
153  // If the node has a name, print it.
154  if( node_data.name != "" ) {
155  // auto label = SvgText( node_data.name, SvgPoint( node_data.x + 5, node_data.y ) );
156  // label.dy = "0.4em";
157 
158  auto label = text_template();
159  label.text = node_data.name;
160  label.transform.append( SvgTransform::Translate(
161  node_data.x + 5,
162  node_data.y
163  ));
164  taxa_names << std::move( label );
165  }
166 
167  // If there is a node shape, draw it.
168  if( ! node_data.shape.empty() ) {
169  auto ns = node_data.shape;
170  ns.transform.append( SvgTransform::Translate( node_data.x, node_data.y ));
171  node_shapes << std::move( ns );
172  }
173  }
174 
175  // We are sure that we won't use the groups again, so let's move them!
176  doc << std::move( tree_lines );
177  if( ! taxa_names.empty() ) {
178  doc << std::move( taxa_names );
179  }
180  if( ! node_shapes.empty() ) {
181  doc << std::move( node_shapes );
182  }
183  return doc;
184 }
185 
186 // =================================================================================================
187 // Internal Functions
188 // =================================================================================================
189 
190 void RectangularLayout::init_nodes_( Tree const& orig_tree )
191 {
192  // Init nodes.
193  for( size_t i = 0; i < tree().node_count(); ++i ) {
194  // Safety: correct indices.
195  assert( tree().node_at(i).index() == i && orig_tree.node_at(i).index() == i );
196 
197  // Set the tree node data.
199  auto& node_data = tree().node_at(i).data<RectangularNodeData>();
200 
201  // Set defaults needed to later distinguish whether those values have already been set.
202  node_data.x = -1.0;
203  node_data.y = -1.0;
204 
205  // If the original tree has node names, use them.
206  auto orig_node_data_ptr = orig_tree.node_at(i).data_cast<DefaultNodeData>();
207  if( orig_node_data_ptr ) {
208  node_data.name = orig_node_data_ptr->name;
209  }
210  }
211 }
212 
213 void RectangularLayout::init_edges_( Tree const& orig_tree )
214 {
215  // Init edges.
216  for( size_t i = 0; i < tree().edge_count(); ++i ) {
217  // Safety: correct indices.
218  assert( tree().edge_at(i).index() == i && orig_tree.edge_at(i).index() == i );
219 
220  // Set the tree edge data.
222  auto& edge_data = tree().edge_at(i).data<RectangularEdgeData>();
223 
224  // If the original tree has edge branch lengths, use them.
225  auto orig_edge_data_ptr = orig_tree.edge_at(i).data_cast<DefaultEdgeData>();
226  if( orig_edge_data_ptr ) {
227  edge_data.branch_length = orig_edge_data_ptr->branch_length;
228  }
229  }
230 }
231 
232 void RectangularLayout::set_node_y_()
233 {
234  // Set node parents and y-coord of leaves.
235  size_t leaf_count = 0;
236  size_t parent = 0;
237  for( auto it : eulertour( tree() )) {
238  auto& node_data = tree().node_at( it.node().index() ).data<RectangularNodeData>();
239 
240  if( node_data.parent_index == -1 ) {
241  node_data.parent_index = parent;
242  }
243  if( it.node().is_leaf() ) {
244  node_data.y = scaler_y_ * leaf_count++;
245  }
246 
247  parent = it.node().index();
248  }
249 
250  // Set remaining y-coords of inner nodes to mid-points of their children.
251  for( auto it : postorder( tree() )) {
252  auto& node_data = tree().node_at( it.node().index() ).data<RectangularNodeData>();
253  auto& parent_data = tree().node_at( node_data.parent_index ).data<RectangularNodeData>();
254 
255  if( node_data.y < 0.0 ) {
256  auto min_max_diff = node_data.children_max_y - node_data.children_min_y;
257  node_data.y = node_data.children_min_y + min_max_diff / 2.0;
258  }
259 
260  if( parent_data.children_min_y < 0.0 || parent_data.children_min_y > node_data.y ) {
261  parent_data.children_min_y = node_data.y;
262  }
263  if( parent_data.children_max_y < 0.0 || parent_data.children_max_y < node_data.y ) {
264  parent_data.children_max_y = node_data.y;
265  }
266  }
267 }
268 
269 void RectangularLayout::set_node_x_phylogram_()
270 {
271  auto node_dists = node_branch_length_distance_vector( tree() );
272 
273  for( size_t i = 0; i < node_dists.size(); ++i ) {
274  tree().node_at(i).data<RectangularNodeData>().x = node_dists[i] * scaler_x_;
275  }
276 }
277 
278 void RectangularLayout::set_node_x_cladogram_()
279 {
280  // Set root x to 0.
281  tree().root_node().data<RectangularNodeData>().x = 0.0;
282 
283  // Get the heights of all subtrees starting from the root.
284  auto heights = subtree_max_path_heights( tree() );
285 
286  // Get the height of the tree, i.e. longest path from root to any leaf.
287  auto root_height = heights[ tree().root_node().index() ];
288 
289  for( auto it : preorder( tree() )) {
290  // The subtree height calculation does not work for the root, so skip it.
291  // Also, we already set the leaf.
292  if( it.is_first_iteration() ) {
293  continue;
294  }
295 
296  // Get the height of the subtree starting at the current node.
297  auto height = heights[ it.node().index() ];
298  assert( height <= root_height );
299 
300  // Set the x position.
301  auto x = ( root_height - height ) * scaler_x_;
302  tree().node_at( it.node().index() ).data<RectangularNodeData>().x = x;
303  }
304 }
305 
306 } // namespace tree
307 } // namespace genesis
static std::unique_ptr< RectangularNodeData > create()
size_t index() const
Return the index of this Edge.
Definition: edge.cpp:45
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...
TreeNode & node_at(size_t index)
Return the TreeNode at a certain index.
Definition: tree/tree.cpp:304
Tree operator functions.
TreeEdge & reset_data(std::unique_ptr< BaseEdgeData > data)
Reset the data pointer of this TreeEdge.
Definition: edge.cpp:200
TreeEdge * edge_between(TreeNode &lhs, TreeNode &rhs)
Return the TreeEdge between two TreeNode&s, if they are neighbours, or nullptr otherwise.
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)
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
Tree const & tree() const
Definition: layout_base.cpp:51
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
std::vector< size_t > subtree_max_path_heights(Tree const &tree, TreeNode const &node)
Header of Default Tree distance methods.
Provides easy and fast logging functionality.
static std::unique_ptr< RectangularEdgeData > create()
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
NodeDataType & data()
Definition: node.hpp:108
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
utils::SvgText & text_template()
Definition: layout_base.cpp:85