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
28namespace 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;
123 bgl_named_params(T v = T()) : m_value(v) { }
124 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
144BOOST_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>
152 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
171BOOST_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>
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;
195 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;
203 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;
211 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;
217 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;
225 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&
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>
244 const P& choose_param(const P& param, const Default&) {
245 return param;
246 }
247
248 template <class Default>
249 Default choose_param(const param_not_found&, const Default& d) {
250 return d;
251 }
252
253 template <typename T>
254 inline bool is_default_param(const T&) { return false; }
255
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
284 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
290 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>
297 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
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
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;
361 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;
370 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;
378 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;
384 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;
402 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;
408 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
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;
437 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;
443 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
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;
548 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;
567 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;
597 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:
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
612 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
622 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
638 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
650 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
679 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
688 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
699 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
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
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;
719 get_default_starting_vertex_t(const G& g): g(g) {}
720 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 {
726 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

source code of boost/boost/graph/named_function_params.hpp