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

Subject: Re: [Boost-users] [Graph] Static allocation of nodes and edges
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2013-11-11 08:34:39

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

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