1//=======================================================================
2// Copyright 2009 Trustees of Indiana University.
3// Authors: Michael Hansen, Andrew Lumsdaine
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#ifndef BOOST_GRAPH_MCGREGOR_COMMON_SUBGRAPHS_HPP
11#define BOOST_GRAPH_MCGREGOR_COMMON_SUBGRAPHS_HPP
12
13#include <algorithm>
14#include <vector>
15#include <stack>
16
17#include <boost/make_shared.hpp>
18#include <boost/graph/adjacency_list.hpp>
19#include <boost/graph/filtered_graph.hpp>
20#include <boost/graph/graph_utility.hpp>
21#include <boost/graph/iteration_macros.hpp>
22#include <boost/graph/properties.hpp>
23#include <boost/property_map/shared_array_property_map.hpp>
24
25namespace boost {
26
27 namespace detail {
28
29 // Traits associated with common subgraphs, used mainly to keep a
30 // consistent type for the correspondence maps.
31 template <typename GraphFirst,
32 typename GraphSecond,
33 typename VertexIndexMapFirst,
34 typename VertexIndexMapSecond>
35 struct mcgregor_common_subgraph_traits {
36 typedef typename graph_traits<GraphFirst>::vertex_descriptor vertex_first_type;
37 typedef typename graph_traits<GraphSecond>::vertex_descriptor vertex_second_type;
38
39 typedef shared_array_property_map<vertex_second_type, VertexIndexMapFirst>
40 correspondence_map_first_to_second_type;
41
42 typedef shared_array_property_map<vertex_first_type, VertexIndexMapSecond>
43 correspondence_map_second_to_first_type;
44 };
45
46 } // namespace detail
47
48 // ==========================================================================
49
50 // Binary function object that returns true if the values for item1
51 // in property_map1 and item2 in property_map2 are equivalent.
52 template <typename PropertyMapFirst,
53 typename PropertyMapSecond>
54 struct property_map_equivalent {
55
56 property_map_equivalent(const PropertyMapFirst property_map1,
57 const PropertyMapSecond property_map2) :
58 m_property_map1(property_map1),
59 m_property_map2(property_map2) { }
60
61 template <typename ItemFirst,
62 typename ItemSecond>
63 bool operator()(const ItemFirst item1, const ItemSecond item2) {
64 return (get(m_property_map1, item1) == get(m_property_map2, item2));
65 }
66
67 private:
68 const PropertyMapFirst m_property_map1;
69 const PropertyMapSecond m_property_map2;
70 };
71
72 // Returns a property_map_equivalent object that compares the values
73 // of property_map1 and property_map2.
74 template <typename PropertyMapFirst,
75 typename PropertyMapSecond>
76 property_map_equivalent<PropertyMapFirst,
77 PropertyMapSecond>
78 make_property_map_equivalent
79 (const PropertyMapFirst property_map1,
80 const PropertyMapSecond property_map2) {
81
82 return (property_map_equivalent<PropertyMapFirst, PropertyMapSecond>
83 (property_map1, property_map2));
84 }
85
86 // Binary function object that always returns true. Used when
87 // vertices or edges are always equivalent (i.e. have no labels).
88 struct always_equivalent {
89
90 template <typename ItemFirst,
91 typename ItemSecond>
92 bool operator()(const ItemFirst&, const ItemSecond&) {
93 return (true);
94 }
95 };
96
97 // ==========================================================================
98
99 namespace detail {
100
101 // Return true if new_vertex1 and new_vertex2 can extend the
102 // subgraph represented by correspondence_map_1_to_2 and
103 // correspondence_map_2_to_1. The vertices_equivalent and
104 // edges_equivalent predicates are used to test vertex and edge
105 // equivalency between the two graphs.
106 template <typename GraphFirst,
107 typename GraphSecond,
108 typename CorrespondenceMapFirstToSecond,
109 typename CorrespondenceMapSecondToFirst,
110 typename EdgeEquivalencePredicate,
111 typename VertexEquivalencePredicate>
112 bool can_extend_graph
113 (const GraphFirst& graph1,
114 const GraphSecond& graph2,
115 CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
116 CorrespondenceMapSecondToFirst /*correspondence_map_2_to_1*/,
117 typename graph_traits<GraphFirst>::vertices_size_type subgraph_size,
118 typename graph_traits<GraphFirst>::vertex_descriptor new_vertex1,
119 typename graph_traits<GraphSecond>::vertex_descriptor new_vertex2,
120 EdgeEquivalencePredicate edges_equivalent,
121 VertexEquivalencePredicate vertices_equivalent,
122 bool only_connected_subgraphs)
123 {
124 typedef typename graph_traits<GraphSecond>::vertex_descriptor VertexSecond;
125
126 typedef typename graph_traits<GraphFirst>::edge_descriptor EdgeFirst;
127 typedef typename graph_traits<GraphSecond>::edge_descriptor EdgeSecond;
128
129 // Check vertex equality
130 if (!vertices_equivalent(new_vertex1, new_vertex2)) {
131 return (false);
132 }
133
134 // Vertices match and graph is empty, so we can extend the subgraph
135 if (subgraph_size == 0) {
136 return (true);
137 }
138
139 bool has_one_edge = false;
140
141 // Verify edges with existing sub-graph
142 BGL_FORALL_VERTICES_T(existing_vertex1, graph1, GraphFirst) {
143
144 VertexSecond existing_vertex2 = get(correspondence_map_1_to_2, existing_vertex1);
145
146 // Skip unassociated vertices
147 if (existing_vertex2 == graph_traits<GraphSecond>::null_vertex()) {
148 continue;
149 }
150
151 // NOTE: This will not work with parallel edges, since the
152 // first matching edge is always chosen.
153 EdgeFirst edge_to_new1, edge_from_new1;
154 bool edge_to_new_exists1 = false, edge_from_new_exists1 = false;
155
156 EdgeSecond edge_to_new2, edge_from_new2;
157 bool edge_to_new_exists2 = false, edge_from_new_exists2 = false;
158
159 // Search for edge from existing to new vertex (graph1)
160 BGL_FORALL_OUTEDGES_T(existing_vertex1, edge1, graph1, GraphFirst) {
161 if (target(edge1, graph1) == new_vertex1) {
162 edge_to_new1 = edge1;
163 edge_to_new_exists1 = true;
164 break;
165 }
166 }
167
168 // Search for edge from existing to new vertex (graph2)
169 BGL_FORALL_OUTEDGES_T(existing_vertex2, edge2, graph2, GraphSecond) {
170 if (target(edge2, graph2) == new_vertex2) {
171 edge_to_new2 = edge2;
172 edge_to_new_exists2 = true;
173 break;
174 }
175 }
176
177 // Make sure edges from existing to new vertices are equivalent
178 if ((edge_to_new_exists1 != edge_to_new_exists2) ||
179 ((edge_to_new_exists1 && edge_to_new_exists2) &&
180 !edges_equivalent(edge_to_new1, edge_to_new2))) {
181
182 return (false);
183 }
184
185 bool is_undirected1 = is_undirected(graph1),
186 is_undirected2 = is_undirected(graph2);
187
188 if (is_undirected1 && is_undirected2) {
189
190 // Edge in both graphs exists and both graphs are undirected
191 if (edge_to_new_exists1 && edge_to_new_exists2) {
192 has_one_edge = true;
193 }
194
195 continue;
196 }
197 else {
198
199 if (!is_undirected1) {
200
201 // Search for edge from new to existing vertex (graph1)
202 BGL_FORALL_OUTEDGES_T(new_vertex1, edge1, graph1, GraphFirst) {
203 if (target(edge1, graph1) == existing_vertex1) {
204 edge_from_new1 = edge1;
205 edge_from_new_exists1 = true;
206 break;
207 }
208 }
209 }
210
211 if (!is_undirected2) {
212
213 // Search for edge from new to existing vertex (graph2)
214 BGL_FORALL_OUTEDGES_T(new_vertex2, edge2, graph2, GraphSecond) {
215 if (target(edge2, graph2) == existing_vertex2) {
216 edge_from_new2 = edge2;
217 edge_from_new_exists2 = true;
218 break;
219 }
220 }
221 }
222
223 // Make sure edges from new to existing vertices are equivalent
224 if ((edge_from_new_exists1 != edge_from_new_exists2) ||
225 ((edge_from_new_exists1 && edge_from_new_exists2) &&
226 !edges_equivalent(edge_from_new1, edge_from_new2))) {
227
228 return (false);
229 }
230
231 if ((edge_from_new_exists1 && edge_from_new_exists2) ||
232 (edge_to_new_exists1 && edge_to_new_exists2)) {
233 has_one_edge = true;
234 }
235
236 } // else
237
238 } // BGL_FORALL_VERTICES_T
239
240 // Make sure new vertices are connected to the existing subgraph
241 if (only_connected_subgraphs && !has_one_edge) {
242 return (false);
243 }
244
245 return (true);
246 }
247
248 // Recursive method that does a depth-first search in the space of
249 // potential subgraphs. At each level, every new vertex pair from
250 // both graphs is tested to see if it can extend the current
251 // subgraph. If so, the subgraph is output to subgraph_callback
252 // in the form of two correspondence maps (one for each graph).
253 // Returning false from subgraph_callback will terminate the
254 // search. Function returns true if the entire search space was
255 // explored.
256 template <typename GraphFirst,
257 typename GraphSecond,
258 typename VertexIndexMapFirst,
259 typename VertexIndexMapSecond,
260 typename CorrespondenceMapFirstToSecond,
261 typename CorrespondenceMapSecondToFirst,
262 typename VertexStackFirst,
263 typename EdgeEquivalencePredicate,
264 typename VertexEquivalencePredicate,
265 typename SubGraphInternalCallback>
266 bool mcgregor_common_subgraphs_internal
267 (const GraphFirst& graph1,
268 const GraphSecond& graph2,
269 const VertexIndexMapFirst& vindex_map1,
270 const VertexIndexMapSecond& vindex_map2,
271 CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
272 CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
273 VertexStackFirst& vertex_stack1,
274 EdgeEquivalencePredicate edges_equivalent,
275 VertexEquivalencePredicate vertices_equivalent,
276 bool only_connected_subgraphs,
277 SubGraphInternalCallback subgraph_callback)
278 {
279 typedef typename graph_traits<GraphFirst>::vertex_descriptor VertexFirst;
280 typedef typename graph_traits<GraphSecond>::vertex_descriptor VertexSecond;
281 typedef typename graph_traits<GraphFirst>::vertices_size_type VertexSizeFirst;
282
283 // Get iterators for vertices from both graphs
284 typename graph_traits<GraphFirst>::vertex_iterator
285 vertex1_iter, vertex1_end;
286
287 typename graph_traits<GraphSecond>::vertex_iterator
288 vertex2_begin, vertex2_end, vertex2_iter;
289
290 boost::tie(vertex1_iter, vertex1_end) = vertices(graph1);
291 boost::tie(vertex2_begin, vertex2_end) = vertices(graph2);
292 vertex2_iter = vertex2_begin;
293
294 // Iterate until all vertices have been visited
295 BGL_FORALL_VERTICES_T(new_vertex1, graph1, GraphFirst) {
296
297 VertexSecond existing_vertex2 = get(correspondence_map_1_to_2, new_vertex1);
298
299 // Skip already matched vertices in first graph
300 if (existing_vertex2 != graph_traits<GraphSecond>::null_vertex()) {
301 continue;
302 }
303
304 BGL_FORALL_VERTICES_T(new_vertex2, graph2, GraphSecond) {
305
306 VertexFirst existing_vertex1 = get(correspondence_map_2_to_1, new_vertex2);
307
308 // Skip already matched vertices in second graph
309 if (existing_vertex1 != graph_traits<GraphFirst>::null_vertex()) {
310 continue;
311 }
312
313 // Check if current sub-graph can be extended with the matched vertex pair
314 if (can_extend_graph(graph1, graph2,
315 correspondence_map_1_to_2, correspondence_map_2_to_1,
316 (VertexSizeFirst)vertex_stack1.size(),
317 new_vertex1, new_vertex2,
318 edges_equivalent, vertices_equivalent,
319 only_connected_subgraphs)) {
320
321 // Keep track of old graph size for restoring later
322 VertexSizeFirst old_graph_size = (VertexSizeFirst)vertex_stack1.size(),
323 new_graph_size = old_graph_size + 1;
324
325 // Extend subgraph
326 put(correspondence_map_1_to_2, new_vertex1, new_vertex2);
327 put(correspondence_map_2_to_1, new_vertex2, new_vertex1);
328 vertex_stack1.push(new_vertex1);
329
330 // Returning false from the callback will cancel iteration
331 if (!subgraph_callback(correspondence_map_1_to_2,
332 correspondence_map_2_to_1,
333 new_graph_size)) {
334 return (false);
335 }
336
337 // Depth-first search into the state space of possible sub-graphs
338 bool continue_iteration =
339 mcgregor_common_subgraphs_internal
340 (graph1, graph2,
341 vindex_map1, vindex_map2,
342 correspondence_map_1_to_2, correspondence_map_2_to_1,
343 vertex_stack1,
344 edges_equivalent, vertices_equivalent,
345 only_connected_subgraphs, subgraph_callback);
346
347 if (!continue_iteration) {
348 return (false);
349 }
350
351 // Restore previous state
352 if (vertex_stack1.size() > old_graph_size) {
353
354 VertexFirst stack_vertex1 = vertex_stack1.top();
355 VertexSecond stack_vertex2 = get(correspondence_map_1_to_2,
356 stack_vertex1);
357
358 // Contract subgraph
359 put(correspondence_map_1_to_2, stack_vertex1,
360 graph_traits<GraphSecond>::null_vertex());
361
362 put(correspondence_map_2_to_1, stack_vertex2,
363 graph_traits<GraphFirst>::null_vertex());
364
365 vertex_stack1.pop();
366 }
367
368 } // if can_extend_graph
369
370 } // BGL_FORALL_VERTICES_T (graph2)
371
372 } // BGL_FORALL_VERTICES_T (graph1)
373
374 return (true);
375 }
376
377 // Internal method that initializes blank correspondence maps and
378 // a vertex stack for use in mcgregor_common_subgraphs_internal.
379 template <typename GraphFirst,
380 typename GraphSecond,
381 typename VertexIndexMapFirst,
382 typename VertexIndexMapSecond,
383 typename EdgeEquivalencePredicate,
384 typename VertexEquivalencePredicate,
385 typename SubGraphInternalCallback>
386 inline void mcgregor_common_subgraphs_internal_init
387 (const GraphFirst& graph1,
388 const GraphSecond& graph2,
389 const VertexIndexMapFirst vindex_map1,
390 const VertexIndexMapSecond vindex_map2,
391 EdgeEquivalencePredicate edges_equivalent,
392 VertexEquivalencePredicate vertices_equivalent,
393 bool only_connected_subgraphs,
394 SubGraphInternalCallback subgraph_callback)
395 {
396 typedef mcgregor_common_subgraph_traits<GraphFirst,
397 GraphSecond, VertexIndexMapFirst,
398 VertexIndexMapSecond> SubGraphTraits;
399
400 typename SubGraphTraits::correspondence_map_first_to_second_type
401 correspondence_map_1_to_2(num_vertices(graph1), vindex_map1);
402
403 BGL_FORALL_VERTICES_T(vertex1, graph1, GraphFirst) {
404 put(correspondence_map_1_to_2, vertex1,
405 graph_traits<GraphSecond>::null_vertex());
406 }
407
408 typename SubGraphTraits::correspondence_map_second_to_first_type
409 correspondence_map_2_to_1(num_vertices(graph2), vindex_map2);
410
411 BGL_FORALL_VERTICES_T(vertex2, graph2, GraphSecond) {
412 put(correspondence_map_2_to_1, vertex2,
413 graph_traits<GraphFirst>::null_vertex());
414 }
415
416 typedef typename graph_traits<GraphFirst>::vertex_descriptor
417 VertexFirst;
418
419 std::stack<VertexFirst> vertex_stack1;
420
421 mcgregor_common_subgraphs_internal
422 (graph1, graph2,
423 vindex_map1, vindex_map2,
424 correspondence_map_1_to_2, correspondence_map_2_to_1,
425 vertex_stack1,
426 edges_equivalent, vertices_equivalent,
427 only_connected_subgraphs,
428 subgraph_callback);
429 }
430
431 } // namespace detail
432
433 // ==========================================================================
434
435 // Enumerates all common subgraphs present in graph1 and graph2.
436 // Continues until the search space has been fully explored or false
437 // is returned from user_callback.
438 template <typename GraphFirst,
439 typename GraphSecond,
440 typename VertexIndexMapFirst,
441 typename VertexIndexMapSecond,
442 typename EdgeEquivalencePredicate,
443 typename VertexEquivalencePredicate,
444 typename SubGraphCallback>
445 void mcgregor_common_subgraphs
446 (const GraphFirst& graph1,
447 const GraphSecond& graph2,
448 const VertexIndexMapFirst vindex_map1,
449 const VertexIndexMapSecond vindex_map2,
450 EdgeEquivalencePredicate edges_equivalent,
451 VertexEquivalencePredicate vertices_equivalent,
452 bool only_connected_subgraphs,
453 SubGraphCallback user_callback)
454 {
455
456 detail::mcgregor_common_subgraphs_internal_init
457 (graph1, graph2,
458 vindex_map1, vindex_map2,
459 edges_equivalent, vertices_equivalent,
460 only_connected_subgraphs,
461 user_callback);
462 }
463
464 // Variant of mcgregor_common_subgraphs with all default parameters
465 template <typename GraphFirst,
466 typename GraphSecond,
467 typename SubGraphCallback>
468 void mcgregor_common_subgraphs
469 (const GraphFirst& graph1,
470 const GraphSecond& graph2,
471 bool only_connected_subgraphs,
472 SubGraphCallback user_callback)
473 {
474
475 detail::mcgregor_common_subgraphs_internal_init
476 (graph1, graph2,
477 get(vertex_index, graph1), get(vertex_index, graph2),
478 always_equivalent(), always_equivalent(),
479 only_connected_subgraphs, user_callback);
480 }
481
482 // Named parameter variant of mcgregor_common_subgraphs
483 template <typename GraphFirst,
484 typename GraphSecond,
485 typename SubGraphCallback,
486 typename Param,
487 typename Tag,
488 typename Rest>
489 void mcgregor_common_subgraphs
490 (const GraphFirst& graph1,
491 const GraphSecond& graph2,
492 bool only_connected_subgraphs,
493 SubGraphCallback user_callback,
494 const bgl_named_params<Param, Tag, Rest>& params)
495 {
496
497 detail::mcgregor_common_subgraphs_internal_init
498 (graph1, graph2,
499 choose_const_pmap(get_param(params, vertex_index1),
500 graph1, vertex_index),
501 choose_const_pmap(get_param(params, vertex_index2),
502 graph2, vertex_index),
503 choose_param(get_param(params, edges_equivalent_t()),
504 always_equivalent()),
505 choose_param(get_param(params, vertices_equivalent_t()),
506 always_equivalent()),
507 only_connected_subgraphs, user_callback);
508 }
509
510 // ==========================================================================
511
512 namespace detail {
513
514 // Binary function object that intercepts subgraphs from
515 // mcgregor_common_subgraphs_internal and maintains a cache of
516 // unique subgraphs. The user callback is invoked for each unique
517 // subgraph.
518 template <typename GraphFirst,
519 typename GraphSecond,
520 typename VertexIndexMapFirst,
521 typename VertexIndexMapSecond,
522 typename SubGraphCallback>
523 struct unique_subgraph_interceptor {
524
525 typedef typename graph_traits<GraphFirst>::vertices_size_type
526 VertexSizeFirst;
527
528 typedef mcgregor_common_subgraph_traits<GraphFirst, GraphSecond,
529 VertexIndexMapFirst, VertexIndexMapSecond> SubGraphTraits;
530
531 typedef typename SubGraphTraits::correspondence_map_first_to_second_type
532 CachedCorrespondenceMapFirstToSecond;
533
534 typedef typename SubGraphTraits::correspondence_map_second_to_first_type
535 CachedCorrespondenceMapSecondToFirst;
536
537 typedef std::pair<VertexSizeFirst,
538 std::pair<CachedCorrespondenceMapFirstToSecond,
539 CachedCorrespondenceMapSecondToFirst> > SubGraph;
540
541 typedef std::vector<SubGraph> SubGraphList;
542
543 unique_subgraph_interceptor(const GraphFirst& graph1,
544 const GraphSecond& graph2,
545 const VertexIndexMapFirst vindex_map1,
546 const VertexIndexMapSecond vindex_map2,
547 SubGraphCallback user_callback) :
548 m_graph1(graph1), m_graph2(graph2),
549 m_vindex_map1(vindex_map1), m_vindex_map2(vindex_map2),
550 m_subgraphs(make_shared<SubGraphList>()),
551 m_user_callback(user_callback) { }
552
553 template <typename CorrespondenceMapFirstToSecond,
554 typename CorrespondenceMapSecondToFirst>
555 bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
556 CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
557 VertexSizeFirst subgraph_size) {
558
559 for (typename SubGraphList::const_iterator
560 subgraph_iter = m_subgraphs->begin();
561 subgraph_iter != m_subgraphs->end();
562 ++subgraph_iter) {
563
564 SubGraph subgraph_cached = *subgraph_iter;
565
566 // Compare subgraph sizes
567 if (subgraph_size != subgraph_cached.first) {
568 continue;
569 }
570
571 if (!are_property_maps_different(correspondence_map_1_to_2,
572 subgraph_cached.second.first,
573 m_graph1)) {
574
575 // New subgraph is a duplicate
576 return (true);
577 }
578 }
579
580 // Subgraph is unique, so make a cached copy
581 CachedCorrespondenceMapFirstToSecond
582 new_subgraph_1_to_2 = CachedCorrespondenceMapFirstToSecond
583 (num_vertices(m_graph1), m_vindex_map1);
584
585 CachedCorrespondenceMapSecondToFirst
586 new_subgraph_2_to_1 = CorrespondenceMapSecondToFirst
587 (num_vertices(m_graph2), m_vindex_map2);
588
589 BGL_FORALL_VERTICES_T(vertex1, m_graph1, GraphFirst) {
590 put(new_subgraph_1_to_2, vertex1, get(correspondence_map_1_to_2, vertex1));
591 }
592
593 BGL_FORALL_VERTICES_T(vertex2, m_graph2, GraphFirst) {
594 put(new_subgraph_2_to_1, vertex2, get(correspondence_map_2_to_1, vertex2));
595 }
596
597 m_subgraphs->push_back(std::make_pair(subgraph_size,
598 std::make_pair(new_subgraph_1_to_2,
599 new_subgraph_2_to_1)));
600
601 return (m_user_callback(correspondence_map_1_to_2,
602 correspondence_map_2_to_1,
603 subgraph_size));
604 }
605
606 private:
607 const GraphFirst& m_graph1;
608 const GraphFirst& m_graph2;
609 const VertexIndexMapFirst m_vindex_map1;
610 const VertexIndexMapSecond m_vindex_map2;
611 shared_ptr<SubGraphList> m_subgraphs;
612 SubGraphCallback m_user_callback;
613 };
614
615 } // namespace detail
616
617 // Enumerates all unique common subgraphs between graph1 and graph2.
618 // The user callback is invoked for each unique subgraph as they are
619 // discovered.
620 template <typename GraphFirst,
621 typename GraphSecond,
622 typename VertexIndexMapFirst,
623 typename VertexIndexMapSecond,
624 typename EdgeEquivalencePredicate,
625 typename VertexEquivalencePredicate,
626 typename SubGraphCallback>
627 void mcgregor_common_subgraphs_unique
628 (const GraphFirst& graph1,
629 const GraphSecond& graph2,
630 const VertexIndexMapFirst vindex_map1,
631 const VertexIndexMapSecond vindex_map2,
632 EdgeEquivalencePredicate edges_equivalent,
633 VertexEquivalencePredicate vertices_equivalent,
634 bool only_connected_subgraphs,
635 SubGraphCallback user_callback)
636 {
637 detail::unique_subgraph_interceptor<GraphFirst, GraphSecond,
638 VertexIndexMapFirst, VertexIndexMapSecond,
639 SubGraphCallback> unique_callback
640 (graph1, graph2,
641 vindex_map1, vindex_map2,
642 user_callback);
643
644 detail::mcgregor_common_subgraphs_internal_init
645 (graph1, graph2,
646 vindex_map1, vindex_map2,
647 edges_equivalent, vertices_equivalent,
648 only_connected_subgraphs, unique_callback);
649 }
650
651 // Variant of mcgregor_common_subgraphs_unique with all default
652 // parameters.
653 template <typename GraphFirst,
654 typename GraphSecond,
655 typename SubGraphCallback>
656 void mcgregor_common_subgraphs_unique
657 (const GraphFirst& graph1,
658 const GraphSecond& graph2,
659 bool only_connected_subgraphs,
660 SubGraphCallback user_callback)
661 {
662 mcgregor_common_subgraphs_unique
663 (graph1, graph2,
664 get(vertex_index, graph1), get(vertex_index, graph2),
665 always_equivalent(), always_equivalent(),
666 only_connected_subgraphs, user_callback);
667 }
668
669 // Named parameter variant of mcgregor_common_subgraphs_unique
670 template <typename GraphFirst,
671 typename GraphSecond,
672 typename SubGraphCallback,
673 typename Param,
674 typename Tag,
675 typename Rest>
676 void mcgregor_common_subgraphs_unique
677 (const GraphFirst& graph1,
678 const GraphSecond& graph2,
679 bool only_connected_subgraphs,
680 SubGraphCallback user_callback,
681 const bgl_named_params<Param, Tag, Rest>& params)
682 {
683 mcgregor_common_subgraphs_unique
684 (graph1, graph2,
685 choose_const_pmap(get_param(params, vertex_index1),
686 graph1, vertex_index),
687 choose_const_pmap(get_param(params, vertex_index2),
688 graph2, vertex_index),
689 choose_param(get_param(params, edges_equivalent_t()),
690 always_equivalent()),
691 choose_param(get_param(params, vertices_equivalent_t()),
692 always_equivalent()),
693 only_connected_subgraphs, user_callback);
694 }
695
696 // ==========================================================================
697
698 namespace detail {
699
700 // Binary function object that intercepts subgraphs from
701 // mcgregor_common_subgraphs_internal and maintains a cache of the
702 // largest subgraphs.
703 template <typename GraphFirst,
704 typename GraphSecond,
705 typename VertexIndexMapFirst,
706 typename VertexIndexMapSecond,
707 typename SubGraphCallback>
708 struct maximum_subgraph_interceptor {
709
710 typedef typename graph_traits<GraphFirst>::vertices_size_type
711 VertexSizeFirst;
712
713 typedef mcgregor_common_subgraph_traits<GraphFirst, GraphSecond,
714 VertexIndexMapFirst, VertexIndexMapSecond> SubGraphTraits;
715
716 typedef typename SubGraphTraits::correspondence_map_first_to_second_type
717 CachedCorrespondenceMapFirstToSecond;
718
719 typedef typename SubGraphTraits::correspondence_map_second_to_first_type
720 CachedCorrespondenceMapSecondToFirst;
721
722 typedef std::pair<VertexSizeFirst,
723 std::pair<CachedCorrespondenceMapFirstToSecond,
724 CachedCorrespondenceMapSecondToFirst> > SubGraph;
725
726 typedef std::vector<SubGraph> SubGraphList;
727
728 maximum_subgraph_interceptor(const GraphFirst& graph1,
729 const GraphSecond& graph2,
730 const VertexIndexMapFirst vindex_map1,
731 const VertexIndexMapSecond vindex_map2,
732 SubGraphCallback user_callback) :
733 m_graph1(graph1), m_graph2(graph2),
734 m_vindex_map1(vindex_map1), m_vindex_map2(vindex_map2),
735 m_subgraphs(make_shared<SubGraphList>()),
736 m_largest_size_so_far(make_shared<VertexSizeFirst>(0)),
737 m_user_callback(user_callback) { }
738
739 template <typename CorrespondenceMapFirstToSecond,
740 typename CorrespondenceMapSecondToFirst>
741 bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
742 CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
743 VertexSizeFirst subgraph_size) {
744
745 if (subgraph_size > *m_largest_size_so_far) {
746 m_subgraphs->clear();
747 *m_largest_size_so_far = subgraph_size;
748 }
749
750 if (subgraph_size == *m_largest_size_so_far) {
751
752 // Make a cached copy
753 CachedCorrespondenceMapFirstToSecond
754 new_subgraph_1_to_2 = CachedCorrespondenceMapFirstToSecond
755 (num_vertices(m_graph1), m_vindex_map1);
756
757 CachedCorrespondenceMapSecondToFirst
758 new_subgraph_2_to_1 = CachedCorrespondenceMapSecondToFirst
759 (num_vertices(m_graph2), m_vindex_map2);
760
761 BGL_FORALL_VERTICES_T(vertex1, m_graph1, GraphFirst) {
762 put(new_subgraph_1_to_2, vertex1, get(correspondence_map_1_to_2, vertex1));
763 }
764
765 BGL_FORALL_VERTICES_T(vertex2, m_graph2, GraphFirst) {
766 put(new_subgraph_2_to_1, vertex2, get(correspondence_map_2_to_1, vertex2));
767 }
768
769 m_subgraphs->push_back(std::make_pair(subgraph_size,
770 std::make_pair(new_subgraph_1_to_2,
771 new_subgraph_2_to_1)));
772 }
773
774 return (true);
775 }
776
777 void output_subgraphs() {
778 for (typename SubGraphList::const_iterator
779 subgraph_iter = m_subgraphs->begin();
780 subgraph_iter != m_subgraphs->end();
781 ++subgraph_iter) {
782
783 SubGraph subgraph_cached = *subgraph_iter;
784 m_user_callback(subgraph_cached.second.first,
785 subgraph_cached.second.second,
786 subgraph_cached.first);
787 }
788 }
789
790 private:
791 const GraphFirst& m_graph1;
792 const GraphFirst& m_graph2;
793 const VertexIndexMapFirst m_vindex_map1;
794 const VertexIndexMapSecond m_vindex_map2;
795 shared_ptr<SubGraphList> m_subgraphs;
796 shared_ptr<VertexSizeFirst> m_largest_size_so_far;
797 SubGraphCallback m_user_callback;
798 };
799
800 } // namespace detail
801
802 // Enumerates the largest common subgraphs found between graph1
803 // and graph2. Note that the ENTIRE search space is explored before
804 // user_callback is actually invoked.
805 template <typename GraphFirst,
806 typename GraphSecond,
807 typename VertexIndexMapFirst,
808 typename VertexIndexMapSecond,
809 typename EdgeEquivalencePredicate,
810 typename VertexEquivalencePredicate,
811 typename SubGraphCallback>
812 void mcgregor_common_subgraphs_maximum
813 (const GraphFirst& graph1,
814 const GraphSecond& graph2,
815 const VertexIndexMapFirst vindex_map1,
816 const VertexIndexMapSecond vindex_map2,
817 EdgeEquivalencePredicate edges_equivalent,
818 VertexEquivalencePredicate vertices_equivalent,
819 bool only_connected_subgraphs,
820 SubGraphCallback user_callback)
821 {
822 detail::maximum_subgraph_interceptor<GraphFirst, GraphSecond,
823 VertexIndexMapFirst, VertexIndexMapSecond, SubGraphCallback>
824 max_interceptor
825 (graph1, graph2, vindex_map1, vindex_map2, user_callback);
826
827 detail::mcgregor_common_subgraphs_internal_init
828 (graph1, graph2,
829 vindex_map1, vindex_map2,
830 edges_equivalent, vertices_equivalent,
831 only_connected_subgraphs, max_interceptor);
832
833 // Only output the largest subgraphs
834 max_interceptor.output_subgraphs();
835 }
836
837 // Variant of mcgregor_common_subgraphs_maximum with all default
838 // parameters.
839 template <typename GraphFirst,
840 typename GraphSecond,
841 typename SubGraphCallback>
842 void mcgregor_common_subgraphs_maximum
843 (const GraphFirst& graph1,
844 const GraphSecond& graph2,
845 bool only_connected_subgraphs,
846 SubGraphCallback user_callback)
847 {
848 mcgregor_common_subgraphs_maximum
849 (graph1, graph2,
850 get(vertex_index, graph1), get(vertex_index, graph2),
851 always_equivalent(), always_equivalent(),
852 only_connected_subgraphs, user_callback);
853 }
854
855 // Named parameter variant of mcgregor_common_subgraphs_maximum
856 template <typename GraphFirst,
857 typename GraphSecond,
858 typename SubGraphCallback,
859 typename Param,
860 typename Tag,
861 typename Rest>
862 void mcgregor_common_subgraphs_maximum
863 (const GraphFirst& graph1,
864 const GraphSecond& graph2,
865 bool only_connected_subgraphs,
866 SubGraphCallback user_callback,
867 const bgl_named_params<Param, Tag, Rest>& params)
868 {
869 mcgregor_common_subgraphs_maximum
870 (graph1, graph2,
871 choose_const_pmap(get_param(params, vertex_index1),
872 graph1, vertex_index),
873 choose_const_pmap(get_param(params, vertex_index2),
874 graph2, vertex_index),
875 choose_param(get_param(params, edges_equivalent_t()),
876 always_equivalent()),
877 choose_param(get_param(params, vertices_equivalent_t()),
878 always_equivalent()),
879 only_connected_subgraphs, user_callback);
880 }
881
882 // ==========================================================================
883
884 namespace detail {
885
886 // Binary function object that intercepts subgraphs from
887 // mcgregor_common_subgraphs_internal and maintains a cache of the
888 // largest, unique subgraphs.
889 template <typename GraphFirst,
890 typename GraphSecond,
891 typename VertexIndexMapFirst,
892 typename VertexIndexMapSecond,
893 typename SubGraphCallback>
894 struct unique_maximum_subgraph_interceptor {
895
896 typedef typename graph_traits<GraphFirst>::vertices_size_type
897 VertexSizeFirst;
898
899 typedef mcgregor_common_subgraph_traits<GraphFirst, GraphSecond,
900 VertexIndexMapFirst, VertexIndexMapSecond> SubGraphTraits;
901
902 typedef typename SubGraphTraits::correspondence_map_first_to_second_type
903 CachedCorrespondenceMapFirstToSecond;
904
905 typedef typename SubGraphTraits::correspondence_map_second_to_first_type
906 CachedCorrespondenceMapSecondToFirst;
907
908 typedef std::pair<VertexSizeFirst,
909 std::pair<CachedCorrespondenceMapFirstToSecond,
910 CachedCorrespondenceMapSecondToFirst> > SubGraph;
911
912 typedef std::vector<SubGraph> SubGraphList;
913
914 unique_maximum_subgraph_interceptor(const GraphFirst& graph1,
915 const GraphSecond& graph2,
916 const VertexIndexMapFirst vindex_map1,
917 const VertexIndexMapSecond vindex_map2,
918 SubGraphCallback user_callback) :
919 m_graph1(graph1), m_graph2(graph2),
920 m_vindex_map1(vindex_map1), m_vindex_map2(vindex_map2),
921 m_subgraphs(make_shared<SubGraphList>()),
922 m_largest_size_so_far(make_shared<VertexSizeFirst>(0)),
923 m_user_callback(user_callback) { }
924
925 template <typename CorrespondenceMapFirstToSecond,
926 typename CorrespondenceMapSecondToFirst>
927 bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
928 CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
929 VertexSizeFirst subgraph_size) {
930
931 if (subgraph_size > *m_largest_size_so_far) {
932 m_subgraphs->clear();
933 *m_largest_size_so_far = subgraph_size;
934 }
935
936 if (subgraph_size == *m_largest_size_so_far) {
937
938 // Check if subgraph is unique
939 for (typename SubGraphList::const_iterator
940 subgraph_iter = m_subgraphs->begin();
941 subgraph_iter != m_subgraphs->end();
942 ++subgraph_iter) {
943
944 SubGraph subgraph_cached = *subgraph_iter;
945
946 if (!are_property_maps_different(correspondence_map_1_to_2,
947 subgraph_cached.second.first,
948 m_graph1)) {
949
950 // New subgraph is a duplicate
951 return (true);
952 }
953 }
954
955 // Subgraph is unique, so make a cached copy
956 CachedCorrespondenceMapFirstToSecond
957 new_subgraph_1_to_2 = CachedCorrespondenceMapFirstToSecond
958 (num_vertices(m_graph1), m_vindex_map1);
959
960 CachedCorrespondenceMapSecondToFirst
961 new_subgraph_2_to_1 = CachedCorrespondenceMapSecondToFirst
962 (num_vertices(m_graph2), m_vindex_map2);
963
964 BGL_FORALL_VERTICES_T(vertex1, m_graph1, GraphFirst) {
965 put(new_subgraph_1_to_2, vertex1, get(correspondence_map_1_to_2, vertex1));
966 }
967
968 BGL_FORALL_VERTICES_T(vertex2, m_graph2, GraphFirst) {
969 put(new_subgraph_2_to_1, vertex2, get(correspondence_map_2_to_1, vertex2));
970 }
971
972 m_subgraphs->push_back(std::make_pair(subgraph_size,
973 std::make_pair(new_subgraph_1_to_2,
974 new_subgraph_2_to_1)));
975 }
976
977 return (true);
978 }
979
980 void output_subgraphs() {
981 for (typename SubGraphList::const_iterator
982 subgraph_iter = m_subgraphs->begin();
983 subgraph_iter != m_subgraphs->end();
984 ++subgraph_iter) {
985
986 SubGraph subgraph_cached = *subgraph_iter;
987 m_user_callback(subgraph_cached.second.first,
988 subgraph_cached.second.second,
989 subgraph_cached.first);
990 }
991 }
992
993 private:
994 const GraphFirst& m_graph1;
995 const GraphFirst& m_graph2;
996 const VertexIndexMapFirst m_vindex_map1;
997 const VertexIndexMapSecond m_vindex_map2;
998 shared_ptr<SubGraphList> m_subgraphs;
999 shared_ptr<VertexSizeFirst> m_largest_size_so_far;
1000 SubGraphCallback m_user_callback;
1001 };
1002
1003 } // namespace detail
1004
1005 // Enumerates the largest, unique common subgraphs found between
1006 // graph1 and graph2. Note that the ENTIRE search space is explored
1007 // before user_callback is actually invoked.
1008 template <typename GraphFirst,
1009 typename GraphSecond,
1010 typename VertexIndexMapFirst,
1011 typename VertexIndexMapSecond,
1012 typename EdgeEquivalencePredicate,
1013 typename VertexEquivalencePredicate,
1014 typename SubGraphCallback>
1015 void mcgregor_common_subgraphs_maximum_unique
1016 (const GraphFirst& graph1,
1017 const GraphSecond& graph2,
1018 const VertexIndexMapFirst vindex_map1,
1019 const VertexIndexMapSecond vindex_map2,
1020 EdgeEquivalencePredicate edges_equivalent,
1021 VertexEquivalencePredicate vertices_equivalent,
1022 bool only_connected_subgraphs,
1023 SubGraphCallback user_callback)
1024 {
1025 detail::unique_maximum_subgraph_interceptor<GraphFirst, GraphSecond,
1026 VertexIndexMapFirst, VertexIndexMapSecond, SubGraphCallback>
1027 unique_max_interceptor
1028 (graph1, graph2, vindex_map1, vindex_map2, user_callback);
1029
1030 detail::mcgregor_common_subgraphs_internal_init
1031 (graph1, graph2,
1032 vindex_map1, vindex_map2,
1033 edges_equivalent, vertices_equivalent,
1034 only_connected_subgraphs, unique_max_interceptor);
1035
1036 // Only output the largest, unique subgraphs
1037 unique_max_interceptor.output_subgraphs();
1038 }
1039
1040 // Variant of mcgregor_common_subgraphs_maximum_unique with all default parameters
1041 template <typename GraphFirst,
1042 typename GraphSecond,
1043 typename SubGraphCallback>
1044 void mcgregor_common_subgraphs_maximum_unique
1045 (const GraphFirst& graph1,
1046 const GraphSecond& graph2,
1047 bool only_connected_subgraphs,
1048 SubGraphCallback user_callback)
1049 {
1050
1051 mcgregor_common_subgraphs_maximum_unique
1052 (graph1, graph2,
1053 get(vertex_index, graph1), get(vertex_index, graph2),
1054 always_equivalent(), always_equivalent(),
1055 only_connected_subgraphs, user_callback);
1056 }
1057
1058 // Named parameter variant of
1059 // mcgregor_common_subgraphs_maximum_unique
1060 template <typename GraphFirst,
1061 typename GraphSecond,
1062 typename SubGraphCallback,
1063 typename Param,
1064 typename Tag,
1065 typename Rest>
1066 void mcgregor_common_subgraphs_maximum_unique
1067 (const GraphFirst& graph1,
1068 const GraphSecond& graph2,
1069 bool only_connected_subgraphs,
1070 SubGraphCallback user_callback,
1071 const bgl_named_params<Param, Tag, Rest>& params)
1072 {
1073 mcgregor_common_subgraphs_maximum_unique
1074 (graph1, graph2,
1075 choose_const_pmap(get_param(params, vertex_index1),
1076 graph1, vertex_index),
1077 choose_const_pmap(get_param(params, vertex_index2),
1078 graph2, vertex_index),
1079 choose_param(get_param(params, edges_equivalent_t()),
1080 always_equivalent()),
1081 choose_param(get_param(params, vertices_equivalent_t()),
1082 always_equivalent()),
1083 only_connected_subgraphs, user_callback);
1084 }
1085
1086 // ==========================================================================
1087
1088 // Fills a membership map (vertex -> bool) using the information
1089 // present in correspondence_map_1_to_2. Every vertex in a
1090 // membership map will have a true value only if it is not
1091 // associated with a null vertex in the correspondence map.
1092 template <typename GraphSecond,
1093 typename GraphFirst,
1094 typename CorrespondenceMapFirstToSecond,
1095 typename MembershipMapFirst>
1096 void fill_membership_map
1097 (const GraphFirst& graph1,
1098 const CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
1099 MembershipMapFirst membership_map1) {
1100
1101 BGL_FORALL_VERTICES_T(vertex1, graph1, GraphFirst) {
1102 put(membership_map1, vertex1,
1103 get(correspondence_map_1_to_2, vertex1) != graph_traits<GraphSecond>::null_vertex());
1104 }
1105
1106 }
1107
1108 // Traits associated with a membership map filtered graph. Provided
1109 // for convenience to access graph and vertex filter types.
1110 template <typename Graph,
1111 typename MembershipMap>
1112 struct membership_filtered_graph_traits {
1113 typedef property_map_filter<MembershipMap> vertex_filter_type;
1114 typedef filtered_graph<Graph, keep_all, vertex_filter_type> graph_type;
1115 };
1116
1117 // Returns a filtered sub-graph of graph whose edge and vertex
1118 // inclusion is dictated by membership_map.
1119 template <typename Graph,
1120 typename MembershipMap>
1121 typename membership_filtered_graph_traits<Graph, MembershipMap>::graph_type
1122 make_membership_filtered_graph
1123 (const Graph& graph,
1124 MembershipMap& membership_map) {
1125
1126 typedef membership_filtered_graph_traits<Graph, MembershipMap> MFGTraits;
1127 typedef typename MFGTraits::graph_type MembershipFilteredGraph;
1128
1129 typename MFGTraits::vertex_filter_type v_filter(membership_map);
1130
1131 return (MembershipFilteredGraph(graph, keep_all(), v_filter));
1132
1133 }
1134
1135} // namespace boost
1136
1137#endif // BOOST_GRAPH_MCGREGOR_COMMON_SUBGRAPHS_HPP
1138

source code of boost/boost/graph/mcgregor_common_subgraphs.hpp