[Boost-users] BGL: Bug in depth_first_search

From: Christian Sturz (linuxkaffee_at_[hidden])
Date: 2008-02-27 11:16:20

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
-- 
GMX startet ShortView.de. Hier findest Du Leute mit Deinen Interessen!
Jetzt dabei sein: http://www.shortview.de/?mc=sv_ext_mf@gmx