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: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 2011-04-03 12:21:58

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.

> -- Jeremiah Willcock
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users

Best,

Cedric