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> numeric_limits_max(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; functor_to_visitorboost::detail::functor_to_visitor51 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> operator ()boost::base_visitor90 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> operator ()boost::null_visitor96 void operator()(T, Graph&) { } 97 }; 98 99 //======================================================================== 100 // The invoke_visitors() function 101 102 namespace detail { 103 template <class Visitor, class T, class Graph> invoke_dispatch(Visitor & v,T x,Graph & g,mpl::true_)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> invoke_dispatch(Visitor &,T,Graph &,mpl::false_)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 invoke_visitors(std::pair<Visitor,Rest> & vlist,T x,Graph & g,Tag tag)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 invoke_visitors(Visitor & v,T x,Graph & g,Tag)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; predecessor_recorderboost::predecessor_recorder137 predecessor_recorder(PredecessorMap pa) : m_predecessor(pa) { } 138 template <class Edge, class Graph> operator ()boost::predecessor_recorder139 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> record_predecessors(PredecessorMap pa,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; edge_predecessor_recorderboost::edge_predecessor_recorder158 edge_predecessor_recorder(PredEdgeMap pa) : m_predecessor(pa) { } 159 template <class Edge, class Graph> operator ()boost::edge_predecessor_recorder160 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> record_edge_predecessors(PredEdgeMap pa,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; distance_recorderboost::distance_recorder179 distance_recorder(DistanceMap pa) : m_distance(pa) { } 180 template <class Edge, class Graph> operator ()boost::distance_recorder181 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> record_distances(DistanceMap pa,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; time_stamperboost::time_stamper203 time_stamper(TimeMap pa, TimeT& t) : m_time_pa(pa), m_time(t) { } 204 template <class Vertex, class Graph> operator ()boost::time_stamper205 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> stamp_times(TimeMap pa,TimeT & time_counter,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 property_writerboost::property_writer226 property_writer(PA pa, OutputIterator out) : m_pa(pa), m_out(out) { } 227 228 template <class T, class Graph> operator ()boost::property_writer229 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> write_property(PA pa,OutputIterator out,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 property_putboost::property_put251 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> operator ()boost::property_put257 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> put_property(PropertyMap property_map,typename property_traits<PropertyMap>::value_type value,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 301