Chris@16: //=======================================================================
Chris@16: // Copyright 2009 Trustees of Indiana University.
Chris@16: // Authors: Michael Hansen, Andrew Lumsdaine
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_MCGREGOR_COMMON_SUBGRAPHS_HPP
Chris@16: #define BOOST_GRAPH_MCGREGOR_COMMON_SUBGRAPHS_HPP
Chris@16: 
Chris@16: #include <algorithm>
Chris@16: #include <vector>
Chris@16: #include <stack>
Chris@16: 
Chris@16: #include <boost/make_shared.hpp>
Chris@16: #include <boost/graph/adjacency_list.hpp>
Chris@16: #include <boost/graph/filtered_graph.hpp>
Chris@16: #include <boost/graph/graph_utility.hpp>
Chris@16: #include <boost/graph/iteration_macros.hpp>
Chris@16: #include <boost/graph/properties.hpp>
Chris@16: #include <boost/property_map/shared_array_property_map.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   namespace detail {
Chris@16: 
Chris@16:     // Traits associated with common subgraphs, used mainly to keep a
Chris@16:     // consistent type for the correspondence maps.
Chris@16:     template <typename GraphFirst,
Chris@16:               typename GraphSecond,
Chris@16:               typename VertexIndexMapFirst,
Chris@16:               typename VertexIndexMapSecond>
Chris@16:     struct mcgregor_common_subgraph_traits {
Chris@16:       typedef typename graph_traits<GraphFirst>::vertex_descriptor vertex_first_type;
Chris@16:       typedef typename graph_traits<GraphSecond>::vertex_descriptor vertex_second_type;
Chris@16:       
Chris@16:       typedef shared_array_property_map<vertex_second_type, VertexIndexMapFirst>
Chris@16:         correspondence_map_first_to_second_type;
Chris@16:   
Chris@16:       typedef shared_array_property_map<vertex_first_type, VertexIndexMapSecond>
Chris@16:         correspondence_map_second_to_first_type;
Chris@16:     };  
Chris@16: 
Chris@16:   } // namespace detail
Chris@16: 
Chris@16:   // ==========================================================================
Chris@16: 
Chris@16:   // Binary function object that returns true if the values for item1
Chris@16:   // in property_map1 and item2 in property_map2 are equivalent.
Chris@16:   template <typename PropertyMapFirst,
Chris@16:             typename PropertyMapSecond>
Chris@16:   struct property_map_equivalent {
Chris@16:   
Chris@16:     property_map_equivalent(const PropertyMapFirst property_map1,
Chris@16:                             const PropertyMapSecond property_map2) :
Chris@16:       m_property_map1(property_map1),
Chris@16:       m_property_map2(property_map2) { }
Chris@16: 
Chris@16:     template <typename ItemFirst,
Chris@16:               typename ItemSecond>
Chris@16:     bool operator()(const ItemFirst item1, const ItemSecond item2) {
Chris@16:       return (get(m_property_map1, item1) == get(m_property_map2, item2));
Chris@16:     }
Chris@16:   
Chris@16:   private:
Chris@16:     const PropertyMapFirst m_property_map1;
Chris@16:     const PropertyMapSecond m_property_map2;
Chris@16:   };
Chris@16: 
Chris@16:   // Returns a property_map_equivalent object that compares the values
Chris@16:   // of property_map1 and property_map2.
Chris@16:   template <typename PropertyMapFirst,
Chris@16:             typename PropertyMapSecond>
Chris@16:   property_map_equivalent<PropertyMapFirst,
Chris@16:                           PropertyMapSecond>
Chris@16:   make_property_map_equivalent
Chris@16:   (const PropertyMapFirst property_map1,
Chris@16:    const PropertyMapSecond property_map2) {
Chris@16: 
Chris@16:     return (property_map_equivalent<PropertyMapFirst, PropertyMapSecond>
Chris@16:             (property_map1, property_map2));
Chris@16:   }
Chris@16: 
Chris@16:   // Binary function object that always returns true.  Used when
Chris@16:   // vertices or edges are always equivalent (i.e. have no labels).
Chris@16:   struct always_equivalent {
Chris@16:   
Chris@16:     template <typename ItemFirst,
Chris@16:               typename ItemSecond>
Chris@16:     bool operator()(const ItemFirst&, const ItemSecond&) {
Chris@16:       return (true);
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   // ==========================================================================
Chris@16: 
Chris@16:   namespace detail {
Chris@16: 
Chris@16:     // Return true if new_vertex1 and new_vertex2 can extend the
Chris@16:     // subgraph represented by correspondence_map_1_to_2 and
Chris@16:     // correspondence_map_2_to_1.  The vertices_equivalent and
Chris@16:     // edges_equivalent predicates are used to test vertex and edge
Chris@16:     // equivalency between the two graphs.
Chris@16:     template <typename GraphFirst,
Chris@16:               typename GraphSecond,
Chris@16:               typename CorrespondenceMapFirstToSecond,
Chris@16:               typename CorrespondenceMapSecondToFirst,
Chris@16:               typename EdgeEquivalencePredicate,
Chris@16:               typename VertexEquivalencePredicate>
Chris@16:     bool can_extend_graph
Chris@16:     (const GraphFirst& graph1,
Chris@16:      const GraphSecond& graph2,
Chris@16:      CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
Chris@16:      CorrespondenceMapSecondToFirst /*correspondence_map_2_to_1*/,
Chris@16:      typename graph_traits<GraphFirst>::vertices_size_type subgraph_size,
Chris@16:      typename graph_traits<GraphFirst>::vertex_descriptor new_vertex1,
Chris@16:      typename graph_traits<GraphSecond>::vertex_descriptor new_vertex2,
Chris@16:      EdgeEquivalencePredicate edges_equivalent,
Chris@16:      VertexEquivalencePredicate vertices_equivalent,
Chris@16:      bool only_connected_subgraphs)
Chris@16:     {
Chris@16:       typedef typename graph_traits<GraphSecond>::vertex_descriptor VertexSecond;
Chris@16:       
Chris@16:       typedef typename graph_traits<GraphFirst>::edge_descriptor EdgeFirst;
Chris@16:       typedef typename graph_traits<GraphSecond>::edge_descriptor EdgeSecond;
Chris@16: 
Chris@16:       // Check vertex equality
Chris@16:       if (!vertices_equivalent(new_vertex1, new_vertex2)) {
Chris@16:         return (false);
Chris@16:       }
Chris@16: 
Chris@16:       // Vertices match and graph is empty, so we can extend the subgraph
Chris@16:       if (subgraph_size == 0) {
Chris@16:         return (true);
Chris@16:       }
Chris@16: 
Chris@16:       bool has_one_edge = false;
Chris@16: 
Chris@16:       // Verify edges with existing sub-graph
Chris@16:       BGL_FORALL_VERTICES_T(existing_vertex1, graph1, GraphFirst) {
Chris@16: 
Chris@16:         VertexSecond existing_vertex2 = get(correspondence_map_1_to_2, existing_vertex1);
Chris@16: 
Chris@16:         // Skip unassociated vertices
Chris@16:         if (existing_vertex2 == graph_traits<GraphSecond>::null_vertex()) {
Chris@16:           continue;
Chris@16:         }
Chris@16: 
Chris@16:         // NOTE: This will not work with parallel edges, since the
Chris@16:         // first matching edge is always chosen.
Chris@16:         EdgeFirst edge_to_new1, edge_from_new1;
Chris@16:         bool edge_to_new_exists1 = false, edge_from_new_exists1 = false;
Chris@16:         
Chris@16:         EdgeSecond edge_to_new2, edge_from_new2;
Chris@16:         bool edge_to_new_exists2 = false, edge_from_new_exists2 = false;
Chris@16: 
Chris@16:         // Search for edge from existing to new vertex (graph1)
Chris@16:         BGL_FORALL_OUTEDGES_T(existing_vertex1, edge1, graph1, GraphFirst) {
Chris@16:           if (target(edge1, graph1) == new_vertex1) {
Chris@16:             edge_to_new1 = edge1;
Chris@16:             edge_to_new_exists1 = true;
Chris@16:             break;
Chris@16:           }
Chris@16:         }
Chris@16: 
Chris@16:         // Search for edge from existing to new vertex (graph2)
Chris@16:         BGL_FORALL_OUTEDGES_T(existing_vertex2, edge2, graph2, GraphSecond) {
Chris@16:           if (target(edge2,  graph2) == new_vertex2) {
Chris@16:             edge_to_new2 = edge2;
Chris@16:             edge_to_new_exists2 = true;
Chris@16:             break;
Chris@16:           }
Chris@16:         }
Chris@16: 
Chris@16:         // Make sure edges from existing to new vertices are equivalent
Chris@16:         if ((edge_to_new_exists1 != edge_to_new_exists2) ||
Chris@16:             ((edge_to_new_exists1 && edge_to_new_exists2) &&
Chris@16:              !edges_equivalent(edge_to_new1, edge_to_new2))) {
Chris@16:               
Chris@16:           return (false);
Chris@16:         }
Chris@16: 
Chris@16:         bool is_undirected1 = is_undirected(graph1),
Chris@16:           is_undirected2 = is_undirected(graph2);
Chris@16: 
Chris@16:         if (is_undirected1 && is_undirected2) {
Chris@16: 
Chris@16:           // Edge in both graphs exists and both graphs are undirected
Chris@16:           if (edge_to_new_exists1 && edge_to_new_exists2) {
Chris@16:             has_one_edge = true;
Chris@16:           }
Chris@16: 
Chris@16:           continue;
Chris@16:         }
Chris@16:         else {
Chris@16: 
Chris@16:           if (!is_undirected1) {
Chris@16: 
Chris@16:             // Search for edge from new to existing vertex (graph1)
Chris@16:             BGL_FORALL_OUTEDGES_T(new_vertex1, edge1, graph1, GraphFirst) {
Chris@16:               if (target(edge1, graph1) == existing_vertex1) {
Chris@16:                 edge_from_new1 = edge1;
Chris@16:                 edge_from_new_exists1 = true;
Chris@16:                 break;
Chris@16:               }
Chris@16:             }
Chris@16:           }
Chris@16: 
Chris@16:           if (!is_undirected2) {
Chris@16: 
Chris@16:             // Search for edge from new to existing vertex (graph2)
Chris@16:             BGL_FORALL_OUTEDGES_T(new_vertex2, edge2, graph2, GraphSecond) {
Chris@16:               if (target(edge2, graph2) == existing_vertex2) {
Chris@16:                 edge_from_new2 = edge2;
Chris@16:                 edge_from_new_exists2 = true;
Chris@16:                 break;
Chris@16:               }
Chris@16:             }
Chris@16:           }
Chris@16: 
Chris@16:           // Make sure edges from new to existing vertices are equivalent
Chris@16:           if ((edge_from_new_exists1 != edge_from_new_exists2) ||
Chris@16:               ((edge_from_new_exists1 && edge_from_new_exists2) &&
Chris@16:                !edges_equivalent(edge_from_new1, edge_from_new2))) {
Chris@16:                 
Chris@16:             return (false);
Chris@16:           }
Chris@16: 
Chris@16:           if ((edge_from_new_exists1 && edge_from_new_exists2) ||
Chris@16:               (edge_to_new_exists1 && edge_to_new_exists2)) {
Chris@16:             has_one_edge = true;
Chris@16:           }
Chris@16: 
Chris@16:         } // else
Chris@16: 
Chris@16:       } // BGL_FORALL_VERTICES_T
Chris@16: 
Chris@16:       // Make sure new vertices are connected to the existing subgraph
Chris@16:       if (only_connected_subgraphs && !has_one_edge) {
Chris@16:         return (false);
Chris@16:       }
Chris@16: 
Chris@16:       return (true);
Chris@16:     }    
Chris@16: 
Chris@16:     // Recursive method that does a depth-first search in the space of
Chris@16:     // potential subgraphs.  At each level, every new vertex pair from
Chris@16:     // both graphs is tested to see if it can extend the current
Chris@16:     // subgraph.  If so, the subgraph is output to subgraph_callback
Chris@16:     // in the form of two correspondence maps (one for each graph).
Chris@16:     // Returning false from subgraph_callback will terminate the
Chris@16:     // search.  Function returns true if the entire search space was
Chris@16:     // explored.
Chris@16:     template <typename GraphFirst,
Chris@16:               typename GraphSecond,
Chris@16:               typename VertexIndexMapFirst,
Chris@16:               typename VertexIndexMapSecond,
Chris@16:               typename CorrespondenceMapFirstToSecond,
Chris@16:               typename CorrespondenceMapSecondToFirst,
Chris@16:               typename VertexStackFirst,
Chris@16:               typename EdgeEquivalencePredicate,
Chris@16:               typename VertexEquivalencePredicate,
Chris@16:               typename SubGraphInternalCallback>
Chris@16:     bool mcgregor_common_subgraphs_internal
Chris@16:     (const GraphFirst& graph1,
Chris@16:      const GraphSecond& graph2,
Chris@16:      const VertexIndexMapFirst& vindex_map1,
Chris@16:      const VertexIndexMapSecond& vindex_map2,
Chris@16:      CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
Chris@16:      CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
Chris@16:      VertexStackFirst& vertex_stack1,
Chris@16:      EdgeEquivalencePredicate edges_equivalent,
Chris@16:      VertexEquivalencePredicate vertices_equivalent,
Chris@16:      bool only_connected_subgraphs,
Chris@16:      SubGraphInternalCallback subgraph_callback)
Chris@16:     {
Chris@16:       typedef typename graph_traits<GraphFirst>::vertex_descriptor VertexFirst;
Chris@16:       typedef typename graph_traits<GraphSecond>::vertex_descriptor VertexSecond;
Chris@16:       typedef typename graph_traits<GraphFirst>::vertices_size_type VertexSizeFirst;
Chris@16: 
Chris@16:       // Get iterators for vertices from both graphs
Chris@16:       typename graph_traits<GraphFirst>::vertex_iterator
Chris@16:         vertex1_iter, vertex1_end;
Chris@16:   
Chris@16:       typename graph_traits<GraphSecond>::vertex_iterator
Chris@16:         vertex2_begin, vertex2_end, vertex2_iter;
Chris@16:   
Chris@16:       boost::tie(vertex1_iter, vertex1_end) = vertices(graph1);
Chris@16:       boost::tie(vertex2_begin, vertex2_end) = vertices(graph2);
Chris@16:       vertex2_iter = vertex2_begin;
Chris@16:   
Chris@16:       // Iterate until all vertices have been visited
Chris@16:       BGL_FORALL_VERTICES_T(new_vertex1, graph1, GraphFirst) {
Chris@16: 
Chris@16:         VertexSecond existing_vertex2 = get(correspondence_map_1_to_2, new_vertex1);
Chris@16: 
Chris@16:         // Skip already matched vertices in first graph
Chris@16:         if (existing_vertex2 != graph_traits<GraphSecond>::null_vertex()) {
Chris@16:           continue;
Chris@16:         }
Chris@16:     
Chris@16:         BGL_FORALL_VERTICES_T(new_vertex2, graph2, GraphSecond) {
Chris@16: 
Chris@16:           VertexFirst existing_vertex1 = get(correspondence_map_2_to_1, new_vertex2);
Chris@16: 
Chris@16:           // Skip already matched vertices in second graph
Chris@16:           if (existing_vertex1 != graph_traits<GraphFirst>::null_vertex()) {
Chris@16:             continue;
Chris@16:           }
Chris@16: 
Chris@16:           // Check if current sub-graph can be extended with the matched vertex pair
Chris@16:           if (can_extend_graph(graph1, graph2,
Chris@16:                                correspondence_map_1_to_2, correspondence_map_2_to_1,
Chris@16:                                (VertexSizeFirst)vertex_stack1.size(),
Chris@16:                                new_vertex1, new_vertex2,
Chris@16:                                edges_equivalent, vertices_equivalent,
Chris@16:                                only_connected_subgraphs)) {
Chris@16: 
Chris@16:             // Keep track of old graph size for restoring later
Chris@16:             VertexSizeFirst old_graph_size = (VertexSizeFirst)vertex_stack1.size(),
Chris@16:               new_graph_size = old_graph_size + 1;
Chris@16: 
Chris@16:             // Extend subgraph
Chris@16:             put(correspondence_map_1_to_2, new_vertex1, new_vertex2);
Chris@16:             put(correspondence_map_2_to_1, new_vertex2, new_vertex1);
Chris@16:             vertex_stack1.push(new_vertex1);
Chris@16: 
Chris@101:             // Returning false from the callback will cancel iteration
Chris@101:             if (!subgraph_callback(correspondence_map_1_to_2,
Chris@101:                                    correspondence_map_2_to_1,
Chris@101:                                    new_graph_size)) {
Chris@101:               return (false);
Chris@16:             }
Chris@16:       
Chris@16:             // Depth-first search into the state space of possible sub-graphs
Chris@16:             bool continue_iteration =
Chris@16:               mcgregor_common_subgraphs_internal
Chris@16:               (graph1, graph2,
Chris@16:                vindex_map1, vindex_map2,
Chris@16:                correspondence_map_1_to_2, correspondence_map_2_to_1,
Chris@16:                vertex_stack1,
Chris@16:                edges_equivalent, vertices_equivalent,
Chris@16:                only_connected_subgraphs, subgraph_callback);
Chris@16: 
Chris@16:             if (!continue_iteration) {
Chris@16:               return (false);
Chris@16:             }
Chris@16:       
Chris@16:             // Restore previous state
Chris@16:             if (vertex_stack1.size() > old_graph_size) {
Chris@16:               
Chris@16:               VertexFirst stack_vertex1 = vertex_stack1.top();
Chris@16:               VertexSecond stack_vertex2 = get(correspondence_map_1_to_2,
Chris@16:                                                stack_vertex1);
Chris@16: 
Chris@16:               // Contract subgraph
Chris@16:               put(correspondence_map_1_to_2, stack_vertex1,
Chris@16:                   graph_traits<GraphSecond>::null_vertex());
Chris@16:             
Chris@16:               put(correspondence_map_2_to_1, stack_vertex2,
Chris@16:                   graph_traits<GraphFirst>::null_vertex());
Chris@16:                   
Chris@16:               vertex_stack1.pop();
Chris@16:            }
Chris@16: 
Chris@16:           } // if can_extend_graph
Chris@16: 
Chris@16:         } // BGL_FORALL_VERTICES_T (graph2)
Chris@16: 
Chris@16:       } // BGL_FORALL_VERTICES_T (graph1)
Chris@16: 
Chris@16:       return (true);
Chris@16:     }
Chris@16: 
Chris@16:     // Internal method that initializes blank correspondence maps and
Chris@16:     // a vertex stack for use in mcgregor_common_subgraphs_internal.
Chris@16:     template <typename GraphFirst,
Chris@16:               typename GraphSecond,
Chris@16:               typename VertexIndexMapFirst,
Chris@16:               typename VertexIndexMapSecond,
Chris@16:               typename EdgeEquivalencePredicate,
Chris@16:               typename VertexEquivalencePredicate,
Chris@16:               typename SubGraphInternalCallback>
Chris@16:     inline void mcgregor_common_subgraphs_internal_init
Chris@16:     (const GraphFirst& graph1,
Chris@16:      const GraphSecond& graph2,
Chris@16:      const VertexIndexMapFirst vindex_map1,
Chris@16:      const VertexIndexMapSecond vindex_map2,
Chris@16:      EdgeEquivalencePredicate edges_equivalent,
Chris@16:      VertexEquivalencePredicate vertices_equivalent,
Chris@16:      bool only_connected_subgraphs,
Chris@16:      SubGraphInternalCallback subgraph_callback)
Chris@16:     {
Chris@16:       typedef mcgregor_common_subgraph_traits<GraphFirst,
Chris@16:         GraphSecond, VertexIndexMapFirst,
Chris@16:         VertexIndexMapSecond> SubGraphTraits;
Chris@16:         
Chris@16:       typename SubGraphTraits::correspondence_map_first_to_second_type
Chris@16:         correspondence_map_1_to_2(num_vertices(graph1), vindex_map1);
Chris@16: 
Chris@16:       BGL_FORALL_VERTICES_T(vertex1, graph1, GraphFirst) {
Chris@16:         put(correspondence_map_1_to_2, vertex1,
Chris@16:             graph_traits<GraphSecond>::null_vertex());
Chris@16:       }
Chris@16:                                                  
Chris@16:       typename SubGraphTraits::correspondence_map_second_to_first_type
Chris@16:         correspondence_map_2_to_1(num_vertices(graph2), vindex_map2);
Chris@16: 
Chris@16:       BGL_FORALL_VERTICES_T(vertex2, graph2, GraphSecond) {
Chris@16:         put(correspondence_map_2_to_1, vertex2,
Chris@16:             graph_traits<GraphFirst>::null_vertex());
Chris@16:       }
Chris@16: 
Chris@16:       typedef typename graph_traits<GraphFirst>::vertex_descriptor
Chris@16:         VertexFirst;
Chris@16:         
Chris@16:       std::stack<VertexFirst> vertex_stack1;
Chris@16: 
Chris@16:       mcgregor_common_subgraphs_internal
Chris@16:         (graph1, graph2,
Chris@16:          vindex_map1, vindex_map2,
Chris@16:          correspondence_map_1_to_2, correspondence_map_2_to_1,
Chris@16:          vertex_stack1,
Chris@16:          edges_equivalent, vertices_equivalent,
Chris@16:          only_connected_subgraphs,
Chris@16:          subgraph_callback);
Chris@16:     }
Chris@16:     
Chris@16:   } // namespace detail
Chris@16: 
Chris@16:   // ==========================================================================
Chris@16: 
Chris@16:   // Enumerates all common subgraphs present in graph1 and graph2.
Chris@16:   // Continues until the search space has been fully explored or false
Chris@16:   // is returned from user_callback.
Chris@16:   template <typename GraphFirst,
Chris@16:             typename GraphSecond,
Chris@16:             typename VertexIndexMapFirst,
Chris@16:             typename VertexIndexMapSecond,
Chris@16:             typename EdgeEquivalencePredicate,
Chris@16:             typename VertexEquivalencePredicate,
Chris@16:             typename SubGraphCallback>
Chris@16:   void mcgregor_common_subgraphs
Chris@16:   (const GraphFirst& graph1,
Chris@16:    const GraphSecond& graph2,
Chris@16:    const VertexIndexMapFirst vindex_map1,
Chris@16:    const VertexIndexMapSecond vindex_map2,
Chris@16:    EdgeEquivalencePredicate edges_equivalent,
Chris@16:    VertexEquivalencePredicate vertices_equivalent,
Chris@16:    bool only_connected_subgraphs,
Chris@16:    SubGraphCallback user_callback)
Chris@16:   {
Chris@16:       
Chris@16:     detail::mcgregor_common_subgraphs_internal_init
Chris@16:       (graph1, graph2,
Chris@16:        vindex_map1, vindex_map2,
Chris@16:        edges_equivalent, vertices_equivalent,
Chris@16:        only_connected_subgraphs,
Chris@16:        user_callback);
Chris@16:   }
Chris@16:   
Chris@16:   // Variant of mcgregor_common_subgraphs with all default parameters
Chris@16:   template <typename GraphFirst,
Chris@16:             typename GraphSecond,
Chris@16:             typename SubGraphCallback>
Chris@16:   void mcgregor_common_subgraphs
Chris@16:   (const GraphFirst& graph1,
Chris@16:    const GraphSecond& graph2,
Chris@16:    bool only_connected_subgraphs,
Chris@16:    SubGraphCallback user_callback)
Chris@16:   {
Chris@16:       
Chris@16:     detail::mcgregor_common_subgraphs_internal_init
Chris@16:       (graph1, graph2,
Chris@16:        get(vertex_index, graph1), get(vertex_index, graph2),
Chris@16:        always_equivalent(), always_equivalent(),
Chris@16:        only_connected_subgraphs, user_callback);
Chris@16:   }
Chris@16: 
Chris@16:   // Named parameter variant of mcgregor_common_subgraphs
Chris@16:   template <typename GraphFirst,
Chris@16:             typename GraphSecond,
Chris@16:             typename SubGraphCallback,
Chris@16:             typename Param,
Chris@16:             typename Tag,
Chris@16:             typename Rest>
Chris@16:   void mcgregor_common_subgraphs
Chris@16:   (const GraphFirst& graph1,
Chris@16:    const GraphSecond& graph2,
Chris@16:    bool only_connected_subgraphs,
Chris@16:    SubGraphCallback user_callback,
Chris@16:    const bgl_named_params<Param, Tag, Rest>& params)
Chris@16:   {
Chris@16:       
Chris@16:     detail::mcgregor_common_subgraphs_internal_init
Chris@16:       (graph1, graph2,
Chris@16:        choose_const_pmap(get_param(params, vertex_index1),
Chris@16:                          graph1, vertex_index),
Chris@16:        choose_const_pmap(get_param(params, vertex_index2),
Chris@16:                          graph2, vertex_index),
Chris@16:        choose_param(get_param(params, edges_equivalent_t()),
Chris@16:                     always_equivalent()),
Chris@16:        choose_param(get_param(params, vertices_equivalent_t()),
Chris@16:                     always_equivalent()),
Chris@16:        only_connected_subgraphs, user_callback);
Chris@16:   }
Chris@16: 
Chris@16:   // ==========================================================================
Chris@16: 
Chris@16:   namespace detail {
Chris@16: 
Chris@16:     // Binary function object that intercepts subgraphs from
Chris@16:     // mcgregor_common_subgraphs_internal and maintains a cache of
Chris@16:     // unique subgraphs.  The user callback is invoked for each unique
Chris@16:     // subgraph.
Chris@16:     template <typename GraphFirst,
Chris@16:               typename GraphSecond,
Chris@16:               typename VertexIndexMapFirst,
Chris@16:               typename VertexIndexMapSecond,
Chris@16:               typename SubGraphCallback>
Chris@16:     struct unique_subgraph_interceptor {
Chris@16: 
Chris@16:       typedef typename graph_traits<GraphFirst>::vertices_size_type
Chris@16:         VertexSizeFirst;
Chris@16: 
Chris@16:       typedef mcgregor_common_subgraph_traits<GraphFirst, GraphSecond,
Chris@16:         VertexIndexMapFirst, VertexIndexMapSecond> SubGraphTraits;
Chris@16:         
Chris@16:       typedef typename SubGraphTraits::correspondence_map_first_to_second_type
Chris@16:         CachedCorrespondenceMapFirstToSecond;
Chris@16: 
Chris@16:       typedef typename SubGraphTraits::correspondence_map_second_to_first_type
Chris@16:         CachedCorrespondenceMapSecondToFirst;
Chris@16: 
Chris@16:       typedef std::pair<VertexSizeFirst,
Chris@16:         std::pair<CachedCorrespondenceMapFirstToSecond,
Chris@16:                   CachedCorrespondenceMapSecondToFirst> > SubGraph;
Chris@16:                 
Chris@16:       typedef std::vector<SubGraph> SubGraphList;
Chris@16: 
Chris@16:       unique_subgraph_interceptor(const GraphFirst& graph1,
Chris@16:                                   const GraphSecond& graph2,
Chris@16:                                   const VertexIndexMapFirst vindex_map1,
Chris@16:                                   const VertexIndexMapSecond vindex_map2,
Chris@16:                                   SubGraphCallback user_callback) :                                  
Chris@16:         m_graph1(graph1), m_graph2(graph2),
Chris@16:         m_vindex_map1(vindex_map1), m_vindex_map2(vindex_map2),
Chris@16:         m_subgraphs(make_shared<SubGraphList>()),
Chris@16:         m_user_callback(user_callback) { }
Chris@16:       
Chris@16:       template <typename CorrespondenceMapFirstToSecond,
Chris@16:                 typename CorrespondenceMapSecondToFirst>
Chris@16:       bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
Chris@16:                       CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
Chris@16:                       VertexSizeFirst subgraph_size) {
Chris@16: 
Chris@16:         for (typename SubGraphList::const_iterator
Chris@16:                subgraph_iter = m_subgraphs->begin();
Chris@16:              subgraph_iter != m_subgraphs->end();
Chris@16:              ++subgraph_iter) {
Chris@16: 
Chris@16:           SubGraph subgraph_cached = *subgraph_iter;
Chris@16: 
Chris@16:           // Compare subgraph sizes
Chris@16:           if (subgraph_size != subgraph_cached.first) {
Chris@16:             continue;
Chris@16:           }
Chris@16:           
Chris@16:           if (!are_property_maps_different(correspondence_map_1_to_2,
Chris@16:                                            subgraph_cached.second.first,
Chris@16:                                            m_graph1)) {
Chris@16:                                     
Chris@16:             // New subgraph is a duplicate
Chris@16:             return (true);
Chris@16:           }
Chris@16:         }
Chris@16:   
Chris@16:         // Subgraph is unique, so make a cached copy
Chris@16:         CachedCorrespondenceMapFirstToSecond
Chris@16:           new_subgraph_1_to_2 = CachedCorrespondenceMapFirstToSecond
Chris@16:           (num_vertices(m_graph1), m_vindex_map1);
Chris@16: 
Chris@16:         CachedCorrespondenceMapSecondToFirst
Chris@16:           new_subgraph_2_to_1 = CorrespondenceMapSecondToFirst
Chris@16:           (num_vertices(m_graph2), m_vindex_map2);
Chris@16: 
Chris@16:         BGL_FORALL_VERTICES_T(vertex1, m_graph1, GraphFirst) {
Chris@16:           put(new_subgraph_1_to_2, vertex1, get(correspondence_map_1_to_2, vertex1));
Chris@16:         }
Chris@16: 
Chris@16:         BGL_FORALL_VERTICES_T(vertex2, m_graph2, GraphFirst) {
Chris@16:           put(new_subgraph_2_to_1, vertex2, get(correspondence_map_2_to_1, vertex2));
Chris@16:         }
Chris@16: 
Chris@16:         m_subgraphs->push_back(std::make_pair(subgraph_size,
Chris@16:           std::make_pair(new_subgraph_1_to_2,
Chris@16:                          new_subgraph_2_to_1)));
Chris@16:         
Chris@16:         return (m_user_callback(correspondence_map_1_to_2,
Chris@16:                                 correspondence_map_2_to_1,
Chris@16:                                 subgraph_size));
Chris@16:       }
Chris@16:     
Chris@16:     private:
Chris@16:       const GraphFirst& m_graph1;
Chris@16:       const GraphFirst& m_graph2;
Chris@16:       const VertexIndexMapFirst m_vindex_map1;
Chris@16:       const VertexIndexMapSecond m_vindex_map2;
Chris@16:       shared_ptr<SubGraphList> m_subgraphs;
Chris@16:       SubGraphCallback m_user_callback;
Chris@16:     };
Chris@16:     
Chris@16:   } // namespace detail
Chris@16: 
Chris@16:   // Enumerates all unique common subgraphs between graph1 and graph2.
Chris@16:   // The user callback is invoked for each unique subgraph as they are
Chris@16:   // discovered.
Chris@16:   template <typename GraphFirst,
Chris@16:             typename GraphSecond,
Chris@16:             typename VertexIndexMapFirst,
Chris@16:             typename VertexIndexMapSecond,
Chris@16:             typename EdgeEquivalencePredicate,
Chris@16:             typename VertexEquivalencePredicate,
Chris@16:             typename SubGraphCallback>
Chris@16:   void mcgregor_common_subgraphs_unique
Chris@16:   (const GraphFirst& graph1,
Chris@16:    const GraphSecond& graph2,
Chris@16:    const VertexIndexMapFirst vindex_map1,
Chris@16:    const VertexIndexMapSecond vindex_map2,
Chris@16:    EdgeEquivalencePredicate edges_equivalent,
Chris@16:    VertexEquivalencePredicate vertices_equivalent,
Chris@16:    bool only_connected_subgraphs,
Chris@16:    SubGraphCallback user_callback)
Chris@16:   {
Chris@16:     detail::unique_subgraph_interceptor<GraphFirst, GraphSecond,
Chris@16:       VertexIndexMapFirst, VertexIndexMapSecond,
Chris@16:       SubGraphCallback> unique_callback
Chris@16:       (graph1, graph2,
Chris@16:        vindex_map1, vindex_map2,
Chris@16:        user_callback);
Chris@16:       
Chris@16:     detail::mcgregor_common_subgraphs_internal_init
Chris@16:       (graph1, graph2,
Chris@16:        vindex_map1, vindex_map2,
Chris@16:        edges_equivalent, vertices_equivalent,
Chris@16:        only_connected_subgraphs, unique_callback);
Chris@16:   }
Chris@16: 
Chris@16:   // Variant of mcgregor_common_subgraphs_unique with all default
Chris@16:   // parameters.
Chris@16:   template <typename GraphFirst,
Chris@16:             typename GraphSecond,
Chris@16:             typename SubGraphCallback>
Chris@16:   void mcgregor_common_subgraphs_unique
Chris@16:   (const GraphFirst& graph1,
Chris@16:    const GraphSecond& graph2,
Chris@16:    bool only_connected_subgraphs,
Chris@16:    SubGraphCallback user_callback)
Chris@16:   {
Chris@16:     mcgregor_common_subgraphs_unique
Chris@16:       (graph1, graph2,
Chris@16:        get(vertex_index, graph1), get(vertex_index, graph2),
Chris@16:        always_equivalent(), always_equivalent(),
Chris@16:        only_connected_subgraphs, user_callback);
Chris@16:   }
Chris@16: 
Chris@16:   // Named parameter variant of mcgregor_common_subgraphs_unique
Chris@16:   template <typename GraphFirst,
Chris@16:             typename GraphSecond,
Chris@16:             typename SubGraphCallback,
Chris@16:             typename Param,
Chris@16:             typename Tag,
Chris@16:             typename Rest>
Chris@16:   void mcgregor_common_subgraphs_unique
Chris@16:   (const GraphFirst& graph1,
Chris@16:    const GraphSecond& graph2,
Chris@16:    bool only_connected_subgraphs,
Chris@16:    SubGraphCallback user_callback,
Chris@16:    const bgl_named_params<Param, Tag, Rest>& params)
Chris@16:   {
Chris@16:     mcgregor_common_subgraphs_unique
Chris@16:       (graph1, graph2,
Chris@16:        choose_const_pmap(get_param(params, vertex_index1),
Chris@16:                          graph1, vertex_index),
Chris@16:        choose_const_pmap(get_param(params, vertex_index2),
Chris@16:                          graph2, vertex_index),
Chris@16:        choose_param(get_param(params, edges_equivalent_t()),
Chris@16:                     always_equivalent()),
Chris@16:        choose_param(get_param(params, vertices_equivalent_t()),
Chris@16:                     always_equivalent()),
Chris@16:        only_connected_subgraphs, user_callback);
Chris@16:   }
Chris@16: 
Chris@16:   // ==========================================================================
Chris@16: 
Chris@16:   namespace detail {
Chris@16: 
Chris@16:     // Binary function object that intercepts subgraphs from
Chris@16:     // mcgregor_common_subgraphs_internal and maintains a cache of the
Chris@16:     // largest subgraphs.
Chris@16:     template <typename GraphFirst,
Chris@16:               typename GraphSecond,
Chris@16:               typename VertexIndexMapFirst,
Chris@16:               typename VertexIndexMapSecond,
Chris@16:               typename SubGraphCallback>
Chris@16:     struct maximum_subgraph_interceptor {
Chris@16: 
Chris@16:       typedef typename graph_traits<GraphFirst>::vertices_size_type
Chris@16:         VertexSizeFirst;
Chris@16: 
Chris@16:       typedef mcgregor_common_subgraph_traits<GraphFirst, GraphSecond,
Chris@16:         VertexIndexMapFirst, VertexIndexMapSecond> SubGraphTraits;
Chris@16:         
Chris@16:       typedef typename SubGraphTraits::correspondence_map_first_to_second_type
Chris@16:         CachedCorrespondenceMapFirstToSecond;
Chris@16: 
Chris@16:       typedef typename SubGraphTraits::correspondence_map_second_to_first_type
Chris@16:         CachedCorrespondenceMapSecondToFirst;
Chris@16: 
Chris@16:       typedef std::pair<VertexSizeFirst,
Chris@16:         std::pair<CachedCorrespondenceMapFirstToSecond,
Chris@16:                   CachedCorrespondenceMapSecondToFirst> > SubGraph;
Chris@16: 
Chris@16:       typedef std::vector<SubGraph> SubGraphList;
Chris@16: 
Chris@16:       maximum_subgraph_interceptor(const GraphFirst& graph1,
Chris@16:                                    const GraphSecond& graph2,
Chris@16:                                    const VertexIndexMapFirst vindex_map1,
Chris@16:                                    const VertexIndexMapSecond vindex_map2,
Chris@16:                                    SubGraphCallback user_callback) :
Chris@16:         m_graph1(graph1), m_graph2(graph2),
Chris@16:         m_vindex_map1(vindex_map1), m_vindex_map2(vindex_map2),
Chris@16:         m_subgraphs(make_shared<SubGraphList>()),
Chris@16:         m_largest_size_so_far(make_shared<VertexSizeFirst>(0)),
Chris@16:         m_user_callback(user_callback) { }
Chris@16: 
Chris@16:       template <typename CorrespondenceMapFirstToSecond,
Chris@16:                 typename CorrespondenceMapSecondToFirst>
Chris@16:       bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
Chris@16:                       CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
Chris@16:                       VertexSizeFirst subgraph_size) {
Chris@16: 
Chris@16:         if (subgraph_size > *m_largest_size_so_far) {
Chris@16:           m_subgraphs->clear();
Chris@16:           *m_largest_size_so_far = subgraph_size;
Chris@16:         }
Chris@16: 
Chris@16:         if (subgraph_size == *m_largest_size_so_far) {
Chris@16:         
Chris@16:           // Make a cached copy
Chris@16:           CachedCorrespondenceMapFirstToSecond
Chris@16:             new_subgraph_1_to_2 = CachedCorrespondenceMapFirstToSecond
Chris@16:             (num_vertices(m_graph1), m_vindex_map1);
Chris@16: 
Chris@16:           CachedCorrespondenceMapSecondToFirst
Chris@16:             new_subgraph_2_to_1 = CachedCorrespondenceMapSecondToFirst
Chris@16:             (num_vertices(m_graph2), m_vindex_map2);
Chris@16: 
Chris@16:           BGL_FORALL_VERTICES_T(vertex1, m_graph1, GraphFirst) {
Chris@16:             put(new_subgraph_1_to_2, vertex1, get(correspondence_map_1_to_2, vertex1));
Chris@16:           }
Chris@16: 
Chris@16:           BGL_FORALL_VERTICES_T(vertex2, m_graph2, GraphFirst) {
Chris@16:             put(new_subgraph_2_to_1, vertex2, get(correspondence_map_2_to_1, vertex2));
Chris@16:           }
Chris@16: 
Chris@16:           m_subgraphs->push_back(std::make_pair(subgraph_size,
Chris@16:             std::make_pair(new_subgraph_1_to_2,
Chris@16:                            new_subgraph_2_to_1)));
Chris@16:         }
Chris@16: 
Chris@16:         return (true);
Chris@16:       }
Chris@16: 
Chris@16:       void output_subgraphs() {
Chris@16:         for (typename SubGraphList::const_iterator
Chris@16:                subgraph_iter = m_subgraphs->begin();
Chris@16:              subgraph_iter != m_subgraphs->end();
Chris@16:              ++subgraph_iter) {
Chris@16: 
Chris@16:           SubGraph subgraph_cached = *subgraph_iter;
Chris@16:           m_user_callback(subgraph_cached.second.first,
Chris@16:                           subgraph_cached.second.second,
Chris@16:                           subgraph_cached.first);
Chris@16:         }
Chris@16:       }
Chris@16: 
Chris@16:     private:
Chris@16:       const GraphFirst& m_graph1;
Chris@16:       const GraphFirst& m_graph2;
Chris@16:       const VertexIndexMapFirst m_vindex_map1;
Chris@16:       const VertexIndexMapSecond m_vindex_map2;
Chris@16:       shared_ptr<SubGraphList> m_subgraphs;
Chris@16:       shared_ptr<VertexSizeFirst> m_largest_size_so_far;
Chris@16:       SubGraphCallback m_user_callback;
Chris@16:     };
Chris@16:     
Chris@16:   } // namespace detail
Chris@16: 
Chris@16:   // Enumerates the largest common subgraphs found between graph1
Chris@16:   // and graph2.  Note that the ENTIRE search space is explored before
Chris@16:   // user_callback is actually invoked.
Chris@16:   template <typename GraphFirst,
Chris@16:             typename GraphSecond,
Chris@16:             typename VertexIndexMapFirst,
Chris@16:             typename VertexIndexMapSecond,
Chris@16:             typename EdgeEquivalencePredicate,
Chris@16:             typename VertexEquivalencePredicate,
Chris@16:             typename SubGraphCallback>
Chris@16:   void mcgregor_common_subgraphs_maximum
Chris@16:   (const GraphFirst& graph1,
Chris@16:    const GraphSecond& graph2,
Chris@16:    const VertexIndexMapFirst vindex_map1,
Chris@16:    const VertexIndexMapSecond vindex_map2,
Chris@16:    EdgeEquivalencePredicate edges_equivalent,
Chris@16:    VertexEquivalencePredicate vertices_equivalent,
Chris@16:    bool only_connected_subgraphs,
Chris@16:    SubGraphCallback user_callback)
Chris@16:   {
Chris@16:     detail::maximum_subgraph_interceptor<GraphFirst, GraphSecond,
Chris@16:       VertexIndexMapFirst, VertexIndexMapSecond, SubGraphCallback>
Chris@16:       max_interceptor
Chris@16:       (graph1, graph2, vindex_map1, vindex_map2, user_callback);
Chris@16:       
Chris@16:     detail::mcgregor_common_subgraphs_internal_init
Chris@16:       (graph1, graph2,
Chris@16:        vindex_map1, vindex_map2,
Chris@16:        edges_equivalent, vertices_equivalent,
Chris@16:        only_connected_subgraphs, max_interceptor);
Chris@16: 
Chris@16:     // Only output the largest subgraphs
Chris@16:     max_interceptor.output_subgraphs();
Chris@16:   }
Chris@16: 
Chris@16:   // Variant of mcgregor_common_subgraphs_maximum with all default
Chris@16:   // parameters.
Chris@16:   template <typename GraphFirst,
Chris@16:             typename GraphSecond,
Chris@16:             typename SubGraphCallback>
Chris@16:   void mcgregor_common_subgraphs_maximum
Chris@16:   (const GraphFirst& graph1,
Chris@16:    const GraphSecond& graph2,
Chris@16:    bool only_connected_subgraphs,
Chris@16:    SubGraphCallback user_callback)
Chris@16:   {
Chris@16:     mcgregor_common_subgraphs_maximum
Chris@16:       (graph1, graph2,
Chris@16:        get(vertex_index, graph1), get(vertex_index, graph2),
Chris@16:        always_equivalent(), always_equivalent(),
Chris@16:        only_connected_subgraphs, user_callback);
Chris@16:   }
Chris@16: 
Chris@16:   // Named parameter variant of mcgregor_common_subgraphs_maximum
Chris@16:   template <typename GraphFirst,
Chris@16:             typename GraphSecond,
Chris@16:             typename SubGraphCallback,
Chris@16:             typename Param,
Chris@16:             typename Tag,
Chris@16:             typename Rest>
Chris@16:   void mcgregor_common_subgraphs_maximum
Chris@16:   (const GraphFirst& graph1,
Chris@16:    const GraphSecond& graph2,
Chris@16:    bool only_connected_subgraphs,
Chris@16:    SubGraphCallback user_callback,
Chris@16:    const bgl_named_params<Param, Tag, Rest>& params)
Chris@16:   {
Chris@16:     mcgregor_common_subgraphs_maximum
Chris@16:       (graph1, graph2,
Chris@16:        choose_const_pmap(get_param(params, vertex_index1),
Chris@16:                          graph1, vertex_index),
Chris@16:        choose_const_pmap(get_param(params, vertex_index2),
Chris@16:                          graph2, vertex_index),
Chris@16:        choose_param(get_param(params, edges_equivalent_t()),
Chris@16:                     always_equivalent()),
Chris@16:        choose_param(get_param(params, vertices_equivalent_t()),
Chris@16:                     always_equivalent()),
Chris@16:        only_connected_subgraphs, user_callback);
Chris@16:   }
Chris@16: 
Chris@16:   // ==========================================================================
Chris@16: 
Chris@16:   namespace detail {
Chris@16: 
Chris@16:     // Binary function object that intercepts subgraphs from
Chris@16:     // mcgregor_common_subgraphs_internal and maintains a cache of the
Chris@16:     // largest, unique subgraphs.
Chris@16:     template <typename GraphFirst,
Chris@16:               typename GraphSecond,
Chris@16:               typename VertexIndexMapFirst,
Chris@16:               typename VertexIndexMapSecond,
Chris@16:               typename SubGraphCallback>
Chris@16:     struct unique_maximum_subgraph_interceptor {
Chris@16: 
Chris@16:       typedef typename graph_traits<GraphFirst>::vertices_size_type
Chris@16:         VertexSizeFirst;
Chris@16: 
Chris@16:       typedef mcgregor_common_subgraph_traits<GraphFirst, GraphSecond,
Chris@16:         VertexIndexMapFirst, VertexIndexMapSecond> SubGraphTraits;
Chris@16:         
Chris@16:       typedef typename SubGraphTraits::correspondence_map_first_to_second_type
Chris@16:         CachedCorrespondenceMapFirstToSecond;
Chris@16: 
Chris@16:       typedef typename SubGraphTraits::correspondence_map_second_to_first_type
Chris@16:         CachedCorrespondenceMapSecondToFirst;
Chris@16: 
Chris@16:       typedef std::pair<VertexSizeFirst,
Chris@16:         std::pair<CachedCorrespondenceMapFirstToSecond,
Chris@16:                   CachedCorrespondenceMapSecondToFirst> > SubGraph;
Chris@16: 
Chris@16:       typedef std::vector<SubGraph> SubGraphList;
Chris@16: 
Chris@16:       unique_maximum_subgraph_interceptor(const GraphFirst& graph1,
Chris@16:                                           const GraphSecond& graph2,
Chris@16:                                           const VertexIndexMapFirst vindex_map1,
Chris@16:                                           const VertexIndexMapSecond vindex_map2,
Chris@16:                                           SubGraphCallback user_callback) :                                  
Chris@16:         m_graph1(graph1), m_graph2(graph2),
Chris@16:         m_vindex_map1(vindex_map1), m_vindex_map2(vindex_map2),
Chris@16:         m_subgraphs(make_shared<SubGraphList>()),
Chris@16:         m_largest_size_so_far(make_shared<VertexSizeFirst>(0)),
Chris@16:         m_user_callback(user_callback) { }        
Chris@16:       
Chris@16:       template <typename CorrespondenceMapFirstToSecond,
Chris@16:                 typename CorrespondenceMapSecondToFirst>
Chris@16:       bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
Chris@16:                       CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
Chris@16:                       VertexSizeFirst subgraph_size) {
Chris@16: 
Chris@16:         if (subgraph_size > *m_largest_size_so_far) {
Chris@16:           m_subgraphs->clear();
Chris@16:           *m_largest_size_so_far = subgraph_size;
Chris@16:         }
Chris@16: 
Chris@16:         if (subgraph_size == *m_largest_size_so_far) {
Chris@16: 
Chris@16:           // Check if subgraph is unique
Chris@16:           for (typename SubGraphList::const_iterator
Chris@16:                  subgraph_iter = m_subgraphs->begin();
Chris@16:                subgraph_iter != m_subgraphs->end();
Chris@16:                ++subgraph_iter) {
Chris@16:   
Chris@16:             SubGraph subgraph_cached = *subgraph_iter;
Chris@16:   
Chris@16:             if (!are_property_maps_different(correspondence_map_1_to_2,
Chris@16:                                              subgraph_cached.second.first,
Chris@16:                                              m_graph1)) {
Chris@16:                                       
Chris@16:               // New subgraph is a duplicate
Chris@16:               return (true);
Chris@16:             }
Chris@16:           }
Chris@16:     
Chris@16:           // Subgraph is unique, so make a cached copy
Chris@16:           CachedCorrespondenceMapFirstToSecond
Chris@16:             new_subgraph_1_to_2 = CachedCorrespondenceMapFirstToSecond
Chris@16:             (num_vertices(m_graph1), m_vindex_map1);
Chris@16: 
Chris@16:           CachedCorrespondenceMapSecondToFirst
Chris@16:             new_subgraph_2_to_1 = CachedCorrespondenceMapSecondToFirst
Chris@16:             (num_vertices(m_graph2), m_vindex_map2);
Chris@16: 
Chris@16:           BGL_FORALL_VERTICES_T(vertex1, m_graph1, GraphFirst) {
Chris@16:             put(new_subgraph_1_to_2, vertex1, get(correspondence_map_1_to_2, vertex1));
Chris@16:           }
Chris@16: 
Chris@16:           BGL_FORALL_VERTICES_T(vertex2, m_graph2, GraphFirst) {
Chris@16:             put(new_subgraph_2_to_1, vertex2, get(correspondence_map_2_to_1, vertex2));
Chris@16:           }
Chris@16: 
Chris@16:           m_subgraphs->push_back(std::make_pair(subgraph_size,
Chris@16:             std::make_pair(new_subgraph_1_to_2,
Chris@16:                            new_subgraph_2_to_1)));
Chris@16:         }
Chris@16:     
Chris@16:         return (true);
Chris@16:       }
Chris@16: 
Chris@16:       void output_subgraphs() {
Chris@16:         for (typename SubGraphList::const_iterator
Chris@16:                subgraph_iter = m_subgraphs->begin();
Chris@16:              subgraph_iter != m_subgraphs->end();
Chris@16:              ++subgraph_iter) {
Chris@16: 
Chris@16:           SubGraph subgraph_cached = *subgraph_iter;
Chris@16:           m_user_callback(subgraph_cached.second.first,
Chris@16:                           subgraph_cached.second.second,
Chris@16:                           subgraph_cached.first);
Chris@16:         }
Chris@16:       }
Chris@16:     
Chris@16:     private:
Chris@16:       const GraphFirst& m_graph1;
Chris@16:       const GraphFirst& m_graph2;
Chris@16:       const VertexIndexMapFirst m_vindex_map1;
Chris@16:       const VertexIndexMapSecond m_vindex_map2;
Chris@16:       shared_ptr<SubGraphList> m_subgraphs;
Chris@16:       shared_ptr<VertexSizeFirst> m_largest_size_so_far;
Chris@16:       SubGraphCallback m_user_callback;
Chris@16:     };
Chris@16:     
Chris@16:   } // namespace detail
Chris@16: 
Chris@16:   // Enumerates the largest, unique common subgraphs found between
Chris@16:   // graph1 and graph2.  Note that the ENTIRE search space is explored
Chris@16:   // before user_callback is actually invoked.
Chris@16:   template <typename GraphFirst,
Chris@16:             typename GraphSecond,
Chris@16:             typename VertexIndexMapFirst,
Chris@16:             typename VertexIndexMapSecond,
Chris@16:             typename EdgeEquivalencePredicate,
Chris@16:             typename VertexEquivalencePredicate,
Chris@16:             typename SubGraphCallback>
Chris@16:   void mcgregor_common_subgraphs_maximum_unique
Chris@16:   (const GraphFirst& graph1,
Chris@16:    const GraphSecond& graph2,
Chris@16:    const VertexIndexMapFirst vindex_map1,
Chris@16:    const VertexIndexMapSecond vindex_map2,
Chris@16:    EdgeEquivalencePredicate edges_equivalent,
Chris@16:    VertexEquivalencePredicate vertices_equivalent,
Chris@16:    bool only_connected_subgraphs,
Chris@16:    SubGraphCallback user_callback)
Chris@16:   {
Chris@16:     detail::unique_maximum_subgraph_interceptor<GraphFirst, GraphSecond,
Chris@16:       VertexIndexMapFirst, VertexIndexMapSecond, SubGraphCallback>
Chris@16:       unique_max_interceptor
Chris@16:       (graph1, graph2, vindex_map1, vindex_map2, user_callback);
Chris@16:       
Chris@16:     detail::mcgregor_common_subgraphs_internal_init
Chris@16:       (graph1, graph2,
Chris@16:        vindex_map1, vindex_map2,
Chris@16:        edges_equivalent, vertices_equivalent,
Chris@16:        only_connected_subgraphs, unique_max_interceptor);
Chris@16: 
Chris@16:     // Only output the largest, unique subgraphs
Chris@16:     unique_max_interceptor.output_subgraphs();
Chris@16:   }
Chris@16: 
Chris@16:   // Variant of mcgregor_common_subgraphs_maximum_unique with all default parameters
Chris@16:   template <typename GraphFirst,
Chris@16:             typename GraphSecond,
Chris@16:             typename SubGraphCallback>
Chris@16:   void mcgregor_common_subgraphs_maximum_unique
Chris@16:   (const GraphFirst& graph1,
Chris@16:    const GraphSecond& graph2,
Chris@16:    bool only_connected_subgraphs,
Chris@16:    SubGraphCallback user_callback)
Chris@16:   {
Chris@16: 
Chris@16:     mcgregor_common_subgraphs_maximum_unique
Chris@16:       (graph1, graph2,
Chris@16:        get(vertex_index, graph1), get(vertex_index, graph2),
Chris@16:        always_equivalent(), always_equivalent(),
Chris@16:        only_connected_subgraphs, user_callback);
Chris@16:   }
Chris@16: 
Chris@16:   // Named parameter variant of
Chris@16:   // mcgregor_common_subgraphs_maximum_unique
Chris@16:   template <typename GraphFirst,
Chris@16:             typename GraphSecond,
Chris@16:             typename SubGraphCallback,
Chris@16:             typename Param,
Chris@16:             typename Tag,
Chris@16:             typename Rest>
Chris@16:   void mcgregor_common_subgraphs_maximum_unique
Chris@16:   (const GraphFirst& graph1,
Chris@16:    const GraphSecond& graph2,
Chris@16:    bool only_connected_subgraphs,
Chris@16:    SubGraphCallback user_callback,
Chris@16:    const bgl_named_params<Param, Tag, Rest>& params)
Chris@16:   {
Chris@16:     mcgregor_common_subgraphs_maximum_unique
Chris@16:       (graph1, graph2,
Chris@16:        choose_const_pmap(get_param(params, vertex_index1),
Chris@16:                          graph1, vertex_index),
Chris@16:        choose_const_pmap(get_param(params, vertex_index2),
Chris@16:                          graph2, vertex_index),
Chris@16:        choose_param(get_param(params, edges_equivalent_t()),
Chris@16:                     always_equivalent()),
Chris@16:        choose_param(get_param(params, vertices_equivalent_t()),
Chris@16:                     always_equivalent()),
Chris@16:        only_connected_subgraphs, user_callback);
Chris@16:   }
Chris@16: 
Chris@16:   // ==========================================================================
Chris@16: 
Chris@16:   // Fills a membership map (vertex -> bool) using the information
Chris@16:   // present in correspondence_map_1_to_2. Every vertex in a
Chris@16:   // membership map will have a true value only if it is not
Chris@16:   // associated with a null vertex in the correspondence map.
Chris@16:   template <typename GraphSecond,
Chris@16:             typename GraphFirst,
Chris@16:             typename CorrespondenceMapFirstToSecond,
Chris@16:             typename MembershipMapFirst>
Chris@16:   void fill_membership_map
Chris@16:   (const GraphFirst& graph1,
Chris@16:    const CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
Chris@16:    MembershipMapFirst membership_map1) {
Chris@16: 
Chris@16:     BGL_FORALL_VERTICES_T(vertex1, graph1, GraphFirst) {
Chris@16:       put(membership_map1, vertex1,
Chris@16:           get(correspondence_map_1_to_2, vertex1) != graph_traits<GraphSecond>::null_vertex());
Chris@16:     }
Chris@16: 
Chris@16:   }
Chris@16: 
Chris@16:   // Traits associated with a membership map filtered graph.  Provided
Chris@16:   // for convenience to access graph and vertex filter types.
Chris@16:   template <typename Graph,
Chris@16:             typename MembershipMap>
Chris@16:   struct membership_filtered_graph_traits {
Chris@16:     typedef property_map_filter<MembershipMap> vertex_filter_type;
Chris@16:     typedef filtered_graph<Graph, keep_all, vertex_filter_type> graph_type;
Chris@16:   };
Chris@16: 
Chris@16:   // Returns a filtered sub-graph of graph whose edge and vertex
Chris@16:   // inclusion is dictated by membership_map.
Chris@16:   template <typename Graph,
Chris@16:             typename MembershipMap>            
Chris@16:   typename membership_filtered_graph_traits<Graph, MembershipMap>::graph_type
Chris@16:   make_membership_filtered_graph
Chris@16:   (const Graph& graph,
Chris@16:    MembershipMap& membership_map) {
Chris@16: 
Chris@16:     typedef membership_filtered_graph_traits<Graph, MembershipMap> MFGTraits;
Chris@16:     typedef typename MFGTraits::graph_type MembershipFilteredGraph;
Chris@16: 
Chris@16:     typename MFGTraits::vertex_filter_type v_filter(membership_map);
Chris@16: 
Chris@16:     return (MembershipFilteredGraph(graph, keep_all(), v_filter));
Chris@16:     
Chris@16:   }
Chris@16:   
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_MCGREGOR_COMMON_SUBGRAPHS_HPP