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

Subject: Re: [Boost-users] [BGL] Is vertex_descriptor always integer?
From: Daniel Hofmann (daniel_at_[hidden])
Date: 2015-12-07 06:39:10

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

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 <typename Graph, typename VertexIndexMap>
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<edge_descriptor> 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"
>> <irek.szczesniak_at_[hidden]> wrote:
>>> Daniel, thank you for you answer.
>>>
>>> As you suggested, I tied to use make_iterator_property_map:
>>>
>>>      std::vector<edge_descriptor> 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<boost::vecS, boost::vecS, boost::bidirectionalS>
>>>
>>> but not for:
>>>
>>> boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS>
>>>
>>> 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"
>>> <irek.szczesniak_at_[hidden]> wrote:
>>>>> Hi,
>>>>>
>>>>> In my code I do:
>>>>>
>>>>> vector_property_map<edge_descriptor> 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_at_[hidden]
>>>>> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>>>>
>>>> _______________________________________________
>>>> Boost-users mailing list
>>>> Boost-users_at_[hidden]
>>>> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>>>>
>>>
>>> _______________________________________________
>>> Boost-users mailing list
>>> Boost-users_at_[hidden]
>>> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>>
>> _______________________________________________
>> Boost-users mailing list
>> Boost-users_at_[hidden]
>> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>>
> 
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users