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