path: root/boost/graph/mcgregor_common_subgraphs.hpp

//=======================================================================
// Copyright 2009 Trustees of Indiana University.
// Authors: Michael Hansen, Andrew Lumsdaine
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================

#ifndef BOOST_GRAPH_MCGREGOR_COMMON_SUBGRAPHS_HPP
#define BOOST_GRAPH_MCGREGOR_COMMON_SUBGRAPHS_HPP

#include <algorithm>
#include <vector>
#include <stack>

#include <boost/make_shared.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/properties.hpp>
#include <boost/property_map/shared_array_property_map.hpp>

namespace boost {

  namespace detail {

    // Traits associated with common subgraphs, used mainly to keep a
    // consistent type for the correspondence maps.
    template <typename GraphFirst,
              typename GraphSecond,
              typename VertexIndexMapFirst,
              typename VertexIndexMapSecond>
    struct mcgregor_common_subgraph_traits {
      typedef typename graph_traits<GraphFirst>::vertex_descriptor vertex_first_type;
      typedef typename graph_traits<GraphSecond>::vertex_descriptor vertex_second_type;
      
      typedef shared_array_property_map<vertex_second_type, VertexIndexMapFirst>
        correspondence_map_first_to_second_type;
  
      typedef shared_array_property_map<vertex_first_type, VertexIndexMapSecond>
        correspondence_map_second_to_first_type;
    };  

  } // namespace detail

  // ==========================================================================

  // Binary function object that returns true if the values for item1
  // in property_map1 and item2 in property_map2 are equivalent.
  template <typename PropertyMapFirst,
            typename PropertyMapSecond>
  struct property_map_equivalent {
  
    property_map_equivalent(const PropertyMapFirst property_map1,
                            const PropertyMapSecond property_map2) :
      m_property_map1(property_map1),
      m_property_map2(property_map2) { }

    template <typename ItemFirst,
              typename ItemSecond>
    bool operator()(const ItemFirst item1, const ItemSecond item2) {
      return (get(m_property_map1, item1) == get(m_property_map2, item2));
    }
  
  private:
    const PropertyMapFirst m_property_map1;
    const PropertyMapSecond m_property_map2;
  };

  // Returns a property_map_equivalent object that compares the values
  // of property_map1 and property_map2.
  template <typename PropertyMapFirst,
            typename PropertyMapSecond>
  property_map_equivalent<PropertyMapFirst,
                          PropertyMapSecond>
  make_property_map_equivalent
  (const PropertyMapFirst property_map1,
   const PropertyMapSecond property_map2) {

    return (property_map_equivalent<PropertyMapFirst, PropertyMapSecond>
            (property_map1, property_map2));
  }

  // Binary function object that always returns true.  Used when
  // vertices or edges are always equivalent (i.e. have no labels).
  struct always_equivalent {
  
    template <typename ItemFirst,
              typename ItemSecond>
    bool operator()(const ItemFirst&, const ItemSecond&) {
      return (true);
    }
  };

  // ==========================================================================

  namespace detail {

