[Boost-commit] svn:boost r61929 - in sandbox/metagraph: boost/metagraph/mpl_graph libs/metagraph/example

Subject: [Boost-commit] svn:boost r61929 - in sandbox/metagraph: boost/metagraph/mpl_graph libs/metagraph/example
From: gordon_at_[hidden]
Date: 2010-05-12 03:12:04

Author: gordon.woodhull
Date: 2010-05-12 03:12:02 EDT (Wed, 12 May 2010)
New Revision: 61929
URL: http://svn.boost.org/trac/boost/changeset/61929

Log:
breadth first search
Added:
   sandbox/metagraph/boost/metagraph/mpl_graph/breadth_first_search.hpp   (contents, props changed)
   sandbox/metagraph/boost/metagraph/mpl_graph/search_colors.hpp   (contents, props changed)
   sandbox/metagraph/boost/metagraph/mpl_graph/search_state_and_operations.hpp   (contents, props changed)
   sandbox/metagraph/libs/metagraph/example/breadth_first_search.cpp   (contents, props changed)
Text files modified: 
   sandbox/metagraph/boost/metagraph/mpl_graph/depth_first_search.hpp |    57 +++++++++++---------------------------- 
   sandbox/metagraph/libs/metagraph/example/depth_first_search.cpp    |    12 ++++----                                
   2 files changed, 23 insertions(+), 46 deletions(-)

Added: sandbox/metagraph/boost/metagraph/mpl_graph/breadth_first_search.hpp
==============================================================================
--- (empty file)
+++ sandbox/metagraph/boost/metagraph/mpl_graph/breadth_first_search.hpp	2010-05-12 03:12:02 EDT (Wed, 12 May 2010)
@@ -0,0 +1,158 @@
+#ifndef BOOST_METAGRAPH_MPL_GRAPH_BREADTH_FIRST_SEARCH_HPP_INCLUDED
+#define BOOST_METAGRAPH_MPL_GRAPH_BREADTH_FIRST_SEARCH_HPP_INCLUDED
+
+#include <boost/metagraph/mpl_graph/mpl_graph.hpp>
+
+#include <boost/mpl/has_key.hpp>
+#include <boost/mpl/insert.hpp>
+#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/remove.hpp>
+
+#include "search_colors.hpp"
+#include "search_state_and_operations.hpp"
+
+namespace boost {
+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;       
+    };
+        
+    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;       
+    };
+};
+
+template<typename Graph, typename VisitorOps, typename ColorOps, typename State, typename Edge>
+struct bfs_run_queue_examine_edge {
+    typedef typename VisitorOps::template examine_edge<Edge, Graph, typename mpl::at_c<State, 0>::type>::type visitor_state;
+    typedef typename mpl::at_c<State, 1>::type color_state;
+    typedef typename mpl::at_c<State, 2>::type vertex_queue;
+
+    typedef typename mpl::if_<typename boost::is_same<typename ColorOps::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 ColorOps::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 ColorOps::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; 
+};
+template<typename Graph, typename VertexQueue, typename Visitor, typename ColorMap>
+struct bfs_run_queue;
+
+
+// runs bfs on a queue, passing the new queue forward on recursion
+// returns pair<visitor_state, color_state>
+template<typename Graph, typename VertexQueue, typename Visitor, 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 Visitor::operations::template examine_vertex<Vertex, Graph, typename Visitor::state>::type examined_state;
+    
+    // loop over out edges
+    typedef typename mpl::template 
+        fold<typename mpl_graph::out_edges<Vertex, Graph>::type, 
+             mpl::vector<examined_state, typename ColorMap::state, Tail>,
+             bfs_run_queue_examine_edge<Graph, typename Visitor::operations, typename ColorMap::operations, mpl::_1, mpl::_2>
+            >::type did_edges;
+            
+    typedef typename Visitor::operations::template finish_vertex<Vertex, Graph, typename mpl::at_c<did_edges, 0>::type>::type finished_vertex; 
+    typedef typename ColorMap::operations::template set_color<Vertex, search_colors::Black, 
+            //typename mpl::remove<
+            typename mpl::at_c<did_edges, 1>::type
+            //, Vertex>::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,
+                                   search_state_and_operations<finished_vertex, typename Visitor::operations>,
+                                   search_state_and_operations<colored_vertex, typename ColorMap::operations> > >::type::type 
+                         type;
+};
+
+template<typename Graph, typename Vertex, typename Visitor, 
+         typename ColorMap = search_state_and_operations<create_search_color_map::type, search_color_map_operations> >
+struct breadth_first_search {
+    typedef typename Visitor::operations::template discover_vertex<Vertex, Graph, typename Visitor::state>::type discovered_state;
+    typedef typename ColorMap::operations::template set_color<Vertex, search_colors::Gray, typename ColorMap::state>::type discovered_colors;
+    typedef typename bfs_run_queue<Graph, mpl::vector<Vertex>, 
+                          search_state_and_operations<discovered_state, typename Visitor::operations>, 
+                          search_state_and_operations<discovered_colors, typename ColorMap::operations> >::type type;
+};
+
+template<typename Graph, typename Visitor,
+         typename Vertex = typename mpl::front<typename mpl_graph::vertices<Graph>::type>::type,
+         typename ColorMap = search_state_and_operations<create_search_color_map::type, search_color_map_operations> >
+struct breadth_first_search_all :
+    mpl::fold<typename mpl_graph::vertices<Graph>::type,
+              typename breadth_first_search<Graph, Vertex, Visitor, ColorMap>::type,
+              mpl::if_<boost::is_same<typename ColorMap::operations::template get_color<mpl::_2, mpl::second<mpl::_1> >,
+                                      search_colors::White>,
+                       breadth_first_search<Graph,
+                                 mpl::_2,
+                                 search_state_and_operations<mpl::first<mpl::_1>, typename Visitor::operations>,
+                                 search_state_and_operations<mpl::second<mpl::_1>, typename ColorMap::operations> >,
+                       mpl::_1> >   
+{};
+
+} // namespace mpl_graph
+} // namespace metagraph
+} // namespace boost
+
+
+#endif // BOOST_METAGRAPH_MPL_GRAPH_BREADTH_FIRST_SEARCH_HPP_INCLUDED

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	2010-05-12 03:12:02 EDT (Wed, 12 May 2010)
@@ -9,25 +9,13 @@
 #include <boost/mpl/map.hpp>
 #include <boost/mpl/has_key.hpp>
 
