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

11 Nov 2013

      On Mon, 11 Nov 2013, Sensei wrote:
...
On 08/11/13 22:13, Jeremiah Willcock wrote:
...
...
I have the list of nodes in a std container, for completeness of
information. The edges are calculated by a functional on node pairs
(ie, I need n^2 operations).
Even to find just n*k edges?
Unfortunately, it derives from a NP-hard problem. If I could find a 
heuristics, I will use it, but right now I'm just with a not-so-cool n^2 
computations.
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.
...
...
...
I could create a list of pairs of nodes for edges, but I think it
would defeat the purpose of using a graph, at least, if creating the
graph involves copying all edges. If there were a sort of "moving
semantics" with this respect, it would help a lot.
If you can get aligned vectors of edge sources, targets, and edge
properties (if you have them), there is a constructor that effectively
moves out of those.
You mean these two?
Yes, those two.
...
// In-place unsorted edge list constructors (directed only)
 template<typename InputIterator>
 compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,
                             std::vector& sources,
                             std::vector& targets,
                             vertices_size_type numverts,
                             const GraphProperty& prop = GraphProperty());
template<typename InputIterator>
 compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,
                             std::vector& sources,
                             std::vector& targets,
                             std::vector<EdgeProperty>& edge_props,
                             vertices_size_type numverts,
                             const GraphProperty& prop = GraphProperty());
So, you say I would be able to create two temporary vectors of src/dest and 
those constructors won't create a copy? Isn't the move constructor actually 
defined as constructor(type &&v)? I might be missing something here...
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.

-- Jeremiah Willcock