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 | |
29 | bool was_common_subgraph_found = false, output_graphs = false; |
30 | std::vector< std::string > simple_subgraph_list; |
31 | |
32 | // Callback that compares incoming graphs to the supplied common |
33 | // subgraph. |
34 | template < 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 | |
205 | private: |
206 | const Graph &m_graph1, m_graph2; |
207 | Graph& m_common_subgraph; |
208 | }; |
209 | |
210 | template < 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 | |
243 | private: |
244 | const Graph& m_graph1; |
245 | }; |
246 | |
247 | template < typename Graph, typename RandomNumberGenerator, |
248 | typename VertexNameMap, typename EdgeNameMap > |
249 | void 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 | |
304 | bool 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 | |
311 | int 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 | |