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 | { |
46 | random_functor(Generator& g) : g(g) {} |
47 | 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 > |
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 > |
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 | |
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(u: vertex(n: 0, g1), v: vertex(n: 1, g1), g_&: g1); |
130 | add_edge(u: vertex(n: 1, g1), v: vertex(n: 1, g1), g_&: g1); |
131 | graph2 g2; |
132 | randomly_permute_graph(g1, g2); |
133 | |
134 | int v_idx = 0; |
135 | for (graph2::vertex_iterator v = vertices(g_: g2).first; |
136 | v != vertices(g_: g2).second; ++v) |
137 | { |
138 | put(p: vertex_index_t(), g&: g2, key: *v, value: 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(g_: g1) << std::endl; |
162 | for (graph1::edge_iterator e = edges(g_: g1).first; |
163 | e != edges(g_: g1).second; ++e) |
164 | { |
165 | out << get(p: vertex_index_t(), g&: g1, key: source(e: *e, g1)) << ' ' |
166 | << get(p: vertex_index_t(), g&: g1, key: target(e: *e, g1)) << std::endl; |
167 | } |
168 | } |
169 | |
170 | // Output graph 2 |
171 | { |
172 | std::ofstream out("isomorphism_failure.bg2" ); |
173 | out << num_vertices(g_: g2) << std::endl; |
174 | for (graph2::edge_iterator e = edges(g_: g2).first; |
175 | e != edges(g_: g2).second; ++e) |
176 | { |
177 | out << get(p: vertex_index_t(), g&: g2, key: source(e: *e, g2)) << ' ' |
178 | << get(p: vertex_index_t(), g&: g2, key: target(e: *e, g2)) << std::endl; |
179 | } |
180 | } |
181 | } |
182 | } |
183 | |
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(g&: 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(g_: g2).first; |
199 | v != vertices(g_: g2).second; ++v) |
200 | { |
201 | put(p: vertex_index_t(), g&: g2, key: *v, value: 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(g_: g1) << std::endl; |
224 | for (graph1::edge_iterator e = edges(g_: g1).first; |
225 | e != edges(g_: g1).second; ++e) |
226 | { |
227 | out << get(p: vertex_index_t(), g&: g1, key: source(e: *e, g1)) << ' ' |
228 | << get(p: vertex_index_t(), g&: g1, key: target(e: *e, g1)) << std::endl; |
229 | } |
230 | } |
231 | |
232 | // Output graph 2 |
233 | { |
234 | std::ofstream out("isomorphism_failure.bg2" ); |
235 | out << num_vertices(g_: g2) << std::endl; |
236 | for (graph2::edge_iterator e = edges(g_: g2).first; |
237 | e != edges(g_: g2).second; ++e) |
238 | { |
239 | out << get(p: vertex_index_t(), g&: g2, key: source(e: *e, g2)) << ' ' |
240 | << get(p: vertex_index_t(), g&: g2, key: target(e: *e, g2)) << std::endl; |
241 | } |
242 | } |
243 | } |
244 | } |
245 | |
246 | int main(int argc, char* argv[]) |
247 | { |
248 | int n = argc < 3 ? 30 : boost::lexical_cast< int >(arg: argv[1]); |
249 | double edge_prob = argc < 3 ? 0.45 : boost::lexical_cast< double >(arg: argv[2]); |
250 | test_isomorphism(n, edge_probability: edge_prob); |
251 | |
252 | return boost::report_errors(); |
253 | } |
254 | |