On Mon, Oct 8, 2012 at 1:55 PM, Jeremiah Willcock
<jewillco@osl.iu.edu> wrote:
On Mon, 8 Oct 2012, Jeremy Kawahara wrote:
It seems to me that we need to store the following arrays: (here I assume that the total number of vertices is less than 2^32 (4 bytes) but the total number
of edges will likely be greater than 2^32 (8 bytes).
An "edge array" that stores the vertex indices.
2 vertices per edge at 4 bytes each
Usually (for the directed case where incoming edges aren't stored) there is only one vertex (the target) stored per edge.
I see. I was working from Leo Hidd's earlier example where we create a list of edges...
*ptr_edge_list++ = Edge(i_neigh, i);
and from the
CSR documentation:
E the_edges[] = { E(0, 1), E(0, 2), ...
I'm not quite sure how to change the edge list to store only the target vertex but I'll look into this some more as this would result in quite a bit more space savings.
An "edge cost" array the stores the cost at each edge.
1 edge cost per edge at 4 bytes (say we use a float) each
Yes.
These arguments are than passed to the CSR constructor. I THINK the CSR then sorts and copies these values into an internal structure (I'm basing this off
the documentation which states that "The CSR format stores vertices and edges in separate arrays" - but perhaps I misunderstood it).
The CSR graph takes roughly (nvertices + 1) * sizeof(EdgeIndex) + nedges * sizeof(VertexIndex) bytes for a directed graph, excluding properties.
So I think we need to have enough memory to store the "edge array", the "edge cost array" AND the newly created CSR (the_number_of_edges x 4 bytes +
the_number_of_nodes x 8 bytes) all at the same time.
Is my understanding of this correct?
Yes, except that you need another copy of the edge properties that are sorted along with the edges.
Right, so I think this would be the memory needed to store the "edge cost array", which would equal the_number_of_edges x 4 bytes.
If so, I'm wondering if there is a way we can somehow lower this memory usage where we only store these structures once? I looked at using the
"edges_are_unsorted_multi_pass" parameter but the memory differences did not seem to make a significant difference.
There is an in-place version (construct_inplace_from_sources_and_targets_t) that saves memory by requiring particular input layouts, but it is also slower. You should always use the _multi_pass version when you can since the other one does a copy of the data first.
Alright thanks! The construct_inplace_from _sources_and_targets_t sounds like it might do the trick.
How much more memory are you looking to save? Are you hitting an out-of-memory condition on graphs above a certain size?
Yes on some of my graphs I'm running out of memory. I'm really looking at getting it down to as low as possible since the lower I get it the more data I can run my graphs on. For example, one graph this crashed on had:
37,044,000 nodes
6,328,936,480 edges
I thought that if I can use the same memory to load the data and create the CSR, then I would approximately half my memory requirements. I think if I find this not be enough savings, then I am probably hitting some theoretical limits and would have to look at taking a different approach.
For the reference of others, I added the last "unsigned int" parameter to the call below since I expect the number of nodes to be less than 2^32 but the
number of edges will likely be more.
typedef compressed_sparse_row_graph<directedS, void, Edge_Cost,boost::no_property, unsigned int> graph_t;
Yes, that is how you want to do it in that case. You might want to use uint32_t instead to get more control over the exact data size.