Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r71924 - in sandbox/mgl: . boost boost/mgl boost/mgl/aux_ libs libs/mgl libs/mgl/doc libs/mgl/examples libs/mgl/test
From: F.Alt_at_[hidden]
Date: 2011-05-13 14:15:36

Author: franzalt
Date: 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
New Revision: 71924
URL: http://svn.boost.org/trac/boost/changeset/71924

Log:
added first preview version of Boost.Mgl (meta-graph library)
Added:
   sandbox/mgl/
   sandbox/mgl/boost/
   sandbox/mgl/boost/mgl/
   sandbox/mgl/boost/mgl/aux_/
   sandbox/mgl/boost/mgl/aux_/begin_end_impl.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/aux_/breadth_first_search_impl.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/aux_/contains_cycle_impl.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/aux_/depth_first_search_impl.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/aux_/next_prior_impl.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/aux_/topological_sort_impl.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/aux_/utility.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/aux_/vertex.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/begin_end.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/breadth_first_search.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/colors.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/contains_cycle.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/depth_first_search.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/directed_graph.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/edge.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/find.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/graph.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/graph_policies.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/is_graph.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/iterator.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/iterator_policies.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/iterator_tags.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/next_prior.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/row.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/topological_sort.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/undirected_graph.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/v_prop.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/visitor_helpers.hpp (contents, props changed)
   sandbox/mgl/boost/mgl/visitors.hpp (contents, props changed)
   sandbox/mgl/libs/
   sandbox/mgl/libs/mgl/
   sandbox/mgl/libs/mgl/doc/
   sandbox/mgl/libs/mgl/examples/
   sandbox/mgl/libs/mgl/examples/random_graph.cpp (contents, props changed)
   sandbox/mgl/libs/mgl/examples/simple_directed.cpp (contents, props changed)
   sandbox/mgl/libs/mgl/examples/topological_sort.cpp (contents, props changed)
   sandbox/mgl/libs/mgl/examples/visitor.cpp (contents, props changed)
   sandbox/mgl/libs/mgl/test/
   sandbox/mgl/libs/mgl/test/bfs_iteration.cpp (contents, props changed)
   sandbox/mgl/libs/mgl/test/breadth_first_search.cpp (contents, props changed)
   sandbox/mgl/libs/mgl/test/contains_cycle.cpp (contents, props changed)
   sandbox/mgl/libs/mgl/test/depth_first_search.cpp (contents, props changed)
   sandbox/mgl/libs/mgl/test/dfs_iteration.cpp (contents, props changed)
   sandbox/mgl/libs/mgl/test/find_vertex.cpp (contents, props changed)
   sandbox/mgl/libs/mgl/test/generic_graph.cpp (contents, props changed)
   sandbox/mgl/libs/mgl/test/topological_sort.cpp (contents, props changed)
   sandbox/mgl/libs/mgl/test/visitors.cpp (contents, props changed)

Added: sandbox/mgl/boost/mgl/aux_/begin_end_impl.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/aux_/begin_end_impl.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,131 @@
+// 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)
+
+#ifndef BOOST_MGL_AUX_BEGIN_END_IMPL_HPP
+#define BOOST_MGL_AUX_BEGIN_END_IMPL_HPP
+
+#include <boost/mpl/eval_if.hpp>
+#include <boost/mpl/if.hpp>
+#include <boost/mpl/bool.hpp>
+#include <boost/mpl/void.hpp>
+#include <boost/mpl/has_xxx.hpp>
+
+#include <boost/mgl/is_graph.hpp>
+#include <boost/mgl/iterator.hpp>
+#include <boost/mgl/begin_end.hpp>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+namespace aux
+{
+
+//template<typename Graph, typename EndAtStrategy, typename TracePolicy, typename Visitor>
+//struct dfs_begin_type
+//{
+// typedef typename Graph::template dfs_begin<EndAtStrategy, TracePolicy, Visitor>::type type;
+//};
+//
+//template<typename Graph>
+//struct dfs_end_type
+//{
+// typedef typename Graph::end::type type;
+//};
+//
+//BOOST_MPL_HAS_XXX_TRAIT_DEF(dfs_begin_supported)
+//
+//template<typename Tag>
+//struct dfs_begin_impl
+//{
+// template<typename Graph, typename EndAtStrategy, typename TracePolicy, typename Visitor> struct apply
+// {
+// typedef typename ::boost::mpl::eval_if<
+// typename has_dfs_begin_supported<Graph>::type,
+// //is_graph<Graph>,
+// aux::dfs_begin_type<Graph, EndAtStrategy, TracePolicy, Visitor>,
+// ::boost::mpl::void_
+// >::type type;
+// };
+//};
+//
+//template<typename Tag>
+//struct dfs_end_impl
+//{
+// template<typename Graph> struct apply
+// {
+// typedef typename ::boost::mpl::eval_if<
+// typename has_dfs_begin_supported<Graph>::type,
+// aux::dfs_end_type<Graph>,
+// ::boost::mpl::void_
+// >::type type;
+// };
+//};
+
+//template<typename Graph, typename EndAtStrategy, typename TracePolicy, typename Visitor>
+//struct bfs_begin_type
+//{
+// typedef typename Graph::template bfs_begin<EndAtStrategy, TracePolicy, Visitor>::type type;
+//};
+//
+//template<typename Graph>
+//struct bfs_end_type
+//{
+// typedef typename Graph::end::type type;
+//};
+//
+//BOOST_MPL_HAS_XXX_TRAIT_DEF(bfs_begin_supported)
+//
+//template<typename Tag>
+//struct bfs_begin_impl
+//{
+// template<typename Graph, typename EndAtStrategy, typename TracePolicy, typename Visitor> struct apply
+// {
+// typedef typename ::boost::mpl::eval_if<
+// //typename has_bfs_begin_supported<Graph>::type,
+// is_graph<Graph>,
+// aux::bfs_begin_type<Graph, EndAtStrategy, TracePolicy, Visitor>,
+// ::boost::mpl::void_
+// >::type type;
+// };
+//};
+//
+//template<typename Tag>
+//struct bfs_end_impl
+//{
+// template<typename Graph> struct apply
+// {
+// typedef typename ::boost::mpl::eval_if<
+// typename has_bfs_begin_supported<Graph>::type,
+// aux::bfs_end_type<Graph>,
+// ::boost::mpl::void_
+// >::type type;
+// };
+//};
+
+template<typename Graph, typename VertexIterator>
+struct edge_begin_type
+{
+ typedef typename Graph::template edge_begin<VertexIterator>::type type;
+};
+
+struct edge_begin_impl
+{
+ template<typename Graph, typename VertexIterator> struct apply
+ {
+ typedef typename aux::edge_begin_type<Graph, VertexIterator>::type type;
+ };
+};
+
+} // namespace aux
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_AUX_BEGIN_END_IMPL_HPP

Added: sandbox/mgl/boost/mgl/aux_/breadth_first_search_impl.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/aux_/breadth_first_search_impl.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,69 @@
+// 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)
+
+#ifndef BOOST_MGL_BREADTH_FIRST_SEARCH_IMPL_HPP
+#define BOOST_MGL_BREADTH_FIRST_SEARCH_IMPL_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>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+namespace aux
+{
+
+template<class Iterator, class AtEnd = void>
+struct breadth_first_search_impl
+{
+ typedef typename breadth_first_search_impl<
+ typename ::boost::mgl::next<Iterator>::type
+ >::type type;
+};
+
+template<class Iterator>
+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::set0<>,
+ ::boost::mpl::vector0<>
+ > type;
+
+ typedef typename ::boost::mpl::void_ visitor_type;
+ typedef typename ::boost::mpl::void_ visitor_result;
+};
+
+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>
+{
+ typedef bfs_iterator<
+ typename Iterator::graph,
+ typename Iterator::graph::end,
+ 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;
+};
+
+} // namespace aux
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_BREATH_FIRST_SEARCH_IMPL_HPP

Added: sandbox/mgl/boost/mgl/aux_/contains_cycle_impl.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/aux_/contains_cycle_impl.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,57 @@
+// 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)
+
+#ifndef BOOST_MGL_AUX_CONTAINS_CYCLE_IMPL_HPP
+#define BOOST_MGL_AUX_CONTAINS_CYCLE_IMPL_HPP
+
+#include <boost/mgl/next_prior.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/pair.hpp>
+
+#include <boost/type_traits/is_same.hpp>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+namespace aux
+{
+
+BOOST_MPL_HAS_XXX_TRAIT_DEF(examine_edge)
+
+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;
+ };
+};
+
+} // namespace aux
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_AUX_CONTAINS_CYCLE_IMPL_HPP

Added: sandbox/mgl/boost/mgl/aux_/depth_first_search_impl.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/aux_/depth_first_search_impl.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,73 @@
+// 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)
+
+#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/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
+{
+
+namespace mgl
+{
+
+namespace aux
+{
+
+template<class Iterator, class AtEnd = void>
+struct depth_first_search_impl
+{
+ typedef typename depth_first_search_impl<
+ typename ::boost::mgl::next<Iterator>::type
+ >::type type;
+};
+
+template<class Iterator>
+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::set0<>,
+ ::boost::mpl::vector0<>
+ > type;
+
+ typedef typename ::boost::mpl::void_ visitor_type;
+ typedef typename ::boost::mpl::void_ visitor_result;
+};
+
+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>
+{
+ typedef dfs_iterator<
+ typename Iterator::graph,
+ typename Iterator::graph::end,
+ 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;
+};
+
+} // namespace aux
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_DEPTH_FIRST_SEARCH_IMPL_HPP

Added: sandbox/mgl/boost/mgl/aux_/next_prior_impl.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/aux_/next_prior_impl.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,68 @@
+// 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)
+
+#ifndef BOOST_MGL_AUX_NEXT_PRIOR_IMPL_HPP
+#define BOOST_MGL_AUX_NEXT_PRIOR_IMPL_HPP
+
+#include <boost/utility/enable_if.hpp>
+
+#include <boost/type_traits/is_same.hpp>
+
+#include <boost/mgl/iterator_tags.hpp>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+namespace aux
+{
+
+template<class Tag>
+struct next_impl
+{
+ template<class Iterator, class Enable = void> struct apply
+ {
+ // Return void if not supported iterator type is given.
+ typedef ::boost::mpl::void_ type;
+ };
+
+ template<class Iterator>
+ struct apply<Iterator, typename ::boost::enable_if<typename ::boost::is_same<typename Iterator::category, dfs_iterator_tag> >::type >
+ {
+ typedef typename Iterator::graph::template dfs_next<Iterator>::type type;
+ };
+
+ template<class Iterator>
+ struct apply<Iterator, typename ::boost::enable_if<typename ::boost::is_same<typename Iterator::category, bfs_iterator_tag> >::type >
+ {
+ typedef typename Iterator::graph::template bfs_next<Iterator>::type type;
+ };
+};
+
+template<class Tag>
+struct prior_impl
+{
+ //! @todo Implement me!
+};
+
+template<class Tag>
+struct edge_next_impl
+{
+ template<typename Iterator> struct apply
+ {
+ typedef typename Iterator::graph::template edge_next<Iterator>::type type;
+ };
+};
+
+} // namespace aux
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_AUX_NEXT_PRIOR_IMPL_HPP

Added: sandbox/mgl/boost/mgl/aux_/topological_sort_impl.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/aux_/topological_sort_impl.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,162 @@
+// 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)
+
+#ifndef BOOST_MGL_TOPOLOGICAL_SORT_IMPL_HPP
+#define BOOST_MGL_TOPOLOGICAL_SORT_IMPL_HPP
+
+#include <boost/mpl/has_xxx.hpp>
+#include <boost/mpl/map.hpp>
+#include <boost/mpl/insert.hpp>
+#include <boost/mpl/pair.hpp>
+#include <boost/mpl/eval_if.hpp>
+#include <boost/mpl/if.hpp>
+#include <boost/mpl/has_key.hpp>
+#include <boost/mpl/at.hpp>
+#include <boost/mpl/erase_key.hpp>
+#include <boost/mpl/push_back.hpp>
+#include <boost/mpl/empty.hpp>
+#include <boost/mpl/contains.hpp>
+
+#include <boost/mgl/edge.hpp>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+namespace aux
+{
+
+BOOST_MPL_HAS_XXX_TRAIT_DEF(examine_edge)
+
+struct predecessor_edge_builder
+{
+ typedef ::boost::mpl::true_ examine_edge;
+
+ struct on_init
+ {
+ typedef ::boost::mpl::map0<> type;
+ };
+
+ template<typename Edge, 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,
+ T,
+ typename ::boost::mpl::insert<
+ T,
+ ::boost::mpl::pair<
+ typename ::boost::mpl::first<Edge>::type,
+ ::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,
+ ::boost::mpl::vector0<>
+ >::type bucket;
+
+ typedef typename ::boost::mpl::push_back<
+ bucket,
+ typename ::boost::mpl::first<Edge>::type
+ >::type new_bucket;
+
+ typedef typename ::boost::mpl::erase_key<
+ T_,
+ typename ::boost::mpl::second<Edge>::type
+ >::type T__;
+
+ typedef typename ::boost::mpl::insert<
+ T__,
+ ::boost::mpl::pair<
+ typename ::boost::mpl::second<Edge>::type,
+ new_bucket
+ >
+ >::type type;
+ };
+};
+
+template<typename Vector, typename ExcludedElements>
+struct build_predecessors : ::boost::mpl::fold<
+ Vector,
+ ::boost::mpl::vector0<>,
+ ::boost::mpl::if_<
+ ::boost::mpl::contains<
+ ExcludedElements,
+ ::boost::mpl::placeholders::_2
+ >,
+ ::boost::mpl::placeholders::_1,
+ ::boost::mpl::push_back<
+ ::boost::mpl::placeholders::_1,
+ ::boost::mpl::placeholders::_2
+ >
+ >
+ >
+{};
+
+template<class Graph, class Predecessors, class Result>
+struct topological_sort_impl
+{
+ // find empty basket and add them to the result vector
+ typedef typename ::boost::mpl::fold<
+ Predecessors,
+ Result,
+ ::boost::mpl::if_<
+ ::boost::mpl::empty<
+ ::boost::mpl::second< ::boost::mpl::placeholders::_2>
+ >,
+ ::boost::mpl::push_back<
+ ::boost::mpl::placeholders::_1,
+ ::boost::mpl::first< ::boost::mpl::placeholders::_2>
+ >,
+ ::boost::mpl::placeholders::_1
+ >
+ >::type result;
+
+ // delete the empty baskets
+ typedef typename ::boost::mpl::fold<
+ result,
+ Predecessors,
+ ::boost::mpl::erase_key<
+ ::boost::mpl::placeholders::_1,
+ ::boost::mpl::placeholders::_2
+ >
+ >::type predecessors;
+
+ // build a new predecessor map
+ typedef typename ::boost::mpl::fold<
+ predecessors,
+ ::boost::mpl::map0<>,
+ ::boost::mpl::insert<
+ ::boost::mpl::placeholders::_1,
+ ::boost::mpl::pair<
+ ::boost::mpl::first< ::boost::mpl::placeholders::_2>,
+ build_predecessors<
+ ::boost::mpl::second< ::boost::mpl::placeholders::_2>,
+ result
+ >
+ >
+ >
+ >::type new_predecessors;
+
+ typedef typename ::boost::mpl::eval_if<
+ typename ::boost::mpl::empty<new_predecessors>,
+ result,
+ topological_sort_impl<Graph, new_predecessors, result>
+ >::type type;
+};
+
+} // namespace aux
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_TOPOLOGICAL_SORT_IMPL_HPP

Added: sandbox/mgl/boost/mgl/aux_/utility.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/aux_/utility.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,68 @@
+// 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)
+
+#ifndef BOOST_MGL_AUX_UTILITY_HPP
+#define BOOST_MGL_AUX_UTILITY_HPP
+
+#include <boost/mpl/if.hpp>
+#include <boost/mpl/has_key.hpp>
+#include <boost/mpl/placeholders.hpp>
+#include <boost/mpl/insert.hpp>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+namespace aux
+{
+
+template<class Row>
+struct row_start_vertex
+{
+ typedef typename Row::vertex type;
+};
+
+template<class Row>
+struct row_adjacency_vertices
+{
+ typedef typename Row::adjacency_vertices type;
+};
+
+template<class Vertex>
+struct get_node_id
+{
+ typedef typename Vertex::id type;
+
+ enum { value = type::value };
+};
+
+template<class T>
+struct wrap
+{};
+
+template<class Set, class Vec>
+struct vec_to_set
+{
+ typedef typename ::boost::mpl::fold<
+ Vec,
+ Set,
+ ::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 type;
+};
+
+} // namespace aux
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_AUX_UTILITY_HPP

Added: sandbox/mgl/boost/mgl/aux_/vertex.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/aux_/vertex.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,46 @@
+// 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)
+
+#ifndef BOOST_MGL_AUX_VERTEX_HPP
+#define BOOST_MGL_AUX_VERTEX_HPP
+
+//#include <boost/mpl/int.hpp>
+
+#include <boost/mgl/aux_/utility.hpp>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+namespace aux
+{
+
+template<class Type, class Neighbors/*, int Id*/>
+struct vertex
+{
+ typedef Type type;
+ typedef Neighbors neighbors;
+ //typedef ::boost::mpl::int_<Id> id;
+};
+
+template<class Row>
+struct row2vertex
+{
+ typedef vertex<
+ typename aux::row_start_vertex<Row>::type,
+ typename aux::row_adjacency_vertices<Row>::type
+ > type;
+};
+
+} // namespace aux
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_AUX_VERTEX_HPP

Added: sandbox/mgl/boost/mgl/begin_end.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/begin_end.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,100 @@
+// 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)
+
+#ifndef BOOST_MGL_BEGIN_END_HPP
+#define BOOST_MGL_BEGIN_END_HPP
+
+#include <boost/mpl/has_xxx.hpp>
+
+#include <boost/utility/enable_if.hpp>
+
+#include <boost/mgl/aux_/begin_end_impl.hpp>
+#include <boost/mgl/iterator_policies.hpp>
+#include <boost/mgl/visitors.hpp>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+BOOST_MPL_HAS_XXX_TRAIT_DEF(dfs_begin_supported)
+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>
+struct dfs_begin
+{
+ 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>
+{
+ typedef typename Graph::template dfs_begin<EndAtStrategy, TracePolicy, Visitor>::type type;
+};
+
+/// \brief Get a DFS iterator to the end of a graph
+/// \param Graph Graph where the iteration should be performed
+template<class Graph, class Enable = void>
+struct dfs_end
+{
+ 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;
+};
+
+/// \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>
+struct bfs_begin
+{
+ 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>
+{
+ typedef typename Graph::template bfs_begin<EndAtStrategy, TracePolicy, Visitor>::type type;
+};
+
+/// \brief Get a BFS iterator to the end of a graph
+/// \param Graph Graph where the iteration should be performed
+template<class Graph, class Enable = void>
+struct bfs_end
+{
+ 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;
+};
+
+//! @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;
+};
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_BEGIN_END_HPP

Added: sandbox/mgl/boost/mgl/breadth_first_search.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/breadth_first_search.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,57 @@
+// 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)
+
+#ifndef BOOST_MGL_BREADTH_FIRST_SEARCH_HPP
+#define BOOST_MGL_BREADTH_FIRST_SEARCH_HPP
+
+#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/aux_/breadth_first_search_impl.hpp>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+/// \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>
+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 aux::template breadth_first_search_impl<iter>::type type;
+};
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_BREATH_FIRST_SEARCH_HPP

Added: sandbox/mgl/boost/mgl/colors.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/colors.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,55 @@
+// 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)
+
+#ifndef BOOST_MGL_COLORS_HPP
+#define BOOST_MGL_COLORS_HPP
+
+#include <boost/mpl/erase_key.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
+{
+
+namespace mgl
+{
+
+struct white {};
+struct gray {};
+struct black {};
+
+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;
+};
+
+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;
+};
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_COLORS_HPP

Added: sandbox/mgl/boost/mgl/contains_cycle.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/contains_cycle.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,41 @@
+// 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)
+
+#ifndef BOOST_MGL_CONTAINS_CYCLE_HPP
+#define BOOST_MGL_CONTAINS_CYCLE_HPP
+
+#include <boost/mpl/vector.hpp>
+
+#include <boost/mgl/begin_end.hpp>
+#include <boost/mgl/depth_first_search.hpp>
+#include <boost/mgl/iterator_policies.hpp>
+
+#include <boost/mgl/aux_/contains_cycle_impl.hpp>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+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 aux::template depth_first_search_impl<iter>::type::visitor_result type;
+};
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_CONTAINS_CYCLE_HPP

Added: sandbox/mgl/boost/mgl/depth_first_search.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/depth_first_search.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,57 @@
+// 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)
+
+#ifndef BOOST_MGL_DEPTH_FIRST_SEARCH_HPP
+#define BOOST_MGL_DEPTH_FIRST_SEARCH_HPP
+
+#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/aux_/depth_first_search_impl.hpp>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+/// \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>
+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 aux::template depth_first_search_impl<iter>::type type;
+};
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_DEPTH_FIRST_SEARCH_HPP

Added: sandbox/mgl/boost/mgl/directed_graph.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/directed_graph.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,26 @@
+// 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)
+
+#ifndef BOOST_MGL_DIRECTED_GRAPH_HPP
+#define BOOST_MGL_DIRECTED_GRAPH_HPP
+
+#include <boost/mgl/graph.hpp>
+#include <boost/mgl/graph_policies.hpp>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+template<class Derived>
+class directed_graph : public graph<Derived, VmapDirectedGraph> {};
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_DIRECTED_GRAPH_HPP

Added: sandbox/mgl/boost/mgl/edge.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/edge.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,56 @@
+// 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)
+
+#ifndef BOOST_MGL_EDGE_HPP
+#define BOOST_MGL_EDGE_HPP
+
+#include <boost/mpl/vector.hpp>
+#include <boost/mpl/int.hpp>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+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;
+};
+
+template<class Edge>
+struct edge_begin_vertex
+{
+ typedef typename Edge::vertex_from type;
+};
+
+template<class Edge>
+struct edge_end_vertex
+{
+ typedef typename Edge::vertex_to type;
+};
+
+template<class Edge>
+struct edge_weight
+{
+ typedef typename Edge::weight type;
+};
+
+template<class Edge>
+struct edge_properties
+{
+ typedef typename Edge::properties type;
+};
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_EDGE_HPP

Added: sandbox/mgl/boost/mgl/find.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/find.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,67 @@
+// 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)
+
+#ifndef BOOST_MGL_FIND_HPP
+#define BOOST_MGL_FIND_HPP
+
+#include <boost/mpl/has_xxx.hpp>
+
+#include <boost/utility/enable_if.hpp>
+
+#include <boost/mgl/iterator_policies.hpp>
+#include <boost/mgl/visitors.hpp>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+BOOST_MPL_HAS_XXX_TRAIT_DEF(dfs_find_supported)
+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>
+struct dfs_find
+{
+ 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>
+{
+ typedef typename Graph::template dfs_find<Vertex, EndAtStrategy, TracePolicy, 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>
+struct bfs_find
+{
+ 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>
+{
+ typedef typename Graph::template bfs_find<Vertex, EndAtStrategy, TracePolicy, Visitor>::type type;
+};
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_FIND_HPP

Added: sandbox/mgl/boost/mgl/graph.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/graph.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,1198 @@
+// 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)
+
+#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/at.hpp>
+#include <boost/mpl/find.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/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/eval_if.hpp>
+#include <boost/mpl/joint_view.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/utility/enable_if.hpp>
+#include <boost/type_traits/is_same.hpp>
+#include <boost/type_traits/is_void.hpp>
+
+#include <boost/mgl/graph_policies.hpp>
+#include <boost/mgl/row.hpp>
+#include <boost/mgl/edge.hpp>
+#include <boost/mgl/v_prop.hpp>
+#include <boost/mgl/iterator.hpp>
+#include <boost/mgl/visitor_helpers.hpp>
+#include <boost/mgl/colors.hpp>
+#include <boost/mgl/aux_/vertex.hpp>
+#include <boost/mgl/aux_/utility.hpp>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+template<
+ class Derived,
+ class VmapGenerator // policy class to build the map of vertices
+>
+class graph
+{
+public:
+ 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;
+ };
+
+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;
+ };
+};
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_GRAPH_HPP

Added: sandbox/mgl/boost/mgl/graph_policies.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/graph_policies.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,174 @@
+// 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)
+
+#ifndef BOOST_MGL_GRAPH_POLICIES_HPP
+#define BOOST_MGL_GRAPH_POLICIES_HPP
+
+#include <boost/mpl/fold.hpp>
+#include <boost/mpl/map.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>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+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;
+ };
+};
+
+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;
+ };
+
+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;
+ };
+};
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_GRAPH_POLICIES_HPP

Added: sandbox/mgl/boost/mgl/is_graph.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/is_graph.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,40 @@
+// 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)
+
+#ifndef BOOST_MGL_IS_GRAPH_HPP
+#define BOOST_MGL_IS_GRAPH_HPP
+
+#include <boost/mgl/directed_graph.hpp>
+
+#include <boost/type_traits/is_base_of.hpp>
+#include <boost/type_traits/detail/bool_trait_def.hpp>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+namespace detail
+{
+
+template<typename T>
+struct is_graph_impl :
+ is_base_of<directed_graph<T>, T>::type
+{
+};
+
+} // namespace detail
+
+BOOST_TT_AUX_BOOL_TRAIT_DEF1(is_graph, T, ::boost::mgl::detail::is_graph_impl<T>::value)
+
+} // namespace mgl
+
+} // namespace boost
+
+#include <boost/type_traits/detail/bool_trait_undef.hpp>
+
+#endif // BOOST_MGL_IS_GRAPH_HPP

Added: sandbox/mgl/boost/mgl/iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/iterator.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,112 @@
+// 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)
+
+#ifndef BOOST_MGL_ITERATOR_HPP
+#define BOOST_MGL_ITERATOR_HPP
+
+#include <boost/mpl/at.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/next_prior.hpp>
+#include <boost/mgl/iterator_tags.hpp>
+#include <boost/mgl/iterator_policies.hpp>
+#include <boost/mgl/visitors.hpp>
+#include <boost/mgl/colors.hpp>
+
+namespace boost
+{
+
+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_>
+struct dfs_iterator
+{
+ typedef Graph graph;
+ typedef Vertex vertex;
+
+ typedef ColorMap color_map;
+
+ typedef TraversalStack traversal_stack;
+
+ typedef ::boost::mgl::dfs_iterator_tag category;
+
+ typedef EndAtStrategy end_at_strategy;
+
+ typedef TracePolicy trace_policy;
+ typedef Trace vertex_trace;
+
+ 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_>
+struct bfs_iterator
+{
+ typedef Graph graph;
+ typedef Vertex vertex;
+
+ typedef ColorMap color_map;
+
+ typedef TraversalStack traversal_stack;
+
+ typedef ::boost::mgl::bfs_iterator_tag category;
+
+ typedef EndAtStrategy end_at_strategy;
+
+ typedef TracePolicy trace_policy;
+ typedef Trace vertex_trace;
+
+ 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 Vertex source_vertex;
+ typedef TargetVertex target_vertex;
+
+ typedef EdgeIndex edge_index;
+};
+
+/// \brief Dereference the iterator
+/// \param Iterator Iterator to be dereferences
+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;
+};
+
+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> >
+{
+ typedef Vertex type;
+};
+
+template<class Graph, class Vertex, class TargetVertex, class EdgeIndex>
+struct deref<edge_iterator<Graph, Vertex, TargetVertex, EdgeIndex> >
+{
+ typedef TargetVertex type;
+};
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_ITERATOR_HPP

Added: sandbox/mgl/boost/mgl/iterator_policies.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/iterator_policies.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,52 @@
+// 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)
+
+#ifndef BOOST_MGL_ITERATOR_POLICIES_HPP
+#define BOOST_MGL_ITERATOR_POLICIES_HPP
+
+#include <boost/mpl/vector.hpp>
+
+#include <boost/typeof/typeof.hpp>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+// policies for the DFS iterator
+struct EndWhenNoVerticesFound {};
+struct EndAtEndOfGraph {};
+
+// trace policies
+struct NoTrace
+{
+ typedef ::boost::mpl::void_ container_type;
+
+ template<typename Vertex, typename Container>
+ struct apply
+ {
+ typedef ::boost::mpl::void_ type;
+ };
+};
+
+template<typename TraceVector>
+struct RecordTrace
+{
+ typedef TraceVector container_type;
+
+ template<typename Vertex, typename Container>
+ struct apply
+ {
+ typedef typename ::boost::mpl::push_back<Container, Vertex>::type type;
+ };
+};
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_ITERATOR_POLICIES_HPP

Added: sandbox/mgl/boost/mgl/iterator_tags.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/iterator_tags.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,25 @@
+// 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)
+
+#ifndef BOOST_MGL_ITERATOR_TAGS_HPP
+#define BOOST_MGL_ITERATOR_TAGS_HPP
+
+#include <boost/mpl/int.hpp>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+struct dfs_iterator_tag {};
+struct bfs_iterator_tag {};
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_ITERATOR_TAGS_HPP

Added: sandbox/mgl/boost/mgl/next_prior.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/next_prior.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,53 @@
+// 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)
+
+#ifndef BOOST_MGL_NEXT_PRIOR_HPP
+#define BOOST_MGL_NEXT_PRIOR_HPP
+
+#include <boost/mgl/aux_/next_prior_impl.hpp>
+
+#include <boost/utility/enable_if.hpp>
+#include <boost/type_traits/is_void.hpp>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+/// \brief Move iterator to the next vertex
+/// \param 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;
+};
+
+template<class Iterator>
+struct next<Iterator, typename ::boost::enable_if< ::boost::is_same<Iterator, ::boost::mpl::void_> >::type>
+{
+ typedef ::boost::mpl::void_ type;
+};
+
+/// \brief Move iterator to the previous vertex
+/// \param Iterator Iterator that should be moved
+template<class Iterator>
+struct prior
+{
+ 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;
+};
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_NEXT_PRIOR_HPP

