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_graphboost::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!