Line data    Source code

       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           0 :     inline void invoke_dispatch(Visitor& v, T x, Graph& g, mpl::true_) {
     105           0 :        v(x, g);
     106             :     }
     107             : 
     108             :     template <class Visitor, class T, class Graph>
     109           0 :     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           0 :   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           0 :     detail::invoke_dispatch(vlist.first, x, g, IsSameTag());
     119           0 :     invoke_visitors(vlist.second, x, g, tag);
     120             :   }
     121             :   template <class Visitor, class T, class Graph, class Tag>
     122             :   inline void
     123           0 :   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           0 :     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           0 :     predecessor_recorder(PredecessorMap pa) : m_predecessor(pa) { }
     138             :     template <class Edge, class Graph>
     139           0 :     void operator()(Edge e, const Graph& g) {
     140           0 :       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           0 :   record_predecessors(PredecessorMap pa, Tag) {
     147           0 :     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           0 :     time_stamper(TimeMap pa, TimeT& t) : m_time_pa(pa), m_time(t) { }
     204             :     template <class Vertex, class Graph>
     205           0 :     void operator()(Vertex u, const Graph&) {
     206           0 :       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