如何将自定义DFS代码与Boost Graph DFS进行接口对接？

背景 #

我已经为树结构定义了格式化操作，这些操作作为前序/中序/后序运算符使用时表现良好，对应的节点结构和DFS实现如下（同样适用于k叉树）：

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);
  }
};

我可以通过以下方式格式化该树结构：

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();

目标 #

由于这套格式化操作表现出色，我希望复用相同的函子，对基于Boost图实现的树结构进行格式化。我正尝试让以下（存在bug的示例）代码生效：

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);
  }
};

从而能通过类似下面的语法完成树的格式化：

Formatter formatter(my_config);
my_visitor vis(formatter);
depth_first_search(graph, root, boost::visitor(vis));
auto s = formatter.take_result();

代码 #

当前代码可编译运行，但主函数中最后一个调用的方法尚未实现，我不清楚该如何定义它：

auto s = newick::generate_from(tree);

我有一个该函数的注释草稿，但难以将其适配到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));
}

问题 #

我始终理不清接口一致性问题，也找不到问题根源：

• 我定义的前序/中序/后序操作是仅接受1个具有Node语义参数的可调用对象（该参数同时封装了节点标识符及其所属的图）
• 但BGL定义的访问器方法签名异构，需要接受vertex+graph或edge+graph参数
• 我也不确定如何将前序/中序/后序操作映射到BGL访问器的复杂接口。我猜测pre-order对应discover_vertex，in_order对应examine_edge，post_order对应finish_vertex，但不确定是否正确。

是否存在协调这两个接口的方法，还是二者语义差异过大，必须复制或修改格式化语法？

内容的提问来源于stack exchange，提问作者WaterFox