    // Return true if new_vertex1 and new_vertex2 can extend the
    // subgraph represented by correspondence_map_1_to_2 and
    // correspondence_map_2_to_1.  The vertices_equivalent and
    // edges_equivalent predicates are used to test vertex and edge
    // equivalency between the two graphs.
    template <typename GraphFirst,
              typename GraphSecond,
              typename CorrespondenceMapFirstToSecond,
              typename CorrespondenceMapSecondToFirst,
              typename EdgeEquivalencePredicate,
              typename VertexEquivalencePredicate>
    bool can_extend_graph
    (const GraphFirst& graph1,
     const GraphSecond& graph2,
     CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
     CorrespondenceMapSecondToFirst /*correspondence_map_2_to_1*/,
     typename graph_traits<GraphFirst>::vertices_size_type subgraph_size,
     typename graph_traits<GraphFirst>::vertex_descriptor new_vertex1,
     typename graph_traits<GraphSecond>::vertex_descriptor new_vertex2,
     EdgeEquivalencePredicate edges_equivalent,
     VertexEquivalencePredicate vertices_equivalent,
     bool only_connected_subgraphs)
    {
      typedef typename graph_traits<GraphFirst>::vertex_descriptor VertexFirst;
      typedef typename graph_traits<GraphSecond>::vertex_descriptor VertexSecond;
      
      typedef typename graph_traits<GraphFirst>::edge_descriptor EdgeFirst;
      typedef typename graph_traits<GraphSecond>::edge_descriptor EdgeSecond;

      // Check vertex equality
      if (!vertices_equivalent(new_vertex1, new_vertex2)) {
        return (false);
      }

      // Vertices match and graph is empty, so we can extend the subgraph
      if (subgraph_size == 0) {
        return (true);
      }

      bool has_one_edge = false;

      // Verify edges with existing sub-graph
      BGL_FORALL_VERTICES_T(existing_vertex1, graph1, GraphFirst) {

        VertexSecond existing_vertex2 = get(correspondence_map_1_to_2, existing_vertex1);

        // Skip unassociated vertices
        if (existing_vertex2 == graph_traits<GraphSecond>::null_vertex()) {
          continue;
        }

        // NOTE: This will not work with parallel edges, since the
        // first matching edge is always chosen.
        EdgeFirst edge_to_new1, edge_from_new1;
        bool edge_to_new_exists1 = false, edge_from_new_exists1 = false;
        
        EdgeSecond edge_to_new2, edge_from_new2;
        bool edge_to_new_exists2 = false, edge_from_new_exists2 = false;

        // Search for edge from existing to new vertex (graph1)
        BGL_FORALL_OUTEDGES_T(existing_vertex1, edge1, graph1, GraphFirst) {
          if (target(edge1, graph1) == new_vertex1) {
            edge_to_new1 = edge1;
            edge_to_new_exists1 = true;
            break;
          }
        }

        // Search for edge from existing to new vertex (graph2)
        BGL_FORALL_OUTEDGES_T(existing_vertex2, edge2, graph2, GraphSecond) {
          if (target(edge2,  graph2) == new_vertex2) {
            edge_to_new2 = edge2;
            edge_to_new_exists2 = true;
            break;
          }
        }

        // Make sure edges from existing to new vertices are equivalent
        if ((edge_to_new_exists1 != edge_to_new_exists2) ||
            ((edge_to_new_exists1 && edge_to_new_exists2) &&
             !edges_equivalent(edge_to_new1, edge_to_new2))) {
              
          return (false);
        }

        bool is_undirected1 = is_undirected(graph1),
          is_undirected2 = is_undirected(graph2);

        if (is_undirected1 && is_undirected2) {

          // Edge in both graphs exists and both graphs are undirected
          if (edge_to_new_exists1 && edge_to_new_exists2) {
            has_one_edge = true;
          }

          continue;
        }
        else {

          if (!is_undirected1) {

            // Search for edge from new to existing vertex (graph1)
            BGL_FORALL_OUTEDGES_T(new_vertex1, edge1, graph1, GraphFirst) {
              if (target(edge1, graph1) == existing_vertex1) {
                edge_from_new1 = edge1;
                edge_from_new_exists1 = true;
                break;
              }
            }
          }

          if (!is_undirected2) {

            // Search for edge from new to existing vertex (graph2)
            BGL_FORALL_OUTEDGES_T(new_vertex2, edge2, graph2, GraphSecond) {
              if (target(edge2, graph2) == existing_vertex2) {
                edge_from_new2 = edge2;
                edge_from_new_exists2 = true;
                break;
              }
            }
          }

          // Make sure edges from new to existing vertices are equivalent
          if ((edge_from_new_exists1 != edge_from_new_exists2) ||
              ((edge_from_new_exists1 && edge_from_new_exists2) &&
               !edges_equivalent(edge_from_new1, edge_from_new2))) {
                
            return (false);
          }

          if ((edge_from_new_exists1 && edge_from_new_exists2) ||
              (edge_to_new_exists1 && edge_to_new_exists2)) {
            has_one_edge = true;
          }

        } // else

      } // BGL_FORALL_VERTICES_T

      // Make sure new vertices are connected to the existing subgraph
      if (only_connected_subgraphs && !has_one_edge) {
        return (false);
      }

      return (true);
    }    

