[Boost-commit] svn:boost r54069 - trunk/boost/graph

Subject: [Boost-commit] svn:boost r54069 - trunk/boost/graph
From: jewillco_at_[hidden]
Date: 2009-06-18 18:21:13

Author: jewillco
Date: 2009-06-18 18:21:12 EDT (Thu, 18 Jun 2009)
New Revision: 54069
URL: http://svn.boost.org/trac/boost/changeset/54069

Log:
Added new code from Michael Hansen; refs #3134
Added:
   trunk/boost/graph/mcgregor_common_subgraphs.hpp   (contents, props changed)
Text files modified: 
   trunk/boost/graph/filtered_graph.hpp |    17 +++++++++++++++++                       
   trunk/boost/graph/graph_utility.hpp  |    37 +++++++++++++++++++++++++++++++++++++   
   2 files changed, 54 insertions(+), 0 deletions(-)

Modified: trunk/boost/graph/filtered_graph.hpp
==============================================================================
--- trunk/boost/graph/filtered_graph.hpp	(original)
+++ trunk/boost/graph/filtered_graph.hpp	2009-06-18 18:21:12 EDT (Thu, 18 Jun 2009)
@@ -500,6 +500,23 @@
     return Filter(g, keep_all(), p);
   }
 
+  // Filter that uses a property map whose value_type is a boolean
+  template <typename PropertyMap>
+  struct property_map_filter {
+    
+    property_map_filter() { }
+      
+    property_map_filter(const PropertyMap& property_map) :
+      m_property_map(property_map) { }
+    
+    template <typename Key>
+    bool operator()(const Key& key) const {
+      return (get(m_property_map, key));
+    }
+    
+  private :
+    PropertyMap m_property_map;
+  };
 
 } // namespace boost
 

Modified: trunk/boost/graph/graph_utility.hpp
==============================================================================
--- trunk/boost/graph/graph_utility.hpp	(original)
+++ trunk/boost/graph/graph_utility.hpp	2009-06-18 18:21:12 EDT (Thu, 18 Jun 2009)
@@ -468,6 +468,43 @@
 
   } // namespace graph
 
+  #include <boost/graph/iteration_macros.hpp>
+
+  template <class PropertyIn, class PropertyOut, class Graph>
+  void copy_vertex_property(PropertyIn p_in, PropertyOut p_out, Graph& g)
+  {
+    BGL_FORALL_VERTICES_T(u, g, Graph)
+      put(p_out, u, get(p_in, g));
+  }
+
+  template <class PropertyIn, class PropertyOut, class Graph>
+  void copy_edge_property(PropertyIn p_in, PropertyOut p_out, Graph& g)
+  {
+    BGL_FORALL_EDGES_T(e, g, Graph)
+      put(p_out, e, get(p_in, g));
+  }
+
+  // Return true if property_map1 and property_map2 differ
+  // for any of the vertices in graph.
+  template <typename PropertyMapFirst,
+            typename PropertyMapSecond,
+            typename Graph>
+  bool are_property_maps_different
+  (const PropertyMapFirst property_map1,
+   const PropertyMapSecond property_map2,
+   const Graph& graph) {
+  
+    BGL_FORALL_VERTICES_T(vertex, graph, Graph) {
+      if (get(property_map1, vertex) !=
+          get(property_map2, vertex)) {
+
+        return (true);
+      }
+    }
+
+    return (false);
+  }
+
 } /* namespace boost */
 
 #endif /* BOOST_GRAPH_UTILITY_HPP*/

