]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | // This is a bit more convenient than std::numeric_limits because | |
27 | // you don't have to explicitly provide type T. | |
28 | template <class T> | |
29 | inline T numeric_limits_max(T) { return (std::numeric_limits<T>::max)(); } | |
30 | ||
31 | //======================================================================== | |
32 | // Event Tags | |
33 | ||
34 | namespace detail { | |
35 | // For partial specialization workaround | |
36 | enum event_visitor_enum | |
37 | { on_no_event_num, | |
38 | on_initialize_vertex_num, on_start_vertex_num, | |
39 | on_discover_vertex_num, on_finish_vertex_num, on_examine_vertex_num, | |
40 | on_examine_edge_num, on_tree_edge_num, on_non_tree_edge_num, | |
41 | on_gray_target_num, on_black_target_num, | |
42 | on_forward_or_cross_edge_num, on_back_edge_num, on_finish_edge_num, | |
43 | on_edge_relaxed_num, on_edge_not_relaxed_num, | |
44 | on_edge_minimized_num, on_edge_not_minimized_num | |
45 | }; | |
46 | ||
47 | template<typename Event, typename Visitor> | |
48 | struct functor_to_visitor : Visitor | |
49 | { | |
50 | typedef Event event_filter; | |
51 | functor_to_visitor(const Visitor& visitor) : Visitor(visitor) {} | |
52 | }; | |
53 | ||
54 | } // namespace detail | |
55 | ||
56 | struct on_no_event { enum { num = detail::on_no_event_num }; }; | |
57 | ||
58 | struct on_initialize_vertex { | |
59 | enum { num = detail::on_initialize_vertex_num }; }; | |
60 | struct on_start_vertex { enum { num = detail::on_start_vertex_num }; }; | |
61 | struct on_discover_vertex { enum { num = detail::on_discover_vertex_num }; }; | |
62 | struct on_examine_vertex { enum { num = detail::on_examine_vertex_num }; }; | |
63 | struct on_finish_vertex { enum { num = detail::on_finish_vertex_num }; }; | |
64 | ||
65 | struct on_examine_edge { enum { num = detail::on_examine_edge_num }; }; | |
66 | struct on_tree_edge { enum { num = detail::on_tree_edge_num }; }; | |
67 | struct on_non_tree_edge { enum { num = detail::on_non_tree_edge_num }; }; | |
68 | struct on_gray_target { enum { num = detail::on_gray_target_num }; }; | |
69 | struct on_black_target { enum { num = detail::on_black_target_num }; }; | |
70 | struct on_forward_or_cross_edge { | |
71 | enum { num = detail::on_forward_or_cross_edge_num }; }; | |
72 | struct on_back_edge { enum { num = detail::on_back_edge_num }; }; | |
73 | struct on_finish_edge { enum { num = detail::on_finish_edge_num }; }; | |
74 | ||
75 | struct on_edge_relaxed { enum { num = detail::on_edge_relaxed_num }; }; | |
76 | struct on_edge_not_relaxed { | |
77 | enum { num = detail::on_edge_not_relaxed_num }; }; | |
78 | struct on_edge_minimized { enum { num = detail::on_edge_minimized_num }; }; | |
79 | struct on_edge_not_minimized { | |
80 | enum { num = detail::on_edge_not_minimized_num }; }; | |
81 | ||
82 | //======================================================================== | |
83 | // base_visitor and null_visitor | |
84 | ||
85 | // needed for MSVC workaround | |
86 | template <class Visitor> | |
87 | struct base_visitor { | |
88 | typedef on_no_event event_filter; | |
89 | template <class T, class Graph> | |
90 | void operator()(T, Graph&) { } | |
91 | }; | |
92 | ||
93 | struct null_visitor : public base_visitor<null_visitor> { | |
94 | typedef on_no_event event_filter; | |
95 | template <class T, class Graph> | |
96 | void operator()(T, Graph&) { } | |
97 | }; | |
98 | ||
99 | //======================================================================== | |
100 | // The invoke_visitors() function | |
101 | ||
102 | namespace detail { | |
103 | template <class Visitor, class T, class Graph> | |
104 | inline void invoke_dispatch(Visitor& v, T x, Graph& g, mpl::true_) { | |
105 | v(x, g); | |
106 | } | |
107 | ||
108 | template <class Visitor, class T, class Graph> | |
109 | inline void invoke_dispatch(Visitor&, T, Graph&, mpl::false_) | |
110 | { } | |
111 | } // namespace detail | |
112 | ||
113 | template <class Visitor, class Rest, class T, class Graph, class Tag> | |
114 | inline void | |
115 | invoke_visitors(std::pair<Visitor, Rest>& vlist, T x, Graph& g, Tag tag) { | |
116 | typedef typename Visitor::event_filter Category; | |
117 | typedef typename is_same<Category, Tag>::type IsSameTag; | |
118 | detail::invoke_dispatch(vlist.first, x, g, IsSameTag()); | |
119 | invoke_visitors(vlist.second, x, g, tag); | |
120 | } | |
121 | template <class Visitor, class T, class Graph, class Tag> | |
122 | inline void | |
123 | invoke_visitors(Visitor& v, T x, Graph& g, Tag) { | |
124 | typedef typename Visitor::event_filter Category; | |
125 | typedef typename is_same<Category, Tag>::type IsSameTag; | |
126 | detail::invoke_dispatch(v, x, g, IsSameTag()); | |
127 | } | |
128 | ||
129 | //======================================================================== | |
130 | // predecessor_recorder | |
131 | ||
132 | template <class PredecessorMap, class Tag> | |
133 | struct predecessor_recorder | |
134 | : public base_visitor<predecessor_recorder<PredecessorMap, Tag> > | |
135 | { | |
136 | typedef Tag event_filter; | |
137 | predecessor_recorder(PredecessorMap pa) : m_predecessor(pa) { } | |
138 | template <class Edge, class Graph> | |
139 | void operator()(Edge e, const Graph& g) { | |
140 | put(m_predecessor, target(e, g), source(e, g)); | |
141 | } | |
142 | PredecessorMap m_predecessor; | |
143 | }; | |
144 | template <class PredecessorMap, class Tag> | |
145 | predecessor_recorder<PredecessorMap, Tag> | |
146 | record_predecessors(PredecessorMap pa, Tag) { | |
147 | return predecessor_recorder<PredecessorMap, Tag> (pa); | |
148 | } | |
149 | ||
150 | //======================================================================== | |
151 | // edge_predecessor_recorder | |
152 | ||
153 | template <class PredEdgeMap, class Tag> | |
154 | struct edge_predecessor_recorder | |
155 | : public base_visitor<edge_predecessor_recorder<PredEdgeMap, Tag> > | |
156 | { | |
157 | typedef Tag event_filter; | |
158 | edge_predecessor_recorder(PredEdgeMap pa) : m_predecessor(pa) { } | |
159 | template <class Edge, class Graph> | |
160 | void operator()(Edge e, const Graph& g) { | |
161 | put(m_predecessor, target(e, g), e); | |
162 | } | |
163 | PredEdgeMap m_predecessor; | |
164 | }; | |
165 | template <class PredEdgeMap, class Tag> | |
166 | edge_predecessor_recorder<PredEdgeMap, Tag> | |
167 | record_edge_predecessors(PredEdgeMap pa, Tag) { | |
168 | return edge_predecessor_recorder<PredEdgeMap, Tag> (pa); | |
169 | } | |
170 | ||
171 | //======================================================================== | |
172 | // distance_recorder | |
173 | ||
174 | template <class DistanceMap, class Tag> | |
175 | struct distance_recorder | |
176 | : public base_visitor<distance_recorder<DistanceMap, Tag> > | |
177 | { | |
178 | typedef Tag event_filter; | |
179 | distance_recorder(DistanceMap pa) : m_distance(pa) { } | |
180 | template <class Edge, class Graph> | |
181 | void operator()(Edge e, const Graph& g) { | |
182 | typename graph_traits<Graph>::vertex_descriptor | |
183 | u = source(e, g), v = target(e, g); | |
184 | put(m_distance, v, get(m_distance, u) + 1); | |
185 | } | |
186 | DistanceMap m_distance; | |
187 | }; | |
188 | template <class DistanceMap, class Tag> | |
189 | distance_recorder<DistanceMap, Tag> | |
190 | record_distances(DistanceMap pa, Tag) { | |
191 | return distance_recorder<DistanceMap, Tag> (pa); | |
192 | } | |
193 | ||
194 | //======================================================================== | |
195 | // time_stamper | |
196 | ||
197 | ||
198 | template <class TimeMap, class TimeT, class Tag> | |
199 | struct time_stamper | |
200 | : public base_visitor<time_stamper<TimeMap, TimeT, Tag> > | |
201 | { | |
202 | typedef Tag event_filter; | |
203 | time_stamper(TimeMap pa, TimeT& t) : m_time_pa(pa), m_time(t) { } | |
204 | template <class Vertex, class Graph> | |
205 | void operator()(Vertex u, const Graph&) { | |
206 | put(m_time_pa, u, ++m_time); | |
207 | } | |
208 | TimeMap m_time_pa; | |
209 | TimeT& m_time; | |
210 | }; | |
211 | template <class TimeMap, class TimeT, class Tag> | |
212 | time_stamper<TimeMap, TimeT, Tag> | |
213 | stamp_times(TimeMap pa, TimeT& time_counter, Tag) { | |
214 | return time_stamper<TimeMap, TimeT, Tag>(pa, time_counter); | |
215 | } | |
216 | ||
217 | //======================================================================== | |
218 | // property_writer | |
219 | ||
220 | template <class PA, class OutputIterator, class Tag> | |
221 | struct property_writer | |
222 | : public base_visitor<property_writer<PA, OutputIterator, Tag> > | |
223 | { | |
224 | typedef Tag event_filter; | |
225 | ||
226 | property_writer(PA pa, OutputIterator out) : m_pa(pa), m_out(out) { } | |
227 | ||
228 | template <class T, class Graph> | |
229 | void operator()(T x, Graph&) { *m_out++ = get(m_pa, x); } | |
230 | PA m_pa; | |
231 | OutputIterator m_out; | |
232 | }; | |
233 | template <class PA, class OutputIterator, class Tag> | |
234 | property_writer<PA, OutputIterator, Tag> | |
235 | write_property(PA pa, OutputIterator out, Tag) { | |
236 | return property_writer<PA, OutputIterator, Tag>(pa, out); | |
237 | } | |
238 | ||
239 | //======================================================================== | |
240 | // property_put | |
241 | ||
242 | /** | |
243 | * Functor which just sets a given value to a vertex or edge in a property map. | |
244 | */ | |
245 | ||
246 | template <typename PropertyMap, typename EventTag> | |
247 | struct property_put | |
248 | { | |
249 | typedef EventTag event_filter; | |
250 | ||
251 | property_put (PropertyMap property_map, | |
252 | typename property_traits <PropertyMap>::value_type value) : | |
253 | property_map_ (property_map), value_ (value) | |
254 | {} | |
255 | ||
256 | template <typename VertexOrEdge, typename Graph> | |
257 | void operator() (VertexOrEdge v, const Graph&) | |
258 | { | |
259 | put (property_map_, v, value_); | |
260 | } | |
261 | ||
262 | private: | |
263 | PropertyMap property_map_; | |
264 | typename property_traits <PropertyMap>::value_type value_; | |
265 | }; | |
266 | ||
267 | /** | |
268 | * Creates a property_put functor which just sets a given value to a vertex or edge. | |
269 | * | |
270 | * @param property_map Given writeable property map | |
271 | * @param value Fixed value of the map | |
272 | * @param tag Event Filter | |
273 | * @return The functor. | |
274 | */ | |
275 | ||
276 | template <typename PropertyMap, typename EventTag> | |
277 | inline property_put <PropertyMap, EventTag> | |
278 | put_property (PropertyMap property_map, | |
279 | typename property_traits <PropertyMap>::value_type value, | |
280 | EventTag) | |
281 | { | |
282 | return property_put <PropertyMap, EventTag> (property_map, value); | |
283 | } | |
284 | ||
285 | #define BOOST_GRAPH_EVENT_STUB(Event,Kind) \ | |
286 | typedef ::boost::Event Event##_type; \ | |
287 | template<typename Visitor> \ | |
288 | Kind##_visitor<std::pair<detail::functor_to_visitor<Event##_type, \ | |
289 | Visitor>, Visitors> > \ | |
290 | do_##Event(Visitor visitor) \ | |
291 | { \ | |
292 | typedef std::pair<detail::functor_to_visitor<Event##_type, Visitor>, \ | |
293 | Visitors> visitor_list; \ | |
294 | typedef Kind##_visitor<visitor_list> result_type; \ | |
295 | return result_type(visitor_list(visitor, m_vis)); \ | |
296 | } | |
297 | ||
298 | } /* namespace boost */ | |
299 | ||
300 | #endif |