Re: [Boost-users] [BGL] algorithms and listS as vertex list container

Subject: Re: [Boost-users] [BGL] algorithms and listS as vertex list container
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-06-22 10:57:38

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