Chris@16: // Copyright (C) 2006 The Trustees of Indiana University.
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software
Chris@16: // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: //  Authors: Douglas Gregor
Chris@16: //           Andrew Lumsdaine
Chris@16: #ifndef BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP
Chris@16: #define BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP
Chris@16: 
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/graph/two_bit_color_map.hpp>
Chris@16: #include <boost/graph/iteration_macros.hpp>
Chris@16: #include <boost/pending/queue.hpp>
Chris@16: 
Chris@16: namespace boost { namespace graph {
Chris@16: 
Chris@16: template<typename Graph, typename ColorMap>
Chris@16: bool 
Chris@16: st_connected(const Graph& g, 
Chris@16:              typename graph_traits<Graph>::vertex_descriptor s,
Chris@16:              typename graph_traits<Graph>::vertex_descriptor t,
Chris@16:              ColorMap color)
Chris@16: {
Chris@16:   typedef typename property_traits<ColorMap>::value_type Color;
Chris@16:   typedef color_traits<Color> ColorTraits;
Chris@16:   typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16: 
Chris@16:   // Set all vertices to white (unvisited)
Chris@16:   BGL_FORALL_VERTICES_T(v, g, Graph)
Chris@16:     put(color, v, ColorTraits::white());
Chris@16: 
Chris@16:   // Vertices found from the source are grey
Chris@16:   put(color, s, ColorTraits::gray());
Chris@16: 
Chris@16:   // Vertices found from the target are greeen
Chris@16:   put(color, t, ColorTraits::green());
Chris@16:   queue<Vertex> Q;
Chris@16:   Q.push(s);
Chris@16:   Q.push(t);
Chris@16: 
Chris@16:   while (!Q.empty()) {
Chris@16:     Vertex u = Q.top(); Q.pop();
Chris@16:     Color u_color = get(color, u);
Chris@16: 
Chris@16:     BGL_FORALL_OUTEDGES_T(u, e, g, Graph) {
Chris@16:       Vertex v = target(e, g);
Chris@16:       Color v_color = get(color, v);
Chris@16:       if (v_color == ColorTraits::white()) {
Chris@16:         // We have not seen "v" before; mark it with the same color as u
Chris@16:         Color u_color = get(color, u);
Chris@16:         put(color, v, u_color);
Chris@16:         
Chris@16:         // Push it on the queue
Chris@16:         Q.push(v);
Chris@16:       } else if (v_color != ColorTraits::black() && u_color != v_color) {
Chris@16:         // Colors have collided. We're done!
Chris@16:         return true;
Chris@16:       }
Chris@16:     }
Chris@16:     // u is done, so mark it black
Chris@16:     put(color, u, ColorTraits::black());
Chris@16:   }
Chris@16: 
Chris@16:   return false;
Chris@16: }
Chris@16: 
Chris@16: template<typename Graph>
Chris@16: inline bool 
Chris@16: st_connected(const Graph& g, 
Chris@16:              typename graph_traits<Graph>::vertex_descriptor s,
Chris@16:              typename graph_traits<Graph>::vertex_descriptor t)
Chris@16: {
Chris@16:   return st_connected(g, s, t, 
Chris@16:                       make_two_bit_color_map(num_vertices(g),
Chris@16:                                              get(vertex_index, g)));
Chris@16: }
Chris@16: 
Chris@16: } } // end namespace boost::graph
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP