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-06 04:43:29

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