Date view Thread view Subject view Author view

Subject: [Boost-commit] svn:boost r76957 - in sandbox/mgl: boost/mgl boost/mgl/aux_ libs/mgl/examples libs/mgl/test
From: F.Alt_at_[hidden]
Date: 2012-02-09 13:54:52

Author: franzalt
Date: 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
New Revision: 76957
URL: http://svn.boost.org/trac/boost/changeset/76957

Log:
- added support for weighted graphs
- updated some examples
Added:
   sandbox/mgl/libs/mgl/examples/hello_world.cpp (contents, props changed)
   sandbox/mgl/libs/mgl/examples/sample_graph.cpp (contents, props changed)
   sandbox/mgl/libs/mgl/examples/weighted_graph.cpp (contents, props changed)
Text files modified:
   sandbox/mgl/boost/mgl/aux_/breadth_first_search_impl.hpp | 25
   sandbox/mgl/boost/mgl/aux_/contains_cycle_impl.hpp | 44
   sandbox/mgl/boost/mgl/aux_/depth_first_search_impl.hpp | 25
   sandbox/mgl/boost/mgl/aux_/topological_sort_impl.hpp | 16
   sandbox/mgl/boost/mgl/begin_end.hpp | 77
   sandbox/mgl/boost/mgl/breadth_first_search.hpp | 51
   sandbox/mgl/boost/mgl/colors.hpp | 34
   sandbox/mgl/boost/mgl/contains_cycle.hpp | 15
   sandbox/mgl/boost/mgl/depth_first_search.hpp | 51
   sandbox/mgl/boost/mgl/edge.hpp | 18
   sandbox/mgl/boost/mgl/find.hpp | 77
   sandbox/mgl/boost/mgl/graph.hpp | 2253 +++++++++++++++++++--------------------
   sandbox/mgl/boost/mgl/graph_policies.hpp | 272 ++--
   sandbox/mgl/boost/mgl/is_graph.hpp | 2
   sandbox/mgl/boost/mgl/iterator.hpp | 132 +
   sandbox/mgl/boost/mgl/iterator_policies.hpp | 13
   sandbox/mgl/boost/mgl/iterator_tags.hpp | 2
   sandbox/mgl/boost/mgl/next_prior.hpp | 16
   sandbox/mgl/boost/mgl/row.hpp | 4
   sandbox/mgl/boost/mgl/topological_sort.hpp | 26
   sandbox/mgl/boost/mgl/v_prop.hpp | 8
   sandbox/mgl/boost/mgl/visitor_helpers.hpp | 28
   sandbox/mgl/boost/mgl/visitors.hpp | 108
   sandbox/mgl/libs/mgl/test/bfs_iteration.cpp | 20
   sandbox/mgl/libs/mgl/test/breadth_first_search.cpp | 50
   sandbox/mgl/libs/mgl/test/contains_cycle.cpp | 4
   sandbox/mgl/libs/mgl/test/depth_first_search.cpp | 50
   sandbox/mgl/libs/mgl/test/dfs_iteration.cpp | 20
   sandbox/mgl/libs/mgl/test/find_vertex.cpp | 2
   sandbox/mgl/libs/mgl/test/generic_graph.cpp | 18
   sandbox/mgl/libs/mgl/test/topological_sort.cpp | 4
   sandbox/mgl/libs/mgl/test/visitors.cpp | 67
   32 files changed, 1816 insertions(+), 1716 deletions(-)

Modified: sandbox/mgl/boost/mgl/aux_/breadth_first_search_impl.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/aux_/breadth_first_search_impl.hpp (original)
+++ sandbox/mgl/boost/mgl/aux_/breadth_first_search_impl.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -7,6 +7,10 @@
 #ifndef BOOST_MGL_BREADTH_FIRST_SEARCH_IMPL_HPP
 #define BOOST_MGL_BREADTH_FIRST_SEARCH_IMPL_HPP
 
+#include <boost/mpl/set.hpp>
+#include <boost/mpl/vector.hpp>
+#include <boost/mpl/void.hpp>
+
 #include <boost/mgl/begin_end.hpp>
 #include <boost/mgl/next_prior.hpp>
 
@@ -31,11 +35,15 @@
 };
 
 template<class Iterator>
-struct breadth_first_search_impl<Iterator, typename ::boost::enable_if< ::boost::is_same<Iterator, ::boost::mpl::void_> >::type>
+struct breadth_first_search_impl<
+ Iterator,
+ typename ::boost::enable_if<
+ ::boost::is_same<Iterator, ::boost::mpl::void_>
+ >::type>
 {
         typedef bfs_iterator<
- void,
- void,
+ ::boost::mpl::void_,
+ ::boost::mpl::void_,
                 ::boost::mpl::set0<>,
                 ::boost::mpl::vector0<>
> type;
@@ -45,7 +53,14 @@
 };
 
 template<class Iterator>
-struct breadth_first_search_impl<Iterator, typename ::boost::enable_if< ::boost::is_same<typename ::boost::mgl::dfs_end<typename Iterator::graph>::type, typename Iterator::vertex> >::type>
+struct breadth_first_search_impl<
+ Iterator,
+ typename ::boost::enable_if<
+ ::boost::is_same<
+ typename ::boost::mgl::dfs_end<typename Iterator::graph>::type,
+ typename Iterator::vertex>
+ >::type
+ >
 {
         typedef bfs_iterator<
                 typename Iterator::graph,
@@ -53,8 +68,6 @@
                 typename Iterator::color_map,
                 typename Iterator::traversal_stack,
                 typename Iterator::end_at_strategy,
- typename Iterator::trace_policy,
- typename Iterator::vertex_trace,
                 typename Iterator::visitor_type,
                 typename Iterator::visitor_result
> type;

Modified: sandbox/mgl/boost/mgl/aux_/contains_cycle_impl.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/aux_/contains_cycle_impl.hpp (original)
+++ sandbox/mgl/boost/mgl/aux_/contains_cycle_impl.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -7,12 +7,11 @@
 #ifndef BOOST_MGL_AUX_CONTAINS_CYCLE_IMPL_HPP
 #define BOOST_MGL_AUX_CONTAINS_CYCLE_IMPL_HPP
 
-#include <boost/mgl/next_prior.hpp>
+#include <boost/mgl/colors.hpp>
 
-#include <boost/mpl/has_xxx.hpp>
-#include <boost/mpl/eval_if.hpp>
-#include <boost/mpl/contains.hpp>
 #include <boost/mpl/bool.hpp>
+#include <boost/mpl/has_xxx.hpp>
+#include <boost/mpl/if.hpp>
 #include <boost/mpl/pair.hpp>
 
 #include <boost/type_traits/is_same.hpp>
@@ -30,22 +29,27 @@
 
 struct cycle_detector_visitor
 {
- typedef ::boost::mpl::true_ examine_edge;
-
- struct on_init
- {
- typedef ::boost::mpl::false_ type;
- };
-
- template<typename Edge, typename T, typename TraversalStack, typename ColorMap>
- struct on_examine_edge
- {
- typedef typename ::boost::mpl::eval_if<
- ::boost::is_same<T, ::boost::mpl::false_>,
- ::boost::mpl::contains<TraversalStack, typename ::boost::mpl::second<Edge>::type>,
- ::boost::mpl::true_
- >::type type;
- };
+ typedef ::boost::mpl::true_ examine_edge;
+
+ struct on_init
+ {
+ typedef ::boost::mpl::false_ type;
+ };
+
+ template<typename Vertex1, typename Vertex2, typename Weight, typename T, typename TraversalStack, typename ColorMap>
+ struct on_examine_edge
+ {
+ typedef typename ::boost::mpl::if_<
+ T,
+ ::boost::mpl::true_,
+ ::boost::mpl::bool_<
+ ::boost::is_same<
+ typename ::boost::mgl::get_color<Vertex2, ColorMap>::type,
+ ::boost::mgl::gray
+ >::value
+ >
+ >::type type;
+ };
 };
 
 } // namespace aux

Modified: sandbox/mgl/boost/mgl/aux_/depth_first_search_impl.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/aux_/depth_first_search_impl.hpp (original)
+++ sandbox/mgl/boost/mgl/aux_/depth_first_search_impl.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -7,15 +7,15 @@
 #ifndef BOOST_MGL_DEPTH_FIRST_SEARCH_IMPL_HPP
 #define BOOST_MGL_DEPTH_FIRST_SEARCH_IMPL_HPP
 
-#include <boost/mpl/vector.hpp>
 #include <boost/mpl/set.hpp>
+#include <boost/mpl/vector.hpp>
+#include <boost/mpl/void.hpp>
 
 #include <boost/mgl/begin_end.hpp>
 #include <boost/mgl/next_prior.hpp>
 
 #include <boost/type_traits/is_same.hpp>
 #include <boost/utility/enable_if.hpp>
-#include <boost/type_traits/is_void.hpp>
 
 namespace boost
 {
@@ -35,11 +35,15 @@
 };
 
 template<class Iterator>
-struct depth_first_search_impl<Iterator, typename ::boost::enable_if< ::boost::is_same<Iterator, ::boost::mpl::void_> >::type>
+struct depth_first_search_impl<
+ Iterator,
+ typename ::boost::enable_if<
+ ::boost::is_same<Iterator, ::boost::mpl::void_>
+ >::type>
 {
         typedef dfs_iterator<
- void,
- void,
+ ::boost::mpl::void_,
+ ::boost::mpl::void_,
                 ::boost::mpl::set0<>,
                 ::boost::mpl::vector0<>
> type;
@@ -49,7 +53,14 @@
 };
 
 template<class Iterator>
-struct depth_first_search_impl<Iterator, typename ::boost::enable_if< ::boost::is_same<typename ::boost::mgl::dfs_end<typename Iterator::graph>::type, typename Iterator::vertex> >::type>
+struct depth_first_search_impl<
+ Iterator,
+ typename ::boost::enable_if<
+ ::boost::is_same<
+ typename ::boost::mgl::dfs_end<typename Iterator::graph>::type,
+ typename Iterator::vertex>
+ >::type
+ >
 {
         typedef dfs_iterator<
                 typename Iterator::graph,
@@ -57,8 +68,6 @@
                 typename Iterator::color_map,
                 typename Iterator::traversal_stack,
                 typename Iterator::end_at_strategy,
- typename Iterator::trace_policy,
- typename Iterator::vertex_trace,
                 typename Iterator::visitor_type,
                 typename Iterator::visitor_result
> type;

Modified: sandbox/mgl/boost/mgl/aux_/topological_sort_impl.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/aux_/topological_sort_impl.hpp (original)
+++ sandbox/mgl/boost/mgl/aux_/topological_sort_impl.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -42,41 +42,41 @@
                 typedef ::boost::mpl::map0<> type;
         };
 
- template<typename Edge, typename T, typename TraversalStack, typename ColorMap>
+ template<typename Vertex1, typename Vertex2, typename Weight, typename T, typename TraversalStack, typename ColorMap>
         struct on_examine_edge
         {
                 typedef typename ::boost::mpl::if_<
- typename ::boost::mpl::has_key<T, typename ::boost::mpl::first<Edge>::type>::type,
+ typename ::boost::mpl::has_key<T, Vertex1>::type,
                         T,
                         typename ::boost::mpl::insert<
                                 T,
                                 ::boost::mpl::pair<
- typename ::boost::mpl::first<Edge>::type,
+ Vertex1,
                                         ::boost::mpl::vector0<>
>
>::type
>::type T_;
 
                 typedef typename ::boost::mpl::if_<
- typename ::boost::mpl::has_key<T_, typename ::boost::mpl::second<Edge>::type>::type,
- typename ::boost::mpl::at<T, typename ::boost::mpl::second<Edge>::type>::type,
+ typename ::boost::mpl::has_key<T_, Vertex2>::type,
+ typename ::boost::mpl::at<T, Vertex2>::type,
                         ::boost::mpl::vector0<>
>::type bucket;
 
                 typedef typename ::boost::mpl::push_back<
                         bucket,
- typename ::boost::mpl::first<Edge>::type
+ Vertex1
>::type new_bucket;
 
                 typedef typename ::boost::mpl::erase_key<
                         T_,
- typename ::boost::mpl::second<Edge>::type
+ Vertex2
>::type T__;
 
                 typedef typename ::boost::mpl::insert<
                         T__,
                         ::boost::mpl::pair<
- typename ::boost::mpl::second<Edge>::type,
+ Vertex2,
                                 new_bucket
>
>::type type;

Modified: sandbox/mgl/boost/mgl/begin_end.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/begin_end.hpp (original)
+++ sandbox/mgl/boost/mgl/begin_end.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -25,72 +25,99 @@
 BOOST_MPL_HAS_XXX_TRAIT_DEF(bfs_begin_supported)
 
 /// \brief Get a DFS iterator to the begin of a graph
-/// \param Graph Graph where the iteration should be performed
-/// \param EndAtStrategy The strategy used to abort the iteration
-/// \param TracePolicy The policy used to trace the iteration
-/// \param Visitor The visitor class used during the iteration
-template<class Graph, class EndAtStrategy = ::boost::mgl::EndAtEndOfGraph, class TracePolicy = ::boost::mgl::NoTrace, class Visitor = ::boost::mgl::null_visitor, class Enable = void>
+/// \tparam Graph Graph where the iteration should be performed
+/// \tparam EndAtStrategy The strategy used to abort the iteration
+/// \tparam Visitor The visitor class used during the iteration
+template<
+ class Graph,
+ class EndAtStrategy = ::boost::mgl::EndAtEndOfGraph,
+ class Visitor = ::boost::mgl::null_visitor,
+ class Enable = void
+>
 struct dfs_begin
 {
- typedef ::boost::mpl::void_ type;
+ typedef ::boost::mpl::void_ type;
 };
 
-template<class Graph, class EndAtStrategy, class TracePolicy, class Visitor>
-struct dfs_begin<Graph, EndAtStrategy, TracePolicy, Visitor, typename ::boost::enable_if<has_dfs_begin_supported<Graph> >::type>
+template<
+ class Graph,
+ class EndAtStrategy,
+ class Visitor
+>
+struct dfs_begin<
+ Graph,
+ EndAtStrategy,
+ Visitor,
+ typename ::boost::enable_if<
+ has_dfs_begin_supported<Graph>
+ >::type>
 {
- typedef typename Graph::template dfs_begin<EndAtStrategy, TracePolicy, Visitor>::type type;
+ typedef typename Graph::template dfs_begin<EndAtStrategy, Visitor>::type type;
 };
 
 /// \brief Get a DFS iterator to the end of a graph
-/// \param Graph Graph where the iteration should be performed
+/// \tparam Graph Graph where the iteration should be performed
 template<class Graph, class Enable = void>
 struct dfs_end
 {
- typedef ::boost::mpl::void_ type;
+ typedef ::boost::mpl::void_ type;
 };
 
 template<class Graph>
 struct dfs_end<Graph, typename ::boost::enable_if<has_dfs_begin_supported<Graph> >::type>
 {
- typedef typename Graph::end::type type;
+ typedef typename Graph::end::type type;
 };
 
 /// \brief Get a BFS iterator to the begin of a graph
-/// \param Graph Graph where the iteration should be performed
-/// \param EndAtStrategy The strategy used to abort the iteration
-/// \param TracePolicy The policy used to trace the iteration
-/// \param Visitor The visitor class used during the iteration
-template<class Graph, class EndAtStrategy = ::boost::mgl::EndAtEndOfGraph, class TracePolicy = ::boost::mgl::NoTrace, class Visitor = ::boost::mgl::null_visitor, class Enable = void>
+/// \tparam Graph Graph where the iteration should be performed
+/// \tparam EndAtStrategy The strategy used to abort the iteration
+/// \tparam Visitor The visitor class used during the iteration
+template<
+ class Graph,
+ class EndAtStrategy = ::boost::mgl::EndAtEndOfGraph,
+ class Visitor = ::boost::mgl::null_visitor,
+ class Enable = void
+>
 struct bfs_begin
 {
- typedef ::boost::mpl::void_ type;
+ typedef ::boost::mpl::void_ type;
 };
 
-template<class Graph, class EndAtStrategy, class TracePolicy, class Visitor>
-struct bfs_begin<Graph, EndAtStrategy, TracePolicy, Visitor, typename ::boost::enable_if<has_bfs_begin_supported<Graph> >::type>
+template<
+ class Graph,
+ class EndAtStrategy,
+ class Visitor>
+struct bfs_begin<
+ Graph,
+ EndAtStrategy,
+ Visitor,
+ typename ::boost::enable_if<
+ has_bfs_begin_supported<Graph>
+ >::type>
 {
- typedef typename Graph::template bfs_begin<EndAtStrategy, TracePolicy, Visitor>::type type;
+ typedef typename Graph::template bfs_begin<EndAtStrategy, Visitor>::type type;
 };
 
 /// \brief Get a BFS iterator to the end of a graph
-/// \param Graph Graph where the iteration should be performed
+/// \tparam Graph Graph where the iteration should be performed
 template<class Graph, class Enable = void>
 struct bfs_end
 {
- typedef ::boost::mpl::void_ type;
+ typedef ::boost::mpl::void_ type;
 };
 
 template<class Graph>
 struct bfs_end<Graph, typename ::boost::enable_if<has_bfs_begin_supported<Graph> >::type>
 {
- typedef typename Graph::end::type type;
+ typedef typename Graph::end::type type;
 };
 
 //! @todo Add enable_if's like above!!!
 template<class VertexIterator>
 struct edge_begin
 {
- typedef typename aux::edge_begin_impl::template apply<typename VertexIterator::graph, VertexIterator>::type type;
+ typedef typename aux::edge_begin_impl::template apply<typename VertexIterator::graph, VertexIterator>::type type;
 };
 
 } // namespace mgl

Modified: sandbox/mgl/boost/mgl/breadth_first_search.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/breadth_first_search.hpp (original)
+++ sandbox/mgl/boost/mgl/breadth_first_search.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -10,10 +10,10 @@
 #include <boost/mpl/vector.hpp>
 #include <boost/mpl/void.hpp>
 
-#include <boost/mgl/visitors.hpp>
 #include <boost/mgl/begin_end.hpp>
-#include <boost/mgl/iterator_policies.hpp>
 #include <boost/mgl/find.hpp>
+#include <boost/mgl/iterator_policies.hpp>
+#include <boost/mgl/visitors.hpp>
 #include <boost/mgl/aux_/breadth_first_search_impl.hpp>
 
 namespace boost
@@ -23,31 +23,34 @@
 {
 
 /// \brief Performs a breadth-first-traversal of the vertices in a directed graph
-/// \param Graph The graph that should be traversed
-/// \param Visitor The visitor used at the traversal
-/// \param Vertex The Vertex where the search begins at
-/// \param EndAtStrategy Strategy what is done when all vertices are visited
-template<class Graph, class Visitor = ::boost::mgl::null_visitor, class Vertex = ::boost::mpl::void_, class EndAtStrategy = ::boost::mgl::EndAtEndOfGraph>
+/// \tparam Graph The graph that should be traversed
+/// \tparam Visitor The visitor used at the traversal
+/// \tparam Vertex The Vertex where the search begins at
+/// \tparam EndAtStrategy Strategy what is done when all vertices are visited
+template<
+ class Graph,
+ class Visitor = ::boost::mgl::null_visitor,
+ class Vertex = ::boost::mpl::void_,
+ class EndAtStrategy = ::boost::mgl::EndAtEndOfGraph
+>
 struct breadth_first_search
 {
- typedef typename ::boost::mpl::eval_if<
- typename ::boost::is_same<Vertex, ::boost::mpl::void_>::type,
- ::boost::mgl::bfs_begin<
- Graph,
- EndAtStrategy,
- ::boost::mgl::RecordTrace< ::boost::mpl::vector0<> >,
- Visitor
- >,
- ::boost::mgl::bfs_find<
- Graph,
- Vertex,
- EndAtStrategy,
- ::boost::mgl::RecordTrace< ::boost::mpl::vector0<> >,
- Visitor
- >
- >::type iter;
+ typedef typename ::boost::mpl::eval_if<
+ typename ::boost::is_same<Vertex, ::boost::mpl::void_>::type,
+ ::boost::mgl::bfs_begin<
+ Graph,
+ EndAtStrategy,
+ Visitor
+ >,
+ ::boost::mgl::bfs_find<
+ Graph,
+ Vertex,
+ EndAtStrategy,
+ Visitor
+ >
+ >::type iter;
 
- typedef typename aux::template breadth_first_search_impl<iter>::type type;
+ typedef typename aux::template breadth_first_search_impl<iter>::type type;
 };
 
 } // namespace mgl

Modified: sandbox/mgl/boost/mgl/colors.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/colors.hpp (original)
+++ sandbox/mgl/boost/mgl/colors.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -7,12 +7,12 @@
 #ifndef BOOST_MGL_COLORS_HPP
 #define BOOST_MGL_COLORS_HPP
 
+#include <boost/mpl/at.hpp>
 #include <boost/mpl/erase_key.hpp>
+#include <boost/mpl/has_key.hpp>
+#include <boost/mpl/if.hpp>
 #include <boost/mpl/insert.hpp>
 #include <boost/mpl/pair.hpp>
-#include <boost/mpl/if.hpp>
-#include <boost/mpl/has_key.hpp>
-#include <boost/mpl/at.hpp>
 
 namespace boost
 {
@@ -27,25 +27,25 @@
 template<typename Vertex, typename Color, typename Map>
 struct set_color
 {
- typedef typename ::boost::mpl::erase_key<
- Map,
- Vertex
- >::type map;
-
- typedef typename ::boost::mpl::insert<
- map,
- ::boost::mpl::pair<Vertex, Color>
- >::type type;
+ typedef typename ::boost::mpl::erase_key<
+ Map,
+ Vertex
+ >::type map;
+
+ typedef typename ::boost::mpl::insert<
+ map,
+ ::boost::mpl::pair<Vertex, Color>
+ >::type type;
 };
 
 template<typename Vertex, typename Map>
 struct get_color
 {
- typedef typename ::boost::mpl::if_<
- typename ::boost::mpl::has_key<Map, Vertex>::type,
- typename ::boost::mpl::at<Map, Vertex>::type,
- white
- >::type type;
+ typedef typename ::boost::mpl::if_<
+ typename ::boost::mpl::has_key<Map, Vertex>::type,
+ typename ::boost::mpl::at<Map, Vertex>::type,
+ white
+ >::type type;
 };
 
 } // namespace mgl

Modified: sandbox/mgl/boost/mgl/contains_cycle.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/contains_cycle.hpp (original)
+++ sandbox/mgl/boost/mgl/contains_cycle.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -21,17 +21,18 @@
 namespace mgl
 {
 
+/// \brief Test if a graph has a cycle
+/// \tparam Graph The graph that should be tested
 template<class Graph>
 struct contains_cycle
 {
- typedef typename ::boost::mgl::dfs_begin<
- Graph,
- ::boost::mgl::EndWhenNoVerticesFound,
- ::boost::mgl::RecordTrace< ::boost::mpl::vector0<> >,
- aux::cycle_detector_visitor
- >::type iter;
+ typedef typename ::boost::mgl::dfs_begin<
+ Graph,
+ ::boost::mgl::EndWhenNoVerticesFound,
+ aux::cycle_detector_visitor
+ >::type iter;
 
- typedef typename aux::template depth_first_search_impl<iter>::type::visitor_result type;
+ typedef typename aux::template depth_first_search_impl<iter>::type::visitor_result type;
 };
 
 } // namespace mgl

