boost/graph/st_connected.hpp

   1 // Copyright (C) 2006 The Trustees of Indiana University.
   2
   3 // Use, modification and distribution is subject to the Boost Software
   4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 //  Authors: Douglas Gregor
   8 //           Andrew Lumsdaine
   9 #ifndef BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP
  10 #define BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP
  11
  12 #include <boost/graph/graph_traits.hpp>
  13 #include <boost/graph/two_bit_color_map.hpp>
  14 #include <boost/graph/iteration_macros.hpp>
  15 #include <boost/pending/queue.hpp>
  16
  17 namespace boost { namespace graph {
  18
  19 template<typename Graph, typename ColorMap>
  20 bool
  21 st_connected(const Graph& g,
  22              typename graph_traits<Graph>::vertex_descriptor s,
  23              typename graph_traits<Graph>::vertex_descriptor t,
  24              ColorMap color)
  25 {
  26   typedef typename property_traits<ColorMap>::value_type Color;
  27   typedef color_traits<Color> ColorTraits;
  28   typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  29
  30   // Set all vertices to white (unvisited)
  31   BGL_FORALL_VERTICES_T(v, g, Graph)
  32     put(color, v, ColorTraits::white());
  33
  34   // Vertices found from the source are grey
  35   put(color, s, ColorTraits::gray());
  36
  37   // Vertices found from the target are greeen
  38   put(color, t, ColorTraits::green());
  39   queue<Vertex> Q;
  40   Q.push(s);
  41   Q.push(t);
  42
  43   while (!Q.empty()) {
  44     Vertex u = Q.top(); Q.pop();
  45     Color u_color = get(color, u);
  46
  47     BGL_FORALL_OUTEDGES_T(u, e, g, Graph) {
  48       Vertex v = target(e, g);
  49       Color v_color = get(color, v);
  50       if (v_color == ColorTraits::white()) {
  51         // We have not seen "v" before; mark it with the same color as u
  52         Color u_color = get(color, u);
  53         put(color, v, u_color);
  54
  55         // Push it on the queue
  56         Q.push(v);
  57       } else if (v_color != ColorTraits::black() && u_color != v_color) {
  58         // Colors have collided. We're done!
  59         return true;
  60       }
  61     }
  62     // u is done, so mark it black
  63     put(color, u, ColorTraits::black());
  64   }
  65
  66   return false;
  67 }
  68
  69 template<typename Graph>
  70 inline bool
  71 st_connected(const Graph& g,
  72              typename graph_traits<Graph>::vertex_descriptor s,
  73              typename graph_traits<Graph>::vertex_descriptor t)
  74 {
  75   return st_connected(g, s, t,
  76                       make_two_bit_color_map(num_vertices(g),
  77                                              get(vertex_index, g)));
  78 }
  79
  80 } } // end namespace boost::graph
  81
  82 #endif // BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP