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