Re: [Boost-users] [Graph] Static allocation of nodes and edges

Subject: Re: [Boost-users] [Graph] Static allocation of nodes and edges
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2013-11-08 09:15:42

On Fri, 8 Nov 2013, Sensei wrote:

> Dear all,
>
> I need to optimize my code with regards to both memory and time. The problem 
> is simple: pre-allocating the adjacency matrix.
>
> The graph may have a huge number of nodes N, but the number of edges K per 
> node is limited. While N can be in the order of one hundred million, K is at 
> most 10. The graph will be directed, so no symmetry is needed.
>
> Do you know if I can pre-allocate such an adjacency matrix?
>
> If not, I suppose I must use an adjacency list in order to minimize memory 
> consumption, am I right?

If you have so few edges per vertex, you definitely don't want to use an 
adjacency matrix.  If your graph will be read-only (in terms of structure, 
not properties), use compressed_sparse_row_graph; be sure to change the 
vertex and edge count sizes to uint32_t if you know your graph size will 
fit into that.  If you are going to be doing modifications, use 
adjacency_list instead.  Adjacency matrices use N^2 storage for N 
vertices, regardless of the number of edges, so they are unlikely to fit 
into memory for your problem size.

-- Jeremiah Willcock