// Copyright 2008-2010 Gordon Woodhull
|
// 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_MSM_MPL_GRAPH_DEPTH_FIRST_SEARCH_HPP_INCLUDED
|
#define BOOST_MSM_MPL_GRAPH_DEPTH_FIRST_SEARCH_HPP_INCLUDED
|
|
#include <boost/msm/mpl_graph/mpl_graph.hpp>
|
|
#include <boost/mpl/has_key.hpp>
|
#include <boost/mpl/insert.hpp>
|
#include <boost/mpl/pair.hpp>
|
#include <boost/mpl/map.hpp>
|
#include <boost/mpl/has_key.hpp>
|
|
#include "search_colors.hpp"
|
|
namespace boost {
|
namespace msm {
|
namespace mpl_graph {
|
|
// dfs takes a visitor which has all the bgl-like metafunctions encapsulated in an
|
// "operations" member class, and also a state. the operations are expected to return a new state
|
// in addition, the visitor operations are expected to update the colors of vertices
|
// and need to support a new metafunction get_color<Vertex, State>
|
|
struct dfs_default_visitor_operations {
|
template<typename Vertex, typename Graph, typename State>
|
struct initialize_vertex {
|
typedef State type;
|
};
|
|
template<typename Vertex, typename Graph, typename State>
|
struct discover_vertex {
|
typedef State type;
|
};
|
|
template<typename Vertex, typename Graph, typename State>
|
struct finish_vertex {
|
typedef State type;
|
};
|
|
template<typename Edge, typename Graph, typename State>
|
struct tree_edge {
|
typedef State type;
|
};
|
|
template<typename Edge, typename Graph, typename State>
|
struct back_edge {
|
typedef State type;
|
};
|
|
template<typename Edge, typename Graph, typename State>
|
struct forward_or_cross_edge {
|
typedef State type;
|
};
|
};
|
|
// requires IncidenceGraph
|
// returns pair<VisitorState, ColorState>
|
template<typename Graph, typename VisitorOps, typename VisitorState,
|
typename Vertex,
|
typename ColorState = create_search_color_map::type >
|
struct depth_first_search {
|
// enter vertex
|
typedef typename VisitorOps::template
|
discover_vertex<Vertex, Graph, VisitorState>::type
|
discovered_state;
|
typedef typename search_color_map_ops::template
|
set_color<Vertex, search_colors::Gray, ColorState>::type
|
discovered_colors;
|
|
// loop over out edges
|
typedef typename
|
mpl::fold<typename mpl_graph::out_edges<Vertex, Graph>::type,
|
mpl::pair<discovered_state, discovered_colors>,
|
mpl::if_<boost::is_same<search_color_map_ops::get_color<mpl_graph::target<mpl::_2, Graph>, mpl::second<mpl::_1> >,
|
search_colors::White>,
|
// unseen target: recurse
|
depth_first_search<Graph,
|
VisitorOps, typename VisitorOps::template tree_edge<mpl::_2, Graph, mpl::first<mpl::_1> >,
|
mpl_graph::target<mpl::_2, Graph>,
|
mpl::second<mpl::_1> >,
|
// seen: back or forward edge
|
mpl::pair<mpl::if_<boost::is_same<typename search_color_map_ops::template
|
get_color<mpl_graph::target<mpl::_2, Graph>, mpl::second<mpl::_1 > >,
|
search_colors::Gray>,
|
typename VisitorOps::template back_edge<mpl::_2, Graph, mpl::first<mpl::_1> >,
|
typename VisitorOps::template forward_or_cross_edge<mpl::_2, Graph, mpl::first<mpl::_1> > >, // Black
|
mpl::second<mpl::_1> > >
|
>::type after_outedges;
|
|
// leave vertex, and done!
|
typedef mpl::pair<typename VisitorOps::template finish_vertex<Vertex, Graph, typename mpl::first<after_outedges>::type >::type,
|
typename search_color_map_ops::template set_color<Vertex, search_colors::Black, typename mpl::second<after_outedges>::type>::type> type;
|
};
|
|
// requires IncidenceGraph, VertexListGraph
|
template<typename Graph, typename VisitorOps, typename VisitorState,
|
typename FirstVertex = typename mpl::front<typename mpl_graph::vertices<Graph>::type>::type,
|
typename ColorState = create_search_color_map::type>
|
struct depth_first_search_all : // visit first then rest
|
mpl::fold<typename mpl_graph::vertices<Graph>::type,
|
typename depth_first_search<Graph,
|
VisitorOps, VisitorState,
|
FirstVertex,
|
ColorState>::type,
|
mpl::if_<boost::is_same<search_color_map_ops::get_color<mpl::_2, mpl::second<mpl::_1> >,
|
search_colors::White>, // visit any yet unvisited
|
depth_first_search<Graph,
|
VisitorOps, mpl::first<mpl::_1>,
|
mpl::_2,
|
mpl::second<mpl::_1> >,
|
mpl::_1> >
|
{};
|
|
} // namespace mpl_graph
|
} // namespace msm
|
} // namespace boost
|
|
|
#endif // BOOST_MSM_MPL_GRAPH_DEPTH_FIRST_SEARCH_HPP_INCLUDED
|
