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

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. -- Jeremiah Willcock