Boost Graph Library编写具有简单顶点属性(字符串)的graphviz格式

Question

目标：

我想把Boost Graph封装到一个类中，在这个类上我有更多的控制权，减少主函数中的噪声，并打印一个graphviz格式。

问题

代码编译失败，返回include/boost/graph/detail/adjacency_list.hpp:2601:27: error: cannot form a reference to 'void'

最小可重复示例

代码在编译器资源管理器上编译https://godbolt.org/z/9beKovxc9但如果取消注释main的最后一行，则会重现错误。

// BGL
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/graphviz.hpp>
#include <iostream>                // std::cout
#include <functional>              // std::function
#include <utility>                 // std::pair
///
/// @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 implementation = 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 are prioritizing speed for space
///
using vertex_list_type = boost::listS;
///
/// @brief Coalescent trees are directed acyclic graphs
///
using directed_type = boost::directedS ;
}; // end tree_traits
///
/// @brief A graph with properties suited to represent a coalescent tree
///
template<class VertexProperties=boost::no_property, class EdgeProperties=boost::no_property>
class Tree
{
public:
///
/// @brief Properties of an edge, like the demes visited
/// @see https://www.boost.org/doc/libs/1_80_0/libs/graph/doc/bundles.html
///
using edge_properties = EdgeProperties;
///
/// @brief Properties of a vertex, like the mutational state
/// @see https://www.boost.org/doc/libs/1_80_0/libs/graph/doc/bundles.html
///
using vertex_properties = VertexProperties;
///
/// @brief The type of graph hold by the tree class
///
using graph_type = tree_traits::implementation
<
tree_traits::out_edge_list_type,
tree_traits::vertex_list_type,
tree_traits::directed_type,
VertexProperties,
EdgeProperties
>;
private:
graph_type _graph;
static constexpr bool vertex_prop_undefined = std::is_same<vertex_properties,boost::no_property>::value;
static constexpr bool edge_prop_undefined = std::is_same<edge_properties,boost::no_property>::value;

public:
/// @note adds an object-oriented layer
auto add_vertex(auto&&... args)
{
return boost::add_vertex(std::forward<decltype(args)>(args)..., _graph);
}

/// @note adds an object-oriented layer
/// @note order of vertices determines edge orientation
auto add_edge(auto&&... args)
{
return boost::add_edge(std::forward<decltype(args)>(args)..., _graph);
}

void to_graphviz(std::ostream& out) const
{
using namespace boost;
return boost::write_graphviz(out, _graph,
boost::make_label_writer(boost::get(vertex_bundle, this->_graph)),
boost::make_label_writer(boost::get(edge_bundle, this->_graph))
);
}
};

int main()
{
using q_tree_type = Tree<std::string, double>;
q_tree_type graph;

// We insert the root of tree
auto root = graph.add_vertex("first");
//graph.to_graphviz(std::cout); // <--- huho
}

我能想到什么

• 我认为(可能)将纯std::string作为VertexProperties而不是自定义结构会混淆编译器。我试图用if constexpr来消除歧义，如果VertexProperties类型的求值结果为no_property，则使用default_writer。但在这方面没有成功，但这是我写的令人尴尬的天真代码

// member of Tree<...> class
void to_graphviz(std::ostream& out) const
{
using namespace boost;

if constexpr (vertex_prop_undefined)
{
if constexpr (edge_prop_undefined)
return write_graphviz(out, _graph);

return boost::write_graphviz(out, _graph, default_writer(), boost::make_label_writer(boost::get(edge_bundle, this->_graph)));
}
if constexpr (edge_prop_undefined)
return write_graphviz(out, _graph, boost::make_label_writer(boost::get(vertex_bundle, this->_graph)));

return boost::write_graphviz(out, _graph, boost::make_label_writer(boost::get(vertex_bundle, this->_graph)), boost::make_label_writer(boost::get(edge_bundle, this->_graph)));
}

Answer 1

您的问题与显示捆绑包无关。std::string和double都是可流式输出的，所以它们可以正常工作。

你的问题是经典的：你选择了一个没有合适的隐式顶点索引的图模型。这是由于选择：

///
/// @brief We are prioritizing speed for space
///
using vertex_list_type = boost::listS;

请注意，至少在一般情况下，评论声明是相当不错的不准确。选择listS的唯一原因是

• 插入/擦除可以是更一致的时间(但更慢)
• 顶点描述符和迭代器可以是稳定的(除非删除)

但现在，让我们证明write_graphviz已经与vecS一起工作了：

