[bgl] depth_first_search does not compile. color_map howto?
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).
1. Do I need to provide a color_map parameter here? 2. If so, what is the simplest way to do that and provide an object of the appropriate type? I'd greatly appreciate a working code example. Examples and best practices for defining and handling external propery maps in general would be helpful. TIA, Joachim -- Interval Container Library [Boost.Icl] http://www.joachim-faulhaber.de
... forgot to attach the error message, here it is. 2012/6/25 Joachim Faulhaber <afojgo@googlemail.com>:
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).
1. Do I need to provide a color_map parameter here? 2. If so, what is the simplest way to do that and provide an object of the appropriate type?
I'd greatly appreciate a working code example. Examples and best practices for defining and handling external propery maps in general would be helpful.
TIA, Joachim
-- Interval Container Library [Boost.Icl] http://www.joachim-faulhaber.de
-- Interval Container Library [Boost.Icl] http://www.joachim-faulhaber.de
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/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
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@osl.iu.edu>:
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/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.
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<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
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@osl.iu.edu>:
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/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<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
2012/6/29 Jeremiah Willcock <jewillco@osl.iu.edu>:
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@osl.iu.edu>:
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:
[...]
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.
[...]
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<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.
yes, this was it! Thanks for the answer. This is little trap one can fall into. When extending examples from the documentation using different overloads of an algorithm it is easy to overlook that parameter types are changing from 'named' to 'positional' mode... Thanks for helping :) Cheers, Joachim -- Interval Container Library [Boost.Icl] http://www.joachim-faulhaber.de
participants (5)
-
Jeremiah Willcock -
Joachim Faulhaber