boost/graph/st_connected.hpp

0001 // Copyright (C) 2006 The Trustees of Indiana University.
0002
0003 // Use, modification and distribution is subject to the Boost Software
0004 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Douglas Gregor
0008 //           Andrew Lumsdaine
0009 #ifndef BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP
0010 #define BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP
0011
0012 #include <boost/graph/graph_traits.hpp>
0013 #include <boost/graph/two_bit_color_map.hpp>
0014 #include <boost/graph/iteration_macros.hpp>
0015 #include <boost/pending/queue.hpp>
0016
0017 namespace boost
0018 {
0019 namespace graph
0020 {
0021
0022     template < typename Graph, typename ColorMap >
0023     bool st_connected(const Graph& g,
0024         typename graph_traits< Graph >::vertex_descriptor s,
0025         typename graph_traits< Graph >::vertex_descriptor t, ColorMap color)
0026     {
0027         typedef typename property_traits< ColorMap >::value_type Color;
0028         typedef color_traits< Color > ColorTraits;
0029         typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0030
0031         // Set all vertices to white (unvisited)
0032         BGL_FORALL_VERTICES_T(v, g, Graph)
0033         put(color, v, ColorTraits::white());
0034
0035         // Vertices found from the source are grey
0036         put(color, s, ColorTraits::gray());
0037
0038         // Vertices found from the target are greeen
0039         put(color, t, ColorTraits::green());
0040         queue< Vertex > Q;
0041         Q.push(s);
0042         Q.push(t);
0043
0044         while (!Q.empty())
0045         {
0046             Vertex u = Q.top();
0047             Q.pop();
0048             Color u_color = get(color, u);
0049
0050             BGL_FORALL_OUTEDGES_T(u, e, g, Graph)
0051             {
0052                 Vertex v = target(e, g);
0053                 Color v_color = get(color, v);
0054                 if (v_color == ColorTraits::white())
0055                 {
0056                     // We have not seen "v" before; mark it with the same color
0057                     // as u
0058                     Color u_color = get(color, u);
0059                     put(color, v, u_color);
0060
0061                     // Push it on the queue
0062                     Q.push(v);
0063                 }
0064                 else if (v_color != ColorTraits::black() && u_color != v_color)
0065                 {
0066                     // Colors have collided. We're done!
0067                     return true;
0068                 }
0069             }
0070             // u is done, so mark it black
0071             put(color, u, ColorTraits::black());
0072         }
0073
0074         return false;
0075     }
0076
0077     template < typename Graph >
0078     inline bool st_connected(const Graph& g,
0079         typename graph_traits< Graph >::vertex_descriptor s,
0080         typename graph_traits< Graph >::vertex_descriptor t)
0081     {
0082         return st_connected(g, s, t,
0083             make_two_bit_color_map(num_vertices(g), get(vertex_index, g)));
0084     }
0085
0086 }
0087 } // end namespace boost::graph
0088
0089 #endif // BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP