[Boost-commit] svn:boost r76849 - sandbox/metagraph/boost/metagraph/mpl_graph

Subject: [Boost-commit] svn:boost r76849 - sandbox/metagraph/boost/metagraph/mpl_graph
From: gordon_at_[hidden]
Date: 2012-02-03 00:46:40

Author: gordon.woodhull
Date: 2012-02-03 00:46:33 EST (Fri, 03 Feb 2012)
New Revision: 76849
URL: http://svn.boost.org/trac/boost/changeset/76849

Log:
search iterators
Text files modified: 
   sandbox/metagraph/boost/metagraph/mpl_graph/breadth_first_search.hpp |   280 ++++++++++++++++++++-----------------   
   sandbox/metagraph/boost/metagraph/mpl_graph/depth_first_search.hpp   |   296 +++++++++++++++++++++++++++------------ 
   2 files changed, 354 insertions(+), 222 deletions(-)

Modified: sandbox/metagraph/boost/metagraph/mpl_graph/breadth_first_search.hpp
==============================================================================
--- sandbox/metagraph/boost/metagraph/mpl_graph/breadth_first_search.hpp	(original)
+++ sandbox/metagraph/boost/metagraph/mpl_graph/breadth_first_search.hpp	2012-02-03 00:46:33 EST (Fri, 03 Feb 2012)
@@ -19,148 +19,168 @@
 #include "search_colors.hpp"
 
 namespace boost {
-namespace metagraph {
-namespace mpl_graph {
+  namespace metagraph {
+    namespace mpl_graph {
 
-// bfs takes a visitor which has all the bgl-like metafunctions encapsulated in an 
-// "operations" member class, and also a state.  the operations are expected to return a new state
-struct bfs_default_visitor_operations {
-    template<typename Vertex, typename Graph, typename State>
-    struct initialize_vertex {
-        typedef State type;       
-    };
-    
-    template<typename Vertex, typename Graph, typename State>
-    struct discover_vertex {
-        typedef State type;       
-    };
-    
-    template<typename Vertex, typename Graph, typename State>
-    struct examine_vertex {
-        typedef State type;       
-    };
-    
-    template<typename Vertex, typename Graph, typename State>
-    struct examine_edge {
-        typedef State type;       
-    };
+      // bfs takes a visitor which has all the bgl-like metafunctions encapsulated in an 
+      // "operations" member class, and also a state.  the operations are expected to return a new state
+      struct bfs_default_visitor_operations {
+        template<typename Vertex, typename Graph, typename State>
+        struct initialize_vertex {
+          typedef State type;       
+        };
+    
+        template<typename Vertex, typename Graph, typename State>
+        struct discover_vertex {
+          typedef State type;       
+        };
+    
+        template<typename Vertex, typename Graph, typename State>
+        struct examine_vertex {
+          typedef State type;       
+        };
+    
+        template<typename Vertex, typename Graph, typename State>
+        struct examine_edge {
+          typedef State type;       
+        };
         
-    template<typename Edge, typename Graph, typename State>
-    struct tree_edge {
-        typedef State type;
-    };
-    
-    template<typename Edge, typename Graph, typename State>
-    struct non_tree_edge {
-        typedef State type;
-    };
-    
-    template<typename Edge, typename Graph, typename State>
-    struct gray_target {
-        typedef State type;
-    };  
-    
-    template<typename Edge, typename Graph, typename State>
-    struct black_target {
-        typedef State type;
-    };  
-    
-    template<typename Vertex, typename Graph, typename State>
-    struct finish_vertex {
-        typedef State type;       
-    };
-};
-
-namespace detail {
-
-template<typename Graph, typename VisitorOps, typename VCQState, typename Edge>
-struct bfs_run_queue_examine_edge {
-    typedef typename VisitorOps::template examine_edge<Edge, Graph, typename mpl::at_c<VCQState, 0>::type>::type visitor_state;
-    typedef typename mpl::at_c<VCQState, 1>::type color_state;
-    typedef typename mpl::at_c<VCQState, 2>::type vertex_queue;
-
-    typedef typename mpl::if_<typename boost::is_same<typename search_color_map_ops::template get_color<typename mpl_graph::target<Edge, Graph>::type, color_state>::type, search_colors::White>::type,
-         // unseen target: tree edge, discover target, paint it gray, and enqueue
-         mpl::vector<typename VisitorOps::template discover_vertex<typename mpl_graph::target<Edge, Graph>::type, Graph,
-                                                                            typename VisitorOps::template tree_edge<Edge, Graph, visitor_state>::type>::type,
-                     typename search_color_map_ops::template set_color<typename mpl_graph::target<Edge, Graph>::type, search_colors::Gray, color_state>::type,
-                     typename mpl::push_back<vertex_queue, typename mpl_graph::target<Edge, Graph>::type >::type >,
-         // seen
-         mpl::vector<typename mpl::if_<typename boost::is_same<typename search_color_map_ops::template get_color<mpl_graph::target<Edge, Graph>, color_state>, 
-                                             search_colors::Gray>::type,
-                              typename VisitorOps::template gray_target<Edge, Graph, visitor_state>::type,
-                              typename VisitorOps::template black_target<Edge, Graph, visitor_state>::type>::type,
-                     color_state,
-                     vertex_queue> 
-         >::type type; 
-};
-
-// runs bfs on a queue, passing the new queue forward on recursion
-// returns pair<visitor_state, color_state>
-template<typename Graph, typename VertexQueue, typename VisitorOps, typename VisitorState, typename ColorMap>
-struct bfs_run_queue {
-    // enter vertex
-    typedef typename mpl::front<VertexQueue>::type Vertex;
-    typedef typename mpl::pop_front<VertexQueue>::type Tail;
-    typedef typename VisitorOps::template examine_vertex<Vertex, Graph, VisitorState>::type examined_state;
-    
-    // loop over out edges
-    typedef typename mpl::template 
-        fold<typename mpl_graph::out_edges<Vertex, Graph>::type, 
-             mpl::vector<examined_state, ColorMap, Tail>,
-             bfs_run_queue_examine_edge<Graph, VisitorOps, mpl::_1, mpl::_2>
-            >::type did_edges;
+        template<typename Edge, typename Graph, typename State>
+        struct tree_edge {
+          typedef State type;
+        };
+    
+        template<typename Edge, typename Graph, typename State>
+        struct non_tree_edge {
+          typedef State type;
+        };
+    
+        template<typename Edge, typename Graph, typename State>
+        struct gray_target {
+          typedef State type;
+        };  
+    
+        template<typename Edge, typename Graph, typename State>
+        struct black_target {
+          typedef State type;
+        };  
+    
+        template<typename Vertex, typename Graph, typename State>
+        struct finish_vertex {
+          typedef State type;       
+        };
+      };
+
+      namespace detail {
+
+        template<typename Graph, typename VisitorOps, typename VCQState, typename Edge>
+        struct bfs_run_queue_examine_edge {
+          typedef typename VisitorOps::template examine_edge<Edge, Graph, typename mpl::at_c<VCQState, 0>::type>::type visitor_state;
+          typedef typename mpl::at_c<VCQState, 1>::type color_state;
+          typedef typename mpl::at_c<VCQState, 2>::type vertex_queue;
+          typedef typename mpl_graph::target<Edge, Graph>::type target;
+          typedef typename search_color_map_ops::template get_color<target, color_state>::type color;
+
+          typedef typename 
+          mpl::if_<typename boost::is_same<color, search_colors::White>::type,
+                   // unseen target: tree edge, discover target, paint it gray, and enqueue
+                   mpl::vector<typename VisitorOps::template 
+                               discover_vertex<target, Graph,
+                                               typename VisitorOps::template 
+                                               tree_edge<Edge, Graph, visitor_state>::type>::type,
+                               typename search_color_map_ops::template 
+                               set_color<target, search_colors::Gray, color_state>::type,
+                               typename mpl::push_back<vertex_queue, target >::type >,
+                   // seen
+                   mpl::vector<typename mpl::if_<typename boost::is_same<color, search_colors::Gray>::type,
+                                                 typename VisitorOps::template 
+                                                 gray_target<Edge, Graph, visitor_state>::type,
+                                                 typename VisitorOps::template 
+                                                 black_target<Edge, Graph, visitor_state>::type>::type,
+                               color_state,
+                               vertex_queue> 
+                   >::type type; 
+        };
+        
+        // processes the front vertex from the queue
+        // returns <new_queue, visitor_state, color_state>
+        template<typename Graph, typename VertexQueue, typename VisitorOps, typename VisitorState, typename ColorMap>
+        struct bfs_process_node {
+          // enter vertex
+          typedef typename mpl::front<VertexQueue>::type Vertex;
+          typedef typename mpl::pop_front<VertexQueue>::type Tail;
+          typedef typename VisitorOps::template examine_vertex<Vertex, Graph, VisitorState>::type examined_state;
+    
+          // loop over out edges
+          typedef typename mpl::template 
+          fold<typename mpl_graph::out_edges<Vertex, Graph>::type, 
+               mpl::vector<examined_state, ColorMap, Tail>,
+               bfs_run_queue_examine_edge<Graph, VisitorOps, mpl::_1, mpl::_2>
+               >::type did_edges;
             
-    typedef typename VisitorOps::template 
-        finish_vertex<Vertex, Graph, typename mpl::at_c<did_edges, 0>::type>::type 
-            finished_vertex; 
-    // does map insert always overwrite?  i seem to remember this not working on msvc once
-    typedef typename search_color_map_ops::template 
-        set_color<Vertex, search_colors::Black, typename mpl::at_c<did_edges, 1>::type>::type 
-            colored_vertex;
-    typedef typename mpl::at_c<did_edges, 2>::type queued_targets;
-
-    typedef typename 
-        mpl::if_<typename mpl::empty<queued_targets>::type,
-                 mpl::pair<finished_vertex, colored_vertex>,
-                 bfs_run_queue<Graph, queued_targets,
-                               VisitorOps, finished_vertex,
-                               colored_vertex> >::type::type type;
-};
+          typedef typename VisitorOps::template 
+          finish_vertex<Vertex, Graph, typename mpl::at_c<did_edges, 0>::type>::type 
+          finished_vertex; 
+          // does map insert always overwrite?  i seem to remember this not working on msvc once
+          typedef typename search_color_map_ops::template 
+          set_color<Vertex, search_colors::Black, typename mpl::at_c<did_edges, 1>::type>::type 
+          colored_vertex;
+          typedef typename mpl::at_c<did_edges, 2>::type queued_targets;
 
-} // namespace detail
-
-template<typename Graph, typename VisitorOps, typename VisitorState, 
-         typename Vertex, 
-         typename ColorMap = create_search_color_map::type >
-struct breadth_first_search {
-    typedef typename VisitorOps::template 
-        discover_vertex<Vertex, Graph, VisitorState>::type 
-            discovered_state;
-    typedef typename search_color_map_ops::template 
-        set_color<Vertex, search_colors::Gray, ColorMap>::type 
-            discovered_colors;
-    typedef typename detail::
-        bfs_run_queue<Graph, mpl::vector<Vertex>, 
-                      VisitorOps, discovered_state, 
-                      discovered_colors>::type type;
+          typedef mpl::vector<queued_targets, finished_vertex, colored_vertex> type;
+        };
+        
+        struct bfs_end {};
+        template<typename Graph, typename VertexQueue, typename VisitorOps, typename VisitorState, typename ColorMap>
+        struct bfs_iter {
+          typedef typename bfs_process_node<Graph, VertexQueue, VisitorOps, VisitorState, ColorMap>::type eval;
+          typedef typename mpl::at_c<eval, 0>::type queue;
+          typedef typename mpl::at_c<eval, 1>::type visitor_state;
+          typedef typename mpl::at_c<eval, 2>::type color_map;
+          
+          typedef typename mpl::if_<typename mpl::empty<queue>::type,
+                           bfs_end,
+                           bfs_iter<Graph, queue, VisitorOps, visitor_state, color_map> >::type next;
+          typedef mpl::pair<visitor_state, color_map> type;
+        };
+          
+        template<typename BeginIter>
+        struct bfs_sequence {
+          typedef BeginIter begin;
+          typedef bfs_end end;
+        };
+    } // namespace detail
+
+    template<typename Graph, typename VisitorOps, typename VisitorState, 
+             typename Vertex, 
+             typename ColorMap = create_search_color_map::type >
+    struct breadth_first_search {
+      typedef typename VisitorOps::template 
+      discover_vertex<Vertex, Graph, VisitorState>::type 
+      discovered_state;
+      typedef typename search_color_map_ops::template 
+      set_color<Vertex, search_colors::Gray, ColorMap>::type 
+      discovered_colors;
+      typedef typename mpl::fold<detail::bfs_sequence<detail::bfs_iter<Graph, mpl::vector<Vertex>, VisitorOps, discovered_state, discovered_colors> >,
+                                 void,
+                                 mpl::_2>::type type;
 };
 
 template<typename Graph, typename VisitorOps, typename VisitorState,
          typename FirstVertex = typename mpl::front<typename mpl_graph::vertices<Graph>::type>::type,
          typename ColorMap = create_search_color_map::type>
 struct breadth_first_search_all : // visit "first" first, then visit any still white
-    mpl::fold<typename mpl_graph::vertices<Graph>::type,
-              typename breadth_first_search<Graph, VisitorOps, VisitorState, FirstVertex, ColorMap>::type,
-              mpl::if_<boost::is_same<search_color_map_ops::template get_color<mpl::_2, mpl::second<mpl::_1> >,
-                                      search_colors::White>,
-                       breadth_first_search<Graph, VisitorOps, mpl::first<mpl::_1>,
-                                            mpl::_2, mpl::second<mpl::_1> >,
-                       mpl::_1> >   
+        mpl::fold<typename mpl_graph::vertices<Graph>::type,
+                  typename breadth_first_search<Graph, VisitorOps, VisitorState, FirstVertex, ColorMap>::type,
+                  mpl::if_<boost::is_same<search_color_map_ops::template get_color<mpl::_2, mpl::second<mpl::_1> >,
+                                          search_colors::White>,
+                           breadth_first_search<Graph, VisitorOps, mpl::first<mpl::_1>,
+                                                mpl::_2, mpl::second<mpl::_1> >,
+                           mpl::_1> >   
 {};
 
-} // namespace mpl_graph
-} // namespace metagraph
+    } // namespace mpl_graph
+  } // namespace metagraph
 } // namespace boost
 
 

Modified: sandbox/metagraph/boost/metagraph/mpl_graph/depth_first_search.hpp
==============================================================================
--- sandbox/metagraph/boost/metagraph/mpl_graph/depth_first_search.hpp	(original)
+++ sandbox/metagraph/boost/metagraph/mpl_graph/depth_first_search.hpp	2012-02-03 00:46:33 EST (Fri, 03 Feb 2012)
@@ -12,110 +12,222 @@
 #include <boost/mpl/pair.hpp>
 #include <boost/mpl/map.hpp>
 #include <boost/mpl/has_key.hpp>
+#include <boost/mpl/pop_front.hpp>
+#include <boost/mpl/empty.hpp>
+#include <boost/mpl/quote.hpp>
+#include <boost/mpl/bool.hpp>
 
 #include "search_colors.hpp"
 
 namespace boost {
-namespace metagraph {
-namespace mpl_graph {
+  namespace metagraph {
+    namespace mpl_graph {
 
-// dfs takes a visitor which has all the bgl-like metafunctions encapsulated in an 
-// "operations" member class, and also a state.  the operations are expected to return a new state
-// in addition, the visitor operations are expected to update the colors of vertices
-// and need to support a new metafunction get_color<Vertex, State>
-
-struct dfs_default_visitor_operations {
-    template<typename Vertex, typename Graph, typename State>
-    struct initialize_vertex {
-        typedef State type;       
-    };
+      // dfs takes a visitor which has all the bgl-like metafunctions encapsulated in an 
+      // "operations" member class, and also a state.  the operations are expected to return a new state
+      // in addition, the visitor operations are expected to update the colors of vertices
+      // and need to support a new metafunction get_color<Vertex, State>
+
+      struct dfs_default_visitor_operations {
+        template<typename Vertex, typename Graph, typename State>
+        struct initialize_vertex {
+          typedef State type;       
+        };
     
-    template<typename Vertex, typename Graph, typename State>
-    struct discover_vertex {
-        typedef State type;       
-    };
+        template<typename Vertex, typename Graph, typename State>
+        struct discover_vertex {
+          typedef State type;       
+        };
     
-    template<typename Vertex, typename Graph, typename State>
-    struct finish_vertex {
-        typedef State type;       
-    };
+        template<typename Vertex, typename Graph, typename State>
+        struct finish_vertex {
+          typedef State type;       
+        };
         
-    template<typename Edge, typename Graph, typename State>
-    struct tree_edge {
-        typedef State type;
-    };
+        template<typename Edge, typename Graph, typename State>
+        struct tree_edge {
+          typedef State type;
+        };
     
-    template<typename Edge, typename Graph, typename State>
-    struct back_edge {
-        typedef State type;
-    };
+        template<typename Edge, typename Graph, typename State>
+        struct back_edge {
+          typedef State type;
+        };
     
-    template<typename Edge, typename Graph, typename State>
-    struct forward_or_cross_edge {
-        typedef State type;
-    };  
-};
-
-// requires IncidenceGraph
-// returns pair<VisitorState, ColorState>
-template<typename Graph, typename VisitorOps, typename VisitorState,
-         typename Vertex, 
-         typename ColorState = create_search_color_map::type >
-struct depth_first_search {
-    // enter vertex
-    typedef typename VisitorOps::template 
-        discover_vertex<Vertex, Graph, VisitorState>::type 
-            discovered_state;
-    typedef typename search_color_map_ops::template 
-        set_color<Vertex, search_colors::Gray, ColorState>::type 
-            discovered_colors;
+        template<typename Edge, typename Graph, typename State>
+        struct forward_or_cross_edge {
+          typedef State type;
+        };  
+      };
+
+      namespace detail {
+        template<typename Item, typename IsVertex, typename IsNew>
+        struct dfs_frame {
+          typedef Item item;
+          typedef IsVertex is_vertex;
+          typedef IsNew is_new;
+        };
+        template<typename Item, typename IsVertex, typename IsNew>
+        struct make_dfs_frame {
+          typedef dfs_frame<Item, IsVertex, IsNew> type; // surely there's an easier way to do this?
+        };
+
+        template<typename Graph, typename VisitorOps, typename Stack,
+                 typename VisitorState, typename ColorMap, typename Vertex>
+        struct dfs_step_in_vertex {
+          // enter vertex
+          typedef typename VisitorOps::template 
+          discover_vertex<Vertex, Graph, VisitorState>::type 
+          discovered_state;
+          // color it
+          typedef typename search_color_map_ops::template 
+          set_color<Vertex, search_colors::Gray, ColorMap>::type 
+          discovered_colors;
+
+          // put exit frame on stack
+          typedef typename mpl::push_front<Stack, dfs_frame<Vertex, mpl::true_, mpl::false_> >::type stack;
             
-    // loop over out edges
-    typedef typename 
-        mpl::fold<typename mpl_graph::out_edges<Vertex, Graph>::type, 
-                  mpl::pair<discovered_state, discovered_colors>,
-                  mpl::if_<boost::is_same<search_color_map_ops::get_color<mpl_graph::target<mpl::_2, Graph>, mpl::second<mpl::_1> >, 
-                                          search_colors::White>,
-                           // unseen target: recurse
-                           depth_first_search<Graph, 
-                                              VisitorOps, typename VisitorOps::template tree_edge<mpl::_2, Graph, mpl::first<mpl::_1> >, 
-                                              mpl_graph::target<mpl::_2, Graph>, 
-                                              mpl::second<mpl::_1> >,
-                           // seen: back or forward edge
-                           mpl::pair<mpl::if_<boost::is_same<typename search_color_map_ops::template 
-                                                 get_color<mpl_graph::target<mpl::_2, Graph>, mpl::second<mpl::_1 > >, 
-                                                 search_colors::Gray>,
-                                              typename VisitorOps::template back_edge<mpl::_2, Graph, mpl::first<mpl::_1> >,
-                                              typename VisitorOps::template forward_or_cross_edge<mpl::_2, Graph, mpl::first<mpl::_1> > >,  // Black
-                                     mpl::second<mpl::_1> > > 
-                 >::type after_outedges;
-                 
-    // leave vertex, and done!
-    typedef mpl::pair<typename VisitorOps::template finish_vertex<Vertex, Graph, typename mpl::first<after_outedges>::type >::type,
-                      typename search_color_map_ops::template set_color<Vertex, search_colors::Black, typename mpl::second<after_outedges>::type>::type> type;
-};
-
-// requires IncidenceGraph, VertexListGraph
-template<typename Graph, typename VisitorOps, typename VisitorState,
-         typename FirstVertex = typename mpl::front<typename mpl_graph::vertices<Graph>::type>::type,
-         typename ColorState = create_search_color_map::type>
-struct depth_first_search_all : // visit first then rest
-    mpl::fold<typename mpl_graph::vertices<Graph>::type,
-              typename depth_first_search<Graph, 
-                                          VisitorOps, VisitorState, 
-                                          FirstVertex, 
-                                          ColorState>::type, 
-              mpl::if_<boost::is_same<search_color_map_ops::get_color<mpl::_2, mpl::second<mpl::_1> >,
-                                      search_colors::White>, // visit any yet unvisited
-                       depth_first_search<Graph,
-                                 VisitorOps, mpl::first<mpl::_1>,
-                                 mpl::_2,
-                                 mpl::second<mpl::_1> >,
-                       mpl::_1> >   
-{};
+          // loop over out edges
+          typedef mpl::vector<typename 
+                              mpl::reverse_fold<typename 
+                                        mpl_graph::out_edges<Vertex, Graph>::type, 
+                                        stack,
+                                        mpl::push_front<mpl::_1, make_dfs_frame<mpl::_2, mpl::false_, mpl::false_> > >::type, 
+                              discovered_state, discovered_colors> type;
+        };
+        template<typename Graph, typename VisitorOps, typename Stack,
+                 typename VisitorState, typename ColorMap, typename Vertex>
+        struct dfs_step_out_vertex {
+          typedef mpl::vector<Stack,
+                              typename VisitorOps::template finish_vertex<Vertex, Graph, VisitorState>::type,
+                              typename search_color_map_ops::template set_color<Vertex, search_colors::Black, ColorMap>::type> type;
+        };
+        template<typename Graph, typename VisitorOps, typename Stack,
+                 typename VisitorState, typename ColorMap, typename Edge, typename Target>
+        struct dfs_unseen_target :
+          mpl::vector<typename mpl::push_front<Stack, dfs_frame<Target, mpl::true_, mpl::true_> >::type,
+                      typename VisitorOps::template tree_edge<Edge, Graph, VisitorState >::type, 
+                      ColorMap> {};
+        template<typename Graph, typename VisitorOps, typename Stack,
+                 typename VisitorState, typename ColorMap, typename Edge, typename Color>
+        struct dfs_seen_target :
+          mpl::vector<Stack,
+                      typename
+                      mpl::eval_if<typename boost::is_same<Color, search_colors::Gray>::type,
+                                   typename VisitorOps::template back_edge<Edge, Graph, VisitorState >,
+                                   typename VisitorOps::template forward_or_cross_edge<Edge, Graph, VisitorState > // Black
+                                   >::type, 
+                      ColorMap> {};
+        template<typename Graph, typename VisitorOps, typename Stack,
+                 typename VisitorState, typename ColorMap, typename Edge>
+        struct dfs_step_edge {
+          typedef typename mpl_graph::target<Edge, Graph>::type target;
+          typedef typename search_color_map_ops::get_color<target, ColorMap >::type color;
+          typedef typename 
+          mpl::eval_if<typename boost::is_same<color, search_colors::White>::type,
+                       // unseen target: put it on stack
+                       dfs_unseen_target<Graph, VisitorOps, Stack, VisitorState, ColorMap, Edge, target>,
+                       // seen: back or forward edge
+                       dfs_seen_target<Graph, VisitorOps, Stack, VisitorState, ColorMap, Edge, color>
+                        >::type type;
+        };
+                                     
+          
+        template<typename T> struct err_it;
+         
+        template<typename Frame, typename Graph, typename VisitorOps, typename Stack,
+                 typename VisitorState, typename ColorMap>
+        struct dispatch_frame;
+
+
+        template<typename Item, typename Graph, typename VisitorOps, typename Stack,
+               typename VisitorState, typename ColorMap>
+        struct dispatch_frame<dfs_frame<Item, mpl::true_, mpl::true_>, 
+                              Graph, VisitorOps, Stack,
+                              VisitorState, ColorMap> :
+        dfs_step_in_vertex<Graph, VisitorOps, Stack,
+                           VisitorState, ColorMap, Item> {};
+ 
+
+        template<typename Item, typename Graph, typename VisitorOps, typename Stack,
+               typename VisitorState, typename ColorMap>
+        struct dispatch_frame<dfs_frame<Item, mpl::true_, mpl::false_>, 
+                              Graph, VisitorOps, Stack,
+                              VisitorState, ColorMap> :
+        dfs_step_out_vertex<Graph, VisitorOps, Stack,
+                            VisitorState, ColorMap, Item> {};
+        
+
+        template<typename Item, typename Graph, typename VisitorOps, typename Stack,
+                 typename VisitorState, typename ColorMap, typename Unused>
+        struct dispatch_frame<dfs_frame<Item, mpl::false_, Unused>, 
+                              Graph, VisitorOps, Stack,
+                              VisitorState, ColorMap> :
+        dfs_step_edge<Graph, VisitorOps, Stack,
+                      VisitorState, ColorMap, Item> {};
+ 
+        template<typename Graph, typename VisitorOps, typename Stack,
+                 typename VisitorState, typename ColorMap>
+        struct dfs_step {
+          typedef typename mpl::pop_front<Stack>::type stack;
+          typedef typename mpl::front<Stack>::type frame;
+          //typedef typename err_it<frame>::type foo;
+          typedef typename dispatch_frame<frame, Graph, VisitorOps, stack, VisitorState, ColorMap>::type type;
+        };
+        
+        struct dfs_end {};
+        template<typename Graph, typename VisitorOps, typename Stack,
+                 typename VisitorState, typename ColorMap>
+        struct dfs_iter {
+          typedef typename dfs_step<Graph, VisitorOps, Stack, VisitorState, ColorMap>::type eval;
+          typedef typename mpl::at_c<eval, 0>::type stack;
+          typedef typename mpl::at_c<eval, 1>::type visitor_state;
+          typedef typename mpl::at_c<eval, 2>::type color_map;
+
+          typedef typename mpl::if_<typename mpl::empty<stack>::type,
+                                    dfs_end,
+                                    dfs_iter<Graph, VisitorOps, stack, visitor_state, color_map> >::type next;
+          typedef mpl::pair<visitor_state, color_map> type;
+        };
+        template<typename BeginIter>
+        struct dfs_sequence {
+          typedef BeginIter begin;
+          typedef dfs_end end;
+        };
+      }
+      // requires IncidenceGraph
+      // returns pair<VisitorState, ColorMap>
+      template<typename Graph, typename VisitorOps, typename VisitorState,
+               typename Vertex, 
+               typename ColorMap = create_search_color_map::type >
+      struct depth_first_search {
+        typedef mpl::vector<detail::dfs_frame<Vertex, mpl::true_, mpl::true_> > stack;
+        typedef typename mpl::fold<detail::dfs_sequence<detail::dfs_iter<Graph, VisitorOps, stack, VisitorState, ColorMap> >,
+                                   void,
+                                   mpl::_2>::type type;
+      };
+
+      // requires IncidenceGraph, VertexListGraph
+      template<typename Graph, typename VisitorOps, typename VisitorState,
+               typename FirstVertex = typename mpl::front<typename mpl_graph::vertices<Graph>::type>::type,
+               typename ColorMap = create_search_color_map::type>
+      struct depth_first_search_all : // visit first then rest
+      mpl::fold<typename mpl_graph::vertices<Graph>::type,
+                typename depth_first_search<Graph, 
+                                            VisitorOps, VisitorState, 
+                                            FirstVertex, 
+                                            ColorMap>::type, 
+                mpl::if_<boost::is_same<search_color_map_ops::get_color<mpl::_2, mpl::second<mpl::_1> >,
+                                        search_colors::White>, // visit any yet unvisited
+                         depth_first_search<Graph,
+                                            VisitorOps, mpl::first<mpl::_1>,
+                                            mpl::_2,
+                                            mpl::second<mpl::_1> >,
+                         mpl::_1> >   
+      {};
 
-} // namespace mpl_graph
-} // namespace metagraph
+    } // namespace mpl_graph
+  } // namespace metagraph
 } // namespace boost