Line data Source code
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;
126 0 : bgl_named_params(T v = T()) : m_value(v) { }
127 0 : 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 0 : 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>
155 : 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 0 : 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>
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;
198 : 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;
206 : 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;
214 0 : 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;
220 0 : static const type& get(const bgl_named_params<T, Tag, Base>& p, const Def&) {
221 0 : 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;
228 0 : static const type& get(const bgl_named_params<T, Tag, Base>& p, const Def& def) {
229 0 : 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&
243 0 : get_param(const Args& p, Tag) {
244 0 : return lookup_named_param_def<Tag, Args, param_not_found>::get(p, g_param_not_found);
245 : }
246 :
247 : template <class P, class Default>
248 0 : const P& choose_param(const P& param, const Default&) {
249 : return param;
250 : }
251 :
252 : template <class Default>
253 0 : Default choose_param(const param_not_found&, const Default& d) {
254 : return d;
255 : }
256 :
257 : template <typename T>
258 0 : inline bool is_default_param(const T&) { return false; }
259 :
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
288 0 : f(boost::mpl::true_, const Graph& g, const Param&, PropertyTag tag) {
289 0 : 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
294 : 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>
301 : 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
309 0 : 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 0 : ::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
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;
373 0 : static type conv(const T& x) {
374 0 : 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;
382 : 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;
390 0 : 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;
396 : 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;
411 : 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;
417 : 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
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;
448 : 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;
454 : 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
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;
569 : 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;
591 : 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;
618 : 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:
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
633 0 : operator()(const Graph& g, const ArgPack& ap) const {
634 0 : 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
643 : 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
659 : 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
671 : 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 :
697 : 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 :
706 : 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
717 : 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
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
728 0 : get_default_starting_vertex(const G& g) {
729 0 : std::pair<typename boost::graph_traits<G>::vertex_iterator, typename boost::graph_traits<G>::vertex_iterator> iters = vertices(g);
730 0 : 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;
737 0 : get_default_starting_vertex_t(const G& g): g(g) {}
738 0 : 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 {
744 : 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
|
