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 enum
34 {
35 a,
36 b,
37 c,
38 d,
39 e,
40 f,
41 g,
42 h
43 };
44 enum
45 {
46 _1,
47 _2,
48 _3,
49 _4,
50 _5,
51 _6,
52 _7,
53 _8
54 };
55
test_isomorphism()56 void test_isomorphism()
57 {
58 typedef adjacency_list< vecS, vecS, bidirectionalS > GraphA;
59 typedef adjacency_list< vecS, vecS, bidirectionalS > GraphB;
60
61 char a_names[] = "abcdefgh";
62 char b_names[] = "12345678";
63
64 GraphA Ga(8);
65 add_edge(a, d, Ga);
66 add_edge(a, h, Ga);
67 add_edge(b, c, Ga);
68 add_edge(b, e, Ga);
69 add_edge(c, f, Ga);
70 add_edge(d, a, Ga);
71 add_edge(d, h, Ga);
72 add_edge(e, b, Ga);
73 add_edge(f, b, Ga);
74 add_edge(f, e, Ga);
75 add_edge(g, d, Ga);
76 add_edge(g, f, Ga);
77 add_edge(h, c, Ga);
78 add_edge(h, g, Ga);
79
80 GraphB Gb(8);
81 add_edge(_1, _6, Gb);
82 add_edge(_2, _1, Gb);
83 add_edge(_2, _5, Gb);
84 add_edge(_3, _2, Gb);
85 add_edge(_3, _4, Gb);
86 add_edge(_4, _2, Gb);
87 add_edge(_4, _3, Gb);
88 add_edge(_5, _4, Gb);
89 add_edge(_5, _6, Gb);
90 add_edge(_6, _7, Gb);
91 add_edge(_6, _8, Gb);
92 add_edge(_7, _8, Gb);
93 add_edge(_8, _1, Gb);
94 add_edge(_8, _7, Gb);
95
96 std::vector< std::size_t > in_degree_A(num_vertices(Ga));
97 boost::detail::compute_in_degree(Ga, &in_degree_A[0]);
98
99 std::vector< std::size_t > in_degree_B(num_vertices(Gb));
100 boost::detail::compute_in_degree(Gb, &in_degree_B[0]);
101
102 degree_vertex_invariant< std::size_t*, GraphA > invariantA(
103 &in_degree_A[0], Ga);
104 degree_vertex_invariant< std::size_t*, GraphB > invariantB(
105 &in_degree_B[0], Gb);
106
107 std::vector< graph_traits< GraphB >::vertex_descriptor > f(
108 num_vertices(Ga));
109
110 bool ret = isomorphism(Ga, Gb, &f[0], invariantA, invariantB,
111 (invariantB.max)(), get(vertex_index, Ga), get(vertex_index, Gb));
112 assert(ret == true);
113
114 for (std::size_t i = 0; i < num_vertices(Ga); ++i)
115 std::cout << "f(" << a_names[i] << ")=" << b_names[f[i]] << std::endl;
116
117 BOOST_TEST(verify_isomorphism(Ga, Gb, &f[0]));
118 }
119
test_main(int,char * [])120 int test_main(int, char*[])
121 {
122 test_isomorphism();
123 return boost::report_errors();
124 }
125