]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |