[BGL] Confusion about iterator_property_map and initialization of OffsetMap
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? Best, Cedric
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. -- Jeremiah Willcock
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.
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Best, Cedric
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. -- Jeremiah Willcock
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? 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? 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? Thank you and appologies for my repeated asking.
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Best, Cedric
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
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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Best, Cedric
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
participants (2)
-
Cedric Laczny -
Jeremiah Willcock