Added: trunk/boost/graph/mcgregor_common_subgraphs.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/mcgregor_common_subgraphs.hpp	2009-06-18 18:21:12 EDT (Thu, 18 Jun 2009)
@@ -0,0 +1,1098 @@
+//=======================================================================
+// 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 <map>
+#include <stack>
+#include <set>
+#include <vector>
+
+#include <boost/bind.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
+  // vertex1 in property_map1 and vertex2 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 VertexFirst,
+              typename VertexSecond>
+    bool operator()(const VertexFirst vertex1, const VertexSecond vertex2) {
+      return (get(m_property_map1, vertex1) == get(m_property_map2, vertex2));
+    }
+  
+  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& item1, const ItemSecond& item2) {
+      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)
+    {
+      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 (!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,
+     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;
+  
+      tie(vertex1_iter, vertex1_end) = vertices(graph1);
+      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)) {
+
+            // 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,
+               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 VertexEquivalencePredicate,
+              typename EdgeEquivalencePredicate,
+              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,
+     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,
+         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,
+   SubGraphCallback user_callback)
+  {
+      
+    detail::mcgregor_common_subgraphs_internal_init
+      (graph1, graph2,
+       vindex_map1, vindex_map2,
+       edges_equivalent, vertices_equivalent,
+       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,
+   SubGraphCallback user_callback)
+  {
+      
+    detail::mcgregor_common_subgraphs_internal_init
+      (graph1, graph2,
+       get(vertex_index, graph1), get(vertex_index, graph2),
+       always_equivalent(), always_equivalent(),
+       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,
+   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()),
+       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 mcgregor_common_subgraph_traits<GraphFirst, GraphSecond,
+        VertexIndexMapFirst, VertexIndexMapSecond> SubGraphTraits;
+        
+      typedef typename SubGraphTraits::correspondence_map_first_to_second_type
+        CorrespondenceMapFirstToSecond;
+
+      typedef typename SubGraphTraits::correspondence_map_second_to_first_type
+        CorrespondenceMapSecondToFirst;
+
+      typedef std::pair<std::size_t, std::pair<CorrespondenceMapFirstToSecond,
+                                               CorrespondenceMapSecondToFirst> > 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_user_callback(user_callback) { }
+      
+      bool operator()(CorrespondenceMapFirstToSecond& correspondence_map_1_to_2,
+                      CorrespondenceMapSecondToFirst& correspondence_map_2_to_1,
+                      std::size_t 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;
+          }
+          
+          CorrespondenceMapFirstToSecond correspondence_map_1_to_2_cached =
+            subgraph_cached.second.first;
+          
+          if (!are_property_maps_different(correspondence_map_1_to_2,
+                                           correspondence_map_1_to_2_cached,
+                                           m_graph1)) {
+                                    
+            // New subgraph is a duplicate
+            return (true);
+          }
+        }
+  
+        // Subgraph is unique, so make a cached copy
+        SubGraph new_subgraph = make_pair(subgraph_size,
+          std::make_pair
+          (CorrespondenceMapFirstToSecond(num_vertices(m_graph1), m_vindex_map1),
+           CorrespondenceMapSecondToFirst(num_vertices(m_graph2), m_vindex_map2)));
+          
+        copy_vertex_property(correspondence_map_1_to_2,
+                             new_subgraph.second.first, m_graph1);
+
+        copy_vertex_property(correspondence_map_2_to_1,
+                             new_subgraph.second.second, m_graph1);
+        
+        m_subgraphs.push_back(new_subgraph);
+        
+        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;
+      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,
+   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,
+       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,
+   SubGraphCallback user_callback)
+  {
+    mcgregor_common_subgraphs_unique
+      (graph1, graph2,
+       get(vertex_index, graph1), get(vertex_index, graph2),
+       always_equivalent(), always_equivalent(),
+       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,
+   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()),
+       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 mcgregor_common_subgraph_traits<GraphFirst, GraphSecond,
+        VertexIndexMapFirst, VertexIndexMapSecond> SubGraphTraits;
+        
+      typedef typename SubGraphTraits::correspondence_map_first_to_second_type
+      CorrespondenceMapFirstToSecond;
+
+      typedef typename SubGraphTraits::correspondence_map_second_to_first_type
+      CorrespondenceMapSecondToFirst;
+
+      typedef std::pair<std::size_t,
+                        std::pair<CorrespondenceMapFirstToSecond,
+                                  CorrespondenceMapSecondToFirst> > 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_user_callback(user_callback),
+        m_largest_size_so_far(0) { }
+      
+      bool operator()(CorrespondenceMapFirstToSecond& correspondence_map_1_to_2,
+                      CorrespondenceMapSecondToFirst& correspondence_map_2_to_1,
+                      std::size_t 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
+          SubGraph new_subgraph = make_pair(subgraph_size,
+            std::make_pair(CorrespondenceMapFirstToSecond(num_vertices(m_graph1), m_vindex_map1),
+                           CorrespondenceMapSecondToFirst(num_vertices(m_graph2), m_vindex_map2)));
+            
+          copy_vertex_property(correspondence_map_1_to_2,
+                               new_subgraph.second.first, m_graph1);
+  
+          copy_vertex_property(correspondence_map_2_to_1,
+                               new_subgraph.second.second, m_graph2);
+          
+          m_subgraphs.push_back(new_subgraph);
+        }
+
+        return (true);
+      }
+
+      void output_cached_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;
+      SubGraphList m_subgraphs;
+      SubGraphCallback m_user_callback;
+      typename graph_traits<GraphFirst>::vertices_size_type m_largest_size_so_far;
+    };
+    
+  } // 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_maximum_common_subgraphs
+  (const GraphFirst& graph1,
+   const GraphSecond& graph2,
+   const VertexIndexMapFirst vindex_map1,
+   const VertexIndexMapSecond vindex_map2,
+   EdgeEquivalencePredicate edges_equivalent,
+   VertexEquivalencePredicate vertices_equivalent,
+   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,
+       max_interceptor);
+
+    // Only output the largest subgraphs
+    max_interceptor.output_cached_subgraphs();
+  }
+
+  // Variant of mcgregor_maximum_common_subgraphs with all default parameters
+  template <typename GraphFirst,
+            typename GraphSecond,
+            typename SubGraphCallback>
+  void mcgregor_maximum_common_subgraphs
+  (const GraphFirst& graph1,
+   const GraphSecond& graph2,
+   SubGraphCallback user_callback)
+  {
+    mcgregor_maximum_common_subgraphs
+      (graph1, graph2,
+       get(vertex_index, graph1), get(vertex_index, graph2),
+       always_equivalent(), always_equivalent(),
+       user_callback);
+  }
+
+  // Named parameter variant of mcgregor_maximum_common_subgraphs
+  template <typename GraphFirst,
+            typename GraphSecond,
+            typename SubGraphCallback,
+            typename Param,
+            typename Tag,
+            typename Rest>
+  void mcgregor_maximum_common_subgraphs
+  (const GraphFirst& graph1,
+   const GraphSecond& graph2,
+   SubGraphCallback user_callback,
+   const bgl_named_params<Param, Tag, Rest>& params)
+  {
+    mcgregor_maximum_common_subgraphs
+      (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()),
+       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 mcgregor_common_subgraph_traits<GraphFirst, GraphSecond,
+        VertexIndexMapFirst, VertexIndexMapSecond> SubGraphTraits;
+        
+      typedef typename SubGraphTraits::correspondence_map_first_to_second_type
+      CorrespondenceMapFirstToSecond;
+
+      typedef typename SubGraphTraits::correspondence_map_second_to_first_type
+      CorrespondenceMapSecondToFirst;
+
+      typedef std::pair<std::size_t,
+                        std::pair<CorrespondenceMapFirstToSecond,
+                                  CorrespondenceMapSecondToFirst> > 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_user_callback(user_callback),
+        m_largest_size_so_far(0) { }
+      
+      bool operator()(CorrespondenceMapFirstToSecond& correspondence_map_1_to_2,
+                      CorrespondenceMapSecondToFirst& correspondence_map_2_to_1,
+                      std::size_t 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;
+  
+            CorrespondenceMapFirstToSecond correspondence_map_1_to_2_cached =
+              subgraph_cached.second.first;
+            
+            if (!are_property_maps_different(correspondence_map_1_to_2,
+                                             correspondence_map_1_to_2_cached,
+                                             m_graph1)) {
+                                      
+              // New subgraph is a duplicate
+              return (true);
+            }
+          }
+    
+          // Subgraph is unique, so make a cached copy
+          SubGraph new_subgraph = std::make_pair(subgraph_size,
+            std::make_pair
+              (CorrespondenceMapFirstToSecond(num_vertices(m_graph1), m_vindex_map1),
+               CorrespondenceMapSecondToFirst(num_vertices(m_graph2), m_vindex_map2)));
+            
+          copy_vertex_property(correspondence_map_1_to_2,
+                               new_subgraph.second.first, m_graph1);
+  
+          copy_vertex_property(correspondence_map_2_to_1,
+                               new_subgraph.second.second, m_graph2);
+          
+          m_subgraphs.push_back(new_subgraph);
+        }
+    
+        return (true);
+      }
+
+      void output_cached_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;
+      SubGraphList m_subgraphs;
+      SubGraphCallback m_user_callback;
+      typename graph_traits<GraphFirst>::vertices_size_type m_largest_size_so_far;
+    };
+    
+  } // 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_maximum_common_subgraphs_unique
+  (const GraphFirst& graph1,
+   const GraphSecond& graph2,
+   const VertexIndexMapFirst vindex_map1,
+   const VertexIndexMapSecond vindex_map2,
+   EdgeEquivalencePredicate edges_equivalent,
+   VertexEquivalencePredicate vertices_equivalent,
+   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,
+       unique_max_interceptor);
+
+    // Only output the largest, unique subgraphs
+    unique_max_interceptor.output_cached_subgraphs();
+  }
+
+  // Variant of mcgregor_maximum_common_subgraphs_unique with all default parameters
+  template <typename GraphFirst,
+            typename GraphSecond,
+            typename SubGraphCallback>
+  void mcgregor_maximum_common_subgraphs_unique
+  (const GraphFirst& graph1,
+   const GraphSecond& graph2,
+   SubGraphCallback user_callback)
+  {
+
+    mcgregor_maximum_common_subgraphs_unique
+      (graph1, graph2,
+       get(vertex_index, graph1), get(vertex_index, graph2),
+       always_equivalent(), always_equivalent(),
+       user_callback);
+  }
+
+  // Named parameter variant of mcgregor_maximum_common_subgraphs_unique
+  template <typename GraphFirst,
+            typename GraphSecond,
+            typename SubGraphCallback,
+            typename Param,
+            typename Tag,
+            typename Rest>
+  void mcgregor_maximum_common_subgraphs_unique
+  (const GraphFirst& graph1,
+   const GraphSecond& graph2,
+   SubGraphCallback user_callback,
+   const bgl_named_params<Param, Tag, Rest>& params)
+  {
+    mcgregor_maximum_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()),
+       user_callback);
+  }
+
+  // ==========================================================================
+
+  // Fills two membership maps (vertex -> bool) using the information present
+  // in correspondence_map_1_to_2 and correspondence_map_2_to_1.  Every vertex in a
+  // membership map will have a true value only if it is not associated with
+  // a null vertex in its respective correspondence map.
+  template <typename GraphFirst,
+            typename GraphSecond,
+            typename CorrespondenceMapFirstToSecond,
+            typename CorrespondenceMapSecondToFirst,
+            typename MembershipMapFirst,
+            typename MembershipMapSecond>
+  void fill_membership_maps
+  (const GraphFirst& graph1,
+   const GraphSecond& graph2,
+   const CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
+   const CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
+   MembershipMapFirst membership_map1,
+   MembershipMapSecond membership_map2) {
+
+    typedef typename graph_traits<GraphSecond>::vertex_descriptor
+      VertexSecond;
+
+    BGL_FORALL_VERTICES_T(vertex1, graph1, GraphFirst) {
+      put(membership_map1, vertex1,
+          get(correspondence_map_1_to_2, vertex1) != graph_traits<GraphSecond>::null_vertex());
+    }
+
+    BGL_FORALL_VERTICES_T(vertex2, graph2, GraphSecond) {
+      put(membership_map2, vertex2,
+          get(correspondence_map_2_to_1, vertex2) != graph_traits<GraphFirst>::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