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

   1 // Copyright (C) 2001 Vladimir Prus <ghost@cs.msu.su>
   2 // Copyright (C) 2001 Jeremy Siek <jsiek@cs.indiana.edu>
   3 // Distributed under the Boost Software License, Version 1.0. (See
   4 // accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 #include <iostream>
   8 #include <cstdlib>
   9 #include <ctime>
  10
  11 #include <boost/graph/vector_as_graph.hpp>
  12 #include <boost/graph/adjacency_list.hpp>
  13 #include <boost/graph/adjacency_list_io.hpp>
  14 #include <boost/graph/graph_utility.hpp>
  15 #include <boost/graph/transitive_closure.hpp>
  16 #include <boost/progress.hpp>
  17
  18 using namespace std;
  19 using namespace boost;
  20
  21 void generate_graph(int n, double p, vector< vector<int> >& r1)
  22 {
  23   static class {
  24   public:
  25     double operator()() {
  26       return double(rand())/RAND_MAX;
  27     }
  28   } gen;
  29   r1.clear();
  30   r1.resize(n);
  31   for (int i = 0; i < n; ++i)
  32     for (int j = 0; j < n; ++j)
  33       if (gen() < p)
  34         r1[i].push_back(j);
  35 }
  36
  37 template <class Graph>
  38 typename graph_traits<Graph>::degree_size_type
  39 num_incident(typename graph_traits<Graph>::vertex_descriptor u,
  40              typename graph_traits<Graph>::vertex_descriptor v,
  41              const Graph& g)
  42 {
  43   typename graph_traits<Graph>::degree_size_type d = 0;
  44   typename graph_traits<Graph>::out_edge_iterator i, i_end;
  45   for (boost::tie(i, i_end) = out_edges(u, g); i != i_end; ++i)
  46     if (target(*i, g) == v)
  47       ++d;
  48   return d;
  49 }
  50
  51
  52 // (i,j) is in E' iff j is reachable from i
  53 // Hmm, is_reachable does not detect when there is a non-trivial path
  54 // from i to i. It always returns true for is_reachable(i,i).
  55 // This needs to be fixed/worked around.
  56 template <typename Graph, typename GraphTC>
  57 bool check_transitive_closure(Graph& g, GraphTC& tc)
  58 {
  59   typename graph_traits<Graph>::vertex_iterator i, i_end;
  60   for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i) {
  61     typename graph_traits<Graph>::vertex_iterator j, j_end;
  62     for (boost::tie(j, j_end) = vertices(g); j != j_end; ++j) {
  63       bool g_has_edge;
  64       typename graph_traits<Graph>::edge_descriptor e_g;
  65       typename graph_traits<Graph>::degree_size_type num_tc;
  66       boost::tie (e_g, g_has_edge) = edge(*i, *j, g);
  67       num_tc = num_incident(*i, *j, tc);
  68       if (*i == *j) {
  69         if (g_has_edge) {
  70           if (num_tc != 1)
  71             return false;
  72         } else {
  73           bool can_reach = false;
  74           typename graph_traits<Graph>::adjacency_iterator k, k_end;
  75           for (boost::tie(k, k_end) = adjacent_vertices(*i, g); k != k_end; ++k) {
  76             std::vector<default_color_type> color_map_vec(num_vertices(g));
  77             if (is_reachable(*k, *i, g, boost::make_iterator_property_map(color_map_vec.begin(), get(boost::vertex_index, g)))) {
  78               can_reach = true;
  79               break;
  80             }
  81           }
  82           if (can_reach) {
  83             if (num_tc != 1) {
  84               std::cout << "1. " << *i << std::endl;
  85               return false;
  86             }
  87           } else {
  88             if (num_tc != 0) {
  89               std::cout << "2. " << *i << std::endl;
  90               return false;
  91             }
  92           }
  93         }
  94       } else {
  95         std::vector<default_color_type> color_map_vec(num_vertices(g));
  96         if (is_reachable(*i, *j, g, boost::make_iterator_property_map(color_map_vec.begin(), get(boost::vertex_index, g)))) {
  97           if (num_tc != 1)
  98             return false;
  99         } else {
 100           if (num_tc != 0)
 101             return false;
 102         }
 103       }
 104     }
 105   }
 106   return true;
 107 }
 108
 109 bool test(int n, double p)
 110 {
 111   vector< vector<int> > g1, g1_tc;
 112   generate_graph(n, p, g1);
 113   cout << "Created graph with " << n << " vertices.\n";
 114
 115   vector< vector<int> > g1_c(g1);
 116
 117   {
 118     progress_timer t;
 119     cout << "transitive_closure" << endl;
 120     transitive_closure(g1, g1_tc, vertex_index_map(get(boost::vertex_index, g1)));
 121   }
 122
 123   if(check_transitive_closure(g1, g1_tc))
 124     return true;
 125   else {
 126     cout << "Original graph was ";
 127     print_graph(g1, get(boost::vertex_index, g1));
 128     cout << "Result is ";
 129     print_graph(g1_tc, get(boost::vertex_index, g1_tc));
 130     return false;
 131   }
 132 }
 133
 134
 135 int main()
 136 {
 137   srand(time(0));
 138   static class {
 139   public:
 140     double operator()() {
 141       return double(rand())/RAND_MAX;
 142     }
 143   } gen;
 144
 145
 146   for (size_t i = 0; i < 100; ++i) {
 147     int n = 0 + int(20*gen());
 148     double p = gen();
 149     if (!test(n, p)) {
 150       cout << "Failed." << endl;
 151       return 1;
 152     }
 153   }
 154   cout << "Passed." << endl;
 155 }
 156