[Boost-commit] svn:boost r78030 - in trunk: boost/graph libs/graph/doc libs/graph/example libs/graph/test

Subject: [Boost-commit] svn:boost r78030 - in trunk: boost/graph libs/graph/doc libs/graph/example libs/graph/test
From: jewillco_at_[hidden]
Date: 2012-04-16 19:12:52

Author: jewillco
Date: 2012-04-16 19:12:50 EDT (Mon, 16 Apr 2012)
New Revision: 78030
URL: http://svn.boost.org/trac/boost/changeset/78030

Log:
Added code and docs from #5269 (some code heavily rewritten) and removed old workarounds; fixes #5269
Added:
   trunk/libs/graph/test/undirected_dfs.cpp   (contents, props changed)
Text files modified: 
   trunk/boost/graph/depth_first_search.hpp     |    66 ++++++++++++++++++++++++++++----------- 
   trunk/boost/graph/undirected_dfs.hpp         |    18 ++++++----                              
   trunk/boost/graph/visitors.hpp               |     3 +                                       
   trunk/libs/graph/doc/DFSVisitor.html         |     9 +++++                                   
   trunk/libs/graph/doc/depth_first_search.html |     6 +++                                     
   trunk/libs/graph/doc/undirected_dfs.html     |     8 ++++                                    
   trunk/libs/graph/example/dfs.cpp             |    12 +++++++                                 
   trunk/libs/graph/example/dfs.expected        |     6 +++                                     
   trunk/libs/graph/test/Jamfile.v2             |     1                                         
   trunk/libs/graph/test/dfs.cpp                |     6 +++                                     
   10 files changed, 107 insertions(+), 28 deletions(-)

Modified: trunk/boost/graph/depth_first_search.hpp
==============================================================================
--- trunk/boost/graph/depth_first_search.hpp	(original)
+++ trunk/boost/graph/depth_first_search.hpp	2012-04-16 19:12:50 EDT (Mon, 16 Apr 2012)
@@ -21,8 +21,10 @@
 #include <boost/graph/named_function_params.hpp>
 #include <boost/ref.hpp>
 #include <boost/implicit_cast.hpp>
+#include <boost/optional.hpp>
 #include <boost/parameter.hpp>
 #include <boost/concept/assert.hpp>
+#include <boost/tti/has_member_function.hpp>
 
 #include <vector>
 #include <utility>
@@ -41,6 +43,7 @@
       vis.tree_edge(e, g);
       vis.back_edge(e, g);
       vis.forward_or_cross_edge(e, g);
+      // vis.finish_edge(e, g); // Optional for user
       vis.finish_vertex(u, g);
     }
   private:
@@ -57,6 +60,25 @@
       bool operator()(const T&, const T2&) const { return false; }
     };
 
+    BOOST_TTI_HAS_MEMBER_FUNCTION(finish_edge)
+
+    template <bool IsCallable> struct do_call_finish_edge {
+      template <typename E, typename G, typename Vis>
+      static void call_finish_edge(Vis& vis, const E& e, const G& g) {
+        vis.finish_edge(e, g);
+      }
+    };
+
+    template <> struct do_call_finish_edge<false> {
+      template <typename E, typename G, typename Vis>
+      static void call_finish_edge(Vis&, const E&, const G&) {}
+    };
+
+    template <typename E, typename G, typename Vis>
+    void call_finish_edge(Vis& vis, const E& e, const G& g) { // Only call if method exists
+      do_call_finish_edge<has_member_function_finish_edge<Vis, void>::value>::call_finish_edge(vis, e, g);
+    }
+
 
 // Define BOOST_RECURSIVE_DFS to use older, recursive version.
 // It is retained for a while in order to perform performance
@@ -85,36 +107,35 @@
       BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<IncidenceGraph> ));
       BOOST_CONCEPT_ASSERT(( DFSVisitorConcept<DFSVisitor, IncidenceGraph> ));
       typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;
