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>
36typedef std::mt19937 random_generator_type;
37#else
38typedef boost::mt19937 random_generator_type;
39#endif
40
41using namespace boost;
42
43#ifndef BOOST_NO_CXX98_RANDOM_SHUFFLE
44template < 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
59template < typename Graph1, typename Graph2 >
60void 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
98template < typename Graph >
99void 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
120void 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
184void 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
246int 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

source code of boost/libs/graph/test/isomorphism.cpp