Modified: sandbox/mgl/boost/mgl/depth_first_search.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/depth_first_search.hpp (original)
+++ sandbox/mgl/boost/mgl/depth_first_search.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -10,10 +10,10 @@
 #include <boost/mpl/vector.hpp>
 #include <boost/mpl/void.hpp>
 
-#include <boost/mgl/visitors.hpp>
 #include <boost/mgl/begin_end.hpp>
-#include <boost/mgl/iterator_policies.hpp>
 #include <boost/mgl/find.hpp>
+#include <boost/mgl/iterator_policies.hpp>
+#include <boost/mgl/visitors.hpp>
 #include <boost/mgl/aux_/depth_first_search_impl.hpp>
 
 namespace boost
@@ -23,31 +23,34 @@
 {
 
 /// \brief Performs a depth-first-traversal of the vertices in a directed graph
-/// \param Graph The graph that should be traversed
-/// \param Visitor The visitor used at the traversal
-/// \param Vertex The Vertex where the search begins at
-/// \param EndAtStrategy Strategy what is done when all vertices are visited
-template<class Graph, class Visitor = ::boost::mgl::null_visitor, class Vertex = ::boost::mpl::void_, class EndAtStrategy = ::boost::mgl::EndAtEndOfGraph>
+/// \tparam Graph The graph that should be traversed
+/// \tparam Visitor The visitor used at the traversal
+/// \tparam Vertex The Vertex where the search begins at
+/// \tparam EndAtStrategy Strategy what is done when all vertices are visited
+template<
+ class Graph,
+ class Visitor = ::boost::mgl::null_visitor,
+ class Vertex = ::boost::mpl::void_,
+ class EndAtStrategy = ::boost::mgl::EndAtEndOfGraph
+>
 struct depth_first_search
 {
- typedef typename ::boost::mpl::eval_if<
- typename ::boost::is_same<Vertex, ::boost::mpl::void_>::type,
- ::boost::mgl::dfs_begin<
- Graph,
- EndAtStrategy,
- ::boost::mgl::RecordTrace< ::boost::mpl::vector0<> >,
- Visitor
- >,
- ::boost::mgl::dfs_find<
- Graph,
- Vertex,
- EndAtStrategy,
- ::boost::mgl::RecordTrace< ::boost::mpl::vector0<> >,
- Visitor
- >
- >::type iter;
+ typedef typename ::boost::mpl::eval_if<
+ typename ::boost::is_same<Vertex, ::boost::mpl::void_>::type,
+ ::boost::mgl::dfs_begin<
+ Graph,
+ EndAtStrategy,
+ Visitor
+ >,
+ ::boost::mgl::dfs_find<
+ Graph,
+ Vertex,
+ EndAtStrategy,
+ Visitor
+ >
+ >::type iter;
 
- typedef typename aux::template depth_first_search_impl<iter>::type type;
+ typedef typename aux::template depth_first_search_impl<iter>::type type;
 };
 
 } // namespace mgl

Modified: sandbox/mgl/boost/mgl/edge.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/edge.hpp (original)
+++ sandbox/mgl/boost/mgl/edge.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -7,8 +7,8 @@
 #ifndef BOOST_MGL_EDGE_HPP
 #define BOOST_MGL_EDGE_HPP
 
-#include <boost/mpl/vector.hpp>
 #include <boost/mpl/int.hpp>
+#include <boost/mpl/vector.hpp>
 
 namespace boost
 {
@@ -19,34 +19,34 @@
 template<class VertexFrom, class VertexTo, int Weight, class Properties = ::boost::mpl::vector0<> >
 struct edge
 {
- typedef VertexFrom vertex_from;
- typedef VertexTo vertex_to;
- typedef ::boost::mpl::int_<Weight> weight;
- typedef Properties properties;
+ typedef VertexFrom vertex_from;
+ typedef VertexTo vertex_to;
+ typedef ::boost::mpl::int_<Weight> weight;
+ typedef Properties properties;
 };
 
 template<class Edge>
 struct edge_begin_vertex
 {
- typedef typename Edge::vertex_from type;
+ typedef typename Edge::vertex_from type;
 };
 
 template<class Edge>
 struct edge_end_vertex
 {
- typedef typename Edge::vertex_to type;
+ typedef typename Edge::vertex_to type;
 };
 
 template<class Edge>
 struct edge_weight
 {
- typedef typename Edge::weight type;
+ typedef typename Edge::weight type;
 };
 
 template<class Edge>
 struct edge_properties
 {
- typedef typename Edge::properties type;
+ typedef typename Edge::properties type;
 };
 
 } // namespace mgl

Modified: sandbox/mgl/boost/mgl/find.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/find.hpp (original)
+++ sandbox/mgl/boost/mgl/find.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -24,40 +24,75 @@
 BOOST_MPL_HAS_XXX_TRAIT_DEF(bfs_find_supported)
 
 /// \brief Find a specified vertex inside a graph and return a DFS iterator.
-/// \param Graph Graph where the iteration should be performed
-/// \param Vertex Vertex that should be found inside the graph
-/// \param EndAtStrategy The strategy used to abort the iteration
-/// \param TracePolicy The policy used to trace the iteration
-/// \param Visitor The visitor class used during the iteration
-//template<class Graph, class Vertex, class EndAtStrategy = ::boost::mgl::EndAtEndOfGraph, class TracePolicy = ::boost::mgl::NoTrace, class Visitor = ::boost::mgl::null_visitor>
-template<class Graph, class Vertex, class EndAtStrategy = ::boost::mgl::EndAtEndOfGraph, class TracePolicy = ::boost::mgl::NoTrace, class Visitor = ::boost::mgl::null_visitor, class Enable = void>
+/// \tparam Graph Graph where the iteration should be performed
+/// \tparam Vertex Vertex that should be found inside the graph
+/// \tparam EndAtStrategy The strategy used to abort the iteration
+/// \tparam Visitor The visitor class used during the iteration
+template<
+ class Graph,
+ class Vertex,
+ class EndAtStrategy = ::boost::mgl::EndAtEndOfGraph,
+ class Visitor = ::boost::mgl::null_visitor,
+ class Enable = void
+>
 struct dfs_find
 {
- typedef ::boost::mpl::void_ type;
+ typedef ::boost::mpl::void_ type;
 };
 
-template<class Graph, class Vertex, class EndAtStrategy, class TracePolicy, class Visitor>
-struct dfs_find<Graph, Vertex, EndAtStrategy, TracePolicy, Visitor, typename ::boost::enable_if<has_dfs_find_supported<Graph> >::type>
+template<
+ class Graph,
+ class Vertex,
+ class EndAtStrategy,
+ class Visitor
+>
+struct dfs_find<
+ Graph,
+ Vertex,
+ EndAtStrategy,
+ Visitor,
+ typename ::boost::enable_if<
+ has_dfs_find_supported<Graph>
+ >::type
+>
 {
- typedef typename Graph::template dfs_find<Vertex, EndAtStrategy, TracePolicy, Visitor>::type type;
+ typedef typename Graph::template dfs_find<Vertex, EndAtStrategy, Visitor>::type type;
 };
 
 /// \brief Find a specified vertex inside a graph and return a BFS iterator.
-/// \param Graph Graph where the iteration should be performed
-/// \param Vertex Vertex that should be found inside the graph
-/// \param EndAtStrategy The strategy used to abort the iteration
-/// \param TracePolicy The policy used to trace the iteration
-/// \param Visitor The visitor class used during the iteration
-template<class Graph, class Vertex, class EndAtStrategy = ::boost::mgl::EndAtEndOfGraph, class TracePolicy = ::boost::mgl::NoTrace, class Visitor = ::boost::mgl::null_visitor, class Enable = void>
+/// \tparam Graph Graph where the iteration should be performed
+/// \tparam Vertex Vertex that should be found inside the graph
+/// \tparam EndAtStrategy The strategy used to abort the iteration
+/// \tparam Visitor The visitor class used during the iteration
+template<
+ class Graph,
+ class Vertex,
+ class EndAtStrategy = ::boost::mgl::EndAtEndOfGraph,
+ class Visitor = ::boost::mgl::null_visitor,
+ class Enable = void
+>
 struct bfs_find
 {
- typedef ::boost::mpl::void_ type;
+ typedef ::boost::mpl::void_ type;
 };
 
-template<class Graph, class Vertex, class EndAtStrategy, class TracePolicy, class Visitor>
-struct bfs_find<Graph, Vertex, EndAtStrategy, TracePolicy, Visitor, typename ::boost::enable_if<has_bfs_find_supported<Graph> >::type>
+template<
+ class Graph,
+ class Vertex,
+ class EndAtStrategy,
+ class Visitor
+>
+struct bfs_find<
+ Graph,
+ Vertex,
+ EndAtStrategy,
+ Visitor,
+ typename ::boost::enable_if<
+ has_bfs_find_supported<Graph>
+ >::type
+>
 {
- typedef typename Graph::template bfs_find<Vertex, EndAtStrategy, TracePolicy, Visitor>::type type;
+ typedef typename Graph::template bfs_find<Vertex, EndAtStrategy, Visitor>::type type;
 };
 
 } // namespace mgl

Modified: sandbox/mgl/boost/mgl/graph.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/graph.hpp (original)
+++ sandbox/mgl/boost/mgl/graph.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -7,52 +7,51 @@
 #ifndef BOOST_MGL_GRAPH_HPP
 #define BOOST_MGL_GRAPH_HPP
 
-#include <vector>
-
-#include <boost/mpl/for_each.hpp>
-#include <boost/mpl/fold.hpp>
-#include <boost/mpl/map.hpp>
-#include <boost/mpl/if.hpp>
-#include <boost/mpl/has_key.hpp>
-#include <boost/mpl/placeholders.hpp>
-#include <boost/mpl/pair.hpp>
-#include <boost/mpl/void.hpp>
-#include <boost/mpl/insert.hpp>
-#include <boost/mpl/transform.hpp>
+#include <boost/mpl/accumulate.hpp>
 #include <boost/mpl/at.hpp>
-#include <boost/mpl/find.hpp>
+#include <boost/mpl/back.hpp>
 #include <boost/mpl/begin_end.hpp>
-#include <boost/mpl/int.hpp>
-#include <boost/mpl/equal.hpp>
-#include <boost/mpl/set.hpp>
-#include <boost/mpl/size.hpp>
+#include <boost/mpl/comparison.hpp>
 #include <boost/mpl/contains.hpp>
 #include <boost/mpl/deref.hpp>
-#include <boost/mpl/front.hpp>
-#include <boost/mpl/push_back.hpp>
-#include <boost/mpl/pop_back.hpp>
-#include <boost/mpl/back.hpp>
 #include <boost/mpl/empty.hpp>
+#include <boost/mpl/equal.hpp>
 #include <boost/mpl/eval_if.hpp>
+#include <boost/mpl/find.hpp>
+#include <boost/mpl/fold.hpp>
+#include <boost/mpl/for_each.hpp>
+#include <boost/mpl/front.hpp>
+#include <boost/mpl/greater_equal.hpp>
+#include <boost/mpl/has_key.hpp>
+#include <boost/mpl/has_xxx.hpp>
+#include <boost/mpl/if.hpp>
+#include <boost/mpl/insert.hpp>
+#include <boost/mpl/int.hpp>
 #include <boost/mpl/joint_view.hpp>
+#include <boost/mpl/map.hpp>
+#include <boost/mpl/pair.hpp>
+#include <boost/mpl/placeholders.hpp>
+#include <boost/mpl/pop_back.hpp>
 #include <boost/mpl/pop_front.hpp>
-#include <boost/mpl/accumulate.hpp>
-#include <boost/mpl/greater_equal.hpp>
-#include <boost/mpl/comparison.hpp>
+#include <boost/mpl/push_back.hpp>
+#include <boost/mpl/set.hpp>
+#include <boost/mpl/size.hpp>
+#include <boost/mpl/transform.hpp>
+#include <boost/mpl/void.hpp>
 
-#include <boost/utility/enable_if.hpp>
 #include <boost/type_traits/is_same.hpp>
 #include <boost/type_traits/is_void.hpp>
+#include <boost/utility/enable_if.hpp>
 
-#include <boost/mgl/graph_policies.hpp>
-#include <boost/mgl/row.hpp>
+#include <boost/mgl/colors.hpp>
 #include <boost/mgl/edge.hpp>
-#include <boost/mgl/v_prop.hpp>
+#include <boost/mgl/graph_policies.hpp>
 #include <boost/mgl/iterator.hpp>
+#include <boost/mgl/row.hpp>
 #include <boost/mgl/visitor_helpers.hpp>
-#include <boost/mgl/colors.hpp>
-#include <boost/mgl/aux_/vertex.hpp>
+#include <boost/mgl/v_prop.hpp>
 #include <boost/mgl/aux_/utility.hpp>