    // Recursive method that does a depth-first search in the space of
    // potential subgraphs.  At each level, every new vertex pair from
    // both graphs is tested to see if it can extend the current
    // subgraph.  If so, the subgraph is output to subgraph_callback
    // in the form of two correspondence maps (one for each graph).
    // Returning false from subgraph_callback will terminate the
    // search.  Function returns true if the entire search space was
    // explored.
    template <typename GraphFirst,
              typename GraphSecond,
              typename VertexIndexMapFirst,
              typename VertexIndexMapSecond,
              typename CorrespondenceMapFirstToSecond,
              typename CorrespondenceMapSecondToFirst,
              typename VertexStackFirst,
              typename EdgeEquivalencePredicate,
              typename VertexEquivalencePredicate,
              typename SubGraphInternalCallback>
    bool mcgregor_common_subgraphs_internal
    (const GraphFirst& graph1,
     const GraphSecond& graph2,
     const VertexIndexMapFirst& vindex_map1,
     const VertexIndexMapSecond& vindex_map2,
     CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
     CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
     VertexStackFirst& vertex_stack1,
     EdgeEquivalencePredicate edges_equivalent,
     VertexEquivalencePredicate vertices_equivalent,
     bool only_connected_subgraphs,
     SubGraphInternalCallback subgraph_callback)
    {
      typedef typename graph_traits<GraphFirst>::vertex_descriptor VertexFirst;
      typedef typename graph_traits<GraphSecond>::vertex_descriptor VertexSecond;
      typedef typename graph_traits<GraphFirst>::vertices_size_type VertexSizeFirst;

      // Get iterators for vertices from both graphs
      typename graph_traits<GraphFirst>::vertex_iterator
        vertex1_iter, vertex1_end;
  
      typename graph_traits<GraphSecond>::vertex_iterator
        vertex2_begin, vertex2_end, vertex2_iter;
  
      boost::tie(vertex1_iter, vertex1_end) = vertices(graph1);
      boost::tie(vertex2_begin, vertex2_end) = vertices(graph2);
      vertex2_iter = vertex2_begin;
  
      // Iterate until all vertices have been visited
      BGL_FORALL_VERTICES_T(new_vertex1, graph1, GraphFirst) {

        VertexSecond existing_vertex2 = get(correspondence_map_1_to_2, new_vertex1);

        // Skip already matched vertices in first graph
        if (existing_vertex2 != graph_traits<GraphSecond>::null_vertex()) {
          continue;
        }
    
        BGL_FORALL_VERTICES_T(new_vertex2, graph2, GraphSecond) {

          VertexFirst existing_vertex1 = get(correspondence_map_2_to_1, new_vertex2);

          // Skip already matched vertices in second graph
          if (existing_vertex1 != graph_traits<GraphFirst>::null_vertex()) {
            continue;
          }

          // Check if current sub-graph can be extended with the matched vertex pair
          if (can_extend_graph(graph1, graph2,
                               correspondence_map_1_to_2, correspondence_map_2_to_1,
                               (VertexSizeFirst)vertex_stack1.size(),
                               new_vertex1, new_vertex2,
                               edges_equivalent, vertices_equivalent,
                               only_connected_subgraphs)) {

            // Keep track of old graph size for restoring later
            VertexSizeFirst old_graph_size = (VertexSizeFirst)vertex_stack1.size(),
              new_graph_size = old_graph_size + 1;

            // Extend subgraph
            put(correspondence_map_1_to_2, new_vertex1, new_vertex2);
            put(correspondence_map_2_to_1, new_vertex2, new_vertex1);
            vertex_stack1.push(new_vertex1);

            // Only output sub-graphs larger than a single vertex
            if (new_graph_size > 1) {
            
              // Returning false from the callback will cancel iteration
              if (!subgraph_callback(correspondence_map_1_to_2,
                                     correspondence_map_2_to_1,
                                     new_graph_size)) {
                return (false);
              }
            }
      
            // Depth-first search into the state space of possible sub-graphs
            bool continue_iteration =
              mcgregor_common_subgraphs_internal
              (graph1, graph2,
               vindex_map1, vindex_map2,
               correspondence_map_1_to_2, correspondence_map_2_to_1,
               vertex_stack1,
               edges_equivalent, vertices_equivalent,
               only_connected_subgraphs, subgraph_callback);

            if (!continue_iteration) {
              return (false);
            }
      
            // Restore previous state
            if (vertex_stack1.size() > old_graph_size) {
              
              VertexFirst stack_vertex1 = vertex_stack1.top();
              VertexSecond stack_vertex2 = get(correspondence_map_1_to_2,
                                               stack_vertex1);

              // Contract subgraph
              put(correspondence_map_1_to_2, stack_vertex1,
                  graph_traits<GraphSecond>::null_vertex());
            
              put(correspondence_map_2_to_1, stack_vertex2,
                  graph_traits<GraphFirst>::null_vertex());
                  
              vertex_stack1.pop();
           }

          } // if can_extend_graph

        } // BGL_FORALL_VERTICES_T (graph2)

      } // BGL_FORALL_VERTICES_T (graph1)

      return (true);
    }

    // Internal method that initializes blank correspondence maps and
    // a vertex stack for use in mcgregor_common_subgraphs_internal.
    template <typename GraphFirst,
              typename GraphSecond,
              typename VertexIndexMapFirst,
              typename VertexIndexMapSecond,
              typename EdgeEquivalencePredicate,
              typename VertexEquivalencePredicate,
              typename SubGraphInternalCallback>
    inline void mcgregor_common_subgraphs_internal_init
    (const GraphFirst& graph1,
     const GraphSecond& graph2,
     const VertexIndexMapFirst vindex_map1,
     const VertexIndexMapSecond vindex_map2,
     EdgeEquivalencePredicate edges_equivalent,
     VertexEquivalencePredicate vertices_equivalent,
     bool only_connected_subgraphs,
     SubGraphInternalCallback subgraph_callback)
    {
      typedef mcgregor_common_subgraph_traits<GraphFirst,
        GraphSecond, VertexIndexMapFirst,
        VertexIndexMapSecond> SubGraphTraits;
        
      typename SubGraphTraits::correspondence_map_first_to_second_type
        correspondence_map_1_to_2(num_vertices(graph1), vindex_map1);

      BGL_FORALL_VERTICES_T(vertex1, graph1, GraphFirst) {
        put(correspondence_map_1_to_2, vertex1,
            graph_traits<GraphSecond>::null_vertex());
      }
                                                 
      typename SubGraphTraits::correspondence_map_second_to_first_type
        correspondence_map_2_to_1(num_vertices(graph2), vindex_map2);

      BGL_FORALL_VERTICES_T(vertex2, graph2, GraphSecond) {
        put(correspondence_map_2_to_1, vertex2,
            graph_traits<GraphFirst>::null_vertex());
      }

      typedef typename graph_traits<GraphFirst>::vertex_descriptor
        VertexFirst;
        
      std::stack<VertexFirst> vertex_stack1;

      mcgregor_common_subgraphs_internal
        (graph1, graph2,
         vindex_map1, vindex_map2,
         correspondence_map_1_to_2, correspondence_map_2_to_1,
         vertex_stack1,
         edges_equivalent, vertices_equivalent,
         only_connected_subgraphs,
         subgraph_callback);
    }
    
  } // namespace detail

  // ==========================================================================

  // Enumerates all common subgraphs present in graph1 and graph2.
  // Continues until the search space has been fully explored or false
  // is returned from user_callback.
  template <typename GraphFirst,
            typename GraphSecond,
            typename VertexIndexMapFirst,
            typename VertexIndexMapSecond,
            typename EdgeEquivalencePredicate,
            typename VertexEquivalencePredicate,
            typename SubGraphCallback>
  void mcgregor_common_subgraphs
  (const GraphFirst& graph1,
   const GraphSecond& graph2,
   const VertexIndexMapFirst vindex_map1,
   const VertexIndexMapSecond vindex_map2,
   EdgeEquivalencePredicate edges_equivalent,
   VertexEquivalencePredicate vertices_equivalent,
   bool only_connected_subgraphs,
   SubGraphCallback user_callback)
  {
      
    detail::mcgregor_common_subgraphs_internal_init
      (graph1, graph2,
       vindex_map1, vindex_map2,
       edges_equivalent, vertices_equivalent,
       only_connected_subgraphs,
       user_callback);
  }
  
  // Variant of mcgregor_common_subgraphs with all default parameters
  template <typename GraphFirst,
            typename GraphSecond,
            typename SubGraphCallback>
  void mcgregor_common_subgraphs
  (const GraphFirst& graph1,
   const GraphSecond& graph2,
   bool only_connected_subgraphs,
   SubGraphCallback user_callback)
  {
      
    detail::mcgregor_common_subgraphs_internal_init
      (graph1, graph2,
       get(vertex_index, graph1), get(vertex_index, graph2),
       always_equivalent(), always_equivalent(),
       only_connected_subgraphs, user_callback);
  }

  // Named parameter variant of mcgregor_common_subgraphs
  template <typename GraphFirst,
            typename GraphSecond,
            typename SubGraphCallback,
            typename Param,
            typename Tag,
            typename Rest>
  void mcgregor_common_subgraphs
  (const GraphFirst& graph1,
   const GraphSecond& graph2,
   bool only_connected_subgraphs,
   SubGraphCallback user_callback,
   const bgl_named_params<Param, Tag, Rest>& params)
  {
      
    detail::mcgregor_common_subgraphs_internal_init
      (graph1, graph2,
       choose_const_pmap(get_param(params, vertex_index1),
                         graph1, vertex_index),
       choose_const_pmap(get_param(params, vertex_index2),
                         graph2, vertex_index),
       choose_param(get_param(params, edges_equivalent_t()),
                    always_equivalent()),
       choose_param(get_param(params, vertices_equivalent_t()),
                    always_equivalent()),
       only_connected_subgraphs, user_callback);
  }

  // ==========================================================================

  namespace detail {

    // Binary function object that intercepts subgraphs from
    // mcgregor_common_subgraphs_internal and maintains a cache of
    // unique subgraphs.  The user callback is invoked for each unique
    // subgraph.
    template <typename GraphFirst,
              typename GraphSecond,
              typename VertexIndexMapFirst,
              typename VertexIndexMapSecond,
              typename SubGraphCallback>
    struct unique_subgraph_interceptor {

      typedef typename graph_traits<GraphFirst>::vertices_size_type
        VertexSizeFirst;

      typedef mcgregor_common_subgraph_traits<GraphFirst, GraphSecond,
        VertexIndexMapFirst, VertexIndexMapSecond> SubGraphTraits;
        
      typedef typename SubGraphTraits::correspondence_map_first_to_second_type
        CachedCorrespondenceMapFirstToSecond;

      typedef typename SubGraphTraits::correspondence_map_second_to_first_type
        CachedCorrespondenceMapSecondToFirst;

      typedef std::pair<VertexSizeFirst,
        std::pair<CachedCorrespondenceMapFirstToSecond,
                  CachedCorrespondenceMapSecondToFirst> > SubGraph;
                
      typedef std::vector<SubGraph> SubGraphList;

      unique_subgraph_interceptor(const GraphFirst& graph1,
                                  const GraphSecond& graph2,
                                  const VertexIndexMapFirst vindex_map1,
                                  const VertexIndexMapSecond vindex_map2,
                                  SubGraphCallback user_callback) :                                  
        m_graph1(graph1), m_graph2(graph2),
        m_vindex_map1(vindex_map1), m_vindex_map2(vindex_map2),
        m_subgraphs(make_shared<SubGraphList>()),
        m_user_callback(user_callback) { }
      
