Выполните connected_components с Boost adjacency_list, где VertexList = listS

Question

Я использую Boost Graph Library в проекте, и она объявлена ​​как:

typedef adjacency_list <listS, listS, undirectedS, TrackInformation, LinkInformation> TracksConnectionGraph;

Все идет хорошо, пока я не вызову connected_components на моем графике.

typedef std::map<TracksConnectionGraph::vertex_descriptor, TracksConnectionGraph::vertices_size_type> component_type;
component_type component;
boost::associative_property_map< component_type > component_map(component);

int num_components = connected_components(tracks_connection_graph_, component_map);

Кажется, проблема в том, что если VertexList = listS, у меня нет vertex_index в качестве свойства моей вершины. Это заставляет connected_components выдавать мне ошибки, подобные тезисам:

/ USR / местные / включить / импульс-1_39 / усиление / property_map.hpp: В функции-члене 'R повышение :: iterator_property_map :: оператор [] (имяТип повышение :: property_traits :: key_type) const [with RandomAccessIterator = __gnu_cxx :: __ normal_iterator , IndexMap = boost :: adj_list_vertex_property_map, повышение :: подробнее :: error_property_not_found, Const повышение :: детали :: error_property_not_found и, boost :: vertex_index_t>, T = boost :: default_color_type, R = повышение :: default_color_type &] ':

Итак, вопрос: как мне добавить vertex_index в качестве свойства моих вершин?

Если я добавлю его, означает ли это, что всякий раз, когда я вызываю add_vertex, remove_vertex и т. Д., Я должен обновлять эту информацию для каждой вершины?

Answer 1

Вы можете добавить свойство vertex_index в определение типа вашего графа (в аргументе шаблона свойства вершины на adjacency_list измените TrackInformation на property<vertex_index_t, size_t, TrackInformation>).Перед вызовом алгоритма вам необходимо заполнить карту свойств с помощью цикла, такого как:

size_t index = 0;
BGL_FORALL_VERTICES(v, tracks_connection_graph_, TracksConnectionGraph) {
  put(vertex_index, g, v, index++);
}