+#include <boost/mgl/aux_/vertex.hpp>
 
 namespace boost
 {
@@ -60,1135 +59,1089 @@
 namespace mgl
 {
 
+BOOST_MPL_HAS_XXX_TRAIT_DEF(edge_list)
+
 template<
- class Derived,
- class VmapGenerator // policy class to build the map of vertices
+ class Derived,
+ class VmapGenerator // policy class to build the map of vertices
>
 class graph
 {
 public:
- struct get_vertices;
+ struct get_vertices;
 
 private:
- // get the properties of a given vertex as a vector from the derived graph
- // class
- template<class Vertex>
- struct build_vertex_properties
- {
- // get the vertex property list of the graph
- typedef typename Derived::vertex_property_list vertex_property_list;
-
- // transform the vertex property list into a list only containing the
- // vertices
- typedef typename ::boost::mpl::transform<
- vertex_property_list,
- v_prop_vertex< ::boost::mpl::placeholders::_1>
- >::type vertices;
-
- // search for 'Vertex'
- typedef typename ::boost::mpl::find<
- vertices,
- Vertex
- >::type vertex_iter;
-
- // get iterator to end of the property list
- typedef typename ::boost::mpl::end<vertices>::type last_prop_vertex;
-
- // return an empty vector if 'Vertex' isn't found (no properties exists
- // for 'Vertex') or the properties of 'Vertex'
- typedef typename ::boost::mpl::if_<
- ::boost::is_same<vertex_iter, last_prop_vertex>,
- ::boost::mpl::vector0<>,
- typename v_prop_property<
- typename ::boost::mpl::at<
- vertex_property_list,
- ::boost::mpl::int_<vertex_iter::pos::value>
- >::type
- >::type
- >::type type;
- };
-
- // create a map containing all vertices of the graph stored as keys and
- // their adjacency vertices and weights as values
- struct create_vertex_map
- {
- // adjacency list of the graph
- typedef typename Derived::adjacency_list adjacency_list;
-
- // create a map containing the graph vertices as keys and their
- // adjacency vertices inside a vector as values
- typedef typename ::boost::mpl::fold<
- adjacency_list,
- ::boost::mpl::map0<>,
- ::boost::mpl::insert<
- ::boost::mpl::placeholders::_1,
- ::boost::mpl::pair<
- aux::row_start_vertex< ::boost::mpl::placeholders::_2>,
- ::boost::mpl::pair<
- build_vertex_properties<aux::row_start_vertex< ::boost::mpl::placeholders::_2> >,
- aux::row_adjacency_vertices< ::boost::mpl::placeholders::_2>
- >
- >
- >
- >::type type;
- };
-
- // create a map containing all nodes which are connected with an edge to
- // 'VertexFrom' as key and their properties as value
- template<class VertexFrom>
- struct create_edge_nodes
- {
- typedef typename ::boost::mpl::fold<
- typename Derived::edge_list,
- ::boost::mpl::map0<>,
- ::boost::mpl::if_<
- ::boost::is_same<
- edge_begin_vertex< ::boost::mpl::placeholders::_2>,
- VertexFrom
- >,
- ::boost::mpl::insert<
- ::boost::mpl::placeholders::_1,
- ::boost::mpl::pair<
- edge_end_vertex< ::boost::mpl::placeholders::_2>,
- ::boost::mpl::pair<
- edge_weight< ::boost::mpl::placeholders::_2>,
- edge_properties< ::boost::mpl::placeholders::_2>
- >
- >
- >,
- ::boost::mpl::placeholders::_1
- >
- >::type type;
- };
-
- // create a map containing all edges with their properties and weights
- struct create_edge_map
- {
- typedef typename ::boost::mpl::fold<
- typename get_vertices::type,
- ::boost::mpl::map0<>,
- ::boost::mpl::insert<
- ::boost::mpl::placeholders::_1,
- ::boost::mpl::pair<
- ::boost::mpl::placeholders::_2,
- create_edge_nodes< ::boost::mpl::placeholders::_2>
- >
- >
- >::type type;
- };
-
- template<class MapEntry>
- struct get_map_entry_first
- {
- typedef typename MapEntry::first type;
- };
-
- template<class AdjacencyList>
- struct get_start_nodes
- {
- typedef typename ::boost::mpl::transform<
- AdjacencyList,
- aux::row_start_vertex< ::boost::mpl::placeholders::_1>
- >::type type;
- };
-
- template<class AdjacencyList>
- struct get_adjacency_vertices
- {
- typedef typename ::boost::mpl::transform<
- AdjacencyList,
- aux::row_adjacency_vertices< ::boost::mpl::placeholders::_1>
- >::type type;
- };
-
- template<class StartVertex, class FindVertex, class TraversalStack>
- struct find_vertex_impl
- {
- // get the adjacency list from the graph
- typedef typename Derived::adjacency_list adjacency_list;
-
- // create a separate list only containing the start nodes
- typedef typename ::boost::mpl::transform<
- adjacency_list,
- aux::row_start_vertex< ::boost::mpl::placeholders::_1>
- >::type start_nodes;
-
- BOOST_MPL_ASSERT_RELATION(::boost::mpl::size<start_nodes>::value, ==, ::boost::mpl::size<adjacency_list>::value);
-
- // get an iterator to the row of 'StartNode' from the graph's adjacency list
- typedef typename ::boost::mpl::find<
- start_nodes,
- StartVertex
- >::type row_iter;
-
- //! @todo Add check for iterator!
-
- // get the adjacency nodes of 'StartNode'
- typedef typename aux::row_adjacency_vertices<
- typename ::boost::mpl::at<
- adjacency_list,
- ::boost::mpl::int_<row_iter::pos::value>
- >::type
- >::type adjacency_vertices;
-
- // dereference iterator to get the row itself
- typedef typename ::boost::mpl::deref<row_iter>::type row;
-
- // add node to the traversal stack
- typedef typename ::boost::mpl::if_<
- ::boost::mpl::contains<
- TraversalStack,
- StartVertex
- >,
- TraversalStack,
- typename ::boost::mpl::push_back<
- TraversalStack,
- StartVertex
- >::type
- >::type ext_traversal_stack;
-
- // call 'find_node_impl' recursively to traverse through the adjacency nodes of 'StartNode'
- //! @todo Optimize this O(N^2) operation!!!
- typedef typename ::boost::mpl::if_<
- ::boost::mpl::contains<
- ext_traversal_stack,
- FindVertex
- >,
- ext_traversal_stack,
- typename ::boost::mpl::fold<
- adjacency_vertices,
- ext_traversal_stack,
- ::boost::mpl::if_<
- ::boost::mpl::contains<
- ::boost::mpl::placeholders::_1,
- ::boost::mpl::placeholders::_2
- >,
- ::boost::mpl::placeholders::_1,
- ::boost::mpl::if_<
- ::boost::mpl::contains<
- ::boost::mpl::placeholders::_1,
- FindVertex
- >,
- ::boost::mpl::placeholders::_1,
- find_vertex_impl<
- ::boost::mpl::placeholders::_2,
- FindVertex,
- ::boost::mpl::placeholders::_1
- >
- >
- >
- >::type
- >::type type;
- };
-
- // build a representation (map) for all vertices and their adjacency vertices
- //struct build_vertices_map
- //{
- // typedef typename ::boost::mpl::fold<
- // typename Derived::adjacency_list,
- // ::boost::mpl::map0<>,
- // ::boost::mpl::insert<
- // ::boost::mpl::placeholders::_1,
- // ::boost::mpl::pair<
- // aux::row_start_vertex< ::boost::mpl::placeholders::_2>,
- // aux::row_adjacency_vertices< ::boost::mpl::placeholders::_2>
- // >
- // >
- // >::type type;
- //};
-
- // build a representation (set) of all vertices of the graph
- struct build_vertices_set
- {
- typedef typename ::boost::mpl::fold<
- typename Derived::adjacency_list,
- ::boost::mpl::set0<>,
- ::boost::mpl::insert<
- ::boost::mpl::placeholders::_1,
- aux::row_start_vertex< ::boost::mpl::placeholders::_2>
- >
- >::type type;
- };
-
- template<class ColorMap>
- struct get_next_unvisited
- {
- typedef typename ::boost::mpl::fold<
- typename build_vertices_set::type,
- ::boost::mpl::vector0<>,
- ::boost::mpl::if_<
- ::boost::is_same<
- get_color< ::boost::mpl::placeholders::_2, ColorMap>,
- white
- >,
- ::boost::mpl::push_back< ::boost::mpl::placeholders::_1, ::boost::mpl::placeholders::_2>,
- ::boost::mpl::placeholders::_1
- >
- >::type unvisited_vertices;
-
- typedef typename ::boost::mpl::if_<
- typename ::boost::mpl::empty<unvisited_vertices>::type,
- typename Derived::end::type,
- typename ::boost::mpl::front<unvisited_vertices>::type
- >::type type;
- };
-
- template<class Vertex, class ColorMap, class TraversalStack, class EndAtStrategy, class Enable = void>
- struct get_next_vertex_dfs
- {
- // get the adjacency vertices of 'Vertex'
- typedef typename ::boost::mpl::at<
- //typename build_vertices_map::type,
- typename VmapGenerator::template apply<typename Derived::adjacency_list>::type,
- Vertex
- >::type adjacency_vertices;
-
- // build a vector with all unvisited adjacency vertices
- //! @todo Try to optimize this!
- typedef typename ::boost::mpl::fold<
- adjacency_vertices,
- ::boost::mpl::vector0<>,
- ::boost::mpl::if_<
- ::boost::is_same<
- get_color< ::boost::mpl::placeholders::_2, ColorMap>,
- white
- >,
- ::boost::mpl::push_back< ::boost::mpl::placeholders::_1, ::boost::mpl::placeholders::_2>,
- ::boost::mpl::placeholders::_1
- >
- >::type unvisited_vertices;
-
- // check if current vertex should be marked as 'black'
- typedef typename ::boost::mpl::if_<
- typename ::boost::mpl::empty<unvisited_vertices>::type,
- typename set_color<Vertex, black, ColorMap>::type,
- ColorMap
- >::type color_map;
-
- typedef typename ::boost::mpl::eval_if<
- typename ::boost::mpl::empty<unvisited_vertices>::type,
- // search recursively
- get_next_vertex_dfs<
- typename ::boost::mpl::back<TraversalStack>::type,
- color_map,
- typename ::boost::mpl::pop_back<TraversalStack>::type,
- EndAtStrategy
- >,
- ::boost::mpl::front<unvisited_vertices>
- >::type type;
- };
-
- // specialication when traversal stack is empty
- template<class Vertex, class ColorMap, class TraversalStack, class EndAtStrategy>
- struct get_next_vertex_dfs<Vertex, ColorMap, TraversalStack, EndAtStrategy, typename ::boost::enable_if< ::boost::mpl::empty<TraversalStack> >::type>
- {
- // get the adjacency vertices of 'Vertex'
- typedef typename ::boost::mpl::at<
- //typename build_vertices_map::type,
- typename VmapGenerator::template apply<typename Derived::adjacency_list>::type,
- Vertex
- >::type adjacency_vertices;
-
- // build a vector with all unvisited adjacency vertices
- //! @todo Try to optimize this!
- typedef typename ::boost::mpl::fold<
- adjacency_vertices,
- ::boost::mpl::vector0<>,
- ::boost::mpl::if_<
- ::boost::is_same<
- get_color< ::boost::mpl::placeholders::_2, ColorMap>,
- white
- >,
- ::boost::mpl::push_back< ::boost::mpl::placeholders::_1, ::boost::mpl::placeholders::_2>,
- ::boost::mpl::placeholders::_1
- >
- >::type unvisited_vertices;
-
- // check if current vertex should be marked as 'black'
- typedef typename ::boost::mpl::if_<
- typename ::boost::mpl::empty<unvisited_vertices>::type,
- typename set_color<Vertex, black, ColorMap>::type,
- ColorMap
- >::type color_map;
-
- typedef typename ::boost::mpl::eval_if<
- typename ::boost::mpl::empty<unvisited_vertices>::type,
- // no vertices are reachable -> find unreachables
- ::boost::mpl::eval_if<
- typename ::boost::is_same<EndAtStrategy, ::boost::mgl::EndAtEndOfGraph>::type,
- get_next_unvisited<ColorMap>,
- typename Derived::end::type
- >,
- ::boost::mpl::front<unvisited_vertices>
- >::type type;
- };
-
- // get the next unvisited adjacency vertex from a given vertex
- template<class ColorMap, class TraversalStack, class EndAtStrategy>
- struct get_next_vertex_bfs
- {
- BOOST_MPL_ASSERT_NOT(( ::boost::mpl::empty<TraversalStack> ));
-
- // get the adjacency vertices of 'Vertex'
- typedef typename ::boost::mpl::at<
- //typename build_vertices_map::type,
- typename VmapGenerator::template apply<typename Derived::adjacency_list>::type,
- typename ::boost::mpl::front<TraversalStack>::type
- >::type adjacency_vertices;
-
- // build a vector with all unvisited adjacency vertices
- //! @todo Try to optimize this!
- typedef typename ::boost::mpl::fold<
- adjacency_vertices,
- ::boost::mpl::vector0<>,
- ::boost::mpl::if_<
- ::boost::is_same<
- get_color< ::boost::mpl::placeholders::_2, ColorMap>,
- white
- >,
- ::boost::mpl::push_back< ::boost::mpl::placeholders::_1, ::boost::mpl::placeholders::_2>,
- ::boost::mpl::placeholders::_1
- >
- >::type unvisited_vertices;
-
- // check if current vertex should be marked as 'black'
- typedef typename ::boost::mpl::if_<
- typename ::boost::mpl::empty<unvisited_vertices>::type,
- typename set_color<
- typename ::boost::mpl::front<TraversalStack>::type,
- black,
- ColorMap>::type,
- ColorMap
- >::type color_map;
-
- // push back next vertex to traversal stack
- typedef typename ::boost::mpl::if_<
- typename ::boost::mpl::empty<unvisited_vertices>::type,
- // dequeue first entry or ...
- typename ::boost::mpl::pop_front<TraversalStack>::type,
- // ... enqueue next unvisited adjacency vertex
- //typename ::boost::mpl::push_back<
- // TraversalStack,
- // typename ::boost::mpl::front<unvisited_vertices>::type
- //>::type
- TraversalStack
- >::type traversal_stack;
-
- typedef typename ::boost::mpl::eval_if<
- typename ::boost::mpl::empty<unvisited_vertices>::type,
- // search recursively
- ::boost::mpl::eval_if<
- typename ::boost::mpl::empty<traversal_stack>::type,
- // no vertices are reachable -> find unreachables
- ::boost::mpl::eval_if<
- typename ::boost::is_same<EndAtStrategy, ::boost::mgl::EndAtEndOfGraph>::type,
- get_next_unvisited<ColorMap>,
- typename Derived::end::type
- >,
- get_next_vertex_bfs<
- color_map,
- traversal_stack,
- EndAtStrategy
- >
- >,
- ::boost::mpl::front<unvisited_vertices>
- >::type type;
- };
+ // get the properties of a given vertex as a vector from the derived graph
+ // class
+ template<class Vertex>
+ struct build_vertex_properties
+ {
+ // get the vertex property list of the graph
+ typedef typename Derived::vertex_property_list vertex_property_list;
+
+ // transform the vertex property list into a list only containing the
+ // vertices
+ typedef typename ::boost::mpl::transform<
+ vertex_property_list,
+ v_prop_vertex< ::boost::mpl::placeholders::_1>
+ >::type vertices;
+
+ // search for 'Vertex'
+ typedef typename ::boost::mpl::find<
+ vertices,
+ Vertex
+ >::type vertex_iter;
+
+ // get iterator to end of the property list
+ typedef typename ::boost::mpl::end<vertices>::type last_prop_vertex;
+
+ // return an empty vector if 'Vertex' isn't found (no properties exists
+ // for 'Vertex') or the properties of 'Vertex'
+ typedef typename ::boost::mpl::if_<
+ ::boost::is_same<vertex_iter, last_prop_vertex>,
+ ::boost::mpl::vector0<>,
+ typename v_prop_property<
+ typename ::boost::mpl::at<
+ vertex_property_list,
+ ::boost::mpl::int_<vertex_iter::pos::value>
+ >::type
+ >::type
+ >::type type;
+ };
+
+ // create a map containing all vertices of the graph stored as keys and
+ // their adjacency vertices and weights as values
+ struct create_vertex_map
+ {
+ // adjacency list of the graph
+ typedef typename Derived::adjacency_list adjacency_list;
+
+ // create a map containing the graph vertices as keys and their
+ // adjacency vertices inside a vector as values
+ typedef typename ::boost::mpl::fold<
+ adjacency_list,
+ ::boost::mpl::map0<>,
+ ::boost::mpl::insert<
+ ::boost::mpl::placeholders::_1,
+ ::boost::mpl::pair<
+ aux::row_start_vertex< ::boost::mpl::placeholders::_2>,
+ ::boost::mpl::pair<
+ build_vertex_properties<aux::row_start_vertex< ::boost::mpl::placeholders::_2> >,
+ aux::row_adjacency_vertices< ::boost::mpl::placeholders::_2>
+ >
+ >
+ >
+ >::type type;
+ };
+
+ // create a map containing all nodes which are connected with an edge to
+ // 'VertexFrom' as key and their properties as value
+ template<class VertexFrom>
+ struct create_edge_nodes
+ {
+ typedef typename ::boost::mpl::fold<
+ typename Derived::edge_list,
+ ::boost::mpl::map0<>,
+ ::boost::mpl::if_<
+ ::boost::is_same<
+ edge_begin_vertex< ::boost::mpl::placeholders::_2>,
+ VertexFrom
+ >,
+ ::boost::mpl::insert<
+ ::boost::mpl::placeholders::_1,
+ ::boost::mpl::pair<
+ edge_end_vertex< ::boost::mpl::placeholders::_2>,
+ ::boost::mpl::pair<
+ edge_weight< ::boost::mpl::placeholders::_2>,
+ edge_properties< ::boost::mpl::placeholders::_2>
+ >
+ >
+ >,
+ ::boost::mpl::placeholders::_1
+ >
+ >::type type;
+ };
+
+ // create a map containing all edges with their properties and weights
+ struct create_edge_map
+ {
+ typedef typename ::boost::mpl::fold<
+ typename get_vertices::type,
+ ::boost::mpl::map0<>,
+ ::boost::mpl::insert<
+ ::boost::mpl::placeholders::_1,
+ ::boost::mpl::pair<
+ ::boost::mpl::placeholders::_2,
+ create_edge_nodes< ::boost::mpl::placeholders::_2>
+ >
+ >
+ >::type type;
+ };
+
+ template<class MapEntry>
+ struct get_map_entry_first
+ {
+ typedef typename MapEntry::first type;
+ };
+
+ template<class AdjacencyList>
+ struct get_start_nodes
+ {
+ typedef typename ::boost::mpl::transform<
+ AdjacencyList,
+ aux::row_start_vertex< ::boost::mpl::placeholders::_1>
+ >::type type;
+ };
+
+ template<class AdjacencyList>
+ struct get_adjacency_vertices
+ {
+ typedef typename ::boost::mpl::transform<
+ AdjacencyList,
+ aux::row_adjacency_vertices< ::boost::mpl::placeholders::_1>
+ >::type type;
+ };
+
+ template<class StartVertex, class FindVertex, class TraversalStack>
+ struct find_vertex_impl
+ {
+ // get the adjacency list from the graph
+ typedef typename Derived::adjacency_list adjacency_list;
+
+ // create a separate list only containing the start nodes
+ typedef typename ::boost::mpl::transform<
+ adjacency_list,
+ aux::row_start_vertex< ::boost::mpl::placeholders::_1>
+ >::type start_nodes;
+
+ BOOST_MPL_ASSERT_RELATION(::boost::mpl::size<start_nodes>::value, ==, ::boost::mpl::size<adjacency_list>::value);
+
+ // get an iterator to the row of 'StartNode' from the graph's adjacency list
+ typedef typename ::boost::mpl::find<
+ start_nodes,
+ StartVertex
+ >::type row_iter;
+
+ //! @todo Add check for iterator!
+
+ // get the adjacency nodes of 'StartNode'
+ typedef typename aux::row_adjacency_vertices<
+ typename ::boost::mpl::at<
+ adjacency_list,
+ ::boost::mpl::int_<row_iter::pos::value>
+ >::type
+ >::type adjacency_vertices;
+
+ // dereference iterator to get the row itself
+ typedef typename ::boost::mpl::deref<row_iter>::type row;
+
+ // add node to the traversal stack
+ typedef typename ::boost::mpl::if_<
+ ::boost::mpl::contains<
+ TraversalStack,
+ StartVertex
+ >,
+ TraversalStack,
+ typename ::boost::mpl::push_back<
+ TraversalStack,
+ StartVertex
+ >::type
+ >::type ext_traversal_stack;
+
+ // call 'find_node_impl' recursively to traverse through the adjacency nodes of 'StartNode'
+ //! @todo Optimize this O(N^2) operation!!!
+ typedef typename ::boost::mpl::if_<
+ ::boost::mpl::contains<
+ ext_traversal_stack,
+ FindVertex
+ >,
+ ext_traversal_stack,
+ typename ::boost::mpl::fold<
+ adjacency_vertices,
+ ext_traversal_stack,
+ ::boost::mpl::if_<
+ ::boost::mpl::contains<
+ ::boost::mpl::placeholders::_1,
+ ::boost::mpl::placeholders::_2
+ >,
+ ::boost::mpl::placeholders::_1,
+ ::boost::mpl::if_<
+ ::boost::mpl::contains<
+ ::boost::mpl::placeholders::_1,
+ FindVertex
+ >,
+ ::boost::mpl::placeholders::_1,
+ find_vertex_impl<
+ ::boost::mpl::placeholders::_2,
+ FindVertex,
+ ::boost::mpl::placeholders::_1
+ >
+ >
+ >
+ >::type
+ >::type type;
+ };
+
+ // build a representation (set) of all vertices of the graph
+ struct build_vertices_set
+ {
+ typedef typename ::boost::mpl::fold<
+ typename Derived::adjacency_list,
+ ::boost::mpl::set0<>,
+ ::boost::mpl::insert<
+ ::boost::mpl::placeholders::_1,
+ aux::row_start_vertex< ::boost::mpl::placeholders::_2>
+ >
+ >::type type;
+ };
+
+ template<class ColorMap>
+ struct get_next_unvisited
+ {
+ typedef typename ::boost::mpl::fold<
+ typename build_vertices_set::type,
+ ::boost::mpl::vector0<>,
+ ::boost::mpl::if_<
+ ::boost::is_same<
+ get_color< ::boost::mpl::placeholders::_2, ColorMap>,
+ white
+ >,
+ ::boost::mpl::push_back< ::boost::mpl::placeholders::_1, ::boost::mpl::placeholders::_2>,
+ ::boost::mpl::placeholders::_1
+ >
+ >::type unvisited_vertices;
+
+ typedef typename ::boost::mpl::if_<
+ typename ::boost::mpl::empty<unvisited_vertices>::type,
+ typename Derived::end::type,
+ typename ::boost::mpl::front<unvisited_vertices>::type
+ >::type type;
+ };
+
+ template<class Vertex, class ColorMap, class TraversalStack, class EndAtStrategy, class Enable = void>
+ struct get_next_vertex_dfs
+ {
+ // get the adjacency vertices of 'Vertex'
+ typedef typename ::boost::mpl::at<
+ typename VmapGenerator::template apply<typename Derived::adjacency_list>::type,
+ Vertex
+ >::type adjacency_vertices;
+
+ // build a vector with all unvisited adjacency vertices
+ //! @todo Try to optimize this!
+ typedef typename ::boost::mpl::fold<
+ adjacency_vertices,
+ ::boost::mpl::vector0<>,
+ ::boost::mpl::if_<
+ ::boost::is_same<
+ get_color< ::boost::mpl::placeholders::_2, ColorMap>,
+ white
+ >,
+ ::boost::mpl::push_back< ::boost::mpl::placeholders::_1, ::boost::mpl::placeholders::_2>,
+ ::boost::mpl::placeholders::_1
+ >
+ >::type unvisited_vertices;
+
+ // check if current vertex should be marked as 'black'
+ typedef typename ::boost::mpl::if_<
+ typename ::boost::mpl::empty<unvisited_vertices>::type,
+ typename set_color<Vertex, black, ColorMap>::type,
+ ColorMap
+ >::type color_map;
+
+ typedef typename ::boost::mpl::eval_if<
+ typename ::boost::mpl::empty<unvisited_vertices>::type,
+ // search recursively
+ get_next_vertex_dfs<
+ typename ::boost::mpl::back<TraversalStack>::type,
+ color_map,
+ typename ::boost::mpl::pop_back<TraversalStack>::type,
+ EndAtStrategy
+ >,
+ ::boost::mpl::front<unvisited_vertices>
+ >::type type;
+ };
+
+ // specialication when traversal stack is empty
+ template<class Vertex, class ColorMap, class TraversalStack, class EndAtStrategy>
+ struct get_next_vertex_dfs<Vertex, ColorMap, TraversalStack, EndAtStrategy, typename ::boost::enable_if< ::boost::mpl::empty<TraversalStack> >::type>
+ {
+ // get the adjacency vertices of 'Vertex'
+ typedef typename ::boost::mpl::at<
+ //typename build_vertices_map::type,
+ typename VmapGenerator::template apply<typename Derived::adjacency_list>::type,
+ Vertex
+ >::type adjacency_vertices;
+
+ // build a vector with all unvisited adjacency vertices
+ //! @todo Try to optimize this!
+ typedef typename ::boost::mpl::fold<
+ adjacency_vertices,
+ ::boost::mpl::vector0<>,
+ ::boost::mpl::if_<
+ ::boost::is_same<
+ get_color< ::boost::mpl::placeholders::_2, ColorMap>,
+ white
+ >,
+ ::boost::mpl::push_back< ::boost::mpl::placeholders::_1, ::boost::mpl::placeholders::_2>,
+ ::boost::mpl::placeholders::_1
+ >
+ >::type unvisited_vertices;
+
+ // check if current vertex should be marked as 'black'
+ typedef typename ::boost::mpl::if_<
+ typename ::boost::mpl::empty<unvisited_vertices>::type,
+ typename set_color<Vertex, black, ColorMap>::type,
+ ColorMap
+ >::type color_map;
+
+ typedef typename ::boost::mpl::eval_if<
+ typename ::boost::mpl::empty<unvisited_vertices>::type,
+ // no vertices are reachable -> find unreachables
+ ::boost::mpl::eval_if<
+ typename ::boost::is_same<EndAtStrategy, ::boost::mgl::EndAtEndOfGraph>::type,
+ get_next_unvisited<ColorMap>,
+ typename Derived::end::type
+ >,
+ ::boost::mpl::front<unvisited_vertices>
+ >::type type;
+ };
+
+ // get the next unvisited adjacency vertex from a given vertex
+ template<class ColorMap, class TraversalStack, class EndAtStrategy>
+ struct get_next_vertex_bfs
+ {
+ BOOST_MPL_ASSERT_NOT(( ::boost::mpl::empty<TraversalStack> ));
+
+ // get the adjacency vertices of 'Vertex'
+ typedef typename ::boost::mpl::at<
+ typename VmapGenerator::template apply<typename Derived::adjacency_list>::type,
+ typename ::boost::mpl::front<TraversalStack>::type
+ >::type adjacency_vertices;
+
+ // build a vector with all unvisited adjacency vertices
+ //! @todo Try to optimize this!
+ typedef typename ::boost::mpl::fold<
+ adjacency_vertices,
+ ::boost::mpl::vector0<>,
+ ::boost::mpl::if_<
+ ::boost::is_same<
+ get_color< ::boost::mpl::placeholders::_2, ColorMap>,
+ white
+ >,
+ ::boost::mpl::push_back< ::boost::mpl::placeholders::_1, ::boost::mpl::placeholders::_2>,
+ ::boost::mpl::placeholders::_1
+ >
+ >::type unvisited_vertices;
+
+ // check if current vertex should be marked as 'black'
+ typedef typename ::boost::mpl::if_<
+ typename ::boost::mpl::empty<unvisited_vertices>::type,
+ typename set_color<
+ typename ::boost::mpl::front<TraversalStack>::type,
+ black,
+ ColorMap>::type,
+ ColorMap
+ >::type color_map;
+
+ // push back next vertex to traversal stack
+ typedef typename ::boost::mpl::if_<
+ typename ::boost::mpl::empty<unvisited_vertices>::type,
+ // dequeue first entry or ...
+ typename ::boost::mpl::pop_front<TraversalStack>::type,
+ // ... enqueue next unvisited adjacency vertex
+ //typename ::boost::mpl::push_back<
+ // TraversalStack,
+ // typename ::boost::mpl::front<unvisited_vertices>::type
+ //>::type
+ TraversalStack
+ >::type traversal_stack;
+
+ typedef typename ::boost::mpl::eval_if<
+ typename ::boost::mpl::empty<unvisited_vertices>::type,
+ // search recursively
+ ::boost::mpl::eval_if<
+ typename ::boost::mpl::empty<traversal_stack>::type,
+ // no vertices are reachable -> find unreachables
+ ::boost::mpl::eval_if<
+ typename ::boost::is_same<EndAtStrategy, ::boost::mgl::EndAtEndOfGraph>::type,
+ get_next_unvisited<ColorMap>,
+ typename Derived::end::type
+ >,
+ get_next_vertex_bfs<
+ color_map,
+ traversal_stack,
+ EndAtStrategy
+ >
+ >,
+ ::boost::mpl::front<unvisited_vertices>
+ >::type type;
+ };
 
 public:
- // get all vertices of the graph
- struct get_vertices
- {
- // get the start vertices of the adjacency list
- typedef typename get_start_nodes<typename Derived::adjacency_list>::type start_nodes;
-
- // add those vertices to an empty set
- typedef typename ::boost::mpl::fold<
- start_nodes,
- ::boost::mpl::set0<>,
- ::boost::mpl::if_<
- ::boost::mpl::has_key< ::boost::mpl::placeholders::_1, ::boost::mpl::placeholders::_2>,
- ::boost::mpl::placeholders::_1,
- ::boost::mpl::insert< ::boost::mpl::placeholders::_1, ::boost::mpl::placeholders::_2>
- >
- >::type start_set;
-
- // get the adjacency vertices of the start nodes
- typedef typename get_adjacency_vertices<typename Derived::adjacency_list>::type adjacency_nodes;
-
- // add those vertices to the former created set
- typedef typename ::boost::mpl::fold<
- adjacency_nodes,
- start_set,
- aux::vec_to_set< ::boost::mpl::placeholders::_1, ::boost::mpl::placeholders::_2>
- >::type type;
- };
-
- // get the properties of a given vertex as a vector
- template<class Vertex>
- struct get_vertex_properties
- {
- // transform the vertex property list into a list only containing the
- // vertices
- typedef typename get_map_entry_first<
- typename ::boost::mpl::at<
- typename create_vertex_map::type,
- Vertex
- >::type
- >::type type;
- };
-
- /// \brief Get the properties of a given egde as a vector
- /// \param VertexFrom Source vertex of the edge
- /// \param VertexTo Target vertex of the edge
- template<class VertexFrom, class VertexTo>
- struct get_edge_properties
- {
- // get the edge map
- typedef typename create_edge_map::type edge_map;
-
- // get element 'VertexFrom' at edge map
- typedef typename ::boost::mpl::at<
- edge_map,
- VertexFrom
- >::type type_;
-
- // get element 'VertexTo' at nested map
- typedef typename ::boost::mpl::at<
- type_,
- VertexTo
- >::type type__;
-
- // check if the edge really exists
- typedef typename ::boost::mpl::if_<
- ::boost::is_same<type__, ::boost::mpl::void_>,
- ::boost::mpl::void_,
- typename type__::second
- >::type type;
- };
-
- /// \brief Get the weight of a given egde
- /// \param VertexFrom Source vertex of the edge
- /// \param VertexTo Target vertex of the edge
- template<class VertexFrom, class VertexTo>
- struct get_edge_weight
- {
- // get the edge map
- typedef typename create_edge_map::type edge_map;
-
- // get element 'VertexFrom' at edge map
- typedef typename ::boost::mpl::at<
- edge_map,
- VertexFrom
- >::type type_;
-
- // get element 'VertexTo' at nested map
- typedef typename ::boost::mpl::at<
- type_,
- VertexTo
- >::type type__;
-
- // weight is stored at first entry of pair
- typedef typename type__::first weight;
-
- // get integer value of the weight
- enum { value = weight::type::value };
- };
-
- template<class StartVertex, class FindVertex>
- struct find_vertex
- {
- typedef typename find_vertex_impl<StartVertex, FindVertex, ::boost::mpl::vector0<> >::type type;
- };
-
- // needed to make detection of 'dfs_begin' possible for this graph type
- typedef ::boost::mpl::void_ dfs_begin_supported;
-
- /// \brief Get a DFS iterator to the begin of the graph
- /// \param EndAtStrategy The strategy used to abort the iteration
- /// \param TracePolicy The policy used to trace the iteration
- /// \param Visitor The visitor class used during the iteration
- template<class EndAtStrategy, class TracePolicy, class Visitor>
- struct dfs_begin
- {
- // initialize the visitor
- typedef typename Visitor::on_init::type visitor_init;
-
- // get the first vertex
- typedef typename ::boost::mpl::front<
- //typename build_vertices_map::type
- typename VmapGenerator::template apply<typename Derived::adjacency_list>::type
- >::type::first first_vertex;
-
- // mark first vertex as 'gray'
- typedef typename set_color<first_vertex, gray, ::boost::mpl::map0<> >::type color_map;
-
- // create traversal stack
- typedef ::boost::mpl::vector1<first_vertex> traversal_stack;
-
- // get the adjacency vertices of the first vertex
- typedef typename ::boost::mpl::at<
- //typename build_vertices_map::type,
- typename VmapGenerator::template apply<typename Derived::adjacency_list>::type,
- first_vertex
- >::type adjacency_vertices;
-
- // call the visitor (if it has defined the right functions)
- typedef typename ::boost::mpl::eval_if<
- typename has_discover_vertex<Visitor>::type,
- // call visitor to discover the first vertex
- do_on_discover_vertex<Visitor, first_vertex, visitor_init, traversal_stack, color_map>,
- ::boost::mpl::eval_if<
- typename has_examine_edge<Visitor>::type,
- ::boost::mpl::fold<
- adjacency_vertices,
- visitor_init,
- // call visitor to examine all outgoing edges of the vertex
- do_on_examine_edge<Visitor, first_vertex, ::boost::mpl::placeholders::_2, ::boost::mpl::placeholders::_1, traversal_stack, color_map>
- >,
- ::boost::mpl::void_
- >
- >::type visitor_result;
-
- // create a new iterator to first vertex
- typedef dfs_iterator<
- graph,
- first_vertex,
- color_map,
- traversal_stack,
- EndAtStrategy,
- TracePolicy,
- typename TracePolicy::template apply<first_vertex, typename TracePolicy::container_type>::type,
- Visitor,
- visitor_result
- > type;
- };
-
- // needed to make detection of 'bfs_begin' possible for this graph type
- typedef ::boost::mpl::void_ bfs_begin_supported;
-
- /// \brief Get a BFS iterator to the begin of the graph
- /// \param EndAtStrategy The strategy used to abort the iteration
- /// \param TracePolicy The policy used to trace the iteration
- /// \param Visitor The visitor class used during the iteration
- template<class EndAtStrategy, class TracePolicy, class Visitor>
- struct bfs_begin
- {
- // initialize the visitor
- typedef typename Visitor::on_init::type visitor_init;
-
- // get the first vertex
- typedef typename ::boost::mpl::front<
- //typename build_vertices_map::type
- typename VmapGenerator::template apply<typename Derived::adjacency_list>::type
- >::type::first first_vertex;
-
- // mark first vertex as 'gray'
- typedef typename set_color<first_vertex, gray, ::boost::mpl::map0<> >::type color_map;
-
- // create traversal stack
- typedef ::boost::mpl::vector1<first_vertex> traversal_stack;
-
- // get the adjacency vertices of the first vertex
- typedef typename ::boost::mpl::at<
- //typename build_vertices_map::type,
- typename VmapGenerator::template apply<typename Derived::adjacency_list>::type,
- first_vertex
- >::type adjacency_vertices;
-
- // call the visitor (if it has defined the right functions)
- typedef typename ::boost::mpl::eval_if<
- typename has_discover_vertex<Visitor>::type,
- // call visitor to discover the first vertex
- do_on_discover_vertex<Visitor, first_vertex, visitor_init, traversal_stack, color_map>,
- ::boost::mpl::eval_if<
- typename has_examine_edge<Visitor>::type,
- ::boost::mpl::fold<
- adjacency_vertices,
- visitor_init,
- // call visitor to examine all outgoing edges of the vertex
- do_on_examine_edge<Visitor, first_vertex, ::boost::mpl::placeholders::_2, ::boost::mpl::placeholders::_1, traversal_stack, color_map>
- >,
- ::boost::mpl::void_
- >
- >::type visitor_result;
-
- // create a new iterator to first vertex
- typedef bfs_iterator<
- graph,
- first_vertex,
- color_map,
- traversal_stack,
- EndAtStrategy,
- TracePolicy,
- typename TracePolicy::template apply<first_vertex, typename TracePolicy::container_type>::type,
- Visitor,
- visitor_result
- > type;
- };
-
- template<class VertexIterator>
- struct edge_begin
- {
- // get the adjacency vertices of vertex where the iterator points to
- typedef typename ::boost::mpl::at<
- //typename build_vertices_map::type,
- typename VmapGenerator::template apply<typename Derived::adjacency_list>::type,
- typename VertexIterator::vertex
- >::type adjacency_vertices;
-
- // get first adjacency vertex or the end indicator of no adjacency
- // vertices exists
- typedef typename ::boost::mpl::if_<
- typename ::boost::is_same<adjacency_vertices, ::boost::mpl::void_>::type,
- typename VertexIterator::graph::end,
- typename ::boost::mpl::front<adjacency_vertices>::type
- >::type first_vertex;
-
- // create the edge iterator
- typedef edge_iterator<
- typename VertexIterator::graph,
- typename VertexIterator::vertex,
- first_vertex
- > type;
- };
-
- //! @todo Move this to the derived class to let the user decide which/what should be the end marker.
- struct end
- {
- //typedef ::boost::mpl::void_ type;
- typedef ::boost::mpl::int_<0> type;
- };
-
- template<class VertexIterator>
- struct dfs_next
- {
- // get the next unvisited adjacency vertex of the current vertex
- typedef get_next_vertex_dfs<
- typename VertexIterator::vertex,
- typename VertexIterator::color_map,
- typename VertexIterator::traversal_stack,
- typename VertexIterator::end_at_strategy
- > next;
-
- typedef typename next::type next_vertex;
- typedef typename next::color_map color_map_;
-
- // mark 'next_vertex' as 'gray'
- typedef typename ::boost::mpl::eval_if<
- ::boost::is_same<next_vertex, typename Derived::end::type>,
- color_map_,
- set_color<next_vertex, gray, color_map_>
- >::type color_map;
-
- // add next vertex to traversal stack
- typedef typename ::boost::mpl::eval_if<
- ::boost::is_same<next_vertex, typename Derived::end::type>,
- typename VertexIterator::traversal_stack,
- ::boost::mpl::push_back<typename VertexIterator::traversal_stack, next_vertex>
- >::type traversal_stack;
-
- BOOST_MPL_ASSERT_NOT(( ::boost::mpl::empty<traversal_stack> ));
-
- // get the adjacency vertices of the next vertex
- typedef typename ::boost::mpl::at<
- //typename build_vertices_map::type,
- typename VmapGenerator::template apply<typename Derived::adjacency_list>::type,
- next_vertex
- >::type adjacency_vertices;
-
- // get the iterators visitor class
- typedef typename VertexIterator::visitor_type visitor;
-
- // call the visitor (if it has defined the right functions)
- typedef typename ::boost::mpl::eval_if<
- typename has_discover_vertex<visitor>::type,
- // call visitor to discover the next vertex
- do_on_discover_vertex<visitor, next_vertex, typename VertexIterator::visitor_result, traversal_stack, typename VertexIterator::color_map>,
- ::boost::mpl::eval_if<
- typename has_examine_edge<visitor>::type,
- ::boost::mpl::fold<
- adjacency_vertices,
- typename VertexIterator::visitor_result,
- // call visitor to examine all outgoing edges of the vertex
- do_on_examine_edge<visitor, next_vertex, ::boost::mpl::placeholders::_2, ::boost::mpl::placeholders::_1, traversal_stack, typename VertexIterator::color_map>
- >,
- ::boost::mpl::void_
- >
- >::type visitor_result;
-
- // get the trace policy
- typedef typename VertexIterator::trace_policy trace_policy;
-
- // create a new iterator for the next vertex
- typedef dfs_iterator<
- graph,
- next_vertex,
- color_map,
- traversal_stack,
- typename VertexIterator::end_at_strategy,
- trace_policy,
- typename ::boost::mpl::eval_if<
- ::boost::is_same<next_vertex, typename Derived::end::type>,
- typename VertexIterator::vertex_trace,
- typename trace_policy::template apply<next_vertex, typename VertexIterator::vertex_trace>::type
- >::type,
- visitor,
- typename ::boost::mpl::if_<
- typename has_examine_edge<visitor>::type,
- visitor_result,
- typename ::boost::mpl::if_<
- ::boost::is_same<next_vertex, typename Derived::end::type>,
- typename VertexIterator::visitor_result,
- visitor_result
- >::type
- >::type
- > type;
- };
-
- template<class VertexIterator>
- struct bfs_next
- {
- // get the next unvisited adjacency vertex of the current vertex
- typedef get_next_vertex_bfs<
- typename VertexIterator::color_map,
- typename VertexIterator::traversal_stack,
- typename VertexIterator::end_at_strategy
- > next;
-
- typedef typename next::type next_vertex;
- typedef typename next::color_map color_map_;
- typedef typename next::traversal_stack traversal_stack_;
-
- // mark 'next_vertex' as 'gray'
- typedef typename ::boost::mpl::eval_if<
- ::boost::is_same<next_vertex, typename Derived::end::type>,
- color_map_,
- set_color<next_vertex, gray, color_map_>
- >::type color_map;
-
- // add next vertex to traversal stack
- typedef typename ::boost::mpl::eval_if<
- ::boost::is_same<next_vertex, typename Derived::end::type>,
- traversal_stack_,
- ::boost::mpl::push_back<traversal_stack_, next_vertex>
- >::type traversal_stack;
-
- // get the adjacency vertices of the next vertex
- typedef typename ::boost::mpl::eval_if<
- ::boost::is_same<next_vertex, typename Derived::end::type>,
- ::boost::mpl::vector0<>,
- ::boost::mpl::at<
- //typename build_vertices_map::type,
- typename VmapGenerator::template apply<typename Derived::adjacency_list>::type,
- next_vertex
- >
- >::type adjacency_vertices;
-
- // get the iterators visitor class
- typedef typename VertexIterator::visitor_type visitor;
-
- // call the visitor (if it has defined the right functions)
- typedef typename ::boost::mpl::eval_if<
- typename has_discover_vertex<visitor>::type,
- // call visitor to discover the next vertex
- do_on_discover_vertex<visitor, next_vertex, typename VertexIterator::visitor_result, traversal_stack, typename VertexIterator::color_map>,
- ::boost::mpl::eval_if<
- typename has_examine_edge<visitor>::type,
- ::boost::mpl::fold<
- adjacency_vertices,
- typename VertexIterator::visitor_result,
- // call visitor to examine all outgoing edges of the vertex
- do_on_examine_edge<visitor, next_vertex, ::boost::mpl::placeholders::_2, ::boost::mpl::placeholders::_1, traversal_stack, typename VertexIterator::color_map>
- >,
- ::boost::mpl::void_
- >
- >::type visitor_result;
-
- // get the trace policy
- typedef typename VertexIterator::trace_policy trace_policy;
-
- // create a new iterator for the next vertex
- typedef bfs_iterator<
- graph,
- next_vertex,
- color_map,
- traversal_stack,
- typename VertexIterator::end_at_strategy,
- trace_policy,
- typename ::boost::mpl::eval_if<
- ::boost::is_same<next_vertex, typename Derived::end::type>,
- typename VertexIterator::vertex_trace,
- typename trace_policy::template apply<next_vertex, typename VertexIterator::vertex_trace>::type
- >::type,
- visitor,
- typename ::boost::mpl::if_<
- typename has_examine_edge<visitor>::type,
- visitor_result,
- typename ::boost::mpl::if_<
- ::boost::is_same<next_vertex, typename Derived::end::type>,
- typename VertexIterator::visitor_result,
- visitor_result
- >::type
- >::type
- > type;
- };
-
- template<class EdgeIterator>
- struct edge_next
- {
- // get the adjacency vertices of vertex where the iterator points to
- typedef typename ::boost::mpl::at<
- //typename build_vertices_map::type,
- typename VmapGenerator::template apply<typename Derived::adjacency_list>::type,
- typename EdgeIterator::source_vertex
- >::type adjacency_vertices;
-
- typedef typename ::boost::mpl::plus<typename EdgeIterator::edge_index, ::boost::mpl::int_<1> >::type new_index;
-
- // create a new iterator for the next edge
- typedef edge_iterator<
- typename EdgeIterator::graph,
- typename EdgeIterator::source_vertex,
- typename ::boost::mpl::if_<
- typename ::boost::mpl::greater_equal<new_index, typename ::boost::mpl::size<adjacency_vertices>::type>::type,
- typename EdgeIterator::graph::end::type,
- typename ::boost::mpl::at<adjacency_vertices, new_index>::type
- >::type,
- new_index
- > type;
- };
-
- // needed to make detection of 'dfs_find' possible for this graph type
- typedef ::boost::mpl::void_ dfs_find_supported;
-
- /// \brief Get a DFS iterator to a specific vertex of the graph
- /// \param Vertex The vertex the iteration should be started from
- /// \param EndAtStrategy The strategy used to abort the iteration
- /// \param TracePolicy The policy used to trace the iteration
- /// \param Visitor The visitor class used during the iteration
- template<class Vertex, class EndAtStrategy, class TracePolicy, class Visitor>
- struct dfs_find
- {
- typedef typename build_vertices_set::type vertices;
-
- // initialize the visitor
- typedef typename ::boost::mpl::if_<
- typename ::boost::is_same<typename ::boost::mpl::at<vertices, Vertex>::type, ::boost::mpl::void_>::type,
- ::boost::mpl::void_,
- typename Visitor::on_init::type
- >::type visitor_init;
-
- // get the adjacency vertices of the first vertex
- typedef typename ::boost::mpl::at<
- //typename build_vertices_map::type,
- typename VmapGenerator::template apply<typename Derived::adjacency_list>::type,
- Vertex
- >::type adjacency_vertices;
-
- // mark first vertex as 'gray'
- typedef typename set_color<Vertex, gray, ::boost::mpl::map0<> >::type color_map;
-
- // create traversal stack
- typedef ::boost::mpl::vector1<Vertex> traversal_stack;
-
- typedef typename ::boost::mpl::if_<
- typename ::boost::is_same<typename ::boost::mpl::at<vertices, Vertex>::type, ::boost::mpl::void_>::type,
- ::boost::mpl::void_,
- dfs_iterator<
- graph,
- Vertex,
- color_map,
- traversal_stack,
- EndAtStrategy,
- TracePolicy,
- typename TracePolicy::template apply<Vertex, typename TracePolicy::container_type>::type,
- Visitor,
- typename ::boost::mpl::eval_if<
- typename has_discover_vertex<Visitor>::type,
- do_on_discover_vertex<
- Visitor,
- Vertex,
- visitor_init,
- traversal_stack,
- color_map
- >,
- ::boost::mpl::eval_if<
- typename has_examine_edge<Visitor>::type,
- ::boost::mpl::fold<
- adjacency_vertices,
- visitor_init,
- // call visitor to examine all outgoing edges of the vertex
- do_on_examine_edge<
- Visitor,
- Vertex,
- ::boost::mpl::placeholders::_2,
- ::boost::mpl::placeholders::_1,
- traversal_stack,
- color_map
- >
- >,
- ::boost::mpl::void_
- >
- >::type
- >
- >::type type;
- };
-
- // needed to make detection of 'bfs_find' possible for this graph type
- typedef ::boost::mpl::void_ bfs_find_supported;
-
- /// \brief Get a BFS iterator to a specific vertex of the graph
- /// \param Vertex The vertex the iteration should be started from
- /// \param EndAtStrategy The strategy used to abort the iteration
- /// \param TracePolicy The policy used to trace the iteration
- /// \param Visitor The visitor class used during the iteration
- template<class Vertex, class EndAtStrategy, class TracePolicy, class Visitor>
- struct bfs_find
- {
- typedef typename build_vertices_set::type vertices;
-
- // initialize the visitor
- typedef typename ::boost::mpl::if_<
- typename ::boost::is_same<typename ::boost::mpl::at<vertices, Vertex>::type, ::boost::mpl::void_>::type,
- ::boost::mpl::void_,
- typename Visitor::on_init::type
- >::type visitor_init;
-
- // get the adjacency vertices of the first vertex
- typedef typename ::boost::mpl::at<
- //typename build_vertices_map::type,
- typename VmapGenerator::template apply<typename Derived::adjacency_list>::type,
- Vertex
- >::type adjacency_vertices;
-
- // mark first vertex as 'gray'
- typedef typename set_color<Vertex, gray, ::boost::mpl::map0<> >::type color_map;
-
- // create traversal stack
- typedef ::boost::mpl::vector1<Vertex> traversal_stack;
-
- typedef typename ::boost::mpl::if_<
- typename ::boost::is_same<typename ::boost::mpl::at<vertices, Vertex>::type, ::boost::mpl::void_>::type,
- ::boost::mpl::void_,
- bfs_iterator<
- graph,
- Vertex,
- color_map,
- traversal_stack,
- EndAtStrategy,
- TracePolicy,
- typename TracePolicy::template apply<Vertex, typename TracePolicy::container_type>::type,
- Visitor,
- typename ::boost::mpl::eval_if<
- typename has_discover_vertex<Visitor>::type,
- do_on_discover_vertex<
- Visitor,
- Vertex,
- visitor_init,
- traversal_stack,
- color_map
- >,
- ::boost::mpl::eval_if<
- typename has_examine_edge<Visitor>::type,
- ::boost::mpl::fold<
- adjacency_vertices,
- visitor_init,
- do_on_examine_edge<
- Visitor,
- Vertex,
- ::boost::mpl::placeholders::_2,
- ::boost::mpl::placeholders::_1,
- traversal_stack,
- color_map
- >
- >,
- ::boost::mpl::void_
- >
- >::type
- >
- >::type type;
- };
-
- template<class Vertex>
- struct out_vertices
- {
- typedef typename ::boost::mpl::fold<
- typename Derived::edge_list,
- ::boost::mpl::vector0<>,
- ::boost::mpl::if_<
- ::boost::is_same<
- edge_begin_vertex< ::boost::mpl::placeholders::_2>,
- Vertex
- >,
- ::boost::mpl::push_back<
- ::boost::mpl::placeholders::_1,
- edge_end_vertex< ::boost::mpl::placeholders::_2>
- >,
- ::boost::mpl::placeholders::_1
- >
- >::type type;
- };
-
- template<class Vertex>
- struct out_edges
- {
- typedef typename ::boost::mpl::fold<
- typename Derived::edge_list,
- ::boost::mpl::vector0<>,
- ::boost::mpl::if_<
- ::boost::is_same<
- edge_begin_vertex< ::boost::mpl::placeholders::_2>,
- Vertex
- >,
- ::boost::mpl::push_back<
- ::boost::mpl::placeholders::_1,
- ::boost::mpl::placeholders::_2
- >,
- ::boost::mpl::placeholders::_1
- >
- >::type type;
- };
-
- template<class Vertex>
- struct in_vertices
- {
- typedef typename ::boost::mpl::fold<
- typename Derived::edge_list,
- ::boost::mpl::vector0<>,
- ::boost::mpl::if_<
- ::boost::is_same<
- edge_end_vertex< ::boost::mpl::placeholders::_2>,
- Vertex
- >,
- ::boost::mpl::push_back<
- ::boost::mpl::placeholders::_1,
- edge_begin_vertex< ::boost::mpl::placeholders::_2>
- >,
- ::boost::mpl::placeholders::_1
- >
- >::type type;
- };
-
- template<class Vertex>
- struct in_edges
- {
- typedef typename ::boost::mpl::fold<
- typename Derived::edge_list,
- ::boost::mpl::vector0<>,
- ::boost::mpl::if_<
- ::boost::is_same<
- edge_end_vertex< ::boost::mpl::placeholders::_2>,
- Vertex
- >,
- ::boost::mpl::push_back<
- ::boost::mpl::placeholders::_1,
- ::boost::mpl::placeholders::_2
- >,
- ::boost::mpl::placeholders::_1
- >
- >::type type;
- };
+ // get all vertices of the graph
+ struct get_vertices
+ {
+ // get the start vertices of the adjacency list
+ typedef typename get_start_nodes<typename Derived::adjacency_list>::type start_nodes;
+
+ // add those vertices to an empty set
+ typedef typename ::boost::mpl::fold<
+ start_nodes,
+ ::boost::mpl::set0<>,
+ ::boost::mpl::if_<
+ ::boost::mpl::has_key< ::boost::mpl::placeholders::_1, ::boost::mpl::placeholders::_2>,
+ ::boost::mpl::placeholders::_1,
+ ::boost::mpl::insert< ::boost::mpl::placeholders::_1, ::boost::mpl::placeholders::_2>
+ >
+ >::type start_set;
+
+ // get the adjacency vertices of the start nodes
+ typedef typename get_adjacency_vertices<typename Derived::adjacency_list>::type adjacency_nodes;
+
+ // add those vertices to the former created set
+ typedef typename ::boost::mpl::fold<
+ adjacency_nodes,
+ start_set,
+ aux::vec_to_set< ::boost::mpl::placeholders::_1, ::boost::mpl::placeholders::_2>
+ >::type type;
+ };
+
+ // get the properties of a given vertex as a vector
+ template<class Vertex>
+ struct get_vertex_properties
+ {
+ // transform the vertex property list into a list only containing the
+ // vertices
+ typedef typename get_map_entry_first<
+ typename ::boost::mpl::at<
+ typename create_vertex_map::type,
+ Vertex
+ >::type
+ >::type type;
+ };
+
+ /// \brief Get the properties of a given egde as a vector
+ /// \param VertexFrom Source vertex of the edge
+ /// \param VertexTo Target vertex of the edge
+ template<class VertexFrom, class VertexTo>
+ struct get_edge_properties
+ {
+ // get the edge map
+ typedef typename create_edge_map::type edge_map;
+
+ // get element 'VertexFrom' at edge map
+ typedef typename ::boost::mpl::at<
+ edge_map,
+ VertexFrom
+ >::type type_;
+
+ // get element 'VertexTo' at nested map
+ typedef typename ::boost::mpl::at<
+ type_,
+ VertexTo
+ >::type type__;
+
+ // check if the edge really exists
+ typedef typename ::boost::mpl::if_<
+ ::boost::is_same<type__, ::boost::mpl::void_>,
+ ::boost::mpl::void_,
+ typename type__::second
+ >::type type;
+ };
+
+ /// \brief Get the weight of a given edge
+ /// \param VertexFrom Source vertex of the edge
+ /// \param VertexTo Target vertex of the edge
+ template<class VertexFrom, class VertexTo, class Enable = void>
+ struct get_edge_weight
+ {
+ // get the edge map
+ typedef typename create_edge_map::type edge_map;
+
+ // get element 'VertexFrom' at edge map
+ typedef typename ::boost::mpl::at<
+ edge_map,
+ VertexFrom
+ >::type type_;
+
+ // get element 'VertexTo' at nested map
+ typedef typename ::boost::mpl::at<
+ type_,
+ VertexTo
+ >::type type__;
+
+ // weight is stored at first entry of pair
+ typedef typename type__::first weight;
+
+ typedef typename weight::type type;
+
+ // get integer value of the weight
+ enum { value = weight::type::value };
+ };
+
+ template<class VertexFrom, class VertexTo>
+ struct get_edge_weight<VertexFrom, VertexTo, typename ::boost::disable_if<typename has_edge_list<Derived>::type> >
+ {
+ typedef ::boost::mpl::int_<1> type;
+ };
+
+ template<class StartVertex, class FindVertex>
+ struct find_vertex
+ {
+ typedef typename find_vertex_impl<StartVertex, FindVertex, ::boost::mpl::vector0<> >::type type;
+ };
+
+ // needed to make detection of 'dfs_begin' possible for this graph type
+ typedef ::boost::mpl::void_ dfs_begin_supported;
+
+ /// \brief Get a DFS iterator to the begin of the graph
+ /// \tparam EndAtStrategy The strategy used to abort the iteration
+ /// \tparam Visitor The visitor class used during the iteration
+ template<class EndAtStrategy, class Visitor>
+ struct dfs_begin
+ {
+ // initialize the visitor
+ typedef typename Visitor::on_init::type visitor_init;
+
+ // get the first vertex
+ typedef typename ::boost::mpl::front<
+ typename VmapGenerator::template apply<typename Derived::adjacency_list>::type
+ >::type::first first_vertex;
+
+ // mark first vertex as 'gray'
+ typedef typename set_color<first_vertex, gray, ::boost::mpl::map0<> >::type color_map;
+
+ // create traversal stack
+ typedef ::boost::mpl::vector1<first_vertex> traversal_stack;
+
+ // get the adjacency vertices of the first vertex
+ typedef typename ::boost::mpl::at<
+ typename VmapGenerator::template apply<typename Derived::adjacency_list>::type,
+ first_vertex
+ >::type adjacency_vertices;
+
+ // call the visitor (if it has defined the right functions)
+ typedef typename ::boost::mpl::eval_if<
+ typename has_discover_vertex<Visitor>::type,
+ // call visitor to discover the first vertex
+ do_on_discover_vertex<Visitor, first_vertex, visitor_init, traversal_stack, color_map>,
+ ::boost::mpl::eval_if<
+ typename has_examine_edge<Visitor>::type,
+ ::boost::mpl::fold<
+ adjacency_vertices,
+ visitor_init,
+ // call visitor to examine all outgoing edges of the vertex
+ do_on_examine_edge<Visitor, first_vertex, ::boost::mpl::placeholders::_2, get_edge_weight<first_vertex, ::boost::mpl::placeholders::_2>, ::boost::mpl::placeholders::_1, traversal_stack, color_map>
+ >,
+ ::boost::mpl::void_
+ >
+ >::type visitor_result;
+
+ // create a new iterator to first vertex
+ typedef dfs_iterator<
+ graph,
+ first_vertex,
+ color_map,
+ traversal_stack,
+ EndAtStrategy,
+ Visitor,
+ visitor_result
+ > type;
+ };
+
+ // needed to make detection of 'bfs_begin' possible for this graph type
+ typedef ::boost::mpl::void_ bfs_begin_supported;
+
+ /// \brief Get a BFS iterator to the begin of the graph
+ /// \param EndAtStrategy The strategy used to abort the iteration
+ /// \param Visitor The visitor class used during the iteration
+ template<class EndAtStrategy, class Visitor>
+ struct bfs_begin
+ {
+ // initialize the visitor
+ typedef typename Visitor::on_init::type visitor_init;
+
+ // get the first vertex
+ typedef typename ::boost::mpl::front<
+ typename VmapGenerator::template apply<typename Derived::adjacency_list>::type
+ >::type::first first_vertex;
+
+ // mark first vertex as 'gray'
+ typedef typename set_color<first_vertex, gray, ::boost::mpl::map0<> >::type color_map;
+
+ // create traversal stack
+ typedef ::boost::mpl::vector1<first_vertex> traversal_stack;
+
+ // get the adjacency vertices of the first vertex
+ typedef typename ::boost::mpl::at<
+ typename VmapGenerator::template apply<typename Derived::adjacency_list>::type,
+ first_vertex
+ >::type adjacency_vertices;
+
+ // call the visitor (if it has defined the right functions)
+ typedef typename ::boost::mpl::eval_if<
+ typename has_discover_vertex<Visitor>::type,
+ // call visitor to discover the first vertex
+ do_on_discover_vertex<Visitor, first_vertex, visitor_init, traversal_stack, color_map>,
+ ::boost::mpl::eval_if<
+ typename has_examine_edge<Visitor>::type,
+ ::boost::mpl::fold<
+ adjacency_vertices,
+ visitor_init,
+ // call visitor to examine all outgoing edges of the vertex
+ do_on_examine_edge<Visitor, first_vertex, ::boost::mpl::placeholders::_2, get_edge_weight<first_vertex, ::boost::mpl::placeholders::_2>, ::boost::mpl::placeholders::_1, traversal_stack, color_map>
+ >,
+ ::boost::mpl::void_
+ >
+ >::type visitor_result;
+
+ // create a new iterator to first vertex
+ typedef bfs_iterator<
+ graph,
+ first_vertex,
+ color_map,
+ traversal_stack,
+ EndAtStrategy,
+ Visitor,
+ visitor_result
+ > type;
+ };
+
+ template<class VertexIterator>
+ struct edge_begin
+ {
+ // get the adjacency vertices of vertex where the iterator points to
+ typedef typename ::boost::mpl::at<
+ typename VmapGenerator::template apply<typename Derived::adjacency_list>::type,
+ typename VertexIterator::vertex
+ >::type adjacency_vertices;
+
+ // get first adjacency vertex or the end indicator of no adjacency
+ // vertices exists
+ typedef typename ::boost::mpl::if_<
+ typename ::boost::is_same<adjacency_vertices, ::boost::mpl::void_>::type,
+ typename VertexIterator::graph::end,
+ typename ::boost::mpl::front<adjacency_vertices>::type
+ >::type first_vertex;
+
+ // create the edge iterator
+ typedef edge_iterator<
+ typename VertexIterator::graph,
+ typename VertexIterator::vertex,
+ first_vertex
+ > type;
+ };
+
+ //! @todo Move this to the derived class to let the user decide which/what should be the end marker.
+ struct end
+ {
+ typedef ::boost::mpl::int_<0> type;
+ };
+
+ template<class VertexIterator>
+ struct dfs_next
+ {
+ // get the next unvisited adjacency vertex of the current vertex
+ typedef get_next_vertex_dfs<
+ typename VertexIterator::vertex,
+ typename VertexIterator::color_map,
+ typename VertexIterator::traversal_stack,
+ typename VertexIterator::end_at_strategy
+ > next;
+
+ typedef typename next::type next_vertex;
+ typedef typename next::color_map color_map_;
+
+ // mark 'next_vertex' as 'gray'
+ typedef typename ::boost::mpl::eval_if<
+ ::boost::is_same<next_vertex, typename Derived::end::type>,
+ color_map_,
+ set_color<next_vertex, gray, color_map_>
+ >::type color_map;
+
+ // add next vertex to traversal stack
+ typedef typename ::boost::mpl::eval_if<
+ ::boost::is_same<next_vertex, typename Derived::end::type>,
+ typename VertexIterator::traversal_stack,
+ ::boost::mpl::push_back<typename VertexIterator::traversal_stack, next_vertex>
+ >::type traversal_stack;
+
+ BOOST_MPL_ASSERT_NOT(( ::boost::mpl::empty<traversal_stack> ));
+
+ // get the adjacency vertices of the next vertex
+ typedef typename ::boost::mpl::at<
+ typename VmapGenerator::template apply<typename Derived::adjacency_list>::type,
+ next_vertex
+ >::type adjacency_vertices;
+
+ // get the iterators visitor class
+ typedef typename VertexIterator::visitor_type visitor;
+
+ // call the visitor (if it has defined the right functions)
+ typedef typename ::boost::mpl::eval_if<
+ typename has_discover_vertex<visitor>::type,
+ // call visitor to discover the next vertex
+ do_on_discover_vertex<visitor, next_vertex, typename VertexIterator::visitor_result, traversal_stack, typename VertexIterator::color_map>,
+ ::boost::mpl::eval_if<
+ typename has_examine_edge<visitor>::type,
+ ::boost::mpl::fold<
+ adjacency_vertices,
+ typename VertexIterator::visitor_result,
+ // call visitor to examine all outgoing edges of the vertex
+ do_on_examine_edge<visitor, next_vertex, ::boost::mpl::placeholders::_2, get_edge_weight<next_vertex, ::boost::mpl::placeholders::_2>, ::boost::mpl::placeholders::_1, traversal_stack, typename VertexIterator::color_map>
+ >,
+ ::boost::mpl::void_
+ >
+ >::type visitor_result;
+
+ // create a new iterator for the next vertex
+ typedef dfs_iterator<
+ graph,
+ next_vertex,
+ color_map,
+ traversal_stack,
+ typename VertexIterator::end_at_strategy,
+ visitor,
+ typename ::boost::mpl::if_<
+ typename has_examine_edge<visitor>::type,
+ visitor_result,
+ typename ::boost::mpl::if_<
+ ::boost::is_same<next_vertex, typename Derived::end::type>,
+ typename VertexIterator::visitor_result,
+ visitor_result
+ >::type
+ >::type
+ > type;
+ };
+
+ template<class VertexIterator>
+ struct bfs_next
+ {
+ // get the next unvisited adjacency vertex of the current vertex
+ typedef get_next_vertex_bfs<
+ typename VertexIterator::color_map,
+ typename VertexIterator::traversal_stack,
+ typename VertexIterator::end_at_strategy
+ > next;
+
+ typedef typename next::type next_vertex;
+ typedef typename next::color_map color_map_;
+ typedef typename next::traversal_stack traversal_stack_;
+
+ // mark 'next_vertex' as 'gray'
+ typedef typename ::boost::mpl::eval_if<
+ ::boost::is_same<next_vertex, typename Derived::end::type>,
+ color_map_,
+ set_color<next_vertex, gray, color_map_>
+ >::type color_map;
+
+ // add next vertex to traversal stack
+ typedef typename ::boost::mpl::eval_if<
+ ::boost::is_same<next_vertex, typename Derived::end::type>,
+ traversal_stack_,
+ ::boost::mpl::push_back<traversal_stack_, next_vertex>
+ >::type traversal_stack;
+
+ // get the adjacency vertices of the next vertex
+ typedef typename ::boost::mpl::eval_if<
+ ::boost::is_same<next_vertex, typename Derived::end::type>,
+ ::boost::mpl::vector0<>,
+ ::boost::mpl::at<
+ typename VmapGenerator::template apply<typename Derived::adjacency_list>::type,
+ next_vertex
+ >
+ >::type adjacency_vertices;
+
+ // get the iterators visitor class
+ typedef typename VertexIterator::visitor_type visitor;
+
+ // call the visitor (if it has defined the right functions)
+ typedef typename ::boost::mpl::eval_if<
+ typename has_discover_vertex<visitor>::type,
+ // call visitor to discover the next vertex
+ do_on_discover_vertex<visitor, next_vertex, typename VertexIterator::visitor_result, traversal_stack, typename VertexIterator::color_map>,
+ ::boost::mpl::eval_if<
+ typename has_examine_edge<visitor>::type,
+ ::boost::mpl::fold<
+ adjacency_vertices,
+ typename VertexIterator::visitor_result,
+ // call visitor to examine all outgoing edges of the vertex
+ do_on_examine_edge<visitor, next_vertex, ::boost::mpl::placeholders::_2, get_edge_weight<next_vertex, ::boost::mpl::placeholders::_2>, ::boost::mpl::placeholders::_1, traversal_stack, typename VertexIterator::color_map>
+ >,
+ ::boost::mpl::void_
+ >
+ >::type visitor_result;
+
+ // create a new iterator for the next vertex
+ typedef bfs_iterator<
+ graph,
+ next_vertex,
+ color_map,
+ traversal_stack,
+ typename VertexIterator::end_at_strategy,
+ visitor,
+ typename ::boost::mpl::if_<
+ typename has_examine_edge<visitor>::type,
+ visitor_result,
+ typename ::boost::mpl::if_<
+ ::boost::is_same<next_vertex, typename Derived::end::type>,
+ typename VertexIterator::visitor_result,
+ visitor_result
+ >::type
+ >::type
+ > type;
+ };
+
+ template<class EdgeIterator>
+ struct edge_next
+ {
+ // get the adjacency vertices of vertex where the iterator points to
+ typedef typename ::boost::mpl::at<
+ //typename build_vertices_map::type,
+ typename VmapGenerator::template apply<typename Derived::adjacency_list>::type,
+ typename EdgeIterator::source_vertex
+ >::type adjacency_vertices;
+
+ typedef typename ::boost::mpl::plus<typename EdgeIterator::edge_index, ::boost::mpl::int_<1> >::type new_index;
+
+ // create a new iterator for the next edge
+ typedef edge_iterator<
+ typename EdgeIterator::graph,
+ typename EdgeIterator::source_vertex,
+ typename ::boost::mpl::if_<
+ typename ::boost::mpl::greater_equal<new_index, typename ::boost::mpl::size<adjacency_vertices>::type>::type,
+ typename EdgeIterator::graph::end::type,
+ typename ::boost::mpl::at<adjacency_vertices, new_index>::type
+ >::type,
+ new_index
+ > type;
+ };
+
+ // needed to make detection of 'dfs_find' possible for this graph type
+ typedef ::boost::mpl::void_ dfs_find_supported;
+
+ /// \brief Get a DFS iterator to a specific vertex of the graph
+ /// \tparam Vertex The vertex the iteration should be started from
+ /// \tparam EndAtStrategy The strategy used to abort the iteration
+ /// \tparam Visitor The visitor class used during the iteration
+ template<class Vertex, class EndAtStrategy, class Visitor>
+ struct dfs_find
+ {
+ typedef typename build_vertices_set::type vertices;
+
+ // initialize the visitor
+ typedef typename ::boost::mpl::if_<
+ typename ::boost::is_same<typename ::boost::mpl::at<vertices, Vertex>::type, ::boost::mpl::void_>::type,
+ ::boost::mpl::void_,
+ typename Visitor::on_init::type
+ >::type visitor_init;
+
+ // get the adjacency vertices of the first vertex
+ typedef typename ::boost::mpl::at<
+ typename VmapGenerator::template apply<typename Derived::adjacency_list>::type,
+ Vertex
+ >::type adjacency_vertices;
+
+ // mark first vertex as 'gray'
+ typedef typename set_color<Vertex, gray, ::boost::mpl::map0<> >::type color_map;
+
+ // create traversal stack
+ typedef ::boost::mpl::vector1<Vertex> traversal_stack;
+
+ typedef typename ::boost::mpl::if_<
+ typename ::boost::is_same<typename ::boost::mpl::at<vertices, Vertex>::type, ::boost::mpl::void_>::type,
+ ::boost::mpl::void_,
+ dfs_iterator<
+ graph,
+ Vertex,
+ color_map,
+ traversal_stack,
+ EndAtStrategy,
+ Visitor,
+ typename ::boost::mpl::eval_if<
+ typename has_discover_vertex<Visitor>::type,
+ do_on_discover_vertex<
+ Visitor,
+ Vertex,
+ visitor_init,
+ traversal_stack,
+ color_map
+ >,
+ ::boost::mpl::eval_if<
+ typename has_examine_edge<Visitor>::type,
+ ::boost::mpl::fold<
+ adjacency_vertices,
+ visitor_init,
+ // call visitor to examine all outgoing edges of the vertex
+ do_on_examine_edge<
+ Visitor,
+ Vertex,
+ ::boost::mpl::placeholders::_2,
+ get_edge_weight<Vertex, ::boost::mpl::placeholders::_2>,
+ ::boost::mpl::placeholders::_1,
+ traversal_stack,
+ color_map
+ >
+ >,
+ ::boost::mpl::void_
+ >
+ >::type
+ >
+ >::type type;
+ };
+
+ // needed to make detection of 'bfs_find' possible for this graph type
+ typedef ::boost::mpl::void_ bfs_find_supported;
+
+ /// \brief Get a BFS iterator to a specific vertex of the graph
+ /// \param Vertex The vertex the iteration should be started from
+ /// \param EndAtStrategy The strategy used to abort the iteration
+ /// \param Visitor The visitor class used during the iteration
+ template<class Vertex, class EndAtStrategy, class Visitor>
+ struct bfs_find
+ {
+ typedef typename build_vertices_set::type vertices;
+
+ // initialize the visitor
+ typedef typename ::boost::mpl::if_<
+ typename ::boost::is_same<typename ::boost::mpl::at<vertices, Vertex>::type, ::boost::mpl::void_>::type,
+ ::boost::mpl::void_,
+ typename Visitor::on_init::type
+ >::type visitor_init;
+
+ // get the adjacency vertices of the first vertex
+ typedef typename ::boost::mpl::at<
+ typename VmapGenerator::template apply<typename Derived::adjacency_list>::type,
+ Vertex
+ >::type adjacency_vertices;
+
+ // mark first vertex as 'gray'
+ typedef typename set_color<Vertex, gray, ::boost::mpl::map0<> >::type color_map;
+
+ // create traversal stack
+ typedef ::boost::mpl::vector1<Vertex> traversal_stack;
+
+ typedef typename ::boost::mpl::if_<
+ typename ::boost::is_same<typename ::boost::mpl::at<vertices, Vertex>::type, ::boost::mpl::void_>::type,
+ ::boost::mpl::void_,
+ bfs_iterator<
+ graph,
+ Vertex,
+ color_map,
+ traversal_stack,
+ EndAtStrategy,
+ Visitor,
+ typename ::boost::mpl::eval_if<
+ typename has_discover_vertex<Visitor>::type,
+ do_on_discover_vertex<
+ Visitor,
+ Vertex,
+ visitor_init,
+ traversal_stack,
+ color_map
+ >,
+ ::boost::mpl::eval_if<
+ typename has_examine_edge<Visitor>::type,
+ ::boost::mpl::fold<
+ adjacency_vertices,
+ visitor_init,
+ do_on_examine_edge<
+ Visitor,
+ Vertex,
+ ::boost::mpl::placeholders::_2,
+ get_edge_weight<Vertex, ::boost::mpl::placeholders::_2>,
+ ::boost::mpl::placeholders::_1,
+ traversal_stack,
+ color_map
+ >
+ >,
+ ::boost::mpl::void_
+ >
+ >::type
+ >
+ >::type type;
+ };
+
+ template<class Vertex>
+ struct out_vertices
+ {
+ typedef typename ::boost::mpl::fold<
+ typename Derived::edge_list,
+ ::boost::mpl::vector0<>,
+ ::boost::mpl::if_<
+ ::boost::is_same<
+ edge_begin_vertex< ::boost::mpl::placeholders::_2>,
+ Vertex
+ >,
+ ::boost::mpl::push_back<
+ ::boost::mpl::placeholders::_1,
+ edge_end_vertex< ::boost::mpl::placeholders::_2>
+ >,
+ ::boost::mpl::placeholders::_1
+ >
+ >::type type;
+ };
+
+ template<class Vertex>
+ struct out_edges
+ {
+ typedef typename ::boost::mpl::fold<
+ typename Derived::edge_list,
+ ::boost::mpl::vector0<>,
+ ::boost::mpl::if_<
+ ::boost::is_same<
+ edge_begin_vertex< ::boost::mpl::placeholders::_2>,
+ Vertex
+ >,
+ ::boost::mpl::push_back<
+ ::boost::mpl::placeholders::_1,
+ ::boost::mpl::placeholders::_2
+ >,
+ ::boost::mpl::placeholders::_1
+ >
+ >::type type;
+ };
+
+ template<class Vertex>
+ struct in_vertices
+ {
+ typedef typename ::boost::mpl::fold<
+ typename Derived::edge_list,
+ ::boost::mpl::vector0<>,
+ ::boost::mpl::if_<
+ ::boost::is_same<
+ edge_end_vertex< ::boost::mpl::placeholders::_2>,
+ Vertex
+ >,
+ ::boost::mpl::push_back<
+ ::boost::mpl::placeholders::_1,
+ edge_begin_vertex< ::boost::mpl::placeholders::_2>
+ >,
+ ::boost::mpl::placeholders::_1
+ >
+ >::type type;
+ };
+
+ template<class Vertex>
+ struct in_edges
+ {
+ typedef typename ::boost::mpl::fold<
+ typename Derived::edge_list,
+ ::boost::mpl::vector0<>,
+ ::boost::mpl::if_<
+ ::boost::is_same<
+ edge_end_vertex< ::boost::mpl::placeholders::_2>,
+ Vertex
+ >,
+ ::boost::mpl::push_back<
+ ::boost::mpl::placeholders::_1,
+ ::boost::mpl::placeholders::_2
+ >,
+ ::boost::mpl::placeholders::_1
+ >
+ >::type type;
+ };
 };
 
 } // namespace mgl

Modified: sandbox/mgl/boost/mgl/graph_policies.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/graph_policies.hpp (original)
+++ sandbox/mgl/boost/mgl/graph_policies.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -7,15 +7,15 @@
 #ifndef BOOST_MGL_GRAPH_POLICIES_HPP
 #define BOOST_MGL_GRAPH_POLICIES_HPP
 
+#include <boost/mpl/contains.hpp>
 #include <boost/mpl/fold.hpp>
+#include <boost/mpl/if.hpp>
+#include <boost/mpl/insert.hpp>
 #include <boost/mpl/map.hpp>
+#include <boost/mpl/pair.hpp>
+#include <boost/mpl/push_back.hpp>
 #include <boost/mpl/set.hpp>
-#include <boost/mpl/insert.hpp>
 #include <boost/mpl/vector.hpp>
-#include <boost/mpl/push_back.hpp>
-#include <boost/mpl/if.hpp>
-#include <boost/mpl/contains.hpp>
-#include <boost/mpl/pair.hpp>
 
 #include <boost/mgl/aux_/utility.hpp>
 
@@ -27,144 +27,144 @@
 
 struct VmapDirectedGraph
 {
- template<class AdjacencyList>
- struct apply
- {
- typedef typename ::boost::mpl::fold<
- AdjacencyList,
- ::boost::mpl::map0<>,
- ::boost::mpl::insert<
- ::boost::mpl::placeholders::_1,
- ::boost::mpl::pair<
- aux::row_start_vertex< ::boost::mpl::placeholders::_2>,
- aux::row_adjacency_vertices< ::boost::mpl::placeholders::_2>
- >
- >
- >::type type;
- };
+ template<class AdjacencyList>
+ struct apply
+ {
+ typedef typename ::boost::mpl::fold<
+ AdjacencyList,
+ ::boost::mpl::map0<>,
+ ::boost::mpl::insert<
+ ::boost::mpl::placeholders::_1,
+ ::boost::mpl::pair<
+ aux::row_start_vertex< ::boost::mpl::placeholders::_2>,
+ aux::row_adjacency_vertices< ::boost::mpl::placeholders::_2>
+ >
+ >
+ >::type type;
+ };
 };
 
 struct VmapUndirectedGraph
 {
 private:
- template<class AdjacencyList>
- struct build_vertex_set
- {
- // Add the start vertices to a set
- typedef typename ::boost::mpl::fold<
- AdjacencyList,
- ::boost::mpl::set0<>,
- ::boost::mpl::insert<
- ::boost::mpl::placeholders::_1,
- aux::row_start_vertex< ::boost::mpl::placeholders::_2>
- >
- >::type s;
-
- // Add adjacency vertices to the former created set
- typedef typename ::boost::mpl::fold<
- AdjacencyList,
- s,
- ::boost::mpl::insert<
- ::boost::mpl::placeholders::_1,
- aux::row_adjacency_vertices< ::boost::mpl::placeholders::_2>
- >
- >::type type;
- };
-
- template<class AdjacencyList, class Vertex>
- struct find_ingoing_vertices
- {
- typedef typename ::boost::mpl::fold<
- AdjacencyList,
- ::boost::mpl::vector0<>,
- ::boost::mpl::if_<
- ::boost::mpl::contains<
- aux::row_adjacency_vertices< ::boost::mpl::placeholders::_2>,
- Vertex
- >,
- ::boost::mpl::push_back<
- ::boost::mpl::placeholders::_1,
- aux::row_start_vertex< ::boost::mpl::placeholders::_2>
- >,
- ::boost::mpl::placeholders::_1
- >
- >::type type;
- };
-
- template<class V1, class V2>
- struct join_vectors
- {
- //! @todo: Optimize this!
- typedef typename ::boost::mpl::fold<
- V2,
- V1,
- ::boost::mpl::if_<
- ::boost::mpl::contains<
- V1,
- ::boost::mpl::placeholders::_2
- >,
- ::boost::mpl::placeholders::_1,
- ::boost::mpl::push_back<
- ::boost::mpl::placeholders::_1,
- ::boost::mpl::placeholders::_2
- >
- >
- >::type type;
- };
+ template<class AdjacencyList>
+ struct build_vertex_set
+ {
+ // Add the start vertices to a set
+ typedef typename ::boost::mpl::fold<
+ AdjacencyList,
+ ::boost::mpl::set0<>,
+ ::boost::mpl::insert<
+ ::boost::mpl::placeholders::_1,
+ aux::row_start_vertex< ::boost::mpl::placeholders::_2>
+ >
+ >::type s;
+
+ // Add adjacency vertices to the former created set
+ typedef typename ::boost::mpl::fold<
+ AdjacencyList,
+ s,
+ ::boost::mpl::insert<
+ ::boost::mpl::placeholders::_1,
+ aux::row_adjacency_vertices< ::boost::mpl::placeholders::_2>
+ >
+ >::type type;
+ };
+
+ template<class AdjacencyList, class Vertex>
+ struct find_ingoing_vertices
+ {
+ typedef typename ::boost::mpl::fold<
+ AdjacencyList,
+ ::boost::mpl::vector0<>,
+ ::boost::mpl::if_<
+ ::boost::mpl::contains<
+ aux::row_adjacency_vertices< ::boost::mpl::placeholders::_2>,
+ Vertex
+ >,
+ ::boost::mpl::push_back<
+ ::boost::mpl::placeholders::_1,
+ aux::row_start_vertex< ::boost::mpl::placeholders::_2>
+ >,
+ ::boost::mpl::placeholders::_1
+ >
+ >::type type;
+ };
+
+ template<class V1, class V2>
+ struct join_vectors
+ {
+ //! @todo: Optimize this!
+ typedef typename ::boost::mpl::fold<
+ V2,
+ V1,
+ ::boost::mpl::if_<
+ ::boost::mpl::contains<
+ V1,
+ ::boost::mpl::placeholders::_2
+ >,
+ ::boost::mpl::placeholders::_1,
+ ::boost::mpl::push_back<
+ ::boost::mpl::placeholders::_1,
+ ::boost::mpl::placeholders::_2
+ >
+ >
+ >::type type;
+ };
 
 public:
- template<class AdjacencyList>
- struct apply
- {
- // determine the outgoing vertices
- typedef typename ::boost::mpl::fold<
- AdjacencyList,
- ::boost::mpl::map0<>,
- ::boost::mpl::insert<
- ::boost::mpl::placeholders::_1,
- ::boost::mpl::pair<
- aux::row_start_vertex< ::boost::mpl::placeholders::_2>,
- aux::row_adjacency_vertices< ::boost::mpl::placeholders::_2>
- >
- >
- >::type m1;
-
- // determine the ingoing vertices
- typedef typename ::boost::mpl::fold<
- typename build_vertex_set<AdjacencyList>::type,
- ::boost::mpl::map0<>,
- ::boost::mpl::insert<
- ::boost::mpl::placeholders::_1,
- ::boost::mpl::pair<
- ::boost::mpl::placeholders::_2,
- find_ingoing_vertices<
- AdjacencyList,
- ::boost::mpl::placeholders::_2
- >
- >
- >
- >::type m2;
-
- // merge both maps
- //! @todo: Try to optimize this!
- typedef typename ::boost::mpl::fold<
- m1,
- ::boost::mpl::map0<>,
- ::boost::mpl::insert<
- ::boost::mpl::placeholders::_1,
- ::boost::mpl::pair<
- ::boost::mpl::first< ::boost::mpl::placeholders::_2 >,
- join_vectors<
- ::boost::mpl::second< ::boost::mpl::placeholders::_2 >,
- ::boost::mpl::at<
- m2,
- ::boost::mpl::first< ::boost::mpl::placeholders::_2 >
- >
- >
- >
- >
- >::type type;
- };
+ template<class AdjacencyList>
+ struct apply
+ {
+ // determine the outgoing vertices
+ typedef typename ::boost::mpl::fold<
+ AdjacencyList,
+ ::boost::mpl::map0<>,
+ ::boost::mpl::insert<
+ ::boost::mpl::placeholders::_1,
+ ::boost::mpl::pair<
+ aux::row_start_vertex< ::boost::mpl::placeholders::_2>,
+ aux::row_adjacency_vertices< ::boost::mpl::placeholders::_2>
+ >
+ >
+ >::type m1;
+
+ // determine the ingoing vertices
+ typedef typename ::boost::mpl::fold<
+ typename build_vertex_set<AdjacencyList>::type,
+ ::boost::mpl::map0<>,
+ ::boost::mpl::insert<
+ ::boost::mpl::placeholders::_1,
+ ::boost::mpl::pair<
+ ::boost::mpl::placeholders::_2,
+ find_ingoing_vertices<
+ AdjacencyList,
+ ::boost::mpl::placeholders::_2
+ >
+ >
+ >
+ >::type m2;
+
+ // merge both maps
+ //! @todo: Try to optimize this!
+ typedef typename ::boost::mpl::fold<
+ m1,
+ ::boost::mpl::map0<>,
+ ::boost::mpl::insert<
+ ::boost::mpl::placeholders::_1,
+ ::boost::mpl::pair<
+ ::boost::mpl::first< ::boost::mpl::placeholders::_2 >,
+ join_vectors<
+ ::boost::mpl::second< ::boost::mpl::placeholders::_2 >,
+ ::boost::mpl::at<
+ m2,
+ ::boost::mpl::first< ::boost::mpl::placeholders::_2 >
+ >
+ >
+ >
+ >
+ >::type type;
+ };
 };
 
 } // namespace mgl

