Boost logo

Boost Users :

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!


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net