By default, breadth_first_search uses an std::vector<default_color_type> of size num_vertices(graph) to keep track of which vertices have already been visited. In an adjacency_list that uses VertexList=vecS this is totally fine, as in that case the vertex_descriptors are always from the continuous range [0, num_vertices(graph)). But the EnvireGraph uses VertexList=listS: After removing a vertex from the graph, the range of vertex_descriptors is not continuous anymore and there may exist vertices for which vertex_descriptor < num_vertices(graph) is violated -- hence the assertion failure described in #21.
One way to fix this is to provide a colormap that does not rely on continuous numbering of the vertices, e.g a std::map.
I'm not sure if this is the best choice, or if e.g. an std::unordered_map would yield better performance.
Also, there might be other places where breadth_first_search (or similar algorithms) are used incorrectly, I just cared to fix the error I encountered. :wink:
saarnold
commented
7 years ago
By default,
breadth_first_searchuses anstd::vector<default_color_type>of sizenum_vertices(graph)to keep track of which vertices have already been visited. In anadjacency_listthat usesVertexList=vecSthis is totally fine, as in that case thevertex_descriptorsare always from the continuous range[0, num_vertices(graph)). But the EnvireGraph usesVertexList=listS: After removing a vertex from the graph, the range ofvertex_descriptors is not continuous anymore and there may exist vertices for whichvertex_descriptor < num_vertices(graph)is violated -- hence the assertion failure described in #21.One way to fix this is to provide a colormap that does not rely on continuous numbering of the vertices, e.g a
std::map. I'm not sure if this is the best choice, or if e.g. anstd::unordered_mapwould yield better performance.Also, there might be other places where breadth_first_search (or similar algorithms) are used incorrectly, I just cared to fix the error I encountered. :wink:
See also: http://www.boost.org/doc/libs/1_64_0/libs/graph/doc/breadth_first_search.html Under "Named Parameters", the descriptions of
color_mapandvertex_index_mapare quite useful.