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-06 10:44:16

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
>