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