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-11 08:28:23

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.

>> 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?

   // In-place unsorted edge list constructors (directed only)
   template<typename InputIterator>
   compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,
                               std::vector<vertex_descriptor>& sources,
                               std::vector<vertex_descriptor>& 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<vertex_descriptor>& sources,
                               std::vector<vertex_descriptor>& 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...

Thanks & Cheers!