Modified: sandbox/mgl/boost/mgl/is_graph.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/is_graph.hpp (original)
+++ sandbox/mgl/boost/mgl/is_graph.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -23,7 +23,7 @@
 
 template<typename T>
 struct is_graph_impl :
- is_base_of<directed_graph<T>, T>::type
+ is_base_of<directed_graph<T>, T>::type
 {
 };
 

Modified: sandbox/mgl/boost/mgl/iterator.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/iterator.hpp (original)
+++ sandbox/mgl/boost/mgl/iterator.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -8,17 +8,17 @@
 #define BOOST_MGL_ITERATOR_HPP
 
 #include <boost/mpl/at.hpp>
+#include <boost/mpl/has_key.hpp>
+#include <boost/mpl/insert.hpp>
 #include <boost/mpl/int.hpp>
 #include <boost/mpl/set.hpp>
-#include <boost/mpl/insert.hpp>
-#include <boost/mpl/has_key.hpp>
 #include <boost/type_traits/is_same.hpp>
 
+#include <boost/mgl/colors.hpp>
 #include <boost/mgl/next_prior.hpp>
-#include <boost/mgl/iterator_tags.hpp>
 #include <boost/mgl/iterator_policies.hpp>
+#include <boost/mgl/iterator_tags.hpp>
 #include <boost/mgl/visitors.hpp>
