从升压图中删除100,000+节点 [英] Remove 100,000+ nodes from a Boost graph

问题描述

我有一个图（的adjacency_list（列表，血管内皮细胞，bidirectionalS，VertexVal））中，我需要删除100,000节点。每个节点还包含第2 64位的整数的结构和其他64位整数。这种情况下code的GUID检查是检查结构中的第一个整数。

I have a graph ( adjacency_list (listS, vecS, bidirectionalS, VertexVal) ) in which I need to delete 100,000+ nodes. Each node also contains a structure of 2 64-bit integers and another 64-bit integer. The guid check that happens in the code below is checking 1st integer in the structure.

在我的笔记本电脑（2.7GHz的酷睿i7，16GB RAM），它根据需要VTune™可视化约88秒。

On my laptop ( i7 2.7GHz, 16GB RAM ) it takes about 88 seconds according to VTune.

以下是我如何删除节点：

Following is how I delete the nodes:

  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秒。有没有办法删除这些顶点的更有效的方法？

Vtune shows that the boost::remove_vertex() call takes 88.145 seconds. Is there a more efficient way to delete these vertices?

推荐答案

我能够使用Boost的序列化程序转换成字符串成功序列图，解析字符串并删除我不需要节点和反序列化修改后的字符串。对于图形和需要被删除我能够顺利完成，在不到2秒操作200000总节点100,000。

I was able to successfully serialize the graph using Boost serialization routines into a string, parse the string and remove the nodes I didn't need and de-serialize the modified string. For 200,000 total nodes in graph and 100,000 that needs to be deleted I was able to successfully finish the operation in less than 2 seconds.

有关我的具体使用情况每个顶点有3个64位整数。当它需要被删除，我标记那些整数作为0的2。一个有效的顶点将永远不会有一个0。当点来清理图形 - 删除已删除的顶点，我按照上面的逻辑

For my particular use-case each vertex has 3 64bit integers. When it needs to be deleted, I mark 2 of those integers as 0s. A valid vertex would never have a 0. When the point comes to clean up the graph - to delete the "deleted" vertices, I follow the above logic.

在code以下removeDeletedNodes（）进行字符串解析和删除顶点和绘制边缘号码。

In the code below removeDeletedNodes() does the string parsing and removing the vertices and mapping the edge numbers.

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