BGL: Bug in depth_first_search
Hi, as it seems I've found a bug in the depth_first_search algorithm. I want to use it with my own ColorMap and a start vertex. Here is the code taken from http://www.boost.org/libs/graph/example/dfs-example.cpp with some slight modifications: ------------------------------------ include <boost/graph/adjacency_list.hpp> #include <boost/graph/depth_first_search.hpp> #include <boost/pending/integer_range.hpp> #include <boost/pending/indirect_cmp.hpp> #include <iostream> using namespace boost; template < typename TimeMap > class dfs_time_visitor:public default_dfs_visitor { typedef typename property_traits < TimeMap >::value_type T; public: dfs_time_visitor(TimeMap dmap, TimeMap fmap, T & t) : m_dtimemap(dmap), m_ftimemap(fmap), m_time(t) { } template < typename Vertex, typename Graph > void discover_vertex(Vertex u, const Graph & g) const { put(m_dtimemap, u, m_time++); } template < typename Vertex, typename Graph > void finish_vertex(Vertex u, const Graph & g) const { put(m_ftimemap, u, m_time++); } TimeMap m_dtimemap; TimeMap m_ftimemap; T & m_time; }; int main() { // Select the graph type we wish to use typedef adjacency_list < vecS, vecS, directedS > graph_t; typedef graph_traits < graph_t >::vertices_size_type size_type; // Set up the vertex names enum { u, v, w, x, y, z, N }; char name[] = { 'u', 'v', 'w', 'x', 'y', 'z' }; // Specify the edges in the graph typedef std::pair < int, int >E; E edge_array[] = { E(u, v), E(u, x), E(x, v), E(y, x), E(v, y), E(w, y), E(w, z), E(z, z) }; #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 graph_t g(N); for (std::size_t j = 0; j < sizeof(edge_array) / sizeof(E); ++j) add_edge(edge_array[j].first, edge_array[j].second, g); #else graph_t g(edge_array, edge_array + sizeof(edge_array) / sizeof(E), N); #endif // Typedefs typedef boost::graph_traits < graph_t >::vertex_descriptor Vertex; Vertex root = source( edge_array[2],g ); typedef size_type* Iiter; // discover time and finish time properties std::vector < size_type > dtime(num_vertices(g)); std::vector < size_type > ftime(num_vertices(g)); size_type t = 0; dfs_time_visitor < size_type * >vis(&dtime[0], &ftime[0], t); std::vector<default_color_type> color(num_vertices( g ) ); depth_first_search(g, visitor(vis), &color[0], root ); return 0; } ------------------------------------ So, I've added a ColorMap and a start vertex as 3. and 4. argument to "depth_first_search". This code can't be compiled with the gcc on a Debian Etch machine. These are the compiler errors: dfs.cc: In function `int main()': dfs.cc:47: warning: unused variable 'name' /usr/include/boost/graph/depth_first_search.hpp: In function `void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<G>::vertex_descriptor) [with VertexListGraph = main()::graph_t, DFSVisitor = boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>, ColorMap = boost::default_color_type*]': dfs.cc:76: instantiated from here /usr/include/boost/graph/depth_first_search.hpp:197: error: 'struct boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>' has no member named 'initialize_vertex' dfs.cc:76: instantiated from here /usr/include/boost/graph/depth_first_search.hpp:200: error: 'struct boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>' has no member named 'start_vertex' dfs.cc:76: instantiated from here /usr/include/boost/graph/depth_first_search.hpp:207: error: 'struct boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>' has no member named 'start_vertex' /usr/include/boost/graph/depth_first_search.hpp: In function `void boost::detail::depth_first_visit_impl(const IncidenceGraph&, typename boost::graph_traits<G>::vertex_descriptor, DFSVisitor&, ColorMap, TerminatorFunc) [with IncidenceGraph = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, DFSVisitor = boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>, ColorMap = boost::default_color_type*, TerminatorFunc = boost::detail::nontruth2]': /usr/include/boost/graph/depth_first_search.hpp:201: instantiated from `void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<G>::vertex_descriptor) [with VertexListGraph = main()::graph_t, DFSVisitor = boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>, ColorMap = boost::default_color_type*]' dfs.cc:76: instantiated from here /usr/include/boost/graph/depth_first_search.hpp:103: error: 'struct boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>' has no member named 'discover_vertex' /usr/include/boost/graph/depth_first_search.hpp:201: instantiated from `void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<G>::vertex_descriptor) [with VertexListGraph = main()::graph_t, DFSVisitor = boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>, ColorMap = boost::default_color_type*]' dfs.cc:76: instantiated from here /usr/include/boost/graph/depth_first_search.hpp:120: error: 'struct boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>' has no member named 'examine_edge' /usr/include/boost/graph/depth_first_search.hpp:201: instantiated from `void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<G>::vertex_descriptor) [with VertexListGraph = main()::graph_t, DFSVisitor = boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>, ColorMap = boost::default_color_type*]' dfs.cc:76: instantiated from here /usr/include/boost/graph/depth_first_search.hpp:123: error: 'struct boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>' has no member named 'tree_edge' /usr/include/boost/graph/depth_first_search.hpp:201: instantiated from `void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<G>::vertex_descriptor) [with VertexListGraph = main()::graph_t, DFSVisitor = boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>, ColorMap = boost::default_color_type*]' dfs.cc:76: instantiated from here /usr/include/boost/graph/depth_first_search.hpp:127: error: 'struct boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>' has no member named 'discover_vertex' /usr/include/boost/graph/depth_first_search.hpp:201: instantiated from `void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<G>::vertex_descriptor) [with VertexListGraph = main()::graph_t, DFSVisitor = boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>, ColorMap = boost::default_color_type*]' dfs.cc:76: instantiated from here /usr/include/boost/graph/depth_first_search.hpp:133: error: 'struct boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>' has no member named 'back_edge' /usr/include/boost/graph/depth_first_search.hpp:201: instantiated from `void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<G>::vertex_descriptor) [with VertexListGraph = main()::graph_t, DFSVisitor = boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>, ColorMap = boost::default_color_type*]' dfs.cc:76: instantiated from here /usr/include/boost/graph/depth_first_search.hpp:136: error: 'struct boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>' has no member named 'forward_or_cross_edge' /usr/include/boost/graph/depth_first_search.hpp:201: instantiated from `void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<G>::vertex_descriptor) [with VertexListGraph = main()::graph_t, DFSVisitor = boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>, ColorMap = boost::default_color_type*]' dfs.cc:76: instantiated from here /usr/include/boost/graph/depth_first_search.hpp:141: error: 'struct boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>' has no member named 'finish_vertex' /usr/include/boost/graph/depth_first_search.hpp: In member function `void boost::DFSVisitorConcept<Visitor, Graph>::constraints() [with Visitor = boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>, Graph = main()::graph_t]': /usr/include/boost/concept_check.hpp:48: instantiated from `void boost::function_requires(boost::mpl::identity<T>*) [with Concept = boost::DFSVisitorConcept<boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>, main()::graph_t>]' /usr/include/boost/graph/depth_first_search.hpp:191: instantiated from `void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<G>::vertex_descriptor) [with VertexListGraph = main()::graph_t, DFSVisitor = boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>, ColorMap = boost::default_color_type*]' dfs.cc:76: instantiated from here /usr/include/boost/graph/depth_first_search.hpp:36: error: 'struct boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>' has no member named 'initialize_vertex' /usr/include/boost/graph/depth_first_search.hpp:37: error: 'struct boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>' has no member named 'start_vertex' /usr/include/boost/graph/depth_first_search.hpp:38: error: 'struct boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>' has no member named 'discover_vertex' /usr/include/boost/graph/depth_first_search.hpp:39: error: 'struct boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>' has no member named 'examine_edge' /usr/include/boost/graph/depth_first_search.hpp:40: error: 'struct boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>' has no member named 'tree_edge' /usr/include/boost/graph/depth_first_search.hpp:41: error: 'struct boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>' has no member named 'back_edge' /usr/include/boost/graph/depth_first_search.hpp:42: error: 'struct boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>' has no member named 'forward_or_cross_edge' /usr/include/boost/graph/depth_first_search.hpp:43: error: 'struct boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>' has no member named 'finish_vertex' So, there seem to be a bug in the algorithm. When calling it as defined in the exampl file from the Boost side without a ColorMap and a vertex, it works fine. Could you verify this and tell me if you can reproduce it? Thank you. Regards, Christian -- Psst! Geheimtipp: Online Games kostenlos spielen bei den GMX Free Games! http://games.entertainment.web.de/de/entertainment/games/free
as it seems I've found a bug in the depth_first_search algorithm. I want to use it with my own ColorMap and a start vertex. Here is the code taken from http://www.boost.org/libs/graph/example/dfs-example.cpp with some slight modifications:
It's a problem with the way you're calling the function. You're calling...
depth_first_search(g, visitor(vis), &color[0], root );
And getting...
/usr/include/boost/graph/depth_first_search.hpp:197: error: 'struct boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>' has no member named 'initialize_vertex' dfs.cc:76: instantiated from here
It looks like you're calling a function that takes a visitor type as the 2nd parameter. The problem is that the visitor() function is probably creating a bgl_named_parameters struct, not a visitor. Needless to say, the named parameters structure doesn't have members named initialize_vertex() or finish_vertex(), etc. Try chaining the named parameters together like this: visitor(vis).color_map(&color[0]).start_vertex(root)
So, there seem to be a bug in the algorithm. When calling it as defined in the exampl file from the Boost side without a ColorMap and a vertex, it works fine.
Again, it's not really a bug in the algorithm... There's so much genericism in the interface that it's easy to get lost in the instantiations. This library is due for a serious overhaul. Andrew Sutton asutton@cs.kent.edu
Hi,
/usr/include/boost/graph/depth_first_search.hpp:197: error: 'struct boost::bgl_named_params<dfs_time_visitor<main::size_type*>, boost::graph_visitor_t, boost::no_property>' has no member named 'initialize_vertex' dfs.cc:76: instantiated from here
It looks like you're calling a function that takes a visitor type as the 2nd parameter. The problem is that the visitor() function is probably creating a bgl_named_parameters struct, not a visitor. Needless to say, the named parameters structure doesn't have members named initialize_vertex() or finish_vertex(), etc. Try chaining the named parameters together like this:
visitor(vis).color_map(&color[0]).start_vertex(root) [start_vertex should be root_vertex]
thank you, this works now. Was a great help for me. ;-) However, this is not very intuitive because according to the documentation http://www.boost.org/libs/graph/doc/depth_first_search.html I would expect 4 arguments for the parameterized version of depth_first_search. I have another problem with the DFS. In the description it's said that "once all reachable vertices have been visited, the algorithm selects from any remaining undiscovered vertices and continues the traversal". What I need is a DFS beginning at the root vertex and traversing over all vertices that can be reached from that root vertex. All further remaining vertices not reachable from the root vertex are irrelevant for me. Is there a way to modify depth_first_search to just get the first set of vertices? Or are there maybe other BGL that would be more suitable for that? Thank you. Christian -- Psst! Geheimtipp: Online Games kostenlos spielen bei den GMX Free Games! http://games.entertainment.web.de/de/entertainment/games/free
I have another problem with the DFS. In the description it's said that "once all reachable vertices have been visited, the algorithm selects from any remaining undiscovered vertices and continues the traversal". What I need is a DFS beginning at the root vertex and traversing over all vertices that can be reached from that root vertex. All further remaining vertices not reachable from the root vertex are irrelevant for me. Is there a way to modify depth_first_search to just get the first set of vertices? Or are there maybe other BGL that would be more suitable for that?
depth_first_visit (with the root vertex as the start vertex - http://www.boost.org/libs/graph/doc/depth_first_visit.html) - Allen Ding
participants (3)
-
Allen Ding -
Andrew Sutton -
Christian Sturz