实时编译器资源管理器

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <iostream>
struct tree_traits {
template <class... Types> using model = boost::adjacency_list<Types...>;
using out_edge_list_type              = boost::setS;
using vertex_list_type                = boost::vecS; // listS;
using directed_type                   = boost::directedS;
};
template <class VertexProperties = boost::no_property,
class EdgeProperties   = boost::no_property>
struct Tree {
using edge_properties   = EdgeProperties;   // like the demes visited
using vertex_properties = VertexProperties; // like the mutational state
using graph_type =
tree_traits::model<tree_traits::out_edge_list_type, tree_traits::vertex_list_type,
tree_traits::directed_type, VertexProperties, EdgeProperties>;
private:
graph_type _graph;
static constexpr bool vertex_prop_undefined = std::is_same_v<vertex_properties, boost::no_property>;
static constexpr bool edge_prop_undefined = std::is_same_v<edge_properties, boost::no_property>;
public:
/// @note adds an object-oriented layer
auto add_vertex(auto&&... args) {
return boost::add_vertex(std::forward<decltype(args)>(args)..., _graph);
}
/// @note adds an object-oriented layer
/// @note order of vertices determines edge orientation
auto add_edge(auto&&... args) {
return boost::add_edge(std::forward<decltype(args)>(args)..., _graph);
}
void to_graphviz(std::ostream& out) const {
using namespace boost;
return boost::write_graphviz(
out, _graph,
boost::make_label_writer(boost::get(vertex_bundle, this->_graph)),
boost::make_label_writer(boost::get(edge_bundle, this->_graph)));
}
};
int main() {
using q_tree_type = Tree<std::string, double>;
q_tree_type tree;
auto first  = tree.add_vertex("first");
auto second = tree.add_vertex("second");
auto third  = tree.add_vertex("second");
tree.add_edge(first, second, 444.4);
tree.add_edge(first, third, 555.5);
tree.to_graphviz(std::cout);
}

打印

digraph G {
0[label=first];
1[label=second];
2[label=second];
0->1 [label=444.39999999999998];
0->2 [label=555.5];
}

解决方法

我会坚持vecS。Tree<>的接口不允许插入顶点，除非在末端。您当前不显示用于删除顶点的界面。这意味着重新分配成本和稳定性都不是偏好CCD_ 15的原因。

如果必须使用基于节点的顶点容器选择器，则需要为需要它的算法添加索引：

void to_graphviz(std::ostream& out) const {
boost::container::flat_map<typename graph_type::vertex_descriptor, size_t> index;
index.reserve(num_vertices(_graph));
// OR just: std::map<typename graph_type::vertex_descriptor, size_t> index;
for (size_t i = 0; auto v : boost::make_iterator_range(vertices(_graph)))
index[v] = i++;
return write_graphviz(                                    //
out, _graph,                                          //
make_label_writer(get(boost::vertex_bundle, _graph)), //
make_label_writer(get(boost::edge_bundle, _graph)),   //
boost::default_writer{},                              //
boost::make_assoc_property_map(index));
}

现场演示

将其付诸行动：

实时编译器资源管理器

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <iostream>
#include <numeric>
#include <boost/container/flat_map.hpp>
#include <boost/property_map/property_map.hpp>
struct tree_traits {
template <class... Types> using model = boost::adjacency_list<Types...>;
using out_edge_list_type              = boost::setS;
using vertex_list_type                = boost::listS;
using directed_type                   = boost::directedS;
};
template <class VertexProperties = boost::no_property,
class EdgeProperties   = boost::no_property>
struct Tree {
using edge_properties   = EdgeProperties;   // like the demes visited
using vertex_properties = VertexProperties; // like the mutational state
using graph_type =
tree_traits::model<tree_traits::out_edge_list_type, tree_traits::vertex_list_type,
tree_traits::directed_type, VertexProperties, EdgeProperties>;
private:
graph_type _graph;
static constexpr bool vertex_prop_undefined = std::is_same_v<vertex_properties, boost::no_property>;
static constexpr bool edge_prop_undefined = std::is_same_v<edge_properties, boost::no_property>;
public:
/// @note adds an object-oriented layer
auto add_vertex(auto&&... args) {
return boost::add_vertex(std::forward<decltype(args)>(args)..., _graph);
}
/// @note adds an object-oriented layer
/// @note order of vertices determines edge orientation
auto add_edge(auto&&... args) {
return boost::add_edge(std::forward<decltype(args)>(args)..., _graph);
}
void to_graphviz(std::ostream& out) const {
boost::container::flat_map<typename graph_type::vertex_descriptor, size_t> index;
index.reserve(num_vertices(_graph));
// OR just: std::map<typename graph_type::vertex_descriptor, size_t> index;
for (size_t i = 0; auto v : boost::make_iterator_range(vertices(_graph)))
index[v] = i++;
return write_graphviz(                                    //
out, _graph,                                          //
make_label_writer(get(boost::vertex_bundle, _graph)), //
make_label_writer(get(boost::edge_bundle, _graph)),   //
boost::default_writer{},                              //
boost::make_assoc_property_map(index));
}
};
int main() {
using q_tree_type = Tree<std::string, double>;
q_tree_type tree;
auto first  = tree.add_vertex("first");
auto second = tree.add_vertex("second");
auto third  = tree.add_vertex("second");
tree.add_edge(first, second, 444.4);
tree.add_edge(first, third, 555.5);
tree.to_graphviz(std::cout);
}

打印

digraph G {
0[label=first];
1[label=second];
2[label=second];
0->1 [label=444.39999999999998];
0->2 [label=555.5];
}

备注

请注意，大多数算法都需要顶点索引。例如，breadth_first_search(您已经为其包含)要求它创建默认的颜色映射。你可以通过提供一个自定义的颜色图来解决这个问题，例如：

• https://stackoverflow.com/questions/71540438/how-to-use-boost-graph-algorithm-on-a-named-graph/71543159#71543159:~：text=通过%20Your%20Own%20Color%20Map
• 自定义BGL图使用拓扑排序需要什么