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