-#include <boost/mgl/colors.hpp>
 
 namespace boost
 {
@@ -26,57 +26,67 @@
 namespace mgl
 {
 
-template<class Graph, class Vertex, class ColorMap, class TraversalStack, class EndAtStrategy = ::boost::mgl::EndAtEndOfGraph, class TracePolicy = ::boost::mgl::NoTrace, class Trace = ::boost::mpl::void_, class Visitor = ::boost::mgl::null_visitor, class VisitorResult = ::boost::mpl::void_>
+template<
+ class Graph,
+ class Vertex,
+ class ColorMap,
+ class TraversalStack,
+ class EndAtStrategy = ::boost::mgl::EndAtEndOfGraph,
+ class Visitor = ::boost::mgl::null_visitor,
+ class VisitorResult = ::boost::mpl::void_
+>
 struct dfs_iterator
 {
- typedef Graph graph;
- typedef Vertex vertex;
-
- typedef ColorMap color_map;
+ typedef Graph graph;
+ typedef Vertex vertex;
 
- typedef TraversalStack traversal_stack;
+ typedef ColorMap color_map;
 
- typedef ::boost::mgl::dfs_iterator_tag category;
+ typedef TraversalStack traversal_stack;
 
- typedef EndAtStrategy end_at_strategy;
+ typedef ::boost::mgl::dfs_iterator_tag category;
 
- typedef TracePolicy trace_policy;
- typedef Trace vertex_trace;
+ typedef EndAtStrategy end_at_strategy;
 
- typedef Visitor visitor_type;
- typedef VisitorResult visitor_result;
+ typedef Visitor visitor_type;
+ typedef VisitorResult visitor_result;
 };
 
-template<class Graph, class Vertex, class ColorMap, class TraversalStack, class EndAtStrategy = ::boost::mgl::EndAtEndOfGraph, class TracePolicy = ::boost::mgl::NoTrace, class Trace = ::boost::mpl::void_, class Visitor = ::boost::mgl::null_visitor, class VisitorResult = ::boost::mpl::void_>
+template<
+ class Graph,
+ class Vertex,
+ class ColorMap,
+ class TraversalStack,
+ class EndAtStrategy = ::boost::mgl::EndAtEndOfGraph,
+ class Visitor = ::boost::mgl::null_visitor,
+ class VisitorResult = ::boost::mpl::void_
+>
 struct bfs_iterator
 {
- typedef Graph graph;
- typedef Vertex vertex;
-
- typedef ColorMap color_map;
+ typedef Graph graph;
+ typedef Vertex vertex;
 
- typedef TraversalStack traversal_stack;
+ typedef ColorMap color_map;
 
- typedef ::boost::mgl::bfs_iterator_tag category;
+ typedef TraversalStack traversal_stack;
 
- typedef EndAtStrategy end_at_strategy;
+ typedef ::boost::mgl::bfs_iterator_tag category;
 
- typedef TracePolicy trace_policy;
- typedef Trace vertex_trace;
+ typedef EndAtStrategy end_at_strategy;
 
- typedef Visitor visitor_type;
- typedef VisitorResult visitor_result;
+ typedef Visitor visitor_type;
+ typedef VisitorResult visitor_result;
 };
 
 template<class Graph, class Vertex, class TargetVertex, class EdgeIndex = ::boost::mpl::int_<0> >
 struct edge_iterator
 {
- typedef Graph graph;
+ typedef Graph graph;
 
- typedef Vertex source_vertex;
- typedef TargetVertex target_vertex;
+ typedef Vertex source_vertex;
+ typedef TargetVertex target_vertex;
 
- typedef EdgeIndex edge_index;
+ typedef EdgeIndex edge_index;
 };
 
 /// \brief Dereference the iterator
@@ -84,25 +94,61 @@
 template<class Iterator>
 struct deref
 {
- typedef typename Iterator::type type;
-};
-
-template<class Graph, class Vertex, class VisitedSet, class TraversalStack, class EndAtStrategy, class TracePolicy, class Trace, class Visitor, class VisitorResult>
-struct deref<dfs_iterator<Graph, Vertex, VisitedSet, TraversalStack, EndAtStrategy, TracePolicy, Trace, Visitor, VisitorResult> >
-{
- typedef Vertex type;
+ typedef typename Iterator::type type;
 };
 
-template<class Graph, class Vertex, class VisitedSet, class TraversalStack, class EndAtStrategy, class TracePolicy, class Trace, class Visitor, class VisitorResult>
-struct deref<bfs_iterator<Graph, Vertex, VisitedSet, TraversalStack, EndAtStrategy, TracePolicy, Trace, Visitor, VisitorResult> >
+template<
+ class Graph,
+ class Vertex,
+ class VisitedSet,
+ class TraversalStack,
+ class EndAtStrategy,
+ class Visitor,
+ class VisitorResult
+>
+struct deref<
+ dfs_iterator<
+ Graph,
+ Vertex,
+ VisitedSet,
+ TraversalStack,
+ EndAtStrategy,
+ Visitor,
+ VisitorResult
+ >
+>
+{
+ typedef Vertex type;
+};
+
+template<
+ class Graph,
+ class Vertex,
+ class VisitedSet,
+ class TraversalStack,
+ class EndAtStrategy,
+ class Visitor,
+ class VisitorResult
+>
+struct deref<
+ bfs_iterator<
+ Graph,
+ Vertex,
+ VisitedSet,
+ TraversalStack,
+ EndAtStrategy,
+ Visitor,
+ VisitorResult
+ >
+>
 {
- typedef Vertex type;
+ typedef Vertex type;
 };
 
 template<class Graph, class Vertex, class TargetVertex, class EdgeIndex>
 struct deref<edge_iterator<Graph, Vertex, TargetVertex, EdgeIndex> >
 {
- typedef TargetVertex type;
+ typedef TargetVertex type;
 };
 
 } // namespace mgl

Modified: sandbox/mgl/boost/mgl/iterator_policies.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/iterator_policies.hpp (original)
+++ sandbox/mgl/boost/mgl/iterator_policies.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -8,6 +8,7 @@
 #define BOOST_MGL_ITERATOR_POLICIES_HPP
 
 #include <boost/mpl/vector.hpp>
+#include <boost/mpl/void.hpp>
 
 #include <boost/typeof/typeof.hpp>
 
@@ -24,24 +25,24 @@
 // trace policies
 struct NoTrace
 {
- typedef ::boost::mpl::void_ container_type;
+ typedef ::boost::mpl::void_ container_type;
 
- template<typename Vertex, typename Container>
+ template<typename Vertex, typename Container>
     struct apply
     {
- typedef ::boost::mpl::void_ type;
+ typedef ::boost::mpl::void_ type;
     };
 };
 
 template<typename TraceVector>
 struct RecordTrace
 {
- typedef TraceVector container_type;
+ typedef TraceVector container_type;
 
- template<typename Vertex, typename Container>
+ template<typename Vertex, typename Container>
     struct apply
     {
- typedef typename ::boost::mpl::push_back<Container, Vertex>::type type;
+ typedef typename ::boost::mpl::push_back<Container, Vertex>::type type;
     };
 };
 

Modified: sandbox/mgl/boost/mgl/iterator_tags.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/iterator_tags.hpp (original)
+++ sandbox/mgl/boost/mgl/iterator_tags.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -7,8 +7,6 @@
 #ifndef BOOST_MGL_ITERATOR_TAGS_HPP
 #define BOOST_MGL_ITERATOR_TAGS_HPP
 
-#include <boost/mpl/int.hpp>
-
 namespace boost
 {
 

Modified: sandbox/mgl/boost/mgl/next_prior.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/next_prior.hpp (original)
+++ sandbox/mgl/boost/mgl/next_prior.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -9,8 +9,10 @@
 
 #include <boost/mgl/aux_/next_prior_impl.hpp>
 
+#include <boost/mpl/void.hpp>
+
+#include <boost/type_traits/is_same.hpp>
 #include <boost/utility/enable_if.hpp>
-#include <boost/type_traits/is_void.hpp>
 
 namespace boost
 {
@@ -19,31 +21,31 @@
 {
 
 /// \brief Move iterator to the next vertex
-/// \param Iterator Iterator that should be moved
+/// \tparam Iterator Iterator that should be moved
 template<class Iterator, class Enable = void>
 struct next
 {
- typedef typename aux::next_impl<Iterator>::template apply<Iterator>::type type;
+ typedef typename aux::next_impl<Iterator>::template apply<Iterator>::type type;
 };
 
 template<class Iterator>
 struct next<Iterator, typename ::boost::enable_if< ::boost::is_same<Iterator, ::boost::mpl::void_> >::type>
 {
- typedef ::boost::mpl::void_ type;
+ typedef ::boost::mpl::void_ type;
 };
 
 /// \brief Move iterator to the previous vertex
-/// \param Iterator Iterator that should be moved
+/// \tparam Iterator Iterator that should be moved
 template<class Iterator>
 struct prior
 {
- typedef typename aux::prior_impl<Iterator>::template apply<Iterator>::type type;
+ typedef typename aux::prior_impl<Iterator>::template apply<Iterator>::type type;
 };
 
 template<class Iterator>
 struct edge_next
 {
- typedef typename aux::edge_next_impl<Iterator>::template apply<Iterator>::type type;
+ typedef typename aux::edge_next_impl<Iterator>::template apply<Iterator>::type type;
 };
 
 } // namespace mgl

Modified: sandbox/mgl/boost/mgl/row.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/row.hpp (original)
+++ sandbox/mgl/boost/mgl/row.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -16,8 +16,8 @@
 template<class Vertex, class VertexList>
 struct row
 {
- typedef Vertex vertex;
- typedef VertexList adjacency_vertices;
+ typedef Vertex vertex;
+ typedef VertexList adjacency_vertices;
 };
 
 } // namespace mgl

Modified: sandbox/mgl/boost/mgl/topological_sort.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/topological_sort.hpp (original)
+++ sandbox/mgl/boost/mgl/topological_sort.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -24,20 +24,20 @@
 template<class Graph>
 struct topological_sort
 {
- typedef typename depth_first_search<
- Graph,
- aux::predecessor_edge_builder
- >::type::visitor_result predecessor_map;
-
- BOOST_MPL_ASSERT_NOT(( ::boost::mpl::empty<predecessor_map> ));
-
- typedef typename aux::topological_sort_impl<
- Graph,
- predecessor_map,
- ::boost::mpl::vector0<>
- >::type type;
+ typedef typename depth_first_search<
+ Graph,
+ aux::predecessor_edge_builder
+ >::type::visitor_result predecessor_map;
+
+ BOOST_MPL_ASSERT_NOT(( ::boost::mpl::empty<predecessor_map> ));
+
+ typedef typename aux::topological_sort_impl<
+ Graph,
+ predecessor_map,
+ ::boost::mpl::vector0<>
+ >::type type;
 
- BOOST_MPL_ASSERT_NOT(( ::boost::mpl::empty<type> ));
+ BOOST_MPL_ASSERT_NOT(( ::boost::mpl::empty<type> ));
 };
 
 } // namespace mgl

Modified: sandbox/mgl/boost/mgl/v_prop.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/v_prop.hpp (original)
+++ sandbox/mgl/boost/mgl/v_prop.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -18,20 +18,20 @@
 template<class T, class Property = ::boost::mpl::empty_base>
 struct v_prop
 {
- typedef T vertex;
- typedef Property property;
+ typedef T vertex;
+ typedef Property property;
 };
 
 template<class T>
 struct v_prop_vertex
 {
- typedef typename T::vertex type;
+ typedef typename T::vertex type;
 };
 
 template<class T>
 struct v_prop_property
 {
- typedef typename T::property type;
+ typedef typename T::property type;
 };
 
 } // namespace mgl

