Re: [Boost-users] [BGL] Confusion about iterator_property_map and initialization of OffsetMap

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