      template <typename CorrespondenceMapFirstToSecond,
                typename CorrespondenceMapSecondToFirst>
      bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
                      CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
                      VertexSizeFirst subgraph_size) {

        for (typename SubGraphList::const_iterator
               subgraph_iter = m_subgraphs->begin();
             subgraph_iter != m_subgraphs->end();
             ++subgraph_iter) {

          SubGraph subgraph_cached = *subgraph_iter;

          // Compare subgraph sizes
          if (subgraph_size != subgraph_cached.first) {
            continue;
          }
          
          if (!are_property_maps_different(correspondence_map_1_to_2,
                                           subgraph_cached.second.first,
                                           m_graph1)) {
                                    
            // New subgraph is a duplicate
            return (true);
          }
        }
  
        // Subgraph is unique, so make a cached copy
        CachedCorrespondenceMapFirstToSecond
          new_subgraph_1_to_2 = CachedCorrespondenceMapFirstToSecond
          (num_vertices(m_graph1), m_vindex_map1);

        CachedCorrespondenceMapSecondToFirst
          new_subgraph_2_to_1 = CorrespondenceMapSecondToFirst
          (num_vertices(m_graph2), m_vindex_map2);

        BGL_FORALL_VERTICES_T(vertex1, m_graph1, GraphFirst) {
          put(new_subgraph_1_to_2, vertex1, get(correspondence_map_1_to_2, vertex1));
        }

        BGL_FORALL_VERTICES_T(vertex2, m_graph2, GraphFirst) {
          put(new_subgraph_2_to_1, vertex2, get(correspondence_map_2_to_1, vertex2));
        }

        m_subgraphs->push_back(std::make_pair(subgraph_size,
          std::make_pair(new_subgraph_1_to_2,
                         new_subgraph_2_to_1)));
        
        return (m_user_callback(correspondence_map_1_to_2,
                                correspondence_map_2_to_1,
                                subgraph_size));
      }
    
