| //======================================================================= |
| // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. |
| // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek |
| // |
| // 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_GRAPH_NAMED_FUNCTION_PARAMS_HPP |
| #define BOOST_GRAPH_NAMED_FUNCTION_PARAMS_HPP |
| |
| #include <boost/graph/properties.hpp> |
| #include <boost/ref.hpp> |
| #include <boost/parameter/name.hpp> |
| #include <boost/parameter/binding.hpp> |
| #include <boost/type_traits/is_same.hpp> |
| #include <boost/mpl/not.hpp> |
| #include <boost/type_traits/add_reference.hpp> |
| #include <boost/graph/named_function_params.hpp> |
| #include <boost/property_map/property_map.hpp> |
| #include <boost/property_map/shared_array_property_map.hpp> |
| |
| namespace boost { |
| |
| struct distance_compare_t { }; |
| struct distance_combine_t { }; |
| struct distance_inf_t { }; |
| struct distance_zero_t { }; |
| struct buffer_param_t { }; |
| struct edge_copy_t { }; |
| struct vertex_copy_t { }; |
| struct vertex_isomorphism_t { }; |
| struct vertex_invariant_t { }; |
| struct vertex_invariant1_t { }; |
| struct vertex_invariant2_t { }; |
| struct edge_compare_t { }; |
| struct vertex_max_invariant_t { }; |
| struct orig_to_copy_t { }; |
| struct root_vertex_t { }; |
| struct polling_t { }; |
| struct lookahead_t { }; |
| struct in_parallel_t { }; |
| struct attractive_force_t { }; |
| struct repulsive_force_t { }; |
| struct force_pairs_t { }; |
| struct cooling_t { }; |
| struct vertex_displacement_t { }; |
| struct iterations_t { }; |
| struct diameter_range_t { }; |
| struct learning_constant_range_t { }; |
| struct vertices_equivalent_t { }; |
| struct edges_equivalent_t { }; |
| |
| #define BOOST_BGL_DECLARE_NAMED_PARAMS \ |
| BOOST_BGL_ONE_PARAM_CREF(weight_map, edge_weight) \ |
| BOOST_BGL_ONE_PARAM_CREF(weight_map2, edge_weight2) \ |
| BOOST_BGL_ONE_PARAM_CREF(distance_map, vertex_distance) \ |
| BOOST_BGL_ONE_PARAM_CREF(predecessor_map, vertex_predecessor) \ |
| BOOST_BGL_ONE_PARAM_CREF(rank_map, vertex_rank) \ |
| BOOST_BGL_ONE_PARAM_CREF(root_map, vertex_root) \ |
| BOOST_BGL_ONE_PARAM_CREF(root_vertex, root_vertex) \ |
| BOOST_BGL_ONE_PARAM_CREF(edge_centrality_map, edge_centrality) \ |
| BOOST_BGL_ONE_PARAM_CREF(centrality_map, vertex_centrality) \ |
| BOOST_BGL_ONE_PARAM_CREF(color_map, vertex_color) \ |
| BOOST_BGL_ONE_PARAM_CREF(edge_color_map, edge_color) \ |
| BOOST_BGL_ONE_PARAM_CREF(capacity_map, edge_capacity) \ |
| BOOST_BGL_ONE_PARAM_CREF(residual_capacity_map, edge_residual_capacity) \ |
| BOOST_BGL_ONE_PARAM_CREF(reverse_edge_map, edge_reverse) \ |
| BOOST_BGL_ONE_PARAM_CREF(discover_time_map, vertex_discover_time) \ |
| BOOST_BGL_ONE_PARAM_CREF(lowpoint_map, vertex_lowpoint) \ |
| BOOST_BGL_ONE_PARAM_CREF(vertex_index_map, vertex_index) \ |
| BOOST_BGL_ONE_PARAM_CREF(vertex_index1_map, vertex_index1) \ |
| BOOST_BGL_ONE_PARAM_CREF(vertex_index2_map, vertex_index2) \ |
| BOOST_BGL_ONE_PARAM_CREF(visitor, graph_visitor) \ |
| BOOST_BGL_ONE_PARAM_CREF(distance_compare, distance_compare) \ |
| BOOST_BGL_ONE_PARAM_CREF(distance_combine, distance_combine) \ |
| BOOST_BGL_ONE_PARAM_CREF(distance_inf, distance_inf) \ |
| BOOST_BGL_ONE_PARAM_CREF(distance_zero, distance_zero) \ |
| BOOST_BGL_ONE_PARAM_CREF(edge_copy, edge_copy) \ |
| BOOST_BGL_ONE_PARAM_CREF(vertex_copy, vertex_copy) \ |
| BOOST_BGL_ONE_PARAM_REF(buffer, buffer_param) \ |
| BOOST_BGL_ONE_PARAM_CREF(orig_to_copy, orig_to_copy) \ |
| BOOST_BGL_ONE_PARAM_CREF(isomorphism_map, vertex_isomorphism) \ |
| BOOST_BGL_ONE_PARAM_CREF(vertex_invariant, vertex_invariant) \ |
| BOOST_BGL_ONE_PARAM_CREF(vertex_invariant1, vertex_invariant1) \ |
| BOOST_BGL_ONE_PARAM_CREF(vertex_invariant2, vertex_invariant2) \ |
| BOOST_BGL_ONE_PARAM_CREF(vertex_max_invariant, vertex_max_invariant) \ |
| BOOST_BGL_ONE_PARAM_CREF(polling, polling) \ |
| BOOST_BGL_ONE_PARAM_CREF(lookahead, lookahead) \ |
| BOOST_BGL_ONE_PARAM_CREF(in_parallel, in_parallel) \ |
| BOOST_BGL_ONE_PARAM_CREF(displacement_map, vertex_displacement) \ |
| BOOST_BGL_ONE_PARAM_CREF(attractive_force, attractive_force) \ |
| BOOST_BGL_ONE_PARAM_CREF(repulsive_force, repulsive_force) \ |
| BOOST_BGL_ONE_PARAM_CREF(force_pairs, force_pairs) \ |
| BOOST_BGL_ONE_PARAM_CREF(cooling, cooling) \ |
| BOOST_BGL_ONE_PARAM_CREF(iterations, iterations) \ |
| BOOST_BGL_ONE_PARAM_CREF(diameter_range, diameter_range) \ |
| BOOST_BGL_ONE_PARAM_CREF(learning_constant_range, learning_constant_range) \ |
| BOOST_BGL_ONE_PARAM_CREF(vertices_equivalent, vertices_equivalent) \ |
| BOOST_BGL_ONE_PARAM_CREF(edges_equivalent, edges_equivalent) |
| |
| template <typename T, typename Tag, typename Base = no_property> |
| struct bgl_named_params : public Base |
| { |
| typedef bgl_named_params self; |
| typedef Base next_type; |
| typedef Tag tag_type; |
| typedef T value_type; |
| bgl_named_params(T v = T()) : m_value(v) { } |
| bgl_named_params(T v, const Base& b) : Base(b), m_value(v) { } |
| T m_value; |
| |
| #define BOOST_BGL_ONE_PARAM_REF(name, key) \ |
| template <typename PType> \ |
| bgl_named_params<boost::reference_wrapper<PType>, BOOST_PP_CAT(key, _t), self> \ |
| name(PType& p) const { \ |
| typedef bgl_named_params<boost::reference_wrapper<PType>, BOOST_PP_CAT(key, _t), self> Params; \ |
| return Params(boost::ref(p), *this); \ |
| } \ |
| |
| #define BOOST_BGL_ONE_PARAM_CREF(name, key) \ |
| template <typename PType> \ |
| bgl_named_params<PType, BOOST_PP_CAT(key, _t), self> \ |
| name(const PType& p) const { \ |
| typedef bgl_named_params<PType, BOOST_PP_CAT(key, _t), self> Params; \ |
| return Params(p, *this); \ |
| } \ |
| |
| BOOST_BGL_DECLARE_NAMED_PARAMS |
| |
| #undef BOOST_BGL_ONE_PARAM_REF |
| #undef BOOST_BGL_ONE_PARAM_CREF |
| |
| // Duplicate |
| template <typename PType> |
| bgl_named_params<PType, vertex_color_t, self> |
| vertex_color_map(const PType& p) const {return this->color_map(p);} |
| }; |
| |
| #define BOOST_BGL_ONE_PARAM_REF(name, key) \ |
| template <typename PType> \ |
| bgl_named_params<boost::reference_wrapper<PType>, BOOST_PP_CAT(key, _t)> \ |
| name(PType& p) { \ |
| typedef bgl_named_params<boost::reference_wrapper<PType>, BOOST_PP_CAT(key, _t)> Params; \ |
| return Params(boost::ref(p)); \ |
| } \ |
| |
| #define BOOST_BGL_ONE_PARAM_CREF(name, key) \ |
| template <typename PType> \ |
| bgl_named_params<PType, BOOST_PP_CAT(key, _t)> \ |
| name(const PType& p) { \ |
| typedef bgl_named_params<PType, BOOST_PP_CAT(key, _t)> Params; \ |
| return Params(p); \ |
| } \ |
| |
| BOOST_BGL_DECLARE_NAMED_PARAMS |
| |
| #undef BOOST_BGL_ONE_PARAM_REF |
| #undef BOOST_BGL_ONE_PARAM_CREF |
| |
| // Duplicate |
| template <typename PType> |
| bgl_named_params<PType, vertex_color_t> |
| vertex_color_map(const PType& p) {return color_map(p);} |
| |
| namespace detail { |
| struct unused_tag_type {}; |
| } |
| typedef bgl_named_params<char, detail::unused_tag_type> no_named_parameters; |
| |
| //=========================================================================== |
| // Functions for extracting parameters from bgl_named_params |
| |
| template <class Tag1, class Tag2, class T1, class Base> |
| inline |
| typename property_value< bgl_named_params<T1,Tag1,Base>, Tag2>::type |
| get_param(const bgl_named_params<T1,Tag1,Base>& p, Tag2 tag2) |
| { |
| enum { match = detail::same_property<Tag1,Tag2>::value }; |
| typedef typename |
| property_value< bgl_named_params<T1,Tag1,Base>, Tag2>::type T2; |
| T2* t2 = 0; |
| typedef detail::property_value_dispatch<match> Dispatcher; |
| return Dispatcher::const_get_value(p, t2, tag2); |
| } |
| |
| |
| namespace detail { |
| // MSVC++ workaround |
| template <class Param> |
| struct choose_param_helper { |
| template <class Default> struct result { typedef Param type; }; |
| template <typename Default> |
| static const Param& apply(const Param& p, const Default&) { return p; } |
| }; |
| template <> |
| struct choose_param_helper<error_property_not_found> { |
| template <class Default> struct result { typedef Default type; }; |
| template <typename Default> |
| static const Default& apply(const error_property_not_found&, const Default& d) |
| { return d; } |
| }; |
| } // namespace detail |
| |
| template <class P, class Default> |
| const typename detail::choose_param_helper<P>::template result<Default>::type& |
| choose_param(const P& param, const Default& d) { |
| return detail::choose_param_helper<P>::apply(param, d); |
| } |
| |
| template <typename T> |
| inline bool is_default_param(const T&) { return false; } |
| |
| inline bool is_default_param(const detail::error_property_not_found&) |
| { return true; } |
| |
| namespace detail { |
| |
| struct choose_parameter { |
| template <class P, class Graph, class Tag> |
| struct bind_ { |
| typedef const P& const_result_type; |
| typedef const P& result_type; |
| typedef P type; |
| }; |
| |
| template <class P, class Graph, class Tag> |
| static typename bind_<P, Graph, Tag>::const_result_type |
| const_apply(const P& p, const Graph&, Tag&) |
| { return p; } |
| |
| template <class P, class Graph, class Tag> |
| static typename bind_<P, Graph, Tag>::result_type |
| apply(const P& p, Graph&, Tag&) |
| { return p; } |
| }; |
| |
| struct choose_default_param { |
| template <class P, class Graph, class Tag> |
| struct bind_ { |
| typedef typename property_map<Graph, Tag>::type |
| result_type; |
| typedef typename property_map<Graph, Tag>::const_type |
| const_result_type; |
| typedef typename property_map<Graph, Tag>::const_type |
| type; |
| }; |
| |
| template <class P, class Graph, class Tag> |
| static typename bind_<P, Graph, Tag>::const_result_type |
| const_apply(const P&, const Graph& g, Tag tag) { |
| return get(tag, g); |
| } |
| template <class P, class Graph, class Tag> |
| static typename bind_<P, Graph, Tag>::result_type |
| apply(const P&, Graph& g, Tag tag) { |
| return get(tag, g); |
| } |
| }; |
| |
| template <class Param> |
| struct choose_property_map { |
| typedef choose_parameter type; |
| }; |
| template <> |
| struct choose_property_map<detail::error_property_not_found> { |
| typedef choose_default_param type; |
| }; |
| |
| template <class Param, class Graph, class Tag> |
| struct choose_pmap_helper { |
| typedef typename choose_property_map<Param>::type Selector; |
| typedef typename Selector:: template bind_<Param, Graph, Tag> Bind; |
| typedef Bind type; |
| typedef typename Bind::result_type result_type; |
| typedef typename Bind::const_result_type const_result_type; |
| typedef typename Bind::type result; |
| }; |
| |
| // used in the max-flow algorithms |
| template <class Graph, class P, class T, class R> |
| struct edge_capacity_value |
| { |
| typedef bgl_named_params<P, T, R> Params; |
| typedef typename property_value< Params, edge_capacity_t>::type Param; |
| typedef typename detail::choose_pmap_helper<Param, Graph, |
| edge_capacity_t>::result CapacityEdgeMap; |
| typedef typename property_traits<CapacityEdgeMap>::value_type type; |
| }; |
| |
| } // namespace detail |
| |
| |
| // Use this function instead of choose_param() when you want |
| // to avoid requiring get(tag, g) when it is not used. |
| template <typename Param, typename Graph, typename PropertyTag> |
| typename |
| detail::choose_pmap_helper<Param,Graph,PropertyTag>::const_result_type |
| choose_const_pmap(const Param& p, const Graph& g, PropertyTag tag) |
| { |
| typedef typename |
| detail::choose_pmap_helper<Param,Graph,PropertyTag>::Selector Choice; |
| return Choice::const_apply(p, g, tag); |
| } |
| |
| template <typename Param, typename Graph, typename PropertyTag> |
| typename detail::choose_pmap_helper<Param,Graph,PropertyTag>::result_type |
| choose_pmap(const Param& p, Graph& g, PropertyTag tag) |
| { |
| typedef typename |
| detail::choose_pmap_helper<Param,Graph,PropertyTag>::Selector Choice; |
| return Choice::apply(p, g, tag); |
| } |
| |
| // Declare all new tags |
| namespace graph { |
| namespace keywords { |
| #define BOOST_BGL_ONE_PARAM_REF(name, key) BOOST_PARAMETER_NAME(name) |
| #define BOOST_BGL_ONE_PARAM_CREF(name, key) BOOST_PARAMETER_NAME(name) |
| BOOST_BGL_DECLARE_NAMED_PARAMS |
| #undef BOOST_BGL_ONE_PARAM_REF |
| #undef BOOST_BGL_ONE_PARAM_CREF |
| } |
| } |
| |
| namespace detail { |
| template <typename Tag> struct convert_one_keyword {}; |
| #define BOOST_BGL_ONE_PARAM_REF(name, key) \ |
| template <> \ |
| struct convert_one_keyword<BOOST_PP_CAT(key, _t)> { \ |
| typedef boost::graph::keywords::tag::name type; \ |
| }; |
| #define BOOST_BGL_ONE_PARAM_CREF(name, key) BOOST_BGL_ONE_PARAM_REF(name, key) |
| BOOST_BGL_DECLARE_NAMED_PARAMS |
| #undef BOOST_BGL_ONE_PARAM_REF |
| #undef BOOST_BGL_ONE_PARAM_CREF |
| |
| template <typename T> |
| struct convert_bgl_params_to_boost_parameter { |
| typedef typename convert_one_keyword<typename T::tag_type>::type new_kw; |
| typedef boost::parameter::aux::tagged_argument<new_kw, const typename T::value_type> tagged_arg_type; |
| typedef convert_bgl_params_to_boost_parameter<typename T::next_type> rest_conv; |
| typedef boost::parameter::aux::arg_list<tagged_arg_type, typename rest_conv::type> type; |
| static type conv(const T& x) { |
| return type(tagged_arg_type(x.m_value), rest_conv::conv(x)); |
| } |
| }; |
| |
| template <typename P, typename R> |
| struct convert_bgl_params_to_boost_parameter<bgl_named_params<P, int, R> > { |
| typedef convert_bgl_params_to_boost_parameter<R> rest_conv; |
| typedef typename rest_conv::type type; |
| static type conv(const bgl_named_params<P, int, R>& x) { |
| return rest_conv::conv(x); |
| } |
| }; |
| |
| template <> |
| struct convert_bgl_params_to_boost_parameter<boost::no_property> { |
| typedef boost::parameter::aux::empty_arg_list type; |
| static type conv(const boost::no_property&) {return type();} |
| }; |
| |
| template <> |
| struct convert_bgl_params_to_boost_parameter<boost::no_named_parameters> { |
| typedef boost::parameter::aux::empty_arg_list type; |
| static type conv(const boost::no_property&) {return type();} |
| }; |
| |
| struct bgl_parameter_not_found_type {}; |
| |
| template <typename ArgPack, typename KeywordType> |
| struct parameter_exists : boost::mpl::not_<boost::is_same<typename boost::parameter::binding<ArgPack, KeywordType, bgl_parameter_not_found_type>::type, bgl_parameter_not_found_type> > {}; |
| } |
| |
| #define BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(old_type, old_var) \ |
| typedef typename boost::detail::convert_bgl_params_to_boost_parameter<old_type>::type arg_pack_type; \ |
| arg_pack_type arg_pack = boost::detail::convert_bgl_params_to_boost_parameter<old_type>::conv(old_var); |
| |
| namespace detail { |
| |
| template <typename ArgType, typename Prop, typename Graph, bool Exists> |
| struct override_const_property_t { |
| typedef ArgType result_type; |
| result_type operator()(const Graph& g, const typename boost::add_reference<ArgType>::type a) const {return a;} |
| }; |
| |
| template <typename ArgType, typename Prop, typename Graph> |
| struct override_const_property_t<ArgType, Prop, Graph, false> { |
| typedef typename boost::property_map<Graph, Prop>::const_type result_type; |
| result_type operator()(const Graph& g, const ArgType& a) const {return get(Prop(), g);} |
| }; |
| |
| template <typename ArgPack, typename Tag, typename Prop, typename Graph> |
| typename override_const_property_t< |
| typename boost::parameter::value_type<ArgPack, Tag, int>::type, |
| Prop, |
| Graph, |
| boost::detail::parameter_exists<ArgPack, Tag>::value |
| >::result_type |
| override_const_property(const ArgPack& ap, const boost::parameter::keyword<Tag>& t, const Graph& g, Prop prop) { |
| return override_const_property_t< |
| typename boost::parameter::value_type<ArgPack, Tag, int>::type, |
| Prop, |
| Graph, |
| boost::detail::parameter_exists<ArgPack, Tag>::value |
| >()(g, ap[t | 0]); |
| } |
| |
| template <typename ArgType, typename Prop, typename Graph, bool Exists> |
| struct override_property_t { |
| typedef ArgType result_type; |
| result_type operator()(const Graph& g, const typename boost::add_reference<ArgType>::type a) const {return a;} |
| }; |
| |
| template <typename ArgType, typename Prop, typename Graph> |
| struct override_property_t<ArgType, Prop, Graph, false> { |
| typedef typename boost::property_map<Graph, Prop>::type result_type; |
| result_type operator()(const Graph& g, const ArgType& a) const {return get(Prop(), g);} |
| }; |
| |
| template <typename ArgPack, typename Tag, typename Prop, typename Graph> |
| typename override_property_t< |
| typename boost::parameter::value_type<ArgPack, Tag, int>::type, |
| Prop, |
| Graph, |
| boost::detail::parameter_exists<ArgPack, Tag>::value |
| >::result_type |
| override_property(const ArgPack& ap, const boost::parameter::keyword<Tag>& t, const Graph& g, Prop prop) { |
| return override_property_t< |
| typename boost::parameter::value_type<ArgPack, Tag, int>::type, |
| Prop, |
| Graph, |
| boost::detail::parameter_exists<ArgPack, Tag>::value |
| >()(g, ap[t | 0]); |
| } |
| |
| } |
| |
| namespace detail { |
| |
| template <bool Exists, typename Graph, typename ArgPack, typename Value, typename PM> |
| struct color_map_maker_helper { |
| typedef PM map_type; |
| static PM make_map(const Graph&, Value, const PM& pm, const ArgPack&) { |
| return pm; |
| } |
| }; |
| |
| template <typename Graph, typename ArgPack, typename Value, typename PM> |
| struct color_map_maker_helper<false, Graph, ArgPack, Value, PM> { |
| typedef typename boost::remove_const< |
| typename override_const_property_t< |
| typename boost::parameter::value_type< |
| ArgPack, boost::graph::keywords::tag::vertex_index_map, int>::type, |
| boost::vertex_index_t, |
| Graph, |
| boost::detail::parameter_exists< |
| ArgPack, boost::graph::keywords::tag::vertex_index_map>::value |
| >::result_type>::type vi_map_type; |
| typedef |
| boost::shared_array_property_map<Value, vi_map_type> |
| map_type; |
| static map_type make_map(const Graph& g, |
| Value v, |
| const PM&, |
| const ArgPack& ap) { |
| return make_shared_array_property_map( |
| num_vertices(g), |
| v, |
| override_const_property( |
| ap, |
| boost::graph::keywords::_vertex_index_map, |
| g, vertex_index)); |
| } |
| }; |
| |
| template <typename Graph, typename ArgPack> |
| struct color_map_maker { |
| BOOST_STATIC_CONSTANT( |
| bool, |
| has_color_map = |
| (parameter_exists<ArgPack, boost::graph::keywords::tag::color_map> |
| ::value)); |
| typedef color_map_maker_helper<has_color_map, Graph, ArgPack, default_color_type, |
| typename boost::remove_const< |
| typename boost::parameter::value_type< |
| ArgPack, |
| boost::graph::keywords::tag::color_map, |
| int |
| >::type |
| >::type> helper; |
| typedef typename helper::map_type map_type; |
| static map_type make_map(const Graph& g, const ArgPack& ap) { |
| return helper::make_map(g, white_color, ap[boost::graph::keywords::_color_map | 0], ap); |
| } |
| }; |
| |
| } |
| |
| } // namespace boost |
| |
| #undef BOOST_BGL_DECLARE_NAMED_PARAMS |
| |
| #endif // BOOST_GRAPH_NAMED_FUNCTION_PARAMS_HPP |
