]>
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 | ||
17 | namespace boost { namespace graph { | |
18 | ||
19 | template<typename Graph, typename ColorMap> | |
20 | bool | |
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 | |
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 |