1 files changed, 148 insertions, 0 deletions
diff --git a/src/boost/libs/graph/example/neighbor_bfs.cpp b/src/boost/libs/graph/example/neighbor_bfs.cpp
new file mode 100644
index 00000000..7b3e339a
--- /dev/null
+++ b/src/boost/libs/graph/example/neighbor_bfs.cpp
@@ -0,0 +1,148 @@
+//=======================================================================
+// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
+// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
+//
+// Distributed under 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)
+//=======================================================================
+
+#include <boost/config.hpp>
+
+#include <algorithm>
+#include <vector>
+#include <utility>
+#include <iostream>
+
+#include <boost/graph/visitors.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/graph_utility.hpp>
+#include <boost/graph/neighbor_bfs.hpp>
+#include <boost/property_map/property_map.hpp>
+
+/*
+  
+  Sample Output:
+
+  0 --> 2 
+  1 --> 1 3 4 
+  2 --> 1 3 4 
+  3 --> 1 4 
+  4 --> 0 1 
+  distances: 0 2 1 2 1 
+  parent[0] = 0
+  parent[1] = 2
+  parent[2] = 0
+  parent[3] = 2
+  parent[4] = 0
+
+*/
+
+using namespace boost;
+
+template <class ParentDecorator>
+struct print_parent {
+  print_parent(const ParentDecorator& p_) : p(p_) { }
+  template <class Vertex>
+  void operator()(const Vertex& v) const {
+    std::cout << "parent[" << v << "] = " <<  p[v]  << std::endl;
+  }
+  ParentDecorator p;
+};
+
+template <class DistanceMap, class PredecessorMap, class ColorMap>
+class distance_and_pred_visitor : public neighbor_bfs_visitor<>
+{
+  typedef typename property_traits<ColorMap>::value_type ColorValue;
+  typedef color_traits<ColorValue> Color;
+public:
+  distance_and_pred_visitor(DistanceMap d, PredecessorMap p, ColorMap c)
+    : m_distance(d), m_predecessor(p), m_color(c) { }
+
+  template <class Edge, class Graph>
+  void tree_out_edge(Edge e, const Graph& g) const
+  {
+    typename graph_traits<Graph>::vertex_descriptor 
+      u = source(e, g), v = target(e, g);
+    put(m_distance, v, get(m_distance, u) + 1);
+    put(m_predecessor, v, u);
+  }
+  template <class Edge, class Graph>
+  void tree_in_edge(Edge e, const Graph& g) const
+  {
+    typename graph_traits<Graph>::vertex_descriptor 
+      u = source(e, g), v = target(e, g);
+    put(m_distance, u, get(m_distance, v) + 1);
+    put(m_predecessor, u, v);
+  }
+
+  DistanceMap m_distance;
+  PredecessorMap m_predecessor;
+  ColorMap m_color;
+};
+
+int main(int , char* []) 
+{
+  typedef adjacency_list< 
+    mapS, vecS, bidirectionalS,
+    property<vertex_color_t, default_color_type>
+  > Graph;
+
+  typedef property_map<Graph, vertex_color_t>::type
+    ColorMap;
+  
+  Graph G(5);
+  add_edge(0, 2, G);
+  add_edge(1, 1, G);
+  add_edge(1, 3, G);
+  add_edge(1, 4, G);
+  add_edge(2, 1, G);
+  add_edge(2, 3, G);
+  add_edge(2, 4, G);
+  add_edge(3, 1, G);
+  add_edge(3, 4, G);
+  add_edge(4, 0, G);
+  add_edge(4, 1, G);
+
+  typedef Graph::vertex_descriptor Vertex;
+
+  // Array to store predecessor (parent) of each vertex. This will be
+  // used as a Decorator (actually, its iterator will be).
+  std::vector<Vertex> p(num_vertices(G));
+  // VC++ version of std::vector has no ::pointer, so
+  // I use ::value_type* instead.
+  typedef std::vector<Vertex>::value_type* Piter;
+
+  // Array to store distances from the source to each vertex .  We use
+  // a built-in array here just for variety. This will also be used as
+  // a Decorator.  
+  typedef graph_traits<Graph>::vertices_size_type size_type;
+  size_type d[5];
+  std::fill_n(d, 5, 0);
+
+  // The source vertex
+  Vertex s = *(vertices(G).first);
+  p[s] = s;
+  distance_and_pred_visitor<size_type*, Vertex*, ColorMap> 
+    vis(d, &p[0], get(vertex_color, G));
+  neighbor_breadth_first_search
+    (G, s, visitor(vis).
+     color_map(get(vertex_color, G)));
+
+  print_graph(G);
+
+  if (num_vertices(G) < 11) {
+    std::cout << "distances: ";
+#ifdef BOOST_OLD_STREAM_ITERATORS
+    std::copy(d, d + 5, std::ostream_iterator<int, char>(std::cout, " "));
+#else
+    std::copy(d, d + 5, std::ostream_iterator<int>(std::cout, " "));
+#endif
+    std::cout << std::endl;
+
+    std::for_each(vertices(G).first, vertices(G).second, 
+                  print_parent<Piter>(&p[0]));
+  }
+
+  return 0;
+}