ceph/src/boost/libs/graph/example/neighbor_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/graph_utility.hpp>
  20 #include <boost/graph/neighbor_bfs.hpp>
  21 #include <boost/property_map/property_map.hpp>
  22
  23 /*
  24
  25   Sample Output:
  26
  27   0 --> 2
  28   1 --> 1 3 4
  29   2 --> 1 3 4
  30   3 --> 1 4
  31   4 --> 0 1
  32   distances: 0 2 1 2 1
  33   parent[0] = 0
  34   parent[1] = 2
  35   parent[2] = 0
  36   parent[3] = 2
  37   parent[4] = 0
  38
  39 */
  40
  41 using namespace boost;
  42
  43 template < class ParentDecorator > struct print_parent
  44 {
  45     print_parent(const ParentDecorator& p_) : p(p_) {}
  46     template < class Vertex > void operator()(const Vertex& v) const
  47     {
  48         std::cout << "parent[" << v << "] = " << p[v] << std::endl;
  49     }
  50     ParentDecorator p;
  51 };
  52
  53 template < class DistanceMap, class PredecessorMap, class ColorMap >
  54 class distance_and_pred_visitor : public neighbor_bfs_visitor<>
  55 {
  56     typedef typename property_traits< ColorMap >::value_type ColorValue;
  57     typedef color_traits< ColorValue > Color;
  58
  59 public:
  60     distance_and_pred_visitor(DistanceMap d, PredecessorMap p, ColorMap c)
  61     : m_distance(d), m_predecessor(p), m_color(c)
  62     {
  63     }
  64
  65     template < class Edge, class Graph >
  66     void tree_out_edge(Edge e, const Graph& g) const
  67     {
  68         typename graph_traits< Graph >::vertex_descriptor u = source(e, g),
  69                                                           v = target(e, g);
  70         put(m_distance, v, get(m_distance, u) + 1);
  71         put(m_predecessor, v, u);
  72     }
  73     template < class Edge, class Graph >
  74     void tree_in_edge(Edge e, const Graph& g) const
  75     {
  76         typename graph_traits< Graph >::vertex_descriptor u = source(e, g),
  77                                                           v = target(e, g);
  78         put(m_distance, u, get(m_distance, v) + 1);
  79         put(m_predecessor, u, v);
  80     }
  81
  82     DistanceMap m_distance;
  83     PredecessorMap m_predecessor;
  84     ColorMap m_color;
  85 };
  86
  87 int main(int, char*[])
  88 {
  89     typedef adjacency_list< mapS, vecS, bidirectionalS,
  90         property< vertex_color_t, default_color_type > >
  91         Graph;
  92
  93     typedef property_map< Graph, vertex_color_t >::type ColorMap;
  94
  95     Graph G(5);
  96     add_edge(0, 2, G);
  97     add_edge(1, 1, G);
  98     add_edge(1, 3, G);
  99     add_edge(1, 4, G);
 100     add_edge(2, 1, G);
 101     add_edge(2, 3, G);
 102     add_edge(2, 4, G);
 103     add_edge(3, 1, G);
 104     add_edge(3, 4, G);
 105     add_edge(4, 0, G);
 106     add_edge(4, 1, G);
 107
 108     typedef Graph::vertex_descriptor Vertex;
 109
 110     // Array to store predecessor (parent) of each vertex. This will be
 111     // used as a Decorator (actually, its iterator will be).
 112     std::vector< Vertex > p(num_vertices(G));
 113     // VC++ version of std::vector has no ::pointer, so
 114     // I use ::value_type* instead.
 115     typedef std::vector< Vertex >::value_type* Piter;
 116
 117     // Array to store distances from the source to each vertex .  We use
 118     // a built-in array here just for variety. This will also be used as
 119     // a Decorator.
 120     typedef graph_traits< Graph >::vertices_size_type size_type;
 121     size_type d[5];
 122     std::fill_n(d, 5, 0);
 123
 124     // The source vertex
 125     Vertex s = *(vertices(G).first);
 126     p[s] = s;
 127     distance_and_pred_visitor< size_type*, Vertex*, ColorMap > vis(
 128         d, &p[0], get(vertex_color, G));
 129     neighbor_breadth_first_search(
 130         G, s, visitor(vis).color_map(get(vertex_color, G)));
 131
 132     print_graph(G);
 133
 134     if (num_vertices(G) < 11)
 135     {
 136         std::cout << "distances: ";
 137 #ifdef BOOST_OLD_STREAM_ITERATORS
 138         std::copy(d, d + 5, std::ostream_iterator< int, char >(std::cout, " "));
 139 #else
 140         std::copy(d, d + 5, std::ostream_iterator< int >(std::cout, " "));
 141 #endif
 142         std::cout << std::endl;
 143
 144         std::for_each(vertices(G).first, vertices(G).second,
 145             print_parent< Piter >(&p[0]));
 146     }
 147
 148     return 0;
 149 }