]>
Commit | Line | Data |
---|---|---|
1 | //======================================================================= | |
2 | // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. | |
3 | // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek | |
4 | // | |
5 | // Distributed under the Boost Software License, Version 1.0. (See | |
6 | // accompanying file LICENSE_1_0.txt or copy at | |
7 | // http://www.boost.org/LICENSE_1_0.txt) | |
8 | //======================================================================= | |
9 | ||
10 | #ifndef BOOST_GRAPH_NAMED_FUNCTION_PARAMS_HPP | |
11 | #define BOOST_GRAPH_NAMED_FUNCTION_PARAMS_HPP | |
12 | ||
13 | #include <functional> | |
14 | #include <vector> | |
15 | #include <boost/limits.hpp> | |
16 | #include <boost/ref.hpp> | |
17 | #include <boost/utility/result_of.hpp> | |
18 | #include <boost/preprocessor.hpp> | |
19 | #include <boost/parameter/name.hpp> | |
20 | #include <boost/parameter/binding.hpp> | |
21 | #include <boost/type_traits.hpp> | |
22 | #include <boost/mpl/not.hpp> | |
23 | #include <boost/graph/properties.hpp> | |
24 | #include <boost/graph/detail/d_ary_heap.hpp> | |
25 | #include <boost/property_map/property_map.hpp> | |
26 | #include <boost/property_map/shared_array_property_map.hpp> | |
27 | ||
28 | namespace boost { | |
29 | ||
30 | struct parity_map_t { }; | |
31 | struct vertex_assignment_map_t { }; | |
32 | struct distance_compare_t { }; | |
33 | struct distance_combine_t { }; | |
34 | struct distance_inf_t { }; | |
35 | struct distance_zero_t { }; | |
36 | struct buffer_param_t { }; | |
37 | struct edge_copy_t { }; | |
38 | struct vertex_copy_t { }; | |
39 | struct vertex_isomorphism_t { }; | |
40 | struct vertex_invariant_t { }; | |
41 | struct vertex_invariant1_t { }; | |
42 | struct vertex_invariant2_t { }; | |
43 | struct edge_compare_t { }; | |
44 | struct vertex_max_invariant_t { }; | |
45 | struct orig_to_copy_t { }; | |
46 | struct root_vertex_t { }; | |
47 | struct polling_t { }; | |
48 | struct lookahead_t { }; | |
49 | struct in_parallel_t { }; | |
50 | struct attractive_force_t { }; | |
51 | struct repulsive_force_t { }; | |
52 | struct force_pairs_t { }; | |
53 | struct cooling_t { }; | |
54 | struct vertex_displacement_t { }; | |
55 | struct iterations_t { }; | |
56 | struct diameter_range_t { }; | |
57 | struct learning_constant_range_t { }; | |
58 | struct vertices_equivalent_t { }; | |
59 | struct edges_equivalent_t { }; | |
60 | struct index_in_heap_map_t { }; | |
61 | struct max_priority_queue_t { }; | |
62 | ||
63 | #define BOOST_BGL_DECLARE_NAMED_PARAMS \ | |
64 | BOOST_BGL_ONE_PARAM_CREF(weight_map, edge_weight) \ | |
65 | BOOST_BGL_ONE_PARAM_CREF(weight_map2, edge_weight2) \ | |
66 | BOOST_BGL_ONE_PARAM_CREF(distance_map, vertex_distance) \ | |
67 | BOOST_BGL_ONE_PARAM_CREF(distance_map2, vertex_distance2) \ | |
68 | BOOST_BGL_ONE_PARAM_CREF(predecessor_map, vertex_predecessor) \ | |
69 | BOOST_BGL_ONE_PARAM_CREF(rank_map, vertex_rank) \ | |
70 | BOOST_BGL_ONE_PARAM_CREF(root_map, vertex_root) \ | |
71 | BOOST_BGL_ONE_PARAM_CREF(root_vertex, root_vertex) \ | |
72 | BOOST_BGL_ONE_PARAM_CREF(edge_centrality_map, edge_centrality) \ | |
73 | BOOST_BGL_ONE_PARAM_CREF(centrality_map, vertex_centrality) \ | |
74 | BOOST_BGL_ONE_PARAM_CREF(parity_map, parity_map) \ | |
75 | BOOST_BGL_ONE_PARAM_CREF(color_map, vertex_color) \ | |
76 | BOOST_BGL_ONE_PARAM_CREF(edge_color_map, edge_color) \ | |
77 | BOOST_BGL_ONE_PARAM_CREF(capacity_map, edge_capacity) \ | |
78 | BOOST_BGL_ONE_PARAM_CREF(residual_capacity_map, edge_residual_capacity) \ | |
79 | BOOST_BGL_ONE_PARAM_CREF(reverse_edge_map, edge_reverse) \ | |
80 | BOOST_BGL_ONE_PARAM_CREF(discover_time_map, vertex_discover_time) \ | |
81 | BOOST_BGL_ONE_PARAM_CREF(lowpoint_map, vertex_lowpoint) \ | |
82 | BOOST_BGL_ONE_PARAM_CREF(vertex_index_map, vertex_index) \ | |
83 | BOOST_BGL_ONE_PARAM_CREF(vertex_index1_map, vertex_index1) \ | |
84 | BOOST_BGL_ONE_PARAM_CREF(vertex_index2_map, vertex_index2) \ | |
85 | BOOST_BGL_ONE_PARAM_CREF(vertex_assignment_map, vertex_assignment_map) \ | |
86 | BOOST_BGL_ONE_PARAM_CREF(visitor, graph_visitor) \ | |
87 | BOOST_BGL_ONE_PARAM_CREF(distance_compare, distance_compare) \ | |
88 | BOOST_BGL_ONE_PARAM_CREF(distance_combine, distance_combine) \ | |
89 | BOOST_BGL_ONE_PARAM_CREF(distance_inf, distance_inf) \ | |
90 | BOOST_BGL_ONE_PARAM_CREF(distance_zero, distance_zero) \ | |
91 | BOOST_BGL_ONE_PARAM_CREF(edge_copy, edge_copy) \ | |
92 | BOOST_BGL_ONE_PARAM_CREF(vertex_copy, vertex_copy) \ | |
93 | BOOST_BGL_ONE_PARAM_REF(buffer, buffer_param) \ | |
94 | BOOST_BGL_ONE_PARAM_CREF(orig_to_copy, orig_to_copy) \ | |
95 | BOOST_BGL_ONE_PARAM_CREF(isomorphism_map, vertex_isomorphism) \ | |
96 | BOOST_BGL_ONE_PARAM_CREF(vertex_invariant, vertex_invariant) \ | |
97 | BOOST_BGL_ONE_PARAM_CREF(vertex_invariant1, vertex_invariant1) \ | |
98 | BOOST_BGL_ONE_PARAM_CREF(vertex_invariant2, vertex_invariant2) \ | |
99 | BOOST_BGL_ONE_PARAM_CREF(vertex_max_invariant, vertex_max_invariant) \ | |
100 | BOOST_BGL_ONE_PARAM_CREF(polling, polling) \ | |
101 | BOOST_BGL_ONE_PARAM_CREF(lookahead, lookahead) \ | |
102 | BOOST_BGL_ONE_PARAM_CREF(in_parallel, in_parallel) \ | |
103 | BOOST_BGL_ONE_PARAM_CREF(displacement_map, vertex_displacement) \ | |
104 | BOOST_BGL_ONE_PARAM_CREF(attractive_force, attractive_force) \ | |
105 | BOOST_BGL_ONE_PARAM_CREF(repulsive_force, repulsive_force) \ | |
106 | BOOST_BGL_ONE_PARAM_CREF(force_pairs, force_pairs) \ | |
107 | BOOST_BGL_ONE_PARAM_CREF(cooling, cooling) \ | |
108 | BOOST_BGL_ONE_PARAM_CREF(iterations, iterations) \ | |
109 | BOOST_BGL_ONE_PARAM_CREF(diameter_range, diameter_range) \ | |
110 | BOOST_BGL_ONE_PARAM_CREF(learning_constant_range, learning_constant_range) \ | |
111 | BOOST_BGL_ONE_PARAM_CREF(vertices_equivalent, vertices_equivalent) \ | |
112 | BOOST_BGL_ONE_PARAM_CREF(edges_equivalent, edges_equivalent) \ | |
113 | BOOST_BGL_ONE_PARAM_CREF(index_in_heap_map, index_in_heap_map) \ | |
114 | BOOST_BGL_ONE_PARAM_REF(max_priority_queue, max_priority_queue) | |
115 | ||
116 | template <typename T, typename Tag, typename Base = no_property> | |
117 | struct bgl_named_params | |
118 | { | |
119 | typedef bgl_named_params self; | |
120 | typedef Base next_type; | |
121 | typedef Tag tag_type; | |
122 | typedef T value_type; | |
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<edge_capacity_t, Params>::type, edge_capacity_t>::type CapacityEdgeMap; | |
327 | typedef typename property_traits<CapacityEdgeMap>::value_type type; | |
328 | }; | |
329 | // used in the max-flow algorithms | |
330 | template <class Graph, class P, class T, class R> | |
331 | struct edge_weight_value | |
332 | { | |
333 | typedef bgl_named_params<P, T, R> Params; | |
334 | typedef typename detail::choose_impl_result<boost::mpl::true_, Graph, typename get_param_type<edge_weight_t, Params>::type, edge_weight_t>::type WeightMap; | |
335 | typedef typename property_traits<WeightMap>::value_type type; | |
336 | }; | |
337 | ||
338 | } | |
339 | ||
340 | // Declare all new tags | |
341 | namespace graph { | |
342 | namespace keywords { | |
343 | #define BOOST_BGL_ONE_PARAM_REF(name, key) BOOST_PARAMETER_NAME(name) | |
344 | #define BOOST_BGL_ONE_PARAM_CREF(name, key) BOOST_PARAMETER_NAME(name) | |
345 | BOOST_BGL_DECLARE_NAMED_PARAMS | |
346 | #undef BOOST_BGL_ONE_PARAM_REF | |
347 | #undef BOOST_BGL_ONE_PARAM_CREF | |
348 | } | |
349 | } | |
350 | ||
351 | namespace detail { | |
352 | template <typename Tag> struct convert_one_keyword {}; | |
353 | #define BOOST_BGL_ONE_PARAM_REF(name, key) \ | |
354 | template <> \ | |
355 | struct convert_one_keyword<BOOST_PP_CAT(key, _t)> { \ | |
356 | typedef boost::graph::keywords::tag::name type; \ | |
357 | }; | |
358 | #define BOOST_BGL_ONE_PARAM_CREF(name, key) BOOST_BGL_ONE_PARAM_REF(name, key) | |
359 | BOOST_BGL_DECLARE_NAMED_PARAMS | |
360 | #undef BOOST_BGL_ONE_PARAM_REF | |
361 | #undef BOOST_BGL_ONE_PARAM_CREF | |
362 | ||
363 | template <typename T> | |
364 | struct convert_bgl_params_to_boost_parameter { | |
365 | typedef typename convert_one_keyword<typename T::tag_type>::type new_kw; | |
366 | typedef boost::parameter::aux::tagged_argument<new_kw, const typename T::value_type> tagged_arg_type; | |
367 | typedef convert_bgl_params_to_boost_parameter<typename T::next_type> rest_conv; | |
368 | typedef boost::parameter::aux::arg_list<tagged_arg_type, typename rest_conv::type> type; | |
369 | static type conv(const T& x) { | |
370 | return type(tagged_arg_type(x.m_value), rest_conv::conv(x.m_base)); | |
371 | } | |
372 | }; | |
373 | ||
374 | template <typename P, typename R> | |
375 | struct convert_bgl_params_to_boost_parameter<bgl_named_params<P, int, R> > { | |
376 | typedef convert_bgl_params_to_boost_parameter<R> rest_conv; | |
377 | typedef typename rest_conv::type type; | |
378 | static type conv(const bgl_named_params<P, int, R>& x) { | |
379 | return rest_conv::conv(x.m_base); | |
380 | } | |
381 | }; | |
382 | ||
383 | template <> | |
384 | struct convert_bgl_params_to_boost_parameter<boost::no_property> { | |
385 | typedef boost::parameter::aux::empty_arg_list type; | |
386 | static type conv(const boost::no_property&) {return type();} | |
387 | }; | |
388 | ||
389 | template <> | |
390 | struct convert_bgl_params_to_boost_parameter<boost::no_named_parameters> { | |
391 | typedef boost::parameter::aux::empty_arg_list type; | |
392 | static type conv(const boost::no_named_parameters&) {return type();} | |
393 | }; | |
394 | ||
395 | struct bgl_parameter_not_found_type {}; | |
396 | ||
397 | template <typename ArgPack, typename KeywordType> | |
398 | 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> > {}; | |
399 | } | |
400 | ||
401 | #define BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(old_type, old_var) \ | |
402 | typedef typename boost::detail::convert_bgl_params_to_boost_parameter<old_type>::type arg_pack_type; \ | |
403 | arg_pack_type arg_pack = boost::detail::convert_bgl_params_to_boost_parameter<old_type>::conv(old_var); | |
404 | ||
405 | namespace detail { | |
406 | ||
407 | template <typename ArgType, typename Prop, typename Graph, bool Exists> | |
408 | struct override_const_property_t { | |
409 | typedef typename boost::remove_const<ArgType>::type result_type; | |
410 | result_type operator()(const Graph&, const ArgType& a) const {return a;} | |
411 | }; | |
412 | ||
413 | template <typename ArgType, typename Prop, typename Graph> | |
414 | struct override_const_property_t<ArgType, Prop, Graph, false> { | |
415 | typedef typename boost::property_map<Graph, Prop>::const_type result_type; | |
416 | result_type operator()(const Graph& g, const ArgType&) const {return get(Prop(), g);} | |
417 | }; | |
418 | ||
419 | template <typename ArgPack, typename Tag, typename Prop, typename Graph> | |
420 | struct override_const_property_result { | |
421 | typedef | |
422 | typename override_const_property_t< | |
423 | typename boost::parameter::value_type<ArgPack, Tag, int>::type, | |
424 | Prop, | |
425 | Graph, | |
426 | boost::detail::parameter_exists<ArgPack, Tag>::value | |
427 | >::result_type | |
428 | type; | |
429 | }; | |
430 | ||
431 | template <typename ArgPack, typename Tag, typename Prop, typename Graph> | |
432 | typename override_const_property_result<ArgPack, Tag, Prop, Graph>::type | |
433 | override_const_property(const ArgPack& ap, const boost::parameter::keyword<Tag>& t, const Graph& g, Prop) { | |
434 | return override_const_property_t< | |
435 | typename boost::parameter::value_type<ArgPack, Tag, int>::type, | |
436 | Prop, | |
437 | Graph, | |
438 | boost::detail::parameter_exists<ArgPack, Tag>::value | |
439 | >()(g, ap[t | 0]); | |
440 | } | |
441 | ||
442 | template <typename ArgType, typename Prop, typename Graph, bool Exists> | |
443 | struct override_property_t { | |
444 | typedef ArgType result_type; | |
445 | result_type operator()(const Graph&, const typename boost::add_reference<ArgType>::type a) const {return a;} | |
446 | }; | |
447 | ||
448 | template <typename ArgType, typename Prop, typename Graph> | |
449 | struct override_property_t<ArgType, Prop, Graph, false> { | |
450 | typedef typename boost::property_map<Graph, Prop>::type result_type; | |
451 | result_type operator()(const Graph& g, const ArgType&) const {return get(Prop(), g);} | |
452 | }; | |
453 | ||
454 | template <typename ArgPack, typename Tag, typename Prop, typename Graph> | |
455 | struct override_property_result { | |
456 | typedef | |
457 | typename override_property_t< | |
458 | typename boost::parameter::value_type<ArgPack, Tag, int>::type, | |
459 | Prop, | |
460 | Graph, | |
461 | boost::detail::parameter_exists<ArgPack, Tag>::value | |
462 | >::result_type | |
463 | type; | |
464 | }; | |
465 | ||
466 | template <typename ArgPack, typename Tag, typename Prop, typename Graph> | |
467 | typename override_property_result<ArgPack, Tag, Prop, Graph>::type | |
468 | override_property(const ArgPack& ap, const boost::parameter::keyword<Tag>& t, const Graph& g, Prop) { | |
469 | return override_property_t< | |
470 | typename boost::parameter::value_type<ArgPack, Tag, int>::type, | |
471 | Prop, | |
472 | Graph, | |
473 | boost::detail::parameter_exists<ArgPack, Tag>::value | |
474 | >()(g, ap[t | 0]); | |
475 | } | |
476 | ||
477 | template <typename F> struct make_arg_pack_type; | |
478 | template <> struct make_arg_pack_type<void()> {typedef boost::parameter::aux::empty_arg_list type;}; | |
479 | template <typename K, typename A> | |
480 | struct make_arg_pack_type<void(K, A)> { | |
481 | typedef boost::parameter::aux::tagged_argument<K, A> type; | |
482 | }; | |
483 | ||
484 | #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))>, | |
485 | #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) | |
486 | ||
487 | #define BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION(z, i, _) \ | |
488 | template <BOOST_PP_ENUM_PARAMS(i, typename Keyword), BOOST_PP_ENUM_PARAMS(i, typename Arg)> \ | |
489 | struct make_arg_pack_type<void(BOOST_PP_ENUM_PARAMS(i, Keyword), BOOST_PP_ENUM_PARAMS(i, Arg))> { \ | |
490 | typedef \ | |
491 | 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), ~) \ | |
492 | type; \ | |
493 | }; | |
494 | BOOST_PP_REPEAT_FROM_TO(2, 11, BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION, ~) | |
495 | #undef BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION | |
496 | ||
497 | #define BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(name, nfixed, nnamed_max) \ | |
498 | /* Entry point for conversion from BGL-style named parameters */ \ | |
499 | template <BOOST_PP_ENUM_PARAMS(nfixed, typename Param) BOOST_PP_COMMA_IF(nfixed) typename ArgPack> \ | |
500 | typename boost::result_of< \ | |
501 | 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&) \ | |
502 | >::type \ | |
503 | 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) { \ | |
504 | 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); \ | |
505 | } \ | |
506 | /* Individual functions taking Boost.Parameter-style keyword arguments */ \ | |
507 | BOOST_PP_REPEAT(BOOST_PP_INC(nnamed_max), BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONE, (name)(nfixed)) | |
508 | ||
509 | #define BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONE(z, nnamed, seq) \ | |
510 | BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONEX(z, nnamed, BOOST_PP_SEQ_ELEM(0, seq), BOOST_PP_SEQ_ELEM(1, seq)) | |
511 | ||
512 | #define BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONEX(z, nnamed, name, nfixed) \ | |
513 | template <BOOST_PP_ENUM_PARAMS(nfixed, typename Param) BOOST_PP_ENUM_TRAILING_PARAMS(nnamed, typename Keyword) BOOST_PP_ENUM_TRAILING_PARAMS(nnamed, typename Arg)> \ | |
514 | typename boost::result_of< \ | |
515 | detail::BOOST_PP_CAT(name, _impl)<BOOST_PP_ENUM_PARAMS(nfixed, Param)> \ | |
516 | (BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_COMMA_IF(nfixed) \ | |
517 | 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&) \ | |
518 | >::type \ | |
519 | name(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, & param) \ | |
520 | BOOST_PP_ENUM_TRAILING(nnamed, BOOST_GRAPH_MAKE_PAIR_PARAM, ~)) { \ | |
521 | return detail::BOOST_PP_CAT(name, _impl)<BOOST_PP_ENUM_PARAMS(nfixed, Param)>() \ | |
522 | (BOOST_PP_ENUM_PARAMS(nfixed, param), \ | |
523 | (boost::parameter::aux::empty_arg_list() BOOST_PP_ENUM_TRAILING_PARAMS(nnamed, kw))); \ | |
524 | } | |
525 | ||
526 | #define BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(name, nfixed) \ | |
527 | template <BOOST_PP_ENUM_PARAMS(nfixed, typename Param) BOOST_PP_COMMA_IF(nfixed) class P, class T, class R> \ | |
528 | typename boost::result_of< \ | |
529 | ::boost::graph::detail::BOOST_PP_CAT(name, _impl) BOOST_PP_EXPR_IF(nfixed, <) BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_EXPR_IF(nfixed, >) \ | |
530 | (BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_COMMA_IF(nfixed) \ | |
531 | const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<P, T, R> >::type &) \ | |
532 | >::type \ | |
533 | 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) { \ | |
534 | typedef boost::bgl_named_params<P, T, R> old_style_params_type; \ | |
535 | BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(old_style_params_type, old_style_params) \ | |
536 | return ::boost::graph::BOOST_PP_CAT(name, _with_named_params)(BOOST_PP_ENUM_PARAMS(nfixed, param) BOOST_PP_COMMA_IF(nfixed) arg_pack); \ | |
537 | } \ | |
538 | \ | |
539 | BOOST_PP_EXPR_IF(nfixed, template <) BOOST_PP_ENUM_PARAMS(nfixed, typename Param) BOOST_PP_EXPR_IF(nfixed, >) \ | |
540 | BOOST_PP_EXPR_IF(nfixed, typename) boost::result_of< \ | |
541 | ::boost::graph::detail::BOOST_PP_CAT(name, _impl) BOOST_PP_EXPR_IF(nfixed, <) BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_EXPR_IF(nfixed, >) \ | |
542 | (BOOST_PP_ENUM_PARAMS(nfixed, Param) BOOST_PP_COMMA_IF(nfixed) const boost::parameter::aux::empty_arg_list &) \ | |
543 | >::type \ | |
544 | name(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, & param)) { \ | |
545 | BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(boost::no_named_parameters, boost::no_named_parameters()) \ | |
546 | return ::boost::graph::BOOST_PP_CAT(name, _with_named_params)(BOOST_PP_ENUM_PARAMS(nfixed, param) BOOST_PP_COMMA_IF(nfixed) arg_pack); \ | |
547 | } | |
548 | ||
549 | } | |
550 | ||
551 | namespace detail { | |
552 | ||
553 | template <bool Exists, typename Graph, typename ArgPack, typename Value, typename PM> | |
554 | struct map_maker_helper { | |
555 | typedef PM map_type; | |
556 | static PM make_map(const Graph&, Value, const PM& pm, const ArgPack&) { | |
557 | return pm; | |
558 | } | |
559 | }; | |
560 | ||
561 | template <typename Graph, typename ArgPack, typename Value, typename PM> | |
562 | struct map_maker_helper<false, Graph, ArgPack, Value, PM> { | |
563 | typedef typename boost::remove_const< | |
564 | typename override_const_property_t< | |
565 | typename boost::parameter::value_type< | |
566 | ArgPack, boost::graph::keywords::tag::vertex_index_map, int>::type, | |
567 | boost::vertex_index_t, | |
568 | Graph, | |
569 | boost::detail::parameter_exists< | |
570 | ArgPack, boost::graph::keywords::tag::vertex_index_map>::value | |
571 | >::result_type>::type vi_map_type; | |
572 | typedef | |
573 | boost::shared_array_property_map<Value, vi_map_type> | |
574 | map_type; | |
575 | static map_type make_map(const Graph& g, | |
576 | Value v, | |
577 | const PM&, | |
578 | const ArgPack& ap) { | |
579 | return make_shared_array_property_map( | |
580 | num_vertices(g), | |
581 | v, | |
582 | override_const_property( | |
583 | ap, | |
584 | boost::graph::keywords::_vertex_index_map, | |
585 | g, vertex_index)); | |
586 | } | |
587 | }; | |
588 | ||
589 | template <typename Graph, typename ArgPack, typename MapTag, typename ValueType> | |
590 | struct map_maker { | |
591 | BOOST_STATIC_CONSTANT( | |
592 | bool, | |
593 | has_map = | |
594 | (parameter_exists<ArgPack, MapTag> | |
595 | ::value)); | |
596 | typedef map_maker_helper<has_map, Graph, ArgPack, ValueType, | |
597 | typename boost::remove_const< | |
598 | typename boost::parameter::value_type< | |
599 | ArgPack, | |
600 | MapTag, | |
601 | int | |
602 | >::type | |
603 | >::type> helper; | |
604 | typedef typename helper::map_type map_type; | |
605 | static map_type make_map(const Graph& g, const ArgPack& ap, ValueType default_value) { | |
606 | return helper::make_map(g, default_value, ap[::boost::parameter::keyword<MapTag>::instance | 0], ap); | |
607 | } | |
608 | }; | |
609 | ||
610 | template <typename MapTag, typename ValueType = void> | |
611 | class make_property_map_from_arg_pack_gen { | |
612 | ValueType default_value; | |
613 | ||
614 | public: | |
615 | make_property_map_from_arg_pack_gen(ValueType default_value) | |
616 | : default_value(default_value) {} | |
617 | ||
618 | template <typename Graph, typename ArgPack> | |
619 | typename map_maker<Graph, ArgPack, MapTag, ValueType>::map_type | |
620 | operator()(const Graph& g, const ArgPack& ap) const { | |
621 | return map_maker<Graph, ArgPack, MapTag, ValueType>::make_map(g, ap, default_value); | |
622 | } | |
623 | }; | |
624 | ||
625 | template <typename MapTag> | |
626 | class make_property_map_from_arg_pack_gen<MapTag, void> { | |
627 | public: | |
628 | template <typename ValueType, typename Graph, typename ArgPack> | |
629 | typename map_maker<Graph, ArgPack, MapTag, ValueType>::map_type | |
630 | operator()(const Graph& g, const ArgPack& ap, ValueType default_value) const { | |
631 | return map_maker<Graph, ArgPack, MapTag, ValueType>::make_map(g, ap, default_value); | |
632 | } | |
633 | }; | |
634 | ||
635 | static const | |
636 | make_property_map_from_arg_pack_gen< | |
637 | boost::graph::keywords::tag::color_map, | |
638 | default_color_type> | |
639 | make_color_map_from_arg_pack(white_color); | |
640 | ||
641 | template <bool Exists, class Graph, class ArgPack, class KeyT, class ValueT, class KeyMapTag, class IndexInHeapMapTag, class Compare, class Q> | |
642 | struct priority_queue_maker_helper { | |
643 | typedef Q priority_queue_type; | |
644 | ||
645 | static priority_queue_type | |
646 | make_queue(const Graph&, const ArgPack&, KeyT, const Q& q) { | |
647 | return q; | |
648 | } | |
649 | }; | |
650 | ||
651 | template <class Graph, class ArgPack, class KeyT, class ValueT, class KeyMapTag, class IndexInHeapMapTag, class Compare, class Q> | |
652 | struct priority_queue_maker_helper<false, Graph, ArgPack, KeyT, ValueT, KeyMapTag, IndexInHeapMapTag, Compare, Q> { | |
653 | typedef typename std::vector<ValueT>::size_type default_index_in_heap_type; | |
654 | typedef typename map_maker<Graph, ArgPack, IndexInHeapMapTag, default_index_in_heap_type>::helper::map_type index_in_heap_map; | |
655 | 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; | |
656 | ||
657 | static priority_queue_type | |
658 | make_queue(const Graph& g, const ArgPack& ap, KeyT defaultKey, const Q&) { | |
659 | return priority_queue_type( | |
660 | map_maker<Graph, ArgPack, KeyMapTag, KeyT>::make_map(g, ap, defaultKey), | |
661 | 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)) | |
662 | ); | |
663 | } | |
664 | }; | |
665 | ||
666 | template <class Graph, class ArgPack, class KeyT, class ValueT, class PriorityQueueTag, class KeyMapTag, class IndexInHeapMapTag, class Compare> | |
667 | struct priority_queue_maker { | |
668 | BOOST_STATIC_CONSTANT( | |
669 | bool, | |
670 | g_hasQ = | |
671 | (parameter_exists<ArgPack, PriorityQueueTag> | |
672 | ::value)); | |
673 | typedef boost::reference_wrapper<int> int_refw; | |
674 | typedef typename boost::parameter::value_type< | |
675 | ArgPack, | |
676 | PriorityQueueTag, | |
677 | int_refw | |
678 | >::type | |
679 | param_value_type_wrapper; | |
680 | typedef typename param_value_type_wrapper::type | |
681 | param_value_type; | |
682 | typedef typename boost::remove_const<param_value_type>::type param_value_type_no_const; | |
683 | typedef priority_queue_maker_helper<g_hasQ, Graph, ArgPack, KeyT, ValueT, KeyMapTag, IndexInHeapMapTag, Compare, | |
684 | param_value_type_no_const> helper; | |
685 | typedef typename helper::priority_queue_type priority_queue_type; | |
686 | ||
687 | static priority_queue_type make_queue(const Graph& g, const ArgPack& ap, KeyT defaultKey) { | |
688 | return helper::make_queue(g, ap, defaultKey, ap[::boost::parameter::keyword<PriorityQueueTag>::instance | 0]); | |
689 | } | |
690 | }; | |
691 | ||
692 | 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> | |
693 | struct make_priority_queue_from_arg_pack_gen { | |
694 | KeyT defaultKey; | |
695 | ||
696 | make_priority_queue_from_arg_pack_gen(KeyT defaultKey_) : defaultKey(defaultKey_) { } | |
697 | ||
698 | template <class F> | |
699 | struct result { | |
700 | typedef typename remove_const<typename remove_reference<typename function_traits<F>::arg1_type>::type>::type graph_type; | |
701 | typedef typename remove_const<typename remove_reference<typename function_traits<F>::arg2_type>::type>::type arg_pack_type; | |
702 | typedef typename priority_queue_maker<graph_type, arg_pack_type, KeyT, ValueT, PriorityQueueTag, KeyMapTag, IndexInHeapMapTag, Compare>::priority_queue_type type; | |
703 | }; | |
704 | ||
705 | template <class Graph, class ArgPack> | |
706 | typename priority_queue_maker<Graph, ArgPack, KeyT, ValueT, PriorityQueueTag, KeyMapTag, IndexInHeapMapTag, Compare>::priority_queue_type | |
707 | operator()(const Graph& g, const ArgPack& ap) const { | |
708 | return priority_queue_maker<Graph, ArgPack, KeyT, ValueT, PriorityQueueTag, KeyMapTag, IndexInHeapMapTag, Compare>::make_queue(g, ap, defaultKey); | |
709 | } | |
710 | }; | |
711 | ||
712 | template <typename G> | |
713 | typename boost::graph_traits<G>::vertex_descriptor | |
714 | get_null_vertex(const G&) {return boost::graph_traits<G>::null_vertex();} | |
715 | ||
716 | template <typename G> | |
717 | typename boost::graph_traits<G>::vertex_descriptor | |
718 | get_default_starting_vertex(const G& g) { | |
719 | std::pair<typename boost::graph_traits<G>::vertex_iterator, typename boost::graph_traits<G>::vertex_iterator> iters = vertices(g); | |
720 | return (iters.first == iters.second) ? boost::graph_traits<G>::null_vertex() : *iters.first; | |
721 | } | |
722 | ||
723 | template <typename G> | |
724 | struct get_default_starting_vertex_t { | |
725 | typedef typename boost::graph_traits<G>::vertex_descriptor result_type; | |
726 | const G& g; | |
727 | get_default_starting_vertex_t(const G& g): g(g) {} | |
728 | result_type operator()() const {return get_default_starting_vertex(g);} | |
729 | }; | |
730 | ||
731 | // Wrapper to avoid instantiating numeric_limits when users provide distance_inf value manually | |
732 | template <typename T> | |
733 | struct get_max { | |
734 | T operator()() const { | |
735 | return (std::numeric_limits<T>::max)(); | |
736 | } | |
737 | typedef T result_type; | |
738 | }; | |
739 | ||
740 | } // namespace detail | |
741 | ||
742 | } // namespace boost | |
743 | ||
744 | #undef BOOST_BGL_DECLARE_NAMED_PARAMS | |
745 | ||
746 | #endif // BOOST_GRAPH_NAMED_FUNCTION_PARAMS_HPP |