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
st_connected(const Graph & g,typename graph_traits<Graph>::vertex_descriptor s,typename graph_traits<Graph>::vertex_descriptor t,ColorMap color)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
st_connected(const Graph & g,typename graph_traits<Graph>::vertex_descriptor s,typename graph_traits<Graph>::vertex_descriptor t)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
83