Boost logo

Boost-Commit :

From: gordon_at_[hidden]
Date: 2008-08-25 18:40:07


Author: gordon.woodhull
Date: 2008-08-25 18:40:07 EDT (Mon, 25 Aug 2008)
New Revision: 48390
URL: http://svn.boost.org/trac/boost/changeset/48390

Log:
full depth_first_search with optional start node
Text files modified:
   sandbox/metagraph/boost/metagraph/fusion_graph/fusion_graph.hpp | 40 +++++++++++++---------------------------
   sandbox/metagraph/boost/metagraph/mpl_graph/depth_first_search.hpp | 15 +++++++++++++++
   sandbox/metagraph/libs/metagraph/example/depth_first_search.cpp | 18 +++++++++++++-----
   sandbox/metagraph/libs/metagraph/example/fusion_graph.cpp | 30 +++++++++++++++++-------------
   4 files changed, 58 insertions(+), 45 deletions(-)

Modified: sandbox/metagraph/boost/metagraph/fusion_graph/fusion_graph.hpp
==============================================================================
--- sandbox/metagraph/boost/metagraph/fusion_graph/fusion_graph.hpp (original)
+++ sandbox/metagraph/boost/metagraph/fusion_graph/fusion_graph.hpp 2008-08-25 18:40:07 EDT (Mon, 25 Aug 2008)
@@ -13,6 +13,7 @@
 #include <boost/fusion/include/as_map.hpp>
 #include <boost/fusion/include/mpl.hpp>
 #include <boost/fusion/include/at_key.hpp>
+#include <boost/mpl/joint_view.hpp>
 
 #include <list>
 
@@ -41,27 +42,21 @@
     struct type {
         template<typename VertexTag> struct vertex_impl;
         template<typename EdgeTag>
- struct edge_impl {
- struct type {
- typedef typename vertex_impl<typename mpl_graph::target<EdgeTag,InputGraph>::type>::type target_type;
- typedef typename EdgeTag::template link_container<target_type>::type link_type;
-
- link_type link;
- typename EdgeTag::data_type data;
- };
- };
+ struct edge_impl :
+ EdgeTag::template link_container<typename vertex_impl<typename mpl_graph::target<EdgeTag,InputGraph>::type>::type>
+ {};
             
         template<typename VertexTag>
         struct vertex_impl {
             struct type {
                 typedef typename mpl::transform<typename mpl_graph::out_edges<VertexTag,InputGraph>::type,
- fusion::pair<mpl::_1,
- edge_impl<mpl::_1> >
- >::type tag_n_impl_sequence;
- typedef typename VertexTag::template edges_container<tag_n_impl_sequence>::type
- edges_type;
- edges_type edges;
- typename VertexTag::data_type data;
+ fusion::pair<mpl::_1,
+ edge_impl<mpl::_1> >
+ >::type tag_n_impl_sequence;
+ typedef typename mpl::joint_view<tag_n_impl_sequence,typename VertexTag::data_type>::type all_vertex_data;
+ typedef typename boost::fusion::result_of::as_map<all_vertex_data>::type
+ data_type;
+ data_type data;
             };
         };
     };
@@ -69,29 +64,20 @@
 
 // some vertex and edge data specification classes
 
-// tells fusion_graph to use a fusion::map to keep track of edges in a vertex
 template<typename Data>
-struct mapper_vertex {
- typedef Data data_type;
- template<typename EdgeTagImplVec>
- struct edges_container :
- boost::fusion::result_of::as_map<EdgeTagImplVec>
- {};
+struct vertex_data {
+ typedef Data data_type; // a sequence of tag/data fusion pairs to be concatenated with the edge data
 };
 
 // tells fusion_graph to use a pointer to store zero/one link in edge
-template<typename Data>
 struct ptr_edge {
- typedef Data data_type;
     template<typename VertexImpl>
     struct link_container {
         typedef VertexImpl* type;
     };
 };
 // tells fusion_graph to use a list to store zero or more links in edge
-template<typename Data>
 struct ptr_list_edge {
- typedef Data data_type;
     template<typename VertexImpl>
     struct link_container {
         typedef std::list<VertexImpl*> type;

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 2008-08-25 18:40:07 EDT (Mon, 25 Aug 2008)
@@ -101,6 +101,21 @@
                       typename ColorMap::operations::template set_color<Node, dfs_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> >
+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>,
+ 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> >,
+ mpl::_1> >
+{};
+
 } // namespace mpl_graph
 } // namespace metagraph
 } // namespace boost

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 2008-08-25 18:40:07 EDT (Mon, 25 Aug 2008)
@@ -15,7 +15,7 @@
 */
 
 // vertices
-struct A{}; struct B{}; struct C{}; struct D{}; struct E{}; struct F{};
+struct A{}; struct B{}; struct C{}; struct D{}; struct E{}; struct F{};
 
 // edges
 struct A_B{}; struct B_C{}; struct C_D{}; struct C_E{}; struct C_F{}; struct B_F{};
