2

Objective:

I want to wrap a Boost Graph into a class on which I have a bit more control, reduce the noise in the main function, and print a graphviz format.

Problem

The code fails to compile, returning a include/boost/graph/detail/adjacency_list.hpp:2601:27: error: cannot form a reference to 'void'

Minimal reproducible example

The code compiles on Compiler Explorer https://godbolt.org/z/9beKovxc9 But if you uncomment the last line of main the error is reproduced.

// 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
}

What I can think of

  • I thought that (maybe) having a pure std::string as VertexProperties rather than a custom structure confuses the compiler. I tried to disambiguate with if constexpr, to use a default_writer if the VertexProperties type evaluated to no_property. But no success on this front, but here is the embarassingly naive code I wrote
    // 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)));
    }
sehe
  • 374,641
  • 47
  • 450
  • 633
WaterFox
  • 850
  • 6
  • 18

1 Answers1

1

Your problem has nothing to do with displaying the bundle. std::string and double are both output-streamable, so they will work fine.

Your problem is the classical one: you selected a graph model with no suitable implicit vertex index. This is due to the choice:

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

Note that, at least in general terms, the comment claim is pretty inaccurate. The sole reason to select listS is because

  • insert/erase can be more consistent time (but slower),
  • vertex descriptors and iterators can be stable (unless erased)

But for now, let's demonstrate that write_graphviz already works with vecS instead:

Live On Compiler Explorer

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

Prints

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

Workarounds?

I'd stick with vecS. The interface of Tree<> doesn't allow for inserting vertices except at the end. You currently don't show interface for removing vertices. This means that neither reallocation cost nor stability are reasons for preferring listS.

If you must use a node-based vertex container selector, you're responsible for adding an index for the algorithms that require it:

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

Live Demo

Putting that in action as well:

Live On Compiler Explorer

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

Prints

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

Notes

Note that most algorithms require the vertex index. E.g. breadth_first_search (which you already have the include for) requires it to create the default color map. You can get around it by supplying a custom color map instead for that particular example, examples:

sehe
  • 374,641
  • 47
  • 450
  • 633
  • 1
    Omg I would never have found the problem was with `listS`! Concerning the inacurate statement, it comes from a (naive) reading of the documentation: `The std::list has a higher per-vertex space overhead than the std::vector, storing three extra pointers per vertex.`. Well thank you SO much! – WaterFox Dec 10 '22 at 19:08
  • 1
    Yeah, storage efficiency is *also* a factor, but not the only one :) It *is* possible to create access patterns that will be faster with `listS`, as well. They'd be unusual (and impossible for the interface shown), but not impossible. Always let the profiler guide you. – sehe Dec 10 '22 at 21:06