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