c ++从图中移除顶点 [英] c++ remove vertex from a graph

问题描述

使用boost.1.46.1进行以下编译

  #include< boost / graph / adjacency_list.hpp> 
 
 struct Node {
 int id; 
}; 
 
结构边缘{
 int source; 
 int target; 
 int重量; 
}; 
 
 int main（）{
 / *一个像我们需要它的adjacency_list * / 
 typedef boost :: adjacency_list< 
 boost :: setS，//边缘容器
 boost :: listS，//顶点容器
 boost :: bidirectionalS，//有向图
 Node，Edge>图形; 
 
 typedef boost :: graph_traits< Graph> :: vertex_descriptor Vertex; 
 
图形gp1; 
 
 std :: cout<< 顶点数量1：<< boost :: num_vertices（gp1）<<的std :: ENDL; 
 Vertex v1 = boost :: add_vertex（gp1）; 
顶点v2 = boost :: add_vertex（gp1）; 
 
 std :: cout<< 顶点数2：<< boost :: num_vertices（gp1）<<的std :: ENDL; 
 
 gp1 [v1] .id = 3; 
 gp1 [v2] .id = 4; 
 
图表gp2（gp1）; 
 
 std :: cout<< 顶点数3：<< boost :: num_vertices（gp2）<<的std :: ENDL; 
 
 boost :: remove_vertex（v2，gp2）; 
 
 std :: cout<< 顶点数4：<< boost :: num_vertices（gp1）<<的std :: ENDL; 
 std :: cout<< 顶点数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<< 顶点数6：<< boost :: num_vertices（gp1）<<的std :: ENDL; 
 std :: cout<< 顶点数7：<< boost :: num_vertices（gp2）<<的std :: ENDL; 
 
返回0; 
 
  

gp2在删除时如何知道v2：boost :: remove_vertex （v2，gp2）
，为什么gp1的顶点数减少1？

为什么它在以下位置给出分段错误：boost： ：remove_vertex（* it，gp2）
，我该如何解决它？

解决方案

适用于具有VertexList = listS的图，特别是不适用于具有VertexList = vecS的图。还要注意，通常你不能存储顶点描述符或迭代器，并且稍后将它们删除，因为获取相关网站的相关信息： $ b

void remove_vertex（vertex_descriptor u，adjacency_list& amp; amp; amp; ; g）

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

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?

解决方案

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)). ...

这篇关于c ++从图中移除顶点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！