Which VertexList types are valid for depth_first_search

Question

When using a boost::vecS for VertexList in the adjacency_list boost::depth_first_search(Graph, Visitor) compiles and works correctly. When switching the VertexList type to boost::listS I receive the compiler error:

boost_1_65_0\boost\graph\detail\adjacency_list.hpp(2545): error C2182: 'const_reference': illegal use of type 'void

From this error I would gather that the boost::listS is not a valid type, however the BOOST CONCEPT checks pass.

If boost::listS is not a valid type for depth_first_search, why?

Below is example code demonstrating the issue. Switching from vecS to listS generates the above error. I am using Visual Studio 2017 and boost 1.65.0

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/graph_concepts.hpp>


//typedef boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS> MyGraph;
typedef boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS> MyGraph;
using VertexType = boost::graph_traits<MyGraph>::vertex_descriptor;

BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<MyGraph>));
BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<MyGraph>));
class dfs_visitor : public boost::default_dfs_visitor
{

public:

  void discover_vertex(VertexType u,  const MyGraph& g) const
  {
  }

  void finish_vertex(VertexType u,  const MyGraph& g) const
  {
  }

};

BOOST_CONCEPT_ASSERT((boost::DFSVisitorConcept<dfs_visitor, MyGraph>));

int main()
{
  MyGraph g;
  dfs_visitor vis;
  boost::depth_first_search(g, boost::visitor(vis));
  return 0;
}

Answer 1

First off, I love that you included the concept checks. A trick learned today.

The real answer is simple: the concept constrains the graph type. However, the other arguments add more constraints:

https://www.boost.org/doc/libs/1_69_0/libs/graph/doc/depth_first_search.html (bold mine)

IN: vertex_index_map(VertexIndexMap i_map)

This maps each vertex to an integer in the range [0, num_vertices(g)). This parameter is only necessary when the default color property map is used. The type VertexIndexMap must be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.

Default: get(vertex_index, g). Note: if you use this default, make sure your graph has an internal vertex_index property. For example, adjacency_list with VertexList=listS does not have an internal vertex_index property.

In other words, your graph is FINE. But you have to supply a vertex index.

Live On Wandbox

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <numeric>

typedef boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS> MyGraph;
using VertexType = boost::graph_traits<MyGraph>::vertex_descriptor;

BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<MyGraph>));
BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<MyGraph>));

struct dfs_visitor : boost::default_dfs_visitor {
    void discover_vertex(VertexType, const MyGraph &) const {}
    void finish_vertex(VertexType, const MyGraph &) const {}
};

BOOST_CONCEPT_ASSERT((boost::DFSVisitorConcept<dfs_visitor, MyGraph>));

int main() {
    MyGraph g;
    dfs_visitor vis;
    std::map<MyGraph::vertex_descriptor, int> index;

    // fill index
    for (auto vd : boost::make_iterator_range(vertices(g))) {
        index.emplace(vd, index.size());
    }

    auto index_map = boost::make_assoc_property_map(index);
    boost::depth_first_search(g, boost::visitor(vis).vertex_index_map(index_map));
}

If you read closely, you can also satisfy it by passing a custom color map. This has the tiny advantage that there would be no need to initialize all elements to the default-initialized value:

Live On Wandbox

int main() {
    MyGraph g;
    dfs_visitor vis;
    std::map<MyGraph::vertex_descriptor, boost::default_color_type> colors;

    auto color_map = boost::make_assoc_property_map(colors);
    boost::depth_first_search(g, boost::visitor(vis).color_map(color_map));
}