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