boost图库内存消耗大图

Question

我有一个大图(30k 个顶点，250m 边)并且使用 boost 图库邻接列表(我尝试了 vecs 和列表)消耗超过 25GB。由于获得超过 16gb 内存的电脑并不容易，你有什么建议来减少内存使用？

Answer 1

我在使用我正在处理的图表的验证技术中遇到了同样的问题。
如果您将处理大量数据(顶点和边)，您应该使用自己创建的微调数据结构。

如果你有很多边，你应该考虑使用邻接矩阵。
边缘有权重，所以你可以使用这样的东西:

vector<int> vertices;
vector<vector<int> > edges;

您可以使用优化后的 vector<vector<bool> >如果边缘没有属性，则仅使用一位来表示每个边缘。

尽管当您想要检查边或添加一条边时，邻接矩阵很快，但迭代边并不好。

我可以说，在 BGL 和我自己的图中使用相同的属性，我的图要小得多。