190 lines
4.9 KiB
C++
190 lines
4.9 KiB
C++
|
|
#include <boost/parameter.hpp>
|
|
|
|
BOOST_PARAMETER_NAME((_graph, graphs) graph)
|
|
BOOST_PARAMETER_NAME((_visitor, graphs) visitor)
|
|
BOOST_PARAMETER_NAME((_root_vertex, graphs) in(root_vertex))
|
|
BOOST_PARAMETER_NAME((_index_map, graphs) in(index_map))
|
|
BOOST_PARAMETER_NAME((_color_map, graphs) in_out(color_map))
|
|
|
|
#include <boost/graph/graph_traits.hpp>
|
|
#include <boost/mpl/bool.hpp>
|
|
#include <boost/mpl/if.hpp>
|
|
#include <boost/type_traits/is_convertible.hpp>
|
|
#include <boost/type_traits/is_integral.hpp>
|
|
#include <boost/type_traits/is_same.hpp>
|
|
|
|
struct vertex_descriptor_predicate
|
|
{
|
|
template <typename T, typename Args>
|
|
struct apply
|
|
: boost::mpl::if_<
|
|
boost::is_convertible<
|
|
T
|
|
, typename boost::graph_traits<
|
|
typename boost::parameter::value_type<
|
|
Args
|
|
, graphs::graph
|
|
>::type
|
|
>::vertex_descriptor
|
|
>
|
|
, boost::mpl::true_
|
|
, boost::mpl::false_
|
|
>
|
|
{
|
|
};
|
|
};
|
|
|
|
#include <boost/mpl/eval_if.hpp>
|
|
|
|
struct graph_predicate
|
|
{
|
|
template <typename T, typename Args>
|
|
struct apply
|
|
: boost::mpl::eval_if<
|
|
boost::is_convertible<
|
|
typename boost::graph_traits<T>::traversal_category
|
|
, boost::incidence_graph_tag
|
|
>
|
|
, boost::mpl::if_<
|
|
boost::is_convertible<
|
|
typename boost::graph_traits<T>::traversal_category
|
|
, boost::vertex_list_graph_tag
|
|
>
|
|
, boost::mpl::true_
|
|
, boost::mpl::false_
|
|
>
|
|
, boost::mpl::false_
|
|
>
|
|
{
|
|
};
|
|
};
|
|
|
|
#include <boost/property_map/property_map.hpp>
|
|
#include <boost/type_traits/is_same.hpp>
|
|
|
|
struct color_map_predicate
|
|
{
|
|
template <typename T, typename Args>
|
|
struct apply
|
|
: boost::mpl::if_<
|
|
boost::is_same<
|
|
typename boost::property_traits<T>::key_type
|
|
, typename boost::graph_traits<
|
|
typename boost::parameter::value_type<
|
|
Args
|
|
, graphs::graph
|
|
>::type
|
|
>::vertex_descriptor
|
|
>
|
|
, boost::mpl::true_
|
|
, boost::mpl::false_
|
|
>
|
|
{
|
|
};
|
|
};
|
|
|
|
#include <boost/type_traits/is_integral.hpp>
|
|
|
|
struct index_map_predicate
|
|
{
|
|
template <typename T, typename Args>
|
|
struct apply
|
|
: boost::mpl::eval_if<
|
|
boost::is_integral<
|
|
typename boost::property_traits<T>::value_type
|
|
>
|
|
, boost::mpl::if_<
|
|
boost::is_same<
|
|
typename boost::property_traits<T>::key_type
|
|
, typename boost::graph_traits<
|
|
typename boost::parameter::value_type<
|
|
Args
|
|
, graphs::graph
|
|
>::type
|
|
>::vertex_descriptor
|
|
>
|
|
, boost::mpl::true_
|
|
, boost::mpl::false_
|
|
>
|
|
, boost::mpl::false_
|
|
>
|
|
{
|
|
};
|
|
};
|
|
|
|
#include <boost/graph/properties.hpp>
|
|
#include <vector>
|
|
|
|
template <typename Size, typename IndexMap>
|
|
boost::iterator_property_map<
|
|
std::vector<boost::default_color_type>::iterator
|
|
, IndexMap
|
|
, boost::default_color_type
|
|
, boost::default_color_type&
|
|
>&
|
|
default_color_map(Size num_vertices, IndexMap const& index_map)
|
|
{
|
|
static std::vector<boost::default_color_type> colors(num_vertices);
|
|
static boost::iterator_property_map<
|
|
std::vector<boost::default_color_type>::iterator
|
|
, IndexMap
|
|
, boost::default_color_type
|
|
, boost::default_color_type&
|
|
> m(colors.begin(), index_map);
|
|
return m;
|
|
}
|
|
|
|
#include <boost/graph/depth_first_search.hpp>
|
|
|
|
BOOST_PARAMETER_FUNCTION((void), depth_first_search, graphs,
|
|
(required
|
|
(graph, *(graph_predicate))
|
|
)
|
|
(optional
|
|
(visitor
|
|
, * // not easily checkable
|
|
, boost::dfs_visitor<>()
|
|
)
|
|
(root_vertex
|
|
, *(vertex_descriptor_predicate)
|
|
, *vertices(graph).first
|
|
)
|
|
(index_map
|
|
, *(index_map_predicate)
|
|
, get(boost::vertex_index, graph)
|
|
)
|
|
(color_map
|
|
, *(color_map_predicate)
|
|
, default_color_map(num_vertices(graph), index_map)
|
|
)
|
|
)
|
|
)
|
|
{
|
|
}
|
|
|
|
#include <boost/core/lightweight_test.hpp>
|
|
#include <boost/graph/adjacency_list.hpp>
|
|
#include <utility>
|
|
|
|
int main()
|
|
{
|
|
typedef boost::adjacency_list<
|
|
boost::vecS
|
|
, boost::vecS
|
|
, boost::directedS
|
|
> G;
|
|
enum {u, v, w, x, y, z, N};
|
|
typedef std::pair<std::size_t,std::size_t> E;
|
|
E edges[] = {
|
|
E(u, v), E(u, x), E(x, v), E(y, x),
|
|
E(v, y), E(w, y), E(w, z), E(z, z)
|
|
};
|
|
G g(edges, edges + sizeof(edges) / sizeof(E), N);
|
|
|
|
::depth_first_search(g);
|
|
::depth_first_search(g, _root_vertex = static_cast<std::size_t>(x));
|
|
return boost::report_errors();
|
|
}
|
|
|