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

hi Jeremy, I'm the OP of that topic. With a great help of Jeremiah WillCock (thank you Jeremiah, you are a great and very patient man :) ), I could finally obtain an working case with CSR graphs (a great amount of messages were sent in private, so they do not appear in the list). Here's an example. Note that I don't provide the the class obj_Mesh, since the only variables I use from it are used to compute the number of edges and the cost of each edge. You can replace these info by your own. Note that I'm a newbie boost user, so don't take it as the best of the use cases, it is just an working case. I hope it helps you. cheers, leo ----------------------------------------------------------------------------------------------------------------- #include #include #include class obj_Mesh; class BoostGraph { typedef std::pair < int, int > Edge; struct Edge_Cost { double weight; }; struct vertex_data { boost::graph_traits< boost::compressed_sparse_row_graph< boost::directedS >

::vertex_descriptor p;

double d; }; typedef boost::compressed_sparse_row_graph< boost::directedS, vertex_data, Edge_Cost > graph_t; typedef boost::graph_traits < graph_t >::vertex_descriptor vertex_descriptor; graph_t* Graph; public: std::vector p;//path std::vector<double> d; //distance BoostGraph(obj_Mesh* mesh) { int numb_edges = mesh->NbOfVertices + mesh->NbOfTriangles - 2; numb_edges *= 2; //for directed graph we add the edge twice (both senses) Edge* edge_list = new Edge [numb_edges]; Edge* ptr_edge_list = edge_list; Edge_Cost* edge_weight_list = new Edge_Cost[numb_edges]; Edge_Cost* ptr_edge_weight_list = edge_weight_list; //compute the cost of the edges for (int i = 0; i < mesh->NbOfVertices; ++i) { for (int j = 0; j < mesh->nbOf_Neigh_Vertices[i]; ++j) { int i_neigh = mesh->Neigh_Vertices[i][j]; if (i < i_neigh)//this if is to prevent an edge to be added twice, { //since i_neigh is presented into the list of i and vice-versa *ptr_edge_list++ = Edge(i, i_neigh); (ptr_edge_weight_list++)->weight = sqrt(obj_Mesh::Distance_Sqr_V3(mesh->vertices+3*i, mesh->vertices+3*i_neigh)); *ptr_edge_list++ = Edge(i_neigh, i); (ptr_edge_weight_list++)->weight = sqrt(obj_Mesh::Distance_Sqr_V3(mesh->vertices+3*i, mesh->vertices+3*i_neigh)); } } } Graph = new graph_t( boost::edges_are_unsorted, edge_list, ptr_edge_list, edge_weight_list, mesh->NbOfVertices); delete [] edge_list; delete [] edge_weight_list; this->p.assign(mesh->NbOfVertices, 0); this->d.assign(mesh->NbOfVertices, 0); } void SSSP(int source_idx) { boost::dijkstra_shortest_paths_no_color_map (*Graph, source_idx, boost::predecessor_map(&p[0]). distance_map(&d[0]). weight_map(boost::get(&Edge_Cost::weight, *Graph)) ); } ~BoostGraph() { if (Graph) delete Graph; } }; Le 21/09/2012 23:19, jer.k a écrit :

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-td4446... 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

...

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' 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-m... Sent from the Boost - Users mailing list archive at Nabble.com. _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users