Statically allocating boost Graph

Question

Dear all this is quite easy, I hope!

I have a graph, which I'd like to allocate statically. I know I will have N nodes, and at most K << N edges for each node (for instance, N = 1,000,000 and K = 3). It would be convenient if I could initialize not only a graph with a certain number of nodes, but also with a predefined number of edges.

Do you know if this is possible?

If not, would you recommend ditching the adjacency matrix for adjacency lists? I'll be having a huge number of edges, that's why a static allocation would be great.

Cheers!

Answer 1

Boost.Graph has Compressed Sparse Row Graph which does something close to what you want. It is very memory friendly. As with other Boost graphs you can declare it directed, undirected, etc. and associate properties with its elements.

As a caveat, this graph is immutable, meaning you can create and populate it but not update later. You need to have all your edges ready when you generate the graph. See similar SO topic here

Answer 2

I did not test it, but considering enum { A, B, C, D, E, F, N }; means that A = 0, B = 1, ..., N = 6, Graph g(N); seems to allocate memory on compile-time for N = 6 nodes and by that N*N edges. There seems to be no possibility to reduce or limit the number of edges, unless using an undirected graph.

source: http://www.boost.org/doc/libs/1_54_0/libs/graph/doc/adjacency_matrix.html