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