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; bgl_named_paramsboost::bgl_named_params123 bgl_named_params(T v = T()) : m_value(v) { } bgl_named_paramsboost::bgl_named_params124 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> vertex_color_mapboost::bgl_named_params152 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> vertex_color_map(const PType & p)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; getboost::lookup_named_param195 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; getboost::lookup_named_param203 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; getboost::lookup_named_param_def211 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; getboost::lookup_named_param_def217 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; getboost::lookup_named_param_def225 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& get_param(const Args & p,Tag)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> choose_param(const P & param,const Default &)244 const P& choose_param(const P& param, const Default&) { 245 return param; 246 } 247 248 template <class Default> choose_param(const param_not_found &,const Default & d)249 Default choose_param(const param_not_found&, const Default& d) { 250 return d; 251 } 252 253 template <typename T> is_default_param(const T &)254 inline bool is_default_param(const T&) { return false; } 255 is_default_param(const param_not_found &)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 fboost::detail::choose_impl_helper284 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 fboost::detail::choose_impl_helper290 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> fboost::detail::choose_impl_helper297 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 choose_const_pmap(const Param & p,const Graph & g,PropertyTag tag)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 choose_pmap(const Param & p,Graph & g,PropertyTag tag)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<Params, edge_capacity_t>::type, edge_capacity_t>::type CapacityEdgeMap; 327 typedef typename property_traits<CapacityEdgeMap>::value_type type; 328 }; 329 330 } 331 332 // Declare all new tags 333 namespace graph { 334 namespace keywords { 335 #define BOOST_BGL_ONE_PARAM_REF(name, key) BOOST_PARAMETER_NAME(name) 336 #define BOOST_BGL_ONE_PARAM_CREF(name, key) BOOST_PARAMETER_NAME(name) 337 BOOST_BGL_DECLARE_NAMED_PARAMS 338 #undef BOOST_BGL_ONE_PARAM_REF 339 #undef BOOST_BGL_ONE_PARAM_CREF 340 } 341 } 342 343 namespace detail { 344 template <typename Tag> struct convert_one_keyword {}; 345 #define BOOST_BGL_ONE_PARAM_REF(name, key) \ 346 template <> \ 347 struct convert_one_keyword<BOOST_PP_CAT(key, _t)> { \ 348 typedef boost::graph::keywords::tag::name type; \ 349 }; 350 #define BOOST_BGL_ONE_PARAM_CREF(name, key) BOOST_BGL_ONE_PARAM_REF(name, key) 351 BOOST_BGL_DECLARE_NAMED_PARAMS 352 #undef BOOST_BGL_ONE_PARAM_REF 353 #undef BOOST_BGL_ONE_PARAM_CREF 354 355 template <typename T> 356 struct convert_bgl_params_to_boost_parameter { 357 typedef typename convert_one_keyword<typename T::tag_type>::type new_kw; 358 typedef boost::parameter::aux::tagged_argument<new_kw, const typename T::value_type> tagged_arg_type; 359 typedef convert_bgl_params_to_boost_parameter<typename T::next_type> rest_conv; 360 typedef boost::parameter::aux::arg_list<tagged_arg_type, typename rest_conv::type> type; convboost::detail::convert_bgl_params_to_boost_parameter361 static type conv(const T& x) { 362 return type(tagged_arg_type(x.m_value), rest_conv::conv(x.m_base)); 363 } 364 }; 365 366 template <typename P, typename R> 367 struct convert_bgl_params_to_boost_parameter<bgl_named_params<P, int, R> > { 368 typedef convert_bgl_params_to_boost_parameter<R> rest_conv; 369 typedef typename rest_conv::type type; convboost::detail::convert_bgl_params_to_boost_parameter370 static type conv(const bgl_named_params<P, int, R>& x) { 371 return rest_conv::conv(x.m_base); 372 } 373 }; 374 375 template <> 376 struct convert_bgl_params_to_boost_parameter<boost::no_property> { 377 typedef boost::parameter::aux::empty_arg_list type; convboost::detail::convert_bgl_params_to_boost_parameter378 static type conv(const boost::no_property&) {return type();} 379 }; 380 381 template <> 382 struct convert_bgl_params_to_boost_parameter<boost::no_named_parameters> { 383 typedef boost::parameter::aux::empty_arg_list type; convboost::detail::convert_bgl_params_to_boost_parameter384 static type conv(const boost::no_named_parameters&) {return type();} 385 }; 386 387 struct bgl_parameter_not_found_type {}; 388 389 template <typename ArgPack, typename KeywordType> 390 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> > {}; 391 } 392 393 #define BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(old_type, old_var) \ 394 typedef typename boost::detail::convert_bgl_params_to_boost_parameter<old_type>::type arg_pack_type; \ 395 arg_pack_type arg_pack = boost::detail::convert_bgl_params_to_boost_parameter<old_type>::conv(old_var); 396 397 namespace detail { 398 399 template <typename ArgType, typename Prop, typename Graph, bool Exists> 400 struct override_const_property_t { 401 typedef typename boost::remove_const<ArgType>::type result_type; operator ()boost::detail::override_const_property_t402 result_type operator()(const Graph&, const ArgType& a) const {return a;} 403 }; 404 405 template <typename ArgType, typename Prop, typename Graph> 406 struct override_const_property_t<ArgType, Prop, Graph, false> { 407 typedef typename boost::property_map<Graph, Prop>::const_type result_type; operator ()boost::detail::override_const_property_t408 result_type operator()(const Graph& g, const ArgType&) const {return get(Prop(), g);} 409 }; 410 411 template <typename ArgPack, typename Tag, typename Prop, typename Graph> 412 struct override_const_property_result { 413 typedef 414 typename override_const_property_t< 415 typename boost::parameter::value_type<ArgPack, Tag, int>::type, 416 Prop, 417 Graph, 418 boost::detail::parameter_exists<ArgPack, Tag>::value 419 >::result_type 420 type; 421 }; 422 423 template <typename ArgPack, typename Tag, typename Prop, typename Graph> 424 typename override_const_property_result<ArgPack, Tag, Prop, Graph>::type override_const_property(const ArgPack & ap,const boost::parameter::keyword<Tag> & t,const Graph & g,Prop)425 override_const_property(const ArgPack& ap, const boost::parameter::keyword<Tag>& t, const Graph& g, Prop) { 426 return override_const_property_t< 427 typename boost::parameter::value_type<ArgPack, Tag, int>::type, 428 Prop, 429 Graph, 430 boost::detail::parameter_exists<ArgPack, Tag>::value 431 >()(g, ap[t | 0]); 432 } 433 434 template <typename ArgType, typename Prop, typename Graph, bool Exists> 435 struct override_property_t { 436 typedef ArgType result_type; operator ()boost::detail::override_property_t437 result_type operator()(const Graph&, const typename boost::add_reference<ArgType>::type a) const {return a;} 438 }; 439 440 template <typename ArgType, typename Prop, typename Graph> 441 struct override_property_t<ArgType, Prop, Graph, false> { 442 typedef typename boost::property_map<Graph, Prop>::type result_type; operator ()boost::detail::override_property_t443 result_type operator()(const Graph& g, const ArgType&) const {return get(Prop(), g);} 444 }; 445 446 template <typename ArgPack, typename Tag, typename Prop, typename Graph> 447 struct override_property_result { 448 typedef 449 typename override_property_t< 450 typename boost::parameter::value_type<ArgPack, Tag, int>::type, 451 Prop, 452 Graph, 453 boost::detail::parameter_exists<ArgPack, Tag>::value 454 >::result_type 455 type; 456 }; 457 458 template <typename ArgPack, typename Tag, typename Prop, typename Graph> 459 typename override_property_result<ArgPack, Tag, Prop, Graph>::type override_property(const ArgPack & ap,const boost::parameter::keyword<Tag> & t,const Graph & g,Prop)460 override_property(const ArgPack& ap, const boost::parameter::keyword<Tag>& t, const Graph& g, Prop) { 461 return override_property_t< 462 typename boost::parameter::value_type<ArgPack, Tag, int>::type, 463 Prop, 464 Graph, 465 boost::detail::parameter_exists<ArgPack, Tag>::value 466 >()(g, ap[t | 0]); 467 } 468 469 template <typename F> struct make_arg_pack_type; 470 template <> struct make_arg_pack_type<void()> {typedef boost::parameter::aux::empty_arg_list type;}; 471 template <typename K, typename A> 472 struct make_arg_pack_type<void(K, A)> { 473 typedef boost::parameter::aux::tagged_argument<K, A> type; 474 }; 475 476 #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))>, 477 #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) 478 479 #define BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION(z, i, _) \ 480 template <BOOST_PP_ENUM_PARAMS(i, typename Keyword), BOOST_PP_ENUM_PARAMS(i, typename Arg)> \ 481 struct make_arg_pack_type<void(BOOST_PP_ENUM_PARAMS(i, Keyword), BOOST_PP_ENUM_PARAMS(i, Arg))> { \ 482 typedef \ 483 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), ~) \ 484 type; \ 485 }; 486 BOOST_PP_REPEAT_FROM_TO(2, 11, BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION, ~) 487 #undef BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION 488 489 #define BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(name, nfixed, nnamed_max) \ 490 /* Entry point for conversion from BGL-style named parameters */ \ 491 template <BOOST_PP_ENUM_PARAMS(nfixed, typename Param) BOOST_PP_COMMA_IF(nfixed) typename ArgPack> \ 492 typename boost::result_of< \ 493 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&) \ 494 >::type \ 495 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) { \ 496 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); \ 497 } \ 498 /* Individual functions taking Boost.Parameter-style keyword arguments */ \ 499 BOOST_PP_REPEAT(BOOST_PP_INC(nnamed_max), BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONE, (name)(nfixed)) 500 501 #define BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONE(z, nnamed, seq) \ 502 BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONEX(z, nnamed, BOOST_PP_SEQ_ELEM(0, seq), BOOST_PP_SEQ_ELEM(1, seq)) 503 504 #define BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONEX(z, nnamed, name, nfixed) \ 505 template <BOOST_PP_ENUM_PARAMS(nfixed, typename Param) BOOST_PP_ENUM_TRAILING_PARAMS(nnamed, typename Keyword) BOOST_PP_ENUM_TRAILING_PARAMS(nnamed, typename Arg)> \ 506 typename boost::result_of< \ 507 detail::BOOST_PP_CAT(name, _impl)<BOOST_PP_ENUM_PARAMS(nfixed, Param)> \ 508 (BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_COMMA_IF(nfixed) \ 509 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&) \ 510 >::type \ 511 name(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, & param) \ 512 BOOST_PP_ENUM_TRAILING(nnamed, BOOST_GRAPH_MAKE_PAIR_PARAM, ~)) { \ 513 return detail::BOOST_PP_CAT(name, _impl)<BOOST_PP_ENUM_PARAMS(nfixed, Param)>() \ 514 (BOOST_PP_ENUM_PARAMS(nfixed, param), \ 515 (boost::parameter::aux::empty_arg_list() BOOST_PP_ENUM_TRAILING_PARAMS(nnamed, kw))); \ 516 } 517 518 #define BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(name, nfixed) \ 519 template <BOOST_PP_ENUM_PARAMS(nfixed, typename Param) BOOST_PP_COMMA_IF(nfixed) class P, class T, class R> \ 520 typename boost::result_of< \ 521 ::boost::graph::detail::BOOST_PP_CAT(name, _impl) BOOST_PP_EXPR_IF(nfixed, <) BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_EXPR_IF(nfixed, >) \ 522 (BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_COMMA_IF(nfixed) \ 523 const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<P, T, R> >::type &) \ 524 >::type \ 525 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) { \ 526 typedef boost::bgl_named_params<P, T, R> old_style_params_type; \ 527 BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(old_style_params_type, old_style_params) \ 528 return ::boost::graph::BOOST_PP_CAT(name, _with_named_params)(BOOST_PP_ENUM_PARAMS(nfixed, param) BOOST_PP_COMMA_IF(nfixed) arg_pack); \ 529 } \ 530 \ 531 BOOST_PP_EXPR_IF(nfixed, template <) BOOST_PP_ENUM_PARAMS(nfixed, typename Param) BOOST_PP_EXPR_IF(nfixed, >) \ 532 BOOST_PP_EXPR_IF(nfixed, typename) boost::result_of< \ 533 ::boost::graph::detail::BOOST_PP_CAT(name, _impl) BOOST_PP_EXPR_IF(nfixed, <) BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_EXPR_IF(nfixed, >) \ 534 (BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_COMMA_IF(nfixed) const boost::parameter::aux::empty_arg_list &) \ 535 >::type \ 536 name(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, & param)) { \ 537 BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(boost::no_named_parameters, boost::no_named_parameters()) \ 538 return ::boost::graph::BOOST_PP_CAT(name, _with_named_params)(BOOST_PP_ENUM_PARAMS(nfixed, param) BOOST_PP_COMMA_IF(nfixed) arg_pack); \ 539 } 540 541 } 542 543 namespace detail { 544 545 template <bool Exists, typename Graph, typename ArgPack, typename Value, typename PM> 546 struct map_maker_helper { 547 typedef PM map_type; make_mapboost::detail::map_maker_helper548 static PM make_map(const Graph&, Value, const PM& pm, const ArgPack&) { 549 return pm; 550 } 551 }; 552 553 template <typename Graph, typename ArgPack, typename Value, typename PM> 554 struct map_maker_helper<false, Graph, ArgPack, Value, PM> { 555 typedef typename boost::remove_const< 556 typename override_const_property_t< 557 typename boost::parameter::value_type< 558 ArgPack, boost::graph::keywords::tag::vertex_index_map, int>::type, 559 boost::vertex_index_t, 560 Graph, 561 boost::detail::parameter_exists< 562 ArgPack, boost::graph::keywords::tag::vertex_index_map>::value 563 >::result_type>::type vi_map_type; 564 typedef 565 boost::shared_array_property_map<Value, vi_map_type> 566 map_type; make_mapboost::detail::map_maker_helper567 static map_type make_map(const Graph& g, 568 Value v, 569 const PM&, 570 const ArgPack& ap) { 571 return make_shared_array_property_map( 572 num_vertices(g), 573 v, 574 override_const_property( 575 ap, 576 boost::graph::keywords::_vertex_index_map, 577 g, vertex_index)); 578 } 579 }; 580 581 template <typename Graph, typename ArgPack, typename MapTag, typename ValueType> 582 struct map_maker { 583 BOOST_STATIC_CONSTANT( 584 bool, 585 has_map = 586 (parameter_exists<ArgPack, MapTag> 587 ::value)); 588 typedef map_maker_helper<has_map, Graph, ArgPack, ValueType, 589 typename boost::remove_const< 590 typename boost::parameter::value_type< 591 ArgPack, 592 MapTag, 593 int 594 >::type 595 >::type> helper; 596 typedef typename helper::map_type map_type; make_mapboost::detail::map_maker597 static map_type make_map(const Graph& g, const ArgPack& ap, ValueType default_value) { 598 return helper::make_map(g, default_value, ap[::boost::parameter::keyword<MapTag>::instance | 0], ap); 599 } 600 }; 601 602 template <typename MapTag, typename ValueType = void> 603 class make_property_map_from_arg_pack_gen { 604 ValueType default_value; 605 606 public: make_property_map_from_arg_pack_gen(ValueType default_value)607 make_property_map_from_arg_pack_gen(ValueType default_value) 608 : default_value(default_value) {} 609 610 template <typename Graph, typename ArgPack> 611 typename map_maker<Graph, ArgPack, MapTag, ValueType>::map_type operator ()(const Graph & g,const ArgPack & ap) const612 operator()(const Graph& g, const ArgPack& ap) const { 613 return map_maker<Graph, ArgPack, MapTag, ValueType>::make_map(g, ap, default_value); 614 } 615 }; 616 617 template <typename MapTag> 618 class make_property_map_from_arg_pack_gen<MapTag, void> { 619 public: 620 template <typename ValueType, typename Graph, typename ArgPack> 621 typename map_maker<Graph, ArgPack, MapTag, ValueType>::map_type operator ()(const Graph & g,const ArgPack & ap,ValueType default_value) const622 operator()(const Graph& g, const ArgPack& ap, ValueType default_value) const { 623 return map_maker<Graph, ArgPack, MapTag, ValueType>::make_map(g, ap, default_value); 624 } 625 }; 626 627 static const 628 make_property_map_from_arg_pack_gen< 629 boost::graph::keywords::tag::color_map, 630 default_color_type> 631 make_color_map_from_arg_pack(white_color); 632 633 template <bool Exists, class Graph, class ArgPack, class KeyT, class ValueT, class KeyMapTag, class IndexInHeapMapTag, class Compare, class Q> 634 struct priority_queue_maker_helper { 635 typedef Q priority_queue_type; 636 637 static priority_queue_type make_queueboost::detail::priority_queue_maker_helper638 make_queue(const Graph&, const ArgPack&, KeyT, const Q& q) { 639 return q; 640 } 641 }; 642 643 template <class Graph, class ArgPack, class KeyT, class ValueT, class KeyMapTag, class IndexInHeapMapTag, class Compare, class Q> 644 struct priority_queue_maker_helper<false, Graph, ArgPack, KeyT, ValueT, KeyMapTag, IndexInHeapMapTag, Compare, Q> { 645 typedef typename std::vector<ValueT>::size_type default_index_in_heap_type; 646 typedef typename map_maker<Graph, ArgPack, IndexInHeapMapTag, default_index_in_heap_type>::helper::map_type index_in_heap_map; 647 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; 648 649 static priority_queue_type make_queueboost::detail::priority_queue_maker_helper650 make_queue(const Graph& g, const ArgPack& ap, KeyT defaultKey, const Q&) { 651 return priority_queue_type( 652 map_maker<Graph, ArgPack, KeyMapTag, KeyT>::make_map(g, ap, defaultKey), 653 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)) 654 ); 655 } 656 }; 657 658 template <class Graph, class ArgPack, class KeyT, class ValueT, class PriorityQueueTag, class KeyMapTag, class IndexInHeapMapTag, class Compare> 659 struct priority_queue_maker { 660 BOOST_STATIC_CONSTANT( 661 bool, 662 g_hasQ = 663 (parameter_exists<ArgPack, PriorityQueueTag> 664 ::value)); 665 typedef boost::reference_wrapper<int> int_refw; 666 typedef typename boost::parameter::value_type< 667 ArgPack, 668 PriorityQueueTag, 669 int_refw 670 >::type 671 param_value_type_wrapper; 672 typedef typename param_value_type_wrapper::type 673 param_value_type; 674 typedef typename boost::remove_const<param_value_type>::type param_value_type_no_const; 675 typedef priority_queue_maker_helper<g_hasQ, Graph, ArgPack, KeyT, ValueT, KeyMapTag, IndexInHeapMapTag, Compare, 676 param_value_type_no_const> helper; 677 typedef typename helper::priority_queue_type priority_queue_type; 678 make_queueboost::detail::priority_queue_maker679 static priority_queue_type make_queue(const Graph& g, const ArgPack& ap, KeyT defaultKey) { 680 return helper::make_queue(g, ap, defaultKey, ap[::boost::parameter::keyword<PriorityQueueTag>::instance | 0]); 681 } 682 }; 683 684 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> 685 struct make_priority_queue_from_arg_pack_gen { 686 KeyT defaultKey; 687 make_priority_queue_from_arg_pack_genboost::detail::make_priority_queue_from_arg_pack_gen688 make_priority_queue_from_arg_pack_gen(KeyT defaultKey_) : defaultKey(defaultKey_) { } 689 690 template <class F> 691 struct result { 692 typedef typename remove_const<typename remove_reference<typename function_traits<F>::arg1_type>::type>::type graph_type; 693 typedef typename remove_const<typename remove_reference<typename function_traits<F>::arg2_type>::type>::type arg_pack_type; 694 typedef typename priority_queue_maker<graph_type, arg_pack_type, KeyT, ValueT, PriorityQueueTag, KeyMapTag, IndexInHeapMapTag, Compare>::priority_queue_type type; 695 }; 696 697 template <class Graph, class ArgPack> 698 typename priority_queue_maker<Graph, ArgPack, KeyT, ValueT, PriorityQueueTag, KeyMapTag, IndexInHeapMapTag, Compare>::priority_queue_type operator ()boost::detail::make_priority_queue_from_arg_pack_gen699 operator()(const Graph& g, const ArgPack& ap) const { 700 return priority_queue_maker<Graph, ArgPack, KeyT, ValueT, PriorityQueueTag, KeyMapTag, IndexInHeapMapTag, Compare>::make_queue(g, ap, defaultKey); 701 } 702 }; 703 704 template <typename G> 705 typename boost::graph_traits<G>::vertex_descriptor get_null_vertex(const G &)706 get_null_vertex(const G&) {return boost::graph_traits<G>::null_vertex();} 707 708 template <typename G> 709 typename boost::graph_traits<G>::vertex_descriptor get_default_starting_vertex(const G & g)710 get_default_starting_vertex(const G& g) { 711 std::pair<typename boost::graph_traits<G>::vertex_iterator, typename boost::graph_traits<G>::vertex_iterator> iters = vertices(g); 712 return (iters.first == iters.second) ? boost::graph_traits<G>::null_vertex() : *iters.first; 713 } 714 715 template <typename G> 716 struct get_default_starting_vertex_t { 717 typedef typename boost::graph_traits<G>::vertex_descriptor result_type; 718 const G& g; get_default_starting_vertex_tboost::detail::get_default_starting_vertex_t719 get_default_starting_vertex_t(const G& g): g(g) {} operator ()boost::detail::get_default_starting_vertex_t720 result_type operator()() const {return get_default_starting_vertex(g);} 721 }; 722 723 // Wrapper to avoid instantiating numeric_limits when users provide distance_inf value manually 724 template <typename T> 725 struct get_max { operator ()boost::detail::get_max726 T operator()() const { 727 return (std::numeric_limits<T>::max)(); 728 } 729 typedef T result_type; 730 }; 731 732 } // namespace detail 733 734 } // namespace boost 735 736 #undef BOOST_BGL_DECLARE_NAMED_PARAMS 737 738 #endif // BOOST_GRAPH_NAMED_FUNCTION_PARAMS_HPP 739