Added: sandbox/mgl/boost/mgl/row.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/row.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,27 @@
+// 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)
+
+#ifndef BOOST_MGL_ROW_HPP
+#define BOOST_MGL_ROW_HPP
+
+namespace boost
+{
+
+namespace mgl
+{
+
+template<class Vertex, class VertexList>
+struct row
+{
+ typedef Vertex vertex;
+ typedef VertexList adjacency_vertices;
+};
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_ROW_HPP

Added: sandbox/mgl/boost/mgl/topological_sort.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/topological_sort.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,47 @@
+// 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)
+
+#ifndef BOOST_MGL_TOPOLOGICAL_SORT_HPP
+#define BOOST_MGL_TOPOLOGICAL_SORT_HPP
+
+#include <boost/mpl/vector.hpp>
+#include <boost/mpl/void.hpp>
+
+#include <boost/mgl/depth_first_search.hpp>
+#include <boost/mgl/visitors.hpp>
+
+#include <boost/mgl/aux_/topological_sort_impl.hpp>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+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;
+
+ BOOST_MPL_ASSERT_NOT(( ::boost::mpl::empty<type> ));
+};
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_TOPOLOGICAL_SORT_HPP

Added: sandbox/mgl/boost/mgl/undirected_graph.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/undirected_graph.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,26 @@
+// 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)
+
+#ifndef BOOST_MGL_UNDIRECTED_GRAPH_HPP
+#define BOOST_MGL_DIRECTED_GRAPH_HPP
+
+#include <boost/mgl/graph.hpp>
+#include <boost/mgl/graph_policies.hpp>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+template<class Derived>
+class undirected_graph : public graph<Derived, VmapUndirectedGraph> {};
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_DIRECTED_GRAPH_HPP

Added: sandbox/mgl/boost/mgl/v_prop.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/v_prop.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,41 @@
+// 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)
+
+#ifndef BOOST_MGL_V_PROP_HPP
+#define BOOST_MGL_V_PROP_HPP
+
+#include <boost/mpl/empty_base.hpp>
+
+namespace boost
+{
+
+namespace mgl
+{
+
+template<class T, class Property = ::boost::mpl::empty_base>
+struct v_prop
+{
+ typedef T vertex;
+ typedef Property property;
+};
+
+template<class T>
+struct v_prop_vertex
+{
+ typedef typename T::vertex type;
+};
+
+template<class T>
+struct v_prop_property
+{
+ typedef typename T::property type;
+};
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_V_PROP_HPP

Added: sandbox/mgl/boost/mgl/visitor_helpers.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/visitor_helpers.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,42 @@
+// 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)
+
+#ifndef BOOST_MGL_VISITOR_HELPERS_HPP
+#define BOOST_MGL_VISITOR_HELPERS_HPP
+
+namespace boost
+{
+
+namespace mgl
+{
+
+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;
+};
+
+template<class Visitor, class Vertex1, class Vertex2, 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;
+};
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_VISITOR_HELPERS_HPP

Added: sandbox/mgl/boost/mgl/visitors.hpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/boost/mgl/visitors.hpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,108 @@
+// 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)
+
+#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/int.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
+{
+
+namespace mgl
+{
+
+BOOST_MPL_HAS_XXX_TRAIT_DEF(discover_vertex)
+BOOST_MPL_HAS_XXX_TRAIT_DEF(examine_edge)
+
+struct null_visitor
+{
+ struct on_init
+ {
+ typedef ::boost::mpl::void_ type;
+ };
+};
+
+struct vertex_trace_visitor
+{
+ 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 vertex_counter_visitor
+{
+ 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 edge_trace_visitor
+{
+ 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 edge_counter_visitor
+{
+ 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;
+ };
+};
+
+} // namespace mgl
+
+} // namespace boost
+
+#endif // BOOST_MGL_VISITORS_HPP

Added: sandbox/mgl/libs/mgl/examples/random_graph.cpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/libs/mgl/examples/random_graph.cpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,223 @@
+// 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)
+
+//! @todo Add your include statements here.
+
+#include <iostream>
+#include <typeinfo>
+
+#include <boost/typeof/typeof.hpp>
+#include <boost/mpl/vector.hpp>
+#include <boost/mpl/equal.hpp>
+#include <boost/mpl/assert.hpp>
+
+#include <boost/mgl/directed_graph.hpp>
+#include <boost/mgl/depth_first_search.hpp>
+
+using namespace boost;
+using namespace boost::mgl;
+
+namespace mgl = boost::mgl;
+
+// vertices
+struct v0 {};
+struct v1 {};
+struct v2 {};
+struct v3 {};
+struct v4 {};
+struct v5 {};
+struct v6 {};
+struct v7 {};
+struct v8 {};
+struct v9 {};
+
+class random_graph : public directed_graph<random_graph>
+{
+public:
+ // vertex properties
+ //! @todo Add your vertex properties here.
+
+ // edge properties
+ //! @todo Add your edge properties here.
+
+ // adjacency list of the graph
+ struct adjacency_list : mpl::vector10<
+ // Node Adjacency
+ // from nodes
+ // +------+--------------------------------------------+
+ row < v0 , mpl::vector0<> >,
+ row < v1 , mpl::vector2<v6, v6> >,
+ row < v2 , mpl::vector1<v8> >,
+ row < v3 , mpl::vector0<> >,
+ row < v4 , mpl::vector0<> >,
+ row < v5 , mpl::vector0<> >,
+ row < v6 , mpl::vector3<v7, v5, v3> >,
+ row < v7 , mpl::vector1<v3> >,
+ row < v8 , mpl::vector2<v0, v2> >,
+ row < v9 , mpl::vector1<v5> >
+ // +------+--------------------------------------------+
+ > {};
+
+ // vertex properties
+ //! @todo Fill the structure with your properties from above.
+ struct vertex_property_list : mpl::vector10<
+ // Node Properties
+ // +------+-----------------------------------------+
+ v_prop < v0 , mpl::vector0<> >,
+ v_prop < v1 , mpl::vector0<> >,
+ v_prop < v2 , mpl::vector0<> >,
+ v_prop < v3 , mpl::vector0<> >,
+ v_prop < v4 , mpl::vector0<> >,
+ v_prop < v5 , mpl::vector0<> >,
+ v_prop < v6 , mpl::vector0<> >,
+ v_prop < v7 , mpl::vector0<> >,
+ v_prop < v8 , mpl::vector0<> >,
+ v_prop < v9 , mpl::vector0<> >
+ // +------+-----------------------------------------+
+ > {};
+
+ // edge properties and weights
+ //! @todo Fill the structure with your properties from above and your own weights.
+ struct edge_list : mpl::vector10<
+ // Node Node Weight Properties
+ // from to
+ // +------+------+--------+---------------------------+
+ edge < v2 , v8 , 3 , mpl::vector0<> >,
+ // +------+------+--------+---------------------------+
+ edge < v1 , v6 , 3 , mpl::vector0<> >,
+ // +------+------+--------+---------------------------+
+ edge < v6 , v7 , 4 , mpl::vector0<> >,
+ // +------+------+--------+---------------------------+
+ edge < v9 , v5 , 8 , mpl::vector0<> >,
+ // +------+------+--------+---------------------------+
+ edge < v8 , v0 , 3 , mpl::vector0<> >,
+ // +------+------+--------+---------------------------+
+ edge < v6 , v5 , 2 , mpl::vector0<> >,
+ // +------+------+--------+---------------------------+
+ edge < v1 , v6 , 9 , mpl::vector0<> >,
+ // +------+------+--------+---------------------------+
+ edge < v8 , v2 , 10 , mpl::vector0<> >,
+ // +------+------+--------+---------------------------+
+ edge < v6 , v3 , 1 , mpl::vector0<> >,
+ // +------+------+--------+---------------------------+
+ edge < v7 , v3 , 5 , mpl::vector0<> >
+ // +------+------+--------+---------------------------+
+ > {};
+};
+
+// test vertices (in/out) and edges (in/out) of 'v0'
+typedef random_graph::in_vertices<v0>::type in_vertices_v0;
+typedef random_graph::in_edges<v0>::type in_edges_v0;
+typedef random_graph::out_vertices<v0>::type out_vertices_v0;
+typedef random_graph::out_edges<v0>::type out_edges_v0;
+BOOST_MPL_ASSERT((mpl::equal<in_vertices_v0, mpl::vector1<v8> >::type));
+BOOST_MPL_ASSERT((mpl::equal<in_edges_v0, mpl::vector1<edge<v8, v0, 3, mpl::vector0<> > > >::type));
+BOOST_MPL_ASSERT((mpl::equal<out_vertices_v0, mpl::vector0<> >::type));
+BOOST_MPL_ASSERT((mpl::equal<out_edges_v0, mpl::vector0<> >::type));
+
+// test vertices (in/out) and edges (in/out) of 'v1'
+typedef random_graph::in_vertices<v1>::type in_vertices_v1;
+typedef random_graph::in_edges<v1>::type in_edges_v1;
+typedef random_graph::out_vertices<v1>::type out_vertices_v1;
+typedef random_graph::out_edges<v1>::type out_edges_v1;
+BOOST_MPL_ASSERT((mpl::equal<in_vertices_v1, mpl::vector0<> >::type));
+BOOST_MPL_ASSERT((mpl::equal<in_edges_v1, mpl::vector0<> >::type));
+BOOST_MPL_ASSERT((mpl::equal<out_vertices_v1, mpl::vector2<v6, v6> >::type));
+BOOST_MPL_ASSERT((mpl::equal<out_edges_v1, mpl::vector2<edge<v1, v6, 3, mpl::vector0<> >, edge<v1, v6, 9, mpl::vector0<> > > >::type));
+
+// test vertices (in/out) and edges (in/out) of 'v2'
+typedef random_graph::in_vertices<v2>::type in_vertices_v2;
+typedef random_graph::in_edges<v2>::type in_edges_v2;
+typedef random_graph::out_vertices<v2>::type out_vertices_v2;
+typedef random_graph::out_edges<v2>::type out_edges_v2;
+BOOST_MPL_ASSERT((mpl::equal<in_vertices_v2, mpl::vector1<v8> >::type));
+BOOST_MPL_ASSERT((mpl::equal<in_edges_v2, mpl::vector1<edge<v8, v2, 10, mpl::vector0<> > > >::type));
+BOOST_MPL_ASSERT((mpl::equal<out_vertices_v2, mpl::vector1<v8> >::type));
+BOOST_MPL_ASSERT((mpl::equal<out_edges_v2, mpl::vector1<edge<v2, v8, 3, mpl::vector0<> > > >::type));
+
+// test vertices (in/out) and edges (in/out) of 'v3'
+typedef random_graph::in_vertices<v3>::type in_vertices_v3;
+typedef random_graph::in_edges<v3>::type in_edges_v3;
+typedef random_graph::out_vertices<v3>::type out_vertices_v3;
+typedef random_graph::out_edges<v3>::type out_edges_v3;
+BOOST_MPL_ASSERT((mpl::equal<in_vertices_v3, mpl::vector2<v6, v7> >::type));
+BOOST_MPL_ASSERT((mpl::equal<in_edges_v3, mpl::vector2<edge<v6, v3, 1, mpl::vector0<> >, edge<v7, v3, 5, mpl::vector0<> > > >::type));
+BOOST_MPL_ASSERT((mpl::equal<out_vertices_v3, mpl::vector0<> >::type));
+BOOST_MPL_ASSERT((mpl::equal<out_edges_v3, mpl::vector0<> >::type));
+
+// test vertices (in/out) and edges (in/out) of 'v4'
+typedef random_graph::in_vertices<v4>::type in_vertices_v4;
+typedef random_graph::in_edges<v4>::type in_edges_v4;
+typedef random_graph::out_vertices<v4>::type out_vertices_v4;
+typedef random_graph::out_edges<v4>::type out_edges_v4;
+BOOST_MPL_ASSERT((mpl::equal<in_vertices_v4, mpl::vector0<> >::type));
+BOOST_MPL_ASSERT((mpl::equal<in_edges_v4, mpl::vector0<> >::type));
+BOOST_MPL_ASSERT((mpl::equal<out_vertices_v4, mpl::vector0<> >::type));
+BOOST_MPL_ASSERT((mpl::equal<out_edges_v4, mpl::vector0<> >::type));
+
+// test vertices (in/out) and edges (in/out) of 'v5'
+typedef random_graph::in_vertices<v5>::type in_vertices_v5;
+typedef random_graph::in_edges<v5>::type in_edges_v5;
+typedef random_graph::out_vertices<v5>::type out_vertices_v5;
+typedef random_graph::out_edges<v5>::type out_edges_v5;
+BOOST_MPL_ASSERT((mpl::equal<in_vertices_v5, mpl::vector2<v9, v6> >::type));
+BOOST_MPL_ASSERT((mpl::equal<in_edges_v5, mpl::vector2<edge<v9, v5, 8, mpl::vector0<> >, edge<v6, v5, 2, mpl::vector0<> > > >::type));
+BOOST_MPL_ASSERT((mpl::equal<out_vertices_v5, mpl::vector0<> >::type));
+BOOST_MPL_ASSERT((mpl::equal<out_edges_v5, mpl::vector0<> >::type));
+
+// test vertices (in/out) and edges (in/out) of 'v6'
+typedef random_graph::in_vertices<v6>::type in_vertices_v6;
+typedef random_graph::in_edges<v6>::type in_edges_v6;
+typedef random_graph::out_vertices<v6>::type out_vertices_v6;
+typedef random_graph::out_edges<v6>::type out_edges_v6;
+BOOST_MPL_ASSERT((mpl::equal<in_vertices_v6, mpl::vector2<v1, v1> >::type));
+BOOST_MPL_ASSERT((mpl::equal<in_edges_v6, mpl::vector2<edge<v1, v6, 3, mpl::vector0<> >, edge<v1, v6, 9, mpl::vector0<> > > >::type));
+BOOST_MPL_ASSERT((mpl::equal<out_vertices_v6, mpl::vector3<v7, v5, v3> >::type));
+BOOST_MPL_ASSERT((mpl::equal<out_edges_v6, mpl::vector3<edge<v6, v7, 4, mpl::vector0<> >, edge<v6, v5, 2, mpl::vector0<> >, edge<v6, v3, 1, mpl::vector0<> > > >::type));
+
+// test vertices (in/out) and edges (in/out) of 'v7'
+typedef random_graph::in_vertices<v7>::type in_vertices_v7;
+typedef random_graph::in_edges<v7>::type in_edges_v7;
+typedef random_graph::out_vertices<v7>::type out_vertices_v7;
+typedef random_graph::out_edges<v7>::type out_edges_v7;
+BOOST_MPL_ASSERT((mpl::equal<in_vertices_v7, mpl::vector1<v6> >::type));
+BOOST_MPL_ASSERT((mpl::equal<in_edges_v7, mpl::vector1<edge<v6, v7, 4, mpl::vector0<> > > >::type));
+BOOST_MPL_ASSERT((mpl::equal<out_vertices_v7, mpl::vector1<v3> >::type));
+BOOST_MPL_ASSERT((mpl::equal<out_edges_v7, mpl::vector1<edge<v7, v3, 5, mpl::vector0<> > > >::type));
+
+// test vertices (in/out) and edges (in/out) of 'v8'
+typedef random_graph::in_vertices<v8>::type in_vertices_v8;
+typedef random_graph::in_edges<v8>::type in_edges_v8;
+typedef random_graph::out_vertices<v8>::type out_vertices_v8;
+typedef random_graph::out_edges<v8>::type out_edges_v8;
+BOOST_MPL_ASSERT((mpl::equal<in_vertices_v8, mpl::vector1<v2> >::type));
+BOOST_MPL_ASSERT((mpl::equal<in_edges_v8, mpl::vector1<edge<v2, v8, 3, mpl::vector0<> > > >::type));
+BOOST_MPL_ASSERT((mpl::equal<out_vertices_v8, mpl::vector2<v0, v2> >::type));
+BOOST_MPL_ASSERT((mpl::equal<out_edges_v8, mpl::vector2<edge<v8, v0, 3, mpl::vector0<> >, edge<v8, v2, 10, mpl::vector0<> > > >::type));
+
+// test vertices (in/out) and edges (in/out) of 'v9'
+typedef random_graph::in_vertices<v9>::type in_vertices_v9;
+typedef random_graph::in_edges<v9>::type in_edges_v9;
+typedef random_graph::out_vertices<v9>::type out_vertices_v9;
+typedef random_graph::out_edges<v9>::type out_edges_v9;
+BOOST_MPL_ASSERT((mpl::equal<in_vertices_v9, mpl::vector0<> >::type));
+BOOST_MPL_ASSERT((mpl::equal<in_edges_v9, mpl::vector0<> >::type));
+BOOST_MPL_ASSERT((mpl::equal<out_vertices_v9, mpl::vector1<v5> >::type));
+BOOST_MPL_ASSERT((mpl::equal<out_edges_v9, mpl::vector1<edge<v9, v5, 8, mpl::vector0<> > > >::type));
+
+int main(int argc, char * argv[])
+{
+ // perform a DFS search
+ typedef depth_first_search<random_graph>::type::vertex_trace dfs;
+
+ // get type of the DFS result
+ typedef BOOST_TYPEOF(dfs()) dfs_t;
+
+ // print vertices with DFS result to stdout
+ std::cout << typeid(dfs_t).name() << std::endl;
+
+ return 0;
+}

Added: sandbox/mgl/libs/mgl/examples/simple_directed.cpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/libs/mgl/examples/simple_directed.cpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,683 @@
+// 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 <iostream>
+#include <typeinfo>
+
+#include <boost/mgl/directed_graph.hpp>
+#include <boost/mgl/iterator.hpp>
+#include <boost/mgl/begin_end.hpp>
+#include <boost/mgl/next_prior.hpp>
+
+#include <boost/mpl/vector.hpp>
+#include <boost/mpl/set.hpp>
+
+#include <boost/mpl/assert.hpp>
+#include <boost/mpl/equal.hpp>
+#include <boost/mpl/has_key.hpp>
+#include <boost/type_traits/is_same.hpp>
+
+#include <boost/typeof/typeof.hpp>
+
+using namespace boost;
+using namespace boost::mgl;
+
+namespace mgl = boost::mgl;
+
+class simple_directed : public directed_graph<simple_directed>
+{
+public:
+ // vertices
+ struct a {};
+ struct b {};
+ struct c {};
+ struct d {};
+ struct e {};
+ struct f {};
+ struct g {};
+ struct h {};
+
+ // vertex properties
+ struct prop_v1 {};
+ struct prop_v2 {};
+ struct prop_v3 {};
+
+ // edge properties
+ struct prop_e1 {};
+ struct prop_e2 {};
+
+ //
+ // a-------------b h
+ // |\ \ / |
+ // | \ \ / |
+ // | \ c d
+ // | \ | |
+ // | \ | |
+ // e------f------g
+ //
+ // adjacency list of the graph
+ struct adjacency_list : mpl::vector8<
+ // Node Adjacency
+ // from nodes
+ // +------+--------------------------------------------+
+ row < a , mpl::vector3<c, e, f> >,
+ row >,
+ row < c , mpl::vector2<b, f> >,
+ row < d , mpl::vector2<b, g> >,
+ row < e , mpl::vector2<a, f> >,
+ row < f , mpl::vector0<> >,
+ row < g , mpl::vector2<d, f> >,
+ row < h , mpl::vector0<> >
+ // +------+--------------------------------------------+
+ > {};
+
+ // vertex properties
+ struct vertex_property_list : mpl::vector8<
+ // Node Properties
+ // +------+-----------------------------------------+
+ v_prop < a , mpl::vector1<prop_v1> >,
+ v_prop >,
+ v_prop < c , mpl::vector0<> >,
+ v_prop < d , mpl::vector2<prop_v1, prop_v2> >,
+ v_prop < e , mpl::vector2<prop_v1, prop_v3> >,
+ v_prop < f , mpl::vector2<prop_v2, prop_v3> >,
+ v_prop < g , mpl::vector0<> >,
+ v_prop < h , mpl::vector0<> >
+ // +------+-----------------------------------------+
+ > {};
+
+ // edge properties and weights
+ struct edge_list : mpl::vector12<
+ // Node Node Weight Properties
+ // from to
+ // +------+------+--------+---------------------------+
+ edge < a , b , 3 , mpl::vector1<prop_e1> >,
+ edge < a , c , 2 , mpl::vector1<prop_e1> >,
+ // +------+------+--------+---------------------------+
+ edge >,
+ edge >,
+ edge >,
+ // +------+------+--------+---------------------------+
+ edge < c , a , 2 , mpl::vector0<> >,
+ edge < c , e , 8 , mpl::vector1<prop_e1> >,
+ edge < c , d , 2 , mpl::vector1<prop_e2> >,
+ // +------+------+--------+---------------------------+
+ edge < e , b , 1 , mpl::vector0<> >,
+ edge < e , c , 8 , mpl::vector0<> >,
+ edge < e , d , 11 , mpl::vector0<> >,
+ // +------+------+--------+---------------------------+
+ edge < f , g , 1 , mpl::vector0<> >
+ // +------+------+--------+---------------------------+
+ > {};
+};
+
+template<class TracePolicy>
+void perform_dfs_iteration_to_end_of_graph()
+{
+ // get dfs-iterator to begin of graph
+ typedef typename dfs_begin<simple_directed, EndAtEndOfGraph, TracePolicy>::type dfs_begin;
+
+ typedef BOOST_TYPEOF(dfs_begin()) dfs_begin_t;
+
+ //std::cout << "type of 'dfs_begin' = " << typeid(dfs_begin_t).name() << std::endl;
+
+ // dereference iterator to begin to get first vertex of graph
+ typedef typename deref<dfs_begin>::type dfs_begin_deref;
+
+ typedef BOOST_TYPEOF(dfs_begin_deref()) dfs_begin_deref_t;
+
+ std::cout << "type of 'dfs_begin_deref' = " << typeid(dfs_begin_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<dfs_begin>::type dfs_next1;
+
+ typedef BOOST_TYPEOF(dfs_next1()) dfs_next1_t;
+
+ //std::cout << "type of 'dfs_next1' = " << typeid(dfs_next1_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<dfs_next1>::type dfs_next1_deref;
+
+ typedef BOOST_TYPEOF(dfs_next1_deref()) dfs_next1_deref_t;
+
+ std::cout << "type of 'dfs_next1_deref' = " << typeid(dfs_next1_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<dfs_next1>::type dfs_next2;
+
+ typedef BOOST_TYPEOF(dfs_next2()) dfs_next2_t;
+
+ //std::cout << "type of 'dfs_next2' = " << typeid(dfs_next2_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<dfs_next2>::type dfs_next2_deref;
+
+ typedef BOOST_TYPEOF(dfs_next2_deref()) dfs_next2_deref_t;
+
+ std::cout << "type of 'dfs_next2_deref' = " << typeid(dfs_next2_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<dfs_next2>::type dfs_next3;
+
+ typedef BOOST_TYPEOF(dfs_next3()) dfs_next3_t;
+
+ //std::cout << "type of 'dfs_next3' = " << typeid(dfs_next3_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<dfs_next3>::type dfs_next3_deref;
+
+ typedef BOOST_TYPEOF(dfs_next3_deref()) dfs_next3_deref_t;
+
+ std::cout << "type of 'dfs_next3_deref' = " << typeid(dfs_next3_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<dfs_next3>::type dfs_next4;
+
+ typedef BOOST_TYPEOF(dfs_next4()) dfs_next4_t;
+
+ //std::cout << "type of 'dfs_next4' = " << typeid(dfs_next4_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<dfs_next4>::type dfs_next4_deref;
+
+ typedef BOOST_TYPEOF(dfs_next4_deref()) dfs_next4_deref_t;
+
+ std::cout << "type of 'dfs_next4_deref' = " << typeid(dfs_next4_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<dfs_next4>::type dfs_next5;
+
+ typedef BOOST_TYPEOF(dfs_next5()) dfs_next5_t;
+
+ //std::cout << "type of 'dfs_next5' = " << typeid(dfs_next5_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<dfs_next5>::type dfs_next5_deref;
+
+ typedef BOOST_TYPEOF(dfs_next5_deref()) dfs_next5_deref_t;
+
+ std::cout << "type of 'dfs_next5_deref' = " << typeid(dfs_next5_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<dfs_next5>::type dfs_next6;
+
+ typedef BOOST_TYPEOF(dfs_next6()) dfs_next6_t;
+
+ //std::cout << "type of 'dfs_next6' = " << typeid(dfs_next6_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<dfs_next6>::type dfs_next6_deref;
+
+ typedef BOOST_TYPEOF(dfs_next6_deref()) dfs_next6_deref_t;
+
+ std::cout << "type of 'dfs_next6_deref' = " << typeid(dfs_next6_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<dfs_next6>::type dfs_next7;
+
+ typedef BOOST_TYPEOF(dfs_next7()) dfs_next7_t;
+
+ //std::cout << "type of 'dfs_next7' = " << typeid(dfs_next7_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<dfs_next7>::type dfs_next7_deref;
+
+ typedef BOOST_TYPEOF(dfs_next7_deref()) dfs_next7_deref_t;
+
+ std::cout << "type of 'dfs_next7_deref' = " << typeid(dfs_next7_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<dfs_next7>::type dfs_next8;
+
+ typedef BOOST_TYPEOF(dfs_next8()) dfs_next8_t;
+
+ //std::cout << "type of 'dfs_next8' = " << typeid(dfs_next8_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<dfs_next8>::type dfs_next8_deref;
+
+ typedef BOOST_TYPEOF(dfs_next8_deref()) dfs_next8_deref_t;
+
+ std::cout << "type of 'dfs_next8_deref' = " << typeid(dfs_next8_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<dfs_next8>::type dfs_next9;
+
+ typedef BOOST_TYPEOF(dfs_next9()) dfs_next9_t;
+
+ //std::cout << "type of 'dfs_next9' = " << typeid(dfs_next9_t).name() << std::endl;
+
+ typedef BOOST_TYPEOF((typename dfs_next9::vertex_trace())) dfs_next9_vertices_t;
+
+ //std::cout << "type of 'dfs_next9::vertex_trace' = " << typeid(dfs_next9_vertices_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<dfs_next9>::type dfs_next9_deref;
+
+ typedef BOOST_TYPEOF(dfs_next9_deref()) dfs_next9_deref_t;
+
+ std::cout << "type of 'dfs_next9_deref' = " << typeid(dfs_next9_deref_t).name() << std::endl;
+
+ // print trace
+ std::cout << "trace = " << typeid(dfs_next9_vertices_t).name() << std::endl;
+}
+
+void perform_dfs_iteration_to_end_of_graph_with_trace()
+{
+ std::cout << "perform DFS iteration to end of graph with trace of vertices" << std::endl;
+
+ perform_dfs_iteration_to_end_of_graph< ::boost::mgl::RecordTrace< ::boost::mpl::vector0<> > >();
+}
+
+void perform_dfs_iteration_to_end_of_graph_without_trace()
+{
+ std::cout << "perform DFS iteration to end of graph without any trace" << std::endl;
+
+ perform_dfs_iteration_to_end_of_graph< ::boost::mgl::NoTrace>();
+}
+
+template<class TracePolicy>
+void perform_dfs_iteration_to_end_of_path()
+{
+ // get dfs-iterator to begin of graph
+ typedef typename dfs_begin<simple_directed, EndWhenNoVerticesFound, TracePolicy>::type dfs_begin;
+
+ typedef BOOST_TYPEOF(dfs_begin()) dfs_begin_t;
+
+ //std::cout << "type of 'dfs_begin' = " << typeid(dfs_begin_t).name() << std::endl;
+
+ // dereference iterator to begin to get first vertex of graph
+ typedef typename deref<dfs_begin>::type dfs_begin_deref;
+
+ typedef BOOST_TYPEOF(dfs_begin_deref()) dfs_begin_deref_t;
+
+ std::cout << "type of 'dfs_begin_deref' = " << typeid(dfs_begin_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<dfs_begin>::type dfs_next1;
+
+ typedef BOOST_TYPEOF(dfs_next1()) dfs_next1_t;
+
+ //std::cout << "type of 'dfs_next1' = " << typeid(dfs_next1_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<dfs_next1>::type dfs_next1_deref;
+
+ typedef BOOST_TYPEOF(dfs_next1_deref()) dfs_next1_deref_t;
+
+ std::cout << "type of 'dfs_next1_deref' = " << typeid(dfs_next1_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<dfs_next1>::type dfs_next2;
+
+ typedef BOOST_TYPEOF(dfs_next2()) dfs_next2_t;
+
+ //std::cout << "type of 'dfs_next2' = " << typeid(dfs_next2_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<dfs_next2>::type dfs_next2_deref;
+
+ typedef BOOST_TYPEOF(dfs_next2_deref()) dfs_next2_deref_t;
+
+ std::cout << "type of 'dfs_next2_deref' = " << typeid(dfs_next2_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<dfs_next2>::type dfs_next3;
+
+ typedef BOOST_TYPEOF(dfs_next3()) dfs_next3_t;
+
+ //std::cout << "type of 'dfs_next3' = " << typeid(dfs_next3_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<dfs_next3>::type dfs_next3_deref;
+
+ typedef BOOST_TYPEOF(dfs_next3_deref()) dfs_next3_deref_t;
+
+ std::cout << "type of 'dfs_next3_deref' = " << typeid(dfs_next3_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<dfs_next3>::type dfs_next4;
+
+ typedef BOOST_TYPEOF((typename dfs_next4::traversal_stack())) dfs_next4_t;
+
+ //std::cout << "type of 'dfs_next4' = " << typeid(dfs_next4_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<dfs_next4>::type dfs_next4_deref;
+
+ typedef BOOST_TYPEOF(dfs_next4_deref()) dfs_next4_deref_t;
+
+ std::cout << "type of 'dfs_next4_deref' = " << typeid(dfs_next4_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<dfs_next4>::type dfs_next5;
+
+ typedef BOOST_TYPEOF((typename dfs_next5::traversal_stack())) dfs_next5_t;
+
+ //std::cout << "type of 'dfs_next5' = " << typeid(dfs_next5_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<dfs_next5>::type dfs_next5_deref;
+
+ typedef BOOST_TYPEOF(dfs_next5_deref()) dfs_next5_deref_t;
+
+ std::cout << "type of 'dfs_next5_deref' = " << typeid(dfs_next5_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<dfs_next5>::type dfs_next6;
+
+ typedef BOOST_TYPEOF((typename dfs_next6::traversal_stack())) dfs_next6_t;
+
+ //std::cout << "type of 'dfs_next6' = " << typeid(dfs_next6_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<dfs_next6>::type dfs_next6_deref;
+
+ typedef BOOST_TYPEOF(dfs_next6_deref()) dfs_next6_deref_t;
+
+ std::cout << "type of 'dfs_next6_deref' = " << typeid(dfs_next6_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<dfs_next6>::type dfs_next7;
+
+ typedef BOOST_TYPEOF(dfs_next7()) dfs_next7_t;
+
+ //std::cout << "type of 'dfs_next7' = " << typeid(dfs_next7_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<dfs_next7>::type dfs_next7_deref;
+
+ typedef BOOST_TYPEOF(dfs_next7_deref()) dfs_next7_deref_t;
+
+ std::cout << "type of 'dfs_next7_deref' = " << typeid(dfs_next7_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<dfs_next7>::type dfs_next8;
+
+ typedef BOOST_TYPEOF(dfs_next8()) dfs_next8_t;
+
+ //std::cout << "type of 'dfs_next8' = " << typeid(dfs_next8_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<dfs_next8>::type dfs_next8_deref;
+
+ typedef BOOST_TYPEOF(dfs_next8_deref()) dfs_next8_deref_t;
+
+ std::cout << "type of 'dfs_next8_deref' = " << typeid(dfs_next8_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<dfs_next8>::type dfs_next9;
+
+ typedef BOOST_TYPEOF(dfs_next9()) dfs_next9_t;
+
+ //std::cout << "type of 'dfs_next9' = " << typeid(dfs_next9_t).name() << std::endl;
+
+ typedef BOOST_TYPEOF((typename dfs_next9::vertex_trace())) dfs_next9_vertices_t;
+
+ //std::cout << "type of 'dfs_next9::vertex_trace' = " << typeid(dfs_next9_vertices_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<dfs_next9>::type dfs_next9_deref;
+
+ typedef BOOST_TYPEOF(dfs_next9_deref()) dfs_next9_deref_t;
+
+ std::cout << "type of 'dfs_next9_deref' = " << typeid(dfs_next9_deref_t).name() << std::endl;
+
+ // print trace
+ std::cout << "trace = " << typeid(dfs_next9_vertices_t).name() << std::endl;
+}
+
+void perform_dfs_iteration_to_end_of_path_with_trace()
+{
+ std::cout << "perform DFS iteration to end of path with trace of vertices" << std::endl;
+
+ perform_dfs_iteration_to_end_of_path< ::boost::mgl::RecordTrace< ::boost::mpl::vector0<> > >();
+}
+
+void perform_dfs_iteration_to_end_of_path_without_trace()
+{
+ std::cout << "perform DFS iteration to end of path without any trace" << std::endl;
+
+ perform_dfs_iteration_to_end_of_path< ::boost::mgl::NoTrace>();
+}
+
+template<class TracePolicy>
+void perform_bfs_iteration()
+{
+ // get bfs-iterator to begin of graph
+ typedef typename bfs_begin<simple_directed, TracePolicy>::type bfs_begin;
+
+ typedef BOOST_TYPEOF(bfs_begin()) bfs_begin_t;
+
+ //std::cout << "type of 'bfs_begin' = " << typeid(bfs_begin_t).name() << std::endl;
+
+ typedef BOOST_TYPEOF((typename bfs_begin::vertex_trace())) bfs_begin_vertices_t;
+
+ //std::cout << "type of 'bfs_begin::vertex_trace' = " << typeid(bfs_begin_vertices_t).name() << std::endl;
+
+ // dereference iterator to begin to get first vertex of graph
+ typedef typename deref<bfs_begin>::type bfs_begin_deref;
+
+ typedef BOOST_TYPEOF(bfs_begin_deref()) bfs_begin_deref_t;
+
+ std::cout << "type of 'bfs_begin_deref' = " << typeid(bfs_begin_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<bfs_begin>::type bfs_next1;
+
+ typedef BOOST_TYPEOF(bfs_next1()) bfs_next1_t;
+
+ //std::cout << "type of 'dfs_next1' = " << typeid(bfs_next1_t).name() << std::endl;
+
+ typedef BOOST_TYPEOF((typename bfs_next1::vertex_trace())) bfs_next1_vertices_t;
+
+ //std::cout << "type of 'dfs_next1::vertex_trace' = " << typeid(bfs_next1_vertices_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<bfs_next1>::type bfs_next1_deref;
+
+ typedef BOOST_TYPEOF(bfs_next1_deref()) bfs_next1_deref_t;
+
+ std::cout << "type of 'bfs_next1_deref' = " << typeid(bfs_next1_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<bfs_next1>::type bfs_next2;
+
+ typedef BOOST_TYPEOF(bfs_next2()) bfs_next2_t;
+
+ //std::cout << "type of 'dfs_next2' = " << typeid(bfs_next2_t).name() << std::endl;
+
+ typedef BOOST_TYPEOF((typename bfs_next2::vertex_trace())) bfs_next2_vertices_t;
+
+ //std::cout << "type of 'dfs_next2::vertex_trace' = " << typeid(bfs_next2_vertices_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<bfs_next2>::type bfs_next2_deref;
+
+ typedef BOOST_TYPEOF(bfs_next2_deref()) bfs_next2_deref_t;
+
+ std::cout << "type of 'bfs_next2_deref' = " << typeid(bfs_next2_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<bfs_next2>::type bfs_next3;
+
+ typedef BOOST_TYPEOF(bfs_next3()) bfs_next3_t;
+
+ //std::cout << "type of 'dfs_next3' = " << typeid(bfs_next3_t).name() << std::endl;
+
+ typedef BOOST_TYPEOF((typename bfs_next3::vertex_trace())) bfs_next3_vertices_t;
+
+ //std::cout << "type of 'dfs_next3::vertex_trace' = " << typeid(bfs_next3_vertices_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<bfs_next3>::type bfs_next3_deref;
+
+ typedef BOOST_TYPEOF(bfs_next3_deref()) bfs_next3_deref_t;
+
+ std::cout << "type of 'bfs_next3_deref' = " << typeid(bfs_next3_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<bfs_next3>::type bfs_next4;
+
+ typedef BOOST_TYPEOF(bfs_next4()) bfs_next4_t;
+
+ //std::cout << "type of 'dfs_next4' = " << typeid(bfs_next4_t).name() << std::endl;
+
+ typedef BOOST_TYPEOF((typename bfs_next4::vertex_trace())) bfs_next4_vertices_t;
+
+ //std::cout << "type of 'dfs_next4::vertex_trace' = " << typeid(bfs_next4_vertices_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<bfs_next4>::type bfs_next4_deref;
+
+ typedef BOOST_TYPEOF(bfs_next4_deref()) bfs_next4_deref_t;
+
+ std::cout << "type of 'bfs_next4_deref' = " << typeid(bfs_next4_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<bfs_next4>::type bfs_next5;
+
+ typedef BOOST_TYPEOF(bfs_next5()) bfs_next5_t;
+
+ //std::cout << "type of 'dfs_next5' = " << typeid(bfs_next5_t).name() << std::endl;
+
+ typedef BOOST_TYPEOF((typename bfs_next5::vertex_trace())) bfs_next5_vertices_t;
+
+ //std::cout << "type of 'dfs_next5::vertex_trace' = " << typeid(bfs_next5_vertices_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<bfs_next5>::type bfs_next5_deref;
+
+ typedef BOOST_TYPEOF(bfs_next5_deref()) bfs_next5_deref_t;
+
+ std::cout << "type of 'bfs_next5_deref' = " << typeid(bfs_next5_deref_t).name() << std::endl;
+
+ // move iterator to next element
+ typedef typename next<bfs_next5>::type bfs_next6;
+
+ typedef BOOST_TYPEOF(bfs_next6()) bfs_next6_t;
+
+ //std::cout << "type of 'dfs_next6' = " << typeid(bfs_next6_t).name() << std::endl;
+
+ typedef BOOST_TYPEOF((typename bfs_next6::vertex_trace())) bfs_next6_vertices_t;
+
+ //std::cout << "type of 'dfs_next6::vertex_trace' = " << typeid(bfs_next6_vertices_t).name() << std::endl;
+
+ // dereference iterator to next element
+ typedef typename deref<bfs_next6>::type bfs_next6_deref;
+
+ typedef BOOST_TYPEOF(bfs_next6_deref()) bfs_next6_deref_t;
+
+ std::cout << "type of 'bfs_next6_deref' = " << typeid(bfs_next6_deref_t).name() << std::endl;
+
+ // print trace
+ std::cout << "trace = " << typeid(bfs_next6_vertices_t).name() << std::endl;
+}
+
+void perform_bfs_iteration_with_trace()
+{
+ std::cout << "perform BFS iteration with trace of vertices" << std::endl;
+
+ perform_bfs_iteration< ::boost::mgl::RecordTrace< ::boost::mpl::vector0<> > >();
+}
+
+void perform_bfs_iteration_without_trace()
+{
+ std::cout << "perform BFS iteration without any trace" << std::endl;
+
+ perform_bfs_iteration< ::boost::mgl::NoTrace>();
+}
+
+int main(int /*argc*/, char * /*argv*/[])
+{
+ // graph has vertices 'a', 'b', 'c', 'd', 'e', 'f', 'g' and 'h'
+ BOOST_MPL_ASSERT((mpl::equal<
+ simple_directed::get_vertices::type,
+ mpl::set<simple_directed::a, simple_directed::b, simple_directed::c,
+ simple_directed::d, simple_directed::e, simple_directed::f,
+ simple_directed::g, simple_directed::h> >
+ ));
+
+ // vertex 'a' has property 'prop_v1'
+ BOOST_MPL_ASSERT((mpl::equal<
+ simple_directed::get_vertex_properties<simple_directed::a>::type,
+ mpl::vector1<simple_directed::prop_v1> >
+ ));
+
+ // vertex 'c' has no properties
+ BOOST_MPL_ASSERT((mpl::equal<
+ simple_directed::get_vertex_properties<simple_directed::c>::type,
+ mpl::vector0<> >
+ ));
+
+ // edge from 'b' to 'e' has no properties
+ BOOST_MPL_ASSERT((mpl::equal<
+ simple_directed::get_edge_properties<simple_directed::b, simple_directed::e>::type,
+ mpl::vector0<> >
+ ));
+
+ // edge from 'c' to 'd' has property 'prop_e2'
+ BOOST_MPL_ASSERT((mpl::equal<
+ simple_directed::get_edge_properties<simple_directed::c, simple_directed::d>::type,
+ mpl::vector1<simple_directed::prop_e2> >
+ ));
+
+ //// edge from 'a' to 'e' has no properties
+ //BOOST_MPL_ASSERT((is_same<
+ // simple_directed::get_edge_properties<simple_directed::a, simple_directed::e>::type,
+ // mpl::void_>
+ //));
+
+ //typedef simple_directed::get_edge_properties<simple_directed::a, simple_directed::e>::type edge_ae;
+
+ //typedef BOOST_TYPEOF(edge_ae()) edge_ae_t;
+
+ //std::cout << "type of 'edge_ae' = " << typeid(edge_ae_t).name() << std::endl;
+
+ // weight of edge from 'a' to 'b' is 3
+ BOOST_MPL_ASSERT_RELATION(
+ (simple_directed::get_edge_weight<simple_directed::a, simple_directed::b>::value), ==, 3);
+
+ // weight of edge from 'b' to 'c' is 3
+ BOOST_MPL_ASSERT_RELATION(
+ (simple_directed::get_edge_weight<simple_directed::b, simple_directed::c>::value), ==, 3);
+
+ //// find vertex 'd' beginning from vertex 'a'
+ //BOOST_MPL_ASSERT((mpl::equal<
+ // simple_directed::find_vertex<simple_directed::a, simple_directed::d>::type,
+ // mpl::vector5<simple_directed::a, simple_directed::b, simple_directed::c, simple_directed::e, simple_directed::d> >
+ //));
+
+ // find vertex 'c' beginning from vertex 'a'
+ BOOST_MPL_ASSERT((mpl::equal<
+ simple_directed::find_vertex<simple_directed::a, simple_directed::c>::type,
+ mpl::vector2<simple_directed::a, simple_directed::c> >
+ ));
+
+ // test the DFS iteration to the end of the graph (all vertices has to be
+ // visited) with trace of vertices
+ perform_dfs_iteration_to_end_of_graph_with_trace();
+
+ // test the DFS iteration to the end of the graph (all vertices has to be
+ // visited) without trace of vertices
+ perform_dfs_iteration_to_end_of_graph_without_trace();
+
+ // test the DFS iteration until no vertex is reachable (there could be some
+ // unvisited vertices at the end) with trace of vertices
+ perform_dfs_iteration_to_end_of_path_with_trace();
+
+ // test the DFS iteration until no vertex is reachable (there could be some
+ // unvisited vertices at the end) without trace of vertices
+ perform_dfs_iteration_to_end_of_path_without_trace();
+
+ // test the BFS iteration with trace of vertices
+ perform_bfs_iteration_with_trace();
+
+ // test the BFS iteration without trace of vertices
+ perform_bfs_iteration_without_trace();
+
+ return 0;
+}

Added: sandbox/mgl/libs/mgl/examples/topological_sort.cpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/libs/mgl/examples/topological_sort.cpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,64 @@
+// 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 <iostream>
+#include <typeinfo>
+
+#define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS
+#undef BOOST_MPL_LIMIT_METAFUNCTION_ARITY
+#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 6
+#include <boost/mpl/apply.hpp>
+
+#include <boost/typeof/typeof.hpp>
+
+#include <boost/mgl/directed_graph.hpp>
+#include <boost/mgl/topological_sort.hpp>
+
+using namespace std;
+
+using namespace boost;
+using namespace boost::mgl;
+
+namespace mgl = boost::mgl;
+
+// vertices
+struct pants {};
+struct sox {};
+struct pullover {};
+struct trousers {};
+struct cloak {};
+struct shoes {};
+struct shirt {};
+
+class adduction_graph : public directed_graph<adduction_graph>
+{
+public:
+ // adjacency list of the graph
+ struct adjacency_list : mpl::vector7<
+ // Node Adjacency
+ // from nodes
+ // +----------+----------------------------------------+
+ row < pants , mpl::vector1<trousers> >,
+ row < sox , mpl::vector1<shoes> >,
+ row < pullover , mpl::vector1<cloak> >,
+ row < trousers , mpl::vector2<cloak, shoes> >,
+ row < cloak , mpl::vector0<> >,
+ row < shoes , mpl::vector0<> >,
+ row < shirt , mpl::vector1<pullover> >
+ // +----------+----------------------------------------+
+ > {};
+};
+
+int main(int /*argc*/, char * /*argv*/[])
+{
+ typedef topological_sort<adduction_graph>::type graph;
+
+ typedef BOOST_TYPEOF(graph()) graph_t;
+
+ cout << typeid(graph_t).name() << endl << endl;
+
+ return 0;
+}

Added: sandbox/mgl/libs/mgl/examples/visitor.cpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/libs/mgl/examples/visitor.cpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,152 @@
+// 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)
+
+#define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS
+#undef BOOST_MPL_LIMIT_METAFUNCTION_ARITY
+#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 6
+#include <boost/mpl/apply.hpp>
+
+#include <boost/typeof/typeof.hpp>
+
+#include <boost/type_traits/is_same.hpp>
+
+#include <boost/mpl/vector.hpp>
+#include <boost/mpl/accumulate.hpp>
+#include <boost/mpl/if.hpp>
+#include <boost/mpl/eval_if.hpp>
+#include <boost/mpl/fold.hpp>
+#include <boost/mpl/plus.hpp>
+#include <boost/mpl/int.hpp>
+#include <boost/mpl/placeholders.hpp>
+#include <boost/mpl/greater.hpp>
+#include <boost/mpl/comparison.hpp>
+#include <boost/mpl/push_back.hpp>
+#include <boost/mpl/equal.hpp>
+#include <boost/mpl/assert.hpp>
+
+#include <boost/mgl/directed_graph.hpp>
+#include <boost/mgl/depth_first_search.hpp>
+
+using namespace boost;
+using namespace boost::mgl;
+
+namespace mgl = boost::mgl;
+
+//! @todo Add description of the example.
+
+// vertices
+struct v0 {};
+struct v1 {};
+struct v2 {};
+struct v3 {};
+struct v4 {};
+struct v5 {};
+struct v6 {};
+struct v7 {};
+struct v8 {};
+struct v9 {};
+struct v10 {};
+struct v11 {};
+struct v12 {};
+struct v13 {};
+struct v14 {};
+
+class some_graph : public directed_graph<some_graph>
+{
+public:
+ // adjacency list of the graph
+ struct adjacency_list : mpl::vector15<
+ // Node Adjacency
+ // from nodes
+ // +------+--------------------------------------------+
+ row < v0 , mpl::vector2<v13, v14> >,
+ row < v1 , mpl::vector2<v13, v12> >,
+ row < v2 , mpl::vector0<> >,
+ row < v3 , mpl::vector2<v2, v12> >,
+ row < v4 , mpl::vector3<v13, v8, v9> >,
+ row < v5 , mpl::vector2<v13, v7> >,
+ row < v6 , mpl::vector1<v2> >,
+ row < v7 , mpl::vector3<v6, v8, v11> >,
+ row < v8 , mpl::vector3<v12, v12, v2> >,
+ row < v9 , mpl::vector1<v9> >,
+ row < v10 , mpl::vector2<v5, v3> >,
+ row < v11 , mpl::vector1<v11> >,
+ row < v12 , mpl::vector2<v4, v7> >,
+ row < v13 , mpl::vector3<v12, v9, v5> >,
+ row < v14 , mpl::vector3<v0, v12, v14> >
+ // +------+--------------------------------------------+
+ > {};
+};
+
+typedef mpl::vector5<
+ v0,
+ v9,
+ v10,
+ v12,
+ v2
+> source_vertices;
+
+typedef v2 target_vertex;
+
+typedef mpl::vector4<
+ v0,
+ v10,
+ v12,
+ v2
+> reachable_vertices;
+
+template<class V>
+struct count_vertex_visitor
+{
+ typedef mpl::true_ discover_vertex;
+
+ struct on_init
+ {
+ typedef mpl::int_<0> type;
+ };
+
+ template<typename Vertex, typename T, typename TraversalStack, typename ColorMap>
+ struct on_discover_vertex
+ {
+ typedef typename mpl::if_<
+ typename is_same<Vertex, V>::type,
+ typename mpl::plus<T, mpl::int_<1> >::type,
+ T
+ >::type type;
+ };
+};
+
+template<class Source, class Target>
+struct is_found
+{
+ typedef typename mpl::greater<
+ typename depth_first_search<
+ some_graph,
+ //count_vertex_visitor<Target>,
+ ::boost::mgl::null_visitor,
+ //Source
+ ::boost::mpl::void_
+ >::type::visitor_result,
+ mpl::int_<0>
+ >::type type;
+};
+
+typedef mpl::fold<
+ source_vertices,
+ mpl::vector0<>,
+ mpl::if_<
+ is_found<mpl::placeholders::_2, target_vertex>,
+ mpl::push_back<mpl::placeholders::_1, mpl::placeholders::_2>,
+ mpl::placeholders::_1
+ >
+>::type reached_vertices;
+
+BOOST_MPL_ASSERT(( mpl::equal<reached_vertices, reachable_vertices>::type ));
+
+int main(int argc, char * argv[])
+{
+ return 0;
+}

Added: sandbox/mgl/libs/mgl/test/bfs_iteration.cpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/libs/mgl/test/bfs_iteration.cpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,136 @@
+// 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 <typeinfo>
+
+#include <boost/mpl/vector.hpp>
+#include <boost/mpl/void.hpp>
+
+#include <boost/typeof/typeof.hpp>
+
+#include <boost/mgl/directed_graph.hpp>
+#include <boost/mgl/begin_end.hpp>
+#include <boost/mgl/next_prior.hpp>
+
+#define BOOST_TEST_MODULE "BFS Iteration Test"
+#include <boost/test/unit_test.hpp>
+
+using namespace boost;
+using namespace boost::mgl;
+
+namespace mgl = boost::mgl;
+
+// vertices
+struct v0 {};
+struct v1 {};
+struct v2 {};
+struct v3 {};
+struct v4 {};
+struct v5 {};
+struct v6 {};
+struct v7 {};
+struct v8 {};
+struct v9 {};
+
+class some_graph : public directed_graph<some_graph>
+{
+public:
+ // adjacency list of the graph
+ struct adjacency_list : mpl::vector10<
+ // Node Adjacency
+ // from nodes
+ // +------+--------------------------------------------+
+ row < v0 , mpl::vector1<v2> >,
+ row < v1 , mpl::vector1<v8> >,
+ row < v2 , mpl::vector5<v5, v8, v1, v9, v6> >,
+ row < v3 , mpl::vector1<v7> >,
+ row < v4 , mpl::vector2<v1, v5> >,
+ row < v5 , mpl::vector0<> >,
+ row < v6 , mpl::vector0<> >,
+ row < v7 , mpl::vector1<v1> >,
+ row < v8 , mpl::vector1<v3> >,
+ row < v9 , mpl::vector0<> >
+ // +------+--------------------------------------------+
+ > {};
+};
+
+struct foo {};
+
+BOOST_AUTO_TEST_CASE(invalid_bfs_begin)
+{
+ typedef BOOST_TYPEOF(mpl::void_()) void_t;
+
+ typedef bfs_begin<foo>::type iter;
+ typedef BOOST_TYPEOF(iter()) iter_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_t) == typeid(void_t), "bfs_begin<> should return mpl::void_ at invalid graph type");
+}
+
+BOOST_AUTO_TEST_CASE(bfs_iteration)
+{
+ typedef BOOST_TYPEOF(mpl::void_()) void_t;
+ typedef BOOST_TYPEOF(some_graph::end::type()) end_t;
+
+ typedef bfs_begin<some_graph>::type iter;
+ 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");
+
+ 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");
+
+ 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");
+
+ 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");
+
+ 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");
+
+ 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");
+
+ 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");
+
+ 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");
+
+ 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");
+
+ 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");
+}

Added: sandbox/mgl/libs/mgl/test/breadth_first_search.cpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/libs/mgl/test/breadth_first_search.cpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,503 @@
+// 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 <typeinfo>
+
+#define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS
+#undef BOOST_MPL_LIMIT_METAFUNCTION_ARITY
+#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 6
+#include <boost/mpl/apply.hpp>
+
+#include <boost/mpl/vector.hpp>
+#include <boost/mpl/void.hpp>
+
+#include <boost/typeof/typeof.hpp>
+
+#include <boost/mgl/directed_graph.hpp>
+#include <boost/mgl/breadth_first_search.hpp>
+#include <boost/mgl/visitors.hpp>
+
+#define BOOST_TEST_MODULE "Breadth First Search Test"
+#include <boost/test/unit_test.hpp>
+
+using namespace boost;
+using namespace boost::mgl;
+
+namespace mgl = boost::mgl;
+
+// vertices
+struct v0 {};
+struct v1 {};
+struct v2 {};
+struct v3 {};
+struct v4 {};
+struct v5 {};
+struct v6 {};
+struct v7 {};
+struct v8 {};
+struct v9 {};
+
+class some_graph : public directed_graph<some_graph>
+{
+public:
+ // adjacency list of the graph
+ struct adjacency_list : mpl::vector10<
+ // Node Adjacency
+ // from nodes
+ // +------+--------------------------------------------+
+ row < v0 , mpl::vector1<v6> >,
+ row < v1 , mpl::vector1<v8> >,
+ row < v2 , mpl::vector5<v5, v8, v1, v9, v6> >,
+ row < v3 , mpl::vector1<v7> >,
+ row < v4 , mpl::vector2<v1, v5> >,
+ row < v5 , mpl::vector0<> >,
+ row < v6 , mpl::vector0<> >,
+ row < v7 , mpl::vector1<v1> >,
+ row < v8 , mpl::vector1<v3> >,
+ row < v9 , mpl::vector0<> >
+ // +------+--------------------------------------------+
+ > {};
+};
+
+struct foo {};
+
+BOOST_AUTO_TEST_CASE(invalid_breadth_first_search)
+{
+ typedef BOOST_TYPEOF(mpl::void_()) void_t;
+
+ typedef breadth_first_search<foo>::type::vertex_trace dfs;
+ typedef BOOST_TYPEOF(dfs()) dfs_t;
+
+ BOOST_CHECK_MESSAGE(typeid(dfs_t) == typeid(void_t), "breadth_first_search<> should return mpl::void_ for invalid graph type");
+}
+
+BOOST_AUTO_TEST_CASE(perform_breadth_first_search)
+{
+ // perform search from first vertex
+ typedef mpl::vector2<
+ v0,
+ v6
+ > expected_result11;
+ typedef BOOST_TYPEOF(expected_result11()) expected_result11_t;
+
+ typedef breadth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v0,
+ ::boost::mgl::EndWhenNoVerticesFound
+ >::type::vertex_trace 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");
+
+ // perform search from first vertex (visit all vertices)
+ typedef mpl::vector10<
+ v0,
+ v6,
+ v9,
+ v8,
+ v3,
+ v7,
+ v1,
+ v5,
+ v4,
+ v2
+ > expected_result12;
+ typedef BOOST_TYPEOF(expected_result12()) expected_result12_t;
+
+ typedef breadth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v0
+ >::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");
+
+ // perform search from vertex 'v1'
+ typedef mpl::vector4<
+ v1,
+ v8,
+ v3,
+ v7
+ > expected_result21;
+ typedef BOOST_TYPEOF(expected_result21()) expected_result21_t;
+
+ typedef breadth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v1,
+ ::boost::mgl::EndWhenNoVerticesFound
+ >::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");
+
+ // perform search from vertex 'v1' (visit all vertices)
+ typedef mpl::vector10<
+ v1,
+ v8,
+ v3,
+ v7,
+ v9,
+ v6,
+ v5,
+ v4,
+ v2,
+ v0
+ > expected_result22;
+ typedef BOOST_TYPEOF(expected_result22()) expected_result22_t;
+
+ typedef breadth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v1
+ >::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");
+
+ // perform search from vertex 'v2'
+ typedef mpl::vector8<
+ v2,
+ v5,
+ v8,
+ v1,
+ v9,
+ v6,
+ v3,
+ v7
+ > expected_result31;
+ typedef BOOST_TYPEOF(expected_result31()) expected_result31_t;
+
+ typedef breadth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v2,
+ ::boost::mgl::EndWhenNoVerticesFound
+ >::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");
+
+ // perform search from vertex 'v2' (visit all vertices)
+ typedef mpl::vector10<
+ v2,
+ v5,
+ v8,
+ v1,
+ v9,
+ v6,
+ v3,
+ v7,
+ v4,
+ v0
+ > expected_result32;
+ typedef BOOST_TYPEOF(expected_result32()) expected_result32_t;
+
+ typedef breadth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v2
+ >::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");
+
+ // perform search from vertex 'v3'
+ typedef mpl::vector4<
+ v3,
+ v7,
+ v1,
+ v8
+ > expected_result41;
+ typedef BOOST_TYPEOF(expected_result41()) expected_result41_t;
+
+ typedef breadth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v3,
+ ::boost::mgl::EndWhenNoVerticesFound
+ >::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");
+
+ // perform search from vertex 'v3' (visit all vertices)
+ typedef mpl::vector10<
+ v3,
+ v7,
+ v1,
+ v8,
+ v9,
+ v6,
+ v5,
+ v4,
+ v2,
+ v0
+ > expected_result42;
+ typedef BOOST_TYPEOF(expected_result42()) expected_result42_t;
+
+ typedef breadth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v3
+ >::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");
+
+ // perform search from vertex 'v4'
+ typedef mpl::vector6<
+ v4,
+ v1,
+ v5,
+ v8,
+ v3,
+ v7
+ > expected_result51;
+ typedef BOOST_TYPEOF(expected_result51()) expected_result51_t;
+
+ typedef breadth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v4,
+ ::boost::mgl::EndWhenNoVerticesFound
+ >::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");
+
+ // perform search from vertex 'v4' (visit all vertices)
+ typedef mpl::vector10<
+ v4,
+ v1,
+ v5,
+ v8,
+ v3,
+ v7,
+ v9,
+ v6,
+ v2,
+ v0
+ > expected_result52;
+ typedef BOOST_TYPEOF(expected_result52()) expected_result52_t;
+
+ typedef breadth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v4
+ >::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");
+
+ // perform search from vertex 'v5'
+ typedef mpl::vector1<
+ v5
+ > expected_result61;
+ typedef BOOST_TYPEOF(expected_result61()) expected_result61_t;
+
+ typedef breadth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v5,
+ ::boost::mgl::EndWhenNoVerticesFound
+ >::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");
+
+ // perform search from vertex 'v5' (visit all vertices)
+ typedef mpl::vector10<
+ v5,
+ v9,
+ v8,
+ v3,
+ v7,
+ v1,
+ v6,
+ v4,
+ v2,
+ v0
+ > expected_result62;
+ typedef BOOST_TYPEOF(expected_result62()) expected_result62_t;
+
+ typedef breadth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v5
+ >::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");
+
+ // perform search from vertex 'v6'
+ typedef mpl::vector1<
+ v6
+ > expected_result71;
+ typedef BOOST_TYPEOF(expected_result71()) expected_result71_t;
+
+ typedef breadth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v6,
+ ::boost::mgl::EndWhenNoVerticesFound
+ >::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");
+
+ // perform search from vertex 'v6' (visit all vertices)
+ typedef mpl::vector10<
+ v6,
+ v9,
+ v8,
+ v3,
+ v7,
+ v1,
+ v5,
+ v4,
+ v2,
+ v0
+ > expected_result72;
+ typedef BOOST_TYPEOF(expected_result72()) expected_result72_t;
+
+ typedef breadth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v6
+ >::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");
+
+ // perform search from vertex 'v7'
+ typedef mpl::vector4<
+ v7,
+ v1,
+ v8,
+ v3
+ > expected_result81;
+ typedef BOOST_TYPEOF(expected_result81()) expected_result81_t;
+
+ typedef breadth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v7,
+ ::boost::mgl::EndWhenNoVerticesFound
+ >::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");
+
+ // perform search from vertex 'v7' (visit all vertices)
+ typedef mpl::vector10<
+ v7,
+ v1,
+ v8,
+ v3,
+ v9,
+ v6,
+ v5,
+ v4,
+ v2,
+ v0
+ > expected_result82;
+ typedef BOOST_TYPEOF(expected_result82()) expected_result82_t;
+
+ typedef breadth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v7
+ >::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");
+
+ // perform search from vertex 'v8'
+ typedef mpl::vector4<
+ v8,
+ v3,
+ v7,
+ v1
+ > expected_result91;
+ typedef BOOST_TYPEOF(expected_result91()) expected_result91_t;
+
+ typedef breadth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v8,
+ ::boost::mgl::EndWhenNoVerticesFound
+ >::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");
+
+ // perform search from vertex 'v8' (visit all vertices)
+ typedef mpl::vector10<
+ v8,
+ v3,
+ v7,
+ v1,
+ v9,
+ v6,
+ v5,
+ v4,
+ v2,
+ v0
+ > expected_result92;
+ typedef BOOST_TYPEOF(expected_result92()) expected_result92_t;
+
+ typedef breadth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v8
+ >::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");
+
+ // perform search from vertex 'v9'
+ typedef mpl::vector1<
+ v9
+ > expected_result101;
+ typedef BOOST_TYPEOF(expected_result101()) expected_result101_t;
+
+ typedef breadth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v9,
+ ::boost::mgl::EndWhenNoVerticesFound
+ >::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");
+
+ // perform search from vertex 'v9' (visit all vertices)
+ typedef mpl::vector10<
+ v9,
+ v8,
+ v3,
+ v7,
+ v1,
+ v6,
+ v5,
+ v4,
+ v2,
+ v0
+ > expected_result102;
+ typedef BOOST_TYPEOF(expected_result102()) expected_result102_t;
+
+ typedef breadth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v9
+ >::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");
+}

Added: sandbox/mgl/libs/mgl/test/contains_cycle.cpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/libs/mgl/test/contains_cycle.cpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,85 @@
+// 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 <typeinfo>
+
+#define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS
+#undef BOOST_MPL_LIMIT_METAFUNCTION_ARITY
+#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 6
+#include <boost/mpl/apply.hpp>
+
+#include <boost/mpl/bool.hpp>
+
+#include <boost/mgl/directed_graph.hpp>
+#include <boost/mgl/contains_cycle.hpp>
+
+#include <boost/typeof/typeof.hpp>
+
+#define BOOST_TEST_MODULE "Contains Cycle Test"
+#include <boost/test/unit_test.hpp>
+
+using namespace boost;
+using namespace boost::mgl;
+
+namespace mgl = boost::mgl;
+
+// vertices
+struct a {};
+struct b {};
+struct c {};
+struct d {};
+
+class cycle_graph : public directed_graph<cycle_graph>
+{
+public:
+ // adjacency list of the graph
+ struct adjacency_list : mpl::vector4<
+ // Node Adjacency
+ // from nodes
+ // +------+--------------------------------------------+
+ row < a , mpl::vector1<d> >,
+ row >,
+ row < c , mpl::vector2<a, b> >,
+ row < d , mpl::vector2<c, b> >
+ // +------+--------------------------------------------+
+ > {};
+};
+
+class non_cycle_graph : public directed_graph<non_cycle_graph>
+{
+public:
+ // adjacency list of the graph
+ struct adjacency_list : mpl::vector4<
+ // Node Adjacency
+ // from nodes
+ // +------+--------------------------------------------+
+ row < a , mpl::vector1<d> >,
+ row >,
+ row < c , mpl::vector1 >,
+ row < d , mpl::vector2<c, b> >
+ // +------+--------------------------------------------+
+ > {};
+};
+
+BOOST_AUTO_TEST_CASE(test_cycle_graph)
+{
+ typedef BOOST_TYPEOF(mpl::true_()) true_t;
+
+ typedef contains_cycle<cycle_graph>::type result;
+ typedef BOOST_TYPEOF(result()) result_t;
+
+ BOOST_CHECK_MESSAGE(typeid(result_t) == typeid(true_t), "contains_cycle<> should return a proper ::mpl::true_");
+}
+
+BOOST_AUTO_TEST_CASE(test_non_cycle_graph)
+{
+ typedef BOOST_TYPEOF(mpl::false_()) false_t;
+
+ 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_");
+}

Added: sandbox/mgl/libs/mgl/test/depth_first_search.cpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/libs/mgl/test/depth_first_search.cpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,482 @@
+// 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 <typeinfo>
+
+#define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS
+#undef BOOST_MPL_LIMIT_METAFUNCTION_ARITY
+#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 6
+#include <boost/mpl/apply.hpp>
+
+#include <boost/mpl/vector.hpp>
+#include <boost/mpl/void.hpp>
+
+#include <boost/typeof/typeof.hpp>
+
+#include <boost/mgl/directed_graph.hpp>
+#include <boost/mgl/depth_first_search.hpp>
+#include <boost/mgl/visitors.hpp>
+
+#define BOOST_TEST_MODULE "Depth First Search Test"
+#include <boost/test/unit_test.hpp>
+
+using namespace boost;
+using namespace boost::mgl;
+
+namespace mgl = boost::mgl;
+
+// vertices
+struct v0 {};
+struct v1 {};
+struct v2 {};
+struct v3 {};
+struct v4 {};
+struct v5 {};
+struct v6 {};
+struct v7 {};
+struct v8 {};
+struct v9 {};
+
+class some_graph : public directed_graph<some_graph>
+{
+public:
+ // adjacency list of the graph
+ struct adjacency_list : mpl::vector10<
+ // Node Adjacency
+ // from nodes
+ // +------+--------------------------------------------+
+ row < v0 , mpl::vector1<v6> >,
+ row < v1 , mpl::vector1<v8> >,
+ row < v2 , mpl::vector5<v5, v8, v1, v9, v6> >,
+ row < v3 , mpl::vector1<v7> >,
+ row < v4 , mpl::vector2<v1, v5> >,
+ row < v5 , mpl::vector0<> >,
+ row < v6 , mpl::vector0<> >,
+ row < v7 , mpl::vector1<v1> >,
+ row < v8 , mpl::vector1<v3> >,
+ row < v9 , mpl::vector0<> >
+ // +------+--------------------------------------------+
+ > {};
+};
+
+struct foo {};
+
+BOOST_AUTO_TEST_CASE(invalid_depth_first_search)
+{
+ typedef BOOST_TYPEOF(mpl::void_()) void_t;
+
+ typedef depth_first_search<foo>::type::vertex_trace 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");
+}
+
+BOOST_AUTO_TEST_CASE(perform_depth_first_search)
+{
+ // perform search from first vertex
+ typedef mpl::vector10<
+ v0,
+ v6,
+ v9,
+ v8,
+ v3,
+ v7,
+ v1,
+ v5,
+ v4,
+ v2
+ > expected_result1;
+ typedef BOOST_TYPEOF(expected_result1()) expected_result1_t;
+
+ typedef depth_first_search<some_graph>::type::vertex_trace 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");
+
+ // perform search from vertex 'v1'
+ typedef mpl::vector4<
+ v1,
+ v8,
+ v3,
+ v7
+ > expected_result21;
+ typedef BOOST_TYPEOF(expected_result21()) expected_result21_t;
+
+ typedef depth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v1,
+ ::boost::mgl::EndWhenNoVerticesFound
+ >::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");
+
+ // perform search from vertex 'v1' (visit all vertices)
+ typedef mpl::vector10<
+ v1,
+ v8,
+ v3,
+ v7,
+ v9,
+ v6,
+ v5,
+ v4,
+ v2,
+ v0
+ > expected_result22;
+ typedef BOOST_TYPEOF(expected_result22()) expected_result22_t;
+
+ typedef depth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v1
+ >::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");
+
+ // perform search from vertex 'v2'
+ typedef mpl::vector8<
+ v2,
+ v5,
+ v8,
+ v3,
+ v7,
+ v1,
+ v9,
+ v6
+ > expected_result31;
+ typedef BOOST_TYPEOF(expected_result31()) expected_result31_t;
+
+ typedef depth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v2,
+ ::boost::mgl::EndWhenNoVerticesFound
+ >::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");
+
+ // perform search from vertex 'v2' (visit all vertices)
+ typedef mpl::vector10<
+ v2,
+ v5,
+ v8,
+ v3,
+ v7,
+ v1,
+ v9,
+ v6,
+ v4,
+ v0
+ > expected_result32;
+ typedef BOOST_TYPEOF(expected_result32()) expected_result32_t;
+
+ typedef depth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v2
+ >::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");
+
+ // perform search from vertex 'v3'
+ typedef mpl::vector4<
+ v3,
+ v7,
+ v1,
+ v8
+ > expected_result41;
+ typedef BOOST_TYPEOF(expected_result41()) expected_result41_t;
+
+ typedef depth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v3,
+ ::boost::mgl::EndWhenNoVerticesFound
+ >::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");
+
+ // perform search from vertex 'v3' (visit all vertices)
+ typedef mpl::vector10<
+ v3,
+ v7,
+ v1,
+ v8,
+ v9,
+ v6,
+ v5,
+ v4,
+ v2,
+ v0
+ > expected_result42;
+ typedef BOOST_TYPEOF(expected_result42()) expected_result42_t;
+
+ typedef depth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v3
+ >::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");
+
+ // perform search from vertex 'v4'
+ typedef mpl::vector6<
+ v4,
+ v1,
+ v8,
+ v3,
+ v7,
+ v5
+ > expected_result51;
+ typedef BOOST_TYPEOF(expected_result51()) expected_result51_t;
+
+ typedef depth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v4,
+ ::boost::mgl::EndWhenNoVerticesFound
+ >::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");
+
+ // perform search from vertex 'v4' (visit all vertices)
+ typedef mpl::vector10<
+ v4,
+ v1,
+ v8,
+ v3,
+ v7,
+ v5,
+ v9,
+ v6,
+ v2,
+ v0
+ > expected_result52;
+ typedef BOOST_TYPEOF(expected_result52()) expected_result52_t;
+
+ typedef depth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v4
+ >::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");
+
+ // perform search from vertex 'v5'
+ typedef mpl::vector1<
+ v5
+ > expected_result61;
+ typedef BOOST_TYPEOF(expected_result61()) expected_result61_t;
+
+ typedef depth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v5,
+ ::boost::mgl::EndWhenNoVerticesFound
+ >::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");
+
+ // perform search from vertex 'v5' (visit all vertices)
+ typedef mpl::vector10<
+ v5,
+ v9,
+ v8,
+ v3,
+ v7,
+ v1,
+ v6,
+ v4,
+ v2,
+ v0
+ > expected_result62;
+ typedef BOOST_TYPEOF(expected_result62()) expected_result62_t;
+
+ typedef depth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v5
+ >::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");
+
+ // perform search from vertex 'v6'
+ typedef mpl::vector1<
+ v6
+ > expected_result71;
+ typedef BOOST_TYPEOF(expected_result71()) expected_result71_t;
+
+ typedef depth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v6,
+ ::boost::mgl::EndWhenNoVerticesFound
+ >::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");
+
+ // perform search from vertex 'v6' (visit all vertices)
+ typedef mpl::vector10<
+ v6,
+ v9,
+ v8,
+ v3,
+ v7,
+ v1,
+ v5,
+ v4,
+ v2,
+ v0
+ > expected_result72;
+ typedef BOOST_TYPEOF(expected_result72()) expected_result72_t;
+
+ typedef depth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v6
+ >::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");
+
+ // perform search from vertex 'v7'
+ typedef mpl::vector4<
+ v7,
+ v1,
+ v8,
+ v3
+ > expected_result81;
+ typedef BOOST_TYPEOF(expected_result81()) expected_result81_t;
+
+ typedef depth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v7,
+ ::boost::mgl::EndWhenNoVerticesFound
+ >::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");
+
+ // perform search from vertex 'v7' (visit all vertices)
+ typedef mpl::vector10<
+ v7,
+ v1,
+ v8,
+ v3,
+ v9,
+ v6,
+ v5,
+ v4,
+ v2,
+ v0
+ > expected_result82;
+ typedef BOOST_TYPEOF(expected_result82()) expected_result82_t;
+
+ typedef depth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v7
+ >::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");
+
+ // perform search from vertex 'v8'
+ typedef mpl::vector4<
+ v8,
+ v3,
+ v7,
+ v1
+ > expected_result91;
+ typedef BOOST_TYPEOF(expected_result91()) expected_result91_t;
+
+ typedef depth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v8,
+ ::boost::mgl::EndWhenNoVerticesFound
+ >::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");
+
+ // perform search from vertex 'v8' (visit all vertices)
+ typedef mpl::vector10<
+ v8,
+ v3,
+ v7,
+ v1,
+ v9,
+ v6,
+ v5,
+ v4,
+ v2,
+ v0
+ > expected_result92;
+ typedef BOOST_TYPEOF(expected_result92()) expected_result92_t;
+
+ typedef depth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v8
+ >::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");
+
+ // perform search from vertex 'v9'
+ typedef mpl::vector1<
+ v9
+ > expected_result101;
+ typedef BOOST_TYPEOF(expected_result101()) expected_result101_t;
+
+ typedef depth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v9,
+ ::boost::mgl::EndWhenNoVerticesFound
+ >::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");
+
+ // perform search from vertex 'v9' (visit all vertices)
+ typedef mpl::vector10<
+ v9,
+ v8,
+ v3,
+ v7,
+ v1,
+ v6,
+ v5,
+ v4,
+ v2,
+ v0
+ > expected_result102;
+ typedef BOOST_TYPEOF(expected_result102()) expected_result102_t;
+
+ typedef depth_first_search<
+ some_graph,
+ ::boost::mgl::vertex_trace_visitor,
+ v9
+ >::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");
+}

Added: sandbox/mgl/libs/mgl/test/dfs_iteration.cpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/libs/mgl/test/dfs_iteration.cpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,167 @@
+// 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 <typeinfo>
+
+#include <boost/mpl/vector.hpp>
+#include <boost/mpl/void.hpp>
+
+#include <boost/typeof/typeof.hpp>
+
+#include <boost/mgl/directed_graph.hpp>
+#include <boost/mgl/begin_end.hpp>
+#include <boost/mgl/next_prior.hpp>
+#include <boost/mgl/iterator_policies.hpp>
+
+#define BOOST_TEST_MODULE "DFS Iteration Test"
+#include <boost/test/unit_test.hpp>
+
+using namespace boost;
+using namespace boost::mgl;
+
+namespace mgl = boost::mgl;
+
+// vertices
+struct v0 {};
+struct v1 {};
+struct v2 {};
+struct v3 {};
+struct v4 {};
+struct v5 {};
+struct v6 {};
+struct v7 {};
+struct v8 {};
+struct v9 {};
+
+class some_graph : public directed_graph<some_graph>
+{
+public:
+ // adjacency list of the graph
+ struct adjacency_list : mpl::vector10<
+ // Node Adjacency
+ // from nodes
+ // +------+--------------------------------------------+
+ row < v0 , mpl::vector1<v6> >,
+ row < v1 , mpl::vector1<v8> >,
+ row < v2 , mpl::vector5<v5, v8, v1, v9, v6> >,
+ row < v3 , mpl::vector1<v7> >,
+ row < v4 , mpl::vector2<v1, v5> >,
+ row < v5 , mpl::vector0<> >,
+ row < v6 , mpl::vector0<> >,
+ row < v7 , mpl::vector1<v1> >,
+ row < v8 , mpl::vector1<v3> >,
+ row < v9 , mpl::vector0<> >
+ // +------+--------------------------------------------+
+ > {};
+};
+
+struct foo {};
+
+BOOST_AUTO_TEST_CASE(invalid_dfs_begin)
+{
+ typedef BOOST_TYPEOF(mpl::void_()) void_t;
+
+ typedef dfs_begin<foo>::type iter;
+ typedef BOOST_TYPEOF(iter()) iter_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_t) == typeid(void_t), "dfs_begin<> should return mpl::void_ at invalid graph type");
+}
+
+BOOST_AUTO_TEST_CASE(dfs_iteration_short)
+{
+ typedef BOOST_TYPEOF(mpl::void_()) void_t;
+ typedef BOOST_TYPEOF(some_graph::end::type()) end_t;
+
+ typedef dfs_begin<some_graph, ::boost::mgl::EndWhenNoVerticesFound>::type iter;
+ 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");
+
+ 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");
+
+ 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 graph::end type");
+}
+
+BOOST_AUTO_TEST_CASE(dfs_iteration_complete)
+{
+ typedef BOOST_TYPEOF(mpl::void_()) void_t;
+ typedef BOOST_TYPEOF(some_graph::end::type()) end_t;
+
+ typedef dfs_begin<some_graph>::type iter;
+ 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");
+
+ 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");
+
+ 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");
+
+ 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");
+
+ 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");
+
+ 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");
+
+ 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");
+
+ 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");
+
+ 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");
+
+ 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");
+
+ typedef ::boost::mgl::next<iter_next9>::type iter_next10;
+ typedef deref<iter_next10>::type iter_next10_deref;
+ typedef BOOST_TYPEOF(iter_next10_deref()) iter_next10_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_next10_deref_t) == typeid(end_t), "next<> should return a valid graph::end type");
+}

Added: sandbox/mgl/libs/mgl/test/find_vertex.cpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/libs/mgl/test/find_vertex.cpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,226 @@
+// 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 <typeinfo>
+
+#define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS
+#undef BOOST_MPL_LIMIT_METAFUNCTION_ARITY
+#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 6
+#include <boost/mpl/apply.hpp>
+
+#include <boost/mpl/vector.hpp>
+#include <boost/mpl/void.hpp>
+
+#include <boost/typeof/typeof.hpp>
+
+#include <boost/mgl/directed_graph.hpp>
+#include <boost/mgl/find.hpp>
+
+#define BOOST_TEST_MODULE "Find Vertex Test"
+#include <boost/test/unit_test.hpp>
+
+using namespace boost;
+using namespace boost::mgl;
+
+namespace mgl = boost::mgl;
+
+// vertices
+struct v0 {};
+struct v1 {};
+struct v2 {};
+struct v3 {};
+struct v4 {};
+struct v5 {};
+struct v6 {};
+struct v7 {};
+struct v8 {};
+struct v9 {};
+
+class some_graph : public directed_graph<some_graph>
+{
+public:
+ // adjacency list of the graph
+ struct adjacency_list : mpl::vector10<
+ // Node Adjacency
+ // from nodes
+ // +------+--------------------------------------------+
+ row < v0 , mpl::vector1<v6> >,
+ row < v1 , mpl::vector1<v8> >,
+ row < v2 , mpl::vector5<v5, v8, v1, v9, v6> >,
+ row < v3 , mpl::vector1<v7> >,
+ row < v4 , mpl::vector2<v1, v5> >,
+ row < v5 , mpl::vector0<> >,
+ row < v6 , mpl::vector0<> >,
+ row < v7 , mpl::vector1<v1> >,
+ row < v8 , mpl::vector1<v3> >,
+ row < v9 , mpl::vector0<> >
+ // +------+--------------------------------------------+
+ > {};
+};
+
+BOOST_AUTO_TEST_CASE(dfs_find_all_vertices)
+{
+ typedef BOOST_TYPEOF(mpl::void_()) void_t;
+
+ typedef dfs_find<some_graph, v0>::type iter_v0;
+ typedef deref<iter_v0>::type iter_v0_deref;
+ typedef BOOST_TYPEOF(iter_v0_deref()) iter_v0_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_v0_deref_t) != typeid(void_t), "dfs_find<> should return a valid iterator type");
+
+ typedef dfs_find<some_graph, v1>::type iter_v1;
+ typedef deref<iter_v1>::type iter_v1_deref;
+ typedef BOOST_TYPEOF(iter_v1_deref()) iter_v1_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_v1_deref_t) != typeid(void_t), "dfs_find<> should return a valid iterator type");
+
+ typedef dfs_find<some_graph, v2>::type iter_v2;
+ typedef deref<iter_v2>::type iter_v2_deref;
+ typedef BOOST_TYPEOF(iter_v2_deref()) iter_v2_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_v2_deref_t) != typeid(void_t), "dfs_find<> should return a valid iterator type");
+
+ typedef dfs_find<some_graph, v3>::type iter_v3;
+ typedef deref<iter_v3>::type iter_v3_deref;
+ typedef BOOST_TYPEOF(iter_v3_deref()) iter_v3_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_v3_deref_t) != typeid(void_t), "dfs_find<> should return a valid iterator type");
+
+ typedef dfs_find<some_graph, v4>::type iter_v4;
+ typedef deref<iter_v4>::type iter_v4_deref;
+ typedef BOOST_TYPEOF(iter_v4_deref()) iter_v4_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_v4_deref_t) != typeid(void_t), "dfs_find<> should return a valid iterator type");
+
+ typedef dfs_find<some_graph, v5>::type iter_v5;
+ typedef deref<iter_v5>::type iter_v5_deref;
+ typedef BOOST_TYPEOF(iter_v5_deref()) iter_v5_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_v5_deref_t) != typeid(void_t), "dfs_find<> should return a valid iterator type");
+
+ typedef dfs_find<some_graph, v6>::type iter_v6;
+ typedef deref<iter_v6>::type iter_v6_deref;
+ typedef BOOST_TYPEOF(iter_v6_deref()) iter_v6_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_v6_deref_t) != typeid(void_t), "dfs_find<> should return a valid iterator type");
+
+ typedef dfs_find<some_graph, v7>::type iter_v7;
+ typedef deref<iter_v7>::type iter_v7_deref;
+ typedef BOOST_TYPEOF(iter_v7_deref()) iter_v7_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_v7_deref_t) != typeid(void_t), "dfs_find<> should return a valid iterator type");
+
+ typedef dfs_find<some_graph, v8>::type iter_v8;
+ typedef deref<iter_v8>::type iter_v8_deref;
+ typedef BOOST_TYPEOF(iter_v8_deref()) iter_v8_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_v8_deref_t) != typeid(void_t), "dfs_find<> should return a valid iterator type");
+
+ typedef dfs_find<some_graph, v9>::type iter_v9;
+ typedef deref<iter_v9>::type iter_v9_deref;
+ typedef BOOST_TYPEOF(iter_v9_deref()) iter_v9_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_v9_deref_t) != typeid(void_t), "dfs_find<> should return a valid iterator type");
+}
+
+BOOST_AUTO_TEST_CASE(invalid_dfs_find_vertex)
+{
+ typedef BOOST_TYPEOF(mpl::void_()) void_t;
+
+ typedef dfs_find<int, v0>::type iter1;
+ typedef deref<iter1>::type iter1_deref;
+ typedef BOOST_TYPEOF(iter1_deref()) iter1_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter1_deref_t) == typeid(void_t), "dfs_find<> should return mpl::void_ at invalid graph type");
+
+ typedef dfs_find<some_graph, int>::type iter2;
+ typedef deref<iter2>::type iter2_deref;
+ typedef BOOST_TYPEOF(iter2_deref()) iter2_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter2_deref_t) == typeid(void_t), "dfs_find<> should return mpl::void_ at invalid vertex type");
+}
+
+BOOST_AUTO_TEST_CASE(bfs_find_all_vertices)
+{
+ typedef BOOST_TYPEOF(mpl::void_()) void_t;
+
+ typedef bfs_find<some_graph, v0>::type iter_v0;
+ typedef deref<iter_v0>::type iter_v0_deref;
+ typedef BOOST_TYPEOF(iter_v0_deref()) iter_v0_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_v0_deref_t) != typeid(void_t), "bfs_find<> should return a valid iterator type");
+
+ typedef bfs_find<some_graph, v1>::type iter_v1;
+ typedef deref<iter_v1>::type iter_v1_deref;
+ typedef BOOST_TYPEOF(iter_v1_deref()) iter_v1_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_v1_deref_t) != typeid(void_t), "bfs_find<> should return a valid iterator type");
+
+ typedef bfs_find<some_graph, v2>::type iter_v2;
+ typedef deref<iter_v2>::type iter_v2_deref;
+ typedef BOOST_TYPEOF(iter_v2_deref()) iter_v2_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_v2_deref_t) != typeid(void_t), "bfs_find<> should return a valid iterator type");
+
+ typedef bfs_find<some_graph, v3>::type iter_v3;
+ typedef deref<iter_v3>::type iter_v3_deref;
+ typedef BOOST_TYPEOF(iter_v3_deref()) iter_v3_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_v3_deref_t) != typeid(void_t), "bfs_find<> should return a valid iterator type");
+
+ typedef bfs_find<some_graph, v4>::type iter_v4;
+ typedef deref<iter_v4>::type iter_v4_deref;
+ typedef BOOST_TYPEOF(iter_v4_deref()) iter_v4_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_v4_deref_t) != typeid(void_t), "bfs_find<> should return a valid iterator type");
+
+ typedef bfs_find<some_graph, v5>::type iter_v5;
+ typedef deref<iter_v5>::type iter_v5_deref;
+ typedef BOOST_TYPEOF(iter_v5_deref()) iter_v5_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_v5_deref_t) != typeid(void_t), "bfs_find<> should return a valid iterator type");
+
+ typedef bfs_find<some_graph, v6>::type iter_v6;
+ typedef deref<iter_v6>::type iter_v6_deref;
+ typedef BOOST_TYPEOF(iter_v6_deref()) iter_v6_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_v6_deref_t) != typeid(void_t), "bfs_find<> should return a valid iterator type");
+
+ typedef bfs_find<some_graph, v7>::type iter_v7;
+ typedef deref<iter_v7>::type iter_v7_deref;
+ typedef BOOST_TYPEOF(iter_v7_deref()) iter_v7_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_v7_deref_t) != typeid(void_t), "bfs_find<> should return a valid iterator type");
+
+ typedef bfs_find<some_graph, v8>::type iter_v8;
+ typedef deref<iter_v8>::type iter_v8_deref;
+ typedef BOOST_TYPEOF(iter_v8_deref()) iter_v8_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_v8_deref_t) != typeid(void_t), "bfs_find<> should return a valid iterator type");
+
+ typedef bfs_find<some_graph, v9>::type iter_v9;
+ typedef deref<iter_v9>::type iter_v9_deref;
+ typedef BOOST_TYPEOF(iter_v9_deref()) iter_v9_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter_v9_deref_t) != typeid(void_t), "bfs_find<> should return a valid iterator type");
+}
+
+BOOST_AUTO_TEST_CASE(invalid_bfs_find_vertex)
+{
+ typedef BOOST_TYPEOF(mpl::void_()) void_t;
+
+ typedef bfs_find<int, v0>::type iter1;
+ typedef deref<iter1>::type iter1_deref;
+ typedef BOOST_TYPEOF(iter1_deref()) iter1_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter1_deref_t) == typeid(void_t), "bfs_find<> should return mpl::void_ at invalid graph type");
+
+ typedef bfs_find<some_graph, int>::type iter2;
+ typedef deref<iter2>::type iter2_deref;
+ typedef BOOST_TYPEOF(iter2_deref()) iter2_deref_t;
+
+ BOOST_CHECK_MESSAGE(typeid(iter2_deref_t) == typeid(void_t), "bfs_find<> should return mpl::void_ at invalid vertex type");
+}

