Subject: [Boost-commit] svn:boost r61960 - in sandbox/metagraph: boost/metagraph/mpl_graph libs/metagraph/example
From: gordon_at_[hidden]
Date: 2010-05-13 23:48:35
Author: gordon.woodhull
Date: 2010-05-13 23:48:34 EDT (Thu, 13 May 2010)
New Revision: 61960
URL: http://svn.boost.org/trac/boost/changeset/61960
Log:
clean up interfaces
Removed:
sandbox/metagraph/boost/metagraph/mpl_graph/search_state_and_operations.hpp
Text files modified:
sandbox/metagraph/boost/metagraph/mpl_graph/breadth_first_search.hpp | 93 +++++++++++++++++++++------------------
sandbox/metagraph/boost/metagraph/mpl_graph/depth_first_search.hpp | 90 +++++++++++++++++++++-----------------
sandbox/metagraph/boost/metagraph/mpl_graph/search_colors.hpp | 4
sandbox/metagraph/libs/metagraph/example/breadth_first_search.cpp | 93 +++++++++++++++++++++++++++++++--------
sandbox/metagraph/libs/metagraph/example/depth_first_search.cpp | 66 ++++++++++++++++++++++-----
5 files changed, 227 insertions(+), 119 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 2010-05-13 23:48:34 EDT (Thu, 13 May 2010)
@@ -13,7 +13,6 @@
#include <boost/mpl/remove.hpp>
#include "search_colors.hpp"
-#include "search_state_and_operations.hpp"
namespace boost {
namespace metagraph {
@@ -68,20 +67,22 @@
};
};
-template<typename Graph, typename VisitorOps, typename ColorOps, typename State, typename Edge>
+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<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 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 ColorOps::template get_color<typename mpl_graph::target<Edge, Graph>::type, color_state>::type, search_colors::White>::type,
+ 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 ColorOps::template set_color<typename mpl_graph::target<Edge, Graph>::type, search_colors::Gray, color_state>::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 ColorOps::template get_color<mpl_graph::target<Edge, Graph>, color_state>,
+ 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,
@@ -89,64 +90,68 @@
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>
+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 Visitor::operations::template examine_vertex<Vertex, Graph, typename Visitor::state>::type examined_state;
+ 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, typename ColorMap::state, Tail>,
- bfs_run_queue_examine_edge<Graph, typename Visitor::operations, typename ColorMap::operations, mpl::_1, mpl::_2>
+ mpl::vector<examined_state, ColorMap, Tail>,
+ bfs_run_queue_examine_edge<Graph, VisitorOps, 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 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,
- search_state_and_operations<finished_vertex, typename Visitor::operations>,
- search_state_and_operations<colored_vertex, typename ColorMap::operations> > >::type::type
- type;
+ 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;
};
-template<typename Graph, typename Vertex, typename Visitor,
- typename ColorMap = search_state_and_operations<create_search_color_map::type, search_color_map_operations> >
+} // namespace detail
+
+template<typename Graph, typename VisitorOps, typename VisitorState,
+ typename Vertex,
+ typename ColorMap = create_search_color_map::type >
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;
+ 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;
};
-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 :
+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, Vertex, Visitor, ColorMap>::type,
- mpl::if_<boost::is_same<typename ColorMap::operations::template get_color<mpl::_2, mpl::second<mpl::_1> >,
+ 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,
- mpl::_2,
- search_state_and_operations<mpl::first<mpl::_1>, typename Visitor::operations>,
- search_state_and_operations<mpl::second<mpl::_1>, typename ColorMap::operations> >,
+ breadth_first_search<Graph, VisitorOps, mpl::first<mpl::_1>,
+ mpl::_2, mpl::second<mpl::_1> >,
mpl::_1> >
{};
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-13 23:48:34 EDT (Thu, 13 May 2010)
@@ -10,7 +10,6 @@
#include <boost/mpl/has_key.hpp>
#include "search_colors.hpp"
-#include "search_state_and_operations.hpp"
namespace boost {
namespace metagraph {
@@ -19,20 +18,20 @@
// 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<Node, State>
+// and need to support a new metafunction get_color<Vertex, State>
struct dfs_default_visitor_operations {
- template<typename Node, typename Graph, typename State>
+ template<typename Vertex, typename Graph, typename State>
struct initialize_vertex {
typedef State type;
};
- template<typename Node, typename Graph, typename State>
+ template<typename Vertex, typename Graph, typename State>
struct discover_vertex {
typedef State type;
};
- template<typename Node, typename Graph, typename State>
+ template<typename Vertex, typename Graph, typename State>
struct finish_vertex {
typedef State type;
};
@@ -53,50 +52,59 @@
};
};
-// visitor is operations, state as described above
-// however this returns pair< visitor_state, color_state >
-template<typename Graph, typename Node, typename Visitor,
- typename ColorMap = search_state_and_operations<create_search_color_map::type, search_color_map_operations> >
-struct dfs_visit {
+// 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 Visitor::operations::template discover_vertex<Node, Graph, typename Visitor::state>::type discovered_state;
- typedef typename ColorMap::operations::template set_color<Node, search_colors::Gray, typename ColorMap::state>::type discovered_colors;
+ 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;
+
// 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 > >,
- search_colors::White>,
- // unseen target: recurse
- dfs_visit<Graph,
- mpl_graph::target<mpl::_2, Graph>,
- search_state_and_operations<typename Visitor::operations::template tree_edge<mpl::_2, Graph, mpl::first<mpl::_1> >,
- typename Visitor::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 > >, 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> > >, // Black
- mpl::second<mpl::_1> >
- >
- >::type visited_state_and_colors;
+ 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 Visitor::operations::template finish_vertex<Node, Graph, typename mpl::first<visited_state_and_colors>::type >::type,
- typename ColorMap::operations::template set_color<Node, search_colors::Black, typename mpl::second<visited_state_and_colors>::type>::type> type;
+ 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;
};
-template<typename Graph, typename Visitor,
+template<typename Graph, typename VisitorOps, typename VisitorState,
typename FirstVertex = 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 depth_first_search :
+ 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 dfs_visit<Graph, FirstVertex, Visitor, ColorMap>::type,
- mpl::if_<boost::is_same<typename ColorMap::operations::template get_color<mpl::_2, mpl::second<mpl::_1> >,
- search_colors::White>,
- dfs_visit<Graph,
+ 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,
- search_state_and_operations<mpl::first<mpl::_1>, typename Visitor::operations>,
- search_state_and_operations<mpl::second<mpl::_1>, typename ColorMap::operations> >,
+ mpl::second<mpl::_1> >,
mpl::_1> >
{};
Modified: sandbox/metagraph/boost/metagraph/mpl_graph/search_colors.hpp
==============================================================================
--- sandbox/metagraph/boost/metagraph/mpl_graph/search_colors.hpp (original)
+++ sandbox/metagraph/boost/metagraph/mpl_graph/search_colors.hpp 2010-05-13 23:48:34 EDT (Thu, 13 May 2010)
@@ -5,7 +5,7 @@
namespace metagraph {
namespace mpl_graph {
-struct search_colors {
+namespace search_colors {
struct White {};
struct Gray {};
struct Black {};
@@ -13,7 +13,7 @@
struct create_search_color_map : mpl::map<> {};
-struct search_color_map_operations {
+struct search_color_map_ops {
template<typename Node, typename Color, typename State>
struct set_color :
mpl::insert<State, mpl::pair<Node, Color> >
Deleted: sandbox/metagraph/boost/metagraph/mpl_graph/search_state_and_operations.hpp
==============================================================================
--- sandbox/metagraph/boost/metagraph/mpl_graph/search_state_and_operations.hpp 2010-05-13 23:48:34 EDT (Thu, 13 May 2010)
+++ (empty file)
@@ -1,24 +0,0 @@
-#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
Modified: sandbox/metagraph/libs/metagraph/example/breadth_first_search.cpp
==============================================================================
--- sandbox/metagraph/libs/metagraph/example/breadth_first_search.cpp (original)
+++ sandbox/metagraph/libs/metagraph/example/breadth_first_search.cpp 2010-05-13 23:48:34 EDT (Thu, 13 May 2010)
@@ -86,64 +86,119 @@
// 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;
+typedef mpl::first<mpl_graph::
+ breadth_first_search<some_adjacency_list_graph,
+ preordering_visitor,
+ mpl::vector<>,
+ A>::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;
+typedef mpl::first<mpl_graph::
+ breadth_first_search<some_adjacency_list_graph,
+ examine_edge_visitor,
+ mpl::vector<>,
+ A>::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;
+typedef mpl::first<mpl_graph::
+ breadth_first_search<some_adjacency_list_graph,
+ tree_edge_visitor,
+ mpl::vector<>,
+ A>::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;
+typedef mpl::first<mpl_graph::
+ breadth_first_search_all<some_adjacency_list_graph,
+ preordering_visitor,
+ mpl::vector<> >::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;
+typedef mpl::first<mpl_graph::
+ breadth_first_search<some_adjacency_list_graph,
+ postordering_visitor,
+ mpl::vector<>,
+ A>::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;
+typedef mpl::first<mpl_graph::
+ breadth_first_search_all<some_adjacency_list_graph,
+ postordering_visitor,
+ mpl::vector<> >::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;
+typedef mpl::first<mpl_graph::
+ breadth_first_search<some_adjacency_list_graph,
+ preordering_visitor,
+ mpl::vector<>,
+ C>::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;
+typedef mpl::first<mpl_graph::
+ breadth_first_search_all<some_adjacency_list_graph,
+ preordering_visitor,
+ mpl::vector<>,
+ 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;
+typedef mpl::first<mpl_graph::
+ breadth_first_search<some_incidence_list_graph,
+ preordering_visitor,
+ mpl::vector<>,
+ A>::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;
+typedef mpl::first<mpl_graph::
+ breadth_first_search<some_incidence_list_graph,
+ preordering_visitor,
+ mpl::vector<>,
+ C>::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;
+typedef mpl::first<mpl_graph::
+ breadth_first_search_all<some_incidence_list_graph,
+ preordering_visitor,
+ mpl::vector<> >::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;
+typedef mpl::first<mpl_graph::
+ breadth_first_search_all<some_incidence_list_graph,
+ postordering_visitor,
+ mpl::vector<> >::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;
+typedef mpl::first<mpl_graph::
+ breadth_first_search_all<some_incidence_list_graph,
+ preordering_visitor,
+ mpl::vector<>,
+ 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> > ));
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-13 23:48:34 EDT (Thu, 13 May 2010)
@@ -73,35 +73,75 @@
// adjacency list tests
// preordering, default start node (first)
-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;
+typedef mpl::first<mpl_graph::
+ depth_first_search_all<some_adjacency_list_graph,
+ preordering_visitor,
+ mpl::vector<> >::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::search_state_and_operations<mpl::vector<>, postordering_visitor > >::type>::type postorder_adj;
+typedef mpl::first<mpl_graph::
+ depth_first_search_all<some_adjacency_list_graph,
+ postordering_visitor,
+ mpl::vector<> >::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::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> > ));
+// preordering all starting at C
+typedef mpl::first<mpl_graph::
+ depth_first_search_all<some_adjacency_list_graph,
+ preordering_visitor,
+ mpl::vector<>,
+ C>::type>::type
+ preorder_adj_all_from_c;
+BOOST_MPL_ASSERT(( mpl::equal<preorder_adj_all_from_c::type, mpl::vector<C,D,E,F,A,B,G> > ));
+
+// preordering just those starting at C
+typedef mpl::first<mpl_graph::
+ depth_first_search<some_adjacency_list_graph,
+ preordering_visitor,
+ mpl::vector<>,
+ C>::type>::type
+ preorder_adj_from_c;
+BOOST_MPL_ASSERT(( mpl::equal<preorder_adj_from_c::type, mpl::vector<C,D,E,F> > ));
// incidence list tests
// preordering, default start node (first)
-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;
+typedef mpl::first<mpl_graph::
+ depth_first_search_all<some_incidence_list_graph,
+ preordering_visitor,
+ mpl::vector<> >::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::search_state_and_operations<mpl::vector<>, postordering_visitor > >::type>::type postorder_inc;
+typedef mpl::first<mpl_graph::
+ depth_first_search_all<some_incidence_list_graph,
+ postordering_visitor,
+ mpl::vector<> >::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::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> > ));
+typedef mpl::first<mpl_graph::
+ depth_first_search_all<some_incidence_list_graph,
+ preordering_visitor,
+ mpl::vector<>,
+ C>::type>::type
+ preorder_inc_all_from_c;
+BOOST_MPL_ASSERT(( mpl::equal<preorder_inc_all_from_c::type, mpl::vector<C,D,E,F,A,B> > ));
+
+// preordering starting at B
+typedef mpl::first<mpl_graph::
+ depth_first_search<some_incidence_list_graph,
+ preordering_visitor,
+ mpl::vector<>,
+ B>::type>::type
+ preorder_inc_from_b;
+BOOST_MPL_ASSERT(( mpl::equal<preorder_inc_from_b::type, mpl::vector<B,C,D,E,F> > ));
int main() {