从 Boost 图中删除 100,000 多个节点
我有一个图( adjacency_list (listS, vecS, bidirectionalS, VertexVal) )，我需要在其中删除 100,000 多个节点.每个节点还包含一个由 2 个 64 位整数和另一个 64 位整数组成的结构.下面代码中发生的 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.
在我的笔记本电脑(i7 2.7GHz，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 序列化例程成功将图形序列化为字符串，解析字符串并删除我不需要的节点并反序列化修改后的字符串.对于图中总共 200,000 个节点和需要删除的 100,000 个节点，我能够在不到 2 秒的时间内成功完成操作.
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 位整数.当需要删除时，我将这些整数中的 2 个标记为 0.一个有效的顶点永远不会有 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.
在下面的代码中，removeDeletedNodes() 执行字符串解析和移除顶点并映射边数.
In the code below removeDeletedNodes() does the string parsing and removing the vertices and mapping the edge numbers.
相关文章