boost/graph/mcgregor_common_subgraphs.hpp

0001 //=======================================================================
0002 // Copyright 2009 Trustees of Indiana University.
0003 // Authors: Michael Hansen, Andrew Lumsdaine
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //=======================================================================
0009
0010 #ifndef BOOST_GRAPH_MCGREGOR_COMMON_SUBGRAPHS_HPP
0011 #define BOOST_GRAPH_MCGREGOR_COMMON_SUBGRAPHS_HPP
0012
0013 #include <algorithm>
0014 #include <vector>
0015 #include <stack>
0016
0017 #include <boost/make_shared.hpp>
0018 #include <boost/graph/adjacency_list.hpp>
0019 #include <boost/graph/filtered_graph.hpp>
0020 #include <boost/graph/graph_utility.hpp>
0021 #include <boost/graph/iteration_macros.hpp>
0022 #include <boost/graph/properties.hpp>
0023 #include <boost/property_map/shared_array_property_map.hpp>
0024
0025 namespace boost
0026 {
0027
0028 namespace detail
0029 {
0030
0031     // Traits associated with common subgraphs, used mainly to keep a
0032     // consistent type for the correspondence maps.
0033     template < typename GraphFirst, typename GraphSecond,
0034         typename VertexIndexMapFirst, typename VertexIndexMapSecond >
0035     struct mcgregor_common_subgraph_traits
0036     {
0037         typedef typename graph_traits< GraphFirst >::vertex_descriptor
0038             vertex_first_type;
0039         typedef typename graph_traits< GraphSecond >::vertex_descriptor
0040             vertex_second_type;
0041
0042         typedef shared_array_property_map< vertex_second_type,
0043             VertexIndexMapFirst >
0044             correspondence_map_first_to_second_type;
0045
0046         typedef shared_array_property_map< vertex_first_type,
0047             VertexIndexMapSecond >
0048             correspondence_map_second_to_first_type;
0049     };
0050
0051 } // namespace detail
0052
0053 // ==========================================================================
0054
0055 // Binary function object that returns true if the values for item1
0056 // in property_map1 and item2 in property_map2 are equivalent.
0057 template < typename PropertyMapFirst, typename PropertyMapSecond >
0058 struct property_map_equivalent
0059 {
0060
0061     property_map_equivalent(const PropertyMapFirst property_map1,
0062         const PropertyMapSecond property_map2)
0063     : m_property_map1(property_map1), m_property_map2(property_map2)
0064     {
0065     }
0066
0067     template < typename ItemFirst, typename ItemSecond >
0068     bool operator()(const ItemFirst item1, const ItemSecond item2)
0069     {
0070         return (get(m_property_map1, item1) == get(m_property_map2, item2));
0071     }
0072
0073 private:
0074     const PropertyMapFirst m_property_map1;
0075     const PropertyMapSecond m_property_map2;
0076 };
0077
0078 // Returns a property_map_equivalent object that compares the values
0079 // of property_map1 and property_map2.
0080 template < typename PropertyMapFirst, typename PropertyMapSecond >
0081 property_map_equivalent< PropertyMapFirst, PropertyMapSecond >
0082 make_property_map_equivalent(
0083     const PropertyMapFirst property_map1, const PropertyMapSecond property_map2)
0084 {
0085
0086     return (property_map_equivalent< PropertyMapFirst, PropertyMapSecond >(
0087         property_map1, property_map2));
0088 }
0089
0090 // Binary function object that always returns true.  Used when
0091 // vertices or edges are always equivalent (i.e. have no labels).
0092 struct always_equivalent
0093 {
0094
0095     template < typename ItemFirst, typename ItemSecond >
0096     bool operator()(const ItemFirst&, const ItemSecond&)
0097     {
0098         return (true);
0099     }
0100 };
0101
0102 // ==========================================================================
0103
0104 namespace detail
0105 {
0106
0107     // Return true if new_vertex1 and new_vertex2 can extend the
0108     // subgraph represented by correspondence_map_1_to_2 and
0109     // correspondence_map_2_to_1.  The vertices_equivalent and
0110     // edges_equivalent predicates are used to test vertex and edge
0111     // equivalency between the two graphs.
0112     template < typename GraphFirst, typename GraphSecond,
0113         typename CorrespondenceMapFirstToSecond,
0114         typename CorrespondenceMapSecondToFirst,
0115         typename EdgeEquivalencePredicate, typename VertexEquivalencePredicate >
0116     bool can_extend_graph(const GraphFirst& graph1, const GraphSecond& graph2,
0117         CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
0118         CorrespondenceMapSecondToFirst /*correspondence_map_2_to_1*/,
0119         typename graph_traits< GraphFirst >::vertices_size_type subgraph_size,
0120         typename graph_traits< GraphFirst >::vertex_descriptor new_vertex1,
0121         typename graph_traits< GraphSecond >::vertex_descriptor new_vertex2,
0122         EdgeEquivalencePredicate edges_equivalent,
0123         VertexEquivalencePredicate vertices_equivalent,
0124         bool only_connected_subgraphs)
0125     {
0126         typedef typename graph_traits< GraphSecond >::vertex_descriptor
0127             VertexSecond;
0128
0129         typedef typename graph_traits< GraphFirst >::edge_descriptor EdgeFirst;
0130         typedef
0131             typename graph_traits< GraphSecond >::edge_descriptor EdgeSecond;
0132
0133         // Check vertex equality
0134         if (!vertices_equivalent(new_vertex1, new_vertex2))
0135         {
0136             return (false);
0137         }
0138
0139         // Vertices match and graph is empty, so we can extend the subgraph
0140         if (subgraph_size == 0)
0141         {
0142             return (true);
0143         }
0144
0145         bool has_one_edge = false;
0146
0147         // Verify edges with existing sub-graph
0148         BGL_FORALL_VERTICES_T(existing_vertex1, graph1, GraphFirst)
0149         {
0150
0151             VertexSecond existing_vertex2
0152                 = get(correspondence_map_1_to_2, existing_vertex1);
0153
0154             // Skip unassociated vertices
0155             if (existing_vertex2 == graph_traits< GraphSecond >::null_vertex())
0156             {
0157                 continue;
0158             }
0159
0160             // NOTE: This will not work with parallel edges, since the
0161             // first matching edge is always chosen.
0162             EdgeFirst edge_to_new1, edge_from_new1;
0163             bool edge_to_new_exists1 = false, edge_from_new_exists1 = false;
0164
0165             EdgeSecond edge_to_new2, edge_from_new2;
0166             bool edge_to_new_exists2 = false, edge_from_new_exists2 = false;
0167
0168             // Search for edge from existing to new vertex (graph1)
0169             BGL_FORALL_OUTEDGES_T(existing_vertex1, edge1, graph1, GraphFirst)
0170             {
0171                 if (target(edge1, graph1) == new_vertex1)
0172                 {
0173                     edge_to_new1 = edge1;
0174                     edge_to_new_exists1 = true;
0175                     break;
0176                 }
0177             }
0178
0179             // Search for edge from existing to new vertex (graph2)
0180             BGL_FORALL_OUTEDGES_T(existing_vertex2, edge2, graph2, GraphSecond)
0181             {
0182                 if (target(edge2, graph2) == new_vertex2)
0183                 {
0184                     edge_to_new2 = edge2;
0185                     edge_to_new_exists2 = true;
0186                     break;
0187                 }
0188             }
0189
0190             // Make sure edges from existing to new vertices are equivalent
0191             if ((edge_to_new_exists1 != edge_to_new_exists2)
0192                 || ((edge_to_new_exists1 && edge_to_new_exists2)
0193                     && !edges_equivalent(edge_to_new1, edge_to_new2)))
0194             {
0195
0196                 return (false);
0197             }
0198
0199             bool is_undirected1 = is_undirected(graph1),
0200                  is_undirected2 = is_undirected(graph2);
0201
0202             if (is_undirected1 && is_undirected2)
0203             {
0204
0205                 // Edge in both graphs exists and both graphs are undirected
0206                 if (edge_to_new_exists1 && edge_to_new_exists2)
0207                 {
0208                     has_one_edge = true;
0209                 }
0210
0211                 continue;
0212             }
0213             else
0214             {
0215
0216                 if (!is_undirected1)
0217                 {
0218
0219                     // Search for edge from new to existing vertex (graph1)
0220                     BGL_FORALL_OUTEDGES_T(
0221                         new_vertex1, edge1, graph1, GraphFirst)
0222                     {
0223                         if (target(edge1, graph1) == existing_vertex1)
0224                         {
0225                             edge_from_new1 = edge1;
0226                             edge_from_new_exists1 = true;
0227                             break;
0228                         }
0229                     }
0230                 }
0231
0232                 if (!is_undirected2)
0233                 {
0234
0235                     // Search for edge from new to existing vertex (graph2)
0236                     BGL_FORALL_OUTEDGES_T(
0237                         new_vertex2, edge2, graph2, GraphSecond)
0238                     {
0239                         if (target(edge2, graph2) == existing_vertex2)
0240                         {
0241                             edge_from_new2 = edge2;
0242                             edge_from_new_exists2 = true;
0243                             break;
0244                         }
0245                     }
0246                 }
0247
0248                 // Make sure edges from new to existing vertices are equivalent
0249                 if ((edge_from_new_exists1 != edge_from_new_exists2)
0250                     || ((edge_from_new_exists1 && edge_from_new_exists2)
0251                         && !edges_equivalent(edge_from_new1, edge_from_new2)))
0252                 {
0253
0254                     return (false);
0255                 }
0256
0257                 if ((edge_from_new_exists1 && edge_from_new_exists2)
0258                     || (edge_to_new_exists1 && edge_to_new_exists2))
0259                 {
0260                     has_one_edge = true;
0261                 }
0262
0263             } // else
0264
0265         } // BGL_FORALL_VERTICES_T
0266
0267         // Make sure new vertices are connected to the existing subgraph
0268         if (only_connected_subgraphs && !has_one_edge)
0269         {
0270             return (false);
0271         }
0272
0273         return (true);
0274     }
0275
0276     // Recursive method that does a depth-first search in the space of
0277     // potential subgraphs.  At each level, every new vertex pair from
0278     // both graphs is tested to see if it can extend the current
0279     // subgraph.  If so, the subgraph is output to subgraph_callback
0280     // in the form of two correspondence maps (one for each graph).
0281     // Returning false from subgraph_callback will terminate the
0282     // search.  Function returns true if the entire search space was
0283     // explored.
0284     template < typename GraphFirst, typename GraphSecond,
0285         typename VertexIndexMapFirst, typename VertexIndexMapSecond,
0286         typename CorrespondenceMapFirstToSecond,
0287         typename CorrespondenceMapSecondToFirst, typename VertexStackFirst,
0288         typename EdgeEquivalencePredicate, typename VertexEquivalencePredicate,
0289         typename SubGraphInternalCallback >
0290     bool mcgregor_common_subgraphs_internal(const GraphFirst& graph1,
0291         const GraphSecond& graph2, const VertexIndexMapFirst& vindex_map1,
0292         const VertexIndexMapSecond& vindex_map2,
0293         CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
0294         CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
0295         VertexStackFirst& vertex_stack1,
0296         EdgeEquivalencePredicate edges_equivalent,
0297         VertexEquivalencePredicate vertices_equivalent,
0298         bool only_connected_subgraphs,
0299         SubGraphInternalCallback subgraph_callback)
0300     {
0301         typedef
0302             typename graph_traits< GraphFirst >::vertex_descriptor VertexFirst;
0303         typedef typename graph_traits< GraphSecond >::vertex_descriptor
0304             VertexSecond;
0305         typedef typename graph_traits< GraphFirst >::vertices_size_type
0306             VertexSizeFirst;
0307
0308         // Get iterators for vertices from both graphs
0309         typename graph_traits< GraphFirst >::vertex_iterator vertex1_iter,
0310             vertex1_end;
0311
0312         typename graph_traits< GraphSecond >::vertex_iterator vertex2_begin,
0313             vertex2_end, vertex2_iter;
0314
0315         boost::tie(vertex1_iter, vertex1_end) = vertices(graph1);
0316         boost::tie(vertex2_begin, vertex2_end) = vertices(graph2);
0317         vertex2_iter = vertex2_begin;
0318
0319         // Iterate until all vertices have been visited
0320         BGL_FORALL_VERTICES_T(new_vertex1, graph1, GraphFirst)
0321         {
0322
0323             VertexSecond existing_vertex2
0324                 = get(correspondence_map_1_to_2, new_vertex1);
0325
0326             // Skip already matched vertices in first graph
0327             if (existing_vertex2 != graph_traits< GraphSecond >::null_vertex())
0328             {
0329                 continue;
0330             }
0331
0332             BGL_FORALL_VERTICES_T(new_vertex2, graph2, GraphSecond)
0333             {
0334
0335                 VertexFirst existing_vertex1
0336                     = get(correspondence_map_2_to_1, new_vertex2);
0337
0338                 // Skip already matched vertices in second graph
0339                 if (existing_vertex1
0340                     != graph_traits< GraphFirst >::null_vertex())
0341                 {
0342                     continue;
0343                 }
0344
0345                 // Check if current sub-graph can be extended with the matched
0346                 // vertex pair
0347                 if (can_extend_graph(graph1, graph2, correspondence_map_1_to_2,
0348                         correspondence_map_2_to_1,
0349                         (VertexSizeFirst)vertex_stack1.size(), new_vertex1,
0350                         new_vertex2, edges_equivalent, vertices_equivalent,
0351                         only_connected_subgraphs))
0352                 {
0353
0354                     // Keep track of old graph size for restoring later
0355                     VertexSizeFirst old_graph_size
0356                         = (VertexSizeFirst)vertex_stack1.size(),
0357                         new_graph_size = old_graph_size + 1;
0358
0359                     // Extend subgraph
0360                     put(correspondence_map_1_to_2, new_vertex1, new_vertex2);
0361                     put(correspondence_map_2_to_1, new_vertex2, new_vertex1);
0362                     vertex_stack1.push(new_vertex1);
0363
0364                     // Returning false from the callback will cancel iteration
0365                     if (!subgraph_callback(correspondence_map_1_to_2,
0366                             correspondence_map_2_to_1, new_graph_size))
0367                     {
0368                         return (false);
0369                     }
0370
0371                     // Depth-first search into the state space of possible
0372                     // sub-graphs
0373                     bool continue_iteration
0374                         = mcgregor_common_subgraphs_internal(graph1, graph2,
0375                             vindex_map1, vindex_map2, correspondence_map_1_to_2,
0376                             correspondence_map_2_to_1, vertex_stack1,
0377                             edges_equivalent, vertices_equivalent,
0378                             only_connected_subgraphs, subgraph_callback);
0379
0380                     if (!continue_iteration)
0381                     {
0382                         return (false);
0383                     }
0384
0385                     // Restore previous state
0386                     if (vertex_stack1.size() > old_graph_size)
0387                     {
0388
0389                         VertexFirst stack_vertex1 = vertex_stack1.top();
0390                         VertexSecond stack_vertex2
0391                             = get(correspondence_map_1_to_2, stack_vertex1);
0392
0393                         // Contract subgraph
0394                         put(correspondence_map_1_to_2, stack_vertex1,
0395                             graph_traits< GraphSecond >::null_vertex());
0396
0397                         put(correspondence_map_2_to_1, stack_vertex2,
0398                             graph_traits< GraphFirst >::null_vertex());
0399
0400                         vertex_stack1.pop();
0401                     }
0402
0403                 } // if can_extend_graph
0404
0405             } // BGL_FORALL_VERTICES_T (graph2)
0406
0407         } // BGL_FORALL_VERTICES_T (graph1)
0408
0409         return (true);
0410     }
0411
0412     // Internal method that initializes blank correspondence maps and
0413     // a vertex stack for use in mcgregor_common_subgraphs_internal.
0414     template < typename GraphFirst, typename GraphSecond,
0415         typename VertexIndexMapFirst, typename VertexIndexMapSecond,
0416         typename EdgeEquivalencePredicate, typename VertexEquivalencePredicate,
0417         typename SubGraphInternalCallback >
0418     inline void mcgregor_common_subgraphs_internal_init(
0419         const GraphFirst& graph1, const GraphSecond& graph2,
0420         const VertexIndexMapFirst vindex_map1,
0421         const VertexIndexMapSecond vindex_map2,
0422         EdgeEquivalencePredicate edges_equivalent,
0423         VertexEquivalencePredicate vertices_equivalent,
0424         bool only_connected_subgraphs,
0425         SubGraphInternalCallback subgraph_callback)
0426     {
0427         typedef mcgregor_common_subgraph_traits< GraphFirst, GraphSecond,
0428             VertexIndexMapFirst, VertexIndexMapSecond >
0429             SubGraphTraits;
0430
0431         typename SubGraphTraits::correspondence_map_first_to_second_type
0432             correspondence_map_1_to_2(num_vertices(graph1), vindex_map1);
0433
0434         BGL_FORALL_VERTICES_T(vertex1, graph1, GraphFirst)
0435         {
0436             put(correspondence_map_1_to_2, vertex1,
0437                 graph_traits< GraphSecond >::null_vertex());
0438         }
0439
0440         typename SubGraphTraits::correspondence_map_second_to_first_type
0441             correspondence_map_2_to_1(num_vertices(graph2), vindex_map2);
0442
0443         BGL_FORALL_VERTICES_T(vertex2, graph2, GraphSecond)
0444         {
0445             put(correspondence_map_2_to_1, vertex2,
0446                 graph_traits< GraphFirst >::null_vertex());
0447         }
0448
0449         typedef
0450             typename graph_traits< GraphFirst >::vertex_descriptor VertexFirst;
0451
0452         std::stack< VertexFirst > vertex_stack1;
0453
0454         mcgregor_common_subgraphs_internal(graph1, graph2, vindex_map1,
0455             vindex_map2, correspondence_map_1_to_2, correspondence_map_2_to_1,
0456             vertex_stack1, edges_equivalent, vertices_equivalent,
0457             only_connected_subgraphs, subgraph_callback);
0458     }
0459
0460 } // namespace detail
0461
0462 // ==========================================================================
0463
0464 // Enumerates all common subgraphs present in graph1 and graph2.
0465 // Continues until the search space has been fully explored or false
0466 // is returned from user_callback.
0467 template < typename GraphFirst, typename GraphSecond,
0468     typename VertexIndexMapFirst, typename VertexIndexMapSecond,
0469     typename EdgeEquivalencePredicate, typename VertexEquivalencePredicate,
0470     typename SubGraphCallback >
0471 void mcgregor_common_subgraphs(const GraphFirst& graph1,
0472     const GraphSecond& graph2, const VertexIndexMapFirst vindex_map1,
0473     const VertexIndexMapSecond vindex_map2,
0474     EdgeEquivalencePredicate edges_equivalent,
0475     VertexEquivalencePredicate vertices_equivalent,
0476     bool only_connected_subgraphs, SubGraphCallback user_callback)
0477 {
0478
0479     detail::mcgregor_common_subgraphs_internal_init(graph1, graph2, vindex_map1,
0480         vindex_map2, edges_equivalent, vertices_equivalent,
0481         only_connected_subgraphs, user_callback);
0482 }
0483
0484 // Variant of mcgregor_common_subgraphs with all default parameters
0485 template < typename GraphFirst, typename GraphSecond,
0486     typename SubGraphCallback >
0487 void mcgregor_common_subgraphs(const GraphFirst& graph1,
0488     const GraphSecond& graph2, bool only_connected_subgraphs,
0489     SubGraphCallback user_callback)
0490 {
0491
0492     detail::mcgregor_common_subgraphs_internal_init(graph1, graph2,
0493         get(vertex_index, graph1), get(vertex_index, graph2),
0494         always_equivalent(), always_equivalent(), only_connected_subgraphs,
0495         user_callback);
0496 }
0497
0498 // Named parameter variant of mcgregor_common_subgraphs
0499 template < typename GraphFirst, typename GraphSecond, typename SubGraphCallback,
0500     typename Param, typename Tag, typename Rest >
0501 void mcgregor_common_subgraphs(const GraphFirst& graph1,
0502     const GraphSecond& graph2, bool only_connected_subgraphs,
0503     SubGraphCallback user_callback,
0504     const bgl_named_params< Param, Tag, Rest >& params)
0505 {
0506
0507     detail::mcgregor_common_subgraphs_internal_init(graph1, graph2,
0508         choose_const_pmap(
0509             get_param(params, vertex_index1), graph1, vertex_index),
0510         choose_const_pmap(
0511             get_param(params, vertex_index2), graph2, vertex_index),
0512         choose_param(
0513             get_param(params, edges_equivalent_t()), always_equivalent()),
0514         choose_param(
0515             get_param(params, vertices_equivalent_t()), always_equivalent()),
0516         only_connected_subgraphs, user_callback);
0517 }
0518
0519 // ==========================================================================
0520
0521 namespace detail
0522 {
0523
0524     // Binary function object that intercepts subgraphs from
0525     // mcgregor_common_subgraphs_internal and maintains a cache of
0526     // unique subgraphs.  The user callback is invoked for each unique
0527     // subgraph.
0528     template < typename GraphFirst, typename GraphSecond,
0529         typename VertexIndexMapFirst, typename VertexIndexMapSecond,
0530         typename SubGraphCallback >
0531     struct unique_subgraph_interceptor
0532     {
0533
0534         typedef typename graph_traits< GraphFirst >::vertices_size_type
0535             VertexSizeFirst;
0536
0537         typedef mcgregor_common_subgraph_traits< GraphFirst, GraphSecond,
0538             VertexIndexMapFirst, VertexIndexMapSecond >
0539             SubGraphTraits;
0540
0541         typedef typename SubGraphTraits::correspondence_map_first_to_second_type
0542             CachedCorrespondenceMapFirstToSecond;
0543
0544         typedef typename SubGraphTraits::correspondence_map_second_to_first_type
0545             CachedCorrespondenceMapSecondToFirst;
0546
0547         typedef std::pair< VertexSizeFirst,
0548             std::pair< CachedCorrespondenceMapFirstToSecond,
0549                 CachedCorrespondenceMapSecondToFirst > >
0550             SubGraph;
0551
0552         typedef std::vector< SubGraph > SubGraphList;
0553
0554         unique_subgraph_interceptor(const GraphFirst& graph1,
0555             const GraphSecond& graph2, const VertexIndexMapFirst vindex_map1,
0556             const VertexIndexMapSecond vindex_map2,
0557             SubGraphCallback user_callback)
0558         : m_graph1(graph1)
0559         , m_graph2(graph2)
0560         , m_vindex_map1(vindex_map1)
0561         , m_vindex_map2(vindex_map2)
0562         , m_subgraphs(make_shared< SubGraphList >())
0563         , m_user_callback(user_callback)
0564         {
0565         }
0566
0567         template < typename CorrespondenceMapFirstToSecond,
0568             typename CorrespondenceMapSecondToFirst >
0569         bool operator()(
0570             CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
0571             CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
0572             VertexSizeFirst subgraph_size)
0573         {
0574
0575             for (typename SubGraphList::const_iterator subgraph_iter
0576                  = m_subgraphs->begin();
0577                  subgraph_iter != m_subgraphs->end(); ++subgraph_iter)
0578             {
0579
0580                 SubGraph subgraph_cached = *subgraph_iter;
0581
0582                 // Compare subgraph sizes
0583                 if (subgraph_size != subgraph_cached.first)
0584                 {
0585                     continue;
0586                 }
0587
0588                 if (!are_property_maps_different(correspondence_map_1_to_2,
0589                         subgraph_cached.second.first, m_graph1))
0590                 {
0591
0592                     // New subgraph is a duplicate
0593                     return (true);
0594                 }
0595             }
0596
0597             // Subgraph is unique, so make a cached copy
0598             CachedCorrespondenceMapFirstToSecond new_subgraph_1_to_2
0599                 = CachedCorrespondenceMapFirstToSecond(
0600                     num_vertices(m_graph1), m_vindex_map1);
0601
0602             CachedCorrespondenceMapSecondToFirst new_subgraph_2_to_1
0603                 = CorrespondenceMapSecondToFirst(
0604                     num_vertices(m_graph2), m_vindex_map2);
0605
0606             BGL_FORALL_VERTICES_T(vertex1, m_graph1, GraphFirst)
0607             {
0608                 put(new_subgraph_1_to_2, vertex1,
0609                     get(correspondence_map_1_to_2, vertex1));
0610             }
0611
0612             BGL_FORALL_VERTICES_T(vertex2, m_graph2, GraphFirst)
0613             {
0614                 put(new_subgraph_2_to_1, vertex2,
0615                     get(correspondence_map_2_to_1, vertex2));
0616             }
0617
0618             m_subgraphs->push_back(std::make_pair(subgraph_size,
0619                 std::make_pair(new_subgraph_1_to_2, new_subgraph_2_to_1)));
0620
0621             return (m_user_callback(correspondence_map_1_to_2,
0622                 correspondence_map_2_to_1, subgraph_size));
0623         }
0624
0625     private:
0626         const GraphFirst& m_graph1;
0627         const GraphFirst& m_graph2;
0628         const VertexIndexMapFirst m_vindex_map1;
0629         const VertexIndexMapSecond m_vindex_map2;
0630         shared_ptr< SubGraphList > m_subgraphs;
0631         SubGraphCallback m_user_callback;
0632     };
0633
0634 } // namespace detail
0635
0636 // Enumerates all unique common subgraphs between graph1 and graph2.
0637 // The user callback is invoked for each unique subgraph as they are
0638 // discovered.
0639 template < typename GraphFirst, typename GraphSecond,
0640     typename VertexIndexMapFirst, typename VertexIndexMapSecond,
0641     typename EdgeEquivalencePredicate, typename VertexEquivalencePredicate,
0642     typename SubGraphCallback >
0643 void mcgregor_common_subgraphs_unique(const GraphFirst& graph1,
0644     const GraphSecond& graph2, const VertexIndexMapFirst vindex_map1,
0645     const VertexIndexMapSecond vindex_map2,
0646     EdgeEquivalencePredicate edges_equivalent,
0647     VertexEquivalencePredicate vertices_equivalent,
0648     bool only_connected_subgraphs, SubGraphCallback user_callback)
0649 {
0650     detail::unique_subgraph_interceptor< GraphFirst, GraphSecond,
0651         VertexIndexMapFirst, VertexIndexMapSecond, SubGraphCallback >
0652         unique_callback(
0653             graph1, graph2, vindex_map1, vindex_map2, user_callback);
0654
0655     detail::mcgregor_common_subgraphs_internal_init(graph1, graph2, vindex_map1,
0656         vindex_map2, edges_equivalent, vertices_equivalent,
0657         only_connected_subgraphs, unique_callback);
0658 }
0659
0660 // Variant of mcgregor_common_subgraphs_unique with all default
0661 // parameters.
0662 template < typename GraphFirst, typename GraphSecond,
0663     typename SubGraphCallback >
0664 void mcgregor_common_subgraphs_unique(const GraphFirst& graph1,
0665     const GraphSecond& graph2, bool only_connected_subgraphs,
0666     SubGraphCallback user_callback)
0667 {
0668     mcgregor_common_subgraphs_unique(graph1, graph2, get(vertex_index, graph1),
0669         get(vertex_index, graph2), always_equivalent(), always_equivalent(),
0670         only_connected_subgraphs, user_callback);
0671 }
0672
0673 // Named parameter variant of mcgregor_common_subgraphs_unique
0674 template < typename GraphFirst, typename GraphSecond, typename SubGraphCallback,
0675     typename Param, typename Tag, typename Rest >
0676 void mcgregor_common_subgraphs_unique(const GraphFirst& graph1,
0677     const GraphSecond& graph2, bool only_connected_subgraphs,
0678     SubGraphCallback user_callback,
0679     const bgl_named_params< Param, Tag, Rest >& params)
0680 {
0681     mcgregor_common_subgraphs_unique(graph1, graph2,
0682         choose_const_pmap(
0683             get_param(params, vertex_index1), graph1, vertex_index),
0684         choose_const_pmap(
0685             get_param(params, vertex_index2), graph2, vertex_index),
0686         choose_param(
0687             get_param(params, edges_equivalent_t()), always_equivalent()),
0688         choose_param(
0689             get_param(params, vertices_equivalent_t()), always_equivalent()),
0690         only_connected_subgraphs, user_callback);
0691 }
0692
0693 // ==========================================================================
0694
0695 namespace detail
0696 {
0697
0698     // Binary function object that intercepts subgraphs from
0699     // mcgregor_common_subgraphs_internal and maintains a cache of the
0700     // largest subgraphs.
0701     template < typename GraphFirst, typename GraphSecond,
0702         typename VertexIndexMapFirst, typename VertexIndexMapSecond,
0703         typename SubGraphCallback >
0704     struct maximum_subgraph_interceptor
0705     {
0706
0707         typedef typename graph_traits< GraphFirst >::vertices_size_type
0708             VertexSizeFirst;
0709
0710         typedef mcgregor_common_subgraph_traits< GraphFirst, GraphSecond,
0711             VertexIndexMapFirst, VertexIndexMapSecond >
0712             SubGraphTraits;
0713
0714         typedef typename SubGraphTraits::correspondence_map_first_to_second_type
0715             CachedCorrespondenceMapFirstToSecond;
0716
0717         typedef typename SubGraphTraits::correspondence_map_second_to_first_type
0718             CachedCorrespondenceMapSecondToFirst;
0719
0720         typedef std::pair< VertexSizeFirst,
0721             std::pair< CachedCorrespondenceMapFirstToSecond,
0722                 CachedCorrespondenceMapSecondToFirst > >
0723             SubGraph;
0724
0725         typedef std::vector< SubGraph > SubGraphList;
0726
0727         maximum_subgraph_interceptor(const GraphFirst& graph1,
0728             const GraphSecond& graph2, const VertexIndexMapFirst vindex_map1,
0729             const VertexIndexMapSecond vindex_map2,
0730             SubGraphCallback user_callback)
0731         : m_graph1(graph1)
0732         , m_graph2(graph2)
0733         , m_vindex_map1(vindex_map1)
0734         , m_vindex_map2(vindex_map2)
0735         , m_subgraphs(make_shared< SubGraphList >())
0736         , m_largest_size_so_far(make_shared< VertexSizeFirst >(0))
0737         , m_user_callback(user_callback)
0738         {
0739         }
0740
0741         template < typename CorrespondenceMapFirstToSecond,
0742             typename CorrespondenceMapSecondToFirst >
0743         bool operator()(
0744             CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
0745             CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
0746             VertexSizeFirst subgraph_size)
0747         {
0748
0749             if (subgraph_size > *m_largest_size_so_far)
0750             {
0751                 m_subgraphs->clear();
0752                 *m_largest_size_so_far = subgraph_size;
0753             }
0754
0755             if (subgraph_size == *m_largest_size_so_far)
0756             {
0757
0758                 // Make a cached copy
0759                 CachedCorrespondenceMapFirstToSecond new_subgraph_1_to_2
0760                     = CachedCorrespondenceMapFirstToSecond(
0761                         num_vertices(m_graph1), m_vindex_map1);
0762
0763                 CachedCorrespondenceMapSecondToFirst new_subgraph_2_to_1
0764                     = CachedCorrespondenceMapSecondToFirst(
0765                         num_vertices(m_graph2), m_vindex_map2);
0766
0767                 BGL_FORALL_VERTICES_T(vertex1, m_graph1, GraphFirst)
0768                 {
0769                     put(new_subgraph_1_to_2, vertex1,
0770                         get(correspondence_map_1_to_2, vertex1));
0771                 }
0772
0773                 BGL_FORALL_VERTICES_T(vertex2, m_graph2, GraphFirst)
0774                 {
0775                     put(new_subgraph_2_to_1, vertex2,
0776                         get(correspondence_map_2_to_1, vertex2));
0777                 }
0778
0779                 m_subgraphs->push_back(std::make_pair(subgraph_size,
0780                     std::make_pair(new_subgraph_1_to_2, new_subgraph_2_to_1)));
0781             }
0782
0783             return (true);
0784         }
0785
0786         void output_subgraphs()
0787         {
0788             for (typename SubGraphList::const_iterator subgraph_iter
0789                  = m_subgraphs->begin();
0790                  subgraph_iter != m_subgraphs->end(); ++subgraph_iter)
0791             {
0792
0793                 SubGraph subgraph_cached = *subgraph_iter;
0794                 m_user_callback(subgraph_cached.second.first,
0795                     subgraph_cached.second.second, subgraph_cached.first);
0796             }
0797         }
0798
0799     private:
0800         const GraphFirst& m_graph1;
0801         const GraphFirst& m_graph2;
0802         const VertexIndexMapFirst m_vindex_map1;
0803         const VertexIndexMapSecond m_vindex_map2;
0804         shared_ptr< SubGraphList > m_subgraphs;
0805         shared_ptr< VertexSizeFirst > m_largest_size_so_far;
0806         SubGraphCallback m_user_callback;
0807     };
0808
0809 } // namespace detail
0810
0811 // Enumerates the largest common subgraphs found between graph1
0812 // and graph2.  Note that the ENTIRE search space is explored before
0813 // user_callback is actually invoked.
0814 template < typename GraphFirst, typename GraphSecond,
0815     typename VertexIndexMapFirst, typename VertexIndexMapSecond,
0816     typename EdgeEquivalencePredicate, typename VertexEquivalencePredicate,
0817     typename SubGraphCallback >
0818 void mcgregor_common_subgraphs_maximum(const GraphFirst& graph1,
0819     const GraphSecond& graph2, const VertexIndexMapFirst vindex_map1,
0820     const VertexIndexMapSecond vindex_map2,
0821     EdgeEquivalencePredicate edges_equivalent,
0822     VertexEquivalencePredicate vertices_equivalent,
0823     bool only_connected_subgraphs, SubGraphCallback user_callback)
0824 {
0825     detail::maximum_subgraph_interceptor< GraphFirst, GraphSecond,
0826         VertexIndexMapFirst, VertexIndexMapSecond, SubGraphCallback >
0827         max_interceptor(
0828             graph1, graph2, vindex_map1, vindex_map2, user_callback);
0829
0830     detail::mcgregor_common_subgraphs_internal_init(graph1, graph2, vindex_map1,
0831         vindex_map2, edges_equivalent, vertices_equivalent,
0832         only_connected_subgraphs, max_interceptor);
0833
0834     // Only output the largest subgraphs
0835     max_interceptor.output_subgraphs();
0836 }
0837
0838 // Variant of mcgregor_common_subgraphs_maximum with all default
0839 // parameters.
0840 template < typename GraphFirst, typename GraphSecond,
0841     typename SubGraphCallback >
0842 void mcgregor_common_subgraphs_maximum(const GraphFirst& graph1,
0843     const GraphSecond& graph2, bool only_connected_subgraphs,
0844     SubGraphCallback user_callback)
0845 {
0846     mcgregor_common_subgraphs_maximum(graph1, graph2, get(vertex_index, graph1),
0847         get(vertex_index, graph2), always_equivalent(), always_equivalent(),
0848         only_connected_subgraphs, user_callback);
0849 }
0850
0851 // Named parameter variant of mcgregor_common_subgraphs_maximum
0852 template < typename GraphFirst, typename GraphSecond, typename SubGraphCallback,
0853     typename Param, typename Tag, typename Rest >
0854 void mcgregor_common_subgraphs_maximum(const GraphFirst& graph1,
0855     const GraphSecond& graph2, bool only_connected_subgraphs,
0856     SubGraphCallback user_callback,
0857     const bgl_named_params< Param, Tag, Rest >& params)
0858 {
0859     mcgregor_common_subgraphs_maximum(graph1, graph2,
0860         choose_const_pmap(
0861             get_param(params, vertex_index1), graph1, vertex_index),
0862         choose_const_pmap(
0863             get_param(params, vertex_index2), graph2, vertex_index),
0864         choose_param(
0865             get_param(params, edges_equivalent_t()), always_equivalent()),
0866         choose_param(
0867             get_param(params, vertices_equivalent_t()), always_equivalent()),
0868         only_connected_subgraphs, user_callback);
0869 }
0870
0871 // ==========================================================================
0872
0873 namespace detail
0874 {
0875
0876     // Binary function object that intercepts subgraphs from
0877     // mcgregor_common_subgraphs_internal and maintains a cache of the
0878     // largest, unique subgraphs.
0879     template < typename GraphFirst, typename GraphSecond,
0880         typename VertexIndexMapFirst, typename VertexIndexMapSecond,
0881         typename SubGraphCallback >
0882     struct unique_maximum_subgraph_interceptor
0883     {
0884
0885         typedef typename graph_traits< GraphFirst >::vertices_size_type
0886             VertexSizeFirst;
0887
0888         typedef mcgregor_common_subgraph_traits< GraphFirst, GraphSecond,
0889             VertexIndexMapFirst, VertexIndexMapSecond >
0890             SubGraphTraits;
0891
0892         typedef typename SubGraphTraits::correspondence_map_first_to_second_type
0893             CachedCorrespondenceMapFirstToSecond;
0894
0895         typedef typename SubGraphTraits::correspondence_map_second_to_first_type
0896             CachedCorrespondenceMapSecondToFirst;
0897
0898         typedef std::pair< VertexSizeFirst,
0899             std::pair< CachedCorrespondenceMapFirstToSecond,
0900                 CachedCorrespondenceMapSecondToFirst > >
0901             SubGraph;
0902
0903         typedef std::vector< SubGraph > SubGraphList;
0904
0905         unique_maximum_subgraph_interceptor(const GraphFirst& graph1,
0906             const GraphSecond& graph2, const VertexIndexMapFirst vindex_map1,
0907             const VertexIndexMapSecond vindex_map2,
0908             SubGraphCallback user_callback)
0909         : m_graph1(graph1)
0910         , m_graph2(graph2)
0911         , m_vindex_map1(vindex_map1)
0912         , m_vindex_map2(vindex_map2)
0913         , m_subgraphs(make_shared< SubGraphList >())
0914         , m_largest_size_so_far(make_shared< VertexSizeFirst >(0))
0915         , m_user_callback(user_callback)
0916         {
0917         }
0918
0919         template < typename CorrespondenceMapFirstToSecond,
0920             typename CorrespondenceMapSecondToFirst >
0921         bool operator()(
0922             CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
0923             CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
0924             VertexSizeFirst subgraph_size)
0925         {
0926
0927             if (subgraph_size > *m_largest_size_so_far)
0928             {
0929                 m_subgraphs->clear();
0930                 *m_largest_size_so_far = subgraph_size;
0931             }
0932
0933             if (subgraph_size == *m_largest_size_so_far)
0934             {
0935
0936                 // Check if subgraph is unique
0937                 for (typename SubGraphList::const_iterator subgraph_iter
0938                      = m_subgraphs->begin();
0939                      subgraph_iter != m_subgraphs->end(); ++subgraph_iter)
0940                 {
0941
0942                     SubGraph subgraph_cached = *subgraph_iter;
0943
0944                     if (!are_property_maps_different(correspondence_map_1_to_2,
0945                             subgraph_cached.second.first, m_graph1))
0946                     {
0947
0948                         // New subgraph is a duplicate
0949                         return (true);
0950                     }
0951                 }
0952
0953                 // Subgraph is unique, so make a cached copy
0954                 CachedCorrespondenceMapFirstToSecond new_subgraph_1_to_2
0955                     = CachedCorrespondenceMapFirstToSecond(
0956                         num_vertices(m_graph1), m_vindex_map1);
0957
0958                 CachedCorrespondenceMapSecondToFirst new_subgraph_2_to_1
0959                     = CachedCorrespondenceMapSecondToFirst(
0960                         num_vertices(m_graph2), m_vindex_map2);
0961
0962                 BGL_FORALL_VERTICES_T(vertex1, m_graph1, GraphFirst)
0963                 {
0964                     put(new_subgraph_1_to_2, vertex1,
0965                         get(correspondence_map_1_to_2, vertex1));
0966                 }
0967
0968                 BGL_FORALL_VERTICES_T(vertex2, m_graph2, GraphFirst)
0969                 {
0970                     put(new_subgraph_2_to_1, vertex2,
0971                         get(correspondence_map_2_to_1, vertex2));
0972                 }
0973
0974                 m_subgraphs->push_back(std::make_pair(subgraph_size,
0975                     std::make_pair(new_subgraph_1_to_2, new_subgraph_2_to_1)));
0976             }
0977
0978             return (true);
0979         }
0980
0981         void output_subgraphs()
0982         {
0983             for (typename SubGraphList::const_iterator subgraph_iter
0984                  = m_subgraphs->begin();
0985                  subgraph_iter != m_subgraphs->end(); ++subgraph_iter)
0986             {
0987
0988                 SubGraph subgraph_cached = *subgraph_iter;
0989                 m_user_callback(subgraph_cached.second.first,
0990                     subgraph_cached.second.second, subgraph_cached.first);
0991             }
0992         }
0993
0994     private:
0995         const GraphFirst& m_graph1;
0996         const GraphFirst& m_graph2;
0997         const VertexIndexMapFirst m_vindex_map1;
0998         const VertexIndexMapSecond m_vindex_map2;
0999         shared_ptr< SubGraphList > m_subgraphs;
1000         shared_ptr< VertexSizeFirst > m_largest_size_so_far;
1001         SubGraphCallback m_user_callback;
1002     };
1003
1004 } // namespace detail
1005
1006 // Enumerates the largest, unique common subgraphs found between
1007 // graph1 and graph2.  Note that the ENTIRE search space is explored
1008 // before user_callback is actually invoked.
1009 template < typename GraphFirst, typename GraphSecond,
1010     typename VertexIndexMapFirst, typename VertexIndexMapSecond,
1011     typename EdgeEquivalencePredicate, typename VertexEquivalencePredicate,
1012     typename SubGraphCallback >
1013 void mcgregor_common_subgraphs_maximum_unique(const GraphFirst& graph1,
1014     const GraphSecond& graph2, const VertexIndexMapFirst vindex_map1,
1015     const VertexIndexMapSecond vindex_map2,
1016     EdgeEquivalencePredicate edges_equivalent,
1017     VertexEquivalencePredicate vertices_equivalent,
1018     bool only_connected_subgraphs, SubGraphCallback user_callback)
1019 {
1020     detail::unique_maximum_subgraph_interceptor< GraphFirst, GraphSecond,
1021         VertexIndexMapFirst, VertexIndexMapSecond, SubGraphCallback >
1022         unique_max_interceptor(
1023             graph1, graph2, vindex_map1, vindex_map2, user_callback);
1024
1025     detail::mcgregor_common_subgraphs_internal_init(graph1, graph2, vindex_map1,
1026         vindex_map2, edges_equivalent, vertices_equivalent,
1027         only_connected_subgraphs, unique_max_interceptor);
1028
1029     // Only output the largest, unique subgraphs
1030     unique_max_interceptor.output_subgraphs();
1031 }
1032
1033 // Variant of mcgregor_common_subgraphs_maximum_unique with all default
1034 // parameters
1035 template < typename GraphFirst, typename GraphSecond,
1036     typename SubGraphCallback >
1037 void mcgregor_common_subgraphs_maximum_unique(const GraphFirst& graph1,
1038     const GraphSecond& graph2, bool only_connected_subgraphs,
1039     SubGraphCallback user_callback)
1040 {
1041
1042     mcgregor_common_subgraphs_maximum_unique(graph1, graph2,
1043         get(vertex_index, graph1), get(vertex_index, graph2),
1044         always_equivalent(), always_equivalent(), only_connected_subgraphs,
1045         user_callback);
1046 }
1047
1048 // Named parameter variant of
1049 // mcgregor_common_subgraphs_maximum_unique
1050 template < typename GraphFirst, typename GraphSecond, typename SubGraphCallback,
1051     typename Param, typename Tag, typename Rest >
1052 void mcgregor_common_subgraphs_maximum_unique(const GraphFirst& graph1,
1053     const GraphSecond& graph2, bool only_connected_subgraphs,
1054     SubGraphCallback user_callback,
1055     const bgl_named_params< Param, Tag, Rest >& params)
1056 {
1057     mcgregor_common_subgraphs_maximum_unique(graph1, graph2,
1058         choose_const_pmap(
1059             get_param(params, vertex_index1), graph1, vertex_index),
1060         choose_const_pmap(
1061             get_param(params, vertex_index2), graph2, vertex_index),
1062         choose_param(
1063             get_param(params, edges_equivalent_t()), always_equivalent()),
1064         choose_param(
1065             get_param(params, vertices_equivalent_t()), always_equivalent()),
1066         only_connected_subgraphs, user_callback);
1067 }
1068
1069 // ==========================================================================
1070
1071 // Fills a membership map (vertex -> bool) using the information
1072 // present in correspondence_map_1_to_2. Every vertex in a
1073 // membership map will have a true value only if it is not
1074 // associated with a null vertex in the correspondence map.
1075 template < typename GraphSecond, typename GraphFirst,
1076     typename CorrespondenceMapFirstToSecond, typename MembershipMapFirst >
1077 void fill_membership_map(const GraphFirst& graph1,
1078     const CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
1079     MembershipMapFirst membership_map1)
1080 {
1081
1082     BGL_FORALL_VERTICES_T(vertex1, graph1, GraphFirst)
1083     {
1084         put(membership_map1, vertex1,
1085             get(correspondence_map_1_to_2, vertex1)
1086                 != graph_traits< GraphSecond >::null_vertex());
1087     }
1088 }
1089
1090 // Traits associated with a membership map filtered graph.  Provided
1091 // for convenience to access graph and vertex filter types.
1092 template < typename Graph, typename MembershipMap >
1093 struct membership_filtered_graph_traits
1094 {
1095     typedef property_map_filter< MembershipMap > vertex_filter_type;
1096     typedef filtered_graph< Graph, keep_all, vertex_filter_type > graph_type;
1097 };
1098
1099 // Returns a filtered sub-graph of graph whose edge and vertex
1100 // inclusion is dictated by membership_map.
1101 template < typename Graph, typename MembershipMap >
1102 typename membership_filtered_graph_traits< Graph, MembershipMap >::graph_type
1103 make_membership_filtered_graph(
1104     const Graph& graph, MembershipMap& membership_map)
1105 {
1106
1107     typedef membership_filtered_graph_traits< Graph, MembershipMap > MFGTraits;
1108     typedef typename MFGTraits::graph_type MembershipFilteredGraph;
1109
1110     typename MFGTraits::vertex_filter_type v_filter(membership_map);
1111
1112     return (MembershipFilteredGraph(graph, keep_all(), v_filter));
1113 }
1114
1115 } // namespace boost
1116
1117 #endif // BOOST_GRAPH_MCGREGOR_COMMON_SUBGRAPHS_HPP