Re: [Boost-users] [BGL] Is vertex_descriptor always integer?

Thanks, Daniel. I wanted my code to be generic, and not depend on the graph type. So I wonder how to write this piece of code to be independent of the graph type: vector_property_map pred(num_vertices(g)); auto rep = record_edge_predecessors(pred, on_edge_relaxed()); auto dv = make_dijkstra_visitor(rep); dijkstra_shortest_paths(g, s, visitor(dv)); I was hopping that the approach with the iterator_property_map would be generic, but it's not. Thanks & best, Irek W dniu 06.12.2015 o 10:43, Daniel Hofmann pisze:

When you are using the listS selector, your graph does not have the respective index property. This makes sense if you think about lists and random access, but I guess is hard to understand without context.

For property maps that are dense, such as storing weights for every edge, or the predeccessor for every vertex, I recommend the iterator approach from above, with a contiguous container like vector. This gives you constant time random access and fast iteration while keeping memory usage and overhead to a minimum.

Note that this has requirements on the key, i.e. you have to be able to use for example an edge descriptor as an index into your vector.

On December 6, 2015 12:26:23 AM GMT+01:00, "Ireneusz Szcześniak" wrote:

...

Daniel, thank you for you answer.

As you suggested, I tied to use make_iterator_property_map:

std::vector pred_vec(num_vertices(g)); auto pred = make_iterator_property_map(pred_vec.begin(), get(vertex_index_t(), g)); auto rep = record_edge_predecessors(pred, on_edge_relaxed());

My code compiled for:

boost::adjacency_list

but not for:

boost::adjacency_list

Am I doing something wrong?

As for another solution, my guess is that for a mapping from any kind of vertex_descriptor to edge_descriptor, one could use associative_property_map. Would that be true?

Thanks & best, Irek

On 04.12.2015 17:30, Daniel Hofmann wrote:

...

For the concept a vertex_descriptor models, take a look here:

...

http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/Graph.html

...

A vertex descriptor corresponds to a unique vertex in an abstract graph instance. A vertex descriptor must be Default Constructible, Assignable, and Equality Comparable.

These are the guarantees you get.

I'm usually using make_iterator_property_map with a vector of the graph's vertex or edge descriptor.

Hope that helps, Daniel J H

On December 4, 2015 4:07:58 PM GMT+01:00, "Ireneusz Szcześniak" wrote:

...

Hi,

In my code I do:

vector_property_map pred(num_vertices(g)); auto rep = record_edge_predecessors(pred, on_edge_relaxed()); auto dv = make_dijkstra_visitor(rep); dijkstra_shortest_paths(g, s, visitor(dv));

But this assumes that the vertex_descriptor is integer, since I'm using vector_property.

Does this assumption always hold, or should I choose the type of the property map based on the graph type?

Thanks & best, Irek _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users