[Boost-users] [Graph] Large Graphs: performace boost

Subject: [Boost-users] [Graph] Large Graphs: performace boost
From: Sensei (senseiwa_at_[hidden])
Date: 2014-07-30 10:18:48

Dear all,

Facing an increasing size in my experiments, I am wondering now if my 
data structure is still valid.

I need to traverse a graph (with my custom A*) that now can easily 
contain 10M-100M nodes and 100M-400M edges. The graph is (now) without 
weights, but this may change in the future. The only thing that is 
guaranteed not to change is that the graph is immutable.

The graphs might even be larger, and at some point I will move to 
parallel BGL, but not now.

To spare some memory, I am using a CSR graph:

     typedef boost::compressed_sparse_row_graph<boost::bidirectionalS> 
boost_graph;

     graph_ = new boost_graph(boost::edges_are_unsorted_multi_pass, 
results.begin(), results.end(), nodelist().size());

I am dubious if this the best solution.

I have two objectives right now, optimize with respect to 1) memory 
consumption, and 2) graph traversal time. The main operation I need to 
do on graph is just "given a node, find the adjacent ones" (with my A*).

Do you suggest to switch to another graph data structure? How do you 
think I will sacrifice time for memory, and vice versa, if I move for 
instance to an adjacency list?

Thanks for any suggestion!