@@ -29,14 +29,14 @@
     some_edge_sequence;
 typedef mpl_graph::edgeseq_graph<some_edge_sequence> some_graph;
 
-struct preordering : mpl_graph::dfs_default_visitor_operations {
+struct preordering_visitor : mpl_graph::dfs_default_visitor_operations {
     template<typename Node, typename Graph, typename State>
     struct discover_vertex :
         mpl::push_back<State, Node>
     {};
 };
 
-struct postordering : mpl_graph::dfs_default_visitor_operations {
+struct postordering_visitor : mpl_graph::dfs_default_visitor_operations {
     template<typename Node, typename Graph, typename State>
     struct finish_vertex :
         mpl::push_back<State, Node>
@@ -46,10 +46,18 @@
 template<typename T> struct incomplete;
 
 int main() {
- typedef mpl::first<mpl_graph::dfs_visit<some_graph,A,mpl_graph::state_and_operations<mpl::vector<>, preordering > >::type>::type preorder;
+ // preordering, default start node (first)
+ typedef mpl::first<mpl_graph::depth_first_search<some_graph,mpl_graph::state_and_operations<mpl::vector<>, preordering_visitor > >::type>::type preorder;
     BOOST_MPL_ASSERT(( mpl::equal<preorder::type, mpl::vector<A,B,C,D,E,F> > ));
     
- typedef mpl::first<mpl_graph::dfs_visit<some_graph,A,mpl_graph::state_and_operations<mpl::vector<>, postordering > >::type>::type postorder;
+ // postordering, default start node
+ typedef mpl::first<mpl_graph::depth_first_search<some_graph,mpl_graph::state_and_operations<mpl::vector<>, postordering_visitor > >::type>::type postorder;
     BOOST_MPL_ASSERT(( mpl::equal<postorder::type, mpl::vector<D,E,F,C,B,A> > ));
+
+ // preordering starting at C
+ typedef mpl::first<mpl_graph::depth_first_search<some_graph,
+ mpl_graph::state_and_operations<mpl::vector<>, preordering_visitor >,
+ C>::type>::type preorder_from_c;
+ BOOST_MPL_ASSERT(( mpl::equal<preorder_from_c::type, mpl::vector<C,D,E,F,A,B> > ));
     return 0;
 }
\ No newline at end of file

Modified: sandbox/metagraph/libs/metagraph/example/fusion_graph.cpp
==============================================================================
--- sandbox/metagraph/libs/metagraph/example/fusion_graph.cpp (original)
+++ sandbox/metagraph/libs/metagraph/example/fusion_graph.cpp 2008-08-25 18:40:07 EDT (Mon, 25 Aug 2008)
@@ -6,13 +6,15 @@
 namespace mpl_graph = boost::metagraph::mpl_graph;
 namespace mpl = boost::mpl;
 
-struct G : fusion_graph::mapper_vertex<int> {};
-struct N : fusion_graph::mapper_vertex<int> {};
-struct E : fusion_graph::mapper_vertex<int> {};
-
-struct G_N : fusion_graph::ptr_list_edge<int> {};
-struct N_E : fusion_graph::ptr_list_edge<int> {};
-struct E_N : fusion_graph::ptr_edge<int> {};
+struct Happy {}; // sample data tag
+
+struct G : fusion_graph::vertex_data<mpl::vector<> > {};
+struct N : fusion_graph::vertex_data<mpl::vector<fusion::pair<Happy,bool> > > {};
+struct E : fusion_graph::vertex_data<mpl::vector<> > {};
+
+struct G_N : fusion_graph::ptr_list_edge {};
+struct N_E : fusion_graph::ptr_list_edge {};
+struct E_N : fusion_graph::ptr_edge {};
 struct E_T : E_N {};
 struct E_S : E_N {};
 
@@ -41,13 +43,15 @@
     Node *n1 = new Node, *n2 = new Node;
     Edge *e1 = new Edge;
     
- fusion::at_key<G_N>(g->edges).link.push_back(n1);
- fusion::at_key<G_N>(g->edges).link.push_back(n2);
- fusion::at_key<N_E>(n1->edges).link.push_back(e1);
- fusion::at_key<E_S>(e1->edges).link = n1;
- fusion::at_key<E_T>(e1->edges).link = n2;
+ fusion::at_key<Happy>(n1->data) = true;
+
+ fusion::at_key<G_N>(g->data).push_back(n1);
+ fusion::at_key<G_N>(g->data).push_back(n2);
+ fusion::at_key<N_E>(n1->data).push_back(e1);
+ fusion::at_key<E_S>(e1->data) = n1;
+ fusion::at_key<E_T>(e1->data) = n2;
     
     // NO (generates horribly incomprehensible messages
- //fusion::at_key<N_E>(g->edges).link.push_back(n1);
+ //fusion::at_key<N_E>(g->edges).push_back(n1);
 
 }
\ No newline at end of file


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk