I have defined formatting operations on trees that work pretty well when they are used a pre/in/post order operators with the following structure and DFS definition (it works also on k-ary trees):
struct Node
{
Node *parent = nullptr;
Node *left = nullptr;
Node *right = nullptr;
char data;
template<class Op1, class Op2, class Op3>
void depth_first_search(Op1 pre_order, Op2 in_order, Op3 post_order)
{
pre_order(*this);
if(this->left != nullptr && this->right != nullptr)
{
this->left->depth_first_search(pre_order, in_order, post_order);
in_order(*this);
this->right->depth_first_search(pre_order, in_order, post_order);
in_order(*this);
}
post_order(*this);
}
};
I can format this structure with the following:
Formatter formatter(my_config);
tree.depth_first_search(formatter.get_pre_order(), formatter.get_in_order(), formatter.get_post_order());
auto result = formatter.take_result();
Since they work nicely, I would like to re-use the same functors to operate formatting on Boost graphs when they have values of trees. So I am trying to get this (approximate/buggy) syntax working:
template<class Formatter>
class my_visitor : boost::default_dfs_visitor
{
Formatter & _formatter;
public:
my_visitor(Formatter& formatter) : _formatter(formatter){}
auto discover_vertex(auto vertex, auto const& g)
{
auto f = _formatter.get_pre_order();
f(vertex);
}
auto examine_edge(auto edge, auto const& g)
{
auto f = _formatter.get_in_order();
f(edge);
}
auto finish_vertex(auto vertex, auto const& g)
{
auto f = _formatter.get_post_order();
f(vertex);
}
};
So I can format the tree using a syntax like
Formatter formatter(my_config);
my_visitor vis(formatter);
depth_first_search(graph, root, boost::visitor(vis));
auto s = formatter.take_result();
In its present state, the code compiles and run on Gobolt: https://godbolt.org/z/bzjqjbvE3
However, the last method called in the main function does not exist (yet) since I don't know how to specify it:
auto s = newick::generate_from(tree);
There is a commented draft of such function but I struggle fitting it to BGL:
///
/// @brief Generate a Newick string from a k-ary tree with no properties attached to edges or vertices
///
std::string generate_from(quetzal::coalescence::k_ary_tree<> graph)
{
using vertex_t = typename quetzal::coalescence::k_ary_tree<>::vertex_descriptor;
// Data access
std::predicate<vertex_t> auto has_parent = [&graph](vertex_t v){ return graph.has_parent(v); };
std::predicate<vertex_t> auto has_children = [&graph](vertex_t v){ return graph.has_children(v); };
newick::Formattable<vertex_t> auto label = [&graph](auto){ return ""; };
newick::Formattable<vertex_t> auto branch_length = [&graph](auto){ return ""; };
// We declare a generator passing it the data interfaces
auto generator = newick::make_generator(has_parent, has_children, label, branch_length);
// We expose its interface to the boost DFS algorithm
detail::newick_no_property_visitor vis(generator);
depth_first_search(graph, boost::visitor(vis));
}
I can not really wrap my head around the interface consistency and I struggle identifying the root (lol) of the problem:
Node semantic (encapsulating both the node identifier and the graph it refers to)pre-order maps to discover_vertex, in_order maps to examine_edge and post_order maps to finish_vertex, although I am not certain ?Is there a way to reconcile these two interfaces or their semantic is too different and I have to duplicate/modify the formatting grammar?
Here's my take on it. Instead of generating a random graph, let's replicate the exact graph that you treated with your "old-style Node* 2-ary tree":
using G = quetzal::coalescence::k_ary_tree<>;
using V = G::vertex_descriptor;
enum {a,b,c,d,e,N};
G tree(N);
/*
* a
* / \
* / c
* / / \
* b d e
*/
add_edge(a, b, tree);
add_edge(a, c, tree);
add_edge(c, d, tree);
add_edge(c, e, tree);
auto name_map = boost::make_function_property_map<V>([](V v) -> char { return 'a' + v; });
print_graph(tree, name_map);
Prints
a --> b c
b -->
c --> d e
d -->
e -->
The key is to wrap the "formatter" (generator) into a DFS visitor suitably.
Some notes:
State struct:// We declare a generator passing it the data interfaces
struct State {
newick::generator<V, P, P, F, F, decltype(flavor)> gen;
std::stack<int> nth_child;
} state{{has_parent, has_children, label, branch_length, flavor}, {}};
// We expose its interface to the boost DFS algorithm
struct VisWrap : boost::default_dfs_visitor {
State& state_;
VisWrap(State& ref) : state_(ref) {}
void discover_vertex(V v, G const&) const {
state_.nth_child.push(0);
state_.gen.pre_order()(v);
}
void finish_vertex(V v, G const&) const {
state_.gen.post_order()(v);
state_.nth_child.pop();
}
void tree_edge(E e, G const& g) const {
if (state_.nth_child.top()++ > 0)
state_.gen.in_order()(target(e, g));
}
} vis{state};
depth_first_search(graph, boost::visitor(vis));
return state.gen.take_result();
You had mixed up in_edges and out_edges inside has_parent() and has_children(). So I changed those from:
bool has_parent(vertex_descriptor v) const {
auto [it1, it2] = out_edges(v, *this);
// since it is a tree, at most 1 parent
assert(std::distance(it1,it2) <= 1);
// if iterators equal, then no parent
return it1 == it2 ? false : true;
}
bool has_children(vertex_descriptor v) const {
auto [it1, it2] = in_edges(v, *this);
return std::distance(it1, it2) >= 1;
}
Into the (slightly modernized):
bool has_parent(vertex_descriptor v) const {
auto pp = make_iterator_range(in_edges(v, *this));
// since it is a tree, at most 1 parent
assert(boost::size(pp) <= 1);
return !pp.empty();
}
bool has_children(vertex_descriptor v) const {
return !make_iterator_range(out_edges(v, *this)).empty();
}
Note that using in_edges does necessitate changing to a model of BidirectionalGraph by changing
using directed_type = boost::directedS;
into
using directed_type = boost::bidirectionalS; // for boost::in_edges
Due to the timing issues of the generator operations vs. the visitor events I had to add some guards around adding/removing the comma delimiters. I have a feeling that if you remove the "impedance mismatch" in this area things will become simpler.
There's some work left that you left out of scope for this question (good idea), meaning actually generalizing for the label/length functions.
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/isomorphism.hpp>
#include <concepts>
#include <iostream>
#include <regex>
namespace quetzal::coalescence {
namespace details {
///
/// @brief Defines the desired properties and constraints for a coalescent graph
///
struct tree_traits {
/// @brief Trees are sparse graph in nature, adjacency_matrix would not be justified here
template <class... Types> using model = boost::adjacency_list<Types...>;
/// @brief We want to enforce avoiding multi-graphs (edges with same end nodes)
using out_edge_list_type = boost::setS;
/// @brief We don't allow for inserting vertices except at the end and we don't remove vertices.
/// This means that neither reallocation cost nor stability are reasons for preferring
/// listS to vecS.
using vertex_list_type = boost::vecS;
/// @brief Coalescent trees are directed acyclic graphs
using directed_type = boost::bidirectionalS; // for boost::in_edges
};
} // namespace details
///
/// @brief A class adapted for simulating coalescent trees as a rooted K-ary tree, where each node can
/// hold at most k number of children.
///
/// @remark
/// - Since topology (pure structure) matter, a coalescence tree is more than a data container.
/// - This class inherits from as a boost::graph with specialized edge and vertex properties
/// defined in details#tree_traits
/// - The simulation interface intentionally does not allow for removing edges or vertices,
/// but you may access the underlying boost graph object to do so.
///
template <class VertexProperties = boost::no_property, class EdgeProperties = boost::no_property>
struct k_ary_tree
: public details::tree_traits::model<
details::tree_traits::out_edge_list_type, details::tree_traits::vertex_list_type,
details::tree_traits::directed_type, VertexProperties, EdgeProperties> {
/// @brief Properties of an edge, e.g. a structure representing the series of demes visited or simply
/// the branch length.
using edge_properties = EdgeProperties;
/// @brief Properties of a vertex, e.g. a structure representing the mutational state.
using vertex_properties = VertexProperties;
/// @brief The type of graph hold by the tree class
using base_type = details::tree_traits::model<
details::tree_traits::out_edge_list_type, details::tree_traits::vertex_list_type,
details::tree_traits::directed_type, vertex_properties, edge_properties>;
using self_type = k_ary_tree<vertex_properties, edge_properties>;
/// @brief The type used for identifying vertices within the graph
using vertex_descriptor = typename self_type::vertex_descriptor;
/// @brief Inherit all constructor from boost graph
using base_type::base_type;
///
/// @brief Print the tree to the graphviz format
/// @remarks Intends to hide the bundles writer syntax
///
void to_graphviz(std::ostream& out) const {
using namespace boost;
return boost::write_graphviz(out, *this,
boost::make_label_writer(boost::get(vertex_bundle, *this)),
boost::make_label_writer(boost::get(edge_bundle, *this)));
}
///
/// @brief Returns true if there exists an isomorphism between this and other and false otherwise.
///
template <class T> bool is_isomorphic(T const& other) noexcept {
return boost::isomorphism(*this, other);
}
///
/// @brief Returns true if a given node has a parent node
///
bool has_parent(vertex_descriptor v) const {
auto pp = make_iterator_range(in_edges(v, *this));
// since it is a tree, at most 1 parent
assert(boost::size(pp) <= 1);
return !pp.empty();
}
///
/// @brief Returns true if a given node has children nodes
///
bool has_children(vertex_descriptor v) const {
return !make_iterator_range(out_edges(v, *this)).empty();
}
}; // end class Tree
} // end namespace quetzal::coalescence
namespace quetzal::format::newick {
namespace detail {
// Replacement for `std::function<T(U)>::argument_type`
template <typename T> struct single_function_argument;
template <typename Ret, typename Arg> struct single_function_argument<std::function<Ret(Arg)>> {
using type = Arg;
};
template <typename P1> struct single_function_argument_impl {
using type = typename single_function_argument<decltype(std::function{std::declval<P1>()})>::type;
};
template <typename P1>
using single_function_argument_t = typename single_function_argument_impl<P1>::type;
/// @brief Tag
struct parenthesis {};
/// @brief Tag
struct square_bracket {};
///
/// @brief Check if the string is balanced for open/close symbols (parenthesis,brackets)
///
///
/// @note Since parenthesis checking is a context-free grammar, it requires a stack.
/// Regex can not accomplish that since they do not have memory.
///
bool check_if_balanced(std::string_view input, char const& open = '(', char const& close = ')') {
int count = 0;
for (auto const& ch : input) {
if (ch == open)
count++;
if (ch == close)
count--;
// if a parenthesis is closed without being opened return false
if (count < 0)
return false;
}
// in the end the test is passed only if count is zero
return count == 0;
}
///
/// @brief Default comment removal policy: do not change anything
///
struct identity {
static std::string edit(const std::string s) { return s; }
};
///
/// @brief Class template, base for further specialization
///
template <class tag> struct is_balanced {};
///
/// @brief Specialization for parenthesis
///
template <> struct is_balanced<detail::parenthesis> {
static bool check(std::string_view s) { return check_if_balanced(s, '(', ')'); }
};
///
/// @brief Specialization for square bracket
///
template <> struct is_balanced<detail::square_bracket> {
static bool check(std::string_view s) { return check_if_balanced(s, '[', ']'); }
};
} // namespace detail
using namespace std::string_literals;
///
/// @brief Node names can be any character except blanks, colons, semicolons, parentheses, and square
/// brackets.
///
static inline std::vector<std::string> forbidden_labels = {" "s, ","s, ";"s, "("s, ")"s, "["s, "]"s};
///
/// @brief Underscore characters in unquoted labels are converted to blanks.
///
/// @detail Because you may want to include a blank in a name, it is assumed
/// that an underscore character ("_") stands for a blank; any of
/// these in a name will be converted to a blank when it is read in.
///
static inline constexpr char blank = '_';
///
/// @brief Template class.
///
template <unsigned int N> struct remove_comments_of_depth {};
///
/// @brief Do not remove anything
///
template <> struct remove_comments_of_depth<0> : detail::identity {};
///
/// @brief Remove all comments substrings contained between square brackets
///
/// @note Assumes that text is well formatted so there are no such things like [[]] or unclosed bracket
///
template <> struct remove_comments_of_depth<1> {
static std::string edit(const std::string s) {
if (s.empty())
return s;
return std::regex_replace(s, std::regex(R"(\[[^()]*\])"), "");
}
};
///
/// @brief Remove all comments substrings contained between square brackets of depth 2
///
/// @note Assumes that text is well formatted so there are no such things like [[]] or unclosed bracket
///
template <> struct remove_comments_of_depth<2> {
static std::string edit(const std::string s) {
std::string buffer;
int counter = 0;
for (auto const& ch : s) {
if (ch == '[')
counter++;
if (ch == ']')
counter--;
if (ch == '[' && counter == 2)
continue; // do nothing, that was the opening
if (ch == ']' && counter == 1)
continue; // do nothing, that was the closing
if (!(counter >= 2 || (counter == 1 && ch == ']')))
buffer.append(std::string(1, ch));
}
return buffer;
}
};
///
/// @brief Policy allowing to keep nested comments.
///
/// @note Use this as a template parameter to specialize a Newick generator policy
///
struct PAUP {
// return empty string
static inline std::string root_branch_length() { return ""; }
// do nothing
static inline std::string treat_comments(std::string& s) { return s; }
};
///
/// @brief Set a root node branch length to zero, allow comments of depth 1, but will remove nested
/// comments.
///
/// @note Use this as a template parameter to specialize a Newick generator policy
///
struct TreeAlign {
// Set explicit null branch length for root node
static inline std::string root_branch_length() { return ":0.0"; }
// Remove comments that are nested, keep comments of depth 1
static inline std::string treat_comments(const std::string s) {
return remove_comments_of_depth<2>::edit(s);
}
};
///
/// @brief Requires that an unrooted tree begin with a trifurcation; it will not "uproot" a rooted tree.
/// Allow comments of depth 1, but does not allow nested comments.
/// @note Use this as a template parameter to specialize a Newick generator policy
///
struct PHYLIP {
// Branch length for root node is not explicit.
static inline std::string root_branch_length() { return ""; }
// Remove comments that are nested, keep comments of depth 1
static inline std::string treat_comments(std::string& s) {
// Allow comments of depth 1, but does not allow nested comments.
return remove_comments_of_depth<2>::edit(s);
}
};
///
/// @brief Concept for label name: invocable and the return type is convertible to a string.
///
template <class F, class... Args>
concept Formattable =
std::invocable<F, Args...> && std::convertible_to<std::invoke_result_t<F, Args...>, std::string>;
///
/// @brief Generate the Newick formula from an external (custom) tree class.
///
/// @remark This is a non-intrusive interface implementation so users can reuse Newick formatting
/// logic and expose the formatting internals to their own Tree class's DFS.
template <class T, std::predicate<T> P1, std::predicate<T> P2, Formattable<T> F1, Formattable<T> F2,
class Policy = PAUP>
class generator : public Policy {
public:
///
/// @brief Type of node being formatted
///
using node_type = T;
///
/// @brief Type of formula being generated
///
using formula_type = std::string;
///
/// @brief Type of formula being generated
///
using policy_type = Policy;
private:
///
/// @brief End character.
///
static inline constexpr char _end = ';';
///
/// @brief The string formula to be updated.
///
mutable formula_type _formula;
///
/// @brief Functor inspecting if the node being visited has a parent.
///
P1 _has_parent;
///
/// @brief Functor inspecting if the node being visited has children.
///
P2 _has_children;
///
/// @brief Retrieve the name of the node being visited.
///
/// @detail A name can be any string of printable characters except blanks,
/// colons, semicolons, parentheses, and square brackets.
///
/// @remark Return type must be convertible to std::string
///
F1 _label;
///
/// @brief Retrieve the branch length immediately above the node being visited.
///
/// @details Branch lengths can be incorporated into a tree by putting a
/// real number, with or without decimal point, after a node and
/// preceded by a colon. This represents the length of the branch
/// immediately above that node (that is, distance to parent node)
/// @remark Return type must be convertible to std::string
///
F2 _branch_length;
void _pre_order(node_type const& node) const {
if (std::invoke(_has_children, node)) {
_formula += '(';
}
}
void _in_order(node_type const&) const { _formula += ","; }
void _post_order(node_type const& node) const {
if (std::invoke(_has_children, node)) {
if (_formula.back() == ',')
_formula.pop_back(); // Remove comma
_formula += ')';
}
if (std::invoke(_has_parent, node)) {
auto label = std::invoke(_label, node);
if (has_forbidden_characters(remove_comments_of_depth<1>::edit(label))) {
throw std::invalid_argument(std::string("Label with forbidden characters:") +
std::string(label));
}
_formula += label;
std::string branch(std::invoke(_branch_length, node));
if (!branch.empty()) {
_formula += ":";
_formula += branch;
}
} else {
_formula += std::invoke(_label, node);
_formula += policy_type::root_branch_length();
}
}
public:
///
/// @brief Constructor
///
generator(P1 has_parent, P2 has_children, F1 label, F2 branch_length, Policy pol = {})
: policy_type(std::move(pol))
, _has_parent(std::move(has_parent))
, _has_children(std::move(has_children))
, _label(std::move(label))
, _branch_length(std::move(branch_length)) {}
///
/// @brief Operation called in the general DFS algorithm to open a parenthesis if node has children to
/// be visited.
///
/// @param node the node currently visited
///
auto pre_order() {
return [this](node_type const& node) { this->_pre_order(node); };
}
///
/// @brief Operation called in the general DFS algorithm to add a comma between visited nodes.
///
auto in_order() {
return [this](node_type const& node) { this->_in_order(node); };
}
///
/// @brief Operation to be passed to a generic DFS algorithm to open a parenthesis if node has
/// children to be visited.
///
/// @param node the node currently visited
///
auto post_order() {
return [this](node_type const& node) { this->_post_order(node); };
}
///
/// @brief Check if a string contains characters forbidden by the standard
///
bool has_forbidden_characters(std::string const& s) const {
if (s.empty())
return false;
std::string forbidden = " ,;()[\\]";
bool is_forbidden = std::regex_search(s, std::regex("[" + forbidden + "]"));
return is_forbidden;
}
///
/// @brief Clear the formula buffer to refresh the generator.
///
void clear() { _formula.clear(); }
///
/// @brief Retrieve the formatted string of the given node in the specified format
///
std::string&& take_result() const {
_formula.push_back(this->_end);
_formula = policy_type::treat_comments(_formula);
if (detail::is_balanced<detail::parenthesis>::check(_formula) == false) {
throw std::runtime_error(std::string("Failed: formula parenthesis are not balanced:") +
_formula);
}
if (detail::is_balanced<detail::square_bracket>::check(_formula) == false) {
throw std::runtime_error(std::string("Failed: formula square brackets are not balanced:") +
_formula);
}
return std::move(_formula);
}
}; // end structure generator
///
/// @brief User-defined deduction guide where the node/graph type T is deduced from P1
/// @remark Template deduction guides are patterns associated with a template
/// class that tell the compiler how to translate a set of constructor
/// arguments (and their types) into template parameters for the class.
template <class P1, class P2, class F1, class F2, class Policy = PAUP>
generator(P1, P2, F1, F2, Policy pol = {})
-> generator<detail::single_function_argument_t<P1>, P1, P2, F1, F2, Policy>;
} // end namespace quetzal::format::newick
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <iomanip>
// Simplistic tree for testing - emulates implementations found in my field
struct Node {
Node* parent = nullptr;
Node* left = nullptr;
Node* right = nullptr;
char data;
template <class Op1, class Op2, class Op3>
void depth_first_search(Op1 pre_order, Op2 in_order, Op3 post_order) {
pre_order(*this);
if (this->left != nullptr && this->right != nullptr) {
this->left->depth_first_search(pre_order, in_order, post_order);
in_order(*this);
this->right->depth_first_search(pre_order, in_order, post_order);
in_order(*this);
}
post_order(*this);
}
};
using Flavor = quetzal::format::newick::TreeAlign;
std::string legacy_implementation() {
/* Topology :
*
* a
* / \
* / c
* / / \
* b d e
*/
Node a, b, c, d, e;
a.data = 'a';
b.data = 'b';
c.data = 'c';
d.data = 'd';
e.data = 'e';
a.left = &b;
b.parent = &a;
a.right = &c;
c.parent = &a;
c.left = &d;
d.parent = &c;
c.right = &e;
e.parent = &c;
namespace newick = quetzal::format::newick;
// Interfacing Quetzal generator with non-quetzal tree types
std::predicate<Node> auto has_parent = [](Node const& n) { return n.parent; };
std::predicate<Node> auto has_children = [](Node const& n) { return n.left && n.right; };
// Random data is generated for the branch length
newick::Formattable<Node> auto branch_length = [](Node const&) /*-> std::string*/ { return "0.1"; };
// More sophisticated label formatting
newick::Formattable<Node> auto label = [](Node const& n) {
return std::string(1, n.data) + "[my[comment]]";
};
// Writes a root node branch length with a value of 0.0 and disable/remove nested comments
newick::generator generator(has_parent, has_children, label, branch_length, Flavor());
a.depth_first_search(generator.pre_order(), generator.in_order(), generator.post_order());
// We retrieve the formatted string
return generator.take_result();
}
//
// @brief Generate a Newick string from a k-ary tree with no properties attached to edges or vertices
//
std::string generate_from(quetzal::coalescence::k_ary_tree<> const& graph, auto flavor) {
using G = quetzal::coalescence::k_ary_tree<>;
using V = G::vertex_descriptor;
using E = G::edge_descriptor;
namespace newick = quetzal::format::newick;
// Data access
using P = std::function<bool(V)>;
using F = std::function<std::string(V)>;
P has_parent = [&graph](V v) { return graph.has_parent(v); };
P has_children = [&graph](V v) { return graph.has_children(v); };
F branch_length = [](V) { return "0.1"; };
F label = [](V v) {
std::string r = "a[my[comment]]";
r.front() += v;
return r;
};
// We declare a generator passing it the data interfaces
struct State {
newick::generator<V, P, P, F, F, decltype(flavor)> gen;
std::stack<int> nth_child;
} state{{has_parent, has_children, label, branch_length, flavor}, {}};
// We expose its interface to the boost DFS algorithm
struct VisWrap : boost::default_dfs_visitor {
State& state_;
VisWrap(State& ref) : state_(ref) {}
void discover_vertex(V v, G const&) const {
state_.nth_child.push(0);
state_.gen.pre_order()(v);
}
void finish_vertex(V v, G const&) const {
state_.gen.post_order()(v);
state_.nth_child.pop();
}
void tree_edge(E e, G const& g) const {
if (state_.nth_child.top()++ > 0)
state_.gen.in_order()(target(e, g));
}
} vis{state};
depth_first_search(graph, boost::visitor(vis));
return state.gen.take_result();
}
int main() {
std::string const legacy = legacy_implementation();
assert(legacy == "(b[my]:0.1,(d[my]:0.1,e[my]:0.1)c[my]:0.1)a[my]:0.0;");
// NOW WITH BGL GRAPHS
using G = quetzal::coalescence::k_ary_tree<>;
enum {a,b,c,d,e,N};
G tree(N);
add_edge(a, b, tree);
add_edge(a, c, tree);
add_edge(c, d, tree);
add_edge(c, e, tree);
// Generate the newick string
auto const bgl = generate_from(tree, Flavor());
std::cout << quoted(bgl) << "\n";
std::cout << quoted(legacy) << "\n";
std::cout << (bgl == legacy?"matching":"MISMATCH") << "\n";
}
Prints
"(b[my]:0.1,(d[my]:0.1,e[my]:0.1)c[my]:0.1)a[my]:0.0;"
"(b[my]:0.1,(d[my]:0.1,e[my]:0.1)c[my]:0.1)a[my]:0.0;"
matching