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

Subject: Re: [Boost-users] CSR graph and Dijkstra's to lower graph memory
From: Leo Hidd (leohidd_at_[hidden])
Date: 2012-09-21 21:35:06

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 <boost/graph/adjacency_list.hpp>
#include <boost/graph/compressed_sparse_row_graph.hpp>
#include <boost/graph/dijkstra_shortest_paths_no_color_map.hpp>

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<vertex_descriptor> 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-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.
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users