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

   1 // Boost.Graph library isomorphism test
   2
   3 // Copyright (C) 2001-20044 Douglas Gregor (dgregor at cs dot indiana dot edu)
   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 // For more information, see http://www.boost.org
  10 //
  11 // Revision History:
  12 //
  13 // 29 Nov 2001    Jeremy Siek
  14 //      Changed to use Boost.Random.
  15 // 29 Nov 2001    Doug Gregor
  16 //      Initial checkin.
  17
  18 #include <iostream>
  19 #include <fstream>
  20 #include <map>
  21 #include <algorithm>
  22 #include <cstdlib>
  23 #include <time.h> // clock used without std:: qualifier?
  24 #include <boost/test/minimal.hpp>
  25 #include <boost/graph/adjacency_list.hpp>
  26 #include <boost/graph/isomorphism.hpp>
  27 #include <boost/property_map/property_map.hpp>
  28 #include <boost/random/variate_generator.hpp>
  29 #include <boost/random/uniform_real.hpp>
  30 #include <boost/random/uniform_int.hpp>
  31 #include <boost/random/mersenne_twister.hpp>
  32 #include <boost/lexical_cast.hpp>
  33
  34 #ifndef BOOST_NO_CXX11_HDR_RANDOM
  35 #include <random>
  36 typedef std::mt19937 random_generator_type;
  37 #else
  38 typedef boost::mt19937 random_generator_type;
  39 #endif
  40
  41 using namespace boost;
  42
  43 #ifndef BOOST_NO_CXX98_RANDOM_SHUFFLE
  44 template <typename Generator>
  45 struct random_functor {
  46   random_functor(Generator& g) : g(g) { }
  47   std::size_t operator()(std::size_t n) {
  48     boost::uniform_int<std::size_t> distrib(0, n-1);
  49     boost::variate_generator<random_generator_type&, boost::uniform_int<std::size_t> >
  50       x(g, distrib);
  51     return x();
  52   }
  53   Generator& g;
  54 };
  55 #endif
  56
  57 template<typename Graph1, typename Graph2>
  58 void randomly_permute_graph(const Graph1& g1, Graph2& g2)
  59 {
  60   // Need a clean graph to start with
  61   BOOST_REQUIRE(num_vertices(g2) == 0);
  62   BOOST_REQUIRE(num_edges(g2) == 0);
  63
  64   typedef typename graph_traits<Graph1>::vertex_descriptor vertex1;
  65   typedef typename graph_traits<Graph2>::vertex_descriptor vertex2;
  66   typedef typename graph_traits<Graph1>::edge_iterator edge_iterator;
  67
  68   random_generator_type gen;
  69
  70 #ifndef BOOST_NO_CXX98_RANDOM_SHUFFLE
  71   random_functor<random_generator_type> rand_fun(gen);
  72 #endif
  73
  74   // Decide new order
  75   std::vector<vertex1> orig_vertices;
  76   std::copy(vertices(g1).first, vertices(g1).second, std::back_inserter(orig_vertices));
  77 #ifndef BOOST_NO_CXX98_RANDOM_SHUFFLE
  78   std::random_shuffle(orig_vertices.begin(), orig_vertices.end(), rand_fun);
  79 #else
  80   std::shuffle(orig_vertices.begin(), orig_vertices.end(), gen);
  81 #endif
  82   std::map<vertex1, vertex2> vertex_map;
  83
  84   for (std::size_t i = 0; i < num_vertices(g1); ++i) {
  85     vertex_map[orig_vertices[i]] = add_vertex(g2);
  86   }
  87
  88   for (edge_iterator e = edges(g1).first; e != edges(g1).second; ++e) {
  89     add_edge(vertex_map[source(*e, g1)], vertex_map[target(*e, g1)], g2);
  90   }
  91 }
  92
  93 template<typename Graph>
  94 void generate_random_digraph(Graph& g, double edge_probability)
  95 {
  96   typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
  97   random_generator_type random_gen;
  98   boost::uniform_real<double> distrib(0.0, 1.0);
  99   boost::variate_generator<random_generator_type&, boost::uniform_real<double> >
 100     random_dist(random_gen, distrib);
 101
 102   for (vertex_iterator u = vertices(g).first; u != vertices(g).second; ++u) {
 103     vertex_iterator v = u;
 104     ++v;
 105     for (; v != vertices(g).second; ++v) {
 106       if (random_dist() <= edge_probability)
 107         add_edge(*u, *v, g);
 108     }
 109   }
 110 }
 111
 112 void test_isomorphism2()
 113 {
 114   using namespace boost::graph::keywords;
 115   typedef adjacency_list<vecS, vecS, bidirectionalS> graph1;
 116   typedef adjacency_list<listS, listS, bidirectionalS,
 117                          property<vertex_index_t, int> > graph2;
 118
 119   graph1 g1(2);
 120   add_edge(vertex(0, g1), vertex(1, g1), g1);
 121   add_edge(vertex(1, g1), vertex(1, g1), g1);
 122   graph2 g2;
 123   randomly_permute_graph(g1, g2);
 124
 125   int v_idx = 0;
 126   for (graph2::vertex_iterator v = vertices(g2).first;
 127        v != vertices(g2).second; ++v) {
 128     put(vertex_index_t(), g2, *v, v_idx++);
 129   }
 130
 131   std::map<graph1::vertex_descriptor, graph2::vertex_descriptor> mapping;
 132
 133   bool isomorphism_correct;
 134   clock_t start = clock();
 135   BOOST_CHECK(isomorphism_correct = boost::graph::isomorphism
 136                (g1, g2, _vertex_index1_map = get(vertex_index, g1),
 137                 _isomorphism_map = make_assoc_property_map(mapping)));
 138   clock_t end = clock();
 139
 140   std::cout << "Elapsed time (clock cycles): " << (end - start) << std::endl;
 141
 142   bool verify_correct;
 143   BOOST_CHECK(verify_correct =
 144              verify_isomorphism(g1, g2, make_assoc_property_map(mapping)));
 145
 146   if (!isomorphism_correct || !verify_correct) {
 147     // Output graph 1
 148     {
 149       std::ofstream out("isomorphism_failure.bg1");
 150       out << num_vertices(g1) << std::endl;
 151       for (graph1::edge_iterator e = edges(g1).first;
 152            e != edges(g1).second; ++e) {
 153         out << get(vertex_index_t(), g1, source(*e, g1)) << ' '
 154             << get(vertex_index_t(), g1, target(*e, g1)) << std::endl;
 155       }
 156     }
 157
 158     // Output graph 2
 159     {
 160       std::ofstream out("isomorphism_failure.bg2");
 161       out << num_vertices(g2) << std::endl;
 162       for (graph2::edge_iterator e = edges(g2).first;
 163            e != edges(g2).second; ++e) {
 164         out << get(vertex_index_t(), g2, source(*e, g2)) << ' '
 165             << get(vertex_index_t(), g2, target(*e, g2)) << std::endl;
 166       }
 167     }
 168   }
 169 }
 170
 171 void test_isomorphism(int n, double edge_probability)
 172 {
 173   using namespace boost::graph::keywords;
 174   typedef adjacency_list<vecS, vecS, bidirectionalS> graph1;
 175   typedef adjacency_list<listS, listS, bidirectionalS,
 176                          property<vertex_index_t, int> > graph2;
 177
 178   graph1 g1(n);
 179   generate_random_digraph(g1, edge_probability);
 180   graph2 g2;
 181   randomly_permute_graph(g1, g2);
 182
 183   int v_idx = 0;
 184   for (graph2::vertex_iterator v = vertices(g2).first;
 185        v != vertices(g2).second; ++v) {
 186     put(vertex_index_t(), g2, *v, v_idx++);
 187   }
 188
 189   std::map<graph1::vertex_descriptor, graph2::vertex_descriptor> mapping;
 190
 191   bool isomorphism_correct;
 192   clock_t start = clock();
 193   BOOST_CHECK(isomorphism_correct = boost::graph::isomorphism
 194                (g1, g2, _isomorphism_map = make_assoc_property_map(mapping)));
 195   clock_t end = clock();
 196
 197   std::cout << "Elapsed time (clock cycles): " << (end - start) << std::endl;
 198
 199   bool verify_correct;
 200   BOOST_CHECK(verify_correct =
 201              verify_isomorphism(g1, g2, make_assoc_property_map(mapping)));
 202
 203   if (!isomorphism_correct || !verify_correct) {
 204     // Output graph 1
 205     {
 206       std::ofstream out("isomorphism_failure.bg1");
 207       out << num_vertices(g1) << std::endl;
 208       for (graph1::edge_iterator e = edges(g1).first;
 209            e != edges(g1).second; ++e) {
 210         out << get(vertex_index_t(), g1, source(*e, g1)) << ' '
 211             << get(vertex_index_t(), g1, target(*e, g1)) << std::endl;
 212       }
 213     }
 214
 215     // Output graph 2
 216     {
 217       std::ofstream out("isomorphism_failure.bg2");
 218       out << num_vertices(g2) << std::endl;
 219       for (graph2::edge_iterator e = edges(g2).first;
 220            e != edges(g2).second; ++e) {
 221         out << get(vertex_index_t(), g2, source(*e, g2)) << ' '
 222             << get(vertex_index_t(), g2, target(*e, g2)) << std::endl;
 223       }
 224     }
 225   }
 226 }
 227
 228 int test_main(int argc, char* argv[])
 229 {
 230   if (argc < 3) {
 231     test_isomorphism(30, 0.45);
 232     return 0;
 233   }
 234
 235   int n = boost::lexical_cast<int>(argv[1]);
 236   double edge_prob = boost::lexical_cast<double>(argv[2]);
 237   test_isomorphism(n, edge_prob);
 238
 239   return 0;
 240 }