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

   1 //=======================================================================
   2 // Copyright 2001 University of Notre Dame.
   3 // Author: Andrew Janiszewski, 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/test/minimal.hpp>
  11 #include <boost/graph/adjacency_list.hpp>
  12 #include <boost/graph/random.hpp>
  13 #include <boost/graph/graph_utility.hpp>
  14 #include <boost/graph/graph_archetypes.hpp>
  15 #include <boost/graph/breadth_first_search.hpp>
  16
  17 #include <boost/random/mersenne_twister.hpp>
  18
  19 #ifdef BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP
  20 using namespace boost;
  21 #endif
  22
  23 template <typename DistanceMap, typename ParentMap,
  24           typename Graph, typename ColorMap>
  25 class bfs_testing_visitor
  26 {
  27   typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
  28   typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;
  29   typedef typename boost::color_traits<
  30     typename boost::property_traits<ColorMap>::value_type
  31   > Color;
  32 public:
  33
  34   bfs_testing_visitor(Vertex s, DistanceMap d, ParentMap p, ColorMap c)
  35     : current_distance(0), distance(d), parent(p), color(c), src(s) { }
  36
  37   void initialize_vertex(const Vertex& u, const Graph& ) const {
  38     BOOST_CHECK(get(color, u) == Color::white());
  39   }
  40   void examine_vertex(const Vertex& u, const Graph& ) const {
  41     current_vertex = u;
  42     // Ensure that the distances monotonically increase.
  43     BOOST_CHECK( distance[u] == current_distance
  44                        || distance[u] == current_distance + 1 );
  45     if (distance[u] == current_distance + 1) // new level
  46       ++current_distance;
  47   }
  48   void discover_vertex(const Vertex& u, const Graph& ) const {
  49     BOOST_CHECK( get(color, u) == Color::gray() );
  50     if (u == src) {
  51       current_vertex = src;
  52     } else {
  53       BOOST_CHECK( parent[u] == current_vertex );
  54       BOOST_CHECK( distance[u] == current_distance + 1 );
  55       BOOST_CHECK( distance[u] == distance[parent[u]] + 1 );
  56     }
  57   }
  58   void examine_edge(const Edge& e, const Graph& g) const {
  59     BOOST_CHECK( source(e, g) == current_vertex );
  60   }
  61   void tree_edge(const Edge& e, const Graph& g) const {
  62     BOOST_CHECK( get(color, target(e, g)) == Color::white() );
  63     Vertex u = source(e, g), v = target(e, g);
  64     BOOST_CHECK( distance[u] == current_distance );
  65     parent[v] = u;
  66     distance[v] = distance[u] + 1;
  67   }
  68   void non_tree_edge(const Edge& e, const Graph& g) const {
  69     BOOST_CHECK( color[target(e, g)] != Color::white() );
  70
  71     if (boost::is_directed(g))
  72       // cross or back edge
  73       BOOST_CHECK(distance[target(e, g)] <= distance[source(e, g)] + 1);
  74     else {
  75       // cross edge (or going backwards on a tree edge)
  76       BOOST_CHECK(distance[target(e, g)] == distance[source(e, g)]
  77                         || distance[target(e, g)] == distance[source(e, g)] + 1
  78                         || distance[target(e, g)] == distance[source(e, g)] - 1
  79                         );
  80     }
  81   }
  82
  83   void gray_target(const Edge& e, const Graph& g) const {
  84     BOOST_CHECK( color[target(e, g)] == Color::gray() );
  85   }
  86
  87   void black_target(const Edge& e, const Graph& g) const {
  88     BOOST_CHECK( color[target(e, g)] == Color::black() );
  89
  90     // All vertices adjacent to a black vertex must already be discovered
  91     typename boost::graph_traits<Graph>::adjacency_iterator ai, ai_end;
  92     for (boost::tie(ai, ai_end) = adjacent_vertices(target(e, g), g);
  93          ai != ai_end; ++ai)
  94       BOOST_CHECK( color[*ai] != Color::white() );
  95   }
  96   void finish_vertex(const Vertex& u, const Graph& ) const {
  97     BOOST_CHECK( color[u] == Color::black() );
  98
  99   }
 100 private:
 101   mutable Vertex current_vertex;
 102   mutable typename boost::property_traits<DistanceMap>::value_type
 103     current_distance;
 104   DistanceMap distance;
 105   ParentMap parent;
 106   ColorMap color;
 107   Vertex src;
 108 };
 109
 110
 111 template <class Graph>
 112 struct bfs_test
 113 {
 114   typedef boost::graph_traits<Graph> Traits;
 115   typedef typename Traits::vertices_size_type
 116     vertices_size_type;
 117   static void go(vertices_size_type max_V) {
 118     typedef typename Traits::vertex_descriptor vertex_descriptor;
 119     typedef boost::color_traits<boost::default_color_type> Color;
 120
 121     vertices_size_type i;
 122     typename Traits::edges_size_type j;
 123     typename Traits::vertex_iterator ui, ui_end;
 124
 125     boost::mt19937 gen;
 126
 127     for (i = 0; i < max_V; ++i)
 128       for (j = 0; j < i*i; ++j) {
 129         Graph g;
 130         boost::generate_random_graph(g, i, j, gen);
 131
 132         // declare the "start" variable
 133         vertex_descriptor start = boost::random_vertex(g, gen);
 134
 135         // vertex properties
 136         std::vector<int> distance(i, (std::numeric_limits<int>::max)());
 137         distance[start] = 0;
 138         std::vector<vertex_descriptor> parent(i);
 139         for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
 140           parent[*ui] = *ui;
 141         std::vector<boost::default_color_type> color(i);
 142
 143         // Get vertex index map
 144         typedef typename boost::property_map<Graph, boost::vertex_index_t>::const_type idx_type;
 145         idx_type idx = get(boost::vertex_index, g);
 146
 147         // Make property maps from vectors
 148         typedef
 149           boost::iterator_property_map<std::vector<int>::iterator, idx_type>
 150           distance_pm_type;
 151         distance_pm_type distance_pm(distance.begin(), idx);
 152         typedef
 153           boost::iterator_property_map<typename std::vector<vertex_descriptor>::iterator, idx_type>
 154           parent_pm_type;
 155         parent_pm_type parent_pm(parent.begin(), idx);
 156         typedef
 157           boost::iterator_property_map<std::vector<boost::default_color_type>::iterator, idx_type>
 158           color_pm_type;
 159         color_pm_type color_pm(color.begin(), idx);
 160
 161         // Create the testing visitor.
 162         bfs_testing_visitor<distance_pm_type, parent_pm_type, Graph,
 163           color_pm_type>
 164           vis(start, distance_pm, parent_pm, color_pm);
 165
 166         boost::breadth_first_search(g, start,
 167                                     visitor(vis).
 168                                     color_map(color_pm));
 169
 170         // All white vertices should be unreachable from the source.
 171         for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
 172           if (color[*ui] == Color::white()) {
 173             std::vector<boost::default_color_type> color2(i, Color::white());
 174             BOOST_CHECK(!boost::is_reachable(start, *ui, g, color_pm_type(color2.begin(), idx)));
 175           }
 176
 177         // The shortest path to a child should be one longer than
 178         // shortest path to the parent.
 179         for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
 180           if (parent[*ui] != *ui) // *ui not the root of the bfs tree
 181             BOOST_CHECK(distance[*ui] == distance[parent[*ui]] + 1);
 182       }
 183   }
 184 };
 185
 186
 187 int test_main(int argc, char* argv[])
 188 {
 189   using namespace boost;
 190   int max_V = 7;
 191   if (argc > 1)
 192     max_V = atoi(argv[1]);
 193
 194   bfs_test< adjacency_list<vecS, vecS, directedS> >::go(max_V);
 195   bfs_test< adjacency_list<vecS, vecS, undirectedS> >::go(max_V);
 196   return 0;
 197 }