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

29 Jun 2012

      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 :
...
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 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 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/SteinerArborescen...
for an example.  You can also look at
http://boost.2283326.n4.nabble.com/BGL-dijkstra-shortest-paths-with-listS-td...
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/SteinerArborescen...
... 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 GraphLL;
 typedef graph_traits<GraphLL>::vertex_descriptor VertexLL;
 typedef graph_traits<GraphLL>::vertex_iterator vertex_iter;
//Add an associative color map type.
 typedef map 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 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