[BGL] algorithms and listS as vertex list container
Hello, I recently tried to use some (almost all) shortest path algorithms from BGL. But since my program remove a lot of vertices, I opted for an adjacency list graph with list as vertex list container instead of vector.
boost::adjacency_list <boost::setS, boost::listS, boost::bidirectionalS,[...]
This seems to trigger some troubles at compilation level. If I try anything else than vector for vertex list I'm rewarded by similar errors:
boost/graph/relax.hpp:55: error: no matching function for call to ‘put(long unsigned int*&, void*&, long unsigned int)’
My question is as follow, do algorithms handle graphs with list (or set) as vertex list containers? I searched for information about this on the internet and in the documentation but failed to find any clues. Thanks -- Christophe
On Tue, 22 Jun 2010, Christophe Goessen wrote:
Hello,
I recently tried to use some (almost all) shortest path algorithms from BGL. But since my program remove a lot of vertices, I opted for an adjacency list graph with list as vertex list container instead of vector.
boost::adjacency_list <boost::setS, boost::listS, boost::bidirectionalS,[...]
This seems to trigger some troubles at compilation level. If I try anything else than vector for vertex list I'm rewarded by similar errors:
boost/graph/relax.hpp:55: error: no matching function for call to ‘put(long unsigned int*&, void*&, long unsigned int)’
My question is as follow, do algorithms handle graphs with list (or set) as vertex list containers? I searched for information about this on the internet and in the documentation but failed to find any clues.
Which algorithms are you using? The error you are getting is indicative of a bug in the algorithms. Even after the fix, however, they will still not work on graphs with listS, etc. as vertex containers by default. In order to get the shortest path algorithms to work on your graphs, you need to add a vertex_index property map (either internally to the graph or as an external container) and pass it to the algorithm (an internal property map named vertex_index will be found automatically; an external one needs to be passed in explicitly using the vertex_index_map named parameter). Note that you will also need to fill in the map to give a numbering of your graph vertices (in the half-open range [0, num_vertices(g))), and that the map will need to be rebuilt whenever the set of graph vertices changes. -- Jeremiah Willcock
The error is not exactly the same but quite similar (always a such missing function) with all the single source shortest paths algorithms (dijkstra's, bellman-ford's and dag). Also, I already have a vertex_index property map (internal one). What you are implying is that this is a know bug? By the way I'm using the 1.42 version Thanks On 22 June 2010 16:57, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Tue, 22 Jun 2010, Christophe Goessen wrote:
Hello,
I recently tried to use some (almost all) shortest path algorithms from BGL. But since my program remove a lot of vertices, I opted for an adjacency list graph with list as vertex list container instead of vector.
boost::adjacency_list <boost::setS, boost::listS, boost::bidirectionalS,[...]
This seems to trigger some troubles at compilation level. If I try anything else than vector for vertex list I'm rewarded by similar errors:
boost/graph/relax.hpp:55: error: no matching function for call to ‘put(long unsigned int*&, void*&, long unsigned int)’
My question is as follow, do algorithms handle graphs with list (or set) as vertex list containers? I searched for information about this on the internet and in the documentation but failed to find any clues.
Which algorithms are you using? The error you are getting is indicative of a bug in the algorithms. Even after the fix, however, they will still not work on graphs with listS, etc. as vertex containers by default. In order to get the shortest path algorithms to work on your graphs, you need to add a vertex_index property map (either internally to the graph or as an external container) and pass it to the algorithm (an internal property map named vertex_index will be found automatically; an external one needs to be passed in explicitly using the vertex_index_map named parameter). Note that you will also need to fill in the map to give a numbering of your graph vertices (in the half-open range [0, num_vertices(g))), and that the map will need to be rebuilt whenever the set of graph vertices changes.
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
-- Christophe
On Tue, 22 Jun 2010, Christophe Goessen wrote:
The error is not exactly the same but quite similar (always a such missing function) with all the single source shortest paths algorithms (dijkstra's, bellman-ford's and dag). Also, I already have a vertex_index property map (internal one). What you are implying is that this is a know bug?
By the way I'm using the 1.42 version
No, it's not a known bug, it's an unknown one I need to fix. If you have a vertex_index map, all of the algorithms should work with your vertex and edge types. Could you please send me a small example that fails? -- Jeremiah Willcock
Here's an example attached to this message. If replaced by vecS everything compile fine but as is I receive the described compilation error. Hope it will help you On 22 June 2010 19:23, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Tue, 22 Jun 2010, Christophe Goessen wrote:
The error is not exactly the same but quite similar (always a such missing
function) with all the single source shortest paths algorithms (dijkstra's, bellman-ford's and dag). Also, I already have a vertex_index property map (internal one). What you are implying is that this is a know bug?
By the way I'm using the 1.42 version
No, it's not a known bug, it's an unknown one I need to fix. If you have a vertex_index map, all of the algorithms should work with your vertex and edge types. Could you please send me a small example that fails?
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
-- Christophe
On Tue, 22 Jun 2010, Christophe Goessen wrote:
Here's an example attached to this message.
If replaced by vecS everything compile fine but as is I receive the described compilation error.
I looked through your test program; the bug is in there, not in BGL. You are directly using a pointer as a property map, which requires vertex numbers to be integers and does not use a vertex index map. Your properties either need to be internal, use associative_property_map, or (preferred) use an iterator_property_map created with your vector and vertex_index map. If any algorithms fail with iterator_property_map passed in, those may still be bugs in BGL. -- Jeremiah Willcock
participants (2)
-
Christophe Goessen -
Jeremiah Willcock