ceph/src/boost/libs/graph/example/bfs.cpp

   1 //=======================================================================
   2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8 //=======================================================================
   9
  10 #include <boost/config.hpp>
  11
  12 #include <algorithm>
  13 #include <vector>
  14 #include <utility>
  15 #include <iostream>
  16
  17 #include <boost/graph/visitors.hpp>
  18 #include <boost/graph/adjacency_list.hpp>
  19 #include <boost/graph/breadth_first_search.hpp>
  20 #include <boost/property_map/property_map.hpp>
  21 #include <boost/graph/graph_utility.hpp>
  22
  23 /*
  24
  25   This examples shows how to use the breadth_first_search() GGCL
  26   algorithm, specifically the 3 argument variant of bfs that assumes
  27   the graph has a color property (property) stored internally.
  28
  29   Two pre-defined visitors are used to record the distance of each
  30   vertex from the source vertex, and also to record the parent of each
  31   vertex. Any number of visitors can be layered and passed to a GGCL
  32   algorithm.
  33
  34   The call to vertices(G) returns an STL-compatible container which
  35   contains all of the vertices in the graph.  In this example we use
  36   the vertices container in the STL for_each() function.
  37
  38   Sample Output:
  39
  40   0 --> 2
  41   1 --> 1 3 4
  42   2 --> 1 3 4
  43   3 --> 1 4
  44   4 --> 0 1
  45   0 --> 2
  46   1 --> 1 3 4
  47   2 --> 1 3 4
  48   3 --> 1 4
  49   4 --> 0 1
  50   distances: 0 2 1 2 2
  51   parent[0] = 0
  52   parent[1] = 2
  53   parent[2] = 0
  54   parent[3] = 2
  55   parent[4] = 2
  56
  57 */
  58
  59 template <class ParentDecorator>
  60 struct print_parent {
  61   print_parent(const ParentDecorator& p_) : p(p_) { }
  62   template <class Vertex>
  63   void operator()(const Vertex& v) const {
  64     std::cout << "parent[" << v << "] = " <<  p[v]  << std::endl;
  65   }
  66   ParentDecorator p;
  67 };
  68
  69
  70 template <class NewGraph, class Tag>
  71 struct graph_copier
  72   : public boost::base_visitor<graph_copier<NewGraph, Tag> >
  73 {
  74   typedef Tag event_filter;
  75
  76   graph_copier(NewGraph& graph) : new_g(graph) { }
  77
  78   template <class Edge, class Graph>
  79   void operator()(Edge e, Graph& g) {
  80     boost::add_edge(boost::source(e, g), boost::target(e, g), new_g);
  81   }
  82 private:
  83   NewGraph& new_g;
  84 };
  85
  86 template <class NewGraph, class Tag>
  87 inline graph_copier<NewGraph, Tag>
  88 copy_graph(NewGraph& g, Tag) {
  89   return graph_copier<NewGraph, Tag>(g);
  90 }
  91
  92 int main(int , char* [])
  93 {
  94   typedef boost::adjacency_list<
  95     boost::mapS, boost::vecS, boost::bidirectionalS,
  96     boost::property<boost::vertex_color_t, boost::default_color_type,
  97         boost::property<boost::vertex_degree_t, int,
  98           boost::property<boost::vertex_in_degree_t, int,
  99     boost::property<boost::vertex_out_degree_t, int> > > >
 100   > Graph;
 101
 102   Graph G(5);
 103   boost::add_edge(0, 2, G);
 104   boost::add_edge(1, 1, G);
 105   boost::add_edge(1, 3, G);
 106   boost::add_edge(1, 4, G);
 107   boost::add_edge(2, 1, G);
 108   boost::add_edge(2, 3, G);
 109   boost::add_edge(2, 4, G);
 110   boost::add_edge(3, 1, G);
 111   boost::add_edge(3, 4, G);
 112   boost::add_edge(4, 0, G);
 113   boost::add_edge(4, 1, G);
 114
 115   typedef Graph::vertex_descriptor Vertex;
 116
 117   Graph G_copy(5);
 118   // Array to store predecessor (parent) of each vertex. This will be
 119   // used as a Decorator (actually, its iterator will be).
 120   std::vector<Vertex> p(boost::num_vertices(G));
 121   // VC++ version of std::vector has no ::pointer, so
 122   // I use ::value_type* instead.
 123   typedef std::vector<Vertex>::value_type* Piter;
 124
 125   // Array to store distances from the source to each vertex .  We use
 126   // a built-in array here just for variety. This will also be used as
 127   // a Decorator.
 128   boost::graph_traits<Graph>::vertices_size_type d[5];
 129   std::fill_n(d, 5, 0);
 130
 131   // The source vertex
 132   Vertex s = *(boost::vertices(G).first);
 133   p[s] = s;
 134   boost::breadth_first_search
 135     (G, s,
 136      boost::visitor(boost::make_bfs_visitor
 137      (std::make_pair(boost::record_distances(d, boost::on_tree_edge()),
 138                      std::make_pair
 139                      (boost::record_predecessors(&p[0],
 140                                                  boost::on_tree_edge()),
 141                       copy_graph(G_copy, boost::on_examine_edge())))) ));
 142
 143   boost::print_graph(G);
 144   boost::print_graph(G_copy);
 145
 146   if (boost::num_vertices(G) < 11) {
 147     std::cout << "distances: ";
 148 #ifdef BOOST_OLD_STREAM_ITERATORS
 149     std::copy(d, d + 5, std::ostream_iterator<int, char>(std::cout, " "));
 150 #else
 151     std::copy(d, d + 5, std::ostream_iterator<int>(std::cout, " "));
 152 #endif
 153     std::cout << std::endl;
 154
 155     std::for_each(boost::vertices(G).first, boost::vertices(G).second,
 156                   print_parent<Piter>(&p[0]));
 157   }
 158
 159   return 0;
 160 }