]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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: | |
f67539c2 | 13 | // 8 April 2013: Fixed a typo in random_functor. (Flavio De Lorenzi) |
7c673cae FG |
14 | |
15 | #include <iostream> | |
16 | #include <fstream> | |
17 | #include <map> | |
18 | #include <algorithm> | |
19 | #include <cstdlib> | |
f67539c2 TL |
20 | #include <time.h> |
21 | #include <boost/core/lightweight_test.hpp> | |
7c673cae FG |
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 | ||
92f5a8d4 TL |
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 | |
7c673cae | 40 | |
92f5a8d4 | 41 | using namespace boost; |
7c673cae | 42 | |
92f5a8d4 | 43 | #ifndef BOOST_NO_CXX98_RANDOM_SHUFFLE |
f67539c2 TL |
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; | |
7c673cae | 56 | }; |
92f5a8d4 | 57 | #endif |
7c673cae | 58 | |
f67539c2 TL |
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; | |
92f5a8d4 | 71 | #ifndef BOOST_NO_CXX98_RANDOM_SHUFFLE |
f67539c2 | 72 | random_functor< random_generator_type > rand_fun(gen); |
92f5a8d4 | 73 | #endif |
f67539c2 TL |
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)); | |
92f5a8d4 | 79 | #ifndef BOOST_NO_CXX98_RANDOM_SHUFFLE |
f67539c2 | 80 | std::random_shuffle(orig_vertices.begin(), orig_vertices.end(), rand_fun); |
92f5a8d4 | 81 | #else |
f67539c2 | 82 | std::shuffle(orig_vertices.begin(), orig_vertices.end(), gen); |
92f5a8d4 | 83 | #endif |
f67539c2 TL |
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 | } | |
7c673cae FG |
103 | } |
104 | ||
f67539c2 TL |
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 | { | |
7c673cae | 110 | |
f67539c2 TL |
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 | } | |
7c673cae | 139 | } |
7c673cae | 140 | } |
7c673cae | 141 | |
f67539c2 TL |
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 | } | |
7c673cae FG |
158 | } |
159 | ||
f67539c2 TL |
160 | template < typename Graph1, typename Graph2, typename EdgeEquivalencePredicate, |
161 | typename VertexEquivalencePredicate > | |
162 | struct test_callback | |
163 | { | |
7c673cae | 164 | |
f67539c2 TL |
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 | { | |
7c673cae | 174 | } |
f67539c2 TL |
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 | ||
7c673cae | 200 | private: |
f67539c2 TL |
201 | const Graph1& graph1_; |
202 | const Graph2& graph2_; | |
203 | EdgeEquivalencePredicate edge_comp_; | |
204 | VertexEquivalencePredicate vertex_comp_; | |
205 | bool output_; | |
7c673cae FG |
206 | }; |
207 | ||
f67539c2 TL |
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 | ||
7c673cae | 218 | public: |
f67539c2 | 219 | const G& g; |
7c673cae FG |
220 | }; |
221 | ||
f67539c2 TL |
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); | |
7c673cae FG |
229 | } |
230 | ||
f67539c2 TL |
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(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(g1).first; | |
255 | vi != vertices(g1).second; ++vi) | |
256 | { | |
257 | put(vertex_index_t(), g1, *vi, 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 | get(vertex_name, g1), get(vertex_name, 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(get(edge_name, g1), get(edge_name, 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 | ||
7c673cae | 283 | std::cout << std::endl; |
f67539c2 TL |
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(g1) == num_vertices(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(file_graph1, g1, | |
309 | make_label_writer(get(boost::vertex_name, g1)), | |
310 | make_label_writer(get(boost::edge_name, g1))); | |
311 | ||
312 | std::fstream file_graph2("graph2.dot", std::fstream::out); | |
313 | write_graphviz(file_graph2, g2, | |
314 | make_label_writer(get(boost::vertex_name, g2)), | |
315 | make_label_writer(get(boost::edge_name, g2))); | |
316 | } | |
7c673cae FG |
317 | } |
318 | ||
f67539c2 TL |
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 >(argv[1]); | |
334 | } | |
335 | ||
336 | if (argc > 2) | |
337 | { | |
338 | num_vertices_g2 = boost::lexical_cast< int >(argv[2]); | |
339 | } | |
340 | ||
341 | if (argc > 3) | |
342 | { | |
343 | edge_probability = boost::lexical_cast< double >(argv[3]); | |
344 | } | |
345 | ||
346 | if (argc > 4) | |
347 | { | |
348 | max_parallel_edges = boost::lexical_cast< int >(argv[4]); | |
349 | } | |
350 | ||
351 | if (argc > 5) | |
352 | { | |
353 | parallel_edge_probability = boost::lexical_cast< double >(argv[5]); | |
354 | } | |
355 | ||
356 | if (argc > 6) | |
357 | { | |
358 | max_edge_name = boost::lexical_cast< int >(argv[6]); | |
359 | } | |
360 | ||
361 | if (argc > 7) | |
362 | { | |
363 | max_vertex_name = boost::lexical_cast< int >(argv[7]); | |
364 | } | |
365 | ||
366 | if (argc > 8) | |
367 | { | |
368 | output = boost::lexical_cast< bool >(argv[8]); | |
369 | } | |
370 | ||
371 | test_vf2_sub_graph_iso(num_vertices_g1, 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(); | |
7c673cae | 376 | } |