ceph/src/boost/libs/graph/include/boost/graph/named_function_params.hpp

   1 //=======================================================================
   2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8 //=======================================================================
   9
  10 #ifndef BOOST_GRAPH_NAMED_FUNCTION_PARAMS_HPP
  11 #define BOOST_GRAPH_NAMED_FUNCTION_PARAMS_HPP
  12
  13 #include <functional>
  14 #include <vector>
  15 #include <boost/limits.hpp>
  16 #include <boost/ref.hpp>
  17 #include <boost/utility/result_of.hpp>
  18 #include <boost/preprocessor.hpp>
  19 #include <boost/parameter/name.hpp>
  20 #include <boost/parameter/binding.hpp>
  21 #include <boost/type_traits.hpp>
  22 #include <boost/mpl/not.hpp>
  23 #include <boost/graph/properties.hpp>
  24 #include <boost/graph/detail/d_ary_heap.hpp>
  25 #include <boost/property_map/property_map.hpp>
  26 #include <boost/property_map/shared_array_property_map.hpp>
  27
  28 namespace boost {
  29
  30   struct parity_map_t { };
  31   struct vertex_assignment_map_t { };
  32   struct distance_compare_t { };
  33   struct distance_combine_t { };
  34   struct distance_inf_t { };
  35   struct distance_zero_t { };
  36   struct buffer_param_t { };
  37   struct edge_copy_t { };
  38   struct vertex_copy_t { };
  39   struct vertex_isomorphism_t { };
  40   struct vertex_invariant_t { };
  41   struct vertex_invariant1_t { };
  42   struct vertex_invariant2_t { };
  43   struct edge_compare_t { };
  44   struct vertex_max_invariant_t { };
  45   struct orig_to_copy_t { };
  46   struct root_vertex_t { };
  47   struct polling_t { };
  48   struct lookahead_t { };
  49   struct in_parallel_t { };
  50   struct attractive_force_t { };
  51   struct repulsive_force_t { };
  52   struct force_pairs_t { };
  53   struct cooling_t { };
  54   struct vertex_displacement_t { };
  55   struct iterations_t { };
  56   struct diameter_range_t { };
  57   struct learning_constant_range_t { };
  58   struct vertices_equivalent_t { };
  59   struct edges_equivalent_t { };
  60   struct index_in_heap_map_t { };
  61   struct max_priority_queue_t { };
  62
  63 #define BOOST_BGL_DECLARE_NAMED_PARAMS \
  64     BOOST_BGL_ONE_PARAM_CREF(weight_map, edge_weight) \
  65     BOOST_BGL_ONE_PARAM_CREF(weight_map2, edge_weight2) \
  66     BOOST_BGL_ONE_PARAM_CREF(distance_map, vertex_distance) \
  67     BOOST_BGL_ONE_PARAM_CREF(distance_map2, vertex_distance2) \
  68     BOOST_BGL_ONE_PARAM_CREF(predecessor_map, vertex_predecessor) \
  69     BOOST_BGL_ONE_PARAM_CREF(rank_map, vertex_rank) \
  70     BOOST_BGL_ONE_PARAM_CREF(root_map, vertex_root) \
  71     BOOST_BGL_ONE_PARAM_CREF(root_vertex, root_vertex) \
  72     BOOST_BGL_ONE_PARAM_CREF(edge_centrality_map, edge_centrality) \
  73     BOOST_BGL_ONE_PARAM_CREF(centrality_map, vertex_centrality) \
  74     BOOST_BGL_ONE_PARAM_CREF(parity_map, parity_map) \
  75     BOOST_BGL_ONE_PARAM_CREF(color_map, vertex_color) \
  76     BOOST_BGL_ONE_PARAM_CREF(edge_color_map, edge_color) \
  77     BOOST_BGL_ONE_PARAM_CREF(capacity_map, edge_capacity) \
  78     BOOST_BGL_ONE_PARAM_CREF(residual_capacity_map, edge_residual_capacity) \
  79     BOOST_BGL_ONE_PARAM_CREF(reverse_edge_map, edge_reverse) \
  80     BOOST_BGL_ONE_PARAM_CREF(discover_time_map, vertex_discover_time) \
  81     BOOST_BGL_ONE_PARAM_CREF(lowpoint_map, vertex_lowpoint) \
  82     BOOST_BGL_ONE_PARAM_CREF(vertex_index_map, vertex_index) \
  83     BOOST_BGL_ONE_PARAM_CREF(vertex_index1_map, vertex_index1) \
  84     BOOST_BGL_ONE_PARAM_CREF(vertex_index2_map, vertex_index2) \
  85     BOOST_BGL_ONE_PARAM_CREF(vertex_assignment_map, vertex_assignment_map) \
  86     BOOST_BGL_ONE_PARAM_CREF(visitor, graph_visitor) \
  87     BOOST_BGL_ONE_PARAM_CREF(distance_compare, distance_compare) \
  88     BOOST_BGL_ONE_PARAM_CREF(distance_combine, distance_combine) \
  89     BOOST_BGL_ONE_PARAM_CREF(distance_inf, distance_inf) \
  90     BOOST_BGL_ONE_PARAM_CREF(distance_zero, distance_zero) \
  91     BOOST_BGL_ONE_PARAM_CREF(edge_copy, edge_copy) \
  92     BOOST_BGL_ONE_PARAM_CREF(vertex_copy, vertex_copy) \
  93     BOOST_BGL_ONE_PARAM_REF(buffer, buffer_param) \
  94     BOOST_BGL_ONE_PARAM_CREF(orig_to_copy, orig_to_copy) \
  95     BOOST_BGL_ONE_PARAM_CREF(isomorphism_map, vertex_isomorphism) \
  96     BOOST_BGL_ONE_PARAM_CREF(vertex_invariant, vertex_invariant) \
  97     BOOST_BGL_ONE_PARAM_CREF(vertex_invariant1, vertex_invariant1) \
  98     BOOST_BGL_ONE_PARAM_CREF(vertex_invariant2, vertex_invariant2) \
  99     BOOST_BGL_ONE_PARAM_CREF(vertex_max_invariant, vertex_max_invariant) \
 100     BOOST_BGL_ONE_PARAM_CREF(polling, polling) \
 101     BOOST_BGL_ONE_PARAM_CREF(lookahead, lookahead) \
 102     BOOST_BGL_ONE_PARAM_CREF(in_parallel, in_parallel) \
 103     BOOST_BGL_ONE_PARAM_CREF(displacement_map, vertex_displacement) \
 104     BOOST_BGL_ONE_PARAM_CREF(attractive_force, attractive_force) \
 105     BOOST_BGL_ONE_PARAM_CREF(repulsive_force, repulsive_force) \
 106     BOOST_BGL_ONE_PARAM_CREF(force_pairs, force_pairs) \
 107     BOOST_BGL_ONE_PARAM_CREF(cooling, cooling) \
 108     BOOST_BGL_ONE_PARAM_CREF(iterations, iterations) \
 109     BOOST_BGL_ONE_PARAM_CREF(diameter_range, diameter_range) \
 110     BOOST_BGL_ONE_PARAM_CREF(learning_constant_range, learning_constant_range) \
 111     BOOST_BGL_ONE_PARAM_CREF(vertices_equivalent, vertices_equivalent) \
 112     BOOST_BGL_ONE_PARAM_CREF(edges_equivalent, edges_equivalent) \
 113     BOOST_BGL_ONE_PARAM_CREF(index_in_heap_map, index_in_heap_map) \
 114     BOOST_BGL_ONE_PARAM_REF(max_priority_queue, max_priority_queue)
 115
 116   template <typename T, typename Tag, typename Base = no_property>
 117   struct bgl_named_params
 118   {
 119     typedef bgl_named_params self;
 120     typedef Base next_type;
 121     typedef Tag tag_type;
 122     typedef T value_type;
 123     bgl_named_params(T v = T()) : m_value(v) { }
 124     bgl_named_params(T v, const Base& b) : m_value(v), m_base(b) { }
 125     T m_value;
 126     Base m_base;
 127
 128 #define BOOST_BGL_ONE_PARAM_REF(name, key) \
 129     template <typename PType> \
 130     bgl_named_params<boost::reference_wrapper<PType>, BOOST_PP_CAT(key, _t), self> \
 131     name(PType& p) const { \
 132       typedef bgl_named_params<boost::reference_wrapper<PType>, BOOST_PP_CAT(key, _t), self> Params; \
 133       return Params(boost::ref(p), *this); \
 134     } \
 135
 136 #define BOOST_BGL_ONE_PARAM_CREF(name, key) \
 137     template <typename PType> \
 138     bgl_named_params<PType, BOOST_PP_CAT(key, _t), self> \
 139     name(const PType& p) const { \
 140       typedef bgl_named_params<PType, BOOST_PP_CAT(key, _t), self> Params; \
 141       return Params(p, *this); \
 142     } \
 143
 144 BOOST_BGL_DECLARE_NAMED_PARAMS
 145
 146 #undef BOOST_BGL_ONE_PARAM_REF
 147 #undef BOOST_BGL_ONE_PARAM_CREF
 148
 149     // Duplicate
 150     template <typename PType>
 151     bgl_named_params<PType, vertex_color_t, self>
 152     vertex_color_map(const PType& p) const {return this->color_map(p);}
 153   };
 154
 155 #define BOOST_BGL_ONE_PARAM_REF(name, key) \
 156     template <typename PType> \
 157     bgl_named_params<boost::reference_wrapper<PType>, BOOST_PP_CAT(key, _t)> \
 158     name(PType& p) { \
 159       typedef bgl_named_params<boost::reference_wrapper<PType>, BOOST_PP_CAT(key, _t)> Params; \
 160       return Params(boost::ref(p)); \
 161     } \
 162
 163 #define BOOST_BGL_ONE_PARAM_CREF(name, key) \
 164     template <typename PType> \
 165     bgl_named_params<PType, BOOST_PP_CAT(key, _t)> \
 166     name(const PType& p) { \
 167       typedef bgl_named_params<PType, BOOST_PP_CAT(key, _t)> Params; \
 168       return Params(p); \
 169     } \
 170
 171 BOOST_BGL_DECLARE_NAMED_PARAMS
 172
 173 #undef BOOST_BGL_ONE_PARAM_REF
 174 #undef BOOST_BGL_ONE_PARAM_CREF
 175
 176   // Duplicate
 177   template <typename PType>
 178   bgl_named_params<PType, vertex_color_t>
 179   vertex_color_map(const PType& p) {return color_map(p);}
 180
 181   namespace detail {
 182     struct unused_tag_type {};
 183   }
 184   typedef bgl_named_params<char, detail::unused_tag_type> no_named_parameters;
 185
 186   //===========================================================================
 187   // Functions for extracting parameters from bgl_named_params
 188
 189   template <typename Tag, typename Args>
 190   struct lookup_named_param {};
 191
 192   template <typename T, typename Tag, typename Base>
 193   struct lookup_named_param<Tag, bgl_named_params<T, Tag, Base> > {
 194     typedef T type;
 195     static const T& get(const bgl_named_params<T, Tag, Base>& p) {
 196       return p.m_value;
 197     }
 198   };
 199
 200   template <typename Tag1, typename T, typename Tag, typename Base>
 201   struct lookup_named_param<Tag1, bgl_named_params<T, Tag, Base> > {
 202     typedef typename lookup_named_param<Tag1, Base>::type type;
 203     static const type& get(const bgl_named_params<T, Tag, Base>& p) {
 204       return lookup_named_param<Tag1, Base>::get(p.m_base);
 205     }
 206   };
 207
 208   template <typename Tag, typename Args, typename Def>
 209   struct lookup_named_param_def {
 210     typedef Def type;
 211     static const Def& get(const Args&, const Def& def) {return def;}
 212   };
 213
 214   template <typename T, typename Tag, typename Base, typename Def>
 215   struct lookup_named_param_def<Tag, bgl_named_params<T, Tag, Base>, Def> {
 216     typedef T type;
 217     static const type& get(const bgl_named_params<T, Tag, Base>& p, const Def&) {
 218       return p.m_value;
 219     }
 220   };
 221
 222   template <typename Tag1, typename T, typename Tag, typename Base, typename Def>
 223   struct lookup_named_param_def<Tag1, bgl_named_params<T, Tag, Base>, Def> {
 224     typedef typename lookup_named_param_def<Tag1, Base, Def>::type type;
 225     static const type& get(const bgl_named_params<T, Tag, Base>& p, const Def& def) {
 226       return lookup_named_param_def<Tag1, Base, Def>::get(p.m_base, def);
 227     }
 228   };
 229
 230   struct param_not_found {};
 231
 232   template <typename Tag, typename Args>
 233   struct get_param_type:
 234     lookup_named_param_def<Tag, Args, param_not_found> {};
 235
 236   template <class Tag, typename Args>
 237   inline
 238   const typename lookup_named_param_def<Tag, Args, param_not_found>::type&
 239   get_param(const Args& p, Tag) {
 240     return lookup_named_param_def<Tag, Args, param_not_found>::get(p, param_not_found());
 241   }
 242
 243   template <class P, class Default>
 244   const P& choose_param(const P& param, const Default&) {
 245     return param;
 246   }
 247
 248   template <class Default>
 249   Default choose_param(const param_not_found&, const Default& d) {
 250     return d;
 251   }
 252
 253   template <typename T>
 254   inline bool is_default_param(const T&) { return false; }
 255
 256   inline bool is_default_param(const param_not_found&)
 257     { return true; }
 258
 259   namespace detail {
 260     template <typename T>
 261     struct const_type_as_type {typedef typename T::const_type type;};
 262   } // namespace detail
 263
 264
 265   // Use this function instead of choose_param() when you want
 266   // to avoid requiring get(tag, g) when it is not used.
 267   namespace detail {
 268     template <typename GraphIsConst, typename Graph, typename Param, typename Tag>
 269     struct choose_impl_result:
 270       boost::mpl::eval_if<
 271         boost::is_same<Param, param_not_found>,
 272         boost::mpl::eval_if<
 273           GraphIsConst,
 274           detail::const_type_as_type<property_map<Graph, Tag> >,
 275           property_map<Graph, Tag> >,
 276         boost::mpl::identity<Param> > {};
 277
 278     // Parameters of f are (GraphIsConst, Graph, Param, Tag)
 279     template <bool Found> struct choose_impl_helper;
 280
 281     template <> struct choose_impl_helper<false> {
 282       template <typename Param, typename Graph, typename PropertyTag>
 283       static typename property_map<typename boost::remove_const<Graph>::type, PropertyTag>::const_type
 284       f(boost::mpl::true_, const Graph& g, const Param&, PropertyTag tag) {
 285         return get(tag, g);
 286       }
 287
 288       template <typename Param, typename Graph, typename PropertyTag>
 289       static typename property_map<typename boost::remove_const<Graph>::type, PropertyTag>::type
 290       f(boost::mpl::false_, Graph& g, const Param&, PropertyTag tag) {
 291         return get(tag, g);
 292       }
 293     };
 294
 295     template <> struct choose_impl_helper<true> {
 296       template <typename GraphIsConst, typename Param, typename Graph, typename PropertyTag>
 297       static Param f(GraphIsConst, const Graph&, const Param& p, PropertyTag) {
 298         return p;
 299       }
 300     };
 301   }
 302
 303   template <typename Param, typename Graph, typename PropertyTag>
 304   typename detail::choose_impl_result<boost::mpl::true_, Graph, Param, PropertyTag>::type
 305   choose_const_pmap(const Param& p, const Graph& g, PropertyTag tag)
 306   {
 307     return detail::choose_impl_helper<!boost::is_same<Param, param_not_found>::value>
 308              ::f(boost::mpl::true_(), g, p, tag);
 309   }
 310
 311   template <typename Param, typename Graph, typename PropertyTag>
 312   typename detail::choose_impl_result<boost::mpl::false_, Graph, Param, PropertyTag>::type
 313   choose_pmap(const Param& p, Graph& g, PropertyTag tag)
 314   {
 315     return detail::choose_impl_helper<!boost::is_same<Param, param_not_found>::value>
 316              ::f(boost::mpl::false_(), g, p, tag);
 317   }
 318
 319   namespace detail {
 320
 321     // used in the max-flow algorithms
 322     template <class Graph, class P, class T, class R>
 323     struct edge_capacity_value
 324     {
 325       typedef bgl_named_params<P, T, R> Params;
 326       typedef typename detail::choose_impl_result<boost::mpl::true_, Graph, typename get_param_type<edge_capacity_t, Params>::type, edge_capacity_t>::type CapacityEdgeMap;
 327       typedef typename property_traits<CapacityEdgeMap>::value_type type;
 328     };
 329     // used in the max-flow algorithms
 330     template <class Graph, class P, class T, class R>
 331     struct edge_weight_value
 332     {
 333       typedef bgl_named_params<P, T, R> Params;
 334       typedef typename detail::choose_impl_result<boost::mpl::true_, Graph, typename get_param_type<edge_weight_t, Params>::type, edge_weight_t>::type WeightMap;
 335       typedef typename property_traits<WeightMap>::value_type type;
 336     };
 337
 338   }
 339
 340   // Declare all new tags
 341   namespace graph {
 342     namespace keywords {
 343 #define BOOST_BGL_ONE_PARAM_REF(name, key) BOOST_PARAMETER_NAME(name)
 344 #define BOOST_BGL_ONE_PARAM_CREF(name, key) BOOST_PARAMETER_NAME(name)
 345       BOOST_BGL_DECLARE_NAMED_PARAMS
 346 #undef BOOST_BGL_ONE_PARAM_REF
 347 #undef BOOST_BGL_ONE_PARAM_CREF
 348     }
 349   }
 350
 351   namespace detail {
 352     template <typename Tag> struct convert_one_keyword {};
 353 #define BOOST_BGL_ONE_PARAM_REF(name, key) \
 354     template <> \
 355     struct convert_one_keyword<BOOST_PP_CAT(key, _t)> { \
 356       typedef boost::graph::keywords::tag::name type; \
 357     };
 358 #define BOOST_BGL_ONE_PARAM_CREF(name, key) BOOST_BGL_ONE_PARAM_REF(name, key)
 359     BOOST_BGL_DECLARE_NAMED_PARAMS
 360 #undef BOOST_BGL_ONE_PARAM_REF
 361 #undef BOOST_BGL_ONE_PARAM_CREF
 362
 363     template <typename T>
 364     struct convert_bgl_params_to_boost_parameter {
 365       typedef typename convert_one_keyword<typename T::tag_type>::type new_kw;
 366       typedef boost::parameter::aux::tagged_argument<new_kw, const typename T::value_type> tagged_arg_type;
 367       typedef convert_bgl_params_to_boost_parameter<typename T::next_type> rest_conv;
 368       typedef boost::parameter::aux::arg_list<tagged_arg_type, typename rest_conv::type> type;
 369       static type conv(const T& x) {
 370         return type(tagged_arg_type(x.m_value), rest_conv::conv(x.m_base));
 371       }
 372     };
 373
 374     template <typename P, typename R>
 375     struct convert_bgl_params_to_boost_parameter<bgl_named_params<P, int, R> > {
 376       typedef convert_bgl_params_to_boost_parameter<R> rest_conv;
 377       typedef typename rest_conv::type type;
 378       static type conv(const bgl_named_params<P, int, R>& x) {
 379         return rest_conv::conv(x.m_base);
 380       }
 381     };
 382
 383     template <>
 384     struct convert_bgl_params_to_boost_parameter<boost::no_property> {
 385       typedef boost::parameter::aux::empty_arg_list type;
 386       static type conv(const boost::no_property&) {return type();}
 387     };
 388
 389     template <>
 390     struct convert_bgl_params_to_boost_parameter<boost::no_named_parameters> {
 391       typedef boost::parameter::aux::empty_arg_list type;
 392       static type conv(const boost::no_named_parameters&) {return type();}
 393     };
 394
 395     struct bgl_parameter_not_found_type {};
 396
 397     template <typename ArgPack, typename KeywordType>
 398     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> > {};
 399   }
 400
 401 #define BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(old_type, old_var) \
 402   typedef typename boost::detail::convert_bgl_params_to_boost_parameter<old_type>::type arg_pack_type; \
 403   arg_pack_type arg_pack = boost::detail::convert_bgl_params_to_boost_parameter<old_type>::conv(old_var);
 404
 405   namespace detail {
 406
 407     template <typename ArgType, typename Prop, typename Graph, bool Exists>
 408     struct override_const_property_t {
 409       typedef typename boost::remove_const<ArgType>::type result_type;
 410       result_type operator()(const Graph&, const ArgType& a) const {return a;}
 411     };
 412
 413     template <typename ArgType, typename Prop, typename Graph>
 414     struct override_const_property_t<ArgType, Prop, Graph, false> {
 415       typedef typename boost::property_map<Graph, Prop>::const_type result_type;
 416       result_type operator()(const Graph& g, const ArgType&) const {return get(Prop(), g);}
 417     };
 418
 419     template <typename ArgPack, typename Tag, typename Prop, typename Graph>
 420     struct override_const_property_result {
 421       typedef
 422         typename override_const_property_t<
 423                    typename boost::parameter::value_type<ArgPack, Tag, int>::type,
 424                    Prop,
 425                    Graph,
 426                    boost::detail::parameter_exists<ArgPack, Tag>::value
 427                  >::result_type
 428         type;
 429     };
 430
 431     template <typename ArgPack, typename Tag, typename Prop, typename Graph>
 432     typename override_const_property_result<ArgPack, Tag, Prop, Graph>::type
 433     override_const_property(const ArgPack& ap, const boost::parameter::keyword<Tag>& t, const Graph& g, Prop) {
 434     return override_const_property_t<
 435              typename boost::parameter::value_type<ArgPack, Tag, int>::type,
 436              Prop,
 437              Graph,
 438              boost::detail::parameter_exists<ArgPack, Tag>::value
 439            >()(g, ap[t | 0]);
 440     }
 441
 442     template <typename ArgType, typename Prop, typename Graph, bool Exists>
 443     struct override_property_t {
 444       typedef ArgType result_type;
 445       result_type operator()(const Graph&, const typename boost::add_reference<ArgType>::type a) const {return a;}
 446     };
 447
 448     template <typename ArgType, typename Prop, typename Graph>
 449     struct override_property_t<ArgType, Prop, Graph, false> {
 450       typedef typename boost::property_map<Graph, Prop>::type result_type;
 451       result_type operator()(const Graph& g, const ArgType&) const {return get(Prop(), g);}
 452     };
 453
 454     template <typename ArgPack, typename Tag, typename Prop, typename Graph>
 455     struct override_property_result {
 456       typedef
 457         typename override_property_t<
 458                    typename boost::parameter::value_type<ArgPack, Tag, int>::type,
 459                    Prop,
 460                    Graph,
 461                    boost::detail::parameter_exists<ArgPack, Tag>::value
 462                  >::result_type
 463         type;
 464     };
 465
 466     template <typename ArgPack, typename Tag, typename Prop, typename Graph>
 467     typename override_property_result<ArgPack, Tag, Prop, Graph>::type
 468     override_property(const ArgPack& ap, const boost::parameter::keyword<Tag>& t, const Graph& g, Prop) {
 469     return override_property_t<
 470              typename boost::parameter::value_type<ArgPack, Tag, int>::type,
 471              Prop,
 472              Graph,
 473              boost::detail::parameter_exists<ArgPack, Tag>::value
 474            >()(g, ap[t | 0]);
 475     }
 476
 477     template <typename F> struct make_arg_pack_type;
 478     template <> struct make_arg_pack_type<void()> {typedef boost::parameter::aux::empty_arg_list type;};
 479     template <typename K, typename A>
 480     struct make_arg_pack_type<void(K, A)> {
 481       typedef boost::parameter::aux::tagged_argument<K, A> type;
 482     };
 483
 484 #define BOOST_GRAPH_OPENING_PART_OF_PAIR(z, i, n) boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<BOOST_PP_CAT(Keyword, BOOST_PP_SUB(n, i)),  BOOST_PP_CAT(Arg, BOOST_PP_SUB(n, i))>,
 485 #define BOOST_GRAPH_MAKE_PAIR_PARAM(z, i, _) const boost::parameter::aux::tagged_argument<BOOST_PP_CAT(Keyword, i), BOOST_PP_CAT(Arg, i)>& BOOST_PP_CAT(kw, i)
 486
 487 #define BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION(z, i, _) \
 488     template <BOOST_PP_ENUM_PARAMS(i, typename Keyword), BOOST_PP_ENUM_PARAMS(i, typename Arg)> \
 489     struct make_arg_pack_type<void(BOOST_PP_ENUM_PARAMS(i, Keyword), BOOST_PP_ENUM_PARAMS(i, Arg))> { \
 490       typedef \
 491         BOOST_PP_REPEAT(i, BOOST_GRAPH_OPENING_PART_OF_PAIR, BOOST_PP_DEC(i)) boost::parameter::aux::empty_arg_list BOOST_PP_REPEAT(i, > BOOST_PP_TUPLE_EAT(3), ~) \
 492         type; \
 493     };
 494     BOOST_PP_REPEAT_FROM_TO(2, 11, BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION, ~)
 495 #undef BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION
 496
 497 #define BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(name, nfixed, nnamed_max) \
 498   /* Entry point for conversion from BGL-style named parameters */ \
 499   template <BOOST_PP_ENUM_PARAMS(nfixed, typename Param) BOOST_PP_COMMA_IF(nfixed) typename ArgPack> \
 500   typename boost::result_of< \
 501              detail::BOOST_PP_CAT(name, _impl)<BOOST_PP_ENUM_PARAMS(nfixed, Param)>(BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_COMMA_IF(nfixed) const ArgPack&) \
 502            >::type \
 503   BOOST_PP_CAT(name, _with_named_params)(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, & param) BOOST_PP_COMMA_IF(nfixed) const ArgPack& arg_pack) { \
 504     return detail::BOOST_PP_CAT(name, _impl)<BOOST_PP_ENUM_PARAMS(nfixed, Param)>()(BOOST_PP_ENUM_PARAMS(nfixed, param) BOOST_PP_COMMA_IF(nfixed) arg_pack); \
 505   } \
 506   /* Individual functions taking Boost.Parameter-style keyword arguments */ \
 507   BOOST_PP_REPEAT(BOOST_PP_INC(nnamed_max), BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONE, (name)(nfixed))
 508
 509 #define BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONE(z, nnamed, seq) \
 510   BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONEX(z, nnamed, BOOST_PP_SEQ_ELEM(0, seq), BOOST_PP_SEQ_ELEM(1, seq))
 511
 512 #define BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONEX(z, nnamed, name, nfixed) \
 513   template <BOOST_PP_ENUM_PARAMS(nfixed, typename Param) BOOST_PP_ENUM_TRAILING_PARAMS(nnamed, typename Keyword) BOOST_PP_ENUM_TRAILING_PARAMS(nnamed, typename Arg)> \
 514   typename boost::result_of< \
 515              detail::BOOST_PP_CAT(name, _impl)<BOOST_PP_ENUM_PARAMS(nfixed, Param)> \
 516                (BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_COMMA_IF(nfixed) \
 517                 const typename boost::detail::make_arg_pack_type<void(BOOST_PP_ENUM_PARAMS(nnamed, Keyword) BOOST_PP_COMMA_IF(nnamed) BOOST_PP_ENUM_PARAMS(nnamed, Arg))>::type&) \
 518            >::type \
 519   name(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, & param) \
 520        BOOST_PP_ENUM_TRAILING(nnamed, BOOST_GRAPH_MAKE_PAIR_PARAM, ~)) { \
 521     return detail::BOOST_PP_CAT(name, _impl)<BOOST_PP_ENUM_PARAMS(nfixed, Param)>() \
 522              (BOOST_PP_ENUM_PARAMS(nfixed, param), \
 523               (boost::parameter::aux::empty_arg_list() BOOST_PP_ENUM_TRAILING_PARAMS(nnamed, kw))); \
 524   }
 525
 526 #define BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(name, nfixed) \
 527   template <BOOST_PP_ENUM_PARAMS(nfixed, typename Param) BOOST_PP_COMMA_IF(nfixed) class P, class T, class R> \
 528   typename boost::result_of< \
 529     ::boost::graph::detail::BOOST_PP_CAT(name, _impl) BOOST_PP_EXPR_IF(nfixed, <) BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_EXPR_IF(nfixed, >) \
 530       (BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_COMMA_IF(nfixed) \
 531        const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<P, T, R> >::type &) \
 532     >::type \
 533   name(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, & param) BOOST_PP_COMMA_IF(nfixed) const boost::bgl_named_params<P, T, R>& old_style_params) { \
 534     typedef boost::bgl_named_params<P, T, R> old_style_params_type; \
 535     BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(old_style_params_type, old_style_params) \
 536     return ::boost::graph::BOOST_PP_CAT(name, _with_named_params)(BOOST_PP_ENUM_PARAMS(nfixed, param) BOOST_PP_COMMA_IF(nfixed) arg_pack); \
 537   } \
 538   \
 539   BOOST_PP_EXPR_IF(nfixed, template <) BOOST_PP_ENUM_PARAMS(nfixed, typename Param) BOOST_PP_EXPR_IF(nfixed, >) \
 540   BOOST_PP_EXPR_IF(nfixed, typename) boost::result_of< \
 541     ::boost::graph::detail::BOOST_PP_CAT(name, _impl) BOOST_PP_EXPR_IF(nfixed, <) BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_EXPR_IF(nfixed, >) \
 542       (BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_COMMA_IF(nfixed) const boost::parameter::aux::empty_arg_list &) \
 543     >::type \
 544   name(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, & param)) { \
 545     BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(boost::no_named_parameters, boost::no_named_parameters()) \
 546     return ::boost::graph::BOOST_PP_CAT(name, _with_named_params)(BOOST_PP_ENUM_PARAMS(nfixed, param) BOOST_PP_COMMA_IF(nfixed) arg_pack); \
 547   }
 548
 549   }
 550
 551   namespace detail {
 552
 553     template <bool Exists, typename Graph, typename ArgPack, typename Value, typename PM>
 554     struct map_maker_helper {
 555       typedef PM map_type;
 556       static PM make_map(const Graph&, Value, const PM& pm, const ArgPack&) {
 557         return pm;
 558       }
 559     };
 560
 561     template <typename Graph, typename ArgPack, typename Value, typename PM>
 562     struct map_maker_helper<false, Graph, ArgPack, Value, PM> {
 563       typedef typename boost::remove_const<
 564         typename override_const_property_t<
 565           typename boost::parameter::value_type<
 566             ArgPack, boost::graph::keywords::tag::vertex_index_map, int>::type,
 567           boost::vertex_index_t,
 568           Graph,
 569           boost::detail::parameter_exists<
 570             ArgPack, boost::graph::keywords::tag::vertex_index_map>::value
 571         >::result_type>::type vi_map_type;
 572       typedef
 573         boost::shared_array_property_map<Value, vi_map_type>
 574         map_type;
 575       static map_type make_map(const Graph& g,
 576                                Value v,
 577                                const PM&,
 578                                const ArgPack& ap) {
 579         return make_shared_array_property_map(
 580                  num_vertices(g),
 581                  v,
 582                  override_const_property(
 583                    ap,
 584                    boost::graph::keywords::_vertex_index_map,
 585                    g, vertex_index));
 586       }
 587     };
 588
 589     template <typename Graph, typename ArgPack, typename MapTag, typename ValueType>
 590     struct map_maker {
 591       BOOST_STATIC_CONSTANT(
 592         bool,
 593         has_map =
 594           (parameter_exists<ArgPack, MapTag>
 595            ::value));
 596       typedef map_maker_helper<has_map, Graph, ArgPack, ValueType,
 597                                typename boost::remove_const<
 598                                  typename boost::parameter::value_type<
 599                                             ArgPack,
 600                                             MapTag,
 601                                             int
 602                                           >::type
 603                                         >::type> helper;
 604       typedef typename helper::map_type map_type;
 605       static map_type make_map(const Graph& g, const ArgPack& ap, ValueType default_value) {
 606         return helper::make_map(g, default_value, ap[::boost::parameter::keyword<MapTag>::instance | 0], ap);
 607       }
 608     };
 609
 610     template <typename MapTag, typename ValueType = void>
 611     class make_property_map_from_arg_pack_gen {
 612       ValueType default_value;
 613
 614       public:
 615       make_property_map_from_arg_pack_gen(ValueType default_value)
 616         : default_value(default_value) {}
 617
 618       template <typename Graph, typename ArgPack>
 619       typename map_maker<Graph, ArgPack, MapTag, ValueType>::map_type
 620       operator()(const Graph& g, const ArgPack& ap) const {
 621         return map_maker<Graph, ArgPack, MapTag, ValueType>::make_map(g, ap, default_value);
 622       }
 623     };
 624
 625     template <typename MapTag>
 626     class make_property_map_from_arg_pack_gen<MapTag, void> {
 627       public:
 628       template <typename ValueType, typename Graph, typename ArgPack>
 629       typename map_maker<Graph, ArgPack, MapTag, ValueType>::map_type
 630       operator()(const Graph& g, const ArgPack& ap, ValueType default_value) const {
 631         return map_maker<Graph, ArgPack, MapTag, ValueType>::make_map(g, ap, default_value);
 632       }
 633     };
 634
 635     static const
 636       make_property_map_from_arg_pack_gen<
 637         boost::graph::keywords::tag::color_map,
 638         default_color_type>
 639       make_color_map_from_arg_pack(white_color);
 640
 641     template <bool Exists, class Graph, class ArgPack, class KeyT, class ValueT, class KeyMapTag, class IndexInHeapMapTag, class Compare, class Q>
 642     struct priority_queue_maker_helper {
 643       typedef Q priority_queue_type;
 644
 645       static priority_queue_type
 646       make_queue(const Graph&, const ArgPack&, KeyT, const Q& q) {
 647         return q;
 648       }
 649     };
 650
 651     template <class Graph, class ArgPack, class KeyT, class ValueT, class KeyMapTag, class IndexInHeapMapTag, class Compare, class Q>
 652     struct priority_queue_maker_helper<false, Graph, ArgPack, KeyT, ValueT, KeyMapTag, IndexInHeapMapTag, Compare, Q> {
 653       typedef typename std::vector<ValueT>::size_type default_index_in_heap_type;
 654       typedef typename map_maker<Graph, ArgPack, IndexInHeapMapTag, default_index_in_heap_type>::helper::map_type index_in_heap_map;
 655       typedef boost::d_ary_heap_indirect<ValueT, 4, index_in_heap_map, typename map_maker<Graph, ArgPack, KeyMapTag, KeyT>::helper::map_type, Compare> priority_queue_type;
 656
 657       static priority_queue_type
 658       make_queue(const Graph& g, const ArgPack& ap, KeyT defaultKey, const Q&) {
 659         return priority_queue_type(
 660             map_maker<Graph, ArgPack, KeyMapTag, KeyT>::make_map(g, ap, defaultKey),
 661             map_maker<Graph, ArgPack, IndexInHeapMapTag, default_index_in_heap_type>::make_map(g, ap, typename boost::property_traits<index_in_heap_map>::value_type(-1))
 662           );
 663       }
 664     };
 665
 666     template <class Graph, class ArgPack, class KeyT, class ValueT, class PriorityQueueTag, class KeyMapTag, class IndexInHeapMapTag, class Compare>
 667     struct priority_queue_maker {
 668       BOOST_STATIC_CONSTANT(
 669         bool,
 670         g_hasQ =
 671           (parameter_exists<ArgPack, PriorityQueueTag>
 672            ::value));
 673       typedef boost::reference_wrapper<int> int_refw;
 674       typedef typename boost::parameter::value_type<
 675                          ArgPack,
 676                          PriorityQueueTag,
 677                          int_refw
 678                        >::type
 679         param_value_type_wrapper;
 680       typedef typename param_value_type_wrapper::type
 681         param_value_type;
 682       typedef typename boost::remove_const<param_value_type>::type param_value_type_no_const;
 683       typedef priority_queue_maker_helper<g_hasQ, Graph, ArgPack, KeyT, ValueT, KeyMapTag, IndexInHeapMapTag, Compare,
 684                                           param_value_type_no_const> helper;
 685       typedef typename helper::priority_queue_type priority_queue_type;
 686
 687       static priority_queue_type make_queue(const Graph& g, const ArgPack& ap, KeyT defaultKey) {
 688         return helper::make_queue(g, ap, defaultKey, ap[::boost::parameter::keyword<PriorityQueueTag>::instance | 0]);
 689       }
 690     };
 691
 692     template <class PriorityQueueTag, class KeyT, class ValueT, class Compare = std::less<KeyT>, class KeyMapTag = boost::graph::keywords::tag::distance_map, class IndexInHeapMapTag = boost::graph::keywords::tag::index_in_heap_map>
 693     struct make_priority_queue_from_arg_pack_gen {
 694       KeyT defaultKey;
 695
 696       make_priority_queue_from_arg_pack_gen(KeyT defaultKey_) : defaultKey(defaultKey_) { }
 697
 698       template <class F>
 699       struct result {
 700         typedef typename remove_const<typename remove_reference<typename function_traits<F>::arg1_type>::type>::type graph_type;
 701         typedef typename remove_const<typename remove_reference<typename function_traits<F>::arg2_type>::type>::type arg_pack_type;
 702         typedef typename priority_queue_maker<graph_type, arg_pack_type, KeyT, ValueT, PriorityQueueTag, KeyMapTag, IndexInHeapMapTag, Compare>::priority_queue_type type;
 703       };
 704
 705       template <class Graph, class ArgPack>
 706       typename priority_queue_maker<Graph, ArgPack, KeyT, ValueT, PriorityQueueTag, KeyMapTag, IndexInHeapMapTag, Compare>::priority_queue_type
 707       operator()(const Graph& g, const ArgPack& ap) const {
 708         return priority_queue_maker<Graph, ArgPack, KeyT, ValueT, PriorityQueueTag, KeyMapTag, IndexInHeapMapTag, Compare>::make_queue(g, ap, defaultKey);
 709       }
 710     };
 711
 712     template <typename G>
 713     typename boost::graph_traits<G>::vertex_descriptor
 714     get_null_vertex(const G&) {return boost::graph_traits<G>::null_vertex();}
 715
 716     template <typename G>
 717     typename boost::graph_traits<G>::vertex_descriptor
 718     get_default_starting_vertex(const G& g) {
 719       std::pair<typename boost::graph_traits<G>::vertex_iterator, typename boost::graph_traits<G>::vertex_iterator> iters = vertices(g);
 720       return (iters.first == iters.second) ? boost::graph_traits<G>::null_vertex() : *iters.first;
 721     }
 722
 723     template <typename G>
 724     struct get_default_starting_vertex_t {
 725       typedef typename boost::graph_traits<G>::vertex_descriptor result_type;
 726       const G& g;
 727       get_default_starting_vertex_t(const G& g): g(g) {}
 728       result_type operator()() const {return get_default_starting_vertex(g);}
 729     };
 730
 731     // Wrapper to avoid instantiating numeric_limits when users provide distance_inf value manually
 732     template <typename T>
 733     struct get_max {
 734       T operator()() const {
 735         return (std::numeric_limits<T>::max)();
 736       }
 737       typedef T result_type;
 738     };
 739
 740   } // namespace detail
 741
 742 } // namespace boost
 743
 744 #undef BOOST_BGL_DECLARE_NAMED_PARAMS
 745
 746 #endif // BOOST_GRAPH_NAMED_FUNCTION_PARAMS_HPP