]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
f67539c2 TL |
17 | namespace boost |
18 | { | |
19 | namespace graph | |
7c673cae | 20 | { |
7c673cae | 21 | |
f67539c2 TL |
22 | template < typename Graph, typename ColorMap > |
23 | bool st_connected(const Graph& g, | |
24 | typename graph_traits< Graph >::vertex_descriptor s, | |
25 | typename graph_traits< Graph >::vertex_descriptor t, ColorMap color) | |
26 | { | |
27 | typedef typename property_traits< ColorMap >::value_type Color; | |
28 | typedef color_traits< Color > ColorTraits; | |
29 | typedef typename graph_traits< Graph >::vertex_descriptor Vertex; | |
30 | ||
31 | // Set all vertices to white (unvisited) | |
32 | BGL_FORALL_VERTICES_T(v, g, Graph) | |
33 | put(color, v, ColorTraits::white()); | |
34 | ||
35 | // Vertices found from the source are grey | |
36 | put(color, s, ColorTraits::gray()); | |
37 | ||
38 | // Vertices found from the target are greeen | |
39 | put(color, t, ColorTraits::green()); | |
40 | queue< Vertex > Q; | |
41 | Q.push(s); | |
42 | Q.push(t); | |
7c673cae | 43 | |
f67539c2 TL |
44 | while (!Q.empty()) |
45 | { | |
46 | Vertex u = Q.top(); | |
47 | Q.pop(); | |
48 | Color u_color = get(color, u); | |
7c673cae | 49 | |
f67539c2 TL |
50 | BGL_FORALL_OUTEDGES_T(u, e, g, Graph) |
51 | { | |
52 | Vertex v = target(e, g); | |
53 | Color v_color = get(color, v); | |
54 | if (v_color == ColorTraits::white()) | |
55 | { | |
56 | // We have not seen "v" before; mark it with the same color | |
57 | // as u | |
58 | Color u_color = get(color, u); | |
59 | put(color, v, u_color); | |
7c673cae | 60 | |
f67539c2 TL |
61 | // Push it on the queue |
62 | Q.push(v); | |
63 | } | |
64 | else if (v_color != ColorTraits::black() && u_color != v_color) | |
65 | { | |
66 | // Colors have collided. We're done! | |
67 | return true; | |
68 | } | |
69 | } | |
70 | // u is done, so mark it black | |
71 | put(color, u, ColorTraits::black()); | |
72 | } | |
7c673cae | 73 | |
f67539c2 | 74 | return false; |
7c673cae | 75 | } |
7c673cae | 76 | |
f67539c2 TL |
77 | template < typename Graph > |
78 | inline bool st_connected(const Graph& g, | |
79 | typename graph_traits< Graph >::vertex_descriptor s, | |
80 | typename graph_traits< Graph >::vertex_descriptor t) | |
81 | { | |
82 | return st_connected(g, s, t, | |
83 | make_two_bit_color_map(num_vertices(g), get(vertex_index, g))); | |
84 | } | |
7c673cae | 85 | |
7c673cae | 86 | } |
f67539c2 | 87 | } // end namespace boost::graph |
7c673cae FG |
88 | |
89 | #endif // BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP |