1 | //======================================================================= |
2 | // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. |
3 | // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek |
4 | // |
5 | // Distributed under the Boost Software License, Version 1.0. (See |
6 | // accompanying file LICENSE_1_0.txt or copy at |
7 | // http://www.boost.org/LICENSE_1_0.txt) |
8 | //======================================================================= |
9 | |
10 | #ifndef BOOST_GRAPH_NAMED_FUNCTION_PARAMS_HPP |
11 | #define BOOST_GRAPH_NAMED_FUNCTION_PARAMS_HPP |
12 | |
13 | #include <functional> |
14 | #include <vector> |
15 | #include <boost/limits.hpp> |
16 | #include <boost/ref.hpp> |
17 | #include <boost/utility/result_of.hpp> |
18 | #include <boost/preprocessor.hpp> |
19 | #include <boost/parameter/name.hpp> |
20 | #include <boost/parameter/binding.hpp> |
21 | #include <boost/type_traits.hpp> |
22 | #include <boost/mpl/not.hpp> |
23 | #include <boost/graph/properties.hpp> |
24 | #include <boost/graph/detail/d_ary_heap.hpp> |
25 | #include <boost/property_map/property_map.hpp> |
26 | #include <boost/property_map/shared_array_property_map.hpp> |
27 | |
28 | namespace boost { |
29 | |
30 | struct parity_map_t { }; |
31 | struct vertex_assignment_map_t { }; |
32 | struct distance_compare_t { }; |
33 | struct distance_combine_t { }; |
34 | struct distance_inf_t { }; |
35 | struct distance_zero_t { }; |
36 | struct buffer_param_t { }; |
37 | struct edge_copy_t { }; |
38 | struct vertex_copy_t { }; |
39 | struct vertex_isomorphism_t { }; |
40 | struct vertex_invariant_t { }; |
41 | struct vertex_invariant1_t { }; |
42 | struct vertex_invariant2_t { }; |
43 | struct edge_compare_t { }; |
44 | struct vertex_max_invariant_t { }; |
45 | struct orig_to_copy_t { }; |
46 | struct root_vertex_t { }; |
47 | struct polling_t { }; |
48 | struct lookahead_t { }; |
49 | struct in_parallel_t { }; |
50 | struct attractive_force_t { }; |
51 | struct repulsive_force_t { }; |
52 | struct force_pairs_t { }; |
53 | struct cooling_t { }; |
54 | struct vertex_displacement_t { }; |
55 | struct iterations_t { }; |
56 | struct diameter_range_t { }; |
57 | struct learning_constant_range_t { }; |
58 | struct vertices_equivalent_t { }; |
59 | struct edges_equivalent_t { }; |
60 | struct index_in_heap_map_t { }; |
61 | struct max_priority_queue_t { }; |
62 | |
63 | #define BOOST_BGL_DECLARE_NAMED_PARAMS \ |
64 | BOOST_BGL_ONE_PARAM_CREF(weight_map, edge_weight) \ |
65 | BOOST_BGL_ONE_PARAM_CREF(weight_map2, edge_weight2) \ |
66 | BOOST_BGL_ONE_PARAM_CREF(distance_map, vertex_distance) \ |
67 | BOOST_BGL_ONE_PARAM_CREF(distance_map2, vertex_distance2) \ |
68 | BOOST_BGL_ONE_PARAM_CREF(predecessor_map, vertex_predecessor) \ |
69 | BOOST_BGL_ONE_PARAM_CREF(rank_map, vertex_rank) \ |
70 | BOOST_BGL_ONE_PARAM_CREF(root_map, vertex_root) \ |
71 | BOOST_BGL_ONE_PARAM_CREF(root_vertex, root_vertex) \ |
72 | BOOST_BGL_ONE_PARAM_CREF(edge_centrality_map, edge_centrality) \ |
73 | BOOST_BGL_ONE_PARAM_CREF(centrality_map, vertex_centrality) \ |
74 | BOOST_BGL_ONE_PARAM_CREF(parity_map, parity_map) \ |
75 | BOOST_BGL_ONE_PARAM_CREF(color_map, vertex_color) \ |
76 | BOOST_BGL_ONE_PARAM_CREF(edge_color_map, edge_color) \ |
77 | BOOST_BGL_ONE_PARAM_CREF(capacity_map, edge_capacity) \ |
78 | BOOST_BGL_ONE_PARAM_CREF(residual_capacity_map, edge_residual_capacity) \ |
79 | BOOST_BGL_ONE_PARAM_CREF(reverse_edge_map, edge_reverse) \ |
80 | BOOST_BGL_ONE_PARAM_CREF(discover_time_map, vertex_discover_time) \ |
81 | BOOST_BGL_ONE_PARAM_CREF(lowpoint_map, vertex_lowpoint) \ |
82 | BOOST_BGL_ONE_PARAM_CREF(vertex_index_map, vertex_index) \ |
83 | BOOST_BGL_ONE_PARAM_CREF(vertex_index1_map, vertex_index1) \ |
84 | BOOST_BGL_ONE_PARAM_CREF(vertex_index2_map, vertex_index2) \ |
85 | BOOST_BGL_ONE_PARAM_CREF(vertex_assignment_map, vertex_assignment_map) \ |
86 | BOOST_BGL_ONE_PARAM_CREF(visitor, graph_visitor) \ |
87 | BOOST_BGL_ONE_PARAM_CREF(distance_compare, distance_compare) \ |
88 | BOOST_BGL_ONE_PARAM_CREF(distance_combine, distance_combine) \ |
89 | BOOST_BGL_ONE_PARAM_CREF(distance_inf, distance_inf) \ |
90 | BOOST_BGL_ONE_PARAM_CREF(distance_zero, distance_zero) \ |
91 | BOOST_BGL_ONE_PARAM_CREF(edge_copy, edge_copy) \ |
92 | BOOST_BGL_ONE_PARAM_CREF(vertex_copy, vertex_copy) \ |
93 | BOOST_BGL_ONE_PARAM_REF(buffer, buffer_param) \ |
94 | BOOST_BGL_ONE_PARAM_CREF(orig_to_copy, orig_to_copy) \ |
95 | BOOST_BGL_ONE_PARAM_CREF(isomorphism_map, vertex_isomorphism) \ |
96 | BOOST_BGL_ONE_PARAM_CREF(vertex_invariant, vertex_invariant) \ |
97 | BOOST_BGL_ONE_PARAM_CREF(vertex_invariant1, vertex_invariant1) \ |
98 | BOOST_BGL_ONE_PARAM_CREF(vertex_invariant2, vertex_invariant2) \ |
99 | BOOST_BGL_ONE_PARAM_CREF(vertex_max_invariant, vertex_max_invariant) \ |
100 | BOOST_BGL_ONE_PARAM_CREF(polling, polling) \ |
101 | BOOST_BGL_ONE_PARAM_CREF(, lookahead) \ |
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 | |
144 | BOOST_BGL_DECLARE_NAMED_PARAMS |
145 | |
146 | #undef BOOST_BGL_ONE_PARAM_REF |
147 | #undef BOOST_BGL_ONE_PARAM_CREF |
148 | |
149 | // Duplicate |
150 | template <typename PType> |
151 | bgl_named_params<PType, vertex_color_t, self> |
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 | |
171 | BOOST_BGL_DECLARE_NAMED_PARAMS |
172 | |
173 | #undef BOOST_BGL_ONE_PARAM_REF |
174 | #undef BOOST_BGL_ONE_PARAM_CREF |
175 | |
176 | // Duplicate |
177 | template <typename PType> |
178 | bgl_named_params<PType, vertex_color_t> |
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 | |