Modified: sandbox/mgl/boost/mgl/visitor_helpers.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/visitor_helpers.hpp (original)
+++ sandbox/mgl/boost/mgl/visitor_helpers.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -16,23 +16,25 @@
 template<class Visitor, class Vertex, class VisitorResult, class TraversalStack, class ColorMap>
 struct do_on_discover_vertex
 {
- typedef typename Visitor::template on_discover_vertex<
- Vertex,
- VisitorResult,
- TraversalStack,
- ColorMap
- >::type type;
+ typedef typename Visitor::template on_discover_vertex<
+ Vertex,
+ VisitorResult,
+ TraversalStack,
+ ColorMap
+ >::type type;
 };
 
-template<class Visitor, class Vertex1, class Vertex2, class VisitorResult, class TraversalStack, class ColorMap>
+template<class Visitor, class Vertex1, class Vertex2, typename Weight, class VisitorResult, class TraversalStack, class ColorMap>
 struct do_on_examine_edge
 {
- typedef typename Visitor::template on_examine_edge<
- ::boost::mpl::pair<Vertex1, Vertex2>,
- VisitorResult,
- TraversalStack,
- ColorMap
- >::type type;
+ typedef typename Visitor::template on_examine_edge<
+ Vertex1,
+ Vertex2,
+ Weight,
+ VisitorResult,
+ TraversalStack,
+ ColorMap
+ >::type type;
 };
 
 } // namespace mgl

Modified: sandbox/mgl/boost/mgl/visitors.hpp
==============================================================================
--- sandbox/mgl/boost/mgl/visitors.hpp (original)
+++ sandbox/mgl/boost/mgl/visitors.hpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -7,19 +7,17 @@
 #ifndef BOOST_MGL_VISITORS_HPP
 #define BOOST_MGL_VISITORS_HPP
 
-#include <boost/mpl/has_xxx.hpp>
-#include <boost/mpl/push_back.hpp>
-#include <boost/mpl/plus.hpp>
 #include <boost/mpl/arithmetic.hpp>
+#include <boost/mpl/contains.hpp>
+#include <boost/mpl/equal.hpp>
+#include <boost/mpl/has_xxx.hpp>
 #include <boost/mpl/int.hpp>
+#include <boost/mpl/plus.hpp>
+#include <boost/mpl/push_back.hpp>
 #include <boost/mpl/void.hpp>
-#include <boost/mpl/equal.hpp>
-#include <boost/mpl/contains.hpp>
 
 #include <boost/mgl/colors.hpp>
 
-#include <boost/type_traits/is_same.hpp>
-
 namespace boost
 {
 
@@ -31,74 +29,74 @@
 
 struct null_visitor
 {
- struct on_init
- {
- typedef ::boost::mpl::void_ type;
- };
+ struct on_init
+ {
+ typedef ::boost::mpl::void_ type;
+ };
 };
 
 struct vertex_trace_visitor
 {
- typedef ::boost::mpl::true_ discover_vertex;
+ typedef ::boost::mpl::true_ discover_vertex;
 
- struct on_init
- {
- typedef ::boost::mpl::vector0<> type;
- };
-
- template<typename Vertex, typename T, typename TraversalStack, typename ColorMap>
- struct on_discover_vertex
- {
- typedef typename ::boost::mpl::push_back<T, Vertex>::type type;
- };
+ struct on_init
+ {
+ typedef ::boost::mpl::vector0<> type;
+ };
+
+ template<typename Vertex, typename T, typename TraversalStack, typename ColorMap>
+ struct on_discover_vertex
+ {
+ typedef typename ::boost::mpl::push_back<T, Vertex>::type type;
+ };
 };
 
 struct vertex_counter_visitor
 {
- typedef ::boost::mpl::true_ discover_vertex;
+ typedef ::boost::mpl::true_ discover_vertex;
 
- struct on_init
- {
- typedef ::boost::mpl::int_<0> type;
- };
-
- template<typename Vertex, typename T, typename TraversalStack, typename ColorMap>
- struct on_discover_vertex
- {
- typedef typename ::boost::mpl::plus<T, ::boost::mpl::int_<1> >::type type;
- };
+ struct on_init
+ {
+ typedef ::boost::mpl::int_<0> type;
+ };
+
+ template<typename Vertex, typename T, typename TraversalStack, typename ColorMap>
+ struct on_discover_vertex
+ {
+ typedef typename ::boost::mpl::plus<T, ::boost::mpl::int_<1> >::type type;
+ };
 };
 
 struct edge_trace_visitor
 {
- typedef ::boost::mpl::true_ examine_edge;
+ typedef ::boost::mpl::true_ examine_edge;
 
- struct on_init
- {
- typedef ::boost::mpl::vector0<> type;
- };
-
- template<typename Edge, typename T, typename TraversalStack, typename ColorMap>
- struct on_examine_edge
- {
- typedef typename ::boost::mpl::push_back<T, Edge>::type type;
- };
+ struct on_init
+ {
+ typedef ::boost::mpl::vector0<> type;
+ };
+
+ template<typename Vertex1, typename Vertex2, typename Weight, typename T, typename TraversalStack, typename ColorMap>
+ struct on_examine_edge
+ {
+ typedef typename ::boost::mpl::push_back<T, ::boost::mpl::pair<Vertex1, Vertex2> >::type type;
+ };
 };
 
 struct edge_counter_visitor
 {
- typedef ::boost::mpl::true_ examine_edge;
+ typedef ::boost::mpl::true_ examine_edge;
 
- struct on_init
- {
- typedef ::boost::mpl::int_<0> type;
- };
-
- template<typename Edge, typename T, typename TraversalStack, typename ColorMap>
- struct on_examine_edge
- {
- typedef typename ::boost::mpl::plus<T, ::boost::mpl::int_<1> >::type type;
- };
+ struct on_init
+ {
+ typedef ::boost::mpl::int_<0> type;
+ };
+
+ template<typename Vertex1, typename Vertex2, typename Weight, typename T, typename TraversalStack, typename ColorMap>
+ struct on_examine_edge
+ {
+ typedef typename ::boost::mpl::plus<T, ::boost::mpl::int_<1> >::type type;
+ };
 };
 
 } // namespace mgl

