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

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