我想重用在
this offline header中定义的
bidirectional_binary_tree类的一些实现。此类不管理我需要的属性。
为此我定义了一个偏特化
binary_tree<Vertex=boost::no_property,Edge=boost::no_property>bidirectional_binary_tree我的想法是将这个类提供给解析工具，这样我就可以写类似的东西
auto [tree,root] = quetzal::get_random_binary_tree<>(5, rng);
using Flavor = quetzal::format::newick::TreeAlign;
auto s = quetzal::format::newick::generate_from(tree, Flavor());
binary_treeboost::adjacency_list我遇到一个
no type named 'type' in 'boost::no_property'error: no type named 'type' in 'boost::no_property'
typedef typename f_::type type;
~~~~~~~~~~~~~^~~~
/Users/arnaudbecheler/.conan/data/boost/1.79.0/_/_/package/f176d793a4209b0ad6faa2430140a1edfe7c4446/include/boost/graph/graph_traits.hpp:316:3: note: in instantiation of template class 'boost::mpl::eval_if<boost::detail::has_vertex_property_type<quetzal::coalescence::binary_tree<boost::no_property, boost::no_property>>, boost::detail::get_vertex_property_type<quetzal::coalescence::binary_tree<boost::no_property, boost::no_property>>, boost::no_property>' requested here
: boost::mpl::eval_if< detail::has_vertex_property_type< G >,
^
复制：我将尝试将许多文件总结为一个可重现的示例。与此同时，有问题的代码可以在这里找到文件
example/newick_generator_1.cppaccumulator2c056c2我在上面添加的代码如下（它可以用 CRTP 简化，但那是在我让它工作之后）：
namespace quetzal::coalescence
{
namespace detail
{
template<class... Types>
struct count {
static const std::size_t value = sizeof...(Types);
};
template <typename T1, typename... Ts>
std::tuple<Ts...> unshift_tuple(const std::tuple<T1, Ts...>& tuple)
{
return std::apply([](auto&&, const auto&... args) {return std::tie(args...);}, tuple);
}
template<typename Graph, typename VertexProperty>
struct VertexManager
{
using vertex_descriptor = typename Graph::vertex_descriptor;
using vertex_hashmap_type = std::map<vertex_descriptor, VertexProperty>;
vertex_hashmap_type _vertex_property_hashmap;
boost::associative_property_map< vertex_hashmap_type > _vertex_property_map { _vertex_property_hashmap };
template<typename... Args>
vertex_descriptor add_vertex_to_manager(Graph &g, Args&&... args)
{
vertex_descriptor key = add_vertex(g);
VertexProperty value = { std::forward<Args>(args)...};
put(_vertex_property_map, key, value);
return key;
}
const VertexProperty& operator [](vertex_descriptor v) const
{
return get(_vertex_property_map, v);
}
VertexProperty & operator [](vertex_descriptor v)
{
return _vertex_property_map[v];
}
};
template<typename Graph, typename EdgeProperty>
struct EdgeManager
{
using vertex_descriptor = typename Graph::vertex_descriptor;
using edge_descriptor = typename Graph::edge_descriptor;
using edge_hashmap_type = std::map<edge_descriptor, EdgeProperty>;
edge_hashmap_type _edge_property_hashmap;
boost::associative_property_map< edge_hashmap_type > _edge_property_map { _edge_property_hashmap };
template<typename... Args>
std::pair<edge_descriptor,edge_descriptor>
add_children(Graph &g,
vertex_descriptor parent,
std::tuple<vertex_descriptor, Args...> left,
std::tuple<vertex_descriptor, Args...> right)
{
assert(parent != get<0>(left));
assert(parent != get<0>(right));
assert(get<0>(left) != get<0>(right));
std::pair<vertex_descriptor,vertex_descriptor> left_edge = add_left_edge(parent, get<0>(left), g);
std::pair<vertex_descriptor,vertex_descriptor> right_edge = add_right_edge(parent, get<0>(right), g);
auto p1 = std::apply([](Args&&... ts){ return EdgeProperty { std::forward<Args>(ts)... }; }, detail::unshift_tuple(left));
auto p2 = std::apply([](Args&&... ts){ return EdgeProperty { std::forward<Args>(ts)... }; }, detail::unshift_tuple(right));
put(_edge_property_map, left_edge, p1);
put(_edge_property_map, right_edge, p2);
return {left_edge, right_edge};
}
const EdgeProperty& operator [](const std::pair<vertex_descriptor,vertex_descriptor>& edge) const
{
return get(_edge_property_map, edge);
}
EdgeProperty & operator [](const std::pair<vertex_descriptor,vertex_descriptor>& edge)
{
return _edge_property_map[edge];
}
};
}
/// @brief A binary tree class
/// @remarks Primary template for partial specialization
template<class VertexProperty, class EdgeProperty>
class binary_tree {};
/// @brief A binary tree class
/// @remarks Explicit (full) specialization where there is no property attached to either vertices nor edges.
template<>
class binary_tree<boost::no_property, boost::no_property> :
public boost::bidirectional_binary_tree<>
{
private:
using self_type = binary_tree<boost::no_property, boost::no_property>;
using base = boost::bidirectional_binary_tree<>;
public:
using edge_properties = boost::no_property;
using vertex_properties = boost::no_property;
/// @brief Inheriting constructors
using base::base;
/// @brief Edge descriptor
using edge_descriptor = typename base::edge_descriptor;
/// @brief Vertex descriptor
using vertex_descriptor = typename base::vertex_descriptor;
/// @brief degree size type
using degree_size_type = typename base::degree_size_type;
/// @brief Add a vertex to the graph
friend
vertex_descriptor add_vertex(self_type &g)
{
return g.add_vertex();
}
/// @brief Add edges between the parent vertex and the two children.
friend
std::pair<edge_descriptor,edge_descriptor>
add_children(
self_type &g,
vertex_descriptor parent,
vertex_descriptor left,
vertex_descriptor right)
{
assert(parent != left);
assert(parent != right);
assert(left != right);
std::pair<vertex_descriptor,vertex_descriptor> left_edge = g.add_left_edge(parent, left);
std::pair<vertex_descriptor,vertex_descriptor> right_edge = g.add_right_edge(parent, right);
return {left_edge, right_edge};
}
};
/// @brief A binary tree class
/// @remarks Partial specialization where there is no edge property attached
template<class VertexProperty>
requires (!std::is_same_v<VertexProperty, boost::no_property>)
class binary_tree<VertexProperty, boost::no_property> :
public boost::bidirectional_binary_tree<>
{
private:
using self_type = binary_tree<VertexProperty, boost::no_property>;
using base = boost::bidirectional_binary_tree<>;
detail::VertexManager<self_type, VertexProperty> _vertex_manager;
public:
/// @brief Inheriting constructors
using base::base;
/// @brief Edge descriptor
using edge_descriptor = typename base::edge_descriptor;
/// @brief Vertex descriptor
using vertex_descriptor = typename base::vertex_descriptor;
/// @brief degree size type
using degree_size_type = typename base::degree_size_type;
/// @brief Add a vertex to the graph
template<typename... Args>
requires ( detail::count<Args...>::value != 0U )
friend
vertex_descriptor add_vertex(self_type &g, Args&&... args)
{
return g._vertex_manager.add_vertex_to_manager(g, std::forward<Args>(args)...);
}
/// @brief Add edges between the parent vertex and the two children.
friend
std::pair<edge_descriptor,edge_descriptor>
add_children(
self_type &g,
vertex_descriptor parent,
vertex_descriptor left,
vertex_descriptor right)
{
assert(parent != left);
assert(parent != right);
assert(left != right);
std::pair<vertex_descriptor,vertex_descriptor> left_edge = g.add_left_edge(parent, left);
std::pair<vertex_descriptor,vertex_descriptor> right_edge = g.add_right_edge(parent, right);
return {left_edge, right_edge};
}
const VertexProperty& operator [](vertex_descriptor vertex) const
{
return _vertex_manager[vertex];
}
VertexProperty & operator [](vertex_descriptor vertex)
{
return _vertex_manager[vertex];
}
};
/// @brief A binary tree class
/// @remarks Partial specialization where there is no vertex property attached
template<class EdgeProperty>
requires (!std::is_same_v<EdgeProperty, boost::no_property>)
class binary_tree<boost::no_property, EdgeProperty> :
public boost::bidirectional_binary_tree<>
{
private:
using self_type = binary_tree<boost::no_property, EdgeProperty>;
using base = boost::bidirectional_binary_tree<>;
detail::EdgeManager<self_type, EdgeProperty> _edge_manager;
public:
/// @brief Inheriting constructors
using base::base;
/// @brief Edge descriptor
using edge_descriptor = typename base::edge_descriptor;
/// @brief Vertex descriptor
using vertex_descriptor = typename base::vertex_descriptor;
/// @brief degree size type
using degree_size_type = typename base::degree_size_type;
friend
vertex_descriptor add_vertex(self_type &g)
{
return g.add_vertex();
}
/// @brief Add edges between the parent vertex and the two children.
template<typename... Args>
friend
std::pair<edge_descriptor,edge_descriptor>
add_children(self_type &g,
vertex_descriptor parent,
std::tuple<vertex_descriptor, Args...> left,
std::tuple<vertex_descriptor, Args...> right)
{
return g._edge_manager.add_children(g, parent, left, right);
}
const EdgeProperty& operator [](const std::pair<vertex_descriptor, vertex_descriptor>& edge) const
{
return _edge_manager[edge];
}
EdgeProperty & operator [](const std::pair<vertex_descriptor, vertex_descriptor>& edge)
{
return _edge_manager[edge];
}
};
/// @brief A binary tree class
/// @remarks Partial specialization where there is no vertex property attached
template<class VertexProperty, class EdgeProperty>
requires (!std::is_same_v<VertexProperty, boost::no_property> && !std::is_same_v<VertexProperty, boost::no_property>)
class binary_tree<VertexProperty, EdgeProperty> :
public boost::bidirectional_binary_tree<>
{
private:
using self_type = binary_tree<VertexProperty, EdgeProperty>;
using base = boost::bidirectional_binary_tree<>;
detail::EdgeManager<self_type, EdgeProperty> _edge_manager;
detail::VertexManager<self_type, VertexProperty> _vertex_manager;
public:
/// @brief Inheriting constructors
using base::base;
/// @brief Edge descriptor
using edge_descriptor = typename base::edge_descriptor;
/// @brief Vertex descriptor
using vertex_descriptor = typename base::vertex_descriptor;
/// @brief degree size type
using degree_size_type = typename base::degree_size_type;
/// @brief Add a vertex to the graph
/// @brief Add a vertex to the graph
template<typename... Args>
requires ( detail::count<Args...>::value != 0U )
friend
vertex_descriptor add_vertex(self_type &g, Args&&... args)
{
return g._vertex_manager.add_vertex_to_manager(g, std::forward<Args>(args)...);
}
/// @brief Add edges between the parent vertex and the two children.
template<typename... Args>
friend
std::pair<edge_descriptor,edge_descriptor>
add_children(self_type &g,
vertex_descriptor parent,
std::tuple<vertex_descriptor, Args...> left,
std::tuple<vertex_descriptor, Args...> right)
{
return g._edge_manager.add_children(g, parent, left, right);
}
const VertexProperty& operator [](vertex_descriptor v) const
{
return _vertex_manager[v];
}
VertexProperty & operator [](vertex_descriptor v)
{
return _vertex_manager[v];
}
const EdgeProperty& operator [](const std::pair<vertex_descriptor, vertex_descriptor>& edge) const
{
return _edge_manager[edge];
}
EdgeProperty & operator [](const std::pair<vertex_descriptor, vertex_descriptor>& edge)
{
return _edge_manager[edge];
}
};
}
算法如下：
std::string generate_from(boost::bidirectional_binary_tree<> const& graph, auto flavor) {
using Graph = boost::bidirectional_binary_tree<>;
using Node = Graph::vertex_descriptor;
namespace newick = quetzal::format::newick;
// Data access
std::predicate<Node> auto has_parent = [&graph](Node const& v) { return has_predecessor(v,graph); };
std::predicate<Node> auto has_children = [&graph](Node v) { return static_cast<bool>(out_degree(v, graph)); };
newick::Formattable<Node> auto branch_length = [](Node) { return ""; };
newick::Formattable<Node> auto label = [](Node v) { return ""; };
// We declare a generator passing it the data interfaces
newick::generator gen{has_parent, has_children, label, branch_length, flavor};
using Gen = decltype(gen);
using Stack = std::stack<int>;
Stack nth_child;
// We expose its interface to the boost DFS algorithm
struct VisWrap : boost::default_dfs_visitor {
Gen& gen_;
Stack& stack_;
VisWrap(Gen& gen, Stack& s) : gen_(gen), stack_(s) {}
void discover_vertex(Node v, Graph const&) const {
stack_.push(0);
gen_.pre_order()(v);
}
void finish_vertex(Node v, Graph const&) const {
gen_.post_order()(v);
stack_.pop();
}
void tree_edge(Graph::edge_descriptor e, Graph const& g) const {
if (stack_.top()++ > 0)
gen_.in_order()();
}
} vis{gen, nth_child};
depth_first_search(graph, boost::visitor(vis));
return gen.take_result();
}
我怀疑问题是因为我没有在我的 binary_tree 类中实现
PropertyGraph的概念：在越野车的情况下它不存在，但在工作情况下它隐式继承自
adjacency_list