Added: sandbox/mgl/libs/mgl/test/generic_graph.cpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/libs/mgl/test/generic_graph.cpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,208 @@
+// 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 <typeinfo>
+
+#define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS
+#undef BOOST_MPL_LIMIT_METAFUNCTION_ARITY
+#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 6
+#include <boost/mpl/apply.hpp>
+
+#include <boost/mpl/assert.hpp>
+#include <boost/mpl/void.hpp>
+
+#include <boost/typeof/typeof.hpp>
+
+#include <boost/mgl/graph.hpp>
+#include <boost/mgl/graph_policies.hpp>
+#include <boost/mgl/depth_first_search.hpp>
+#include <boost/mgl/breadth_first_search.hpp>
+#include <boost/mgl/find.hpp>
+
+#define BOOST_TEST_MODULE "Generic Graph Test"
+#include <boost/test/unit_test.hpp>
+
+using namespace boost;
+using namespace boost::mgl;
+
+namespace mgl = boost::mgl;
+
+// something that has nothing to do with the test
+struct foo {};
+
+// vertices
+struct a {};
+struct b {};
+struct c {};
+struct d {};
+
+class simple_directed_graph : public graph<simple_directed_graph, VmapDirectedGraph>
+{
+public:
+ // adjacency list of the graph
+ struct adjacency_list : mpl::vector4<
+ // Node Adjacency
+ // from nodes
+ // +------+--------------------------------------------+
+ row < a , mpl::vector2<b, c> >,
+ row >,
+ row < c , mpl::vector1 >,
+ row < d , mpl::vector0<> >
+ // +------+--------------------------------------------+
+ > {};
+};
+
+class simple_undirected_graph : public graph<simple_undirected_graph, VmapUndirectedGraph>
+{
+public:
+ // adjacency list of the graph
+ struct adjacency_list : mpl::vector4<
+ // Node Adjacency
+ // from nodes
+ // +------+--------------------------------------------+
+ row < a , mpl::vector2<b, c> >,
+ row >,
+ row < c , mpl::vector1 >,
+ row < d , mpl::vector0<> >
+ // +------+--------------------------------------------+
+ > {};
+};
+
+BOOST_AUTO_TEST_CASE(test_directed_graph_dfs)
+{
+ typedef mpl::vector4<
+ mpl::pair<b, d>,
+ mpl::pair<c, b>,
+ mpl::pair<a, b>,
+ mpl::pair<a, c>
+ > expected_result1;
+ typedef BOOST_TYPEOF(expected_result1()) expected_result1_t;
+
+ 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<>");
+
+ typedef mpl::vector1<
+ mpl::pair<b, d>
+ > expected_result2;
+ typedef BOOST_TYPEOF(expected_result2()) expected_result2_t;
+
+ 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_AUTO_TEST_CASE(test_directed_graph_dfs_find)
+{
+ typedef dfs_find<simple_directed_graph, a>::type result1;
+ typedef dfs_find<simple_directed_graph, b>::type result2;
+ typedef dfs_find<simple_directed_graph, c>::type result3;
+ typedef dfs_find<simple_directed_graph, d>::type result4;
+
+ BOOST_CHECK_MESSAGE(mpl::is_not_void_<result1>::value, "dfs_find<> should return a valid iterator");
+ BOOST_CHECK_MESSAGE(mpl::is_not_void_<result2>::value, "dfs_find<> should return a valid iterator");
+ BOOST_CHECK_MESSAGE(mpl::is_not_void_<result3>::value, "dfs_find<> should return a valid iterator");
+ BOOST_CHECK_MESSAGE(mpl::is_not_void_<result4>::value, "dfs_find<> should return a valid iterator");
+
+ typedef dfs_find<simple_directed_graph, foo>::type result5;
+
+ BOOST_CHECK_MESSAGE(mpl::is_void_<result5>::value, "dfs_find<> should return an invalid iterator");
+}
+
+BOOST_AUTO_TEST_CASE(test_undirected_graph_dfs)
+{
+ typedef mpl::vector8<
+ mpl::pair<b, d>,
+ mpl::pair<b, a>,
+ mpl::pair<b, c>,
+ mpl::pair<d, b>,
+ mpl::pair<a, b>,
+ mpl::pair<a, c>,
+ mpl::pair<c, b>,
+ mpl::pair<c, a>
+ > expected_result;
+ typedef BOOST_TYPEOF(expected_result()) expected_result_t;
+
+ 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<>");
+
+ 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_AUTO_TEST_CASE(test_directed_graph_bfs)
+{
+ typedef mpl::vector4<
+ mpl::pair<b, d>,
+ mpl::pair<c, b>,
+ mpl::pair<a, b>,
+ mpl::pair<a, c>
+ > expected_result1;
+ typedef BOOST_TYPEOF(expected_result1()) expected_result1_t;
+
+ 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<>");
+
+ typedef mpl::vector1<
+ mpl::pair<b, d>
+ > expected_result2;
+ typedef BOOST_TYPEOF(expected_result2()) expected_result2_t;
+
+ 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_AUTO_TEST_CASE(test_directed_graph_bfs_find)
+{
+ typedef bfs_find<simple_directed_graph, a>::type result1;
+ typedef bfs_find<simple_directed_graph, b>::type result2;
+ typedef bfs_find<simple_directed_graph, c>::type result3;
+ typedef bfs_find<simple_directed_graph, d>::type result4;
+
+ BOOST_CHECK_MESSAGE(mpl::is_not_void_<result1>::value, "bfs_find<> should return a valid iterator");
+ BOOST_CHECK_MESSAGE(mpl::is_not_void_<result2>::value, "bfs_find<> should return a valid iterator");
+ BOOST_CHECK_MESSAGE(mpl::is_not_void_<result3>::value, "bfs_find<> should return a valid iterator");
+ BOOST_CHECK_MESSAGE(mpl::is_not_void_<result4>::value, "bfs_find<> should return a valid iterator");
+
+ typedef bfs_find<simple_directed_graph, foo>::type result5;
+
+ BOOST_CHECK_MESSAGE(mpl::is_void_<result5>::value, "bfs_find<> should return an invalid iterator");
+}
+
+BOOST_AUTO_TEST_CASE(test_undirected_graph_bfs)
+{
+ typedef mpl::vector8<
+ mpl::pair<b, d>,
+ mpl::pair<b, a>,
+ mpl::pair<b, c>,
+ mpl::pair<d, b>,
+ mpl::pair<a, b>,
+ mpl::pair<a, c>,
+ mpl::pair<c, b>,
+ mpl::pair<c, a>
+ > expected_result;
+ typedef BOOST_TYPEOF(expected_result()) expected_result_t;
+
+ 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<>");
+
+ 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<>");
+}

Added: sandbox/mgl/libs/mgl/test/topological_sort.cpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/libs/mgl/test/topological_sort.cpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,64 @@
+// 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 <typeinfo>
+
+#define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS
+#undef BOOST_MPL_LIMIT_METAFUNCTION_ARITY
+#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 6
+#include <boost/mpl/apply.hpp>
+
+#include <boost/typeof/typeof.hpp>
+
+#include <boost/mpl/equal.hpp>
+
+#include <boost/mgl/directed_graph.hpp>
+#include <boost/mgl/topological_sort.hpp>
+
+#define BOOST_TEST_MODULE "Topological Sort Test"
+#include <boost/test/unit_test.hpp>
+
+using namespace boost;
+using namespace boost::mgl;
+
+namespace mgl = boost::mgl;
+
+// vertices
+struct a {};
+struct b {};
+struct c {};
+struct d {};
+struct e {};
+struct f {};
+
+class some_graph : public directed_graph<some_graph>
+{
+public:
+ // adjacency list of the graph
+ struct adjacency_list : mpl::vector6<
+ // Node Adjacency
+ // from nodes
+ // +------+--------------------------------------------+
+ row < a , mpl::vector1 >,
+ row >,
+ row < c , mpl::vector1<d> >,
+ row < d , mpl::vector0<> >,
+ row < e , mpl::vector2<b, d> >,
+ row < f , mpl::vector1<c> >
+ // +------+--------------------------------------------+
+ > {};
+};
+
+BOOST_AUTO_TEST_CASE(check_topological_sort)
+{
+ typedef ::boost::mpl::vector6<a, f, e, b, c, d> expected_result;
+ typedef BOOST_TYPEOF(expected_result()) expected_result_t;
+
+ 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<>");
+}

Added: sandbox/mgl/libs/mgl/test/visitors.cpp
==============================================================================
--- (empty file)
+++ sandbox/mgl/libs/mgl/test/visitors.cpp 2011-05-13 14:15:33 EDT (Fri, 13 May 2011)
@@ -0,0 +1,113 @@
+// 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 <typeinfo>
+
+#define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS
+#undef BOOST_MPL_LIMIT_METAFUNCTION_ARITY
+#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 6
+#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/type_traits/is_integral.hpp>
+
+#include <boost/mgl/directed_graph.hpp>
+#include <boost/mgl/depth_first_search.hpp>
+
+#define BOOST_TEST_MODULE "Visitor Test"
+#include <boost/test/unit_test.hpp>
+
+using namespace boost;
+using namespace boost::mgl;
+
+namespace mgl = boost::mgl;
+
+// vertices
+struct v0 {};
+struct v1 {};
+struct v2 {};
+struct v3 {};
+struct v4 {};
+
+class some_graph : public directed_graph<some_graph>
+{
+public:
+ // adjacency list of the graph
+ struct adjacency_list : mpl::vector5<
+ // Node Adjacency
+ // from nodes
+ // +------+--------------------------------------------+
+ row < v0 , mpl::vector1<v4> >,
+ row < v1 , mpl::vector3<v2, v1, v0> >,
+ row < v2 , mpl::vector2<v1, v0> >,
+ row < v3 , mpl::vector1<v0> >,
+ row < v4 , mpl::vector1<v4> >
+ // +------+--------------------------------------------+
+ > {};
+};
+
+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 BOOST_TYPEOF(mpl::void_()) void_t;
+
+ 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;
+
+ 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 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_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;
+
+ 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 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<>");
+}

Date view	Thread view	Subject view	Author view

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