Re: [Boost-users] [bgl] depth_first_search does not compile. color_map howto?

Subject: Re: [Boost-users] [bgl] depth_first_search does not compile. color_map howto?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-06-28 15:24:59

On Mon, 25 Jun 2012, Joachim Faulhaber wrote:

> Hi,
>
> When using visitors with the depth_first_search algorithm I can
> successfully compile and run this code:
>
> //=========================================================
> template<class Graph>
> class Visitor: public default_dfs_visitor
> {
> public:
>  typedef typename
>    graph_traits<Graph>::vertex_descriptor Vertex;
>
>  void discover_vertex(Vertex v, const Graph& g)const
>  {cout << v << " "; return;}
> };
>
> void GLV_visit()
> {
>  typedef adjacency_list<listS, vecS, directedS> GraphLV;
>  GraphLV g;
>  add_edge(0, 1, g);
>  add_edge(0, 2, g);
>  add_edge(1, 2, g);
>  add_edge(1, 3, g);
>
>  Visitor<GraphLV> vis;
>  boost::depth_first_search(g, visitor(vis));
>  cout << endl;
> }
>
> BOOST_AUTO_TEST_CASE(graph_test)
> {
>  GLV_visit();
> }
> //=========================================================
>
> With a slightly different graph (listS instead of vecS for vertices)
> the same call of depth_first_search fails to compile with msvc-10.
>
> //=========================================================
> struct Int{
>  Int(): _value(0){}
>  Int(int val): _value(val){}
>  int _value;
> };
>
> void GLL_visit()
> {
>  typedef adjacency_list<listS, listS, directedS, Int> GraphLL;
>  typedef graph_traits<GraphLL>::vertex_descriptor VertexLL;
>  GraphLL g;
>  Int val(42);
>  VertexLL v0 = boost::add_vertex(g);
>  VertexLL v1 = boost::add_vertex(g);
>  g[v0] = Int(0);
>  g[v1] = Int(1);
>  add_edge(v0, v1, g);
>
>  Visitor<GraphLL> vis;
>  boost::depth_first_search(g, visitor(vis)); //compile errors
> }
> //=========================================================
>
>> From the tiny error message of 108 long verbose lines of internal
> graph template instantiations (see attachment) it seems that the
> compiler is unable to create a default color_map (but I might be wrong
> with this interpretation of the template jungle).

Yes, that is the issue; BGL can't create a default color map because your 
graph does not have a built-in vertex index map (which is provided 
automatically for vecS as vertex container but needs to be built manually 
for listS).

> 1. Do I need to provide a color_map parameter here?

Yes, or vertex_index_map.

> 2. If so, what is the simplest way to do that and provide an object of
> the appropriate type?

The simplest way is probably to use associative_property_map; see lines 
129-140 of 
http://www.informatik.uni-koeln.de/scil/documentation/html/SteinerArborescence_8cc_source.html 
for an example.  You can also look at 
http://boost.2283326.n4.nabble.com/BGL-dijkstra-shortest-paths-with-listS-td2557281.html 
for other places where associative_property_map can be used.

> I'd greatly appreciate a working code example. Examples and best
> practices for defining and handling external propery maps in general
> would be helpful.

There are several examples of external properties around; it's just hard 
to find examples that match up with graphs using listS since most people 
probably use vecS as their vertex container for performance.

-- Jeremiah Willcock