c++ remove vertex from a graph

Question

3he following compiles using boost.1.46.1

#include <boost/graph/adjacency_list.hpp>

struct Node {
  int id;
};

struct Edge {
  int source;
  int target;
  int weight;
};

int main() {
  /* an adjacency_list like we need it */
  typedef boost::adjacency_list<
    boost::setS, // edge container
    boost::listS, // vertex container
    boost::bidirectionalS, // directed graph
    Node, Edge> Graph;

  typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;

  Graph gp1;

  std::cout << "Number of vertices 1: " << boost::num_vertices(gp1) << std::endl;
  Vertex v1 = boost::add_vertex(gp1);
  Vertex v2 = boost::add_vertex(gp1);

  std::cout << "Number of vertices 2: " << boost::num_vertices(gp1) << std::endl;

  gp1[v1].id = 3;
  gp1[v2].id = 4;

  Graph gp2(gp1);

  std::cout << "Number of vertices 3: " << boost::num_vertices(gp2) << std::endl;

  boost::remove_vertex(v2, gp2);

  std::cout << "Number of vertices 4: " << boost::num_vertices(gp1) << std::endl;
  std::cout << "Number of vertices 5: " << boost::num_vertices(gp2) << std::endl;

  boost::graph_traits<Graph>::vertex_iterator it, end;
  for (boost::tie( it, end ) = vertices(gp2); it != end; ++it) {
    if ( gp2[*it].id == 3 ) {
      boost::remove_vertex(*it, gp2);
    }
  }

  std::cout << "Number of vertices 6: " << boost::num_vertices(gp1) << std::endl;
  std::cout << "Number of vertices 7: " << boost::num_vertices(gp2) << std::endl;

  return 0;
}

How does gp2 know about v2 when removing it at: "boost::remove_vertex(v2, gp2)" and why does the number of vertices of gp1 decrease by 1?

Why does it give a segmentation fault at: "boost::remove_vertex(*it, gp2)" and how can I fix it?

Answer 1

Note that sehe's solution only applies to graphs with a VertexList=listS, and in particular not to graphs with VertexList=vecS. Also note that in general you can't store either vertex descriptors or iterators and delete them later, because of this from the Boost Graph Library webiste:

void remove_vertex(vertex_descriptor u, adjacency_list& g)

... If the VertexList template parameter of the adjacency_list was vecS, then all vertex descriptors, edge descriptors, and iterators for the graph are invalidated by this operation. The builtin vertex_index_t property for each vertex is renumbered so that after the operation the vertex indices still form a contiguous range [0, num_vertices(g)). ...

Answer 2

You are modifying the vertex collection while iterating it.

Collect the vertices to be removed first, then remove them. Or use the followingpattern:

// Remove all the vertices. This is OK.
graph_traits<Graph>::vertex_iterator vi, vi_end, next;
tie(vi, vi_end) = vertices(G);
for (next = vi; vi != vi_end; vi = next) {
  ++next;
  remove_vertex(*vi, G);
}

Sample taken from this page: http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/adjacency_list.html (which is what google returns when you look for remove vertices boost graph)

Edit

Translated that quickly into your sample:

boost::graph_traits<Graph>::vertex_iterator vi, vi_end, next;
boost::tie(vi, vi_end) = vertices(gp2);
for (next = vi; vi != vi_end; vi = next) {
    ++next;
    if (gp2[*vi].id == 3)
        remove_vertex(*vi, gp2);
}

Output:

Number of vertices 1: 0
Number of vertices 2: 2
Number of vertices 3: 2
Number of vertices 4: 1
Number of vertices 5: 2
Number of vertices 6: 1
Number of vertices 7: 1

No more crashes :)