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!