Блог

При использовании boost::vecS для VertexList в списке смежности boost::depth_first_search(график, посетитель) компилируется и работает корректно. При переключении типа VertexList на boost::listS я получаю ошибку компилятора:

boost_1_65_0boostgraphdetailadjacency_list.hpp(2545): ошибка C2182: ‘const_reference’: незаконное использование типа ‘void

Из этой ошибки я бы сделал вывод, что boost::listS не является допустимым типом, однако проверки КОНЦЕПЦИИ BOOST проходят.

Если 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 MyGraphamp; g) const
  {
  }

  void finish_vertex(VertexType u,  const MyGraphamp; 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;
}

  

Во-первых, мне нравится, что вы включили проверки концепции. Трюк, изученный сегодня.

Реальный ответ прост: концепция ограничивает тип графика. Однако другие аргументы добавляют больше ограничений:

https://www.boost.org/doc/libs/1_69_0/libs/graph/doc/depth_first_search.html (выделено жирным шрифтом)

В: vertex_index_map(VertexIndexMap i_map)

Это сопоставляет каждую вершину целому числу в диапазоне [0, num_vertices(g)). Этот параметр необходим только тогда, когда используется карта свойств цвета по умолчанию. Тип VertexIndexMap должен быть моделью читаемой карты свойств. Тип значения map должен быть целочисленным типом. Тип дескриптора вершины графа должен использоваться в качестве ключевого типа карты.

По умолчанию: get(vertex_index, g). Примечание: если вы используете это значение по умолчанию, убедитесь, что ваш график имеет внутреннее свойство vertex_index. Например, adjacency_list с VertexList=listS не имеет внутреннего свойства 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 amp;) const {}
    void finish_vertex(VertexType, const MyGraph amp;) 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));
}