boost/graph/visitors.hpp

0001 //=======================================================================
0002 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0003 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //=======================================================================
0009 //
0010 // Revision History:
0011 //   01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
0012 //
0013 #ifndef BOOST_GRAPH_GRAPH_SEARCH_VISITORS_HPP
0014 #define BOOST_GRAPH_GRAPH_SEARCH_VISITORS_HPP
0015
0016 #include <iosfwd>
0017 #include <boost/config.hpp>
0018 #include <boost/type_traits/is_same.hpp>
0019 #include <boost/mpl/bool.hpp>
0020 #include <boost/property_map/property_map.hpp>
0021 #include <boost/graph/graph_traits.hpp>
0022 #include <boost/limits.hpp>
0023
0024 namespace boost
0025 {
0026
0027 // This is a bit more convenient than std::numeric_limits because
0028 // you don't have to explicitly provide type T.
0029 template < class T > inline T numeric_limits_max(T)
0030 {
0031     return (std::numeric_limits< T >::max)();
0032 }
0033
0034 //========================================================================
0035 // Event Tags
0036
0037 namespace detail
0038 {
0039     // For partial specialization workaround
0040     enum event_visitor_enum
0041     {
0042         on_no_event_num,
0043         on_initialize_vertex_num,
0044         on_start_vertex_num,
0045         on_discover_vertex_num,
0046         on_finish_vertex_num,
0047         on_examine_vertex_num,
0048         on_examine_edge_num,
0049         on_tree_edge_num,
0050         on_non_tree_edge_num,
0051         on_gray_target_num,
0052         on_black_target_num,
0053         on_forward_or_cross_edge_num,
0054         on_back_edge_num,
0055         on_finish_edge_num,
0056         on_edge_relaxed_num,
0057         on_edge_not_relaxed_num,
0058         on_edge_minimized_num,
0059         on_edge_not_minimized_num
0060     };
0061
0062     template < typename Event, typename Visitor >
0063     struct functor_to_visitor : Visitor
0064     {
0065         typedef Event event_filter;
0066         functor_to_visitor(const Visitor& visitor) : Visitor(visitor) {}
0067     };
0068
0069 } // namespace detail
0070
0071 struct on_no_event
0072 {
0073     enum
0074     {
0075         num = detail::on_no_event_num
0076     };
0077 };
0078
0079 struct on_initialize_vertex
0080 {
0081     enum
0082     {
0083         num = detail::on_initialize_vertex_num
0084     };
0085 };
0086 struct on_start_vertex
0087 {
0088     enum
0089     {
0090         num = detail::on_start_vertex_num
0091     };
0092 };
0093 struct on_discover_vertex
0094 {
0095     enum
0096     {
0097         num = detail::on_discover_vertex_num
0098     };
0099 };
0100 struct on_examine_vertex
0101 {
0102     enum
0103     {
0104         num = detail::on_examine_vertex_num
0105     };
0106 };
0107 struct on_finish_vertex
0108 {
0109     enum
0110     {
0111         num = detail::on_finish_vertex_num
0112     };
0113 };
0114
0115 struct on_examine_edge
0116 {
0117     enum
0118     {
0119         num = detail::on_examine_edge_num
0120     };
0121 };
0122 struct on_tree_edge
0123 {
0124     enum
0125     {
0126         num = detail::on_tree_edge_num
0127     };
0128 };
0129 struct on_non_tree_edge
0130 {
0131     enum
0132     {
0133         num = detail::on_non_tree_edge_num
0134     };
0135 };
0136 struct on_gray_target
0137 {
0138     enum
0139     {
0140         num = detail::on_gray_target_num
0141     };
0142 };
0143 struct on_black_target
0144 {
0145     enum
0146     {
0147         num = detail::on_black_target_num
0148     };
0149 };
0150 struct on_forward_or_cross_edge
0151 {
0152     enum
0153     {
0154         num = detail::on_forward_or_cross_edge_num
0155     };
0156 };
0157 struct on_back_edge
0158 {
0159     enum
0160     {
0161         num = detail::on_back_edge_num
0162     };
0163 };
0164 struct on_finish_edge
0165 {
0166     enum
0167     {
0168         num = detail::on_finish_edge_num
0169     };
0170 };
0171
0172 struct on_edge_relaxed
0173 {
0174     enum
0175     {
0176         num = detail::on_edge_relaxed_num
0177     };
0178 };
0179 struct on_edge_not_relaxed
0180 {
0181     enum
0182     {
0183         num = detail::on_edge_not_relaxed_num
0184     };
0185 };
0186 struct on_edge_minimized
0187 {
0188     enum
0189     {
0190         num = detail::on_edge_minimized_num
0191     };
0192 };
0193 struct on_edge_not_minimized
0194 {
0195     enum
0196     {
0197         num = detail::on_edge_not_minimized_num
0198     };
0199 };
0200
0201 //========================================================================
0202 // base_visitor and null_visitor
0203
0204 // needed for MSVC workaround
0205 template < class Visitor > struct base_visitor
0206 {
0207     typedef on_no_event event_filter;
0208     template < class T, class Graph > void operator()(T, Graph&) {}
0209 };
0210
0211 struct null_visitor : public base_visitor< null_visitor >
0212 {
0213     typedef on_no_event event_filter;
0214     template < class T, class Graph > void operator()(T, Graph&) {}
0215 };
0216
0217 //========================================================================
0218 // The invoke_visitors() function
0219
0220 namespace detail
0221 {
0222     template < class Visitor, class T, class Graph >
0223     inline void invoke_dispatch(Visitor& v, T x, Graph& g, mpl::true_)
0224     {
0225         v(x, g);
0226     }
0227
0228     template < class Visitor, class T, class Graph >
0229     inline void invoke_dispatch(Visitor&, T, Graph&, mpl::false_)
0230     {
0231     }
0232 } // namespace detail
0233
0234 template < class Visitor, class Rest, class T, class Graph, class Tag >
0235 inline void invoke_visitors(
0236     std::pair< Visitor, Rest >& vlist, T x, Graph& g, Tag tag)
0237 {
0238     typedef typename Visitor::event_filter Category;
0239     typedef typename is_same< Category, Tag >::type IsSameTag;
0240     detail::invoke_dispatch(vlist.first, x, g, IsSameTag());
0241     invoke_visitors(vlist.second, x, g, tag);
0242 }
0243 template < class Visitor, class T, class Graph, class Tag >
0244 inline void invoke_visitors(Visitor& v, T x, Graph& g, Tag)
0245 {
0246     typedef typename Visitor::event_filter Category;
0247     typedef typename is_same< Category, Tag >::type IsSameTag;
0248     detail::invoke_dispatch(v, x, g, IsSameTag());
0249 }
0250
0251 //========================================================================
0252 // predecessor_recorder
0253
0254 template < class PredecessorMap, class Tag >
0255 struct predecessor_recorder
0256 : public base_visitor< predecessor_recorder< PredecessorMap, Tag > >
0257 {
0258     typedef Tag event_filter;
0259     predecessor_recorder(PredecessorMap pa) : m_predecessor(pa) {}
0260     template < class Edge, class Graph > void operator()(Edge e, const Graph& g)
0261     {
0262         put(m_predecessor, target(e, g), source(e, g));
0263     }
0264     PredecessorMap m_predecessor;
0265 };
0266 template < class PredecessorMap, class Tag >
0267 predecessor_recorder< PredecessorMap, Tag > record_predecessors(
0268     PredecessorMap pa, Tag)
0269 {
0270     return predecessor_recorder< PredecessorMap, Tag >(pa);
0271 }
0272
0273 //========================================================================
0274 // edge_predecessor_recorder
0275
0276 template < class PredEdgeMap, class Tag >
0277 struct edge_predecessor_recorder
0278 : public base_visitor< edge_predecessor_recorder< PredEdgeMap, Tag > >
0279 {
0280     typedef Tag event_filter;
0281     edge_predecessor_recorder(PredEdgeMap pa) : m_predecessor(pa) {}
0282     template < class Edge, class Graph > void operator()(Edge e, const Graph& g)
0283     {
0284         put(m_predecessor, target(e, g), e);
0285     }
0286     PredEdgeMap m_predecessor;
0287 };
0288 template < class PredEdgeMap, class Tag >
0289 edge_predecessor_recorder< PredEdgeMap, Tag > record_edge_predecessors(
0290     PredEdgeMap pa, Tag)
0291 {
0292     return edge_predecessor_recorder< PredEdgeMap, Tag >(pa);
0293 }
0294
0295 //========================================================================
0296 // distance_recorder
0297
0298 template < class DistanceMap, class Tag >
0299 struct distance_recorder
0300 : public base_visitor< distance_recorder< DistanceMap, Tag > >
0301 {
0302     typedef Tag event_filter;
0303     distance_recorder(DistanceMap pa) : m_distance(pa) {}
0304     template < class Edge, class Graph > void operator()(Edge e, const Graph& g)
0305     {
0306         typename graph_traits< Graph >::vertex_descriptor u = source(e, g),
0307                                                           v = target(e, g);
0308         put(m_distance, v, get(m_distance, u) + 1);
0309     }
0310     DistanceMap m_distance;
0311 };
0312 template < class DistanceMap, class Tag >
0313 distance_recorder< DistanceMap, Tag > record_distances(DistanceMap pa, Tag)
0314 {
0315     return distance_recorder< DistanceMap, Tag >(pa);
0316 }
0317
0318 //========================================================================
0319 // time_stamper
0320
0321 template < class TimeMap, class TimeT, class Tag >
0322 struct time_stamper : public base_visitor< time_stamper< TimeMap, TimeT, Tag > >
0323 {
0324     typedef Tag event_filter;
0325     time_stamper(TimeMap pa, TimeT& t) : m_time_pa(pa), m_time(t) {}
0326     template < class Vertex, class Graph >
0327     void operator()(Vertex u, const Graph&)
0328     {
0329         put(m_time_pa, u, ++m_time);
0330     }
0331     TimeMap m_time_pa;
0332     TimeT& m_time;
0333 };
0334 template < class TimeMap, class TimeT, class Tag >
0335 time_stamper< TimeMap, TimeT, Tag > stamp_times(
0336     TimeMap pa, TimeT& time_counter, Tag)
0337 {
0338     return time_stamper< TimeMap, TimeT, Tag >(pa, time_counter);
0339 }
0340
0341 //========================================================================
0342 // property_writer
0343
0344 template < class PA, class OutputIterator, class Tag >
0345 struct property_writer
0346 : public base_visitor< property_writer< PA, OutputIterator, Tag > >
0347 {
0348     typedef Tag event_filter;
0349
0350     property_writer(PA pa, OutputIterator out) : m_pa(pa), m_out(out) {}
0351
0352     template < class T, class Graph > void operator()(T x, Graph&)
0353     {
0354         *m_out++ = get(m_pa, x);
0355     }
0356     PA m_pa;
0357     OutputIterator m_out;
0358 };
0359 template < class PA, class OutputIterator, class Tag >
0360 property_writer< PA, OutputIterator, Tag > write_property(
0361     PA pa, OutputIterator out, Tag)
0362 {
0363     return property_writer< PA, OutputIterator, Tag >(pa, out);
0364 }
0365
0366 //========================================================================
0367 // property_put
0368
0369 /**
0370  * Functor which just sets a given value to a vertex or edge in a property map.
0371  */
0372
0373 template < typename PropertyMap, typename EventTag > struct property_put
0374 {
0375     typedef EventTag event_filter;
0376
0377     property_put(PropertyMap property_map,
0378         typename property_traits< PropertyMap >::value_type value)
0379     : property_map_(property_map), value_(value)
0380     {
0381     }
0382
0383     template < typename VertexOrEdge, typename Graph >
0384     void operator()(VertexOrEdge v, const Graph&)
0385     {
0386         put(property_map_, v, value_);
0387     }
0388
0389 private:
0390     PropertyMap property_map_;
0391     typename property_traits< PropertyMap >::value_type value_;
0392 };
0393
0394 /**
0395  * Creates a property_put functor which just sets a given value to a vertex or
0396  * edge.
0397  *
0398  * @param property_map Given writeable property map
0399  * @param value Fixed value of the map
0400  * @param tag Event Filter
0401  * @return The functor.
0402  */
0403
0404 template < typename PropertyMap, typename EventTag >
0405 inline property_put< PropertyMap, EventTag > put_property(
0406     PropertyMap property_map,
0407     typename property_traits< PropertyMap >::value_type value, EventTag)
0408 {
0409     return property_put< PropertyMap, EventTag >(property_map, value);
0410 }
0411
0412 #define BOOST_GRAPH_EVENT_STUB(Event, Kind)                                 \
0413     typedef ::boost::Event Event##_type;                                    \
0414     template < typename Visitor >                                           \
0415     Kind##_visitor< std::pair<                                              \
0416         detail::functor_to_visitor< Event##_type, Visitor >, Visitors > >   \
0417         do_##Event(Visitor visitor)                                         \
0418     {                                                                       \
0419         typedef std::pair<                                                  \
0420             detail::functor_to_visitor< Event##_type, Visitor >, Visitors > \
0421             visitor_list;                                                   \
0422         typedef Kind##_visitor< visitor_list > result_type;                 \
0423         return result_type(visitor_list(visitor, m_vis));                   \
0424     }
0425
0426 } /* namespace boost */
0427
0428 #endif