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
#include
#include
#include
#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 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_paramsmain::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_paramsmain::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_paramsmain::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_paramsmain::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, DFSVisitor = boost::bgl_named_paramsmain::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_paramsmain::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_paramsmain::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_paramsmain::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_paramsmain::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_paramsmain::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_paramsmain::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_paramsmain::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_paramsmain::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_paramsmain::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_paramsmain::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_paramsmain::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_paramsmain::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_paramsmain::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_paramsmain::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::constraints() [with Visitor = boost::bgl_named_paramsmain::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::DFSVisitorConceptmain::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_paramsmain::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_paramsmain::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_paramsmain::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_paramsmain::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_paramsmain::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_paramsmain::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_paramsmain::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_paramsmain::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_paramsmain::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
--
GMX startet ShortView.de. Hier findest Du Leute mit Deinen Interessen!
Jetzt dabei sein: http://www.shortview.de/?mc=sv_ext_mf@gmx
