ceph/src/boost/libs/graph/doc/eg1-iso.cpp

   1 // Boost.Graph library isomorphism test
   2
   3 // Copyright (C) 2001 Douglas Gregor (gregod@cs.rpi.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 #define BOOST_INCLUDE_MAIN
  19 #include <boost/test/test_tools.hpp>
  20 #include <boost/graph/adjacency_list.hpp>
  21 #include <boost/graph/isomorphism.hpp>
  22 //#include "isomorphism-v3.hpp"
  23 #include <boost/property_map/property_map.hpp>
  24 #include <iostream>
  25 #include <fstream>
  26 #include <map>
  27 #include <algorithm>
  28 #include <cstdlib>
  29 #include <ctime>
  30
  31 using namespace boost;
  32
  33
  34 enum { a, b, c, d, e, f, g, h };
  35 enum { _1, _2, _3, _4, _5, _6, _7, _8 };
  36
  37 void test_isomorphism()
  38 {
  39   typedef adjacency_list<vecS, vecS, bidirectionalS> GraphA;
  40   typedef adjacency_list<vecS, vecS, bidirectionalS> GraphB;
  41
  42   char a_names[] = "abcdefgh";
  43   char b_names[] = "12345678";
  44
  45   GraphA Ga(8);
  46   add_edge(a, d, Ga);
  47   add_edge(a, h, Ga);
  48   add_edge(b, c, Ga);
  49   add_edge(b, e, Ga);
  50   add_edge(c, f, Ga);
  51   add_edge(d, a, Ga);
  52   add_edge(d, h, Ga);
  53   add_edge(e, b, Ga);
  54   add_edge(f, b, Ga);
  55   add_edge(f, e, Ga);
  56   add_edge(g, d, Ga);
  57   add_edge(g, f, Ga);
  58   add_edge(h, c, Ga);
  59   add_edge(h, g, Ga);
  60
  61   GraphB Gb(8);
  62   add_edge(_1, _6, Gb);
  63   add_edge(_2, _1, Gb);
  64   add_edge(_2, _5, Gb);
  65   add_edge(_3, _2, Gb);
  66   add_edge(_3, _4, Gb);
  67   add_edge(_4, _2, Gb);
  68   add_edge(_4, _3, Gb);
  69   add_edge(_5, _4, Gb);
  70   add_edge(_5, _6, Gb);
  71   add_edge(_6, _7, Gb);
  72   add_edge(_6, _8, Gb);
  73   add_edge(_7, _8, Gb);
  74   add_edge(_8, _1, Gb);
  75   add_edge(_8, _7, Gb);
  76
  77
  78   std::vector<std::size_t> in_degree_A(num_vertices(Ga));
  79   boost::detail::compute_in_degree(Ga, &in_degree_A[0]);
  80
  81   std::vector<std::size_t> in_degree_B(num_vertices(Gb));
  82   boost::detail::compute_in_degree(Gb, &in_degree_B[0]);
  83
  84   degree_vertex_invariant<std::size_t*, GraphA>
  85     invariantA(&in_degree_A[0], Ga);
  86   degree_vertex_invariant<std::size_t*, GraphB>
  87     invariantB(&in_degree_B[0], Gb);
  88
  89   std::vector<graph_traits<GraphB>::vertex_descriptor> f(num_vertices(Ga));
  90
  91   bool ret = isomorphism(Ga, Gb, &f[0], invariantA, invariantB,
  92                          (invariantB.max)(),
  93                          get(vertex_index, Ga), get(vertex_index, Gb));
  94   assert(ret == true);
  95
  96   for (std::size_t i = 0; i < num_vertices(Ga); ++i)
  97     std::cout << "f(" << a_names[i] << ")=" << b_names[f[i]] << std::endl;
  98
  99   BOOST_TEST(verify_isomorphism(Ga, Gb, &f[0]));
 100 }
 101
 102 int test_main(int, char* [])
 103 {
 104   test_isomorphism();
 105   return boost::report_errors();
 106 }