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