Re: [Boost-users] [Graph] Static allocation of nodes and edges

Subject: Re: [Boost-users] [Graph] Static allocation of nodes and edges
From: Sensei (senseiwa_at_[hidden])
Date: 2013-11-13 05:24:03

On 11/11/13 14:34, Jeremiah Willcock wrote:
> OK, so you can iterate them, just not store them.  One approach you
> might consider is to:
>
> 1. Create an iterator range containing all possible (source, target)
> pairs in sorted order.
>
> 2. Apply a boost::filter_iterator or similar that computes your
> predicate.
>
> 3. Use one of the edges_are_sorted_t constructors to do a single copy
> from the filtered iterator range; those constructors only make one pass
> over the range for a directed graph, so the fact that filter_iterator
> recomputes the predicate for each pass over the sequence is not a
> problem.

Actually, I must admit I'm quite new to boost :(

You are suggesting me to take a look to boost.range, and to 
boost.iterator libraries, am I correct?

Then, after creating these magical objects (I assume they're like 
functors that will be computed at runtime), the graph constructor will 
do the rest.

Did I interpret this correctly?

Since this is a N^2 problem, and I must apply a function f(vert1, vert2) 
in order to create or not an edge, I was in the process of parallelizing 
the edge construction. Note that computations are completely independent 
from one node to another.

This would be a great thing, as you can imagine. I read that BGL does 
not support concurrency, so if you have any suggestion, I would greatly 
appreciate that :)

> Yes, but this is C++03 code, so I didn't have move construction to work
> with.  Thus, you pass in your own vectors by reference and they are
> given back empty.

Thanks for your pointer. However, I feel something is weird in my code: 
the targets get deallocated, while sources remain the same. This is my 
testing code, just for fun:

     // IN THE HEADER:
     // typedef boost::compressed_sparse_row_graph<boost::directedS> 
boost_graph;

     long num_verts = 1000000;

     std::vector<std::size_t> orig, dest;

     orig.reserve(num_verts * 16);
     dest.reserve(num_verts * 16);

     std::cout << "reserved " << num_verts * 16 << std::endl;
     std::cout << "orig " << orig.size() << " dest " << dest.size() << 
std::endl;

     std::default_random_engine generator;
     std::uniform_int_distribution<std::size_t> distribution(0, num_verts);
     auto rng = std::bind(distribution, generator);

     for (long i = 0; i < num_verts; i++)
     {
         std::size_t s = rng();
         std::size_t e = rng() ;
         orig.push_back(s);
         dest.push_back(e);
         //std::cout << s << " - " << e << std::endl;
     }

     std::cout << "orig " << orig.size() << " dest " << dest.size() << 
std::endl;

     graph_ = std::unique_ptr<boost_graph>(new 
boost_graph(boost::construct_inplace_from_sources_and_targets, orig, 
dest, num_verts));

     std::cout << "orig " << orig.size() << " dest " << dest.size() << 
std::endl;

Now let's skip over the 16 in the reservation, I am just doing tests 
now. My output says:

orig 0 dest 0
orig 1000000 dest 1000000
orig 1000000 dest 0

The first two lines are cool, from zero to num_verts, but the last one 
puzzles me. Inspecting the RAM allocation, I have 66 MB allocated before 
reserving my vectors, 81 MB after generating the fake edges, and 89 
after creating the graph.

Am I doing something wrong with my code?

Thanks & Cheers!