降低邻接表的内存需求

BGL中有一种鲜为人知的图类型,称为“压缩稀疏行”图。它似乎很新,没有从索引页面链接。然而,它确实采用了一个漂亮的小技巧来使图形表示尽可能小。 http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/compressed_sparse_row.html

对于我们的一些图表,我已经能够将总内存使用量减少20%,因此这确实是一个非常值得的优化。

它还将顶点/边属性存储在向量中,从而为这些属性提供尽可能小的开销。

请注意,随最新boost 1.40附带的版本仅支持方向图(而不是双向图)。如果你需要能够有效地迭代vertice的外边缘和内边缘(就像我一样),你需要从subversion中检查boost主干。Jeremiah在我的要求下添加了这个功能,非常有帮助。

1. 开销取决于您使用的版本以及您是否选择了“捆绑”属性。我只使用了捆绑属性,阅读代码后,我预计每个属性捆绑都会花费2个指针+sizeof你正在使用的捆绑类型+sizeof每个附加属性。二进制afaik中没有留下任何概念检查内容。既然你有代码,为什么不直接衡量成本呢?如果你没有任何工具来帮助你,试着在已知大小的缓冲区中生成已知大小的图形。有些事情最终会失败,在那一点上你应该有计数。

2. 你试过打电话吗 adjacency_list<blah>.swap(adjacency_list& x)

3. ???

我开始编写类似你描述的系统,但最终放弃了BGL,转而编写自己的算法,在所有链接器符号的sqlite数据库上运行。

由于BGL旨在 interoperate with legacy or custom graphs ,你最好自己写图表。

作为对以下问题的回答:

3) 是否可以将增强池分配器与BGL一起使用?据我所知,BGL目前执行了大量的小分配——出于空间和运行时效率的原因,我真的很想避免这种情况。

here :

 template <class Allocator>
  struct list_with_allocatorS { };

  namespace boost {
    template <class Alloc, class ValueType>
    struct container_gen<list_with_allocatorS<Alloc>, ValueType>
    {
      typedef typename Alloc::template rebind<ValueType>::other Allocator;
      typedef std::list<ValueType, Allocator> type;
    };
  }

  // now you can define a graph using std::list 
  //   and a specific allocator  
  typedef adjacency_list< list_with_allocatorS< std::allocator<int> >, vecS, directedS> MyGraph;