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/test/minimal.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 using namespace boost;
35
36
37 template <typename Generator>
38 struct random_functor {
random_functorrandom_functor39 random_functor(Generator& g) : g(g) { }
operator ()random_functor40 std::size_t operator()(std::size_t n) {
41 boost::uniform_int<std::size_t> distrib(0, n-1);
42 boost::variate_generator<Generator&, boost::uniform_int<std::size_t> >
43 x(g, distrib);
44 return x();
45 }
46 Generator& g;
47 };
48
49
50 template<typename Graph1, typename Graph2>
randomly_permute_graph(Graph1 & g1,const Graph2 & g2)51 void randomly_permute_graph(Graph1& g1, const Graph2& g2) {
52 BOOST_REQUIRE(num_vertices(g1) <= num_vertices(g2));
53 BOOST_REQUIRE(num_edges(g1) == 0);
54
55 typedef typename graph_traits<Graph1>::vertex_descriptor vertex1;
56 typedef typename graph_traits<Graph2>::vertex_descriptor vertex2;
57 typedef typename graph_traits<Graph1>::vertex_iterator vertex_iterator;
58 typedef typename graph_traits<Graph2>::edge_iterator edge_iterator;
59
60 boost::mt19937 gen;
61 random_functor<boost::mt19937> rand_fun(gen);
62
63 // Decide new order
64 std::vector<vertex2> orig_vertices;
65 std::copy(vertices(g2).first, vertices(g2).second, std::back_inserter(orig_vertices));
66 std::random_shuffle(orig_vertices.begin(), orig_vertices.end(), rand_fun);
67 std::map<vertex2, vertex1> vertex_map;
68
69 std::size_t i = 0;
70 for (vertex_iterator vi = vertices(g1).first;
71 vi != vertices(g1).second; ++i, ++vi) {
72 vertex_map[orig_vertices[i]] = *vi;
73 put(vertex_name_t(), g1, *vi, get(vertex_name_t(), g2, orig_vertices[i]));
74 }
75
76 for (edge_iterator ei = edges(g2).first; ei != edges(g2).second; ++ei) {
77 typename std::map<vertex2, vertex1>::iterator si = vertex_map.find(source(*ei, g2)),
78 ti = vertex_map.find(target(*ei, g2));
79 if ((si != vertex_map.end()) && (ti != vertex_map.end()))
80 add_edge(si->second, ti->second, get(edge_name_t(), g2, *ei), g1);
81 }
82 }
83
84
85 template<typename Graph>
generate_random_digraph(Graph & g,double edge_probability,int max_parallel_edges,double parallel_edge_probability,int max_edge_name,int max_vertex_name)86 void generate_random_digraph(Graph& g, double edge_probability,
87 int max_parallel_edges, double parallel_edge_probability,
88 int max_edge_name, int max_vertex_name) {
89
90 BOOST_REQUIRE((0 <= edge_probability) && (edge_probability <= 1));
91 BOOST_REQUIRE((0 <= parallel_edge_probability) && (parallel_edge_probability <= 1));
92 BOOST_REQUIRE(0 <= max_parallel_edges);
93 BOOST_REQUIRE(0 <= max_edge_name);
94 BOOST_REQUIRE(0 <= max_vertex_name);
95
96 typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
97 boost::mt19937 random_gen;
98 boost::uniform_real<double> dist_real(0.0, 1.0);
99 boost::variate_generator<boost::mt19937&, boost::uniform_real<double> >
100 random_real_dist(random_gen, dist_real);
101
102 for (vertex_iterator u = vertices(g).first; u != vertices(g).second; ++u) {
103 for (vertex_iterator v = vertices(g).first; v != vertices(g).second; ++v) {
104 if (random_real_dist() <= edge_probability) {
105 add_edge(*u, *v, g);
106 for (int i = 0; i < max_parallel_edges; ++i) {
107 if (random_real_dist() <= parallel_edge_probability)
108 add_edge(*u, *v, g);
109 }
110 }
111 }
112 }
113
114 {
115 boost::uniform_int<int> dist_int(0, max_edge_name);
116 boost::variate_generator<boost::mt19937&, boost::uniform_int<int> >
117 random_int_dist(random_gen, dist_int);
118 randomize_property<vertex_name_t>(g, random_int_dist);
119 }
120
121 {
122 boost::uniform_int<int> dist_int(0, max_vertex_name);
123 boost::variate_generator<boost::mt19937&, boost::uniform_int<int> >
124 random_int_dist(random_gen, dist_int);
125
126 randomize_property<edge_name_t>(g, random_int_dist);
127 }
128
129 }
130
131
132 template <typename Graph1,
133 typename Graph2,
134 typename EdgeEquivalencePredicate,
135 typename VertexEquivalencePredicate>
136 struct test_callback {
137
test_callbacktest_callback138 test_callback(const Graph1& graph1, const Graph2& graph2,
139 EdgeEquivalencePredicate edge_comp,
140 VertexEquivalencePredicate vertex_comp, bool output)
141 : graph1_(graph1), graph2_(graph2), edge_comp_(edge_comp), vertex_comp_(vertex_comp),
142 output_(output) {}
143
144 template <typename CorrespondenceMap1To2,
145 typename CorrespondenceMap2To1>
operator ()test_callback146 bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1) {
147
148 bool verified;
149 BOOST_CHECK(verified = verify_vf2_subgraph_iso(graph1_, graph2_, f, edge_comp_, vertex_comp_));
150
151 // Output (sub)graph isomorphism map
152 if (!verified || output_) {
153 std::cout << "Verfied: " << std::boolalpha << verified << std::endl;
154 std::cout << "Num vertices: " << num_vertices(graph1_) << ' ' << num_vertices(graph2_) << std::endl;
155 BGL_FORALL_VERTICES_T(v, graph1_, Graph1)
156 std::cout << '(' << get(vertex_index_t(), graph1_, v) << ", "
157 << get(vertex_index_t(), graph2_, get(f, v)) << ") ";
158
159 std::cout << std::endl;
160 }
161
162 return true;
163 }
164
165 private:
166 const Graph1& graph1_;
167 const Graph2& graph2_;
168 EdgeEquivalencePredicate edge_comp_;
169 VertexEquivalencePredicate vertex_comp_;
170 bool output_;
171 };
172
173
test_vf2_sub_graph_iso(int n1,int n2,double edge_probability,int max_parallel_edges,double parallel_edge_probability,int max_edge_name,int max_vertex_name,bool output)174 void test_vf2_sub_graph_iso(int n1, int n2, double edge_probability,
175 int max_parallel_edges, double parallel_edge_probability,
176 int max_edge_name, int max_vertex_name, bool output) {
177
178 typedef property<edge_name_t, int> edge_property;
179 typedef property<vertex_name_t, int, property<vertex_index_t, int> > vertex_property;
180
181 typedef adjacency_list<listS, listS, bidirectionalS, vertex_property, edge_property> graph1;
182 typedef adjacency_list<vecS, vecS, bidirectionalS, vertex_property, edge_property> graph2;
183
184 graph1 g1(n1);
185 graph2 g2(n2);
186 generate_random_digraph(g2, edge_probability, max_parallel_edges, parallel_edge_probability,
187 max_edge_name, max_vertex_name);
188 randomly_permute_graph(g1, g2);
189
190 int v_idx = 0;
191 for (graph_traits<graph1>::vertex_iterator vi = vertices(g1).first;
192 vi != vertices(g1).second; ++vi) {
193 put(vertex_index_t(), g1, *vi, v_idx++);
194 }
195
196
197 // Create vertex and edge predicates
198 typedef property_map<graph1, vertex_name_t>::type vertex_name_map1;
199 typedef property_map<graph2, vertex_name_t>::type vertex_name_map2;
200
201 typedef property_map_equivalent<vertex_name_map1, vertex_name_map2> vertex_predicate;
202 vertex_predicate vertex_comp =
203 make_property_map_equivalent(get(vertex_name, g1), get(vertex_name, g2));
204
205 typedef property_map<graph1, edge_name_t>::type edge_name_map1;
206 typedef property_map<graph2, edge_name_t>::type edge_name_map2;
207
208 typedef property_map_equivalent<edge_name_map1, edge_name_map2> edge_predicate;
209 edge_predicate edge_comp =
210 make_property_map_equivalent(get(edge_name, g1), get(edge_name, g2));
211
212
213 std::clock_t start = std::clock();
214
215 // Create callback
216 test_callback<graph1, graph2, edge_predicate, vertex_predicate>
217 callback(g1, g2, edge_comp, vertex_comp, output);
218
219 std::cout << std::endl;
220 BOOST_CHECK(vf2_subgraph_iso(g1, g2, callback, vertex_order_by_mult(g1),
221 edges_equivalent(edge_comp).vertices_equivalent(vertex_comp)));
222
223 std::clock_t end1 = std::clock();
224 std::cout << "vf2_subgraph_iso: elapsed time (clock cycles): " << (end1 - start) << std::endl;
225
226 if (num_vertices(g1) == num_vertices(g2)) {
227 std::cout << std::endl;
228 BOOST_CHECK(vf2_graph_iso(g1, g2, callback, vertex_order_by_mult(g1),
229 edges_equivalent(edge_comp).vertices_equivalent(vertex_comp)));
230
231 std::clock_t end2 = std::clock();
232 std::cout << "vf2_graph_iso: elapsed time (clock cycles): " << (end2 - end1) << std::endl;
233 }
234
235 if (output) {
236 std::fstream file_graph1("graph1.dot", std::fstream::out);
237 write_graphviz(file_graph1, g1,
238 make_label_writer(get(boost::vertex_name, g1)),
239 make_label_writer(get(boost::edge_name, g1)));
240
241 std::fstream file_graph2("graph2.dot", std::fstream::out);
242 write_graphviz(file_graph2, g2,
243 make_label_writer(get(boost::vertex_name, g2)),
244 make_label_writer(get(boost::edge_name, g2)));
245 }
246 }
247
test_main(int argc,char * argv[])248 int test_main(int argc, char* argv[]) {
249
250 int num_vertices_g1 = 10;
251 int num_vertices_g2 = 20;
252 double edge_probability = 0.4;
253 int max_parallel_edges = 2;
254 double parallel_edge_probability = 0.4;
255 int max_edge_name = 5;
256 int max_vertex_name = 5;
257 bool output = false;
258
259 if (argc > 1) {
260 num_vertices_g1 = boost::lexical_cast<int>(argv[1]);
261 }
262
263 if (argc > 2) {
264 num_vertices_g2 = boost::lexical_cast<int>(argv[2]);
265 }
266
267 if (argc > 3) {
268 edge_probability = boost::lexical_cast<double>(argv[3]);
269 }
270
271 if (argc > 4) {
272 max_parallel_edges = boost::lexical_cast<int>(argv[4]);
273 }
274
275 if (argc > 5) {
276 parallel_edge_probability = boost::lexical_cast<double>(argv[5]);
277 }
278
279 if (argc > 6) {
280 max_edge_name = boost::lexical_cast<int>(argv[6]);
281 }
282
283 if (argc > 7) {
284 max_vertex_name = boost::lexical_cast<int>(argv[7]);
285 }
286
287 if (argc > 8) {
288 output = boost::lexical_cast<bool>(argv[8]);
289 }
290
291 test_vf2_sub_graph_iso(num_vertices_g1, num_vertices_g2, edge_probability,
292 max_parallel_edges, parallel_edge_probability,
293 max_edge_name, max_vertex_name, output);
294
295 return 0;
296 }
297