Какие типы VertexList действительны для deep_first_search - PullRequest
Новая
       39

Какие типы VertexList действительны для deep_first_search

1 голос
/ 27 марта 2019

При использовании boost :: vecS для VertexList в adjacency_list boost :: deep_first_search (Graph, Visitor) компилируется и работает правильно.При переключении типа VertexList на boost :: listS я получаю сообщение об ошибке компилятора:

boost_1_65_0 \ boost \ graph \ detail \ adjacency_list.hpp (2545): ошибка C2182: «const_reference»: недопустимое использование типа «void»

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

Если boost :: listS не является допустимым типом для deep_first_search,почему?

Ниже приведен пример кода, демонстрирующий проблему.Переключение с vecS на listS вызывает вышеуказанную ошибку.Я использую Visual Studio 2017 и буст 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;
}

1 Ответ

0 голосов
/ 27 марта 2019

Прежде всего, мне нравится, что вы включили проверку концепции.Сегодня уловка.

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

https://www.boost.org/doc/libs/1_69_0/libs/graph/doc/depth_first_search.html (жирный шрифт)

IN : vertex_index_map(VertexIndexMap i_map)

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

По умолчанию: get (vertex_index, g).Примечание: если вы используете это значение по умолчанию, убедитесь, что ваш график имеет внутреннее свойство vertex_index.Например, adjacency_list с VertexList = listS не имеет внутреннего свойства vertex_index.

Другими словами, ваш график - FINE.Но вы должны указать индекс вершины.

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