comparison DEPENDENCIES/generic/include/boost/graph/st_connected.hpp @ 16:2665513ce2d3

Add boost headers

+// 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