从Boost图中删除100,000多个节点

Question

我有一个图表(adjacency_list(listS,vecS,bidirectionalS,VertexVal)),我需要删除100,000多个节点.每个节点还包含2个64位整数和另一个64位整数的结构.下面代码中发生的guid检查是检查结构中的第一个整数.

根据VTune,在我的笔记本电脑(i7 2.7GHz,16GB RAM)上大约需要88秒.

以下是我删除节点的方法:

  vertex_iterator vi,vi_end;
  boost::tie(vi, vi_end) = boost::vertices(m_graph);
  while (vi!=vi_end) {
    if (m_graph[*vi].guid.part1 == 0) {
      boost::remove_vertex(*vi,m_graph);
      boost::tie(vi, vi_end) = boost::vertices(m_graph);
    } else 
      ++vi;
  }

Vtune显示boost :: remove_vertex()调用需要88.145秒.有没有更有效的方法来删除这些顶点？

Answer 1

在你的删除分支中你重新tie()获得迭代器:

boost::tie(vi, vi_end) = boost::vertices(m_graph);

这将导致每次重新启动循环时重新启动循环.这正是 Schlemiel The Painter.

我会发现你是否可以信任remove_vertex不会触发重新分配.如果是这样,它很容易修复.否则,您需要基于索引器的循环而不是基于迭代器的循环.或者你可能能够处理原始容器(虽然我记得这是一个私人成员).

更新使用vecS作为顶点的容器将导致糟糕的性能:

如果VertexList的模板参数adjacency_list是vecS,那么所有顶点描述符,边描述符,并为图形迭代器会被全部无效.<...> 如果需要经常使用该remove_vertex()函数,则listS选择器是VertexList模板参数的更好选择.

这个小基准test.cpp比较:

• 用-DSTABLE_IT(listS)

  $ ./stable 
  Generated 100000 vertices and 5000 edges in 14954ms
  The graph has a cycle? false
  starting selective removal...
  Done in 0ms
  After: 99032 vertices and 4916 edges
  

• 没有-DSTABLE_IT(vecS)

  $ ./unstable 
  Generated 100000 vertices and 5000 edges in 76ms
  The graph has a cycle? false
  starting selective removal...
  Done in 396ms
  After: 99032 vertices and 4916 edges
  

• 使用filtered_graph(感谢@cv_and_he评论)

  Generated 100000 vertices and 5000 edges in 15ms
  The graph has a cycle? false
  starting selective removal...
  Done in 0ms
  After: 99032 vertices and 4916 edges
  Done in 13ms
  

您可以清楚地看到删除速度要快得多,listS但生成速度要慢得多.

Answer 2

我能够使用 Boost 序列化例程成功地将图序列化为字符串，解析该字符串并删除不需要的节点，并对修改后的字符串进行反序列化。对于图中总共 200,000 个节点以及需要删除的 100,000 个节点，我能够在不到 2 秒的时间内成功完成操作。

对于我的特定用例，每个顶点都有 3 个 64 位整数。当需要删除时，我将其中 2 个整数标记为 0。有效的顶点永远不会有 0。当需要清理图形时 - 删除“已删除”的顶点，我遵循上述逻辑。

在下面的代码中，removeDeletedNodes() 执行字符串解析并删除顶点并映射边数。