+#include "search_colors.hpp"
+#include "search_state_and_operations.hpp"
+
 namespace boost {
 namespace metagraph {
 namespace mpl_graph {
 
-struct dfs_colors {
-    struct White {};
-    struct Grey {};
-    struct Black {};
-};
-
-// as with all mpl algorithms, state must be carried along
-// because metadata is immutable.  so we do something like the mpl inserter pattern, 
-// only there are many operations, which we stick in a blob (? not sure how to avoid this)
-template<typename State, typename Operations>
-struct state_and_operations {
-    typedef State state;
-    typedef Operations operations;
-};
-
 // 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
@@ -53,73 +41,62 @@
     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 forward_or_cross_edge {
         typedef State type;
     };  
 };
 
-struct dfs_color_map_operations {
-    template<typename Node, typename Color, typename State>
-    struct set_color :
-        mpl::insert<State, mpl::pair<Node, Color> >
-    {};
-    template<typename Node, typename State>
-    struct get_color :
-        mpl::if_<mpl::has_key<State, Node>,
-                 mpl::at<State, Node>,
-                 dfs_colors::White>
-    {};
-};
-
 // visitor is operations, state as described above
 // however this returns pair< visitor_state, color_state >
 template<typename Graph, typename Node, typename Visitor, 
-         typename ColorMap = state_and_operations<mpl::map<>, dfs_color_map_operations> >
+         typename ColorMap = search_state_and_operations<create_search_color_map::type, search_color_map_operations> >
 struct dfs_visit {
     // enter vertex
     typedef typename Visitor::operations::template discover_vertex<Node, Graph, typename Visitor::state>::type discovered_state;
-    typedef typename ColorMap::operations::template set_color<Node, dfs_colors::Grey, typename ColorMap::state>::type discovered_colors;
+    typedef typename ColorMap::operations::template set_color<Node, search_colors::Gray, typename ColorMap::state>::type discovered_colors;
     // loop over out edges
     typedef typename mpl::template 
         fold<typename mpl_graph::out_edges<Node, Graph>::type, 
              mpl::pair<discovered_state, discovered_colors>,
              mpl::if_<boost::is_same<typename ColorMap::operations::template get_color<mpl_graph::target<mpl::_2, Graph>, mpl::second<mpl::_1 > >, 
-                                     dfs_colors::White>,
+                                     search_colors::White>,
                       // unseen target: recurse
                       dfs_visit<Graph, 
                                 mpl_graph::target<mpl::_2, Graph>, 
-                                state_and_operations<typename Visitor::operations::template tree_edge<mpl::_2, Graph, mpl::first<mpl::_1> >, 
+                                search_state_and_operations<typename Visitor::operations::template tree_edge<mpl::_2, Graph, mpl::first<mpl::_1> >, 
                                                      typename Visitor::operations>,
-                                state_and_operations<mpl::second<mpl::_1>, typename ColorMap::operations> >,
+                                search_state_and_operations<mpl::second<mpl::_1>, typename ColorMap::operations> >,
                       // seen: back or forward edge
-                      mpl::pair<mpl::if_<boost::is_same<typename ColorMap::operations::template get_color<mpl_graph::target<mpl::_2, Graph>, mpl::second<mpl::_1 > >, dfs_colors::Grey>,
+                      mpl::pair<mpl::if_<boost::is_same<typename ColorMap::operations::template get_color<mpl_graph::target<mpl::_2, Graph>, mpl::second<mpl::_1 > >, search_colors::Gray>,
                                          typename Visitor::operations::template back_edge<mpl::_2, Graph, mpl::first<mpl::_1> >,
-                                         typename Visitor::operations::template forward_or_cross_edge<mpl::_2, Graph, mpl::first<mpl::_1> > >, 
+                                         typename Visitor::operations::template forward_or_cross_edge<mpl::_2, Graph, mpl::first<mpl::_1> > >,  // Black
                                 mpl::second<mpl::_1> >
                       > 
              >::type visited_state_and_colors;
     // leave vertex, and done!
     typedef mpl::pair<typename Visitor::operations::template finish_vertex<Node, Graph, typename mpl::first<visited_state_and_colors>::type >::type,
-                      typename ColorMap::operations::template set_color<Node, dfs_colors::Black, typename mpl::second<visited_state_and_colors>::type>::type> type;
+                      typename ColorMap::operations::template set_color<Node, search_colors::Black, typename mpl::second<visited_state_and_colors>::type>::type> type;
 };
 
 template<typename Graph, typename Visitor,
          typename FirstVertex = typename mpl::front<typename mpl_graph::vertices<Graph>::type>::type,
-         typename ColorMap = state_and_operations<mpl::map<>, dfs_color_map_operations> >
+         typename ColorMap = search_state_and_operations<create_search_color_map::type, search_color_map_operations> >
 struct depth_first_search :
     mpl::fold<typename mpl_graph::vertices<Graph>::type,
               typename dfs_visit<Graph, FirstVertex, Visitor, ColorMap>::type,
               mpl::if_<boost::is_same<typename ColorMap::operations::template get_color<mpl::_2, mpl::second<mpl::_1> >,
-                                      dfs_colors::White>,
+                                      search_colors::White>,
                        dfs_visit<Graph,
                                  mpl::_2,
-                                 state_and_operations<mpl::first<mpl::_1>, typename Visitor::operations>,
-                                 state_and_operations<mpl::second<mpl::_1>, typename ColorMap::operations> >,
+                                 search_state_and_operations<mpl::first<mpl::_1>, typename Visitor::operations>,
+                                 search_state_and_operations<mpl::second<mpl::_1>, typename ColorMap::operations> >,
                        mpl::_1> >   
 {};
 

Added: sandbox/metagraph/boost/metagraph/mpl_graph/search_colors.hpp
==============================================================================
--- (empty file)
+++ sandbox/metagraph/boost/metagraph/mpl_graph/search_colors.hpp	2010-05-12 03:12:02 EDT (Wed, 12 May 2010)
@@ -0,0 +1,35 @@
+#ifndef BOOST_METAGRAPH_MPL_GRAPH_SEARCH_COLORS_HPP_INCLUDED
+#define BOOST_METAGRAPH_MPL_GRAPH_SEARCH_COLORS_HPP_INCLUDED
+
+namespace boost {
+namespace metagraph {
+namespace mpl_graph {
+
+struct search_colors {
+    struct White {};
+    struct Gray {};
+    struct Black {};
+};
+
+struct create_search_color_map : mpl::map<> {};
+
+struct search_color_map_operations {
+    template<typename Node, typename Color, typename State>
+    struct set_color :
+        mpl::insert<State, mpl::pair<Node, Color> >
+    {};
+    template<typename Node, typename State>
+    struct get_color :
+        mpl::if_<mpl::has_key<State, Node>,
+                 mpl::at<State, Node>,
+                 search_colors::White>
+    {};
+};
+
+
+} // namespace mpl_graph
+} // namespace metagraph
+} // namespace boost
+
+
+#endif // BOOST_METAGRAPH_MPL_GRAPH_SEARCH_COLORS_HPP_INCLUDED

Added: sandbox/metagraph/boost/metagraph/mpl_graph/search_state_and_operations.hpp
==============================================================================
--- (empty file)
+++ sandbox/metagraph/boost/metagraph/mpl_graph/search_state_and_operations.hpp	2010-05-12 03:12:02 EDT (Wed, 12 May 2010)
@@ -0,0 +1,24 @@
+#ifndef BOOST_METAGRAPH_MPL_GRAPH_SEARCH_STATE_AND_OPERATIONS_HPP_INCLUDED
+#define BOOST_METAGRAPH_MPL_GRAPH_SEARCH_STATE_AND_OPERATIONS_HPP_INCLUDED
+
+namespace boost {
+namespace metagraph {
+namespace mpl_graph {
+
+
+// as with all mpl algorithms, state must be carried along
+// because metadata is immutable.  so we do something like the mpl inserter pattern, 
+// only there are many operations, which we stick in a blob (? not sure how to avoid this)
+template<typename State, typename Operations>
+struct search_state_and_operations {
+    typedef State state;
+    typedef Operations operations;
+};
+
+
+} // namespace mpl_graph
+} // namespace metagraph
+} // namespace boost
+
+
+#endif // BOOST_METAGRAPH_MPL_GRAPH_SEARCH_STATE_AND_OPERATIONS_HPP_INCLUDED

Added: sandbox/metagraph/libs/metagraph/example/breadth_first_search.cpp
==============================================================================
--- (empty file)
+++ sandbox/metagraph/libs/metagraph/example/breadth_first_search.cpp	2010-05-12 03:12:02 EDT (Wed, 12 May 2010)
@@ -0,0 +1,152 @@
+#include <boost/metagraph/mpl_graph/breadth_first_search.hpp>
+#include <boost/metagraph/mpl_graph/adjacency_list_graph.hpp>
+#include <boost/metagraph/mpl_graph/incidence_list_graph.hpp>
+
+#include <iostream>
+
+namespace mpl_graph = boost::metagraph::mpl_graph;
+namespace mpl = boost::mpl;
+
+// vertices
+struct A{}; struct B{}; struct C{}; struct D{}; struct E{}; struct F{}; struct G{};
+
+// edges
+struct A_B{}; struct B_C{}; struct C_D{}; struct C_E{}; struct C_F{}; struct B_F{};
+
+
+
+/* 
+    incidence list test graph:
+    A -> B -> C -\--> D
+           \     |--> E
+            \    \--> F
+             \-----/
+*/           
+
+typedef mpl::vector<mpl::vector<A_B,A,B>,
+               mpl::vector<B_C,B,C>,
+               mpl::vector<C_D,C,D>,
+               mpl::vector<C_E,C,E>,
+               mpl::vector<C_F,C,F>,
+               mpl::vector<B_F,B,F> >
+    some_incidence_list;
+typedef mpl_graph::incidence_list_graph<some_incidence_list> some_incidence_list_graph;
+
+
+
+/* 
+    adjacency list test graph:
+    A -> B -> C -\--> D
+           \     |--> E
+            \    \--> F
+             \-----/
+    G
+*/           
+
+typedef mpl::vector<
+            mpl::pair<A, mpl::vector<mpl::pair<A_B, B> > >,
+            mpl::pair<B, mpl::vector<mpl::pair<B_C, C>,
+                                     mpl::pair<B_F, F> > >,
+            mpl::pair<C, mpl::vector<mpl::pair<C_D, D>,
+                                     mpl::pair<C_E, E>,
+                                     mpl::pair<C_F, F> > >,
+            mpl::pair<G, mpl::vector<> > >
+    some_adjacency_list;
+typedef mpl_graph::adjacency_list_graph<some_adjacency_list> some_adjacency_list_graph;
+
+
+struct preordering_visitor : mpl_graph::bfs_default_visitor_operations {    
+    template<typename Vertex, typename Graph, typename State>
+    struct discover_vertex :
+        mpl::push_back<State, Vertex>
+    {};
+};
+
+struct postordering_visitor : mpl_graph::bfs_default_visitor_operations {    
+    template<typename Vertex, typename Graph, typename State>
+    struct finish_vertex :
+        mpl::push_back<State, Vertex>
+    {};
+};
+
+struct examine_edge_visitor : mpl_graph::bfs_default_visitor_operations {    
+    template<typename Edge, typename Graph, typename State>
+    struct examine_edge :
+        mpl::push_back<State, Edge>
+    {};
+};
+
+struct tree_edge_visitor : mpl_graph::bfs_default_visitor_operations {    
+    template<typename Edge, typename Graph, typename State>
+    struct tree_edge :
+        mpl::push_back<State, Edge>
+    {};
+};
+  
+// adjacency list tests
+
+// preordering, start from A
+typedef mpl::first<mpl_graph::breadth_first_search<some_adjacency_list_graph, A, mpl_graph::search_state_and_operations<mpl::vector<>, preordering_visitor > >::type>::type preorder_adj_a;
+BOOST_MPL_ASSERT(( mpl::equal<preorder_adj_a::type, mpl::vector<A,B,C,F,D,E> > ));
+
+// examine edges, start from A
+typedef mpl::first<mpl_graph::breadth_first_search<some_adjacency_list_graph, A, mpl_graph::search_state_and_operations<mpl::vector<>, examine_edge_visitor > >::type>::type ex_edges_adj_a;
+BOOST_MPL_ASSERT(( mpl::equal<ex_edges_adj_a::type, mpl::vector<A_B,B_C,B_F,C_D,C_E,C_F> > ));
+
+// tree edges, start from A
+typedef mpl::first<mpl_graph::breadth_first_search<some_adjacency_list_graph, A, mpl_graph::search_state_and_operations<mpl::vector<>, tree_edge_visitor > >::type>::type tree_edges_adj_a;
+BOOST_MPL_ASSERT(( mpl::equal<tree_edges_adj_a::type, mpl::vector<A_B,B_C,B_F,C_D,C_E> > ));
+
+// preordering, search all, default start node (first)
+typedef mpl::first<mpl_graph::breadth_first_search_all<some_adjacency_list_graph,mpl_graph::search_state_and_operations<mpl::vector<>, preordering_visitor > >::type>::type preorder_adj;
+BOOST_MPL_ASSERT(( mpl::equal<preorder_adj::type, mpl::vector<A,B,C,F,D,E,G> > ));
+
+// postordering, starting at A (same as preordering because BFS fully processes one vertex b4 moving to next)
+typedef mpl::first<mpl_graph::breadth_first_search<some_adjacency_list_graph,A,mpl_graph::search_state_and_operations<mpl::vector<>, postordering_visitor > >::type>::type postorder_adj_a;
+BOOST_MPL_ASSERT(( mpl::equal<postorder_adj_a::type, mpl::vector<A,B,C,F,D,E> > ));
+
+// postordering, default start node (same as preordering because BFS fully processes one vertex b4 moving to next)
+typedef mpl::first<mpl_graph::breadth_first_search_all<some_adjacency_list_graph,mpl_graph::search_state_and_operations<mpl::vector<>, postordering_visitor > >::type>::type postorder_adj;
+BOOST_MPL_ASSERT(( mpl::equal<postorder_adj::type, mpl::vector<A,B,C,F,D,E,G> > ));
+
+// preordering starting at C
+typedef mpl::first<mpl_graph::breadth_first_search<some_adjacency_list_graph, C,
+                                                 mpl_graph::search_state_and_operations<mpl::vector<>, preordering_visitor >
+                                                 >::type>::type preorder_adj_from_c;
+BOOST_MPL_ASSERT(( mpl::equal<preorder_adj_from_c::type, mpl::vector<C,D,E,F> > ));
+
+// preordering, search all, starting at C
+typedef mpl::first<mpl_graph::breadth_first_search_all<some_adjacency_list_graph,
+                                                 mpl_graph::search_state_and_operations<mpl::vector<>, preordering_visitor >,
+                                                 C>::type>::type preorder_adj_from_c_all;
+BOOST_MPL_ASSERT(( mpl::equal<preorder_adj_from_c_all::type, mpl::vector<C,D,E,F,A,B,G> > ));
+
+
+// incidence list tests
+
+// preordering, start from A
+typedef mpl::first<mpl_graph::breadth_first_search<some_incidence_list_graph, A, mpl_graph::search_state_and_operations<mpl::vector<>, preordering_visitor > >::type>::type preorder_inc_a;
+BOOST_MPL_ASSERT(( mpl::equal<preorder_inc_a::type, mpl::vector<A,B,C,F,D,E> > ));
+
+// preordering, start from C
+typedef mpl::first<mpl_graph::breadth_first_search<some_incidence_list_graph, C, mpl_graph::search_state_and_operations<mpl::vector<>, preordering_visitor > >::type>::type preorder_inc_c;
+BOOST_MPL_ASSERT(( mpl::equal<preorder_inc_c::type, mpl::vector<C,D,E,F> > ));
+
+// preordering, default start node (first)
+typedef mpl::first<mpl_graph::breadth_first_search_all<some_incidence_list_graph,mpl_graph::search_state_and_operations<mpl::vector<>, preordering_visitor > >::type>::type preorder_inc;
+BOOST_MPL_ASSERT(( mpl::equal<preorder_inc::type, mpl::vector<A,B,C,F,D,E> > ));
+
+// postordering, default start node
+typedef mpl::first<mpl_graph::breadth_first_search_all<some_incidence_list_graph,mpl_graph::search_state_and_operations<mpl::vector<>, postordering_visitor > >::type>::type postorder_inc;
+BOOST_MPL_ASSERT(( mpl::equal<postorder_inc::type, mpl::vector<A,B,C,F,D,E> > ));
+
+// preordering, search all, starting at C
+typedef mpl::first<mpl_graph::breadth_first_search_all<some_incidence_list_graph,
+                                                 mpl_graph::search_state_and_operations<mpl::vector<>, preordering_visitor >,
+                                                 C>::type>::type preorder_inc_from_c;
+BOOST_MPL_ASSERT(( mpl::equal<preorder_inc_from_c::type, mpl::vector<C,D,E,F,A,B> > ));
+
+
+int main() {
+    return 0;
+}
\ No newline at end of file

Modified: sandbox/metagraph/libs/metagraph/example/depth_first_search.cpp
==============================================================================
--- sandbox/metagraph/libs/metagraph/example/depth_first_search.cpp	(original)
+++ sandbox/metagraph/libs/metagraph/example/depth_first_search.cpp	2010-05-12 03:12:02 EDT (Wed, 12 May 2010)
@@ -73,16 +73,16 @@
 // adjacency list tests
 
 // preordering, default start node (first)
-typedef mpl::first<mpl_graph::depth_first_search<some_adjacency_list_graph,mpl_graph::state_and_operations<mpl::vector<>, preordering_visitor > >::type>::type preorder_adj;
+typedef mpl::first<mpl_graph::depth_first_search<some_adjacency_list_graph,mpl_graph::search_state_and_operations<mpl::vector<>, preordering_visitor > >::type>::type preorder_adj;
 BOOST_MPL_ASSERT(( mpl::equal<preorder_adj::type, mpl::vector<A,B,C,D,E,F,G> > ));
 
 // postordering, default start node
-typedef mpl::first<mpl_graph::depth_first_search<some_adjacency_list_graph,mpl_graph::state_and_operations<mpl::vector<>, postordering_visitor > >::type>::type postorder_adj;
+typedef mpl::first<mpl_graph::depth_first_search<some_adjacency_list_graph,mpl_graph::search_state_and_operations<mpl::vector<>, postordering_visitor > >::type>::type postorder_adj;
 BOOST_MPL_ASSERT(( mpl::equal<postorder_adj::type, mpl::vector<D,E,F,C,B,A,G> > ));
 
 // preordering starting at C
 typedef mpl::first<mpl_graph::depth_first_search<some_adjacency_list_graph,
-                                                 mpl_graph::state_and_operations<mpl::vector<>, preordering_visitor >,
+                                                 mpl_graph::search_state_and_operations<mpl::vector<>, preordering_visitor >,
                                                  C>::type>::type preorder_adj_from_c;
 BOOST_MPL_ASSERT(( mpl::equal<preorder_adj_from_c::type, mpl::vector<C,D,E,F,A,B,G> > ));
 
@@ -90,16 +90,16 @@
 // incidence list tests
 
 // preordering, default start node (first)
-typedef mpl::first<mpl_graph::depth_first_search<some_incidence_list_graph,mpl_graph::state_and_operations<mpl::vector<>, preordering_visitor > >::type>::type preorder_inc;
+typedef mpl::first<mpl_graph::depth_first_search<some_incidence_list_graph,mpl_graph::search_state_and_operations<mpl::vector<>, preordering_visitor > >::type>::type preorder_inc;
 BOOST_MPL_ASSERT(( mpl::equal<preorder_inc::type, mpl::vector<A,B,C,D,E,F> > ));
 
 // postordering, default start node
-typedef mpl::first<mpl_graph::depth_first_search<some_incidence_list_graph,mpl_graph::state_and_operations<mpl::vector<>, postordering_visitor > >::type>::type postorder_inc;
+typedef mpl::first<mpl_graph::depth_first_search<some_incidence_list_graph,mpl_graph::search_state_and_operations<mpl::vector<>, postordering_visitor > >::type>::type postorder_inc;
 BOOST_MPL_ASSERT(( mpl::equal<postorder_inc::type, mpl::vector<D,E,F,C,B,A> > ));
 
 // preordering starting at C
 typedef mpl::first<mpl_graph::depth_first_search<some_incidence_list_graph,
-                                                 mpl_graph::state_and_operations<mpl::vector<>, preordering_visitor >,
+                                                 mpl_graph::search_state_and_operations<mpl::vector<>, preordering_visitor >,
                                                  C>::type>::type preorder_inc_from_c;
 BOOST_MPL_ASSERT(( mpl::equal<preorder_inc_from_c::type, mpl::vector<C,D,E,F,A,B> > ));