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; bgl_named_paramsboost::bgl_named_params126 bgl_named_params(T v = T()) : m_value(v) { } bgl_named_paramsboost::bgl_named_params127 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> vertex_color_mapboost::bgl_named_params155 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> vertex_color_map(const PType & p)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; getboost::lookup_named_param198 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; getboost::lookup_named_param206 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; getboost::lookup_named_param_def214 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; getboost::lookup_named_param_def220 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; getboost::lookup_named_param_def228 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& get_param(const Args & p,Tag)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> choose_param(const P & param,const Default &)248 const P& choose_param(const P& param, const Default&) { 249 return param; 250 } 251 252 template <class Default> choose_param(const param_not_found &,const Default & d)253 Default choose_param(const param_not_found&, const Default& d) { 254 return d; 255 } 256 257 template <typename T> is_default_param(const T &)258 inline bool is_default_param(const T&) { return false; } 259 is_default_param(const param_not_found &)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 fboost::detail::choose_impl_helper288 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 fboost::detail::choose_impl_helper294 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> fboost::detail::choose_impl_helper301 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 choose_const_pmap(const Param & p,const Graph & g,PropertyTag tag)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 choose_pmap(const Param & p,Graph & g,PropertyTag tag)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; convboost::detail::convert_bgl_params_to_boost_parameter373 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; convboost::detail::convert_bgl_params_to_boost_parameter382 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; convboost::detail::convert_bgl_params_to_boost_parameter390 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; convboost::detail::convert_bgl_params_to_boost_parameter396 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; operator ()boost::detail::override_const_property_t411 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; operator ()boost::detail::override_const_property_t417 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 override_const_property(const ArgPack & ap,const boost::parameter::keyword<Tag> & t,const Graph & g,Prop)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; operator ()boost::detail::override_property_t448 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; operator ()boost::detail::override_property_t454 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 override_property(const ArgPack & ap,const boost::parameter::keyword<Tag> & t,const Graph & g,Prop)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; make_mapboost::detail::map_maker_helper569 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; make_mapboost::detail::map_maker_helper591 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; make_mapboost::detail::map_maker618 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: make_property_map_from_arg_pack_gen(ValueType default_value)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 operator ()(const Graph & g,const ArgPack & ap) const633 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 operator ()(const Graph & g,const ArgPack & ap,ValueType default_value) const643 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 make_queueboost::detail::priority_queue_maker_helper659 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 make_queueboost::detail::priority_queue_maker_helper671 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 make_queueboost::detail::priority_queue_maker697 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 make_priority_queue_from_arg_pack_genboost::detail::make_priority_queue_from_arg_pack_gen706 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 operator ()boost::detail::make_priority_queue_from_arg_pack_gen717 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 get_null_vertex(const G &)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 get_default_starting_vertex(const G & g)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; get_default_starting_vertex_tboost::detail::get_default_starting_vertex_t737 get_default_starting_vertex_t(const G& g): g(g) {} operator ()boost::detail::get_default_starting_vertex_t738 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 { operator ()boost::detail::get_max744 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 757