    private:
      const GraphFirst& m_graph1;
      const GraphFirst& m_graph2;
      const VertexIndexMapFirst m_vindex_map1;
      const VertexIndexMapSecond m_vindex_map2;
      shared_ptr<SubGraphList> m_subgraphs;
      SubGraphCallback m_user_callback;
    };
    
  } // namespace detail

  // Enumerates all unique common subgraphs between graph1 and graph2.
  // The user callback is invoked for each unique subgraph as they are
  // discovered.
  template <typename GraphFirst,
            typename GraphSecond,
            typename VertexIndexMapFirst,
            typename VertexIndexMapSecond,
            typename EdgeEquivalencePredicate,
            typename VertexEquivalencePredicate,
            typename SubGraphCallback>
  void mcgregor_common_subgraphs_unique
  (const GraphFirst& graph1,
   const GraphSecond& graph2,
   const VertexIndexMapFirst vindex_map1,
   const VertexIndexMapSecond vindex_map2,
   EdgeEquivalencePredicate edges_equivalent,
   VertexEquivalencePredicate vertices_equivalent,
   bool only_connected_subgraphs,
   SubGraphCallback user_callback)
  {
    detail::unique_subgraph_interceptor<GraphFirst, GraphSecond,
      VertexIndexMapFirst, VertexIndexMapSecond,
      SubGraphCallback> unique_callback
      (graph1, graph2,
       vindex_map1, vindex_map2,
       user_callback);
      
    detail::mcgregor_common_subgraphs_internal_init
      (graph1, graph2,
       vindex_map1, vindex_map2,
       edges_equivalent, vertices_equivalent,
       only_connected_subgraphs, unique_callback);
  }

  // Variant of mcgregor_common_subgraphs_unique with all default
  // parameters.
  template <typename GraphFirst,
            typename GraphSecond,
            typename SubGraphCallback>
  void mcgregor_common_subgraphs_unique
  (const GraphFirst& graph1,
   const GraphSecond& graph2,
   bool only_connected_subgraphs,
   SubGraphCallback user_callback)
  {
    mcgregor_common_subgraphs_unique
      (graph1, graph2,
       get(vertex_index, graph1), get(vertex_index, graph2),
       always_equivalent(), always_equivalent(),
       only_connected_subgraphs, user_callback);
  }

  // Named parameter variant of mcgregor_common_subgraphs_unique
  template <typename GraphFirst,
            typename GraphSecond,
            typename SubGraphCallback,
            typename Param,
            typename Tag,
            typename Rest>
  void mcgregor_common_subgraphs_unique
  (const GraphFirst& graph1,
   const GraphSecond& graph2,
   bool only_connected_subgraphs,
   SubGraphCallback user_callback,
   const bgl_named_params<Param, Tag, Rest>& params)
  {
    mcgregor_common_subgraphs_unique
      (graph1, graph2,
       choose_const_pmap(get_param(params, vertex_index1),
                         graph1, vertex_index),
       choose_const_pmap(get_param(params, vertex_index2),
                         graph2, vertex_index),
       choose_param(get_param(params, edges_equivalent_t()),
                    always_equivalent()),
       choose_param(get_param(params, vertices_equivalent_t()),
                    always_equivalent()),
       only_connected_subgraphs, user_callback);
  }

  // ==========================================================================

  namespace detail {

    // Binary function object that intercepts subgraphs from
    // mcgregor_common_subgraphs_internal and maintains a cache of the
    // largest subgraphs.
    template <typename GraphFirst,
              typename GraphSecond,
              typename VertexIndexMapFirst,
              typename VertexIndexMapSecond,
              typename SubGraphCallback>
    struct maximum_subgraph_interceptor {

      typedef typename graph_traits<GraphFirst>::vertices_size_type
        VertexSizeFirst;

      typedef mcgregor_common_subgraph_traits<GraphFirst, GraphSecond,
        VertexIndexMapFirst, VertexIndexMapSecond> SubGraphTraits;
        
      typedef typename SubGraphTraits::correspondence_map_first_to_second_type
        CachedCorrespondenceMapFirstToSecond;

      typedef typename SubGraphTraits::correspondence_map_second_to_first_type
        CachedCorrespondenceMapSecondToFirst;

      typedef std::pair<VertexSizeFirst,
        std::pair<CachedCorrespondenceMapFirstToSecond,
                  CachedCorrespondenceMapSecondToFirst> > SubGraph;

      typedef std::vector<SubGraph> SubGraphList;

      maximum_subgraph_interceptor(const GraphFirst& graph1,
                                   const GraphSecond& graph2,
                                   const VertexIndexMapFirst vindex_map1,
                                   const VertexIndexMapSecond vindex_map2,
                                   SubGraphCallback user_callback) :
        m_graph1(graph1), m_graph2(graph2),
        m_vindex_map1(vindex_map1), m_vindex_map2(vindex_map2),
        m_subgraphs(make_shared<SubGraphList>()),
        m_largest_size_so_far(make_shared<VertexSizeFirst>(0)),
        m_user_callback(user_callback) { }

      template <typename CorrespondenceMapFirstToSecond,
                typename CorrespondenceMapSecondToFirst>
      bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
                      CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
                      VertexSizeFirst subgraph_size) {

        if (subgraph_size > *m_largest_size_so_far) {
          m_subgraphs->clear();
          *m_largest_size_so_far = subgraph_size;
        }

        if (subgraph_size == *m_largest_size_so_far) {
        
          // Make a cached copy
          CachedCorrespondenceMapFirstToSecond
            new_subgraph_1_to_2 = CachedCorrespondenceMapFirstToSecond
            (num_vertices(m_graph1), m_vindex_map1);

          CachedCorrespondenceMapSecondToFirst
            new_subgraph_2_to_1 = CachedCorrespondenceMapSecondToFirst
            (num_vertices(m_graph2), m_vindex_map2);

          BGL_FORALL_VERTICES_T(vertex1, m_graph1, GraphFirst) {
            put(new_subgraph_1_to_2, vertex1, get(correspondence_map_1_to_2, vertex1));
          }

          BGL_FORALL_VERTICES_T(vertex2, m_graph2, GraphFirst) {
            put(new_subgraph_2_to_1, vertex2, get(correspondence_map_2_to_1, vertex2));
          }

          m_subgraphs->push_back(std::make_pair(subgraph_size,
            std::make_pair(new_subgraph_1_to_2,
                           new_subgraph_2_to_1)));
        }

        return (true);
      }

      void output_subgraphs() {
        for (typename SubGraphList::const_iterator
               subgraph_iter = m_subgraphs->begin();
             subgraph_iter != m_subgraphs->end();
             ++subgraph_iter) {

          SubGraph subgraph_cached = *subgraph_iter;
          m_user_callback(subgraph_cached.second.first,
                          subgraph_cached.second.second,
                          subgraph_cached.first);
        }
      }

    private:
      const GraphFirst& m_graph1;
      const GraphFirst& m_graph2;
      const VertexIndexMapFirst m_vindex_map1;
      const VertexIndexMapSecond m_vindex_map2;
      shared_ptr<SubGraphList> m_subgraphs;
      shared_ptr<VertexSizeFirst> m_largest_size_so_far;
      SubGraphCallback m_user_callback;
    };
    
  } // namespace detail

  // Enumerates the largest common subgraphs found between graph1
  // and graph2.  Note that the ENTIRE search space is explored before
  // user_callback is actually invoked.
  template <typename GraphFirst,
            typename GraphSecond,
            typename VertexIndexMapFirst,
            typename VertexIndexMapSecond,
            typename EdgeEquivalencePredicate,
            typename VertexEquivalencePredicate,
            typename SubGraphCallback>
  void mcgregor_common_subgraphs_maximum
  (const GraphFirst& graph1,
   const GraphSecond& graph2,
   const VertexIndexMapFirst vindex_map1,
   const VertexIndexMapSecond vindex_map2,
   EdgeEquivalencePredicate edges_equivalent,
   VertexEquivalencePredicate vertices_equivalent,
   bool only_connected_subgraphs,
   SubGraphCallback user_callback)
  {
    detail::maximum_subgraph_interceptor<GraphFirst, GraphSecond,
      VertexIndexMapFirst, VertexIndexMapSecond, SubGraphCallback>
      max_interceptor
      (graph1, graph2, vindex_map1, vindex_map2, user_callback);
      
    detail::mcgregor_common_subgraphs_internal_init
      (graph1, graph2,
       vindex_map1, vindex_map2,
       edges_equivalent, vertices_equivalent,
       only_connected_subgraphs, max_interceptor);

    // Only output the largest subgraphs
    max_interceptor.output_subgraphs();
  }

  // Variant of mcgregor_common_subgraphs_maximum with all default
  // parameters.
  template <typename GraphFirst,
            typename GraphSecond,
            typename SubGraphCallback>
  void mcgregor_common_subgraphs_maximum
  (const GraphFirst& graph1,
   const GraphSecond& graph2,
   bool only_connected_subgraphs,
   SubGraphCallback user_callback)
  {
    mcgregor_common_subgraphs_maximum
      (graph1, graph2,
       get(vertex_index, graph1), get(vertex_index, graph2),
       always_equivalent(), always_equivalent(),
       only_connected_subgraphs, user_callback);
  }

  // Named parameter variant of mcgregor_common_subgraphs_maximum
  template <typename GraphFirst,
            typename GraphSecond,
            typename SubGraphCallback,
            typename Param,
            typename Tag,
            typename Rest>
  void mcgregor_common_subgraphs_maximum
  (const GraphFirst& graph1,
   const GraphSecond& graph2,
   bool only_connected_subgraphs,
   SubGraphCallback user_callback,
   const bgl_named_params<Param, Tag, Rest>& params)
  {
    mcgregor_common_subgraphs_maximum
      (graph1, graph2,
       choose_const_pmap(get_param(params, vertex_index1),
                         graph1, vertex_index),
       choose_const_pmap(get_param(params, vertex_index2),
                         graph2, vertex_index),
       choose_param(get_param(params, edges_equivalent_t()),
                    always_equivalent()),
       choose_param(get_param(params, vertices_equivalent_t()),
                    always_equivalent()),
       only_connected_subgraphs, user_callback);
  }

  // ==========================================================================

  namespace detail {

    // Binary function object that intercepts subgraphs from
    // mcgregor_common_subgraphs_internal and maintains a cache of the
    // largest, unique subgraphs.
    template <typename GraphFirst,
              typename GraphSecond,
              typename VertexIndexMapFirst,
              typename VertexIndexMapSecond,
              typename SubGraphCallback>
    struct unique_maximum_subgraph_interceptor {

      typedef typename graph_traits<GraphFirst>::vertices_size_type
        VertexSizeFirst;

      typedef mcgregor_common_subgraph_traits<GraphFirst, GraphSecond,
        VertexIndexMapFirst, VertexIndexMapSecond> SubGraphTraits;
        
      typedef typename SubGraphTraits::correspondence_map_first_to_second_type
        CachedCorrespondenceMapFirstToSecond;

      typedef typename SubGraphTraits::correspondence_map_second_to_first_type
        CachedCorrespondenceMapSecondToFirst;

      typedef std::pair<VertexSizeFirst,
        std::pair<CachedCorrespondenceMapFirstToSecond,
                  CachedCorrespondenceMapSecondToFirst> > SubGraph;

      typedef std::vector<SubGraph> SubGraphList;

      unique_maximum_subgraph_interceptor(const GraphFirst& graph1,
                                          const GraphSecond& graph2,
                                          const VertexIndexMapFirst vindex_map1,
                                          const VertexIndexMapSecond vindex_map2,
                                          SubGraphCallback user_callback) :                                  
        m_graph1(graph1), m_graph2(graph2),
        m_vindex_map1(vindex_map1), m_vindex_map2(vindex_map2),
        m_subgraphs(make_shared<SubGraphList>()),
        m_largest_size_so_far(make_shared<VertexSizeFirst>(0)),
        m_user_callback(user_callback) { }        
      
      template <typename CorrespondenceMapFirstToSecond,
                typename CorrespondenceMapSecondToFirst>
      bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
                      CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
                      VertexSizeFirst subgraph_size) {

        if (subgraph_size > *m_largest_size_so_far) {
          m_subgraphs->clear();
          *m_largest_size_so_far = subgraph_size;
        }

        if (subgraph_size == *m_largest_size_so_far) {

          // Check if subgraph is unique
          for (typename SubGraphList::const_iterator
                 subgraph_iter = m_subgraphs->begin();
               subgraph_iter != m_subgraphs->end();
               ++subgraph_iter) {
  
            SubGraph subgraph_cached = *subgraph_iter;
  
            if (!are_property_maps_different(correspondence_map_1_to_2,
                                             subgraph_cached.second.first,
                                             m_graph1)) {
                                      
              // New subgraph is a duplicate
              return (true);
            }
          }
    
          // Subgraph is unique, so make a cached copy
          CachedCorrespondenceMapFirstToSecond
            new_subgraph_1_to_2 = CachedCorrespondenceMapFirstToSecond
            (num_vertices(m_graph1), m_vindex_map1);

          CachedCorrespondenceMapSecondToFirst
            new_subgraph_2_to_1 = CachedCorrespondenceMapSecondToFirst
            (num_vertices(m_graph2), m_vindex_map2);

          BGL_FORALL_VERTICES_T(vertex1, m_graph1, GraphFirst) {
            put(new_subgraph_1_to_2, vertex1, get(correspondence_map_1_to_2, vertex1));
          }

          BGL_FORALL_VERTICES_T(vertex2, m_graph2, GraphFirst) {
            put(new_subgraph_2_to_1, vertex2, get(correspondence_map_2_to_1, vertex2));
          }

          m_subgraphs->push_back(std::make_pair(subgraph_size,
            std::make_pair(new_subgraph_1_to_2,
                           new_subgraph_2_to_1)));
        }
    
        return (true);
      }

      void output_subgraphs() {
        for (typename SubGraphList::const_iterator
               subgraph_iter = m_subgraphs->begin();
             subgraph_iter != m_subgraphs->end();
             ++subgraph_iter) {

          SubGraph subgraph_cached = *subgraph_iter;
          m_user_callback(subgraph_cached.second.first,
                          subgraph_cached.second.second,
                          subgraph_cached.first);
        }
      }
    
    private:
      const GraphFirst& m_graph1;
      const GraphFirst& m_graph2;
      const VertexIndexMapFirst m_vindex_map1;
      const VertexIndexMapSecond m_vindex_map2;
      shared_ptr<SubGraphList> m_subgraphs;
      shared_ptr<VertexSizeFirst> m_largest_size_so_far;
      SubGraphCallback m_user_callback;
    };
    
  } // namespace detail

  // Enumerates the largest, unique common subgraphs found between
  // graph1 and graph2.  Note that the ENTIRE search space is explored
  // before user_callback is actually invoked.
  template <typename GraphFirst,
            typename GraphSecond,
            typename VertexIndexMapFirst,
            typename VertexIndexMapSecond,
            typename EdgeEquivalencePredicate,
            typename VertexEquivalencePredicate,
            typename SubGraphCallback>
  void mcgregor_common_subgraphs_maximum_unique
  (const GraphFirst& graph1,
   const GraphSecond& graph2,
   const VertexIndexMapFirst vindex_map1,
   const VertexIndexMapSecond vindex_map2,
   EdgeEquivalencePredicate edges_equivalent,
   VertexEquivalencePredicate vertices_equivalent,
   bool only_connected_subgraphs,
   SubGraphCallback user_callback)
  {
    detail::unique_maximum_subgraph_interceptor<GraphFirst, GraphSecond,
      VertexIndexMapFirst, VertexIndexMapSecond, SubGraphCallback>
      unique_max_interceptor
      (graph1, graph2, vindex_map1, vindex_map2, user_callback);
      
    detail::mcgregor_common_subgraphs_internal_init
      (graph1, graph2,
       vindex_map1, vindex_map2,
       edges_equivalent, vertices_equivalent,
       only_connected_subgraphs, unique_max_interceptor);

    // Only output the largest, unique subgraphs
    unique_max_interceptor.output_subgraphs();
  }

  // Variant of mcgregor_common_subgraphs_maximum_unique with all default parameters
  template <typename GraphFirst,
            typename GraphSecond,
            typename SubGraphCallback>
  void mcgregor_common_subgraphs_maximum_unique
  (const GraphFirst& graph1,
   const GraphSecond& graph2,
   bool only_connected_subgraphs,
   SubGraphCallback user_callback)
  {

    mcgregor_common_subgraphs_maximum_unique
      (graph1, graph2,
       get(vertex_index, graph1), get(vertex_index, graph2),
       always_equivalent(), always_equivalent(),
       only_connected_subgraphs, user_callback);
  }

  // Named parameter variant of
  // mcgregor_common_subgraphs_maximum_unique
  template <typename GraphFirst,
            typename GraphSecond,
            typename SubGraphCallback,
            typename Param,
            typename Tag,
            typename Rest>
  void mcgregor_common_subgraphs_maximum_unique
  (const GraphFirst& graph1,
   const GraphSecond& graph2,
   bool only_connected_subgraphs,
   SubGraphCallback user_callback,
   const bgl_named_params<Param, Tag, Rest>& params)
  {
    mcgregor_common_subgraphs_maximum_unique
      (graph1, graph2,
       choose_const_pmap(get_param(params, vertex_index1),
                         graph1, vertex_index),
       choose_const_pmap(get_param(params, vertex_index2),
                         graph2, vertex_index),
       choose_param(get_param(params, edges_equivalent_t()),
                    always_equivalent()),
       choose_param(get_param(params, vertices_equivalent_t()),
                    always_equivalent()),
       only_connected_subgraphs, user_callback);
  }

  // ==========================================================================

  // Fills a membership map (vertex -> bool) using the information
  // present in correspondence_map_1_to_2. Every vertex in a
  // membership map will have a true value only if it is not
  // associated with a null vertex in the correspondence map.
  template <typename GraphSecond,
            typename GraphFirst,
            typename CorrespondenceMapFirstToSecond,
            typename MembershipMapFirst>
  void fill_membership_map
  (const GraphFirst& graph1,
   const CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
   MembershipMapFirst membership_map1) {

    BGL_FORALL_VERTICES_T(vertex1, graph1, GraphFirst) {
      put(membership_map1, vertex1,
          get(correspondence_map_1_to_2, vertex1) != graph_traits<GraphSecond>::null_vertex());
    }

  }

  // Traits associated with a membership map filtered graph.  Provided
  // for convenience to access graph and vertex filter types.
  template <typename Graph,
            typename MembershipMap>
  struct membership_filtered_graph_traits {
    typedef property_map_filter<MembershipMap> vertex_filter_type;
    typedef filtered_graph<Graph, keep_all, vertex_filter_type> graph_type;
  };

  // Returns a filtered sub-graph of graph whose edge and vertex
  // inclusion is dictated by membership_map.
  template <typename Graph,
            typename MembershipMap>            
  typename membership_filtered_graph_traits<Graph, MembershipMap>::graph_type
  make_membership_filtered_graph
  (const Graph& graph,
   MembershipMap& membership_map) {

    typedef membership_filtered_graph_traits<Graph, MembershipMap> MFGTraits;
    typedef typename MFGTraits::graph_type MembershipFilteredGraph;

    typename MFGTraits::vertex_filter_type v_filter(membership_map);

    return (MembershipFilteredGraph(graph, keep_all(), v_filter));
    
  }
  
} // namespace boost

#endif // BOOST_GRAPH_MCGREGOR_COMMON_SUBGRAPHS_HPP