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