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: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2012-06-29 09:53:46

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.

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.

>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); //(*)
}

int main()
{
  GLL_visit();
  return 0;
}
//=========================================================

The code at (*) still does not compile. [Boost verison: trunk,
Compiler msvc-10].

+ Could someone provide a concrete fix of the code and point out what
I am doing wrong?

Any help greatly appreciated,
Joachim

-- 
Interval Container Library [Boost.Icl]
http://www.joachim-faulhaber.de