Adding upstream version 14.2.21.upstream/14.2.21upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 160 insertions, 0 deletions

diff --git a/src/boost/libs/graph/example/bfs.cpp b/src/boost/libs/graph/example/bfs.cpp
new file mode 100644
index 00000000..1f34c155
--- /dev/null
+++ b/src/boost/libs/graph/example/bfs.cpp
@@ -0,0 +1,160 @@
+//=======================================================================
+// 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/breadth_first_search.hpp>
+#include <boost/property_map/property_map.hpp>
+#include <boost/graph/graph_utility.hpp>
+
+/*
+  
+  This examples shows how to use the breadth_first_search() GGCL
+  algorithm, specifically the 3 argument variant of bfs that assumes
+  the graph has a color property (property) stored internally.
+
+  Two pre-defined visitors are used to record the distance of each
+  vertex from the source vertex, and also to record the parent of each
+  vertex. Any number of visitors can be layered and passed to a GGCL
+  algorithm.
+
+  The call to vertices(G) returns an STL-compatible container which
+  contains all of the vertices in the graph.  In this example we use
+  the vertices container in the STL for_each() function.
+
+  Sample Output:
+
+  0 --> 2 
+  1 --> 1 3 4 
+  2 --> 1 3 4 
+  3 --> 1 4 
+  4 --> 0 1 
+  0 --> 2 
+  1 --> 1 3 4 
+  2 --> 1 3 4 
+  3 --> 1 4 
+  4 --> 0 1 
+  distances: 0 2 1 2 2 
+  parent[0] = 0
+  parent[1] = 2
+  parent[2] = 0
+  parent[3] = 2
+  parent[4] = 2
+
+*/
+
+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 NewGraph, class Tag>
+struct graph_copier 
+  : public boost::base_visitor<graph_copier<NewGraph, Tag> >
+{
+  typedef Tag event_filter;
+
+  graph_copier(NewGraph& graph) : new_g(graph) { }
+
+  template <class Edge, class Graph>
+  void operator()(Edge e, Graph& g) {
+    boost::add_edge(boost::source(e, g), boost::target(e, g), new_g);
+  }
+private:
+  NewGraph& new_g;
+};
+
+template <class NewGraph, class Tag>
+inline graph_copier<NewGraph, Tag>
+copy_graph(NewGraph& g, Tag) {
+  return graph_copier<NewGraph, Tag>(g);
+}
+
+int main(int , char* []) 
+{
+  typedef boost::adjacency_list< 
+    boost::mapS, boost::vecS, boost::bidirectionalS,
+    boost::property<boost::vertex_color_t, boost::default_color_type,
+        boost::property<boost::vertex_degree_t, int,
+          boost::property<boost::vertex_in_degree_t, int,
+    boost::property<boost::vertex_out_degree_t, int> > > >
+  > Graph;
+  
+  Graph G(5);
+  boost::add_edge(0, 2, G);
+  boost::add_edge(1, 1, G);
+  boost::add_edge(1, 3, G);
+  boost::add_edge(1, 4, G);
+  boost::add_edge(2, 1, G);
+  boost::add_edge(2, 3, G);
+  boost::add_edge(2, 4, G);
+  boost::add_edge(3, 1, G);
+  boost::add_edge(3, 4, G);
+  boost::add_edge(4, 0, G);
+  boost::add_edge(4, 1, G);
+
+  typedef Graph::vertex_descriptor Vertex;
+
+  Graph G_copy(5);
+  // Array to store predecessor (parent) of each vertex. This will be
+  // used as a Decorator (actually, its iterator will be).
+  std::vector<Vertex> p(boost::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.  
+  boost::graph_traits<Graph>::vertices_size_type d[5];
+  std::fill_n(d, 5, 0);
+
+  // The source vertex
+  Vertex s = *(boost::vertices(G).first);
+  p[s] = s;
+  boost::breadth_first_search
+    (G, s, 
+     boost::visitor(boost::make_bfs_visitor
+     (std::make_pair(boost::record_distances(d, boost::on_tree_edge()),
+                     std::make_pair
+                     (boost::record_predecessors(&p[0], 
+                                                 boost::on_tree_edge()),
+                      copy_graph(G_copy, boost::on_examine_edge())))) ));
+
+  boost::print_graph(G);
+  boost::print_graph(G_copy);
+
+  if (boost::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(boost::vertices(G).first, boost::vertices(G).second, 
+                  print_parent<Piter>(&p[0]));
+  }
+
+  return 0;
+}