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