how to call "boost::remove_vertex" without re-indexing the vertices?

Question

I noticed that if I call boost::remove_vertex, the vertices are re-indexed to start from zero.

For example:

#include <boost/graph/adjacency_list.hpp>
#include <utility>
#include <algorithm>
#include <iterator>
#include <iostream>

int main()
{
  boost::adjacency_list<> g;

  boost::add_vertex(g);
  boost::add_vertex(g);
  boost::add_vertex(g);
  boost::add_vertex(g);

  boost::remove_vertex(0, g); // remove vertex 0

  std::pair<boost::adjacency_list<>::vertex_iterator,
            boost::adjacency_list<>::vertex_iterator> vs = boost::vertices(g);

  std::copy(vs.first, vs.second,
            std::ostream_iterator<boost::adjacency_list<>::vertex_descriptor>{
              std::cout, "\n"
                });
  // expects: 1, 2 and 3
  // actual: 0, 1 and 2, I suspect re-indexing happened.
}

I'm wondering how to make the above code outputs 1, 2 and 3?

Answer 1

The reason for the vertex index invalidation is the default for vertex container selector (VertexListS) of the adjacency_list template.

  template <class OutEdgeListS = vecS,
        class VertexListS = vecS,
        class DirectedS = directedS,
        ...
  class adjacency_list {};

When you invoke remove_vertex for adjacency_list which has VertexListS as vecS all iterators and descriptors for the graph are invalidated.

To avoid invalidating descriptors you can use listS instead vecS as VertexListS. If you use listS, you won't get an implicit vertex_index because the descriptor is not a suitable integral type. Instead for listS you will an opaque vertex descriptor type (that the implementation can translate back into a list element reference or iterator).

This is why you should use vertex_descriptor for referring to a vertex. So you can write

 typedef boost::adjacency_list<boost::vecS,boost::listS> graph;
 graph g;

 graph::vertex_descriptor desc1 = boost::add_vertex(g);
 boost::add_vertex(g);
 boost::add_vertex(g);
 boost::add_vertex(g);

 boost::remove_vertex(desc1, g);

 std::pair<graph::vertex_iterator,
        graph::vertex_iterator> vs = boost::vertices(g);

 std::copy(vs.first, vs.second,
        std::ostream_iterator<graph::vertex_descriptor>{
          std::cout, "\n"
            });