1//=======================================================================
2// Copyright 2009 Trustees of Indiana University.
3// Authors: Michael Hansen
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
10#include <cmath>
11#include <iostream>
12#include <fstream>
13#include <sstream>
14#include <vector>
15#include <ctime>
16
17#include <boost/lexical_cast.hpp>
18#include <boost/random.hpp>
19#include <boost/graph/adjacency_list.hpp>
20#include <boost/graph/filtered_graph.hpp>
21#include <boost/graph/graphviz.hpp>
22#include <boost/graph/isomorphism.hpp>
23#include <boost/graph/iteration_macros.hpp>
24#include <boost/graph/random.hpp>
25#include <boost/graph/mcgregor_common_subgraphs.hpp>
26#include <boost/property_map/shared_array_property_map.hpp>
27#include <boost/core/lightweight_test.hpp>
28
29bool was_common_subgraph_found = false, output_graphs = false;
30std::vector< std::string > simple_subgraph_list;
31
32// Callback that compares incoming graphs to the supplied common
33// subgraph.
34template < typename Graph > struct test_callback
35{
36
37 test_callback(
38 Graph& common_subgraph, const Graph& graph1, const Graph& graph2)
39 : m_graph1(graph1), m_graph2(graph2), m_common_subgraph(common_subgraph)
40 {
41 }
42
43 template < typename CorrespondenceMapFirstToSecond,
44 typename CorrespondenceMapSecondToFirst >
45 bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
46 CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
47 typename boost::graph_traits< Graph >::vertices_size_type subgraph_size)
48 {
49
50 typedef typename boost::graph_traits< Graph >::vertex_descriptor Vertex;
51 typedef typename boost::graph_traits< Graph >::edge_descriptor Edge;
52 typedef std::pair< Edge, bool > EdgeInfo;
53
54 typedef
55 typename boost::property_map< Graph, boost::vertex_index_t >::type
56 VertexIndexMap;
57 typedef
58 typename boost::property_map< Graph, boost::vertex_name_t >::type
59 VertexNameMap;
60 typedef typename boost::property_map< Graph, boost::edge_name_t >::type
61 EdgeNameMap;
62
63 if (subgraph_size != num_vertices(m_common_subgraph))
64 {
65 return (true);
66 }
67
68 // Fill membership maps for both graphs
69 typedef boost::shared_array_property_map< bool, VertexIndexMap >
70 MembershipMap;
71
72 MembershipMap membership_map1(
73 num_vertices(m_graph1), get(boost::vertex_index, m_graph1));
74
75 MembershipMap membership_map2(
76 num_vertices(m_graph2), get(boost::vertex_index, m_graph2));
77
78 boost::fill_membership_map< Graph >(
79 m_graph1, correspondence_map_1_to_2, membership_map1);
80 boost::fill_membership_map< Graph >(
81 m_graph2, correspondence_map_2_to_1, membership_map2);
82
83 // Generate filtered graphs using membership maps
84 typedef typename boost::membership_filtered_graph_traits< Graph,
85 MembershipMap >::graph_type MembershipFilteredGraph;
86
87 MembershipFilteredGraph subgraph1
88 = boost::make_membership_filtered_graph(m_graph1, membership_map1);
89
90 MembershipFilteredGraph subgraph2
91 = boost::make_membership_filtered_graph(m_graph2, membership_map2);
92
93 VertexIndexMap vindex_map1 = get(boost::vertex_index, subgraph1);
94 VertexIndexMap vindex_map2 = get(boost::vertex_index, subgraph2);
95
96 VertexNameMap vname_map_common
97 = get(boost::vertex_name, m_common_subgraph);
98 VertexNameMap vname_map1 = get(boost::vertex_name, subgraph1);
99 VertexNameMap vname_map2 = get(boost::vertex_name, subgraph2);
100
101 EdgeNameMap ename_map_common = get(boost::edge_name, m_common_subgraph);
102 EdgeNameMap ename_map1 = get(boost::edge_name, subgraph1);
103 EdgeNameMap ename_map2 = get(boost::edge_name, subgraph2);
104
105 // Verify that subgraph1 matches the supplied common subgraph
106 BGL_FORALL_VERTICES_T(vertex1, subgraph1, MembershipFilteredGraph)
107 {
108
109 Vertex vertex_common
110 = vertex(get(vindex_map1, vertex1), m_common_subgraph);
111
112 // Match vertex names
113 if (get(vname_map_common, vertex_common)
114 != get(vname_map1, vertex1))
115 {
116
117 // Keep looking
118 return (true);
119 }
120
121 BGL_FORALL_VERTICES_T(vertex1_2, subgraph1, MembershipFilteredGraph)
122 {
123
124 Vertex vertex_common2
125 = vertex(get(vindex_map1, vertex1_2), m_common_subgraph);
126 EdgeInfo edge_common
127 = edge(vertex_common, vertex_common2, m_common_subgraph);
128 EdgeInfo edge1 = edge(vertex1, vertex1_2, subgraph1);
129
130 if ((edge_common.second != edge1.second)
131 || ((edge_common.second && edge1.second)
132 && (get(ename_map_common, edge_common.first)
133 != get(ename_map1, edge1.first))))
134 {
135
136 // Keep looking
137 return (true);
138 }
139 }
140
141 } // BGL_FORALL_VERTICES_T (subgraph1)
142
143 // Verify that subgraph2 matches the supplied common subgraph
144 BGL_FORALL_VERTICES_T(vertex2, subgraph2, MembershipFilteredGraph)
145 {
146
147 Vertex vertex_common
148 = vertex(get(vindex_map2, vertex2), m_common_subgraph);
149
150 // Match vertex names
151 if (get(vname_map_common, vertex_common)
152 != get(vname_map2, vertex2))
153 {
154
155 // Keep looking
156 return (true);
157 }
158
159 BGL_FORALL_VERTICES_T(vertex2_2, subgraph2, MembershipFilteredGraph)
160 {
161
162 Vertex vertex_common2
163 = vertex(get(vindex_map2, vertex2_2), m_common_subgraph);
164 EdgeInfo edge_common
165 = edge(vertex_common, vertex_common2, m_common_subgraph);
166 EdgeInfo edge2 = edge(vertex2, vertex2_2, subgraph2);
167
168 if ((edge_common.second != edge2.second)
169 || ((edge_common.second && edge2.second)
170 && (get(ename_map_common, edge_common.first)
171 != get(ename_map2, edge2.first))))
172 {
173
174 // Keep looking
175 return (true);
176 }
177 }
178
179 } // BGL_FORALL_VERTICES_T (subgraph2)
180
181 // Check isomorphism just to be thorough
182 if (verify_isomorphism(subgraph1, subgraph2, correspondence_map_1_to_2))
183 {
184
185 was_common_subgraph_found = true;
186
187 if (output_graphs)
188 {
189
190 std::fstream file_subgraph(
191 "found_common_subgraph.dot", std::fstream::out);
192 write_graphviz(file_subgraph, subgraph1,
193 make_label_writer(get(boost::vertex_name, m_graph1)),
194 make_label_writer(get(boost::edge_name, m_graph1)));
195 }
196
197 // Stop iterating
198 return (false);
199 }
200
201 // Keep looking
202 return (true);
203 }
204
205private:
206 const Graph &m_graph1, m_graph2;
207 Graph& m_common_subgraph;
208};
209
210template < typename Graph > struct simple_callback
211{
212
213 simple_callback(const Graph& graph1) : m_graph1(graph1) {}
214
215 template < typename CorrespondenceMapFirstToSecond,
216 typename CorrespondenceMapSecondToFirst >
217 bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
218 CorrespondenceMapSecondToFirst /*correspondence_map_2_to_1*/,
219 typename boost::graph_traits<
220 Graph >::vertices_size_type /*subgraph_size*/)
221 {
222
223 typedef typename boost::graph_traits< Graph >::vertex_descriptor Vertex;
224
225 std::stringstream subgraph_string;
226
227 BGL_FORALL_VERTICES_T(vertex1, m_graph1, Graph)
228 {
229
230 Vertex vertex2 = get(correspondence_map_1_to_2, vertex1);
231
232 if (vertex2 != boost::graph_traits< Graph >::null_vertex())
233 {
234 subgraph_string << vertex1 << "," << vertex2 << " ";
235 }
236 }
237
238 simple_subgraph_list.push_back(x: subgraph_string.str());
239
240 return (true);
241 }
242
243private:
244 const Graph& m_graph1;
245};
246
247template < typename Graph, typename RandomNumberGenerator,
248 typename VertexNameMap, typename EdgeNameMap >
249void add_random_vertices(Graph& graph, RandomNumberGenerator& generator,
250 int vertices_to_create, int max_edges_per_vertex, VertexNameMap vname_map,
251 EdgeNameMap ename_map)
252{
253
254 typedef typename boost::graph_traits< Graph >::vertex_descriptor Vertex;
255 typedef std::vector< Vertex > VertexList;
256
257 VertexList new_vertices;
258
259 for (int v_index = 0; v_index < vertices_to_create; ++v_index)
260 {
261
262 Vertex new_vertex = add_vertex(graph);
263 put(vname_map, new_vertex, generator());
264 new_vertices.push_back(new_vertex);
265 }
266
267 // Add edges for every new vertex. Care is taken to avoid parallel
268 // edges.
269 for (typename VertexList::const_iterator v_iter = new_vertices.begin();
270 v_iter != new_vertices.end(); ++v_iter)
271 {
272
273 Vertex source_vertex = *v_iter;
274 int edges_for_vertex
275 = (std::min)(a: (int)(generator() % max_edges_per_vertex) + 1,
276 b: (int)num_vertices(graph));
277
278 while (edges_for_vertex > 0)
279 {
280
281 Vertex target_vertex = random_vertex(graph, generator);
282
283 if (source_vertex == target_vertex)
284 {
285 continue;
286 }
287
288 BGL_FORALL_OUTEDGES_T(source_vertex, edge, graph, Graph)
289 {
290 if (target(edge, graph) == target_vertex)
291 {
292 continue;
293 }
294 }
295
296 put(ename_map, add_edge(source_vertex, target_vertex, graph).first,
297 generator());
298
299 edges_for_vertex--;
300 }
301 }
302}
303
304bool has_subgraph_string(std::string set_string)
305{
306 return (std::find(first: simple_subgraph_list.begin(), last: simple_subgraph_list.end(),
307 val: set_string)
308 != simple_subgraph_list.end());
309}
310
311int main(int argc, char* argv[])
312{
313 int vertices_to_create = 10;
314 int max_edges_per_vertex = 2;
315 std::size_t random_seed = std::time(timer: 0);
316
317 if (argc > 1)
318 {
319 vertices_to_create = boost::lexical_cast< int >(arg: argv[1]);
320 }
321
322 if (argc > 2)
323 {
324 max_edges_per_vertex = boost::lexical_cast< int >(arg: argv[2]);
325 }
326
327 if (argc > 3)
328 {
329 output_graphs = boost::lexical_cast< bool >(arg: argv[3]);
330 }
331
332 if (argc > 4)
333 {
334 random_seed = boost::lexical_cast< std::size_t >(arg: argv[4]);
335 }
336
337 boost::minstd_rand generator(random_seed);
338
339 // Using a vecS graph here so that we don't have to mess around with
340 // a vertex index map; it will be implicit.
341 typedef boost::adjacency_list< boost::listS, boost::vecS, boost::directedS,
342 boost::property< boost::vertex_name_t, unsigned int,
343 boost::property< boost::vertex_index_t, unsigned int > >,
344 boost::property< boost::edge_name_t, unsigned int > >
345 Graph;
346
347 typedef boost::property_map< Graph, boost::vertex_name_t >::type
348 VertexNameMap;
349 typedef boost::property_map< Graph, boost::edge_name_t >::type EdgeNameMap;
350
351 // Generate a random common subgraph and then add random vertices
352 // and edges to the two parent graphs.
353 Graph common_subgraph, graph1, graph2;
354
355 VertexNameMap vname_map_common = get(p: boost::vertex_name, g&: common_subgraph);
356 VertexNameMap vname_map1 = get(p: boost::vertex_name, g&: graph1);
357 VertexNameMap vname_map2 = get(p: boost::vertex_name, g&: graph2);
358
359 EdgeNameMap ename_map_common = get(p: boost::edge_name, g&: common_subgraph);
360 EdgeNameMap ename_map1 = get(p: boost::edge_name, g&: graph1);
361 EdgeNameMap ename_map2 = get(p: boost::edge_name, g&: graph2);
362
363 for (int vindex = 0; vindex < vertices_to_create; ++vindex)
364 {
365 put(pa: vname_map_common, k: add_vertex(g_&: common_subgraph), v: generator());
366 }
367
368 BGL_FORALL_VERTICES(source_vertex, common_subgraph, Graph)
369 {
370
371 BGL_FORALL_VERTICES(target_vertex, common_subgraph, Graph)
372 {
373
374 if (source_vertex != target_vertex)
375 {
376 put(pa: ename_map_common,
377 k: add_edge(u: source_vertex, v: target_vertex, g_&: common_subgraph)
378 .first,
379 v: generator());
380 }
381 }
382 }
383
384 boost::randomize_property< boost::vertex_name_t >(
385 g&: common_subgraph, rg&: generator);
386 boost::randomize_property< boost::edge_name_t >(g&: common_subgraph, rg&: generator);
387
388 boost::copy_graph(g_in: common_subgraph, g_out&: graph1);
389 boost::copy_graph(g_in: common_subgraph, g_out&: graph2);
390
391 // Randomly add vertices and edges to graph1 and graph2.
392 add_random_vertices(graph&: graph1, generator, vertices_to_create,
393 max_edges_per_vertex, vname_map: vname_map1, ename_map: ename_map1);
394
395 add_random_vertices(graph&: graph2, generator, vertices_to_create,
396 max_edges_per_vertex, vname_map: vname_map2, ename_map: ename_map2);
397
398 if (output_graphs)
399 {
400
401 std::fstream file_graph1("graph1.dot", std::fstream::out),
402 file_graph2("graph2.dot", std::fstream::out),
403 file_common_subgraph(
404 "expected_common_subgraph.dot", std::fstream::out);
405
406 write_graphviz(out&: file_graph1, g: graph1, vw: make_label_writer(n: vname_map1),
407 ew: make_label_writer(n: ename_map1));
408
409 write_graphviz(out&: file_graph2, g: graph2, vw: make_label_writer(n: vname_map2),
410 ew: make_label_writer(n: ename_map2));
411
412 write_graphviz(out&: file_common_subgraph, g: common_subgraph,
413 vw: make_label_writer(n: get(p: boost::vertex_name, g&: common_subgraph)),
414 ew: make_label_writer(n: get(p: boost::edge_name, g&: common_subgraph)));
415 }
416
417 std::cout << "Searching for common subgraph of size "
418 << num_vertices(g_: common_subgraph) << std::endl;
419
420 test_callback< Graph > user_callback(common_subgraph, graph1, graph2);
421
422 boost::mcgregor_common_subgraphs(graph1, graph2, only_connected_subgraphs: true, user_callback,
423 params: boost::edges_equivalent(
424 p: boost::make_property_map_equivalent(property_map1: ename_map1, property_map2: ename_map2))
425 .vertices_equivalent(
426 p: boost::make_property_map_equivalent(property_map1: vname_map1, property_map2: vname_map2)));
427
428 BOOST_TEST(was_common_subgraph_found);
429
430 // Test maximum and unique variants on known graphs
431 Graph graph_simple1, graph_simple2;
432 simple_callback< Graph > user_callback_simple(graph_simple1);
433
434 VertexNameMap vname_map_simple1 = get(p: boost::vertex_name, g&: graph_simple1);
435 VertexNameMap vname_map_simple2 = get(p: boost::vertex_name, g&: graph_simple2);
436
437 put(pa: vname_map_simple1, k: add_vertex(g_&: graph_simple1), v: 1);
438 put(pa: vname_map_simple1, k: add_vertex(g_&: graph_simple1), v: 2);
439 put(pa: vname_map_simple1, k: add_vertex(g_&: graph_simple1), v: 3);
440
441 add_edge(u: 0, v: 1, g_&: graph_simple1);
442 add_edge(u: 0, v: 2, g_&: graph_simple1);
443 add_edge(u: 1, v: 2, g_&: graph_simple1);
444
445 put(pa: vname_map_simple2, k: add_vertex(g_&: graph_simple2), v: 1);
446 put(pa: vname_map_simple2, k: add_vertex(g_&: graph_simple2), v: 2);
447 put(pa: vname_map_simple2, k: add_vertex(g_&: graph_simple2), v: 3);
448 put(pa: vname_map_simple2, k: add_vertex(g_&: graph_simple2), v: 4);
449
450 add_edge(u: 0, v: 1, g_&: graph_simple2);
451 add_edge(u: 0, v: 2, g_&: graph_simple2);
452 add_edge(u: 1, v: 2, g_&: graph_simple2);
453 add_edge(u: 1, v: 3, g_&: graph_simple2);
454
455 // Unique subgraphs
456 std::cout << "Searching for unique subgraphs" << std::endl;
457 boost::mcgregor_common_subgraphs_unique(graph1: graph_simple1, graph2: graph_simple2, only_connected_subgraphs: true,
458 user_callback: user_callback_simple,
459 params: boost::vertices_equivalent(p: boost::make_property_map_equivalent(
460 property_map1: vname_map_simple1, property_map2: vname_map_simple2)));
461
462 BOOST_TEST(has_subgraph_string("0,0 1,1 "));
463 BOOST_TEST(has_subgraph_string("0,0 1,1 2,2 "));
464 BOOST_TEST(has_subgraph_string("0,0 2,2 "));
465 BOOST_TEST(has_subgraph_string("1,1 2,2 "));
466
467 if (output_graphs)
468 {
469 std::copy(first: simple_subgraph_list.begin(), last: simple_subgraph_list.end(),
470 result: std::ostream_iterator< std::string >(std::cout, "\n"));
471
472 std::cout << std::endl;
473 }
474
475 simple_subgraph_list.clear();
476
477 // Maximum subgraphs
478 std::cout << "Searching for maximum subgraphs" << std::endl;
479 boost::mcgregor_common_subgraphs_maximum(graph1: graph_simple1, graph2: graph_simple2, only_connected_subgraphs: true,
480 user_callback: user_callback_simple,
481 params: boost::vertices_equivalent(p: boost::make_property_map_equivalent(
482 property_map1: vname_map_simple1, property_map2: vname_map_simple2)));
483
484 BOOST_TEST(has_subgraph_string("0,0 1,1 2,2 "));
485
486 if (output_graphs)
487 {
488 std::copy(first: simple_subgraph_list.begin(), last: simple_subgraph_list.end(),
489 result: std::ostream_iterator< std::string >(std::cout, "\n"));
490
491 std::cout << std::endl;
492 }
493
494 simple_subgraph_list.clear();
495
496 // Maximum, unique subgraphs
497 std::cout << "Searching for maximum unique subgraphs" << std::endl;
498 boost::mcgregor_common_subgraphs_maximum_unique(graph1: graph_simple1,
499 graph2: graph_simple2, only_connected_subgraphs: true, user_callback: user_callback_simple,
500 params: boost::vertices_equivalent(p: boost::make_property_map_equivalent(
501 property_map1: vname_map_simple1, property_map2: vname_map_simple2)));
502
503 BOOST_TEST(simple_subgraph_list.size() == 1);
504 BOOST_TEST(has_subgraph_string("0,0 1,1 2,2 "));
505
506 if (output_graphs)
507 {
508 std::copy(first: simple_subgraph_list.begin(), last: simple_subgraph_list.end(),
509 result: std::ostream_iterator< std::string >(std::cout, "\n"));
510
511 std::cout << std::endl;
512 }
513
514 return boost::report_errors();
515}
516

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