Boost logo

Boost Users :

Subject: Re: [Boost-users] [BGL] Confusion about iterator_property_map and initialization of OffsetMap
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-04-03 14:18:55

On Sun, 3 Apr 2011, Cedric Laczny wrote:

> On Saturday, 2. April 2011 21:00:01 Jeremiah Willcock wrote:
>> On Sat, 2 Apr 2011, Cedric Laczny wrote:
>>> On Friday, 1. April 2011 20:25:54 Jeremiah Willcock wrote:
>>>> On Fri, 1 Apr 2011, Cedric Laczny wrote:
>>>>> Hi,
>>>>> I have modified the astar-cities.cpp example to use an external
>>>>> rank_map based on iterator_property_map.
>>>>> The following should give you an idea:
>>>>> vector<cost> v_vec(num_vertices(g), 0.0);
>>>>> typedef property_map< mygraph_t, vertex_index_t>::type VertexIndexMap;
>>>>> VertexIndexMap v_index = get(vertex_index, g); // Initialization of
>>>>> interest // Create the external property map
>>>>> typedef iterator_property_map< std::vector< cost >::iterator,
>>>>> VertexIndexMap
>>>>>> CostMap;
>>>>> CostMap c_map(v_vec.begin(), v_index);
>>>>> and the function-call of astar_search is as follows:
>>>>> astar_search
>>>>> (g, start,
>>>>> distance_heuristic<mygraph_t, cost, location*, const char**>
>>>>> (locations, goal, name),
>>>>> predecessor_map(&p[0]).distance_map(&d[0]).
>>>>> visitor(a_star_vis).
>>>>> rank_map(c_map)); // Here we use the "global" cost map
>>>>> Basically, the code is the same as in the example, with only the
>>>>> addition of the explicit rank_map.
>>>>> Now I am fairly confused that the function call seems to behave the
>>>>> same if I have "get(vertex_index, g)" and if I don't have it.
>>>>> This comes unexpected to me as I would think that it needs OffsetMap
>>>>> (v_index) to correctly find the index in the random access container
>>>>> (v_vec). But when I simply declare an object it is not yet initialized
>>>>> and will not contain any meaningfull offsets (not using
>>>>> "get(vertex_index, g)").
>>>>> So why does it work, when the map is not initialized? Or what am I
>>>>> missing here please?
>>>> The default index map is just a typed_identity_property_map, and that
>>>> class doen't have any parameters to its constructor. However, you
>>>> should not rely on those properties, since algorithms in BGL have
>>>> broken because their authors assumed the vertex index map was the
>>>> identity then users passed in graphs (such as adjacency_list with listS
>>>> as the vertex container) with non-identity maps.
>>> My vertex-list is vecS, therefore the get(vertex_index, g) should work.
>>> But this does not confuse me. It's the fact, that it does not seem to
>>> matter if the map is actually correctly initialized or not. Simply using
>>> the iterator_property_map on an IndexMap() seems to work, which is not
>>> what I would expect as the mapping from a vertex to an offset is hence
>>> missing. So I am unfortunately still confused.
>> The default for the index map when you create an iterator_property_map is
>> the identity (since the property map doesn't know what graph you're using
>> it with), not the graph's vertex index map. Thus, it doesn't matter
>> whether the graph has an index map or not, leaving that argument off of
>> the iterator_property_map's template argument list and constructor will
>> give you the identity.
> Thanks to this information, I think I was able to trace the whole thing down,
> so where basically the identity_property_map comes from.
> The definition of property_map comes from graph/properties.hpp (some bad luck
> in naming IMHO as I expected everything in property_map.hpp) and all this is
> in fact a combination of different typedefs etc.
> I think I could follow through the inner workings so far, except for one thing
> that I have never seen until today, interestingly.
> It's in the line containing:
> typedef typename Selector::template bind_<Graph, Property> Bind;
> What does the "::template" do here please? Using "::type" etc. is a familiar
> thing, but I could not find what the "::template" refers to. I assume it is due
> to the fact that the definition of "bind_" is again integrated into the
> definition of another struct and this makes some more work necessary to apply
> it in a typedef, but I am just guessing here and would like to know it for
> sure. Some additional details about this "technique" (does this have a
> name?...) are also appreciated.
> Thank you.

Are you asking about the ::template syntax? That is a C++ requirement for
accessing member templates of a dependent type. It has a similar
motivation to the requirement for typename in certain places in templates;
the compiler would not know that bind_ is a template rather than a value
(in which case the < becomes an operator) without some kind of flag, and
the template keyword is that flag. I suspect the code is written that way
(rather than with a normal traits class) to avoid partial specialization,
but I am not sure.

-- Jeremiah Willcock

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at