1 | //======================================================================= |
2 | // Boost.Graph library vf2_sub_graph_iso test |
3 | // Adapted from isomorphism.cpp and mcgregor_subgraphs_test.cpp |
4 | // |
5 | // Copyright (C) 2012 Flavio De Lorenzi (fdlorenzi@gmail.com) |
6 | // |
7 | // Distributed under the Boost Software License, Version 1.0. (See |
8 | // accompanying file LICENSE_1_0.txt or copy at |
9 | // http://www.boost.org/LICENSE_1_0.txt) |
10 | //======================================================================= |
11 | |
12 | // Revision History: |
13 | // 8 April 2013: Fixed a typo in random_functor. (Flavio De Lorenzi) |
14 | |
15 | #include <iostream> |
16 | #include <fstream> |
17 | #include <map> |
18 | #include <algorithm> |
19 | #include <cstdlib> |
20 | #include <time.h> |
21 | #include <boost/core/lightweight_test.hpp> |
22 | #include <boost/graph/adjacency_list.hpp> |
23 | #include <boost/graph/vf2_sub_graph_iso.hpp> |
24 | #include <boost/graph/random.hpp> |
25 | #include <boost/property_map/property_map.hpp> |
26 | #include <boost/random.hpp> |
27 | #include <boost/random/variate_generator.hpp> |
28 | #include <boost/random/uniform_real.hpp> |
29 | #include <boost/random/uniform_int.hpp> |
30 | #include <boost/random/mersenne_twister.hpp> |
31 | #include <boost/lexical_cast.hpp> |
32 | #include <boost/graph/graphviz.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< Generator&, |
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(Graph1& g1, const Graph2& g2) |
61 | { |
62 | BOOST_TEST(num_vertices(g1) <= num_vertices(g2)); |
63 | BOOST_TEST(num_edges(g1) == 0); |
64 | |
65 | typedef typename graph_traits< Graph1 >::vertex_descriptor vertex1; |
66 | typedef typename graph_traits< Graph2 >::vertex_descriptor vertex2; |
67 | typedef typename graph_traits< Graph1 >::vertex_iterator vertex_iterator; |
68 | typedef typename graph_traits< Graph2 >::edge_iterator edge_iterator; |
69 | |
70 | random_generator_type gen; |
71 | #ifndef BOOST_NO_CXX98_RANDOM_SHUFFLE |
72 | random_functor< random_generator_type > rand_fun(gen); |
73 | #endif |
74 | |
75 | // Decide new order |
76 | std::vector< vertex2 > orig_vertices; |
77 | std::copy(vertices(g2).first, vertices(g2).second, |
78 | std::back_inserter(orig_vertices)); |
79 | #ifndef BOOST_NO_CXX98_RANDOM_SHUFFLE |
80 | std::random_shuffle(orig_vertices.begin(), orig_vertices.end(), rand_fun); |
81 | #else |
82 | std::shuffle(orig_vertices.begin(), orig_vertices.end(), gen); |
83 | #endif |
84 | std::map< vertex2, vertex1 > vertex_map; |
85 | |
86 | std::size_t i = 0; |
87 | for (vertex_iterator vi = vertices(g1).first; vi != vertices(g1).second; |
88 | ++i, ++vi) |
89 | { |
90 | vertex_map[orig_vertices[i]] = *vi; |
91 | put(vertex_name_t(), g1, *vi, |
92 | get(vertex_name_t(), g2, orig_vertices[i])); |
93 | } |
94 | |
95 | for (edge_iterator ei = edges(g2).first; ei != edges(g2).second; ++ei) |
96 | { |
97 | typename std::map< vertex2, vertex1 >::iterator si |
98 | = vertex_map.find(source(*ei, g2)), |
99 | ti = vertex_map.find(target(*ei, g2)); |
100 | if ((si != vertex_map.end()) && (ti != vertex_map.end())) |
101 | add_edge(si->second, ti->second, get(edge_name_t(), g2, *ei), g1); |
102 | } |
103 | } |
104 | |
105 | template < typename Graph > |
106 | void generate_random_digraph(Graph& g, double edge_probability, |
107 | int max_parallel_edges, double parallel_edge_probability, int max_edge_name, |
108 | int max_vertex_name) |
109 | { |
110 | |
111 | BOOST_TEST((0 <= edge_probability) && (edge_probability <= 1)); |
112 | BOOST_TEST( |
113 | (0 <= parallel_edge_probability) && (parallel_edge_probability <= 1)); |
114 | BOOST_TEST(0 <= max_parallel_edges); |
115 | BOOST_TEST(0 <= max_edge_name); |
116 | BOOST_TEST(0 <= max_vertex_name); |
117 | |
118 | typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator; |
119 | random_generator_type random_gen; |
120 | boost::uniform_real< double > dist_real(0.0, 1.0); |
121 | boost::variate_generator< random_generator_type&, |
122 | boost::uniform_real< double > > |
123 | random_real_dist(random_gen, dist_real); |
124 | |
125 | for (vertex_iterator u = vertices(g).first; u != vertices(g).second; ++u) |
126 | { |
127 | for (vertex_iterator v = vertices(g).first; v != vertices(g).second; |
128 | ++v) |
129 | { |
130 | if (random_real_dist() <= edge_probability) |
131 | { |
132 | add_edge(*u, *v, g); |
133 | for (int i = 0; i < max_parallel_edges; ++i) |
134 | { |
135 | if (random_real_dist() <= parallel_edge_probability) |
136 | add_edge(*u, *v, g); |
137 | } |
138 | } |
139 | } |
140 | } |
141 | |
142 | { |
143 | boost::uniform_int< int > dist_int(0, max_edge_name); |
144 | boost::variate_generator< random_generator_type&, |
145 | boost::uniform_int< int > > |
146 | random_int_dist(random_gen, dist_int); |
147 | randomize_property< vertex_name_t >(g, random_int_dist); |
148 | } |
149 | |
150 | { |
151 | boost::uniform_int< int > dist_int(0, max_vertex_name); |
152 | boost::variate_generator< random_generator_type&, |
153 | boost::uniform_int< int > > |
154 | random_int_dist(random_gen, dist_int); |
155 | |
156 | randomize_property< edge_name_t >(g, random_int_dist); |
157 | } |
158 | } |
159 | |
160 | template < typename Graph1, typename Graph2, typename EdgeEquivalencePredicate, |
161 | typename VertexEquivalencePredicate > |
162 | struct test_callback |
163 | { |
164 | |
165 | test_callback(const Graph1& graph1, const Graph2& graph2, |
166 | EdgeEquivalencePredicate edge_comp, |
167 | VertexEquivalencePredicate vertex_comp, bool output) |
168 | : graph1_(graph1) |
169 | , graph2_(graph2) |
170 | , edge_comp_(edge_comp) |
171 | , vertex_comp_(vertex_comp) |
172 | , output_(output) |
173 | { |
174 | } |
175 | |
176 | template < typename CorrespondenceMap1To2, typename CorrespondenceMap2To1 > |
177 | bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1) |
178 | { |
179 | |
180 | bool verified; |
181 | BOOST_TEST(verified = verify_vf2_subgraph_iso( |
182 | graph1_, graph2_, f, edge_comp_, vertex_comp_)); |
183 | |
184 | // Output (sub)graph isomorphism map |
185 | if (!verified || output_) |
186 | { |
187 | std::cout << "Verfied: " << std::boolalpha << verified << std::endl; |
188 | std::cout << "Num vertices: " << num_vertices(graph1_) << ' ' |
189 | << num_vertices(graph2_) << std::endl; |
190 | BGL_FORALL_VERTICES_T(v, graph1_, Graph1) |
191 | std::cout << '(' << get(vertex_index_t(), graph1_, v) << ", " |
192 | << get(vertex_index_t(), graph2_, get(f, v)) << ") " ; |
193 | |
194 | std::cout << std::endl; |
195 | } |
196 | |
197 | return true; |
198 | } |
199 | |
200 | private: |
201 | const Graph1& graph1_; |
202 | const Graph2& graph2_; |
203 | EdgeEquivalencePredicate edge_comp_; |
204 | VertexEquivalencePredicate vertex_comp_; |
205 | bool output_; |
206 | }; |
207 | |
208 | // we pretend this is something more complicated which calculates indices |
209 | // somehow |
210 | template < typename G > struct IndirectIndexMap |
211 | { |
212 | typedef std::size_t value_type; |
213 | typedef value_type reference; |
214 | typedef typename boost::graph_traits< G >::vertex_descriptor key_type; |
215 | typedef boost::readable_property_map_tag category; |
216 | explicit IndirectIndexMap(const G& g) : g(g) {} |
217 | |
218 | public: |
219 | const G& g; |
220 | }; |
221 | |
222 | template < typename G > |
223 | std::size_t get(const IndirectIndexMap< G >& map, |
224 | typename boost::graph_traits< G >::vertex_descriptor v) |
225 | { |
226 | // we pretend this is something more complicated which calculates indices |
227 | // somehow |
228 | return get(vertex_index_t(), map.g, v); |
229 | } |
230 | |
231 | void test_vf2_sub_graph_iso(int n1, int n2, double edge_probability, |
232 | int max_parallel_edges, double parallel_edge_probability, int max_edge_name, |
233 | int max_vertex_name, bool output) |
234 | { |
235 | |
236 | typedef property< edge_name_t, int > edge_property; |
237 | typedef property< vertex_name_t, int, property< vertex_index_t, int > > |
238 | vertex_property; |
239 | |
240 | typedef adjacency_list< listS, listS, bidirectionalS, vertex_property, |
241 | edge_property > |
242 | graph1; |
243 | typedef adjacency_list< vecS, vecS, bidirectionalS, vertex_property, |
244 | edge_property > |
245 | graph2; |
246 | |
247 | graph1 g1(n1); |
248 | graph2 g2(n2); |
249 | generate_random_digraph(g&: g2, edge_probability, max_parallel_edges, |
250 | parallel_edge_probability, max_edge_name, max_vertex_name); |
251 | randomly_permute_graph(g1, g2); |
252 | |
253 | int v_idx = 0; |
254 | for (graph_traits< graph1 >::vertex_iterator vi = vertices(g_: g1).first; |
255 | vi != vertices(g_: g1).second; ++vi) |
256 | { |
257 | put(p: vertex_index_t(), g&: g1, key: *vi, value: v_idx++); |
258 | } |
259 | |
260 | // Create vertex and edge predicates |
261 | typedef property_map< graph1, vertex_name_t >::type vertex_name_map1; |
262 | typedef property_map< graph2, vertex_name_t >::type vertex_name_map2; |
263 | |
264 | typedef property_map_equivalent< vertex_name_map1, vertex_name_map2 > |
265 | vertex_predicate; |
266 | vertex_predicate vertex_comp = make_property_map_equivalent( |
267 | property_map1: get(p: vertex_name, g&: g1), property_map2: get(p: vertex_name, g&: g2)); |
268 | |
269 | typedef property_map< graph1, edge_name_t >::type edge_name_map1; |
270 | typedef property_map< graph2, edge_name_t >::type edge_name_map2; |
271 | |
272 | typedef property_map_equivalent< edge_name_map1, edge_name_map2 > |
273 | edge_predicate; |
274 | edge_predicate edge_comp |
275 | = make_property_map_equivalent(property_map1: get(p: edge_name, g&: g1), property_map2: get(p: edge_name, g&: g2)); |
276 | |
277 | std::clock_t start = std::clock(); |
278 | |
279 | // Create callback |
280 | test_callback< graph1, graph2, edge_predicate, vertex_predicate > callback( |
281 | g1, g2, edge_comp, vertex_comp, output); |
282 | |
283 | std::cout << std::endl; |
284 | BOOST_TEST(vf2_subgraph_iso(g1, g2, callback, vertex_order_by_mult(g1), |
285 | edges_equivalent(edge_comp).vertices_equivalent(vertex_comp))); |
286 | BOOST_TEST(vf2_subgraph_iso(g1, g2, callback, |
287 | IndirectIndexMap< graph1 >(g1), IndirectIndexMap< graph2 >(g2), |
288 | vertex_order_by_mult(g1), edge_comp, vertex_comp)); |
289 | |
290 | std::clock_t end1 = std::clock(); |
291 | std::cout << "vf2_subgraph_iso: elapsed time (clock cycles): " |
292 | << (end1 - start) << std::endl; |
293 | |
294 | if (num_vertices(g_: g1) == num_vertices(g_: g2)) |
295 | { |
296 | std::cout << std::endl; |
297 | BOOST_TEST(vf2_graph_iso(g1, g2, callback, vertex_order_by_mult(g1), |
298 | edges_equivalent(edge_comp).vertices_equivalent(vertex_comp))); |
299 | |
300 | std::clock_t end2 = std::clock(); |
301 | std::cout << "vf2_graph_iso: elapsed time (clock cycles): " |
302 | << (end2 - end1) << std::endl; |
303 | } |
304 | |
305 | if (output) |
306 | { |
307 | std::fstream file_graph1("graph1.dot" , std::fstream::out); |
308 | write_graphviz(out&: file_graph1, g: g1, |
309 | vw: make_label_writer(n: get(p: boost::vertex_name, g&: g1)), |
310 | ew: make_label_writer(n: get(p: boost::edge_name, g&: g1))); |
311 | |
312 | std::fstream file_graph2("graph2.dot" , std::fstream::out); |
313 | write_graphviz(out&: file_graph2, g: g2, |
314 | vw: make_label_writer(n: get(p: boost::vertex_name, g&: g2)), |
315 | ew: make_label_writer(n: get(p: boost::edge_name, g&: g2))); |
316 | } |
317 | } |
318 | |
319 | int main(int argc, char* argv[]) |
320 | { |
321 | |
322 | int num_vertices_g1 = 10; |
323 | int num_vertices_g2 = 20; |
324 | double edge_probability = 0.4; |
325 | int max_parallel_edges = 2; |
326 | double parallel_edge_probability = 0.4; |
327 | int max_edge_name = 5; |
328 | int max_vertex_name = 5; |
329 | bool output = false; |
330 | |
331 | if (argc > 1) |
332 | { |
333 | num_vertices_g1 = boost::lexical_cast< int >(arg: argv[1]); |
334 | } |
335 | |
336 | if (argc > 2) |
337 | { |
338 | num_vertices_g2 = boost::lexical_cast< int >(arg: argv[2]); |
339 | } |
340 | |
341 | if (argc > 3) |
342 | { |
343 | edge_probability = boost::lexical_cast< double >(arg: argv[3]); |
344 | } |
345 | |
346 | if (argc > 4) |
347 | { |
348 | max_parallel_edges = boost::lexical_cast< int >(arg: argv[4]); |
349 | } |
350 | |
351 | if (argc > 5) |
352 | { |
353 | parallel_edge_probability = boost::lexical_cast< double >(arg: argv[5]); |
354 | } |
355 | |
356 | if (argc > 6) |
357 | { |
358 | max_edge_name = boost::lexical_cast< int >(arg: argv[6]); |
359 | } |
360 | |
361 | if (argc > 7) |
362 | { |
363 | max_vertex_name = boost::lexical_cast< int >(arg: argv[7]); |
364 | } |
365 | |
366 | if (argc > 8) |
367 | { |
368 | output = boost::lexical_cast< bool >(arg: argv[8]); |
369 | } |
370 | |
371 | test_vf2_sub_graph_iso(n1: num_vertices_g1, n2: num_vertices_g2, edge_probability, |
372 | max_parallel_edges, parallel_edge_probability, max_edge_name, |
373 | max_vertex_name, output); |
374 | |
375 | return boost::report_errors(); |
376 | } |
377 | |