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 property_map_equivalentboost::property_map_equivalent56 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> operator ()boost::property_map_equivalent63 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> make_property_map_equivalent(const PropertyMapFirst property_map1,const PropertyMapSecond property_map2)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> operator ()boost::always_equivalent92 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> 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)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> 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)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> 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)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> 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)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> mcgregor_common_subgraphs(const GraphFirst & graph1,const GraphSecond & graph2,bool only_connected_subgraphs,SubGraphCallback user_callback)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> mcgregor_common_subgraphs(const GraphFirst & graph1,const GraphSecond & graph2,bool only_connected_subgraphs,SubGraphCallback user_callback,const bgl_named_params<Param,Tag,Rest> & params)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 unique_subgraph_interceptorboost::detail::unique_subgraph_interceptor543 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> operator ()boost::detail::unique_subgraph_interceptor555 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> 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)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> mcgregor_common_subgraphs_unique(const GraphFirst & graph1,const GraphSecond & graph2,bool only_connected_subgraphs,SubGraphCallback user_callback)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> 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 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 maximum_subgraph_interceptorboost::detail::maximum_subgraph_interceptor728 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> operator ()boost::detail::maximum_subgraph_interceptor741 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 output_subgraphsboost::detail::maximum_subgraph_interceptor777 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> 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)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> mcgregor_common_subgraphs_maximum(const GraphFirst & graph1,const GraphSecond & graph2,bool only_connected_subgraphs,SubGraphCallback user_callback)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> 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)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 unique_maximum_subgraph_interceptorboost::detail::unique_maximum_subgraph_interceptor914 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> operator ()boost::detail::unique_maximum_subgraph_interceptor927 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 output_subgraphsboost::detail::unique_maximum_subgraph_interceptor980 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> 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)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> mcgregor_common_subgraphs_maximum_unique(const GraphFirst & graph1,const GraphSecond & graph2,bool only_connected_subgraphs,SubGraphCallback user_callback)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> 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)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> fill_membership_map(const GraphFirst & graph1,const CorrespondenceMapFirstToSecond correspondence_map_1_to_2,MembershipMapFirst membership_map1)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 make_membership_filtered_graph(const Graph & graph,MembershipMap & membership_map)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