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