c++ Boost图形库使用简单的顶点属性（字符串）写入graphviz格式

目标：

我想把一个Boost Graph封装到一个类中，这样我就有更多的控制权，减少main函数中的噪音，并打印一个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)));
    }

您的问题与显示bundle无关。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<>的接口不允许插入顶点，除非在最后。您目前没有显示删除顶点的接口。这意味着重新分配成本和稳定性都不是首选listS的原因。
如果必须使用基于节点的顶点容器选择器，则需要为需要它的算法添加索引：

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

现场演示

也将其付诸实践：

**第一个e第一个f第一个x

#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（你已经有了include for）requires it to create the default color map，你可以通过提供一个自定义的颜色Map表来解决这个问题，例如：

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

c++ Boost图形库使用简单的顶点属性（字符串）写入graphviz格式

目标：

问题

最小可重现示例

1条答案

变通方案？

现场演示

注解

相关问题

热门标签

最新问答