C++如何从图中删除顶点

Question

以下内容使用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;
}

当使用"boost::remove_vertex(v2, gp2)"移除v2时，gp2是如何知道v2的存在的？为什么gp1的顶点数量会减少1个？

为什么在"boost::remove_vertex(*it, gp2)"处会出现分段错误，并且我该如何解决？

- Stephen

Answer 1

请注意，sehe的解决方案仅适用于VertexList=listS的图形，特别是不适用于VertexList=vecS的图形。此外，请注意，通常情况下，您不能存储顶点描述符或迭代器并稍后将它们删除，因为这会导致来自Boost Graph Library网站中所述的以下操作使得所有图形的顶点描述符、边描述符和迭代器都无效：

void remove_vertex(vertex_descriptor u, adjacency_list& g)

如果adjacency_list的VertexList模板参数是vecS，则该操作会使所有图形的顶点描述符、边描述符和迭代器无效。每个顶点的内置vertex_index_t属性被重新编号，以便在操作之后，顶点指数仍然形成一个连续的范围[0，num_vertices(g))。

- Gary R. Van Sickle

Answer 2

您正在迭代修改顶点集合。

先收集要删除的顶点，然后再删除它们。或者使用以下模式：

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

这个示例取自于这个页面：http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/adjacency_list.html（当您搜索remove vertices boost graph时，谷歌会返回此页面）

编辑

快速将其翻译成您的示例：

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

输出结果：

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

没有更多的崩溃了 :)

- sehe

---

好的，阅读文档后我理解了remove_vertex()的失效/稳定性问题，但我的第一个问题呢？当我将gp1复制到gp2时，“boost::remove_vertex(v2, gp2)”是如何工作的？为什么它会使gp1减少一个顶点？ - Stephen