/usr/include/boost/graph/st_connected.hpp is in libboost1.46-dev 1.46.1-7ubuntu3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | // 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
|