+      typedef typename graph_traits<IncidenceGraph>::edge_descriptor Edge;
       BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<ColorMap, Vertex> ));
       typedef typename property_traits<ColorMap>::value_type ColorValue;
       BOOST_CONCEPT_ASSERT(( ColorValueConcept<ColorValue> ));
       typedef color_traits<ColorValue> Color;
       typedef typename graph_traits<IncidenceGraph>::out_edge_iterator Iter;
-      typedef std::pair<Vertex, std::pair<Iter, Iter> > VertexInfo;
+      typedef std::pair<Vertex, std::pair<boost::optional<Edge>, std::pair<Iter, Iter> > > VertexInfo;
 
+      boost::optional<Edge> src_e;
       Iter ei, ei_end;
       std::vector<VertexInfo> stack;
 
       // Possible optimization for vector
       //stack.reserve(num_vertices(g));
 
-      typedef typename unwrap_reference<TerminatorFunc>::type TF;
-
       put(color, u, Color::gray());
       vis.discover_vertex(u, g);
       boost::tie(ei, ei_end) = out_edges(u, g);
-      // Variable is needed to workaround a borland bug.
-      TF& fn = static_cast<TF&>(func);
-      if (fn(u, g)) {
+      if (func(u, g)) {
           // If this vertex terminates the search, we push empty range
-          stack.push_back(std::make_pair(u, std::make_pair(ei_end, ei_end)));
+          stack.push_back(std::make_pair(u, std::make_pair(boost::optional<Edge>(), std::make_pair(ei_end, ei_end))));
       } else {
-          stack.push_back(std::make_pair(u, std::make_pair(ei, ei_end)));
+          stack.push_back(std::make_pair(u, std::make_pair(boost::optional<Edge>(), std::make_pair(ei, ei_end))));
       }
       while (!stack.empty()) {
         VertexInfo& back = stack.back();
         u = back.first;
-        boost::tie(ei, ei_end) = back.second;
+        src_e = back.second.first;
+        boost::tie(ei, ei_end) = back.second.second;
         stack.pop_back();
         while (ei != ei_end) {
           Vertex v = target(*ei, g);
@@ -122,24 +143,28 @@
           ColorValue v_color = get(color, v);
           if (v_color == Color::white()) {
             vis.tree_edge(*ei, g);
-            stack.push_back(std::make_pair(u, std::make_pair(++ei, ei_end)));
+            src_e = *ei;
+            stack.push_back(std::make_pair(u, std::make_pair(src_e, std::make_pair(++ei, ei_end))));
             u = v;
             put(color, u, Color::gray());
             vis.discover_vertex(u, g);
             boost::tie(ei, ei_end) = out_edges(u, g);
-            if (fn(u, g)) {
+            if (func(u, g)) {
                 ei = ei_end;
             }
-          } else if (v_color == Color::gray()) {
-            vis.back_edge(*ei, g);
-            ++ei;
           } else {
-            vis.forward_or_cross_edge(*ei, g);
+            if (v_color == Color::gray()) {
+              vis.back_edge(*ei, g);
+            } else {
+              vis.forward_or_cross_edge(*ei, g);
+            }
+            call_finish_edge(vis, *ei, g);
             ++ei;
           }
         }
         put(color, u, Color::black());
         vis.finish_vertex(u, g);
+        if (src_e) call_finish_edge(vis, src_e.get(), g);
       }
     }
 
@@ -164,10 +189,7 @@
 
       put(color, u, Color::gray());          vis.discover_vertex(u, g);
 
-      typedef typename unwrap_reference<TerminatorFunc>::type TF;
-      // Variable is needed to workaround a borland bug.
-      TF& fn = static_cast<TF&>(func);
-      if (!fn(u, g))
+      if (!func(u, g))
         for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
           Vertex v = target(*ei, g);           vis.examine_edge(*ei, g);
           ColorValue v_color = get(color, v);
@@ -175,6 +197,7 @@
           depth_first_visit_impl(g, v, vis, color, func);
           } else if (v_color == Color::gray()) vis.back_edge(*ei, g);
           else                                 vis.forward_or_cross_edge(*ei, g);
+          call_finish_edge(vis, *ei, g);
         }
       put(color, u, Color::black());         vis.finish_vertex(u, g);
     }
@@ -259,6 +282,10 @@
     void forward_or_cross_edge(Edge u, const Graph& g) {
       invoke_visitors(m_vis, u, g, ::boost::on_forward_or_cross_edge());
     }
+    template <class Edge, class Graph>
+    void finish_edge(Edge u, const Graph& g) {
+      invoke_visitors(m_vis, u, g, ::boost::on_finish_edge());
+    }
     template <class Vertex, class Graph>
     void finish_vertex(Vertex u, const Graph& g) {
       invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
@@ -271,6 +298,7 @@
     BOOST_GRAPH_EVENT_STUB(on_tree_edge,dfs)
     BOOST_GRAPH_EVENT_STUB(on_back_edge,dfs)
     BOOST_GRAPH_EVENT_STUB(on_forward_or_cross_edge,dfs)
+    BOOST_GRAPH_EVENT_STUB(on_finish_edge,dfs)
     BOOST_GRAPH_EVENT_STUB(on_finish_vertex,dfs)
 
   protected:

Modified: trunk/boost/graph/undirected_dfs.hpp
==============================================================================
--- trunk/boost/graph/undirected_dfs.hpp	(original)
+++ trunk/boost/graph/undirected_dfs.hpp	2012-04-16 19:12:50 EDT (Mon, 16 Apr 2012)
@@ -46,18 +46,18 @@
       typedef color_traits<ColorValue> Color;
       typedef color_traits<EColorValue> EColor;
       typedef typename graph_traits<IncidenceGraph>::out_edge_iterator Iter;
-      typedef std::pair<Vertex, std::pair<Iter, Iter> > VertexInfo;
+      typedef std::pair<Vertex, std::pair<boost::optional<Edge>, std::pair<Iter, Iter> > > VertexInfo;
 
       std::vector<VertexInfo> stack;
 
       put(vertex_color, u, Color::gray());
       vis.discover_vertex(u, g);
-      stack.push_back(std::make_pair(u, out_edges(u, g)));
+      stack.push_back(std::make_pair(u, std::make_pair(boost::optional<Edge>(), out_edges(u, g))));
       while (!stack.empty()) {
         VertexInfo& back = stack.back();
         u = back.first;
-        Iter ei, ei_end;
-        boost::tie(ei, ei_end) = back.second;
+        boost::optional<Edge> src_e = back.second.first;
+        Iter ei = back.second.second.first, ei_end = back.second.second.second;
         stack.pop_back();
         while (ei != ei_end) {
           Vertex v = target(*ei, g);
@@ -67,20 +67,24 @@
           put(edge_color, *ei, EColor::black());
           if (v_color == Color::white()) {
             vis.tree_edge(*ei, g);
-            stack.push_back(std::make_pair(u, std::make_pair(++ei, ei_end)));
+            src_e = *ei;
+            stack.push_back(std::make_pair(u, std::make_pair(src_e, std::make_pair(++ei, ei_end))));
             u = v;
             put(vertex_color, u, Color::gray());
             vis.discover_vertex(u, g);
             boost::tie(ei, ei_end) = out_edges(u, g);
           } else if (v_color == Color::gray()) {
             if (uv_color == EColor::white()) vis.back_edge(*ei, g);
+            call_finish_edge(vis, *ei, g);
             ++ei;
           } else { // if (v_color == Color::black())
+            call_finish_edge(vis, *ei, g);
             ++ei;
           }
         }
         put(vertex_color, u, Color::black());
         vis.finish_vertex(u, g);
+        if (src_e) call_finish_edge(vis, src_e.get(), g);
       }
     }
 
@@ -119,6 +123,7 @@
           undir_dfv_impl(g, v, vis, vertex_color, edge_color);
         } else if (v_color == Color::gray() && uv_color == EColor::white())
                                              vis.back_edge(*ei, g);
+                                             call_finish_edge(vis, *ei, g);
       }
       put(vertex_color, u, Color::black());  vis.finish_vertex(u, g);
     }
