[Boost-users] CSR graph and Dijkstra's to lower graph memory

Subject: [Boost-users] CSR graph and Dijkstra's to lower graph memory
From: jer.k (jeremy.kawahara_at_[hidden])
Date: 2012-09-21 17:19:51

Hello,

This is my first post and I'm very new to BOOST, so please let me know if I
have missed some of the mailing list etiquette :)

When I run Dijkstra's on my graph, I quickly run out of memory and I'm
trying to find ways to lower the memory needed to store the graph.

My graphs has around ~3,600,000 nodes and ~580,000,000 edges (I will
eventually need a graph at least 5x this number - more if possible). I only
store a weight (double) at each edge (I don't need to store any information
at each node) and find that while this only takes about 1.5 hrs to run, this
takes up around ~95GB (I have access to a cluster so I can run these high
memory jobs). I use an adjacency_list to store this graph.

typedef adjacency_list < setS, vecS, undirectedS, no_property, property <
edge_weight_t, double > > graph_t;

My two questions are:
1) Is this a reasonable amount of memory to expect a graph of this size
using an adjacency_list? Or am I doing some terribly wrong? This is much
more memory needed than I expected.

2) From what I  understand, the compressed sparse row (CSR) graph is a
possible solution to lowering the memory requirements as I know the number
of edges and the number of nodes prior to forming the graph.

I've been going through the documentation and I followed  this tread
<http://boost.2283326.n4.nabble.com/Graph-On-Dijkstra-SSSP-performance-td4446749.html>  
which had an example of using a CSR instead of an adjacency_list and running
Dijkstra's.  However I can't seem to get the last step (last reply by
Jeremiah Willcock) of  
> "plus adding the weight map parameter explicitly
> to the call to dijkstra_shortest_paths_no_color_map"
to work successfully. 

I guess I'm not sure how to add the weigh map parameter to the Dijkstra's
call. 
The following is the relevant code dealing with edge weights.
=======
...
struct Edge_Cost { double weight;}; // Needed for bundled properties.

Edge_Cost *edgeCosts = new Edge_Cost[2]; // Add 3 edges costs.
edgeCosts[0].weight = (2.0);
edgeCosts[1].weight = (5.2);
edgeCosts[2].weight =(3.33);
...
typedef compressed_sparse_row_graph<directedS, 
    WebPage, // From the example docs on CSR
    Edge_Cost // The struct.
> graph_t; 

graph_t g(boost::edges_are_unsorted, &the_edges[0], &the_edges[0] +
numEdges, 
                edgeCosts, // Add the weights here???
                numNodes);
...
boost::dijkstra_shortest_paths(g, // The graph.
          s, // VertexDescriptor - the source vertex.
         &p[0], &d[0], 
         edgeCosts, // <--- WHAT DO I PUT HERE??
         indexmap, 
     std::less<int>(), closed_plus<int>(), 
     (std::numeric_limits<int>::max)(), 0,
         default_dijkstra_visitor()
                          );
=======
When I run this, I get several errors, the first is:
error C2664: 'boost::get' : cannot convert parameter 2 from
'boost::detail::csr_edge_descriptor<Vertex,EdgeIndex>' to 'ptrdiff_t'
c:\boost_1_49_0\boost_1_49_0\boost\graph\dijkstra_shortest_paths.hpp	162

I might be totally off here so please let me know :)

Thanks!
- Jeremy

--
View this message in context: http://boost.2283326.n4.nabble.com/CSR-graph-and-Dijkstra-s-to-lower-graph-memory-tp4636116.html
Sent from the Boost - Users mailing list archive at Nabble.com.