Added: sandbox/mgl/libs/mgl/examples/hello_world.cpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/libs/mgl/examples/hello_world.cpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -0,0 +1,35 @@
+// Copyright Franz Alt 2009-2011
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/mgl/mgl.hpp>
+
+using namespace boost::mgl;
+
+namespace mpl = boost::mpl;
+
+class hello_world : public directed_graph<hello_world>
+{
+public:
+ // vertices
+ struct hello {};
+ struct mgl {};
+ struct world {};
+
+ // adjacency list
+ struct adjacency_list : mpl::vector3<
+ // node from adjacency nodes
+ // +--------------+----------------------------+
+ row< hello , mpl::vector1<mgl> >,
+ row< mgl , mpl::vector1<world> >,
+ row< world , mpl::vector1<world> >
+ // +--------------+----------------------------+
+ > {};
+};
+
+int main()
+{
+ return 0;
+}

Added: sandbox/mgl/libs/mgl/examples/sample_graph.cpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/libs/mgl/examples/sample_graph.cpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -0,0 +1,51 @@
+// Copyright Franz Alt 2009-2011
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <cxxabi.h>
+#include <iostream>
+#include <typeinfo>
+
+#include <boost/mgl/mgl.hpp>
+
+using namespace std;
+using namespace boost::mgl;
+
+namespace mpl = boost::mpl;
+
+class sample_graph : public directed_graph<sample_graph>
+{
+public:
+ // vertices
+ struct A {};
+ struct B {};
+ struct C {};
+ struct D {};
+ struct E {};
+ struct F {};
+
+ // adjacency list
+ struct adjacency_list : mpl::vector6<
+ // node from adjacency nodes
+ // +--------------+----------------------------+
+ row< A , mpl::vector1<B> >,
+ row< B , mpl::vector2<B, C> >,
+ row< C , mpl::vector2<A, E> >,
+ row< D , mpl::vector0<> >,
+ row< E , mpl::vector2<B, C> >,
+ row< F , mpl::vector1<D> >
+ // +--------------+----------------------------+
+ > {};
+};
+
+int main()
+{
+ typedef depth_first_search<sample_graph,vertex_trace_visitor>::type::visitor_result result;
+ typedef BOOST_TYPEOF(result()) result_t;
+
+ cout << abi::__cxa_demangle(typeid(result_t).name(), 0, 0, 0) << endl;
+
+ return 0;
+}

Added: sandbox/mgl/libs/mgl/examples/weighted_graph.cpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/libs/mgl/examples/weighted_graph.cpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -0,0 +1,97 @@
+// Copyright Franz Alt 2009-2011
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <cxxabi.h>
+#include <iostream>
+#include <typeinfo>
+
+#define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS
+#undef BOOST_MPL_LIMIT_METAFUNCTION_ARITY
+#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 7
+#include <boost/mpl/apply.hpp>
+#include <boost/mpl/int.hpp>
+#include <boost/mpl/plus.hpp>
+
+#include <boost/mgl/mgl.hpp>
+
+using namespace std;
+using namespace boost::mgl;
+
+namespace mpl = boost::mpl;
+
+class weighted_graph : public directed_graph<weighted_graph>
+{
+public:
+ // vertices
+ struct A {};
+ struct B {};
+ struct C {};
+ struct D {};
+ struct E {};
+ struct F {};
+ struct G {};
+
+ // adjacency list
+ struct adjacency_list : mpl::vector7<
+ // node from adjacency nodes
+ // +--------------+----------------------------+
+ row< A , mpl::vector2<B, C> >,
+ row< B , mpl::vector2<E, D> >,
+ row< C , mpl::vector2<F, G> >,
+ row< D , mpl::vector1<A> >,
+ row< E , mpl::vector0<> >,
+ row< F , mpl::vector0<> >,
+ row< G , mpl::vector1<C> >
+ // +--------------+----------------------------+
+ > {};
+
+ // edge weights
+ struct edge_list : mpl::vector8<
+ // node from node to weight
+ // +-----------+-----------+-----------+
+ edge < A , B , 2 >,
+ edge < A , C , 4 >,
+ // +-----------+-----------+-----------+
+ edge < B , E , 7 >,
+ edge < B , D , 1 >,
+ // +-----------+-----------+-----------+
+ edge < C , F , 3 >,
+ edge < C , G , 5 >,
+ // +-----------+-----------+-----------+
+ edge < D , A , 3 >,
+ // +-----------+-----------+-----------+
+ edge < G , C , 8 >
+ // +-----------+-----------+-----------+
+ > {};
+};
+
+// a visitor accumulating the weights of the edges
+struct edge_weights_accumulator
+{
+ typedef ::boost::mpl::true_ examine_edge;
+
+ struct on_init
+ {
+ typedef ::boost::mpl::int_<0> type;
+ };
+
+ template<typename Vertex1, typename Vertex2, typename Weight, typename T, typename TraversalStack, typename ColorMap>
+ struct on_examine_edge
+ {
+// typedef typename ::boost::mpl::push_back<T, Edge>::type type;
+ typedef typename ::boost::mpl::plus<T, Weight>::type type;
+ };
+};
+
+int main()
+{
+ typedef depth_first_search<weighted_graph, edge_weights_accumulator>::type::visitor_result result;
+ typedef BOOST_TYPEOF(result()) result_t;
+
+ cout << abi::__cxa_demangle(typeid(result_t).name(), 0, 0, 0) << endl;
+
+ return 0;
+}

Modified: sandbox/mgl/libs/mgl/test/bfs_iteration.cpp
==============================================================================
--- sandbox/mgl/libs/mgl/test/bfs_iteration.cpp (original)
+++ sandbox/mgl/libs/mgl/test/bfs_iteration.cpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -78,59 +78,59 @@
         typedef deref<iter>::type iter_deref;
         typedef BOOST_TYPEOF(iter_deref()) iter_deref_t;
 
- BOOST_CHECK_MESSAGE(typeid(iter_deref_t) != typeid(void_t), "bfs_begin<> should return a valid iterator type");
+ BOOST_CHECK_MESSAGE(typeid(iter_deref_t) != typeid(void_t), "bfs_begin<> shouldn't return a valid iterator type");
 
         typedef ::boost::mgl::next<iter>::type iter_next1;
         typedef deref<iter_next1>::type iter_next1_deref;
         typedef BOOST_TYPEOF(iter_next1_deref()) iter_next1_deref_t;
 
- BOOST_CHECK_MESSAGE(typeid(iter_next1_deref_t) != typeid(end_t), "next<> should return a valid iterator type");
+ BOOST_CHECK_MESSAGE(typeid(iter_next1_deref_t) != typeid(end_t), "next<> shouldn't return a valid iterator type");
 
         typedef ::boost::mgl::next<iter_next1>::type iter_next2;
         typedef deref<iter_next2>::type iter_next2_deref;
         typedef BOOST_TYPEOF(iter_next2_deref()) iter_next2_deref_t;
 
- BOOST_CHECK_MESSAGE(typeid(iter_next2_deref_t) != typeid(end_t), "next<> should return a valid iterator type");
+ BOOST_CHECK_MESSAGE(typeid(iter_next2_deref_t) != typeid(end_t), "next<> shouldn't return a valid iterator type");
 
         typedef ::boost::mgl::next<iter_next2>::type iter_next3;
         typedef deref<iter_next3>::type iter_next3_deref;
         typedef BOOST_TYPEOF(iter_next3_deref()) iter_next3_deref_t;
 
- BOOST_CHECK_MESSAGE(typeid(iter_next3_deref_t) != typeid(end_t), "next<> should return a valid iterator type");
+ BOOST_CHECK_MESSAGE(typeid(iter_next3_deref_t) != typeid(end_t), "next<> shouldn't return a valid iterator type");
 
         typedef ::boost::mgl::next<iter_next3>::type iter_next4;
         typedef deref<iter_next4>::type iter_next4_deref;
         typedef BOOST_TYPEOF(iter_next4_deref()) iter_next4_deref_t;
 
- BOOST_CHECK_MESSAGE(typeid(iter_next4_deref_t) != typeid(end_t), "next<> should return a valid iterator type");
+ BOOST_CHECK_MESSAGE(typeid(iter_next4_deref_t) != typeid(end_t), "next<> shouldn't return a valid iterator type");
 
         typedef ::boost::mgl::next<iter_next4>::type iter_next5;
         typedef deref<iter_next5>::type iter_next5_deref;
         typedef BOOST_TYPEOF(iter_next5_deref()) iter_next5_deref_t;
 
- BOOST_CHECK_MESSAGE(typeid(iter_next5_deref_t) != typeid(end_t), "next<> should return a valid iterator type");
+ BOOST_CHECK_MESSAGE(typeid(iter_next5_deref_t) != typeid(end_t), "next<> shouldn't return a valid iterator type");
 
         typedef ::boost::mgl::next<iter_next5>::type iter_next6;
         typedef deref<iter_next6>::type iter_next6_deref;
         typedef BOOST_TYPEOF(iter_next6_deref()) iter_next6_deref_t;
 
- BOOST_CHECK_MESSAGE(typeid(iter_next6_deref_t) != typeid(end_t), "next<> should return a valid iterator type");
+ BOOST_CHECK_MESSAGE(typeid(iter_next6_deref_t) != typeid(end_t), "next<> shouldn't return a valid iterator type");
 
         typedef ::boost::mgl::next<iter_next6>::type iter_next7;
         typedef deref<iter_next7>::type iter_next7_deref;
         typedef BOOST_TYPEOF(iter_next7_deref()) iter_next7_deref_t;
 
- BOOST_CHECK_MESSAGE(typeid(iter_next7_deref_t) != typeid(end_t), "next<> should return a valid iterator type");
+ BOOST_CHECK_MESSAGE(typeid(iter_next7_deref_t) != typeid(end_t), "next<> shouldn't return a valid iterator type");
 
         typedef ::boost::mgl::next<iter_next7>::type iter_next8;
         typedef deref<iter_next8>::type iter_next8_deref;
         typedef BOOST_TYPEOF(iter_next8_deref()) iter_next8_deref_t;
 
- BOOST_CHECK_MESSAGE(typeid(iter_next8_deref_t) != typeid(end_t), "next<> should return a valid iterator type");
+ BOOST_CHECK_MESSAGE(typeid(iter_next8_deref_t) != typeid(end_t), "next<> shouldn't return a valid iterator type");
 
         typedef ::boost::mgl::next<iter_next8>::type iter_next9;
         typedef deref<iter_next9>::type iter_next9_deref;
         typedef BOOST_TYPEOF(iter_next9_deref()) iter_next9_deref_t;
 
- BOOST_CHECK_MESSAGE(typeid(iter_next9_deref_t) == typeid(end_t), "bfs_begin<> should return mpl::void_ at invalid graph type");
+ BOOST_CHECK_MESSAGE(typeid(iter_next9_deref_t) == typeid(end_t), "next<> should return a valid graph::end type");
 }

Modified: sandbox/mgl/libs/mgl/test/breadth_first_search.cpp
==============================================================================
--- sandbox/mgl/libs/mgl/test/breadth_first_search.cpp (original)
+++ sandbox/mgl/libs/mgl/test/breadth_first_search.cpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -8,7 +8,7 @@
 
 #define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS
 #undef BOOST_MPL_LIMIT_METAFUNCTION_ARITY
-#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 6
+#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 7
 #include <boost/mpl/apply.hpp>
 
 #include <boost/mpl/vector.hpp>
@@ -68,10 +68,10 @@
 {
         typedef BOOST_TYPEOF(mpl::void_()) void_t;
 
- typedef breadth_first_search<foo>::type::vertex_trace dfs;
- typedef BOOST_TYPEOF(dfs()) dfs_t;
+ typedef breadth_first_search<foo>::type::vertex bfs;
+ typedef BOOST_TYPEOF(bfs()) bfs_t;
 
- BOOST_CHECK_MESSAGE(typeid(dfs_t) == typeid(void_t), "breadth_first_search<> should return mpl::void_ for invalid graph type");
+ BOOST_CHECK_MESSAGE(typeid(bfs_t) == typeid(void_t), "breadth_first_search<> should return mpl::void_ for invalid graph type");
 }
 
 BOOST_AUTO_TEST_CASE(perform_breadth_first_search)
@@ -88,10 +88,10 @@
                 ::boost::mgl::vertex_trace_visitor,
                 v0,
                 ::boost::mgl::EndWhenNoVerticesFound
- >::type::vertex_trace result11;
+ >::type::visitor_result result11;
         typedef BOOST_TYPEOF(result11()) result11_t;
 
