Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 09:37:34 

0001 //=======================================================================
0002 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0003 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //=======================================================================
0009 
0010 #ifndef BOOST_GRAPH_NAMED_FUNCTION_PARAMS_HPP
0011 #define BOOST_GRAPH_NAMED_FUNCTION_PARAMS_HPP
0012 
0013 #include <functional>
0014 #include <vector>
0015 #include <boost/limits.hpp>
0016 #include <boost/core/enable_if.hpp>
0017 #include <boost/core/ref.hpp>
0018 #include <boost/utility/result_of.hpp>
0019 #include <boost/preprocessor.hpp>
0020 #include <boost/parameter/is_argument_pack.hpp>
0021 #include <boost/parameter/name.hpp>
0022 #include <boost/parameter/binding.hpp>
0023 #include <boost/type_traits.hpp>
0024 #include <boost/mpl/bool.hpp>
0025 #include <boost/mpl/has_key.hpp>
0026 #include <boost/graph/properties.hpp>
0027 #include <boost/graph/detail/d_ary_heap.hpp>
0028 #include <boost/property_map/property_map.hpp>
0029 #include <boost/property_map/shared_array_property_map.hpp>
0030 
0031 namespace boost
0032 {
0033 
0034 struct parity_map_t
0035 {
0036 };
0037 struct vertex_assignment_map_t
0038 {
0039 };
0040 struct distance_compare_t
0041 {
0042 };
0043 struct distance_combine_t
0044 {
0045 };
0046 struct distance_inf_t
0047 {
0048 };
0049 struct distance_zero_t
0050 {
0051 };
0052 struct buffer_param_t
0053 {
0054 };
0055 struct edge_copy_t
0056 {
0057 };
0058 struct vertex_copy_t
0059 {
0060 };
0061 struct vertex_isomorphism_t
0062 {
0063 };
0064 struct vertex_invariant_t
0065 {
0066 };
0067 struct vertex_invariant1_t
0068 {
0069 };
0070 struct vertex_invariant2_t
0071 {
0072 };
0073 struct edge_compare_t
0074 {
0075 };
0076 struct vertex_max_invariant_t
0077 {
0078 };
0079 struct orig_to_copy_t
0080 {
0081 };
0082 struct root_vertex_t
0083 {
0084 };
0085 struct polling_t
0086 {
0087 };
0088 struct lookahead_t
0089 {
0090 };
0091 struct in_parallel_t
0092 {
0093 };
0094 struct attractive_force_t
0095 {
0096 };
0097 struct repulsive_force_t
0098 {
0099 };
0100 struct force_pairs_t
0101 {
0102 };
0103 struct cooling_t
0104 {
0105 };
0106 struct vertex_displacement_t
0107 {
0108 };
0109 struct iterations_t
0110 {
0111 };
0112 struct diameter_range_t
0113 {
0114 };
0115 struct learning_constant_range_t
0116 {
0117 };
0118 struct vertices_equivalent_t
0119 {
0120 };
0121 struct edges_equivalent_t
0122 {
0123 };
0124 struct index_in_heap_map_t
0125 {
0126 };
0127 struct max_priority_queue_t
0128 {
0129 };
0130 
0131 #define BOOST_BGL_DECLARE_NAMED_PARAMS                                         \
0132     BOOST_BGL_ONE_PARAM_CREF(weight_map, edge_weight)                          \
0133     BOOST_BGL_ONE_PARAM_CREF(weight_map2, edge_weight2)                        \
0134     BOOST_BGL_ONE_PARAM_CREF(distance_map, vertex_distance)                    \
0135     BOOST_BGL_ONE_PARAM_CREF(distance_map2, vertex_distance2)                  \
0136     BOOST_BGL_ONE_PARAM_CREF(predecessor_map, vertex_predecessor)              \
0137     BOOST_BGL_ONE_PARAM_CREF(rank_map, vertex_rank)                            \
0138     BOOST_BGL_ONE_PARAM_CREF(root_map, vertex_root)                            \
0139     BOOST_BGL_ONE_PARAM_CREF(root_vertex, root_vertex)                         \
0140     BOOST_BGL_ONE_PARAM_CREF(edge_centrality_map, edge_centrality)             \
0141     BOOST_BGL_ONE_PARAM_CREF(centrality_map, vertex_centrality)                \
0142     BOOST_BGL_ONE_PARAM_CREF(parity_map, parity_map)                           \
0143     BOOST_BGL_ONE_PARAM_CREF(color_map, vertex_color)                          \
0144     BOOST_BGL_ONE_PARAM_CREF(edge_color_map, edge_color)                       \
0145     BOOST_BGL_ONE_PARAM_CREF(capacity_map, edge_capacity)                      \
0146     BOOST_BGL_ONE_PARAM_CREF(residual_capacity_map, edge_residual_capacity)    \
0147     BOOST_BGL_ONE_PARAM_CREF(reverse_edge_map, edge_reverse)                   \
0148     BOOST_BGL_ONE_PARAM_CREF(discover_time_map, vertex_discover_time)          \
0149     BOOST_BGL_ONE_PARAM_CREF(lowpoint_map, vertex_lowpoint)                    \
0150     BOOST_BGL_ONE_PARAM_CREF(vertex_index_map, vertex_index)                   \
0151     BOOST_BGL_ONE_PARAM_CREF(vertex_index1_map, vertex_index1)                 \
0152     BOOST_BGL_ONE_PARAM_CREF(vertex_index2_map, vertex_index2)                 \
0153     BOOST_BGL_ONE_PARAM_CREF(vertex_assignment_map, vertex_assignment_map)     \
0154     BOOST_BGL_ONE_PARAM_CREF(visitor, graph_visitor)                           \
0155     BOOST_BGL_ONE_PARAM_CREF(distance_compare, distance_compare)               \
0156     BOOST_BGL_ONE_PARAM_CREF(distance_combine, distance_combine)               \
0157     BOOST_BGL_ONE_PARAM_CREF(distance_inf, distance_inf)                       \
0158     BOOST_BGL_ONE_PARAM_CREF(distance_zero, distance_zero)                     \
0159     BOOST_BGL_ONE_PARAM_CREF(edge_copy, edge_copy)                             \
0160     BOOST_BGL_ONE_PARAM_CREF(vertex_copy, vertex_copy)                         \
0161     BOOST_BGL_ONE_PARAM_REF(buffer, buffer_param)                              \
0162     BOOST_BGL_ONE_PARAM_CREF(orig_to_copy, orig_to_copy)                       \
0163     BOOST_BGL_ONE_PARAM_CREF(isomorphism_map, vertex_isomorphism)              \
0164     BOOST_BGL_ONE_PARAM_CREF(vertex_invariant, vertex_invariant)               \
0165     BOOST_BGL_ONE_PARAM_CREF(vertex_invariant1, vertex_invariant1)             \
0166     BOOST_BGL_ONE_PARAM_CREF(vertex_invariant2, vertex_invariant2)             \
0167     BOOST_BGL_ONE_PARAM_CREF(vertex_max_invariant, vertex_max_invariant)       \
0168     BOOST_BGL_ONE_PARAM_CREF(polling, polling)                                 \
0169     BOOST_BGL_ONE_PARAM_CREF(lookahead, lookahead)                             \
0170     BOOST_BGL_ONE_PARAM_CREF(in_parallel, in_parallel)                         \
0171     BOOST_BGL_ONE_PARAM_CREF(displacement_map, vertex_displacement)            \
0172     BOOST_BGL_ONE_PARAM_CREF(attractive_force, attractive_force)               \
0173     BOOST_BGL_ONE_PARAM_CREF(repulsive_force, repulsive_force)                 \
0174     BOOST_BGL_ONE_PARAM_CREF(force_pairs, force_pairs)                         \
0175     BOOST_BGL_ONE_PARAM_CREF(cooling, cooling)                                 \
0176     BOOST_BGL_ONE_PARAM_CREF(iterations, iterations)                           \
0177     BOOST_BGL_ONE_PARAM_CREF(diameter_range, diameter_range)                   \
0178     BOOST_BGL_ONE_PARAM_CREF(learning_constant_range, learning_constant_range) \
0179     BOOST_BGL_ONE_PARAM_CREF(vertices_equivalent, vertices_equivalent)         \
0180     BOOST_BGL_ONE_PARAM_CREF(edges_equivalent, edges_equivalent)               \
0181     BOOST_BGL_ONE_PARAM_CREF(index_in_heap_map, index_in_heap_map)             \
0182     BOOST_BGL_ONE_PARAM_REF(max_priority_queue, max_priority_queue)
0183 
0184 template < typename T, typename Tag, typename Base = no_property >
0185 struct bgl_named_params
0186 {
0187     typedef bgl_named_params self;
0188     typedef Base next_type;
0189     typedef Tag tag_type;
0190     typedef T value_type;
0191     bgl_named_params(T v = T()) : m_value(v) {}
0192     bgl_named_params(T v, const Base& b) : m_value(v), m_base(b) {}
0193     T m_value;
0194     Base m_base;
0195 
0196 #define BOOST_BGL_ONE_PARAM_REF(name, key)                           \
0197     template < typename PType >                                      \
0198     bgl_named_params< boost::reference_wrapper< PType >,             \
0199         BOOST_PP_CAT(key, _t), self >                                \
0200     name(PType& p) const                                             \
0201     {                                                                \
0202         typedef bgl_named_params< boost::reference_wrapper< PType >, \
0203             BOOST_PP_CAT(key, _t), self >                            \
0204             Params;                                                  \
0205         return Params(boost::ref(p), *this);                         \
0206     }
0207 
0208 #define BOOST_BGL_ONE_PARAM_CREF(name, key)                                    \
0209     template < typename PType >                                                \
0210     bgl_named_params< PType, BOOST_PP_CAT(key, _t), self > name(               \
0211         const PType& p) const                                                  \
0212     {                                                                          \
0213         typedef bgl_named_params< PType, BOOST_PP_CAT(key, _t), self > Params; \
0214         return Params(p, *this);                                               \
0215     }
0216 
0217     BOOST_BGL_DECLARE_NAMED_PARAMS
0218 
0219 #undef BOOST_BGL_ONE_PARAM_REF
0220 #undef BOOST_BGL_ONE_PARAM_CREF
0221 
0222     // Duplicate
0223     template < typename PType >
0224     bgl_named_params< PType, vertex_color_t, self > vertex_color_map(
0225         const PType& p) const
0226     {
0227         return this->color_map(p);
0228     }
0229 };
0230 
0231 #define BOOST_BGL_ONE_PARAM_REF(name, key)                           \
0232     template < typename PType >                                      \
0233     bgl_named_params< boost::reference_wrapper< PType >,             \
0234         BOOST_PP_CAT(key, _t) >                                      \
0235     name(PType& p)                                                   \
0236     {                                                                \
0237         typedef bgl_named_params< boost::reference_wrapper< PType >, \
0238             BOOST_PP_CAT(key, _t) >                                  \
0239             Params;                                                  \
0240         return Params(boost::ref(p));                                \
0241     }
0242 
0243 #define BOOST_BGL_ONE_PARAM_CREF(name, key)                               \
0244     template < typename PType >                                           \
0245     bgl_named_params< PType, BOOST_PP_CAT(key, _t) > name(const PType& p) \
0246     {                                                                     \
0247         typedef bgl_named_params< PType, BOOST_PP_CAT(key, _t) > Params;  \
0248         return Params(p);                                                 \
0249     }
0250 
0251 BOOST_BGL_DECLARE_NAMED_PARAMS
0252 
0253 #undef BOOST_BGL_ONE_PARAM_REF
0254 #undef BOOST_BGL_ONE_PARAM_CREF
0255 
0256 // Duplicate
0257 template < typename PType >
0258 bgl_named_params< PType, vertex_color_t > vertex_color_map(const PType& p)
0259 {
0260     return color_map(p);
0261 }
0262 
0263 namespace detail
0264 {
0265     struct unused_tag_type
0266     {
0267     };
0268 }
0269 typedef bgl_named_params< char, detail::unused_tag_type > no_named_parameters;
0270 
0271 //===========================================================================
0272 // Functions for extracting parameters from bgl_named_params
0273 
0274 template < typename Tag, typename Args > struct lookup_named_param
0275 {
0276 };
0277 
0278 template < typename T, typename Tag, typename Base >
0279 struct lookup_named_param< Tag, bgl_named_params< T, Tag, Base > >
0280 {
0281     typedef T type;
0282     static const T& get(const bgl_named_params< T, Tag, Base >& p)
0283     {
0284         return p.m_value;
0285     }
0286 };
0287 
0288 template < typename Tag1, typename T, typename Tag, typename Base >
0289 struct lookup_named_param< Tag1, bgl_named_params< T, Tag, Base > >
0290 {
0291     typedef typename lookup_named_param< Tag1, Base >::type type;
0292     static const type& get(const bgl_named_params< T, Tag, Base >& p)
0293     {
0294         return lookup_named_param< Tag1, Base >::get(p.m_base);
0295     }
0296 };
0297 
0298 template < typename Tag, typename Args, typename Def >
0299 struct lookup_named_param_def
0300 {
0301     typedef Def type;
0302     static const Def& get(const Args&, const Def& def) { return def; }
0303 };
0304 
0305 template < typename T, typename Tag, typename Base, typename Def >
0306 struct lookup_named_param_def< Tag, bgl_named_params< T, Tag, Base >, Def >
0307 {
0308     typedef T type;
0309     static const type& get(
0310         const bgl_named_params< T, Tag, Base >& p, const Def&)
0311     {
0312         return p.m_value;
0313     }
0314 };
0315 
0316 template < typename Tag1, typename T, typename Tag, typename Base,
0317     typename Def >
0318 struct lookup_named_param_def< Tag1, bgl_named_params< T, Tag, Base >, Def >
0319 {
0320     typedef typename lookup_named_param_def< Tag1, Base, Def >::type type;
0321     static const type& get(
0322         const bgl_named_params< T, Tag, Base >& p, const Def& def)
0323     {
0324         return lookup_named_param_def< Tag1, Base, Def >::get(p.m_base, def);
0325     }
0326 };
0327 
0328 struct param_not_found
0329 {
0330 };
0331 static param_not_found g_param_not_found;
0332 
0333 template < typename Tag, typename Args >
0334 struct get_param_type : lookup_named_param_def< Tag, Args, param_not_found >
0335 {
0336 };
0337 
0338 template < class Tag, typename Args >
0339 inline const typename lookup_named_param_def< Tag, Args,
0340     param_not_found >::type&
0341 get_param(const Args& p, Tag)
0342 {
0343     return lookup_named_param_def< Tag, Args, param_not_found >::get(
0344         p, g_param_not_found);
0345 }
0346 
0347 template < class P, class Default >
0348 const P& choose_param(const P& param, const Default&)
0349 {
0350     return param;
0351 }
0352 
0353 template < class Default >
0354 Default choose_param(const param_not_found&, const Default& d)
0355 {
0356     return d;
0357 }
0358 
0359 template < typename T > inline bool is_default_param(const T&) { return false; }
0360 
0361 inline bool is_default_param(const param_not_found&) { return true; }
0362 
0363 namespace detail
0364 {
0365     template < typename T > struct const_type_as_type
0366     {
0367         typedef typename T::const_type type;
0368     };
0369 } // namespace detail
0370 
0371 // Use this function instead of choose_param() when you want
0372 // to avoid requiring get(tag, g) when it is not used.
0373 namespace detail
0374 {
0375     template < typename GraphIsConst, typename Graph, typename Param,
0376         typename Tag >
0377     struct choose_impl_result
0378     : boost::mpl::eval_if< boost::is_same< Param, param_not_found >,
0379           boost::mpl::eval_if< GraphIsConst,
0380               detail::const_type_as_type< property_map< Graph, Tag > >,
0381               property_map< Graph, Tag > >,
0382           boost::mpl::identity< Param > >
0383     {
0384     };
0385 
0386     // Parameters of f are (GraphIsConst, Graph, Param, Tag)
0387     template < bool Found > struct choose_impl_helper;
0388 
0389     template <> struct choose_impl_helper< false >
0390     {
0391         template < typename Param, typename Graph, typename PropertyTag >
0392         static
0393             typename property_map< typename boost::remove_const< Graph >::type,
0394                 PropertyTag >::const_type
0395             f(boost::mpl::true_, const Graph& g, const Param&, PropertyTag tag)
0396         {
0397             return get(tag, g);
0398         }
0399 
0400         template < typename Param, typename Graph, typename PropertyTag >
0401         static
0402             typename property_map< typename boost::remove_const< Graph >::type,
0403                 PropertyTag >::type
0404             f(boost::mpl::false_, Graph& g, const Param&, PropertyTag tag)
0405         {
0406             return get(tag, g);
0407         }
0408     };
0409 
0410     template <> struct choose_impl_helper< true >
0411     {
0412         template < typename GraphIsConst, typename Param, typename Graph,
0413             typename PropertyTag >
0414         static Param f(GraphIsConst, const Graph&, const Param& p, PropertyTag)
0415         {
0416             return p;
0417         }
0418     };
0419 }
0420 
0421 template < typename Param, typename Graph, typename PropertyTag >
0422 typename detail::choose_impl_result< boost::mpl::true_, Graph, Param,
0423     PropertyTag >::type
0424 choose_const_pmap(const Param& p, const Graph& g, PropertyTag tag)
0425 {
0426     return detail::choose_impl_helper< !boost::is_same< Param,
0427         param_not_found >::value >::f(boost::mpl::true_(), g, p, tag);
0428 }
0429 
0430 template < typename Param, typename Graph, typename PropertyTag >
0431 typename detail::choose_impl_result< boost::mpl::false_, Graph, Param,
0432     PropertyTag >::type
0433 choose_pmap(const Param& p, Graph& g, PropertyTag tag)
0434 {
0435     return detail::choose_impl_helper< !boost::is_same< Param,
0436         param_not_found >::value >::f(boost::mpl::false_(), g, p, tag);
0437 }
0438 
0439 namespace detail
0440 {
0441 
0442     // used in the max-flow algorithms
0443     template < class Graph, class P, class T, class R >
0444     struct edge_capacity_value
0445     {
0446         typedef bgl_named_params< P, T, R > Params;
0447         typedef typename detail::choose_impl_result< boost::mpl::true_, Graph,
0448             typename get_param_type< edge_capacity_t, Params >::type,
0449             edge_capacity_t >::type CapacityEdgeMap;
0450         typedef typename property_traits< CapacityEdgeMap >::value_type type;
0451     };
0452     // used in the max-flow algorithms
0453     template < class Graph, class P, class T, class R > struct edge_weight_value
0454     {
0455         typedef bgl_named_params< P, T, R > Params;
0456         typedef typename detail::choose_impl_result< boost::mpl::true_, Graph,
0457             typename get_param_type< edge_weight_t, Params >::type,
0458             edge_weight_t >::type WeightMap;
0459         typedef typename property_traits< WeightMap >::value_type type;
0460     };
0461 
0462 }
0463 
0464 // Declare all new tags
0465 namespace graph
0466 {
0467     namespace keywords
0468     {
0469 #define BOOST_BGL_ONE_PARAM_REF(name, key) BOOST_PARAMETER_NAME(name)
0470 #define BOOST_BGL_ONE_PARAM_CREF(name, key) BOOST_PARAMETER_NAME(name)
0471         BOOST_BGL_DECLARE_NAMED_PARAMS
0472 #undef BOOST_BGL_ONE_PARAM_REF
0473 #undef BOOST_BGL_ONE_PARAM_CREF
0474     }
0475 }
0476 
0477 namespace detail
0478 {
0479     template < typename Tag > struct convert_one_keyword
0480     {
0481     };
0482 #define BOOST_BGL_ONE_PARAM_REF(name, key)                          \
0483     template <> struct convert_one_keyword< BOOST_PP_CAT(key, _t) > \
0484     {                                                               \
0485         typedef boost::graph::keywords::tag::name type;             \
0486     };
0487 #define BOOST_BGL_ONE_PARAM_CREF(name, key) BOOST_BGL_ONE_PARAM_REF(name, key)
0488     BOOST_BGL_DECLARE_NAMED_PARAMS
0489 #undef BOOST_BGL_ONE_PARAM_REF
0490 #undef BOOST_BGL_ONE_PARAM_CREF
0491 
0492     template < typename T > struct convert_bgl_params_to_boost_parameter
0493     {
0494         typedef
0495             typename convert_one_keyword< typename T::tag_type >::type new_kw;
0496         typedef boost::parameter::aux::tagged_argument< new_kw,
0497             const typename T::value_type >
0498             tagged_arg_type;
0499         typedef convert_bgl_params_to_boost_parameter< typename T::next_type >
0500             rest_conv;
0501         typedef boost::parameter::aux::arg_list< tagged_arg_type,
0502             typename rest_conv::type >
0503             type;
0504         static type conv(const T& x)
0505         {
0506             return type(tagged_arg_type(x.m_value), rest_conv::conv(x.m_base));
0507         }
0508     };
0509 
0510     template < typename P, typename R >
0511     struct convert_bgl_params_to_boost_parameter<
0512         bgl_named_params< P, int, R > >
0513     {
0514         typedef convert_bgl_params_to_boost_parameter< R > rest_conv;
0515         typedef typename rest_conv::type type;
0516         static type conv(const bgl_named_params< P, int, R >& x)
0517         {
0518             return rest_conv::conv(x.m_base);
0519         }
0520     };
0521 
0522     template <>
0523     struct convert_bgl_params_to_boost_parameter< boost::no_property >
0524     {
0525         typedef boost::parameter::aux::empty_arg_list type;
0526         static type conv(const boost::no_property&) { return type(); }
0527     };
0528 
0529     template <>
0530     struct convert_bgl_params_to_boost_parameter< boost::no_named_parameters >
0531     {
0532         typedef boost::parameter::aux::empty_arg_list type;
0533         static type conv(const boost::no_named_parameters&) { return type(); }
0534     };
0535 
0536     struct bgl_parameter_not_found_type
0537     {
0538     };
0539 }
0540 
0541 #define BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(old_type, old_var)        \
0542     typedef typename boost::detail::convert_bgl_params_to_boost_parameter< \
0543         old_type >::type arg_pack_type;                                    \
0544     arg_pack_type arg_pack                                                 \
0545         = boost::detail::convert_bgl_params_to_boost_parameter<            \
0546             old_type >::conv(old_var);
0547 
0548 namespace detail
0549 {
0550 
0551     template < typename ArgType, typename Prop, typename Graph, bool Exists >
0552     struct override_const_property_t
0553     {
0554         typedef typename boost::remove_const< ArgType >::type result_type;
0555         result_type operator()(const Graph&, const ArgType& a) const
0556         {
0557             return a;
0558         }
0559     };
0560 
0561     template < typename ArgType, typename Prop, typename Graph >
0562     struct override_const_property_t< ArgType, Prop, Graph, false >
0563     {
0564         typedef
0565             typename boost::property_map< Graph, Prop >::const_type result_type;
0566         result_type operator()(const Graph& g, const ArgType&) const
0567         {
0568             return get(Prop(), g);
0569         }
0570     };
0571 
0572     template < typename ArgPack, typename Tag, typename Prop, typename Graph >
0573     struct override_const_property_result
0574     {
0575         typedef typename boost::mpl::has_key< ArgPack, Tag >::type
0576             _parameter_exists;
0577         typedef typename override_const_property_t<
0578             typename boost::parameter::value_type< ArgPack, Tag, int >::type,
0579             Prop, Graph, _parameter_exists::value >::result_type type;
0580     };
0581 
0582     template < typename ArgPack, typename Tag, typename Prop, typename Graph >
0583     typename override_const_property_result< ArgPack, Tag, Prop, Graph >::type
0584     override_const_property(const ArgPack& ap,
0585         const boost::parameter::keyword< Tag >& t, const Graph& g, Prop)
0586     {
0587         typedef typename boost::mpl::has_key< ArgPack, Tag >::type
0588             _parameter_exists;
0589         return override_const_property_t<
0590             typename boost::parameter::value_type< ArgPack, Tag, int >::type,
0591             Prop, Graph, _parameter_exists::value >()(g, ap[t | 0]);
0592     }
0593 
0594     template < typename ArgType, typename Prop, typename Graph, bool Exists >
0595     struct override_property_t
0596     {
0597         typedef ArgType result_type;
0598         result_type operator()(const Graph&,
0599             typename boost::add_lvalue_reference< ArgType >::type a) const
0600         {
0601             return a;
0602         }
0603     };
0604 
0605     template < typename ArgType, typename Prop, typename Graph >
0606     struct override_property_t< ArgType, Prop, Graph, false >
0607     {
0608         typedef typename boost::property_map< Graph, Prop >::type result_type;
0609         result_type operator()(const Graph& g, const ArgType&) const
0610         {
0611             return get(Prop(), g);
0612         }
0613     };
0614 
0615     template < typename ArgPack, typename Tag, typename Prop, typename Graph >
0616     struct override_property_result
0617     {
0618         typedef typename boost::mpl::has_key< ArgPack, Tag >::type
0619             _parameter_exists;
0620         typedef typename override_property_t<
0621             typename boost::parameter::value_type< ArgPack, Tag, int >::type,
0622             Prop, Graph, _parameter_exists::value >::result_type type;
0623     };
0624 
0625     template < typename ArgPack, typename Tag, typename Prop, typename Graph >
0626     typename override_property_result< ArgPack, Tag, Prop, Graph >::type
0627     override_property(const ArgPack& ap,
0628         const boost::parameter::keyword< Tag >& t, const Graph& g, Prop)
0629     {
0630         typedef typename boost::mpl::has_key< ArgPack, Tag >::type
0631             _parameter_exists;
0632         return override_property_t<
0633             typename boost::parameter::value_type< ArgPack, Tag, int >::type,
0634             Prop, Graph, _parameter_exists::value >()(g, ap[t | 0]);
0635     }
0636 
0637     template < typename F > struct make_arg_pack_type;
0638     template <> struct make_arg_pack_type< void() >
0639     {
0640         typedef boost::parameter::aux::empty_arg_list type;
0641     };
0642     template < typename K, typename A > struct make_arg_pack_type< void(K, A) >
0643     {
0644         typedef boost::parameter::aux::tagged_argument< K, A > type;
0645     };
0646 
0647 #define BOOST_GRAPH_OPENING_PART_OF_PAIR(z, i, n)                          \
0648     boost::parameter::aux::arg_list                                        \
0649         < boost::parameter::aux::tagged_argument< BOOST_PP_CAT(Keyword,    \
0650                                                       BOOST_PP_SUB(n, i)), \
0651             BOOST_PP_CAT(Arg, BOOST_PP_SUB(n, i)) >,
0652 #define BOOST_GRAPH_MAKE_PAIR_PARAM(z, i, _)                                \
0653     const boost::parameter::aux::tagged_argument< BOOST_PP_CAT(Keyword, i), \
0654         BOOST_PP_CAT(Arg, i) >& BOOST_PP_CAT(kw, i)
0655 
0656 #define BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION(z, i, _)                  \
0657     template < BOOST_PP_ENUM_PARAMS(i, typename Keyword),                 \
0658         BOOST_PP_ENUM_PARAMS(i, typename Arg) >                           \
0659     struct make_arg_pack_type< void(                                      \
0660         BOOST_PP_ENUM_PARAMS(i, Keyword), BOOST_PP_ENUM_PARAMS(i, Arg)) > \
0661     {                                                                     \
0662         typedef BOOST_PP_REPEAT(i, BOOST_GRAPH_OPENING_PART_OF_PAIR,      \
0663             BOOST_PP_DEC(i)) boost::parameter::aux::empty_arg_list        \
0664             BOOST_PP_REPEAT(i, > BOOST_PP_TUPLE_EAT(3), ~) type;          \
0665     };
0666     BOOST_PP_REPEAT_FROM_TO(2, 11, BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION, ~)
0667 #undef BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION
0668 
0669 #define BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(name, nfixed, nnamed_max)        \
0670     /* Entry point for conversion from BGL-style named parameters */          \
0671     template < BOOST_PP_ENUM_PARAMS(nfixed, typename Param)                   \
0672             BOOST_PP_COMMA_IF(nfixed) typename ArgPack >                      \
0673         typename boost::result_of< detail::BOOST_PP_CAT(name, _impl)          \
0674             < BOOST_PP_ENUM_PARAMS(nfixed, Param) >(BOOST_PP_ENUM_PARAMS(     \
0675             nfixed, Param) BOOST_PP_COMMA_IF(nfixed) const ArgPack&)          \
0676         > ::type BOOST_PP_CAT(name, _with_named_params)(                      \
0677             BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, &param)          \
0678                 BOOST_PP_COMMA_IF(nfixed) const ArgPack& arg_pack)            \
0679     {                                                                         \
0680         return detail::BOOST_PP_CAT(                                          \
0681             name, _impl)< BOOST_PP_ENUM_PARAMS(nfixed, Param) >()(            \
0682             BOOST_PP_ENUM_PARAMS(nfixed, param) BOOST_PP_COMMA_IF(nfixed)     \
0683                 arg_pack);                                                    \
0684     }                                                                         \
0685     /* Individual functions taking Boost.Parameter-style keyword arguments */ \
0686     BOOST_PP_REPEAT(BOOST_PP_INC(nnamed_max),                                 \
0687         BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONE, (name)(nfixed))
0688 
0689 #define BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONE(z, nnamed, seq) \
0690     BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONEX(                   \
0691         z, nnamed, BOOST_PP_SEQ_ELEM(0, seq), BOOST_PP_SEQ_ELEM(1, seq))
0692 
0693 #define BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONEX(z, nnamed, name, nfixed)     \
0694     template < BOOST_PP_ENUM_PARAMS_Z(z, nfixed, typename Param)               \
0695             BOOST_PP_ENUM_TRAILING_PARAMS_Z(                                   \
0696                 z, nnamed, typename ArgumentPack) >                            \
0697     typename BOOST_PP_EXPR_IF(nnamed,                                          \
0698         boost::lazy_enable_if                                                  \
0699             < boost::parameter::is_argument_pack< ArgumentPack0 >)             \
0700         BOOST_PP_COMMA_IF(nnamed)::boost::graph::detail::BOOST_PP_CAT(         \
0701             name, _impl)< BOOST_PP_ENUM_PARAMS_Z(z, nfixed, Param) >           \
0702             BOOST_PP_EXPR_IF(nnamed, >)::type name(                            \
0703                 BOOST_PP_ENUM_BINARY_PARAMS_Z(z, nfixed, Param, const& param)  \
0704                     BOOST_PP_ENUM_TRAILING_BINARY_PARAMS_Z(                    \
0705                         z, nnamed, ArgumentPack, const& tagged_arg))           \
0706     {                                                                          \
0707         return ::boost::graph::BOOST_PP_CAT(name, _with_named_params)(         \
0708             BOOST_PP_ENUM_PARAMS_Z(z, nfixed, param) BOOST_PP_COMMA_IF(nnamed) \
0709                 BOOST_PP_LPAREN_IF(nnamed) BOOST_PP_ENUM_PARAMS_Z(             \
0710                     z, nnamed, tagged_arg) BOOST_PP_RPAREN_IF(nnamed));        \
0711     }
0712 
0713 #define BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(name, nfixed)            \
0714     template < BOOST_PP_ENUM_PARAMS(nfixed, typename Param)                    \
0715                    BOOST_PP_COMMA_IF(nfixed) class P,                          \
0716         class T, class R >                                                     \
0717     typename boost::result_of< ::boost::graph::detail::BOOST_PP_CAT(           \
0718         name, _impl) BOOST_PP_EXPR_IF(nfixed, <) BOOST_PP_ENUM_PARAMS(nfixed,  \
0719         Param) BOOST_PP_EXPR_IF(nfixed, >)(BOOST_PP_ENUM_PARAMS(nfixed, Param) \
0720             BOOST_PP_COMMA_IF(nfixed) const typename boost::detail::           \
0721                 convert_bgl_params_to_boost_parameter<                         \
0722                     boost::bgl_named_params< P, T, R > >::type&) >::type       \
0723     name(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, &param)              \
0724             BOOST_PP_COMMA_IF(nfixed)                                          \
0725                 const boost::bgl_named_params< P, T, R >& old_style_params)    \
0726     {                                                                          \
0727         typedef boost::bgl_named_params< P, T, R > old_style_params_type;      \
0728         BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(                              \
0729             old_style_params_type, old_style_params)                           \
0730         return ::boost::graph::BOOST_PP_CAT(name, _with_named_params)(         \
0731             BOOST_PP_ENUM_PARAMS(nfixed, param) BOOST_PP_COMMA_IF(nfixed)      \
0732                 arg_pack);                                                     \
0733     }                                                                          \
0734     BOOST_PP_EXPR_IF(nfixed, template < )                                      \
0735     BOOST_PP_ENUM_PARAMS(nfixed, typename Param)                               \
0736     BOOST_PP_EXPR_IF(nfixed, >)                                                \
0737     BOOST_PP_EXPR_IF(nfixed, typename)                                         \
0738         boost::result_of< ::boost::graph::detail::BOOST_PP_CAT(                \
0739             name, _impl) BOOST_PP_EXPR_IF(nfixed,                              \
0740             <) BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_EXPR_IF(nfixed,    \
0741             >)(BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_COMMA_IF(nfixed)   \
0742                 const boost::parameter::aux::empty_arg_list&) >::type          \
0743             name(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, &param))     \
0744     {                                                                          \
0745         BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(                              \
0746             boost::no_named_parameters, boost::no_named_parameters())          \
0747         return ::boost::graph::BOOST_PP_CAT(name, _with_named_params)(         \
0748             BOOST_PP_ENUM_PARAMS(nfixed, param) BOOST_PP_COMMA_IF(nfixed)      \
0749                 arg_pack);                                                     \
0750     }
0751 
0752 }
0753 
0754 namespace detail
0755 {
0756 
0757     template < bool Exists, typename Graph, typename ArgPack, typename Value,
0758         typename PM >
0759     struct map_maker_helper
0760     {
0761         typedef PM map_type;
0762         static PM make_map(const Graph&, Value, const PM& pm, const ArgPack&)
0763         {
0764             return pm;
0765         }
0766     };
0767 
0768     template < typename Graph, typename ArgPack, typename Value, typename PM >
0769     struct map_maker_helper< false, Graph, ArgPack, Value, PM >
0770     {
0771         typedef typename boost::mpl::has_key< ArgPack,
0772             boost::graph::keywords::tag::vertex_index_map >::type
0773             _parameter_exists;
0774         typedef
0775             typename boost::remove_const< typename override_const_property_t<
0776                 typename boost::parameter::value_type< ArgPack,
0777                     boost::graph::keywords::tag::vertex_index_map, int >::type,
0778                 boost::vertex_index_t, Graph,
0779                 _parameter_exists::value >::result_type >::type vi_map_type;
0780         typedef boost::shared_array_property_map< Value, vi_map_type > map_type;
0781         static map_type make_map(
0782             const Graph& g, Value v, const PM&, const ArgPack& ap)
0783         {
0784             return make_shared_array_property_map(num_vertices(g), v,
0785                 override_const_property(ap,
0786                     boost::graph::keywords::_vertex_index_map, g,
0787                     vertex_index));
0788         }
0789     };
0790 
0791     template < typename Graph, typename ArgPack, typename MapTag,
0792         typename ValueType >
0793     struct map_maker
0794     {
0795         typedef typename boost::mpl::has_key< ArgPack, MapTag >::type
0796             _parameter_exists;
0797         BOOST_STATIC_CONSTANT(bool, has_map = (_parameter_exists::value));
0798         typedef map_maker_helper< has_map, Graph, ArgPack, ValueType,
0799             typename boost::remove_const< typename boost::parameter::value_type<
0800                 ArgPack, MapTag, int >::type >::type >
0801             helper;
0802         typedef typename helper::map_type map_type;
0803         static map_type make_map(
0804             const Graph& g, const ArgPack& ap, ValueType default_value)
0805         {
0806             return helper::make_map(g, default_value,
0807                 ap[::boost::parameter::keyword< MapTag >::instance | 0], ap);
0808         }
0809     };
0810 
0811     template < typename MapTag, typename ValueType = void >
0812     class make_property_map_from_arg_pack_gen
0813     {
0814         ValueType default_value;
0815 
0816     public:
0817         make_property_map_from_arg_pack_gen(ValueType default_value)
0818         : default_value(default_value)
0819         {
0820         }
0821 
0822         template < typename Graph, typename ArgPack >
0823         typename map_maker< Graph, ArgPack, MapTag, ValueType >::map_type
0824         operator()(const Graph& g, const ArgPack& ap) const
0825         {
0826             return map_maker< Graph, ArgPack, MapTag, ValueType >::make_map(
0827                 g, ap, default_value);
0828         }
0829     };
0830 
0831     template < typename MapTag >
0832     class make_property_map_from_arg_pack_gen< MapTag, void >
0833     {
0834     public:
0835         template < typename ValueType, typename Graph, typename ArgPack >
0836         typename map_maker< Graph, ArgPack, MapTag, ValueType >::map_type
0837         operator()(
0838             const Graph& g, const ArgPack& ap, ValueType default_value) const
0839         {
0840             return map_maker< Graph, ArgPack, MapTag, ValueType >::make_map(
0841                 g, ap, default_value);
0842         }
0843     };
0844 
0845     static const make_property_map_from_arg_pack_gen<
0846         boost::graph::keywords::tag::color_map, default_color_type >
0847         make_color_map_from_arg_pack(white_color);
0848 
0849     template < bool Exists, class Graph, class ArgPack, class KeyT,
0850         class ValueT, class KeyMapTag, class IndexInHeapMapTag, class Compare,
0851         class Q >
0852     struct priority_queue_maker_helper
0853     {
0854         typedef Q priority_queue_type;
0855 
0856         static priority_queue_type make_queue(
0857             const Graph&, const ArgPack&, KeyT, const Q& q)
0858         {
0859             return q;
0860         }
0861     };
0862 
0863     template < class Graph, class ArgPack, class KeyT, class ValueT,
0864         class KeyMapTag, class IndexInHeapMapTag, class Compare, class Q >
0865     struct priority_queue_maker_helper< false, Graph, ArgPack, KeyT, ValueT,
0866         KeyMapTag, IndexInHeapMapTag, Compare, Q >
0867     {
0868         typedef typename std::vector< ValueT >::size_type
0869             default_index_in_heap_type;
0870         typedef typename map_maker< Graph, ArgPack, IndexInHeapMapTag,
0871             default_index_in_heap_type >::helper::map_type index_in_heap_map;
0872         typedef boost::d_ary_heap_indirect< ValueT, 4, index_in_heap_map,
0873             typename map_maker< Graph, ArgPack, KeyMapTag,
0874                 KeyT >::helper::map_type,
0875             Compare >
0876             priority_queue_type;
0877 
0878         static priority_queue_type make_queue(
0879             const Graph& g, const ArgPack& ap, KeyT defaultKey, const Q&)
0880         {
0881             return priority_queue_type(
0882                 map_maker< Graph, ArgPack, KeyMapTag, KeyT >::make_map(
0883                     g, ap, defaultKey),
0884                 map_maker< Graph, ArgPack, IndexInHeapMapTag,
0885                     default_index_in_heap_type >::make_map(g, ap,
0886                     typename boost::property_traits<
0887                         index_in_heap_map >::value_type(-1)));
0888         }
0889     };
0890 
0891     template < class Graph, class ArgPack, class KeyT, class ValueT,
0892         class PriorityQueueTag, class KeyMapTag, class IndexInHeapMapTag,
0893         class Compare >
0894     struct priority_queue_maker
0895     {
0896         typedef typename boost::mpl::has_key< ArgPack, PriorityQueueTag >::type
0897             _parameter_exists;
0898         BOOST_STATIC_CONSTANT(bool, g_hasQ = (_parameter_exists::value));
0899         typedef boost::reference_wrapper< int > int_refw;
0900         typedef typename boost::parameter::value_type< ArgPack,
0901             PriorityQueueTag, int_refw >::type param_value_type_wrapper;
0902         typedef typename param_value_type_wrapper::type param_value_type;
0903         typedef typename boost::remove_const< param_value_type >::type
0904             param_value_type_no_const;
0905         typedef priority_queue_maker_helper< g_hasQ, Graph, ArgPack, KeyT,
0906             ValueT, KeyMapTag, IndexInHeapMapTag, Compare,
0907             param_value_type_no_const >
0908             helper;
0909         typedef typename helper::priority_queue_type priority_queue_type;
0910 
0911         static priority_queue_type make_queue(
0912             const Graph& g, const ArgPack& ap, KeyT defaultKey)
0913         {
0914             return helper::make_queue(g, ap, defaultKey,
0915                 ap[::boost::parameter::keyword< PriorityQueueTag >::instance
0916                     | 0]);
0917         }
0918     };
0919 
0920     template < class PriorityQueueTag, class KeyT, class ValueT,
0921         class Compare = std::less< KeyT >,
0922         class KeyMapTag = boost::graph::keywords::tag::distance_map,
0923         class IndexInHeapMapTag
0924         = boost::graph::keywords::tag::index_in_heap_map >
0925     struct make_priority_queue_from_arg_pack_gen
0926     {
0927         KeyT defaultKey;
0928 
0929         make_priority_queue_from_arg_pack_gen(KeyT defaultKey_)
0930         : defaultKey(defaultKey_)
0931         {
0932         }
0933 
0934         template < class F > struct result
0935         {
0936             typedef typename remove_const< typename remove_reference<
0937                 typename function_traits< F >::arg1_type >::type >::type
0938                 graph_type;
0939             typedef typename remove_const< typename remove_reference<
0940                 typename function_traits< F >::arg2_type >::type >::type
0941                 arg_pack_type;
0942             typedef typename priority_queue_maker< graph_type, arg_pack_type,
0943                 KeyT, ValueT, PriorityQueueTag, KeyMapTag, IndexInHeapMapTag,
0944                 Compare >::priority_queue_type type;
0945         };
0946 
0947         template < class Graph, class ArgPack >
0948         typename priority_queue_maker< Graph, ArgPack, KeyT, ValueT,
0949             PriorityQueueTag, KeyMapTag, IndexInHeapMapTag,
0950             Compare >::priority_queue_type
0951         operator()(const Graph& g, const ArgPack& ap) const
0952         {
0953             return priority_queue_maker< Graph, ArgPack, KeyT, ValueT,
0954                 PriorityQueueTag, KeyMapTag, IndexInHeapMapTag,
0955                 Compare >::make_queue(g, ap, defaultKey);
0956         }
0957     };
0958 
0959     template < typename G >
0960     typename boost::graph_traits< G >::vertex_descriptor get_null_vertex(
0961         const G&)
0962     {
0963         return boost::graph_traits< G >::null_vertex();
0964     }
0965 
0966     template < typename G >
0967     typename boost::graph_traits< G >::vertex_descriptor
0968     get_default_starting_vertex(const G& g)
0969     {
0970         std::pair< typename boost::graph_traits< G >::vertex_iterator,
0971             typename boost::graph_traits< G >::vertex_iterator >
0972             iters = vertices(g);
0973         return (iters.first == iters.second)
0974             ? boost::graph_traits< G >::null_vertex()
0975             : *iters.first;
0976     }
0977 
0978     template < typename G > struct get_default_starting_vertex_t
0979     {
0980         typedef
0981             typename boost::graph_traits< G >::vertex_descriptor result_type;
0982         const G& g;
0983         get_default_starting_vertex_t(const G& g) : g(g) {}
0984         result_type operator()() const
0985         {
0986             return get_default_starting_vertex(g);
0987         }
0988     };
0989 
0990     // Wrapper to avoid instantiating numeric_limits when users provide
0991     // distance_inf value manually
0992     template < typename T > struct get_max
0993     {
0994         T operator()() const { return (std::numeric_limits< T >::max)(); }
0995         typedef T result_type;
0996     };
0997 
0998 } // namespace detail
0999 
1000 } // namespace boost
1001 
1002 #undef BOOST_BGL_DECLARE_NAMED_PARAMS
1003 
1004 #endif // BOOST_GRAPH_NAMED_FUNCTION_PARAMS_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!