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 // Revision History:
11 // 01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
12 //
13 #ifndef BOOST_GRAPH_GRAPH_SEARCH_VISITORS_HPP
14 #define BOOST_GRAPH_GRAPH_SEARCH_VISITORS_HPP
15
16 #include <iosfwd>
17 #include <boost/config.hpp>
18 #include <boost/type_traits/is_same.hpp>
19 #include <boost/mpl/bool.hpp>
20 #include <boost/property_map/property_map.hpp>
21 #include <boost/graph/graph_traits.hpp>
22 #include <boost/limits.hpp>
23
24 namespace boost
25 {
26
27 // This is a bit more convenient than std::numeric_limits because
28 // you don't have to explicitly provide type T.
numeric_limits_max(T)29 template < class T > inline T numeric_limits_max(T)
30 {
31 return (std::numeric_limits< T >::max)();
32 }
33
34 //========================================================================
35 // Event Tags
36
37 namespace detail
38 {
39 // For partial specialization workaround
40 enum event_visitor_enum
41 {
42 on_no_event_num,
43 on_initialize_vertex_num,
44 on_start_vertex_num,
45 on_discover_vertex_num,
46 on_finish_vertex_num,
47 on_examine_vertex_num,
48 on_examine_edge_num,
49 on_tree_edge_num,
50 on_non_tree_edge_num,
51 on_gray_target_num,
52 on_black_target_num,
53 on_forward_or_cross_edge_num,
54 on_back_edge_num,
55 on_finish_edge_num,
56 on_edge_relaxed_num,
57 on_edge_not_relaxed_num,
58 on_edge_minimized_num,
59 on_edge_not_minimized_num
60 };
61
62 template < typename Event, typename Visitor >
63 struct functor_to_visitor : Visitor
64 {
65 typedef Event event_filter;
functor_to_visitorboost::detail::functor_to_visitor66 functor_to_visitor(const Visitor& visitor) : Visitor(visitor) {}
67 };
68
69 } // namespace detail
70
71 struct on_no_event
72 {
73 enum
74 {
75 num = detail::on_no_event_num
76 };
77 };
78
79 struct on_initialize_vertex
80 {
81 enum
82 {
83 num = detail::on_initialize_vertex_num
84 };
85 };
86 struct on_start_vertex
87 {
88 enum
89 {
90 num = detail::on_start_vertex_num
91 };
92 };
93 struct on_discover_vertex
94 {
95 enum
96 {
97 num = detail::on_discover_vertex_num
98 };
99 };
100 struct on_examine_vertex
101 {
102 enum
103 {
104 num = detail::on_examine_vertex_num
105 };
106 };
107 struct on_finish_vertex
108 {
109 enum
110 {
111 num = detail::on_finish_vertex_num
112 };
113 };
114
115 struct on_examine_edge
116 {
117 enum
118 {
119 num = detail::on_examine_edge_num
120 };
121 };
122 struct on_tree_edge
123 {
124 enum
125 {
126 num = detail::on_tree_edge_num
127 };
128 };
129 struct on_non_tree_edge
130 {
131 enum
132 {
133 num = detail::on_non_tree_edge_num
134 };
135 };
136 struct on_gray_target
137 {
138 enum
139 {
140 num = detail::on_gray_target_num
141 };
142 };
143 struct on_black_target
144 {
145 enum
146 {
147 num = detail::on_black_target_num
148 };
149 };
150 struct on_forward_or_cross_edge
151 {
152 enum
153 {
154 num = detail::on_forward_or_cross_edge_num
155 };
156 };
157 struct on_back_edge
158 {
159 enum
160 {
161 num = detail::on_back_edge_num
162 };
163 };
164 struct on_finish_edge
165 {
166 enum
167 {
168 num = detail::on_finish_edge_num
169 };
170 };
171
172 struct on_edge_relaxed
173 {
174 enum
175 {
176 num = detail::on_edge_relaxed_num
177 };
178 };
179 struct on_edge_not_relaxed
180 {
181 enum
182 {
183 num = detail::on_edge_not_relaxed_num
184 };
185 };
186 struct on_edge_minimized
187 {
188 enum
189 {
190 num = detail::on_edge_minimized_num
191 };
192 };
193 struct on_edge_not_minimized
194 {
195 enum
196 {
197 num = detail::on_edge_not_minimized_num
198 };
199 };
200
201 //========================================================================
202 // base_visitor and null_visitor
203
204 // needed for MSVC workaround
205 template < class Visitor > struct base_visitor
206 {
207 typedef on_no_event event_filter;
operator ()boost::base_visitor208 template < class T, class Graph > void operator()(T, Graph&) {}
209 };
210
211 struct null_visitor : public base_visitor< null_visitor >
212 {
213 typedef on_no_event event_filter;
operator ()boost::null_visitor214 template < class T, class Graph > void operator()(T, Graph&) {}
215 };
216
217 //========================================================================
218 // The invoke_visitors() function
219
220 namespace detail
221 {
222 template < class Visitor, class T, class Graph >
invoke_dispatch(Visitor & v,T x,Graph & g,mpl::true_)223 inline void invoke_dispatch(Visitor& v, T x, Graph& g, mpl::true_)
224 {
225 v(x, g);
226 }
227
228 template < class Visitor, class T, class Graph >
invoke_dispatch(Visitor &,T,Graph &,mpl::false_)229 inline void invoke_dispatch(Visitor&, T, Graph&, mpl::false_)
230 {
231 }
232 } // namespace detail
233
234 template < class Visitor, class Rest, class T, class Graph, class Tag >
invoke_visitors(std::pair<Visitor,Rest> & vlist,T x,Graph & g,Tag tag)235 inline void invoke_visitors(
236 std::pair< Visitor, Rest >& vlist, T x, Graph& g, Tag tag)
237 {
238 typedef typename Visitor::event_filter Category;
239 typedef typename is_same< Category, Tag >::type IsSameTag;
240 detail::invoke_dispatch(vlist.first, x, g, IsSameTag());
241 invoke_visitors(vlist.second, x, g, tag);
242 }
243 template < class Visitor, class T, class Graph, class Tag >
invoke_visitors(Visitor & v,T x,Graph & g,Tag)244 inline void invoke_visitors(Visitor& v, T x, Graph& g, Tag)
245 {
246 typedef typename Visitor::event_filter Category;
247 typedef typename is_same< Category, Tag >::type IsSameTag;
248 detail::invoke_dispatch(v, x, g, IsSameTag());
249 }
250
251 //========================================================================
252 // predecessor_recorder
253
254 template < class PredecessorMap, class Tag >
255 struct predecessor_recorder
256 : public base_visitor< predecessor_recorder< PredecessorMap, Tag > >
257 {
258 typedef Tag event_filter;
predecessor_recorderboost::predecessor_recorder259 predecessor_recorder(PredecessorMap pa) : m_predecessor(pa) {}
operator ()boost::predecessor_recorder260 template < class Edge, class Graph > void operator()(Edge e, const Graph& g)
261 {
262 put(m_predecessor, target(e, g), source(e, g));
263 }
264 PredecessorMap m_predecessor;
265 };
266 template < class PredecessorMap, class Tag >
record_predecessors(PredecessorMap pa,Tag)267 predecessor_recorder< PredecessorMap, Tag > record_predecessors(
268 PredecessorMap pa, Tag)
269 {
270 return predecessor_recorder< PredecessorMap, Tag >(pa);
271 }
272
273 //========================================================================
274 // edge_predecessor_recorder
275
276 template < class PredEdgeMap, class Tag >
277 struct edge_predecessor_recorder
278 : public base_visitor< edge_predecessor_recorder< PredEdgeMap, Tag > >
279 {
280 typedef Tag event_filter;
edge_predecessor_recorderboost::edge_predecessor_recorder281 edge_predecessor_recorder(PredEdgeMap pa) : m_predecessor(pa) {}
operator ()boost::edge_predecessor_recorder282 template < class Edge, class Graph > void operator()(Edge e, const Graph& g)
283 {
284 put(m_predecessor, target(e, g), e);
285 }
286 PredEdgeMap m_predecessor;
287 };
288 template < class PredEdgeMap, class Tag >
record_edge_predecessors(PredEdgeMap pa,Tag)289 edge_predecessor_recorder< PredEdgeMap, Tag > record_edge_predecessors(
290 PredEdgeMap pa, Tag)
291 {
292 return edge_predecessor_recorder< PredEdgeMap, Tag >(pa);
293 }
294
295 //========================================================================
296 // distance_recorder
297
298 template < class DistanceMap, class Tag >
299 struct distance_recorder
300 : public base_visitor< distance_recorder< DistanceMap, Tag > >
301 {
302 typedef Tag event_filter;
distance_recorderboost::distance_recorder303 distance_recorder(DistanceMap pa) : m_distance(pa) {}
operator ()boost::distance_recorder304 template < class Edge, class Graph > void operator()(Edge e, const Graph& g)
305 {
306 typename graph_traits< Graph >::vertex_descriptor u = source(e, g),
307 v = target(e, g);
308 put(m_distance, v, get(m_distance, u) + 1);
309 }
310 DistanceMap m_distance;
311 };
312 template < class DistanceMap, class Tag >
record_distances(DistanceMap pa,Tag)313 distance_recorder< DistanceMap, Tag > record_distances(DistanceMap pa, Tag)
314 {
315 return distance_recorder< DistanceMap, Tag >(pa);
316 }
317
318 //========================================================================
319 // time_stamper
320
321 template < class TimeMap, class TimeT, class Tag >
322 struct time_stamper : public base_visitor< time_stamper< TimeMap, TimeT, Tag > >
323 {
324 typedef Tag event_filter;
time_stamperboost::time_stamper325 time_stamper(TimeMap pa, TimeT& t) : m_time_pa(pa), m_time(t) {}
326 template < class Vertex, class Graph >
operator ()boost::time_stamper327 void operator()(Vertex u, const Graph&)
328 {
329 put(m_time_pa, u, ++m_time);
330 }
331 TimeMap m_time_pa;
332 TimeT& m_time;
333 };
334 template < class TimeMap, class TimeT, class Tag >
stamp_times(TimeMap pa,TimeT & time_counter,Tag)335 time_stamper< TimeMap, TimeT, Tag > stamp_times(
336 TimeMap pa, TimeT& time_counter, Tag)
337 {
338 return time_stamper< TimeMap, TimeT, Tag >(pa, time_counter);
339 }
340
341 //========================================================================
342 // property_writer
343
344 template < class PA, class OutputIterator, class Tag >
345 struct property_writer
346 : public base_visitor< property_writer< PA, OutputIterator, Tag > >
347 {
348 typedef Tag event_filter;
349
property_writerboost::property_writer350 property_writer(PA pa, OutputIterator out) : m_pa(pa), m_out(out) {}
351
operator ()boost::property_writer352 template < class T, class Graph > void operator()(T x, Graph&)
353 {
354 *m_out++ = get(m_pa, x);
355 }
356 PA m_pa;
357 OutputIterator m_out;
358 };
359 template < class PA, class OutputIterator, class Tag >
write_property(PA pa,OutputIterator out,Tag)360 property_writer< PA, OutputIterator, Tag > write_property(
361 PA pa, OutputIterator out, Tag)
362 {
363 return property_writer< PA, OutputIterator, Tag >(pa, out);
364 }
365
366 //========================================================================
367 // property_put
368
369 /**
370 * Functor which just sets a given value to a vertex or edge in a property map.
371 */
372
373 template < typename PropertyMap, typename EventTag > struct property_put
374 {
375 typedef EventTag event_filter;
376
property_putboost::property_put377 property_put(PropertyMap property_map,
378 typename property_traits< PropertyMap >::value_type value)
379 : property_map_(property_map), value_(value)
380 {
381 }
382
383 template < typename VertexOrEdge, typename Graph >
operator ()boost::property_put384 void operator()(VertexOrEdge v, const Graph&)
385 {
386 put(property_map_, v, value_);
387 }
388
389 private:
390 PropertyMap property_map_;
391 typename property_traits< PropertyMap >::value_type value_;
392 };
393
394 /**
395 * Creates a property_put functor which just sets a given value to a vertex or
396 * edge.
397 *
398 * @param property_map Given writeable property map
399 * @param value Fixed value of the map
400 * @param tag Event Filter
401 * @return The functor.
402 */
403
404 template < typename PropertyMap, typename EventTag >
put_property(PropertyMap property_map,typename property_traits<PropertyMap>::value_type value,EventTag)405 inline property_put< PropertyMap, EventTag > put_property(
406 PropertyMap property_map,
407 typename property_traits< PropertyMap >::value_type value, EventTag)
408 {
409 return property_put< PropertyMap, EventTag >(property_map, value);
410 }
411
412 #define BOOST_GRAPH_EVENT_STUB(Event, Kind) \
413 typedef ::boost::Event Event##_type; \
414 template < typename Visitor > \
415 Kind##_visitor< std::pair< \
416 detail::functor_to_visitor< Event##_type, Visitor >, Visitors > > \
417 do_##Event(Visitor visitor) \
418 { \
419 typedef std::pair< \
420 detail::functor_to_visitor< Event##_type, Visitor >, Visitors > \
421 visitor_list; \
422 typedef Kind##_visitor< visitor_list > result_type; \
423 return result_type(visitor_list(visitor, m_vis)); \
424 }
425
426 } /* namespace boost */
427
428 #endif
429