- BOOST_CHECK_MESSAGE(typeid(result11_t) == typeid(expected_result11_t), "breadth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result11_t, expected_result11_t>::value), "breadth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from first vertex (visit all vertices)
         typedef mpl::vector10<
@@ -115,7 +115,7 @@
>::type::visitor_result result12;
         typedef BOOST_TYPEOF(result12()) result12_t;
 
- BOOST_CHECK_MESSAGE(typeid(result12_t) == typeid(expected_result12_t), "breadth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result12_t, expected_result12_t>::value), "breadth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v1'
         typedef mpl::vector4<
@@ -134,7 +134,7 @@
>::type::visitor_result result21;
         typedef BOOST_TYPEOF(result21()) result21_t;
 
- BOOST_CHECK_MESSAGE(typeid(result21_t) == typeid(expected_result21_t), "breadth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result21_t, expected_result21_t>::value), "breadth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v1' (visit all vertices)
         typedef mpl::vector10<
@@ -158,7 +158,7 @@
>::type::visitor_result result22;
         typedef BOOST_TYPEOF(result22()) result22_t;
 
- BOOST_CHECK_MESSAGE(typeid(result22_t) == typeid(expected_result22_t), "breadth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result22_t, expected_result22_t>::value), "breadth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v2'
         typedef mpl::vector8<
@@ -181,7 +181,7 @@
>::type::visitor_result result31;
         typedef BOOST_TYPEOF(result31()) result31_t;
 
- BOOST_CHECK_MESSAGE(typeid(result31_t) == typeid(expected_result31_t), "breadth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result31_t, expected_result31_t>::value), "breadth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v2' (visit all vertices)
         typedef mpl::vector10<
@@ -205,7 +205,7 @@
>::type::visitor_result result32;
         typedef BOOST_TYPEOF(result32()) result32_t;
 
- BOOST_CHECK_MESSAGE(typeid(result32_t) == typeid(expected_result32_t), "breadth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result32_t, expected_result32_t>::value), "breadth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v3'
         typedef mpl::vector4<
@@ -224,7 +224,7 @@
>::type::visitor_result result41;
         typedef BOOST_TYPEOF(result41()) result41_t;
 
- BOOST_CHECK_MESSAGE(typeid(result41_t) == typeid(expected_result41_t), "breadth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result41_t, expected_result41_t>::value), "breadth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v3' (visit all vertices)
         typedef mpl::vector10<
@@ -248,7 +248,7 @@
>::type::visitor_result result42;
         typedef BOOST_TYPEOF(result42()) result42_t;
 
- BOOST_CHECK_MESSAGE(typeid(result42_t) == typeid(expected_result42_t), "breadth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result42_t, expected_result42_t>::value), "breadth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v4'
         typedef mpl::vector6<
@@ -269,7 +269,7 @@
>::type::visitor_result result51;
         typedef BOOST_TYPEOF(result51()) result51_t;
 
- BOOST_CHECK_MESSAGE(typeid(result51_t) == typeid(expected_result51_t), "breadth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result51_t, expected_result51_t>::value), "breadth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v4' (visit all vertices)
         typedef mpl::vector10<
@@ -293,7 +293,7 @@
>::type::visitor_result result52;
         typedef BOOST_TYPEOF(result52()) result52_t;
 
- BOOST_CHECK_MESSAGE(typeid(result52_t) == typeid(expected_result52_t), "breadth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result52_t, expected_result52_t>::value), "breadth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v5'
         typedef mpl::vector1<
@@ -309,7 +309,7 @@
>::type::visitor_result result61;
         typedef BOOST_TYPEOF(result61()) result61_t;
 
- BOOST_CHECK_MESSAGE(typeid(result61_t) == typeid(expected_result61_t), "breadth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result61_t, expected_result61_t>::value), "breadth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v5' (visit all vertices)
         typedef mpl::vector10<
@@ -333,7 +333,7 @@
>::type::visitor_result result62;
         typedef BOOST_TYPEOF(result62()) result62_t;
 
- BOOST_CHECK_MESSAGE(typeid(result62_t) == typeid(expected_result62_t), "breadth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result62_t, expected_result62_t>::value), "breadth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v6'
         typedef mpl::vector1<
@@ -349,7 +349,7 @@
>::type::visitor_result result71;
         typedef BOOST_TYPEOF(result71()) result71_t;
 
- BOOST_CHECK_MESSAGE(typeid(result71_t) == typeid(expected_result71_t), "breadth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result71_t, expected_result71_t>::value), "breadth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v6' (visit all vertices)
         typedef mpl::vector10<
@@ -373,7 +373,7 @@
>::type::visitor_result result72;
         typedef BOOST_TYPEOF(result72()) result72_t;
 
- BOOST_CHECK_MESSAGE(typeid(result72_t) == typeid(expected_result72_t), "breadth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result72_t, expected_result72_t>::value), "breadth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v7'
         typedef mpl::vector4<
@@ -392,7 +392,7 @@
>::type::visitor_result result81;
         typedef BOOST_TYPEOF(result81()) result81_t;
 
- BOOST_CHECK_MESSAGE(typeid(result81_t) == typeid(expected_result81_t), "breadth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result81_t, expected_result81_t>::value), "breadth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v7' (visit all vertices)
         typedef mpl::vector10<
@@ -416,7 +416,7 @@
>::type::visitor_result result82;
         typedef BOOST_TYPEOF(result82()) result82_t;
 
- BOOST_CHECK_MESSAGE(typeid(result82_t) == typeid(expected_result82_t), "breadth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result82_t, expected_result82_t>::value), "breadth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v8'
         typedef mpl::vector4<
@@ -435,7 +435,7 @@
>::type::visitor_result result91;
         typedef BOOST_TYPEOF(result91()) result91_t;
 
- BOOST_CHECK_MESSAGE(typeid(result91_t) == typeid(expected_result91_t), "breadth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result91_t, expected_result91_t>::value), "breadth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v8' (visit all vertices)
         typedef mpl::vector10<
@@ -459,7 +459,7 @@
>::type::visitor_result result92;
         typedef BOOST_TYPEOF(result92()) result92_t;
 
- BOOST_CHECK_MESSAGE(typeid(result92_t) == typeid(expected_result92_t), "breadth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result92_t, expected_result92_t>::value), "breadth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v9'
         typedef mpl::vector1<
@@ -475,7 +475,7 @@
>::type::visitor_result result101;
         typedef BOOST_TYPEOF(result101()) result101_t;
 
- BOOST_CHECK_MESSAGE(typeid(result101_t) == typeid(expected_result101_t), "breadth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result101_t, expected_result101_t>::value), "breadth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v9' (visit all vertices)
         typedef mpl::vector10<
@@ -499,5 +499,5 @@
>::type::visitor_result result102;
         typedef BOOST_TYPEOF(result102()) result102_t;
 
- BOOST_CHECK_MESSAGE(typeid(result102_t) == typeid(expected_result102_t), "breadth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result102_t, expected_result102_t>::value), "breadth_first_search<> should return the right mpl::vector<> type");
 }

Modified: sandbox/mgl/libs/mgl/test/contains_cycle.cpp
==============================================================================
--- sandbox/mgl/libs/mgl/test/contains_cycle.cpp (original)
+++ sandbox/mgl/libs/mgl/test/contains_cycle.cpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -8,7 +8,7 @@
 
 #define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS
 #undef BOOST_MPL_LIMIT_METAFUNCTION_ARITY
-#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 6
+#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 7
 #include <boost/mpl/apply.hpp>
 
 #include <boost/mpl/bool.hpp>
@@ -81,5 +81,5 @@
         typedef contains_cycle<non_cycle_graph>::type result;
         typedef BOOST_TYPEOF(result()) result_t;
 
- BOOST_CHECK_MESSAGE(typeid(result_t) == typeid(false_t), "contains_cycle<> should return a proper ::mpl::false_");
+ BOOST_CHECK_MESSAGE(typeid(result_t) == typeid(false_t), "contains_cycle<> should return a proper ::mpl::true_");
 }

Modified: sandbox/mgl/libs/mgl/test/depth_first_search.cpp
==============================================================================
--- sandbox/mgl/libs/mgl/test/depth_first_search.cpp (original)
+++ sandbox/mgl/libs/mgl/test/depth_first_search.cpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -8,9 +8,10 @@
 
 #define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS
 #undef BOOST_MPL_LIMIT_METAFUNCTION_ARITY
-#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 6
+#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 7
 #include <boost/mpl/apply.hpp>
 
+#include <boost/mpl/equal.hpp>
 #include <boost/mpl/vector.hpp>
 #include <boost/mpl/void.hpp>
 
@@ -66,9 +67,9 @@
 
 BOOST_AUTO_TEST_CASE(invalid_depth_first_search)
 {
- typedef BOOST_TYPEOF(mpl::void_()) void_t;
+ typedef BOOST_TYPEOF(mpl::void_()) void_t;
 
- typedef depth_first_search<foo>::type::vertex_trace dfs;
+ typedef depth_first_search<foo>::type::vertex dfs;
         typedef BOOST_TYPEOF(dfs()) dfs_t;
 
         BOOST_CHECK_MESSAGE(typeid(dfs_t) == typeid(void_t), "depth_first_search<> should return mpl::void_ for invalid graph type");
@@ -91,10 +92,13 @@
> expected_result1;
         typedef BOOST_TYPEOF(expected_result1()) expected_result1_t;
 
- typedef depth_first_search<some_graph>::type::vertex_trace result1;
+ typedef depth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor
+ >::type::visitor_result result1;
         typedef BOOST_TYPEOF(result1()) result1_t;
 
- BOOST_CHECK_MESSAGE(typeid(result1_t) == typeid(expected_result1_t), "depth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result1_t, expected_result1_t>::value), "depth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v1'
         typedef mpl::vector4<
@@ -113,7 +117,7 @@
>::type::visitor_result result21;
         typedef BOOST_TYPEOF(result21()) result21_t;
 
- BOOST_CHECK_MESSAGE(typeid(result21_t) == typeid(expected_result21_t), "depth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result21_t, expected_result21_t>::value), "depth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v1' (visit all vertices)
         typedef mpl::vector10<
@@ -137,7 +141,7 @@
>::type::visitor_result result22;
         typedef BOOST_TYPEOF(result22()) result22_t;
 
- BOOST_CHECK_MESSAGE(typeid(result22_t) == typeid(expected_result22_t), "depth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result22_t, expected_result22_t>::value), "depth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v2'
         typedef mpl::vector8<
@@ -160,7 +164,7 @@
>::type::visitor_result result31;
         typedef BOOST_TYPEOF(result31()) result31_t;
 
- BOOST_CHECK_MESSAGE(typeid(result31_t) == typeid(expected_result31_t), "depth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result31_t, expected_result31_t>::value), "depth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v2' (visit all vertices)
         typedef mpl::vector10<
@@ -184,7 +188,7 @@
>::type::visitor_result result32;
         typedef BOOST_TYPEOF(result32()) result32_t;
 
- BOOST_CHECK_MESSAGE(typeid(result32_t) == typeid(expected_result32_t), "depth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result32_t, expected_result32_t>::value), "depth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v3'
         typedef mpl::vector4<
@@ -203,7 +207,7 @@
>::type::visitor_result result41;
         typedef BOOST_TYPEOF(result41()) result41_t;
 
- BOOST_CHECK_MESSAGE(typeid(result41_t) == typeid(expected_result41_t), "depth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result41_t, expected_result41_t>::value), "depth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v3' (visit all vertices)
         typedef mpl::vector10<
@@ -227,7 +231,7 @@
>::type::visitor_result result42;
         typedef BOOST_TYPEOF(result42()) result42_t;
 
- BOOST_CHECK_MESSAGE(typeid(result42_t) == typeid(expected_result42_t), "depth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result42_t, expected_result42_t>::value), "depth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v4'
         typedef mpl::vector6<
@@ -248,7 +252,7 @@
>::type::visitor_result result51;
         typedef BOOST_TYPEOF(result51()) result51_t;
 
- BOOST_CHECK_MESSAGE(typeid(result51_t) == typeid(expected_result51_t), "depth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result51_t, expected_result51_t>::value), "depth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v4' (visit all vertices)
         typedef mpl::vector10<
@@ -272,7 +276,7 @@
>::type::visitor_result result52;
         typedef BOOST_TYPEOF(result52()) result52_t;
 
- BOOST_CHECK_MESSAGE(typeid(result52_t) == typeid(expected_result52_t), "depth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result52_t, expected_result52_t>::value), "depth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v5'
         typedef mpl::vector1<
@@ -288,7 +292,7 @@
>::type::visitor_result result61;
         typedef BOOST_TYPEOF(result61()) result61_t;
 
- BOOST_CHECK_MESSAGE(typeid(result61_t) == typeid(expected_result61_t), "depth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result61_t, expected_result61_t>::value), "depth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v5' (visit all vertices)
         typedef mpl::vector10<
@@ -312,7 +316,7 @@
>::type::visitor_result result62;
         typedef BOOST_TYPEOF(result62()) result62_t;
 
- BOOST_CHECK_MESSAGE(typeid(result62_t) == typeid(expected_result62_t), "depth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result62_t, expected_result62_t>::value), "depth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v6'
         typedef mpl::vector1<
@@ -328,7 +332,7 @@
>::type::visitor_result result71;
         typedef BOOST_TYPEOF(result71()) result71_t;
 
- BOOST_CHECK_MESSAGE(typeid(result71_t) == typeid(expected_result71_t), "depth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result71_t, expected_result71_t>::value), "depth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v6' (visit all vertices)
         typedef mpl::vector10<
@@ -352,7 +356,7 @@
>::type::visitor_result result72;
         typedef BOOST_TYPEOF(result72()) result72_t;
 
- BOOST_CHECK_MESSAGE(typeid(result72_t) == typeid(expected_result72_t), "depth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result72_t, expected_result72_t>::value), "depth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v7'
         typedef mpl::vector4<
@@ -371,7 +375,7 @@
>::type::visitor_result result81;
         typedef BOOST_TYPEOF(result81()) result81_t;
 
- BOOST_CHECK_MESSAGE(typeid(result81_t) == typeid(expected_result81_t), "depth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result81_t, expected_result81_t>::value), "depth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v7' (visit all vertices)
         typedef mpl::vector10<
@@ -395,7 +399,7 @@
>::type::visitor_result result82;
         typedef BOOST_TYPEOF(result82()) result82_t;
 
- BOOST_CHECK_MESSAGE(typeid(result82_t) == typeid(expected_result82_t), "depth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result82_t, expected_result82_t>::value), "depth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v8'
         typedef mpl::vector4<
@@ -414,7 +418,7 @@
>::type::visitor_result result91;
         typedef BOOST_TYPEOF(result91()) result91_t;
 
- BOOST_CHECK_MESSAGE(typeid(result91_t) == typeid(expected_result91_t), "depth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result91_t, expected_result91_t>::value), "depth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v8' (visit all vertices)
         typedef mpl::vector10<
@@ -438,7 +442,7 @@
>::type::visitor_result result92;
         typedef BOOST_TYPEOF(result92()) result92_t;
 
- BOOST_CHECK_MESSAGE(typeid(result92_t) == typeid(expected_result92_t), "depth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result92_t, expected_result92_t>::value), "depth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v9'
         typedef mpl::vector1<
@@ -454,7 +458,7 @@
>::type::visitor_result result101;
         typedef BOOST_TYPEOF(result101()) result101_t;
 
- BOOST_CHECK_MESSAGE(typeid(result101_t) == typeid(expected_result101_t), "depth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result101_t, expected_result101_t>::value), "depth_first_search<> should return the right mpl::vector<> type");
 
         // perform search from vertex 'v9' (visit all vertices)
         typedef mpl::vector10<
@@ -478,5 +482,5 @@
>::type::visitor_result result102;
         typedef BOOST_TYPEOF(result102()) result102_t;
 
- BOOST_CHECK_MESSAGE(typeid(result102_t) == typeid(expected_result102_t), "depth_first_search<> should return the right mpl::vector<> type");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result102_t, expected_result102_t>::value), "depth_first_search<> should return the right mpl::vector<> type");
 }

Modified: sandbox/mgl/libs/mgl/test/dfs_iteration.cpp
==============================================================================
--- sandbox/mgl/libs/mgl/test/dfs_iteration.cpp (original)
+++ sandbox/mgl/libs/mgl/test/dfs_iteration.cpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -103,61 +103,61 @@
         typedef deref<iter>::type iter_deref;
         typedef BOOST_TYPEOF(iter_deref()) iter_deref_t;
 
- BOOST_CHECK_MESSAGE(typeid(iter_deref_t) != typeid(void_t), "dfs_begin<> should return a valid iterator type");
+ BOOST_CHECK_MESSAGE(typeid(iter_deref_t) != typeid(void_t), "dfs_begin<> shouldn't return a valid iterator type");
 
         typedef ::boost::mgl::next<iter>::type iter_next1;
         typedef deref<iter_next1>::type iter_next1_deref;
         typedef BOOST_TYPEOF(iter_next1_deref()) iter_next1_deref_t;
 
- BOOST_CHECK_MESSAGE(typeid(iter_next1_deref_t) != typeid(end_t), "next<> should return a valid iterator type");
+ BOOST_CHECK_MESSAGE(typeid(iter_next1_deref_t) != typeid(end_t), "next<> shouldn't return a valid iterator type");
 
         typedef ::boost::mgl::next<iter_next1>::type iter_next2;
         typedef deref<iter_next2>::type iter_next2_deref;
         typedef BOOST_TYPEOF(iter_next2_deref()) iter_next2_deref_t;
 
- BOOST_CHECK_MESSAGE(typeid(iter_next2_deref_t) != typeid(end_t), "next<> should return a valid iterator type");
+ BOOST_CHECK_MESSAGE(typeid(iter_next2_deref_t) != typeid(end_t), "next<> shouldn't return a valid iterator type");
 
         typedef ::boost::mgl::next<iter_next2>::type iter_next3;
         typedef deref<iter_next3>::type iter_next3_deref;
         typedef BOOST_TYPEOF(iter_next3_deref()) iter_next3_deref_t;
 
- BOOST_CHECK_MESSAGE(typeid(iter_next3_deref_t) != typeid(end_t), "next<> should return a valid iterator type");
+ BOOST_CHECK_MESSAGE(typeid(iter_next3_deref_t) != typeid(end_t), "next<> shouldn't return a valid iterator type");
 
         typedef ::boost::mgl::next<iter_next3>::type iter_next4;
         typedef deref<iter_next4>::type iter_next4_deref;
         typedef BOOST_TYPEOF(iter_next4_deref()) iter_next4_deref_t;
 
- BOOST_CHECK_MESSAGE(typeid(iter_next4_deref_t) != typeid(end_t), "next<> should return a valid iterator type");
+ BOOST_CHECK_MESSAGE(typeid(iter_next4_deref_t) != typeid(end_t), "next<> shouldn't return a valid iterator type");
 
         typedef ::boost::mgl::next<iter_next4>::type iter_next5;
         typedef deref<iter_next5>::type iter_next5_deref;
         typedef BOOST_TYPEOF(iter_next5_deref()) iter_next5_deref_t;
 
- BOOST_CHECK_MESSAGE(typeid(iter_next5_deref_t) != typeid(end_t), "next<> should return a valid iterator type");
+ BOOST_CHECK_MESSAGE(typeid(iter_next5_deref_t) != typeid(end_t), "next<> shouldn't return a valid iterator type");
 
         typedef ::boost::mgl::next<iter_next5>::type iter_next6;
         typedef deref<iter_next6>::type iter_next6_deref;
         typedef BOOST_TYPEOF(iter_next6_deref()) iter_next6_deref_t;
 
- BOOST_CHECK_MESSAGE(typeid(iter_next6_deref_t) != typeid(end_t), "next<> should return a valid iterator type");
+ BOOST_CHECK_MESSAGE(typeid(iter_next6_deref_t) != typeid(end_t), "next<> shouldn't return a valid iterator type");
 
         typedef ::boost::mgl::next<iter_next6>::type iter_next7;
         typedef deref<iter_next7>::type iter_next7_deref;
         typedef BOOST_TYPEOF(iter_next7_deref()) iter_next7_deref_t;
 
- BOOST_CHECK_MESSAGE(typeid(iter_next7_deref_t) != typeid(end_t), "next<> should return a valid iterator type");
+ BOOST_CHECK_MESSAGE(typeid(iter_next7_deref_t) != typeid(end_t), "next<> shouldn't return a valid iterator type");
 
         typedef ::boost::mgl::next<iter_next7>::type iter_next8;
         typedef deref<iter_next8>::type iter_next8_deref;
         typedef BOOST_TYPEOF(iter_next8_deref()) iter_next8_deref_t;
 
- BOOST_CHECK_MESSAGE(typeid(iter_next8_deref_t) != typeid(end_t), "next<> should return a valid iterator type");
+ BOOST_CHECK_MESSAGE(typeid(iter_next8_deref_t) != typeid(end_t), "next<> shouldn't return a valid iterator type");
 
         typedef ::boost::mgl::next<iter_next8>::type iter_next9;
         typedef deref<iter_next9>::type iter_next9_deref;
         typedef BOOST_TYPEOF(iter_next9_deref()) iter_next9_deref_t;
 
- BOOST_CHECK_MESSAGE(typeid(iter_next9_deref_t) != typeid(end_t), "next<> should return a valid iterator type");
+ BOOST_CHECK_MESSAGE(typeid(iter_next9_deref_t) != typeid(end_t), "next<> shouldn't return a valid iterator type");
 
         typedef ::boost::mgl::next<iter_next9>::type iter_next10;
         typedef deref<iter_next10>::type iter_next10_deref;

Modified: sandbox/mgl/libs/mgl/test/find_vertex.cpp
==============================================================================
--- sandbox/mgl/libs/mgl/test/find_vertex.cpp (original)
+++ sandbox/mgl/libs/mgl/test/find_vertex.cpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -8,7 +8,7 @@
 
 #define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS
 #undef BOOST_MPL_LIMIT_METAFUNCTION_ARITY
-#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 6
+#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 7
 #include <boost/mpl/apply.hpp>
 
 #include <boost/mpl/vector.hpp>

Modified: sandbox/mgl/libs/mgl/test/generic_graph.cpp
==============================================================================
--- sandbox/mgl/libs/mgl/test/generic_graph.cpp (original)
+++ sandbox/mgl/libs/mgl/test/generic_graph.cpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -8,7 +8,7 @@
 
 #define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS
 #undef BOOST_MPL_LIMIT_METAFUNCTION_ARITY
-#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 6
+#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 7
 #include <boost/mpl/apply.hpp>
 
 #include <boost/mpl/assert.hpp>
@@ -84,7 +84,7 @@
         typedef depth_first_search<simple_directed_graph, ::boost::mgl::edge_trace_visitor, b>::type::visitor_result result1;
         typedef BOOST_TYPEOF(result1()) result1_t;
 
- BOOST_CHECK_MESSAGE(typeid(result1_t) == typeid(expected_result1_t), "depth_first_search<> should return the expected mpl::vector<>");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result1_t, expected_result1_t>::value), "depth_first_search<> should return the expected mpl::vector<>");
 
         typedef mpl::vector1<
                 mpl::pair<b, d>
@@ -94,7 +94,7 @@
         typedef depth_first_search<simple_directed_graph, ::boost::mgl::edge_trace_visitor, b, EndWhenNoVerticesFound>::type::visitor_result result2;
         typedef BOOST_TYPEOF(result2()) result2_t;
 
- BOOST_CHECK_MESSAGE(typeid(result2_t) == typeid(expected_result2_t), "depth_first_search<> should return the expected mpl::vector<>");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result2_t, expected_result2_t>::value), "depth_first_search<> should return the expected mpl::vector<>");
 }
 
 BOOST_AUTO_TEST_CASE(test_directed_graph_dfs_find)
@@ -131,12 +131,12 @@
         typedef depth_first_search<simple_undirected_graph, ::boost::mgl::edge_trace_visitor, b>::type::visitor_result result1;
         typedef BOOST_TYPEOF(result1()) result1_t;
 
- BOOST_CHECK_MESSAGE(typeid(result1_t) == typeid(expected_result_t), "depth_first_search<> should return the expected mpl::vector<>");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result1_t, expected_result_t>::value), "depth_first_search<> should return the expected mpl::vector<>");
 
         typedef depth_first_search<simple_undirected_graph, ::boost::mgl::edge_trace_visitor, b, EndWhenNoVerticesFound>::type::visitor_result result2;
         typedef BOOST_TYPEOF(result2()) result2_t;
 
- BOOST_CHECK_MESSAGE(typeid(result2_t) == typeid(expected_result_t), "depth_first_search<> should return the expected mpl::vector<>");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result2_t, expected_result_t>::value), "depth_first_search<> should return the expected mpl::vector<>");
 }
 
 BOOST_AUTO_TEST_CASE(test_directed_graph_bfs)
@@ -152,7 +152,7 @@
         typedef breadth_first_search<simple_directed_graph, ::boost::mgl::edge_trace_visitor, b>::type::visitor_result result1;
         typedef BOOST_TYPEOF(result1()) result1_t;
 
- BOOST_CHECK_MESSAGE(typeid(result1_t) == typeid(expected_result1_t), "breadth_first_search<> should return the expected mpl::vector<>");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result1_t, expected_result1_t>::value), "breadth_first_search<> should return the expected mpl::vector<>");
 
         typedef mpl::vector1<
                 mpl::pair<b, d>
@@ -162,7 +162,7 @@
         typedef breadth_first_search<simple_directed_graph, ::boost::mgl::edge_trace_visitor, b, EndWhenNoVerticesFound>::type::visitor_result result2;
         typedef BOOST_TYPEOF(result2()) result2_t;
 
- BOOST_CHECK_MESSAGE(typeid(result2_t) == typeid(expected_result2_t), "breadth_first_search<> should return the expected mpl::vector<>");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result2_t, expected_result2_t>::value), "breadth_first_search<> should return the expected mpl::vector<>");
 }
 
 BOOST_AUTO_TEST_CASE(test_directed_graph_bfs_find)
@@ -199,10 +199,10 @@
         typedef breadth_first_search<simple_undirected_graph, ::boost::mgl::edge_trace_visitor, b>::type::visitor_result result1;
         typedef BOOST_TYPEOF(result1()) result1_t;
 
- BOOST_CHECK_MESSAGE(typeid(result1_t) == typeid(expected_result_t), "breadth_first_search<> should return the expected mpl::vector<>");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result1_t, expected_result_t>::value), "breadth_first_search<> should return the expected mpl::vector<>");
 
         typedef breadth_first_search<simple_undirected_graph, ::boost::mgl::edge_trace_visitor, b, EndWhenNoVerticesFound>::type::visitor_result result2;
         typedef BOOST_TYPEOF(result2()) result2_t;
 
- BOOST_CHECK_MESSAGE(typeid(result2_t) == typeid(expected_result_t), "breadth_first_search<> should return the expected mpl::vector<>");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result2_t, expected_result_t>::value), "breadth_first_search<> should return the expected mpl::vector<>");
 }

Modified: sandbox/mgl/libs/mgl/test/topological_sort.cpp
==============================================================================
--- sandbox/mgl/libs/mgl/test/topological_sort.cpp (original)
+++ sandbox/mgl/libs/mgl/test/topological_sort.cpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -8,7 +8,7 @@
 
 #define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS
 #undef BOOST_MPL_LIMIT_METAFUNCTION_ARITY
-#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 6
+#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 7
 #include <boost/mpl/apply.hpp>
 
 #include <boost/typeof/typeof.hpp>
@@ -60,5 +60,5 @@
         typedef topological_sort<some_graph>::type result;
         typedef BOOST_TYPEOF(result()) result_t;
 
- BOOST_CHECK_MESSAGE(typeid(result_t) == typeid(expected_result_t), "topological_sort<> should return a proper ::mpl::vector<>");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result_t, expected_result_t>::value), "topological_sort<> should return a proper ::mpl::vector<>");
 }

Modified: sandbox/mgl/libs/mgl/test/visitors.cpp
==============================================================================
--- sandbox/mgl/libs/mgl/test/visitors.cpp (original)
+++ sandbox/mgl/libs/mgl/test/visitors.cpp 2012-02-09 13:54:47 EST (Thu, 09 Feb 2012)
@@ -8,20 +8,21 @@
 
 #define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS
 #undef BOOST_MPL_LIMIT_METAFUNCTION_ARITY
-#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 6
+#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 7
 #include <boost/mpl/apply.hpp>
 
 #include <boost/typeof/typeof.hpp>
 
 #include <boost/mpl/bool.hpp>
-#include <boost/mpl/void.hpp>
-#include <boost/mpl/vector.hpp>
 #include <boost/mpl/equal.hpp>
+#include <boost/mpl/vector.hpp>
+#include <boost/mpl/void.hpp>
 
 #include <boost/type_traits/is_integral.hpp>
 
-#include <boost/mgl/directed_graph.hpp>
 #include <boost/mgl/depth_first_search.hpp>
+#include <boost/mgl/directed_graph.hpp>
+#include <boost/mgl/visitors.hpp>
 
 #define BOOST_TEST_MODULE "Visitor Test"
 #include <boost/test/unit_test.hpp>
@@ -57,57 +58,57 @@
 
 BOOST_AUTO_TEST_CASE(test_null_visitor)
 {
- typedef depth_first_search<some_graph, ::boost::mgl::null_visitor>::type::visitor_result result;
- typedef BOOST_TYPEOF(result()) result_t;
+ typedef depth_first_search<some_graph, ::boost::mgl::null_visitor>::type::visitor_result result;
+ typedef BOOST_TYPEOF(result()) result_t;
 
- typedef BOOST_TYPEOF(mpl::void_()) void_t;
+ typedef BOOST_TYPEOF(mpl::void_()) void_t;
 
- BOOST_CHECK_MESSAGE(typeid(result_t) == typeid(void_t), "depth_first_search<> should return ::mpl::void_");
+ BOOST_CHECK_MESSAGE(typeid(result_t) == typeid(void_t), "depth_first_search<> should return ::mpl::void_");
 }
 
 BOOST_AUTO_TEST_CASE(test_vertex_counter_visitor)
 {
- typedef depth_first_search<some_graph, ::boost::mgl::vertex_counter_visitor>::type::visitor_result result;
- typedef BOOST_TYPEOF(result()) result_t;
+ typedef depth_first_search<some_graph, ::boost::mgl::vertex_counter_visitor>::type::visitor_result result;
+ typedef BOOST_TYPEOF(result()) result_t;
 
- BOOST_CHECK_MESSAGE(result::value == 5, "depth_first_search<> should return 5");
+ BOOST_CHECK_MESSAGE(result::value == 5, "depth_first_search<> should return 5");
 }
 
 BOOST_AUTO_TEST_CASE(test_vertex_trace_visitor)
 {
- typedef mpl::vector5<v0, v4, v3, v2, v1> expected_result;
- typedef BOOST_TYPEOF(expected_result()) expected_result_t;
+ typedef mpl::vector5<v0, v4, v3, v2, v1> expected_result;
+ typedef BOOST_TYPEOF(expected_result()) expected_result_t;
 
- typedef depth_first_search<some_graph, ::boost::mgl::vertex_trace_visitor>::type::visitor_result result;
- typedef BOOST_TYPEOF(result()) result_t;
+ typedef depth_first_search<some_graph, ::boost::mgl::vertex_trace_visitor>::type::visitor_result result;
+ typedef BOOST_TYPEOF(result()) result_t;
 
- BOOST_CHECK_MESSAGE(typeid(result_t) == typeid(expected_result_t), "depth_first_search<> should return expected ::mpl::vector<>");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result_t, expected_result_t>::value), "depth_first_search<> should return expected ::mpl::vector<>");
 }
 
 BOOST_AUTO_TEST_CASE(test_edge_counter_visitor)
 {
- typedef depth_first_search<some_graph, ::boost::mgl::edge_counter_visitor>::type::visitor_result result;
- typedef BOOST_TYPEOF(result()) result_t;
+ typedef depth_first_search<some_graph, ::boost::mgl::edge_counter_visitor>::type::visitor_result result;
+ typedef BOOST_TYPEOF(result()) result_t;
 
- BOOST_CHECK_MESSAGE(result::value == 8, "depth_first_search<> should return 8");
+ BOOST_CHECK_MESSAGE(result::value == 8, "depth_first_search<> should return 8");
 }
 
 BOOST_AUTO_TEST_CASE(test_edge_trace_visitor)
 {
- typedef mpl::vector8<
- mpl::pair<v0, v4>,
- mpl::pair<v4, v4>,
- mpl::pair<v3, v0>,
- mpl::pair<v2, v1>,
- mpl::pair<v2, v0>,
- mpl::pair<v1, v2>,
- mpl::pair<v1, v1>,
- mpl::pair<v1, v0>
- > expected_result;
- typedef BOOST_TYPEOF(expected_result()) expected_result_t;
+ typedef mpl::vector8<
+ mpl::pair<v0, v4>,
+ mpl::pair<v4, v4>,
+ mpl::pair<v3, v0>,
+ mpl::pair<v2, v1>,
+ mpl::pair<v2, v0>,
+ mpl::pair<v1, v2>,
+ mpl::pair<v1, v1>,
+ mpl::pair<v1, v0>
+ > expected_result;
+ typedef BOOST_TYPEOF(expected_result()) expected_result_t;
 
- typedef depth_first_search<some_graph, ::boost::mgl::edge_trace_visitor>::type::visitor_result result;
- typedef BOOST_TYPEOF(result()) result_t;
+ typedef depth_first_search<some_graph, ::boost::mgl::edge_trace_visitor>::type::visitor_result result;
+ typedef BOOST_TYPEOF(result()) result_t;
 
- BOOST_CHECK_MESSAGE(typeid(result_t) == typeid(expected_result_t), "depth_first_search<> should return expected ::mpl::vector<>");
+ BOOST_CHECK_MESSAGE((::boost::mpl::equal<result_t, expected_result_t>::value), "depth_first_search<> should return expected ::mpl::vector<>");
 }

Date view Thread view Subject view Author view