Adding upstream version 14.2.21.upstream/14.2.21upstream

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

1 files changed, 249 insertions, 0 deletions

diff --git a/src/boost/libs/graph/example/dave.cpp b/src/boost/libs/graph/example/dave.cpp
new file mode 100644
index 00000000..04c69f88
--- /dev/null
+++ b/src/boost/libs/graph/example/dave.cpp
@@ -0,0 +1,249 @@
+//=======================================================================
+// 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 <iostream>
+#include <iterator>
+#include <vector>
+#include <list>
+// Use boost::queue instead of std::queue because std::queue doesn't
+// model Buffer; it has to top() function. -Jeremy
+#include <boost/pending/queue.hpp>
+
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/visitors.hpp>
+#include <boost/graph/breadth_first_search.hpp>
+#include <boost/graph/dijkstra_shortest_paths.hpp>
+#include <boost/graph/graph_utility.hpp>
+
+using namespace std;
+using namespace boost;
+/*
+  This example does a best-first-search (using dijkstra's) and
+  simultaneously makes a copy of the graph (assuming the graph is
+  connected).
+
+  Example Graph: (p. 90 "Data Structures and Network Algorithms", Tarjan)
+
+              g
+            3+ +2
+            / 1 \
+           e+----f
+           |+0 5++
+           | \ / |
+         10|  d  |12
+           |8++\7|
+           +/ | +|
+           b 4|  c
+            \ | +
+            6+|/3
+              a
+
+  Sample Output:
+a --> c d 
+b --> a d
+c --> f
+d --> c e f
+e --> b g
+f --> e g
+g -->
+Starting graph:
+a(32767); c d
+c(32767); f
+d(32767); c e f
+f(32767); e g
+e(32767); b g
+g(32767);
+b(32767); a d
+Result:
+a(0); d c
+d(4); f e c
+c(3); f
+f(9); g e
+e(4); g b
+g(7);
+b(14); d a 
+
+*/
+
+typedef property<vertex_color_t, default_color_type, 
+         property<vertex_distance_t,int> > VProperty;
+typedef int weight_t;
+typedef property<edge_weight_t,weight_t> EProperty;
+
+typedef adjacency_list<vecS, vecS, directedS, VProperty, EProperty > Graph;
+
+
+
+template <class Tag>
+struct endl_printer
+  : public boost::base_visitor< endl_printer<Tag> >
+{
+  typedef Tag event_filter;
+  endl_printer(std::ostream& os) : m_os(os) { }
+  template <class T, class Graph>
+  void operator()(T, Graph&) { m_os << std::endl; }
+  std::ostream& m_os;
+};
+template <class Tag>
+endl_printer<Tag> print_endl(std::ostream& os, Tag) {
+  return endl_printer<Tag>(os);
+}
+
+template <class PA, class Tag>
+struct edge_printer
+ : public boost::base_visitor< edge_printer<PA, Tag> >
+{
+  typedef Tag event_filter;
+
+  edge_printer(PA pa, std::ostream& os) : m_pa(pa), m_os(os) { }
+
+  template <class T, class Graph>
+  void operator()(T x, Graph& g) {
+    m_os << "(" << get(m_pa, source(x, g)) << "," 
+         << get(m_pa, target(x, g)) << ") ";
+  }
+  PA m_pa;
+  std::ostream& m_os;
+};
+template <class PA, class Tag>
+edge_printer<PA, Tag>
+print_edge(PA pa, std::ostream& os, Tag) {
+  return edge_printer<PA, Tag>(pa, os);
+}
+
+
+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) {
+    add_edge(source(e, g), 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);
+}
+
+template <class Graph, class Name>
+void print(Graph& G, Name name)
+{
+  typename boost::graph_traits<Graph>::vertex_iterator ui, uiend;
+  for (boost::tie(ui, uiend) = vertices(G); ui != uiend; ++ui) {
+    cout << name[*ui] << " --> ";
+    typename boost::graph_traits<Graph>::adjacency_iterator vi, viend;
+    for(boost::tie(vi, viend) = adjacent_vertices(*ui, G); vi != viend; ++vi)
+      cout << name[*vi] << " ";
+    cout << endl;
+  }
+    
+}
+
+
+int 
+main(int , char* [])
+{
+  // Name and ID numbers for the vertices
+  char name[] = "abcdefg";
+  enum { a, b, c, d, e, f, g, N};
+
+  Graph G(N);
+  boost::property_map<Graph, vertex_index_t>::type 
+    vertex_id = get(vertex_index, G);
+
+  std::vector<weight_t> distance(N, (numeric_limits<weight_t>::max)());
+  typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
+  std::vector<Vertex> parent(N);
+
+  typedef std::pair<int,int> E;
+
+  E edges[] = { E(a,c), E(a,d),
+                E(b,a), E(b,d),
+                E(c,f),
+                E(d,c), E(d,e), E(d,f),
+                E(e,b), E(e,g),
+                E(f,e), E(f,g) };
+
+  int weight[] = { 3, 4,
+                   6, 8,
+                   12,
+                   7, 0, 5,
+                   10, 3,
+                   1, 2 };
+
+  for (int i = 0; i < 12; ++i)
+    add_edge(edges[i].first, edges[i].second, weight[i], G);
+
+  print(G, name);
+
+  adjacency_list<listS, vecS, directedS, 
+    property<vertex_color_t, default_color_type> > G_copy(N);
+
+  cout << "Starting graph:" << endl;
+
+  std::ostream_iterator<int> cout_int(std::cout, " ");
+  std::ostream_iterator<char> cout_char(std::cout, " ");
+
+  boost::queue<Vertex> Q;
+  boost::breadth_first_search
+    (G, vertex(a, G), Q,
+     make_bfs_visitor(
+     boost::make_list
+      (write_property(make_iterator_property_map(name, vertex_id,
+                                                name[0]),
+                      cout_char, on_examine_vertex()),
+       write_property(make_iterator_property_map(distance.begin(),
+                                                vertex_id, 
+                                                distance[0]), 
+                      cout_int, on_examine_vertex()),
+       print_edge(make_iterator_property_map(name, vertex_id, 
+                                            name[0]),
+                  std::cout, on_examine_edge()),
+       print_endl(std::cout, on_finish_vertex()))),
+     get(vertex_color, G));
+
+  std::cout << "about to call dijkstra's" << std::endl;
+
+  parent[vertex(a, G)] = vertex(a, G);
+  boost::dijkstra_shortest_paths
+    (G, vertex(a, G), 
+     distance_map(make_iterator_property_map(distance.begin(), vertex_id, 
+                                             distance[0])).
+     predecessor_map(make_iterator_property_map(parent.begin(), vertex_id,
+                                                parent[0])).
+     visitor(make_dijkstra_visitor(copy_graph(G_copy, on_examine_edge()))));
+
+  cout << endl;
+  cout << "Result:" << endl;
+  boost::breadth_first_search
+    (G, vertex(a, G), 
+     visitor(make_bfs_visitor(
+     boost::make_list
+     (write_property(make_iterator_property_map(name, vertex_id,
+                                                name[0]),
+                     cout_char, on_examine_vertex()),
+      write_property(make_iterator_property_map(distance.begin(),
+                                                vertex_id, 
+                                                distance[0]), 
+                     cout_int, on_examine_vertex()),
+      print_edge(make_iterator_property_map(name, vertex_id, 
+                                            name[0]),
+                 std::cout, on_examine_edge()),
+      print_endl(std::cout, on_finish_vertex())))));
+
+  return 0;
+}