哪些 VertexList 类型对 depth_first_search 有效

Question

当在 adjacency_list boost::depth_first_search(Graph, Visitor) 中对 VertexList 使用 boost::vecS 时，编译和工作正常。将 VertexList 类型切换为 boost::listS 时，我收到编译器错误：

boost_1_65_0\boost\graph\detail\adjacency_list.hpp(2545): error C2182: 'const_reference': 非法使用类型 'void

从这个错误中，我了解到 boost::listS 不是有效类型，但是 BOOST CONCEPT 检查通过了。

如果 boost::listS 不是 depth_first_search 的有效类型，为什么？

下面是演示该问题的示例代码。从 vecS 切换到 listS 会产生上述错误。我正在使用 Visual Studio 2017 和 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

首先，我很高兴您包含了概念检查。今天学到的一个技巧。

真正的答案很简单：概念约束图形类型。但是，其他参数增加了更多限制：

https://www.boost.org/doc/libs/1_69_0/libs/graph/doc/depth_first_search.html （大胆的矿）

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.

换句话说，你的图表很好。但是你必须提供一个顶点索引。

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

仔细看的话，传个自定义色图也能满足。这有一个微小的优势，即不需要将所有元素初始化为默认初始化值：

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