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:28:14

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.
>
> I am really sorry, but I'm still not sure if I get it right.
> So, when I declare the iterator_property_map as follows:
>
> typedef iterator_property_map< std::vector< cost >::iterator, VertexIndexMap
>>> CostMap;
> CostMap c_map(v_vec.begin(), v_index);
>
> and v_index is _not_ initialized, then what will be the size and the content
> of the CostMap? And what will be the size and content of v_index?

Remember that c_map gets its size from v_vec, and so it will have whatever 
size that has.  Its contents will be the contents of v_vec, mapped to 
graph vertices using the identity function (i.e., get(c_map, v) will map 
to v_vec[(size_t)v]).

> Will it be the size of v_vec? And by identity, do you mean that a vertex is
> basically just an integer and thus each vertex will be mapped to its according
> number, so therefore identity? And because this is the default behavior, it is
> equal to using get(vertex_index, g) as this basically is also just an
> identity-map?

It is equal for this particular kind of graph, but you can't rely on that 
in general.

> So basically, the default-initialization of VertexIndexMap will result in the
> identity, aswell as for the CostMap, therefore it doesn't matter whether you
> specify vertex-index, as long as it is the identity?

For this particular kind of map, there are no members in the property map 
as far as I know, and so initializing it is not important.  However, that 
is an accident of this particular graph type having an identity 
vertex_index_map.  If you try similar code with a grid_graph, it will 
fail, since a default-constructed vertex index map for that graph type 
cannot be used without further initialization; leaving off the vertex 
index map for creating something like CostMap for a grid_graph will fail 
since vertex descriptors are not numbers.

-- Jeremiah Willcock