开发者

boost graph library memory consumption large graph

I have a large graph (30k vertices, 250m edges) and using boost graph librar开发者_StackOverflowy adjacency list (I tried both vecs and lists) consumes more than 25gb. since it is not very easy to get a pc with more than 16gb ram, what do you recommend to decrease memory usage ?


I've had the same problem with a verification technique using graphs I'm working on. If you will work with a huge amount of data (vertices and also edges) you should use a fine tuned data structure created by yourself.

If you have a lot of edges, you should consider using an Adjacency Matrix. The edges have weights, so you could use something like this:

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

You could use the optimized vector<vector<bool> > that uses only one bit to represent each edge, if the edges didn't have a property.

Although the adjacency matrix is fast when you want to check for an edge or add one, it's not good to iterate over edges.

I can say that, using the same properties in BGL and in my own graph, my graph is way smaller.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