@@ -219,8 +224,7 @@
   undirected_dfs(const Graph& g, 
                  const bgl_named_params<P, T, R>& params)
   {
-    typedef typename get_param_type< bgl_named_params<P, T, R>, 
-      vertex_color_t>::type C;
+    typedef typename get_param_type< vertex_color_t, bgl_named_params<P, T, R> >::type C;
     detail::udfs_dispatch<C>::apply
       (g,
        choose_param(get_param(params, graph_visitor),

Modified: trunk/boost/graph/visitors.hpp
==============================================================================
--- trunk/boost/graph/visitors.hpp	(original)
+++ trunk/boost/graph/visitors.hpp	2012-04-16 19:12:50 EDT (Mon, 16 Apr 2012)
@@ -44,7 +44,7 @@
       on_discover_vertex_num, on_finish_vertex_num, on_examine_vertex_num,
       on_examine_edge_num, on_tree_edge_num, on_non_tree_edge_num,
       on_gray_target_num, on_black_target_num,
-      on_forward_or_cross_edge_num, on_back_edge_num,
+      on_forward_or_cross_edge_num, on_back_edge_num, on_finish_edge_num,
       on_edge_relaxed_num, on_edge_not_relaxed_num,
       on_edge_minimized_num, on_edge_not_minimized_num
     };
@@ -75,6 +75,7 @@
   struct on_forward_or_cross_edge {
     enum { num = detail::on_forward_or_cross_edge_num }; };
   struct on_back_edge { enum { num = detail::on_back_edge_num }; };
+  struct on_finish_edge { enum { num = detail::on_finish_edge_num }; };
 
   struct on_edge_relaxed { enum { num = detail::on_edge_relaxed_num }; };
   struct on_edge_not_relaxed {

Modified: trunk/libs/graph/doc/DFSVisitor.html
==============================================================================
--- trunk/libs/graph/doc/DFSVisitor.html	(original)
+++ trunk/libs/graph/doc/DFSVisitor.html	2012-04-16 19:12:50 EDT (Mon, 16 Apr 2012)
@@ -150,6 +150,15 @@
 </tr>
 
 <tr>
+<td>Finish Edge</td> 
+<td><tt>vis.finish_edge(e, g)</tt></td> 
+<td><tt>void</tt></td> 
+<td> 
+This is invoked on each non-tree edge as well as on each tree edge after 
+<tt>finish_vertex</tt> has been called on its target vertex.</td> 
+</tr> 
+ 
+<tr> 
 <td>Finish Vertex</td>
 <td><tt>vis.finish_vertex(u, g)</tt></td>
 <td><tt>void</tt></td>

Modified: trunk/libs/graph/doc/depth_first_search.html
==============================================================================
--- trunk/libs/graph/doc/depth_first_search.html	(original)
+++ trunk/libs/graph/doc/depth_first_search.html	2012-04-16 19:12:50 EDT (Mon, 16 Apr 2012)
@@ -107,6 +107,7 @@
       <i>...</i>
     <b>else if</b> (<i>color[v] =</i> BLACK) 
       <i>...</i>
+    <i>...</i>
   <b>end for</b>
   <i>color[u] :=</i> BLACK
   <i>f_time[u] := time := time + 1</i> 
@@ -140,6 +141,8 @@
 -
 <i>(u,v)</i> is a cross or forward edge
 -
+finish edge <i>(u,v)</i>
+-
 finish vertex <i>u</i>
 -
 </pre>
@@ -266,6 +269,9 @@
 <li><b><tt>vis.forward_or_cross_edge(e, g)</tt></b> is invoked on
   forward or cross edges in the graph. In an undirected graph this
   method is never called.
+
+<li><b><tt>vis.finish_edge(e, g)</tt></b> is invoked on the non-tree edges in 
+  the graph as well as on each tree edge after its target vertex is finished. 
   
 <li><b><tt>vis.finish_vertex(u, g)</tt></b> is invoked on a vertex after
   all of its out edges have been added to the search tree and all of

Modified: trunk/libs/graph/doc/undirected_dfs.html
==============================================================================
--- trunk/libs/graph/doc/undirected_dfs.html	(original)
+++ trunk/libs/graph/doc/undirected_dfs.html	2012-04-16 19:12:50 EDT (Mon, 16 Apr 2012)
@@ -7,7 +7,7 @@
      http://www.boost.org/LICENSE_1_0.txt)
   -->
 <Head>
-<Title>Boost Graph Library: Depth-First Search</Title>
+<Title>Boost Graph Library: Undirected Depth-First Search</Title>
 <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
         ALINK="#ff0000"> 
 <IMG SRC="../../../boost.png" 
@@ -116,6 +116,7 @@
       <b>call</b> DFS-VISIT(<i>G</i>, <i>v</i>)
     <b>else if</b> (<i>vcolor[v] =</i> GRAY and <i>ec =</i> WHITE)
       <i>...</i>
+    <i>...</i>
   <b>end for</b>
   <i>vcolor[u] :=</i> BLACK
   <i>f_time[u] := time := time + 1</i> 
@@ -152,6 +153,8 @@
 <i>(u,v)</i> is a back edge
 -
 -
+finish edge <i>(u,v)</i>
+-
 finish vertex <i>u</i>
 -
 </pre>
@@ -291,6 +294,9 @@
 <li><b><tt>vis.back_edge(e, g)</tt></b> is invoked on the back edges in
   the graph. 
 
+<li><b><tt>vis.finish_edge(e, g)</tt></b> is invoked on the back edges in 
+  the graph as well as on each tree edge after its target vertex is finished. 
+
 <li><b><tt>vis.finish_vertex(u, g)</tt></b> is invoked on a vertex after
   all of its out edges have been added to the search tree and all of
   the adjacent vertices have been discovered (but before their

Modified: trunk/libs/graph/example/dfs.cpp
==============================================================================
--- trunk/libs/graph/example/dfs.cpp	(original)
+++ trunk/libs/graph/example/dfs.cpp	2012-04-16 19:12:50 EDT (Mon, 16 Apr 2012)
@@ -27,12 +27,18 @@
   Tree edge: 0 --> 2
   Tree edge: 2 --> 1
   Back edge: 1 --> 1
+  Finish edge: 1 --> 1
   Tree edge: 1 --> 3
   Back edge: 3 --> 1
+  Finish edge: 3 --> 1
   Tree edge: 3 --> 4
   Back edge: 4 --> 0
+  Finish edge: 4 --> 0
   Back edge: 4 --> 1
+  Finish edge: 4 --> 1
   Forward or cross edge: 2 --> 3
+  Finish edge: 2 --> 3
+  Finish edge: 0 --> 2
   1 10
   3 8
   2 9
@@ -69,6 +75,12 @@
          << " --> " <<  target(e, G) << endl;
     Base::forward_or_cross_edge(e, G);
   }
+  template <class Edge, class Graph> 
+  void finish_edge(Edge e, Graph& G) { 
+    cout << "Finish edge: " << source(e, G) << 
+      " --> " <<  target(e, G) << endl; 
+    Base::finish_edge(e, G); 
+  } 
 };
 template <class VisitorList>
 edge_categorizer<VisitorList>

Modified: trunk/libs/graph/example/dfs.expected
==============================================================================
--- trunk/libs/graph/example/dfs.expected	(original)
+++ trunk/libs/graph/example/dfs.expected	2012-04-16 19:12:50 EDT (Mon, 16 Apr 2012)
@@ -1,12 +1,18 @@
 Tree edge: 0 --> 2
 Tree edge: 2 --> 1
 Back edge: 1 --> 1
+Finish edge: 1 --> 1
 Tree edge: 1 --> 3
 Back edge: 3 --> 1
+Finish edge: 3 --> 1
 Tree edge: 3 --> 4
 Back edge: 4 --> 0
+Finish edge: 4 --> 0
 Back edge: 4 --> 1
+Finish edge: 4 --> 1
 Forward or cross edge: 2 --> 3
+Finish edge: 2 --> 3
+Finish edge: 0 --> 2
 1 10
 3 8
 2 9

Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2	(original)
+++ trunk/libs/graph/test/Jamfile.v2	2012-04-16 19:12:50 EDT (Mon, 16 Apr 2012)
@@ -43,6 +43,7 @@
     [ run csr_graph_test.cpp : : : : : <variant>release ]
     [ run dag_longest_paths.cpp ]
     [ run dfs.cpp ../../test/build//boost_test_exec_monitor ]
+    [ run undirected_dfs.cpp ../../test/build//boost_test_exec_monitor ]
     [ compile dfs_cc.cpp ]
     [ compile dijkstra_cc.cpp ]
     [ run dijkstra_heap_performance.cpp : 10000 ]

Modified: trunk/libs/graph/test/dfs.cpp
==============================================================================
--- trunk/libs/graph/test/dfs.cpp	(original)
+++ trunk/libs/graph/test/dfs.cpp	2012-04-16 19:12:50 EDT (Mon, 16 Apr 2012)
@@ -68,6 +68,12 @@
     using namespace boost;
     BOOST_CHECK( get(m_color, target(e, g)) == Color::black() );
   }
+  template <class Edge, class Graph>
+  void finish_edge(Edge e, Graph& g) {
+    using namespace boost;
+    BOOST_CHECK( get(m_color, target(e, g)) == Color::gray() ||
+                 get(m_color, target(e, g)) == Color::black() );
+  }
   template <class Vertex, class Graph>
   void finish_vertex(Vertex u, Graph&) {
     using namespace boost;

Added: trunk/libs/graph/test/undirected_dfs.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/undirected_dfs.cpp	2012-04-16 19:12:50 EDT (Mon, 16 Apr 2012)
@@ -0,0 +1,187 @@
+//=======================================================================
+// Copyright 2001 University of Notre Dame.
+// Author: Jeremy G. Siek
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//=======================================================================
+
+#include <boost/config.hpp>
+#include <boost/test/minimal.hpp>
+#include <stdlib.h>
+
+#include <boost/graph/undirected_dfs.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/graph_archetypes.hpp>
+#include <boost/graph/graph_utility.hpp>
+#include <boost/graph/random.hpp>
+
+#include <boost/random/mersenne_twister.hpp>
+
+template <typename ColorMap, typename ParentMap,
+  typename DiscoverTimeMap, typename FinishTimeMap>
+class dfs_test_visitor {
+  typedef typename boost::property_traits<ColorMap>::value_type ColorValue;
+  typedef typename boost::color_traits<ColorValue> Color;
+public:
+  dfs_test_visitor(ColorMap color, ParentMap p, DiscoverTimeMap d,
+                   FinishTimeMap f)
+    : m_color(color), m_parent(p),
+    m_discover_time(d), m_finish_time(f), m_time(0) { }
+
+  template <class Vertex, class Graph>
+  void initialize_vertex(Vertex u, Graph&) {
+    BOOST_CHECK( boost::get(m_color, u) == Color::white() );
+  }
+  template <class Vertex, class Graph>
+  void start_vertex(Vertex u, Graph&) {
+    BOOST_CHECK( boost::get(m_color, u) == Color::white() );
+  }
+  template <class Vertex, class Graph>
+  void discover_vertex(Vertex u, Graph&) {
+    using namespace boost;
+    BOOST_CHECK( get(m_color, u) == Color::gray() );
+    BOOST_CHECK( get(m_color, get(m_parent, u)) == Color::gray() );
+
+    put(m_discover_time, u, m_time++);
+  }
+  template <class Edge, class Graph>
+  void examine_edge(Edge e, Graph& g) {
+    using namespace boost;
+    BOOST_CHECK( get(m_color, source(e, g)) == Color::gray() );
+  }
+  template <class Edge, class Graph>
+  void tree_edge(Edge e, Graph& g) {
+    using namespace boost;
+    BOOST_CHECK( get(m_color, target(e, g)) == Color::white() );
+
+    put(m_parent, target(e, g), source(e, g));
+  }
+  template <class Edge, class Graph>
+  void back_edge(Edge e, Graph& g) {
+    using namespace boost;
+    BOOST_CHECK( get(m_color, target(e, g)) == Color::gray() );
+  }
+  template <class Edge, class Graph>
+  void forward_or_cross_edge(Edge e, Graph& g) {
+    using namespace boost;
+    BOOST_CHECK( get(m_color, target(e, g)) == Color::black() );
+  }
+  template <class Edge, class Graph>
+  void finish_edge(Edge e, Graph& g) {
+    using namespace boost;
+    BOOST_CHECK(
+        (get(m_color, target(e, g)) == Color::gray())
+     || (get(m_color, target(e, g)) == Color::black())
+    );
+  }
+  template <class Vertex, class Graph>
+  void finish_vertex(Vertex u, Graph&) {
+    using namespace boost;
+    BOOST_CHECK( get(m_color, u) == Color::black() );
+
+    put(m_finish_time, u, m_time++);
+  }
+private:
+  ColorMap m_color;
+  ParentMap m_parent;
+  DiscoverTimeMap m_discover_time;
+  FinishTimeMap m_finish_time;
+  typename boost::property_traits<DiscoverTimeMap>::value_type m_time;
+};
+
+template <typename Graph>
+struct dfs_test
+{
+  typedef boost::graph_traits<Graph> Traits;
+  typedef typename Traits::vertices_size_type
+    vertices_size_type;
+
+  static void go(vertices_size_type max_V) {
+    using namespace boost;
+    typedef typename Traits::vertex_descriptor vertex_descriptor;
+    typedef typename boost::property_map<Graph,
+      boost::vertex_color_t>::type ColorMap;
+    typedef typename boost::property_traits<ColorMap>::value_type ColorValue;
+    typedef typename boost::color_traits<ColorValue> Color;
+    typedef typename boost::property_map<Graph,
+      boost::edge_color_t>::type EColorMap;
+    typedef typename boost::property_traits<EColorMap>::value_type EColorValue;
+    typedef typename boost::color_traits<EColorValue> EColor;
+
+    vertices_size_type i, k;
+    typename Traits::edges_size_type j;
+    typename Traits::vertex_iterator vi, vi_end, ui, ui_end;
+    typename Traits::edge_iterator ei, ei_end;
+
+    boost::mt19937 gen;
+
+    for (i = 0; i < max_V; ++i)
+      for (j = 0; j < i*i; ++j) {
+        Graph g;
+        generate_random_graph(g, i, j, gen);
+
+        ColorMap color = get(boost::vertex_color, g);
+        EColorMap e_color = get(boost::edge_color, g);
+        std::vector<vertex_descriptor> parent(num_vertices(g));
+        for (k = 0; k < num_vertices(g); ++k)
+          parent[k] = k;
+        std::vector<int> discover_time(num_vertices(g)),
+          finish_time(num_vertices(g));
+
+        dfs_test_visitor<ColorMap, vertex_descriptor*,
+          int*, int*> vis(color, &parent[0],
+                          &discover_time[0], &finish_time[0]);
+
+        boost::undirected_dfs(g, visitor(vis).color_map(color)
+                              .edge_color_map(e_color));
+
+        // all vertices should be black
+        for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
+          BOOST_CHECK(get(color, *vi) == Color::black());
+
+        // all edges should be black
+        for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
+          BOOST_CHECK(get(e_color, *ei) == EColor::black());
+
+        // check parenthesis structure of discover/finish times
+        // See CLR p.480
+        for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
+          for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
+            vertex_descriptor u = *ui, v = *vi;
+            if (u != v) {
+              BOOST_CHECK( finish_time[u] < discover_time[v]
+                          || finish_time[v] < discover_time[u]
+                          || (discover_time[v] < discover_time[u]
+                               && finish_time[u] < finish_time[v]
+                               && boost::is_descendant(u, v, &parent[0]))
+                          || (discover_time[u] < discover_time[v]
+                               && finish_time[v] < finish_time[u]
+                               && boost::is_descendant(v, u, &parent[0]))
+                        );
+            }
+          }
+      }
+
+  }
+};
+
+
+// usage: undirected_dfs.exe [max-vertices=15]
+
+int test_main(int argc, char* argv[])
+{
+  int max_V = 7;
+  if (argc > 1)
+    max_V = atoi(argv[1]);
+
+  // Test undirected graphs.
+  dfs_test< boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
+           boost::property<boost::vertex_color_t, boost::default_color_type>,
+           boost::property<boost::edge_color_t, boost::default_color_type> >
+    >::go(max_V);
+
+  return 0;
+}
+