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 | 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 | |