Quetzal-CoaTL
The Coalescence Template Library
Loading...
Searching...
No Matches
from_tree_graph.hpp
1// Copyright 2021 Arnaud Becheler <abechele@umich.edu>
2
10
11#pragma once
12
13#include "quetzal/coalescence/graph/binary_tree.hpp"
14#include "quetzal/coalescence/graph/k_ary_tree.hpp"
15#include "quetzal/io/newick/ast.hpp"
16#include "quetzal/io/newick/generator.hpp"
17#include "quetzal/io/newick/parser.hpp"
18
19#include <algorithm>
20#include <concepts>
21#include <string>
22
23namespace quetzal::format::newick
24{
25namespace detail
26{
27template <class Gen> struct TreeVisitorWrapper
28{
29 std::reference_wrapper<Gen> _generator;
30 boost::visit _previous;
31 TreeVisitorWrapper(Gen &gen) : _generator(gen)
32 {
33 }
34
35 void operator()(boost::visit stage, auto v)
36 {
37 switch (stage)
38 {
39 case boost::visit::pre:
40 _generator.get().pre_order()(v);
41 _previous = boost::visit::pre;
42 break;
43 case boost::visit::in:
44 if (_previous == boost::visit::post)
45 _generator.get().in_order()();
46 _previous = boost::visit::in;
47 break;
48 case boost::visit::post:
49 _generator.get().post_order()(v);
50 _previous = boost::visit::post;
51 break;
52 }
53 }
54};
55
56// We expose its interface to the boost DFS algorithm
57template <typename Gen, typename Stack> struct KaryTreeVisitorWrap : boost::default_dfs_visitor
58{
59 Gen &gen_;
60 Stack &stack_;
61 KaryTreeVisitorWrap(Gen &gen, Stack &s) : gen_(gen), stack_(s)
62 {
63 }
64 void discover_vertex(auto v, auto const &) const
65 {
66 stack_.push(0);
67 gen_.pre_order()(v);
68 }
69 void finish_vertex(auto v, auto const &) const
70 {
71 gen_.post_order()(v);
72 stack_.pop();
73 }
74 void tree_edge(auto e, auto const &g) const
75 {
76 if (stack_.top()++ > 0)
77 gen_.in_order()();
78 }
79};
80} // namespace detail
81
82//
83// @brief Generate a Newick string from a k-ary tree with no properties attached to edges or vertices
84//
85template <typename Flavor>
86std::string generate_from(
87 quetzal::coalescence::k_ary_tree<boost::no_property, boost::no_property> const &graph,
88 typename quetzal::coalescence::k_ary_tree<boost::no_property, boost::no_property>::vertex_descriptor root,
89 Flavor flavor)
90{
91 using tree_type = quetzal::coalescence::k_ary_tree<boost::no_property, boost::no_property>;
92 using vertex_type = tree_type::vertex_descriptor;
93
94 namespace newick = quetzal::format::newick;
95
96 // Data access
97 std::predicate<vertex_type> auto has_parent = [&graph](vertex_type const &v) { return graph.has_predecessor(v); };
98 std::predicate<vertex_type> auto has_children = [&graph](vertex_type v) { return graph.has_successors(v); };
99 newick::Formattable<vertex_type> auto branch_length = [](vertex_type) { return ""; };
100 newick::Formattable<vertex_type> auto label = [](vertex_type v) { return ""; };
101
102 // We declare a generator passing it the data interfaces
103 newick::generator gen{has_parent, has_children, label, branch_length, flavor};
104 using Gen = decltype(gen);
105
106 detail::TreeVisitorWrapper vis(gen);
107 graph.depth_first_search(root, vis);
108 return gen.take_result();
109}
110
111//
112// @brief Generate a Newick string from a k-ary tree with no properties attached to edges or vertices
113//
114template <typename Flavor>
115std::string generate_from(
116 quetzal::coalescence::binary_tree<boost::no_property, boost::no_property> const &graph,
117 typename quetzal::coalescence::binary_tree<boost::no_property, boost::no_property>::vertex_descriptor root,
118 Flavor flavor)
119{
120 using tree_type = quetzal::coalescence::binary_tree<boost::no_property, boost::no_property>;
121 using vertex_type = typename tree_type::vertex_descriptor;
122 namespace newick = quetzal::format::newick;
123
124 // Data access
125 std::predicate<vertex_type> auto has_parent = [&graph](vertex_type const &v) { return graph.has_predecessor(v); };
126
127 std::predicate<vertex_type> auto has_children = [&graph](vertex_type v) {
128 return static_cast<bool>(graph.out_degree(v));
129 };
130
131 newick::Formattable<vertex_type> auto branch_length = [](vertex_type) { return ""; };
132
133 newick::Formattable<vertex_type> auto label = [](vertex_type) { return ""; };
134
135 // We declare a generator passing it the data interfaces
136 newick::generator gen{has_parent, has_children, label, branch_length, flavor};
137 using Gen = decltype(gen);
138
139 // We expose its interface to the boost DFS algorithm
140 struct VisWrap
141 {
142 std::reference_wrapper<Gen> _generator;
143 boost::visit _previous;
144 VisWrap(Gen &gen) : _generator(gen)
145 {
146 }
147 void operator()(boost::visit stage, vertex_type v)
148 {
149 switch (stage)
150 {
151 case boost::visit::pre:
152 _generator.get().pre_order()(v);
153 _previous = boost::visit::pre;
154 break;
155 case boost::visit::in:
156 if (_previous == boost::visit::post)
157 _generator.get().in_order()();
158 _previous = boost::visit::in;
159 break;
160 case boost::visit::post:
161 _generator.get().post_order()(v);
162 _previous = boost::visit::post;
163 break;
164 }
165 }
166 } vis{gen};
167
168 graph.depth_first_search(root, vis);
169 return gen.take_result();
170}
171
172//
173// @brief Generate a Newick string from a binary tree with properties attached to edges and vertices
174//
175template <class VertexProperty, class EdgeProperty, typename Flavor>
176 requires(!std::is_same_v<VertexProperty, boost::no_property> && !std::is_same_v<VertexProperty, boost::no_property>)
177std::string
178 generate_from(quetzal::coalescence::binary_tree<VertexProperty, EdgeProperty> const &graph,
179 typename quetzal::coalescence::binary_tree<VertexProperty, EdgeProperty>::vertex_descriptor root,
180 Flavor flavor)
181{
182 using tree_type = quetzal::coalescence::binary_tree<VertexProperty, EdgeProperty>;
183 using vertex_descriptor = typename tree_type::vertex_descriptor;
184 using edge_descriptor = typename tree_type::edge_descriptor;
185 namespace newick = quetzal::format::newick;
186
187 // Data access
188 std::predicate<vertex_descriptor> auto has_parent = [&graph](vertex_descriptor const &v) {
189 return graph.has_predecessor(v);
190 };
191
192 std::predicate<vertex_descriptor> auto has_children = [&graph](vertex_descriptor v) {
193 return static_cast<bool>(graph.out_degree(v));
194 };
195
196 newick::Formattable<vertex_descriptor> auto branch_length = [&graph = std::as_const(graph)](vertex_descriptor v) {
197 std::string s = graph.has_predecessor(v) ? graph[edge_descriptor(graph.predecessor(v), v)].label() : "";
198 return s;
199 };
200
201 newick::Formattable<vertex_descriptor> auto label = [&graph](vertex_descriptor v) { return graph[v].label(); };
202
203 // We declare a generator passing it the data interfaces
204 newick::generator gen{has_parent, has_children, label, branch_length, flavor};
205 using Gen = decltype(gen);
206
207 // We expose its interface to the boost DFS algorithm
208 struct VisWrap
209 {
210 std::reference_wrapper<Gen> _generator;
211 boost::visit _previous;
212 VisWrap(Gen &gen) : _generator(gen)
213 {
214 }
215 void operator()(boost::visit stage, vertex_descriptor v)
216 {
217 switch (stage)
218 {
219 case boost::visit::pre:
220 _generator.get().pre_order()(v);
221 _previous = boost::visit::pre;
222 break;
223 case boost::visit::in:
224 if (_previous == boost::visit::post)
225 _generator.get().in_order()();
226 _previous = boost::visit::in;
227 break;
228 case boost::visit::post:
229 _generator.get().post_order()(v);
230 _previous = boost::visit::post;
231 break;
232 }
233 }
234 } vis{gen};
235
236 graph.depth_first_search(root, vis);
237 return gen.take_result();
238}
239
243template <class VertexProperty, class EdgeProperty, typename Flavor>
244 requires(!std::is_same_v<VertexProperty, boost::no_property> && !std::is_same_v<VertexProperty, boost::no_property>)
245std::string
246 generate_from(const quetzal::coalescence::k_ary_tree<VertexProperty, EdgeProperty> &graph,
247 typename quetzal::coalescence::binary_tree<VertexProperty, EdgeProperty>::vertex_descriptor root,
248 Flavor flavor)
249{
250 namespace newick = quetzal::format::newick;
251 using tree_type = quetzal::coalescence::k_ary_tree<VertexProperty, EdgeProperty>;
252 using vertex_descriptor = typename tree_type::vertex_descriptor;
253 using edge_descriptor = typename tree_type::edge_descriptor;
254 namespace newick = quetzal::format::newick;
255
256 // Data access
257 std::predicate<vertex_descriptor> auto has_parent = [&graph](vertex_descriptor const &v) {
258 return graph.has_predecessor(v);
259 };
260
261 std::predicate<vertex_descriptor> auto has_children = [&graph](vertex_descriptor v) {
262 return static_cast<bool>(graph.out_degree(v));
263 };
264
265 newick::Formattable<vertex_descriptor> auto branch_length = [&graph = std::as_const(graph)](vertex_descriptor v) {
266 std::string s = graph.has_predecessor(v) ? graph[graph.edge(graph.predecessor(v), v).value()].label() : "";
267 return s;
268 };
269
270 newick::Formattable<vertex_descriptor> auto label = [&graph](vertex_descriptor v) { return graph[v].label(); };
271
272 // We declare a generator passing it the interfaces
273 newick::generator gen(has_parent, has_children, label, branch_length);
274 using Gen = decltype(gen);
275
276 // We expose its interface to the boost DFS algorithm
277 struct VisWrap
278 {
279 std::reference_wrapper<Gen> _generator;
280 boost::visit _previous;
281 VisWrap(Gen &gen) : _generator(gen)
282 {
283 }
284 void operator()(boost::visit stage, vertex_descriptor v)
285 {
286 switch (stage)
287 {
288 case boost::visit::pre:
289 _generator.get().pre_order()(v);
290 _previous = boost::visit::pre;
291 break;
292 case boost::visit::in:
293 if (_previous == boost::visit::post)
294 _generator.get().in_order()();
295 _previous = boost::visit::in;
296 break;
297 case boost::visit::post:
298 _generator.get().post_order()(v);
299 _previous = boost::visit::post;
300 break;
301 }
302 }
303 } vis{gen};
304
305 graph.depth_first_search(root, vis);
306 return gen.take_result();
307}
308
309} // end namespace quetzal::format::newick
quetzal::coalescence::binary_tree
Definition binary_tree.hpp:330
quetzal::coalescence::k_ary_tree
Definition k_ary_tree.hpp:349
quetzal::format::newick::generator
Generate the Newick formula from an external (custom) tree class.
Definition generator.hpp:261
quetzal::format::newick::generator::take_result
std::string && take_result() const
Retrieve the formatted string of the given node in the specified format.
Definition generator.hpp:424
quetzal::format::newick::Formattable
Concept for label name.
Definition from_network.hpp:213
quetzal::format::newick
Generic components for parsing or generating Newick strings.
Definition io.hpp:28