Boost logo

Boost Users :

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]



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