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

Thank you, Daniel, for your informative email. I didn't realize that dijkstra_shortest_paths required an index map. Now I think I'm getting it. I made the changes as you suggested in the piece of code that I would like to contribute to Boost: https://svn.boost.org/trac/boost/ticket/11804#comment:5 Thanks & best, Irek W dniu 07.12.2015 o 12:39, Daniel Hofmann pisze:

Your approach is generic, the only constraints that you have come from the defaults that dijkstra_shortest_path is using.

Take a look here:

...

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

and scroll down to IN: vertex_index_map. There you will find a description of how the default parameter maps each vertex to an index type by means of boost::get(boost::vertex_index, graph). The problem is, that in your scenario using the listS selector does not give you a internal vertex_index property.

Now if you want to be generic as to whether the graph for your function has an internal vertex_index associated with it or not, you can do the following:

template void fn(const Graph& g, VertexIndexMap index_map) { // ... dijkstra_shortest_path(g, s, vertex_index_map(index_map).visitor(dv)); }

that is, you simply push the responsibility to provide an index map to the call site. Then your users can provide you either with a index map of get(vertex_index, g) or their own in case the graph has no internal vertex_index.

If you want to be even more clever, you could dispatch on the graph type and the selectors. For example, see:

...

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

and scroll down to Vertex And Edge Properties, 2nd paragraph. Here the docs state, that if your adjacency list has a VertexList of vecS your graph has a builtin vertex_index.

In that case, the default get(vertex_index, g) is perfectly fine to use.

On 12/06/2015 04:44 PM, Ireneusz Szcześniak wrote:

...

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

_______________________________________________ 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