Re: [Boost-users] Compile error when using breadth_first_search with these adjacency_list template parameters

Subject: Re: [Boost-users] Compile error when using breadth_first_search with these adjacency_list template parameters
From: Michael Olea (oleaj_at_[hidden])
Date: 2009-05-08 18:18:19

On May 8, 2009, at 11:45 AM, Julian wrote:

> Hi,
>
> I get one compiler error when using breadth_first search with the  
> adjacency list shown below.
>
> template < typename Vertex>
> class bfs_reachable_set_visitor : public default_bfs_visitor {
> public:
>     bfs_reachable_set_visitor(set<Vertex>* bucket): m_set(bucket) { }
>     template < typename Graph >
>     void discover_vertex(Vertex u, const Graph & g)
>     {
>         m_set->insert(u);
>     }
>     set<Vertex>* m_set;
> };
>
> typedef adjacency_list<setS, listS, undirectedS,  
> RectGraphVertexData> RectAreaGraph;
> typedef graph_traits<RectAreaGraph>::vertex_descriptor VDescriptor;
> struct RectGraphVertexData {};
>
> void some_func() {
>     RectAreaGraph g;
>     set<VDescriptor> reachableSet;
>
>     bfs_reachable_set_visitor<VDescriptor> setvis(&reachableSet);
>
>     breadth_first_search(g,
>                          *(vertices(g).first),
>                          visitor(setvis));
>
> }
>
> The error:
>

<snip>

>
> For now, since it compiles with vecS, I can change to that, but I  
> would prefer to have setS for edge and listS for vertex.

You need to provide either a "color map" or, if you use the default  
color_map, a vertex_index_map that maps vertex_descriptors into the  
range [0, num_vertices(g)). When you use vecS for the vertex list it  
has a vertex_index_map by default, but not so when you use listS for  
the vertex_list:

http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/ 
breadth_first_search.html

Here is an example that uses listS for the vertex_list and makes  
color a vertex property:

http://www.boost.org/doc/libs/1_39_0/libs/graph/example/bfs-example2.cpp

-- Michael