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-29 15:30:20

On Fri, 29 Jun 2012, Joachim Faulhaber wrote:

> Dear Jeremiah,
>
> thank you for your answer. Unfortunately, it doesn't solve my
> problems. I admit, I am pretty much frustrated with BGL usability.
> Generally I am fond of boost and I recommend using it to my
> colleagues. But currently my experiences with BGL is very
> unsatisfactory. I hope there are solutions.

BGL can be quite frustrating to use, especially since diagnosis of
errors is not always good.  The trunk version should be better by a
little bit, but it still does require some experience to track down
errors.

> 2012/6/28 Jeremiah Willcock <jewillco_at_[hidden]>:
>> 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.
>
> Using a generic library, I expect, that it is working for all
> instantiations of template parameters (particularly adjacency_list
> here), as long as the requirements for the Concepts of the parameters
> are not violated. In my use case I am experimenting with different
> Types for the edge and vertex lists and I had hoped, that the use of a
> very basic algorithm like depth_first_search would gracefully support
> any of those admissible instantiations.

Yes, and one of the requirements in the documentation is that if you do
not provide a color map as an argument, a default version will be used
and that version needs a vertex index map (either as an argument or a
built-in property map in the graph).

>> From your recommendation ...
>
>> 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
>
> ... I have tried to fix my example:
>
> //=========================================================
> 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;}
> };
>
> 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;
>  typedef graph_traits<GraphLL>::vertex_iterator vertex_iter;
>
>  //Add an associative color map type.
>  typedef map<VertexLL, default_color_type> color_map_t;
>  color_map_t color_map; //Declare a container
>
>  GraphLL g; //Graph and color_map should fit.
>  //Fill graph g
>  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);
>
>  //Intitalize the colormap
>  BGL_FORALL_VERTICES(v, g, GraphLL) {
>    color_map[v] = white_color;
>  }
>  //Generate an assoc property map
>  associative_property_map<color_map_t> pm_color(color_map);
>
>  Visitor<GraphLL> vis;
>  //Again compiler errors here:
>  boost::depth_first_search(g, visitor(vis), pm_color); //(*)

You are mixing named parameters and positional parameters -- try either:

boost::depth_first_search(g, vis, pm_color);

or:

boost::depth_first_search(g, visitor(vis).color_map(pm_color));

and see if either of those work.

-- Jeremiah Willcock