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

Subject: Re: [Boost-users] [BGL] Is vertex_descriptor always integer?
From: Ireneusz Szcześniak (irek.szczesniak_at_[hidden])
Date: 2015-12-08 03:58:35

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.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
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>