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>
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< Generator&,
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(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
105template < typename Graph >
106void 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
160template < typename Graph1, typename Graph2, typename EdgeEquivalencePredicate,
161 typename VertexEquivalencePredicate >
162struct 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
200private:
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
210template < 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
218public:
219 const G& g;
220};
221
222template < typename G >
223std::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
231void 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
319int 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

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