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 using namespace boost;
35
36 template <typename Generator>
37 struct random_functor {
random_functorrandom_functor38 random_functor(Generator& g) : g(g) { }
operator ()random_functor39 std::size_t operator()(std::size_t n) {
40 boost::uniform_int<std::size_t> distrib(0, n-1);
41 boost::variate_generator<boost::mt19937&, boost::uniform_int<std::size_t> >
42 x(g, distrib);
43 return x();
44 }
45 Generator& g;
46 };
47
48 template<typename Graph1, typename Graph2>
randomly_permute_graph(const Graph1 & g1,Graph2 & g2)49 void randomly_permute_graph(const Graph1& g1, Graph2& g2)
50 {
51 // Need a clean graph to start with
52 BOOST_REQUIRE(num_vertices(g2) == 0);
53 BOOST_REQUIRE(num_edges(g2) == 0);
54
55 typedef typename graph_traits<Graph1>::vertex_descriptor vertex1;
56 typedef typename graph_traits<Graph2>::vertex_descriptor vertex2;
57 typedef typename graph_traits<Graph1>::edge_iterator edge_iterator;
58
59 boost::mt19937 gen;
60 random_functor<boost::mt19937> rand_fun(gen);
61
62 // Decide new order
63 std::vector<vertex1> orig_vertices;
64 std::copy(vertices(g1).first, vertices(g1).second, std::back_inserter(orig_vertices));
65 std::random_shuffle(orig_vertices.begin(), orig_vertices.end(), rand_fun);
66 std::map<vertex1, vertex2> vertex_map;
67
68 for (std::size_t i = 0; i < num_vertices(g1); ++i) {
69 vertex_map[orig_vertices[i]] = add_vertex(g2);
70 }
71
72 for (edge_iterator e = edges(g1).first; e != edges(g1).second; ++e) {
73 add_edge(vertex_map[source(*e, g1)], vertex_map[target(*e, g1)], g2);
74 }
75 }
76
77 template<typename Graph>
generate_random_digraph(Graph & g,double edge_probability)78 void generate_random_digraph(Graph& g, double edge_probability)
79 {
80 typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
81 boost::mt19937 random_gen;
82 boost::uniform_real<double> distrib(0.0, 1.0);
83 boost::variate_generator<boost::mt19937&, boost::uniform_real<double> >
84 random_dist(random_gen, distrib);
85
86 for (vertex_iterator u = vertices(g).first; u != vertices(g).second; ++u) {
87 vertex_iterator v = u;
88 ++v;
89 for (; v != vertices(g).second; ++v) {
90 if (random_dist() <= edge_probability)
91 add_edge(*u, *v, g);
92 }
93 }
94 }
95
test_isomorphism2()96 void test_isomorphism2()
97 {
98 using namespace boost::graph::keywords;
99 typedef adjacency_list<vecS, vecS, bidirectionalS> graph1;
100 typedef adjacency_list<listS, listS, bidirectionalS,
101 property<vertex_index_t, int> > graph2;
102
103 graph1 g1(2);
104 add_edge(vertex(0, g1), vertex(1, g1), g1);
105 add_edge(vertex(1, g1), vertex(1, g1), g1);
106 graph2 g2;
107 randomly_permute_graph(g1, g2);
108
109 int v_idx = 0;
110 for (graph2::vertex_iterator v = vertices(g2).first;
111 v != vertices(g2).second; ++v) {
112 put(vertex_index_t(), g2, *v, v_idx++);
113 }
114
115 std::map<graph1::vertex_descriptor, graph2::vertex_descriptor> mapping;
116
117 bool isomorphism_correct;
118 clock_t start = clock();
119 BOOST_CHECK(isomorphism_correct = boost::graph::isomorphism
120 (g1, g2, _isomorphism_map = make_assoc_property_map(mapping)));
121 clock_t end = clock();
122
123 std::cout << "Elapsed time (clock cycles): " << (end - start) << std::endl;
124
125 bool verify_correct;
126 BOOST_CHECK(verify_correct =
127 verify_isomorphism(g1, g2, make_assoc_property_map(mapping)));
128
129 if (!isomorphism_correct || !verify_correct) {
130 // Output graph 1
131 {
132 std::ofstream out("isomorphism_failure.bg1");
133 out << num_vertices(g1) << std::endl;
134 for (graph1::edge_iterator e = edges(g1).first;
135 e != edges(g1).second; ++e) {
136 out << get(vertex_index_t(), g1, source(*e, g1)) << ' '
137 << get(vertex_index_t(), g1, target(*e, g1)) << std::endl;
138 }
139 }
140
141 // Output graph 2
142 {
143 std::ofstream out("isomorphism_failure.bg2");
144 out << num_vertices(g2) << std::endl;
145 for (graph2::edge_iterator e = edges(g2).first;
146 e != edges(g2).second; ++e) {
147 out << get(vertex_index_t(), g2, source(*e, g2)) << ' '
148 << get(vertex_index_t(), g2, target(*e, g2)) << std::endl;
149 }
150 }
151 }
152 }
153
test_isomorphism(int n,double edge_probability)154 void test_isomorphism(int n, double edge_probability)
155 {
156 using namespace boost::graph::keywords;
157 typedef adjacency_list<vecS, vecS, bidirectionalS> graph1;
158 typedef adjacency_list<listS, listS, bidirectionalS,
159 property<vertex_index_t, int> > graph2;
160
161 graph1 g1(n);
162 generate_random_digraph(g1, edge_probability);
163 graph2 g2;
164 randomly_permute_graph(g1, g2);
165
166 int v_idx = 0;
167 for (graph2::vertex_iterator v = vertices(g2).first;
168 v != vertices(g2).second; ++v) {
169 put(vertex_index_t(), g2, *v, v_idx++);
170 }
171
172 std::map<graph1::vertex_descriptor, graph2::vertex_descriptor> mapping;
173
174 bool isomorphism_correct;
175 clock_t start = clock();
176 BOOST_CHECK(isomorphism_correct = boost::graph::isomorphism
177 (g1, g2, _isomorphism_map = make_assoc_property_map(mapping)));
178 clock_t end = clock();
179
180 std::cout << "Elapsed time (clock cycles): " << (end - start) << std::endl;
181
182 bool verify_correct;
183 BOOST_CHECK(verify_correct =
184 verify_isomorphism(g1, g2, make_assoc_property_map(mapping)));
185
186 if (!isomorphism_correct || !verify_correct) {
187 // Output graph 1
188 {
189 std::ofstream out("isomorphism_failure.bg1");
190 out << num_vertices(g1) << std::endl;
191 for (graph1::edge_iterator e = edges(g1).first;
192 e != edges(g1).second; ++e) {
193 out << get(vertex_index_t(), g1, source(*e, g1)) << ' '
194 << get(vertex_index_t(), g1, target(*e, g1)) << std::endl;
195 }
196 }
197
198 // Output graph 2
199 {
200 std::ofstream out("isomorphism_failure.bg2");
201 out << num_vertices(g2) << std::endl;
202 for (graph2::edge_iterator e = edges(g2).first;
203 e != edges(g2).second; ++e) {
204 out << get(vertex_index_t(), g2, source(*e, g2)) << ' '
205 << get(vertex_index_t(), g2, target(*e, g2)) << std::endl;
206 }
207 }
208 }
209 }
210
test_main(int argc,char * argv[])211 int test_main(int argc, char* argv[])
212 {
213 if (argc < 3) {
214 test_isomorphism(30, 0.45);
215 return 0;
216 }
217
218 int n = boost::lexical_cast<int>(argv[1]);
219 double edge_prob = boost::lexical_cast<double>(argv[2]);
220 test_isomorphism(n, edge_prob);
221
222 return 0;
223 }
224