[Boost-commit] svn:boost r54540 - in branches/release: boost/graph boost/graph/detail boost/property_map libs/graph/doc libs/graph/example libs/graph/test

Subject: [Boost-commit] svn:boost r54540 - in branches/release: boost/graph boost/graph/detail boost/property_map libs/graph/doc libs/graph/example libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-06-30 13:08:51

Author: jewillco
Date: 2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
New Revision: 54540
URL: http://svn.boost.org/trac/boost/changeset/54540

Log:
Merged patches mentioned in comments 34-53 from ticket 3134 into release branch; refs #3134
Added:
   branches/release/boost/graph/mcgregor_common_subgraphs.hpp
      - copied, changed from r54069, /trunk/boost/graph/mcgregor_common_subgraphs.hpp
   branches/release/libs/graph/doc/mcgregor_common_subgraphs.html
      - copied unchanged from r54344, /trunk/libs/graph/doc/mcgregor_common_subgraphs.html
   branches/release/libs/graph/example/mcgregor_subgraphs_example.cpp
      - copied unchanged from r54344, /trunk/libs/graph/example/mcgregor_subgraphs_example.cpp
   branches/release/libs/graph/test/mcgregor_subgraphs_test.cpp
      - copied, changed from r54216, /trunk/libs/graph/test/mcgregor_subgraphs_test.cpp
Text files modified: 
   branches/release/boost/graph/compressed_sparse_row_graph.hpp      |   514 ++++++++++++++++++++++++--------------- 
   branches/release/boost/graph/detail/indexed_properties.hpp        |    32 ++                                      
   branches/release/boost/graph/filtered_graph.hpp                   |    17 +                                       
   branches/release/boost/graph/graph_utility.hpp                    |    37 ++                                      
   branches/release/boost/graph/mcgregor_common_subgraphs.hpp        |   434 ++++++++++++++++++---------------       
   branches/release/boost/property_map/shared_array_property_map.hpp |     2                                         
   branches/release/libs/graph/doc/compressed_sparse_row.html        |    51 +++                                     
   branches/release/libs/graph/doc/table_of_contents.html            |     1                                         
   branches/release/libs/graph/example/Jamfile.v2                    |     1                                         
   branches/release/libs/graph/test/CMakeLists.txt                   |     1                                         
   branches/release/libs/graph/test/Jamfile.v2                       |     1                                         
   branches/release/libs/graph/test/mcgregor_subgraphs_test.cpp      |   148 ++++++++++                              
   12 files changed, 836 insertions(+), 403 deletions(-)

Modified: branches/release/boost/graph/compressed_sparse_row_graph.hpp
==============================================================================
--- branches/release/boost/graph/compressed_sparse_row_graph.hpp	(original)
+++ branches/release/boost/graph/compressed_sparse_row_graph.hpp	2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
@@ -27,6 +27,7 @@
 #include <boost/graph/filtered_graph.hpp> // For keep_all
 #include <boost/graph/detail/indexed_properties.hpp>
 #include <boost/iterator/counting_iterator.hpp>
+#include <boost/iterator/reverse_iterator.hpp>
 #include <boost/property_map/property_map.hpp>
 #include <boost/integer.hpp>
 #include <boost/iterator/iterator_facade.hpp>
@@ -64,6 +65,11 @@
 enum edges_are_sorted_t {edges_are_sorted};
 
 #ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+// A type (edges_are_sorted_global_t) and a value (edges_are_sorted_global)
+// used to indicate that the edge list passed into the CSR graph is already
+// sorted by source vertex.
+enum edges_are_sorted_global_t {edges_are_sorted_global};
+
 // A type (edges_are_unsorted_t) and a value (edges_are_unsorted) used to
 // indicate that the edge list passed into the CSR graph is not sorted by
 // source vertex.  This version caches the edge information in memory, and thus
@@ -76,13 +82,13 @@
 // memory but requires multi-pass capability on the iterators.
 enum edges_are_unsorted_multi_pass_t {edges_are_unsorted_multi_pass};
 
-// A type (edges_are_unsorted_multi_pass_filtered_t) and a value
-// (edges_are_unsorted_multi_pass_filtered) used to indicate that the edge list
+// A type (edges_are_unsorted_multi_pass_global_t) and a value
+// (edges_are_unsorted_multi_pass_global) used to indicate that the edge list
 // passed into the CSR graph is not sorted by source vertex.  This version uses
 // less memory but requires multi-pass capability on the iterators.  The
-// filtering is done here because it is often faster and it greatly simplifies
-// handling of edge properties.
-enum edges_are_unsorted_multi_pass_filtered_t {edges_are_unsorted_multi_pass_filtered};
+// global mapping and filtering is done here because it is often faster and it
+// greatly simplifies handling of edge properties.
+enum edges_are_unsorted_multi_pass_global_t {edges_are_unsorted_multi_pass_global};
 
 // A type (construct_inplace_from_sources_and_targets_t) and a value
 // (construct_inplace_from_sources_and_targets) used to indicate that mutable
@@ -102,14 +108,14 @@
 // (sequential and distributed).
 enum construct_inplace_from_sources_and_targets_global_t {construct_inplace_from_sources_and_targets_global};
 
-// A type (edges_are_unsorted_for_distributed_graph_t) and a value
-// (edges_are_unsorted_for_distributed_graph) used to indicate that the edge
-// list passed into the CSR graph is not sorted by source vertex.  The data is
-// also stored using global vertex indices, and must be filtered to choose only
-// local vertices.  This constructor caches the edge information in memory, and
-// thus requires only a single pass over the input data.  This constructor is
-// intended for internal use by the distributed CSR constructors.
-enum edges_are_unsorted_for_distributed_graph_t {edges_are_unsorted_for_distributed_graph};
+// A type (edges_are_unsorted_global_t) and a value (edges_are_unsorted_global)
+// used to indicate that the edge list passed into the CSR graph is not sorted
+// by source vertex.  The data is also stored using global vertex indices, and
+// must be filtered to choose only local vertices.  This constructor caches the
+// edge information in memory, and thus requires only a single pass over the
+// input data.  This constructor is intended for internal use by the
+// distributed CSR constructors.
+enum edges_are_unsorted_global_t {edges_are_unsorted_global};
 
 #endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
 
@@ -128,7 +134,6 @@
 template<typename Vertex, typename EdgeIndex>
 class csr_edge_descriptor;
 
-#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
 namespace detail {
   template<typename InputIterator>
   size_t
@@ -157,8 +162,21 @@
       category;
     return reserve_count_for_single_pass_helper(first, last, category());
   }
-}
+
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+  template <typename T>
+  struct default_construct_iterator: public boost::iterator_facade<default_construct_iterator<T>, T, boost::random_access_traversal_tag, const T&> {
+    typedef boost::iterator_facade<default_construct_iterator<T>, T, std::random_access_iterator_tag, const T&> base_type;
+    T saved_value;
+    const T& dereference() const {return saved_value;}
+    bool equal(default_construct_iterator i) const {return true;}
+    void increment() {}
+    void decrement() {}
+    void advance(typename base_type::difference_type) {}
+    typename base_type::difference_type distance_to(default_construct_iterator) const {return 0;}
+  };
 #endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+}
 
 /** Compressed sparse row graph.
  *
@@ -166,8 +184,8 @@
  * specialize numeric_limits.
  */
 template<typename Directed = directedS, 
-         typename VertexProperty = void,
-         typename EdgeProperty = void,
+         typename VertexProperty = no_property,
+         typename EdgeProperty = no_property,
          typename GraphProperty = no_property,
          typename Vertex = std::size_t,
          typename EdgeIndex = Vertex>
@@ -179,6 +197,7 @@
                                                                 EdgeIndex> >
 
 {
+ public:
   typedef detail::indexed_vertex_properties<compressed_sparse_row_graph,
                                             VertexProperty, Vertex>
     inherited_vertex_properties;
@@ -280,25 +299,26 @@
 
 #ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
   //  Rebuild graph from number of vertices and multi-pass unsorted list of
-  //  edges (filtered using edge_pred)
-  template <typename MultiPassInputIterator, typename EdgePred>
+  //  edges (filtered using edge_pred and mapped using global_to_local)
+  template <typename MultiPassInputIterator, typename GlobalToLocal, typename EdgePred>
   void
   assign_unsorted_multi_pass_edges(MultiPassInputIterator edge_begin,
                                    MultiPassInputIterator edge_end,
-                                   vertices_size_type numverts,
+                                   vertices_size_type numlocalverts,
+                                   const GlobalToLocal& global_to_local,
                                    const EdgePred& edge_pred) {
     m_rowstart.clear();
-    m_rowstart.resize(numverts + 1, 0);
+    m_rowstart.resize(numlocalverts + 1, 0);
     // Put the degree of each vertex v into m_rowstart[v + 1]
     for (MultiPassInputIterator i = edge_begin; i != edge_end; ++i)
       if (edge_pred(*i))
-        ++m_rowstart[i->first + 1];
+        ++m_rowstart[get(global_to_local, i->first) + 1];
 
     // Compute the partial sum of the degrees to get the actual values of
     // m_rowstart
     EdgeIndex start_of_this_row = 0;
     m_rowstart[0] = start_of_this_row;
-    for (vertices_size_type i = 1; i <= numverts; ++i) {
+    for (vertices_size_type i = 1; i <= numlocalverts; ++i) {
       start_of_this_row += m_rowstart[i];
       m_rowstart[i] = start_of_this_row;
     }
@@ -308,33 +328,35 @@
     // into m_column.  The index current_insert_positions[v] contains the next
     // location to insert out edges for vertex v.
     std::vector<EdgeIndex>
-      current_insert_positions(m_rowstart.begin(), m_rowstart.begin() + numverts);
+      current_insert_positions(m_rowstart.begin(), m_rowstart.begin() + numlocalverts);
     for (; edge_begin != edge_end; ++edge_begin)
       if (edge_pred(*edge_begin))
-        m_column[current_insert_positions[edge_begin->first]++] = edge_begin->second;
+        m_column[current_insert_positions[get(global_to_local, edge_begin->first)]++] = edge_begin->second;
   }
 
   //  Rebuild graph from number of vertices and multi-pass unsorted list of
-  //  edges and their properties (filtered using edge_pred)
-  template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename EdgePred>
+  //  edges and their properties (filtered using edge_pred and mapped using
+  //  global_to_local)
+  template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename EdgePred>
   void
   assign_unsorted_multi_pass_edges(MultiPassInputIterator edge_begin,
                                    MultiPassInputIterator edge_end,
                                    EdgePropertyIterator ep_iter,
-                                   vertices_size_type numverts,
+                                   vertices_size_type numlocalverts,
+                                   const GlobalToLocal& global_to_local,
                                    const EdgePred& edge_pred) {
     m_rowstart.clear();
-    m_rowstart.resize(numverts + 1, 0);
+    m_rowstart.resize(numlocalverts + 1, 0);
     // Put the degree of each vertex v into m_rowstart[v + 1]
     for (MultiPassInputIterator i = edge_begin; i != edge_end; ++i)
       if (edge_pred(*i))
-        ++m_rowstart[i->first + 1];
+        ++m_rowstart[get(global_to_local, i->first) + 1];
 
     // Compute the partial sum of the degrees to get the actual values of
     // m_rowstart
     EdgeIndex start_of_this_row = 0;
     m_rowstart[0] = start_of_this_row;
-    for (vertices_size_type i = 1; i <= numverts; ++i) {
+    for (vertices_size_type i = 1; i <= numlocalverts; ++i) {
       start_of_this_row += m_rowstart[i];
       m_rowstart[i] = start_of_this_row;
     }
@@ -345,10 +367,10 @@
     // into m_column.  The index current_insert_positions[v] contains the next
     // location to insert out edges for vertex v.
     std::vector<EdgeIndex>
-      current_insert_positions(m_rowstart.begin(), m_rowstart.begin() + numverts);
+      current_insert_positions(m_rowstart.begin(), m_rowstart.begin() + numlocalverts);
     for (; edge_begin != edge_end; ++edge_begin, ++ep_iter) {
       if (edge_pred(*edge_begin)) {
-        vertices_size_type source = edge_begin->first;
+        vertices_size_type source = get(global_to_local, edge_begin->first);
         EdgeIndex insert_pos = current_insert_positions[source];
         ++current_insert_positions[source];
         m_column[insert_pos] = edge_begin->second;
@@ -367,7 +389,7 @@
     : inherited_vertex_properties(numverts), m_rowstart(),
       m_column(0), m_property(prop)
   {
-    assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, keep_all());
+    assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, identity_property_map(), keep_all());
 
     // Default-construct properties for edges
     inherited_edge_properties::resize(m_column.size());
@@ -384,42 +406,113 @@
     : inherited_vertex_properties(numverts), m_rowstart(),
       m_column(0), m_property(prop)
   {
-    assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numverts, keep_all());
+    assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numverts, identity_property_map(), keep_all());
   }
 
-  //  From number of vertices and unsorted list of edges, with filter
-  template <typename MultiPassInputIterator, typename EdgePred>
-  compressed_sparse_row_graph(edges_are_unsorted_multi_pass_filtered_t,
+  //  From number of vertices and unsorted list of edges, with filter and
+  //  global-to-local map
+  template <typename MultiPassInputIterator, typename GlobalToLocal, typename EdgePred>
+  compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
                               MultiPassInputIterator edge_begin,
                               MultiPassInputIterator edge_end,
-                              vertices_size_type numverts,
+                              vertices_size_type numlocalverts,
+                              const GlobalToLocal& global_to_local,
                               const EdgePred& edge_pred,
                               const GraphProperty& prop = GraphProperty())
-    : inherited_vertex_properties(numverts), m_rowstart(),
+    : inherited_vertex_properties(numlocalverts), m_rowstart(),
       m_column(0), m_property(prop)
   {
-    assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, edge_pred);
+    assign_unsorted_multi_pass_edges(edge_begin, edge_end, numlocalverts, global_to_local, edge_pred);
 
     // Default-construct properties for edges
     inherited_edge_properties::resize(m_column.size());
   }
 
-  //  From number of vertices and unsorted list of edges, plus edge properties, with filter
-  template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename EdgePred>
-  compressed_sparse_row_graph(edges_are_unsorted_multi_pass_filtered_t,
+  //  From number of vertices and unsorted list of edges, plus edge properties,
+  //  with filter and global-to-local map
+  template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename EdgePred>
+  compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
                               MultiPassInputIterator edge_begin,
                               MultiPassInputIterator edge_end,
                               EdgePropertyIterator ep_iter,
-                              vertices_size_type numverts,
+                              vertices_size_type numlocalverts,
+                              const GlobalToLocal& global_to_local,
                               const EdgePred& edge_pred,
                               const GraphProperty& prop = GraphProperty())
-    : inherited_vertex_properties(numverts), m_rowstart(),
+    : inherited_vertex_properties(numlocalverts), m_rowstart(),
       m_column(0), m_property(prop)
   {
-    assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numverts, edge_pred);
+    assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numlocalverts, global_to_local, edge_pred);
   }
 #endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
 
+  //  Assign from number of vertices and sorted list of edges
+  template<typename InputIterator, typename GlobalToLocal, typename EdgePred>
+  void assign_from_sorted_edges(
+         InputIterator edge_begin, InputIterator edge_end,
+         const GlobalToLocal& global_to_local,
+         const EdgePred& edge_pred,
+         vertices_size_type numlocalverts,
+         edges_size_type numedges_or_zero) {
+    m_column.clear();
+    m_column.reserve(numedges_or_zero);
+    inherited_vertex_properties::resize(numlocalverts);
+    m_rowstart.resize(numlocalverts + 1);
+    EdgeIndex current_edge = 0;
+    Vertex current_vertex_plus_one = 1;
+    m_rowstart[0] = 0;
+    for (InputIterator ei = edge_begin; ei != edge_end; ++ei) {
+      if (!edge_pred(*ei)) continue;
+      Vertex src = get(global_to_local, ei->first);
+      Vertex tgt = ei->second;
+      for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
+        m_rowstart[current_vertex_plus_one] = current_edge;
+      m_column.push_back(tgt);
+      ++current_edge;
+    }
+
+    // The remaining vertices have no edges
+    for (; current_vertex_plus_one != numlocalverts + 1; ++current_vertex_plus_one)
+      m_rowstart[current_vertex_plus_one] = current_edge;
+
+    // Default-construct properties for edges
+    inherited_edge_properties::resize(m_column.size());
+  }
+
+  //  Assign from number of vertices and sorted list of edges
+  template<typename InputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename EdgePred>
+  void assign_from_sorted_edges(
+         InputIterator edge_begin, InputIterator edge_end,
+         EdgePropertyIterator ep_iter,
+         const GlobalToLocal& global_to_local,
+         const EdgePred& edge_pred,
+         vertices_size_type numlocalverts,
+         edges_size_type numedges_or_zero) {
+    m_column.clear();
+    m_column.reserve(numedges_or_zero);
+    inherited_edge_properties::clear();
+    inherited_edge_properties::reserve(numedges_or_zero);
+    inherited_vertex_properties::resize(numlocalverts);
+    m_rowstart.resize(numlocalverts + 1);
+    EdgeIndex current_edge = 0;
+    Vertex current_vertex_plus_one = 1;
+    m_rowstart[0] = 0;
+    for (InputIterator ei = edge_begin; ei != edge_end; ++ei, ++ep_iter) {
+      if (!edge_pred(*ei)) continue;
+      Vertex src = get(global_to_local, ei->first);
+      Vertex tgt = ei->second;
+      for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
+        m_rowstart[current_vertex_plus_one] = current_edge;
+      m_column.push_back(tgt);
+      inherited_edge_properties::push_back(*ep_iter);
+      ++current_edge;
+    }
+
+    // The remaining vertices have no edges
+    for (; current_vertex_plus_one != numlocalverts + 1; ++current_vertex_plus_one)
+      m_rowstart[current_vertex_plus_one] = current_edge;
+  }
+
 #ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
 
   //  From number of vertices and sorted list of edges (deprecated
@@ -429,8 +522,7 @@
                               vertices_size_type numverts,
                               edges_size_type numedges = 0,
                               const GraphProperty& prop = GraphProperty())
-    : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
-      m_column(0), m_property(prop), m_last_source(numverts)
+    : m_property(prop), m_last_source(numverts)
   {
     // Reserving storage in advance can save us lots of time and
     // memory, but it can only be done if we have forward iterators or
@@ -438,29 +530,9 @@
     if (numedges == 0) {
       typedef typename std::iterator_traits<InputIterator>::iterator_category
         category;
-      maybe_reserve_edge_list_storage(edge_begin, edge_end, category());
-    } else {
-      m_column.reserve(numedges);
-    }
-
-    EdgeIndex current_edge = 0;
-    Vertex current_vertex_plus_one = 1;
-    m_rowstart[0] = 0;
-    for (InputIterator ei = edge_begin; ei != edge_end; ++ei) {
-      Vertex src = ei->first;
-      Vertex tgt = ei->second;
-      for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
-        m_rowstart[current_vertex_plus_one] = current_edge;
-      m_column.push_back(tgt);
-      ++current_edge;
+      numedges = detail::reserve_count_for_single_pass(edge_begin, edge_end);
     }
-
-    // The remaining vertices have no edges
-    for (; current_vertex_plus_one != numverts + 1; ++current_vertex_plus_one)
-      m_rowstart[current_vertex_plus_one] = current_edge;
-
-    // Default-construct properties for edges
-    inherited_edge_properties::resize(m_column.size());
+    assign_from_sorted_edges(edge_begin, edge_end, identity_property_map(), keep_all(), numverts, numedges);
   }
 
   //  From number of vertices and sorted list of edges (deprecated
@@ -471,8 +543,7 @@
                               vertices_size_type numverts,
                               edges_size_type numedges = 0,
                               const GraphProperty& prop = GraphProperty())
-    : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
-      m_column(0), m_property(prop), m_last_source(numverts)
+    : m_property(prop), m_last_source(numverts)
   {
     // Reserving storage in advance can save us lots of time and
     // memory, but it can only be done if we have forward iterators or
@@ -480,27 +551,9 @@
     if (numedges == 0) {
       typedef typename std::iterator_traits<InputIterator>::iterator_category
         category;
-      maybe_reserve_edge_list_storage(edge_begin, edge_end, category());
-    } else {
-      m_column.reserve(numedges);
-    }
-
-    EdgeIndex current_edge = 0;
-    Vertex current_vertex_plus_one = 1;
-    m_rowstart[0] = 0;
-    for (InputIterator ei = edge_begin; ei != edge_end; ++ei, ++ep_iter) {
-      Vertex src = ei->first;
-      Vertex tgt = ei->second;
-      for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
-        m_rowstart[current_vertex_plus_one] = current_edge;
-      m_column.push_back(tgt);
-      inherited_edge_properties::push_back(*ep_iter);
-      ++current_edge;
+      numedges = detail::reserve_count_for_single_pass(edge_begin, edge_end);
     }
-
-    // The remaining vertices have no edges
-    for (; current_vertex_plus_one != numverts + 1; ++current_vertex_plus_one)
-      m_rowstart[current_vertex_plus_one] = current_edge;
+    assign_from_sorted_edges(edge_begin, edge_end, ep_iter, identity_property_map(), keep_all(), numverts, numedges);
   }
 
 #endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
@@ -512,8 +565,7 @@
                               vertices_size_type numverts,
                               edges_size_type numedges = 0,
                               const GraphProperty& prop = GraphProperty())
-    : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
-      m_column(0), m_property(prop)
+    : m_property(prop)
 #ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
       , m_last_source(numverts)
 #endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
@@ -524,29 +576,9 @@
     if (numedges == 0) {
       typedef typename std::iterator_traits<InputIterator>::iterator_category
         category;
-      maybe_reserve_edge_list_storage(edge_begin, edge_end, category());
-    } else {
-      m_column.reserve(numedges);
-    }
-
-    EdgeIndex current_edge = 0;
-    Vertex current_vertex_plus_one = 1;
-    m_rowstart[0] = 0;
-    for (InputIterator ei = edge_begin; ei != edge_end; ++ei) {
-      Vertex src = ei->first;
-      Vertex tgt = ei->second;
-      for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
-        m_rowstart[current_vertex_plus_one] = current_edge;
-      m_column.push_back(tgt);
-      ++current_edge;
+      numedges = detail::reserve_count_for_single_pass(edge_begin, edge_end);
     }
-
-    // The remaining vertices have no edges
-    for (; current_vertex_plus_one != numverts + 1; ++current_vertex_plus_one)
-      m_rowstart[current_vertex_plus_one] = current_edge;
-
-    // Default-construct properties for edges
-    inherited_edge_properties::resize(m_column.size());
+    assign_from_sorted_edges(edge_begin, edge_end, identity_property_map(), keep_all(), numverts, numedges);
   }
 
   //  From number of vertices and sorted list of edges (new interface)
@@ -557,8 +589,7 @@
                               vertices_size_type numverts,
                               edges_size_type numedges = 0,
                               const GraphProperty& prop = GraphProperty())
-    : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
-      m_column(0), m_property(prop)
+    : m_property(prop)
 #ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
       , m_last_source(numverts)
 #endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
@@ -569,30 +600,45 @@
     if (numedges == 0) {
       typedef typename std::iterator_traits<InputIterator>::iterator_category
         category;
-      maybe_reserve_edge_list_storage(edge_begin, edge_end, category());
-    } else {
-      m_column.reserve(numedges);
+      numedges = detail::reserve_count_for_single_pass(edge_begin, edge_end);
     }
+    assign_from_sorted_edges(edge_begin, edge_end, ep_iter, identity_property_map(), keep_all(), numverts, numedges);
+  }
 
-    EdgeIndex current_edge = 0;
-    Vertex current_vertex_plus_one = 1;
-    m_rowstart[0] = 0;
-    for (InputIterator ei = edge_begin; ei != edge_end; ++ei, ++ep_iter) {
-      Vertex src = ei->first;
-      Vertex tgt = ei->second;
-      for (; current_vertex_plus_one != src + 1; ++current_vertex_plus_one)
-        m_rowstart[current_vertex_plus_one] = current_edge;
-      m_column.push_back(tgt);
-      inherited_edge_properties::push_back(*ep_iter);
-      ++current_edge;
-    }
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+  //  From number of vertices and sorted list of edges, filtered and global (new interface)
+  template<typename InputIterator, typename GlobalToLocal, typename EdgePred>
+  compressed_sparse_row_graph(edges_are_sorted_global_t,
+                              InputIterator edge_begin, InputIterator edge_end,
+                              const GlobalToLocal& global_to_local,
+                              const EdgePred& edge_pred,
+                              vertices_size_type numverts,
+                              const GraphProperty& prop = GraphProperty())
+    : m_property(prop)
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+      , m_last_source(numverts)
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+  {
+    assign_from_sorted_edges(edge_begin, edge_end, global_to_local, edge_pred, numverts, 0);
+  }
 
-    // The remaining vertices have no edges
-    for (; current_vertex_plus_one != numverts + 1; ++current_vertex_plus_one)
-      m_rowstart[current_vertex_plus_one] = current_edge;
+  //  From number of vertices and sorted list of edges (new interface)
+  template<typename InputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename EdgePred>
+  compressed_sparse_row_graph(edges_are_sorted_global_t,
+                              InputIterator edge_begin, InputIterator edge_end,
+                              EdgePropertyIterator ep_iter,
+                              const GlobalToLocal& global_to_local,
+                              const EdgePred& edge_pred,
+                              vertices_size_type numverts,
+                              const GraphProperty& prop = GraphProperty())
+    : m_property(prop)
+#ifdef BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+      , m_last_source(numverts)
+#endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
+  {
+    assign_from_sorted_edges(edge_begin, edge_end, ep_iter, global_to_local, edge_pred, numverts, 0);
   }
 
-#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
   //  From number of vertices and mutable vectors of sources and targets;
   //  vectors are returned with unspecified contents but are guaranteed not to
   //  share storage with the constructed graph.
@@ -631,7 +677,7 @@
   compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,
                               std::vector<vertex_descriptor>& sources,
                               std::vector<vertex_descriptor>& targets,
-                              std::vector<typename inherited_edge_properties::edge_property_type>& edge_props,
+                              std::vector<typename inherited_edge_properties::edge_bundled>& edge_props,
                               vertices_size_type numverts,
                               const GraphProperty& prop = GraphProperty())
     : inherited_vertex_properties(numverts), m_rowstart(),
@@ -649,7 +695,7 @@
   compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_global_t,
                               std::vector<vertex_descriptor>& sources,
                               std::vector<vertex_descriptor>& targets,
-                              std::vector<typename inherited_edge_properties::edge_property_type>& edge_props,
+                              std::vector<typename inherited_edge_properties::edge_bundled>& edge_props,
                               vertices_size_type numlocalverts,
                               GlobalToLocal global_to_local,
                               const GraphProperty& prop = GraphProperty())
@@ -694,7 +740,7 @@
       m_column(), m_property(prop)
   {
     std::vector<vertex_descriptor> sources, targets;
-    std::vector<typename inherited_edge_properties::edge_property_type> edge_props;
+    std::vector<typename inherited_edge_properties::edge_bundled> edge_props;
     size_t reserve_size
       = detail::reserve_count_for_single_pass(edge_begin, edge_end);
     sources.reserve(reserve_size);
@@ -712,7 +758,7 @@
   //  cached in coordinate form before creating the actual graph.  Edges are
   //  filtered and transformed for use in a distributed graph.
   template<typename InputIterator, typename GlobalToLocal, typename EdgePred>
-  compressed_sparse_row_graph(edges_are_unsorted_for_distributed_graph_t,
+  compressed_sparse_row_graph(edges_are_unsorted_global_t,
                               InputIterator edge_begin, InputIterator edge_end,
                               vertices_size_type numlocalverts,
                               GlobalToLocal global_to_local,
@@ -737,7 +783,7 @@
   //  use in a distributed graph.
   template<typename InputIterator, typename EdgePropertyIterator,
            typename GlobalToLocal, typename EdgePred>
-  compressed_sparse_row_graph(edges_are_unsorted_for_distributed_graph_t,
+  compressed_sparse_row_graph(edges_are_unsorted_global_t,
                               InputIterator edge_begin, InputIterator edge_end,
                               EdgePropertyIterator ep_iter,
                               vertices_size_type numlocalverts,
@@ -748,7 +794,7 @@
       m_column(), m_property(prop)
   {
     std::vector<vertex_descriptor> sources, targets;
-    std::vector<typename inherited_edge_properties::edge_property_type> edge_props;
+    std::vector<typename inherited_edge_properties::edge_bundled> edge_props;
     for (; edge_begin != edge_end; ++edge_begin, ++ep_iter) {
       if (edge_pred(*edge_begin)) {
         sources.push_back(edge_begin->first);
@@ -776,6 +822,7 @@
     m_rowstart.clear();
     m_rowstart.resize(numverts + 1);
     for (size_t i = 0; i < numedges; ++i) {
+      assert(get(global_to_local, sources[i]) < numverts);
       ++m_rowstart[get(global_to_local, sources[i]) + 1];
     }
     // 2. Do a prefix sum on those to get starting positions of each row
@@ -809,7 +856,7 @@
   template <typename GlobalToLocal>
   void assign_sources_and_targets_global(std::vector<vertex_descriptor>& sources,
                                          std::vector<vertex_descriptor>& targets,
-                                         std::vector<typename inherited_edge_properties::edge_property_type>& edge_props,
+                                         std::vector<typename inherited_edge_properties::edge_bundled>& edge_props,
                                          vertices_size_type numverts,
                                          GlobalToLocal global_to_local) {
     assert (sources.size() == targets.size());
@@ -933,6 +980,100 @@
     assign(g, get(vertex_index, g), num_vertices(g), num_edges(g));
   }
 
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+  // Add edges from a sorted (smallest sources first) range of pairs and edge
+  // properties
+  template <typename BidirectionalIteratorOrig, typename EPIterOrig>
+  void
+  add_edges_sorted_internal(
+      BidirectionalIteratorOrig first_sorted,
+      BidirectionalIteratorOrig last_sorted,
+      EPIterOrig ep_iter_sorted) {
+    typedef boost::reverse_iterator<BidirectionalIteratorOrig> BidirectionalIterator;
+    typedef boost::reverse_iterator<EPIterOrig> EPIter;
+    // Flip sequence
+    BidirectionalIterator first(last_sorted);
+    BidirectionalIterator last(first_sorted);
+    typedef compressed_sparse_row_graph Graph;
+    typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
+    typedef typename boost::graph_traits<Graph>::vertices_size_type vertex_num;
+    typedef typename boost::graph_traits<Graph>::edges_size_type edge_num;
+    edge_num new_edge_count = std::distance(first, last);
+    EPIter ep_iter(ep_iter_sorted);
+    std::advance(ep_iter, -(std::ptrdiff_t)new_edge_count);
+    edge_num edges_added_before_i = new_edge_count; // Count increment to add to rowstarts
+    m_column.resize(m_column.size() + new_edge_count);
+    inherited_edge_properties::resize(inherited_edge_properties::size() + new_edge_count);
+    BidirectionalIterator current_new_edge = first, prev_new_edge = first;
+    EPIter current_new_edge_prop = ep_iter;
+    for (vertex_num i_plus_1 = num_vertices(*this); i_plus_1 > 0; --i_plus_1) {
+      vertex_num i = i_plus_1 - 1;
+      prev_new_edge = current_new_edge;
+      // edges_added_to_this_vertex = #mbrs of new_edges with first == i
+      edge_num edges_added_to_this_vertex = 0;
+      while (current_new_edge != last) {
+        if (current_new_edge->first != i) break;
+        ++current_new_edge;
+        ++current_new_edge_prop;
+        ++edges_added_to_this_vertex;
+      }
+      edges_added_before_i -= edges_added_to_this_vertex;
+      // Invariant: edges_added_before_i = #mbrs of new_edges with first < i
+      edge_num old_rowstart = m_rowstart[i];
+      edge_num new_rowstart = m_rowstart[i] + edges_added_before_i;
+      edge_num old_degree = m_rowstart[i + 1] - m_rowstart[i];
+      edge_num new_degree = old_degree + edges_added_to_this_vertex;
+      // Move old edges forward (by #new_edges before this i) to make room
+      // new_rowstart > old_rowstart, so use copy_backwards
+      if (old_rowstart != new_rowstart) {
+        std::copy_backward(m_column.begin() + old_rowstart,
+                           m_column.begin() + old_rowstart + old_degree,
+                           m_column.begin() + new_rowstart + old_degree);
+        inherited_edge_properties::move_range(old_rowstart, old_rowstart + old_degree, new_rowstart);
+      }
+      // Add new edges (reversed because current_new_edge is a
+      // const_reverse_iterator)
+      BidirectionalIterator temp = current_new_edge;
+      EPIter temp_prop = current_new_edge_prop;
+      for (; temp != prev_new_edge; ++old_degree) {
+        --temp;
+        m_column[new_rowstart + old_degree] = temp->second;
+        inherited_edge_properties::write_by_index(new_rowstart + old_degree, *temp_prop);
+      }
+      m_rowstart[i + 1] = new_rowstart + new_degree;
+      if (edges_added_before_i == 0) break; // No more edges inserted before this point
+      // m_rowstart[i] will be fixed up on the next iteration (to avoid
+      // changing the degree of vertex i - 1); the last iteration never changes
+      // it (either because of the condition of the break or because
+      // m_rowstart[0] is always 0)
+    }
+  }
+
+  // Add edges from a sorted (smallest sources first) range of pairs
+  template <typename BidirectionalIteratorOrig>
+  void
+  add_edges_sorted_internal(
+      BidirectionalIteratorOrig first_sorted,
+      BidirectionalIteratorOrig last_sorted) {
+    add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<typename inherited_edge_properties::edge_bundled>());
+  }
+
+  // Add edges from a range of (source, target) pairs that are unsorted
+  template <typename InputIterator>
+  inline void
+  add_edges_internal(InputIterator first, InputIterator last) {
+    typedef compressed_sparse_row_graph Graph;
+    typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
+    typedef typename boost::graph_traits<Graph>::vertices_size_type vertex_num;
+    typedef typename boost::graph_traits<Graph>::edges_size_type edge_num;
+    typedef std::vector<std::pair<vertex_t, vertex_t> > edge_vector_t;
+    edge_vector_t new_edges(first, last);
+    if (new_edges.empty()) return;
+    std::sort(new_edges.begin(), new_edges.end());
+    add_edges_sorted_internal(new_edges.begin(), new_edges.end());
+  }
+#endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+
   using inherited_vertex_properties::operator[];
   using inherited_edge_properties::operator[];
 
@@ -1044,62 +1185,35 @@
 #endif // BOOST_GRAPH_USE_OLD_CSR_INTERFACE
 
 #ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
-// Add edges from a range of (source, target) pairs that are unsorted
-template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator>
-inline void
-add_edges(InputIterator first, InputIterator last, BOOST_CSR_GRAPH_TYPE& g) {
-  typedef BOOST_CSR_GRAPH_TYPE Graph;
-  typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
-  typedef typename boost::graph_traits<Graph>::vertices_size_type vertex_num;
-  typedef typename boost::graph_traits<Graph>::edges_size_type edge_num;
-  typedef std::vector<std::pair<vertex_t, vertex_t> > edge_vector_t;
-  edge_vector_t new_edges(first, last);
-  if (new_edges.empty()) return;
-  std::sort(new_edges.begin(), new_edges.end());
-  edge_num edges_added_before_i = new_edges.size(); // Count increment to add to rowstarts
-  g.m_column.resize(g.m_column.size() + new_edges.size());
-  typename edge_vector_t::const_reverse_iterator
-    current_new_edge = new_edges.rbegin(),
-    prev_new_edge = new_edges.rbegin();
-  for (vertex_num i_plus_1 = num_vertices(g); i_plus_1 > 0; --i_plus_1) {
-    vertex_num i = i_plus_1 - 1;
-    prev_new_edge = current_new_edge;
-    // edges_added_to_this_vertex = #mbrs of new_edges with first == i
-    edge_num edges_added_to_this_vertex = 0;
-    while (current_new_edge !=
-            (typename edge_vector_t::const_reverse_iterator)new_edges.rend()) {
-      if (current_new_edge->first != i) break;
-      ++current_new_edge;
-      ++edges_added_to_this_vertex;
-    }
-    edges_added_before_i -= edges_added_to_this_vertex;
-    // Invariant: edges_added_before_i = #mbrs of new_edges with first < i
-    edge_num old_rowstart = g.m_rowstart[i];
-    edge_num new_rowstart = g.m_rowstart[i] + edges_added_before_i;
-    edge_num old_degree = g.m_rowstart[i + 1] - g.m_rowstart[i];
-    edge_num new_degree = old_degree + edges_added_to_this_vertex;
-    // Move old edges forward (by #new_edges before this i) to make room
-    // new_rowstart > old_rowstart, so use copy_backwards
-    if (old_rowstart != new_rowstart) {
-      std::copy_backward(g.m_column.begin() + old_rowstart,
-                         g.m_column.begin() + old_rowstart + old_degree,
-                         g.m_column.begin() + new_rowstart + old_degree);
-    }
-    // Add new edges (reversed because current_new_edge is a
-    // const_reverse_iterator)
-    typename edge_vector_t::const_reverse_iterator temp = current_new_edge;
-    for (; temp != prev_new_edge; ++old_degree) {
-      --temp;
-      g.m_column[new_rowstart + old_degree] = temp->second;
-    }
-    g.m_rowstart[i + 1] = new_rowstart + new_degree;
-    if (edges_added_before_i == 0) break; // No more edges inserted before this point
-    // g.m_rowstart[i] will be fixed up on the next iteration (to avoid
-    // changing the degree of vertex i - 1); the last iteration never changes
-    // it (either because of the condition of the break or because
-    // g.m_rowstart[0] is always 0)
+  // Add edges from a sorted (smallest sources first) range of pairs and edge
+  // properties
+  template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
+            typename EPIterOrig>
+  void
+  add_edges_sorted(
+      BidirectionalIteratorOrig first_sorted,
+      BidirectionalIteratorOrig last_sorted,
+      EPIterOrig ep_iter_sorted,
+      BOOST_CSR_GRAPH_TYPE& g) {
+    g.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted);
+  }
+
+  // Add edges from a sorted (smallest sources first) range of pairs
+  template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig>
+  void
+  add_edges_sorted(
+      BidirectionalIteratorOrig first_sorted,
+      BidirectionalIteratorOrig last_sorted,
+      BOOST_CSR_GRAPH_TYPE& g) {
+    g.add_edges_sorted_internal(first_sorted, last_sorted);
+  }
+
+  // Add edges from a range of (source, target) pairs that are unsorted
+  template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator>
+  inline void
+  add_edges(InputIterator first, InputIterator last, BOOST_CSR_GRAPH_TYPE& g) {
+    g.add_edges_internal(first, last);
   }
-}
 #endif // BOOST_GRAPH_USE_NEW_CSR_INTERFACE
 
 // From VertexListGraph

Modified: branches/release/boost/graph/detail/indexed_properties.hpp
==============================================================================
--- branches/release/boost/graph/detail/indexed_properties.hpp	(original)
+++ branches/release/boost/graph/detail/indexed_properties.hpp	2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
@@ -50,6 +50,12 @@
   indexed_vertex_properties(std::size_t n) : m_vertex_properties(n) { }
 
 public:
+  // Clear the properties vector
+  void clear()
+  {
+    m_vertex_properties.clear();
+  }
+
   // Resize the properties vector
   void resize(std::size_t n)
   {
@@ -101,6 +107,7 @@
   indexed_vertex_properties(std::size_t) { }
 
 public:
+  void clear() { }
   void resize(std::size_t) { }
   void reserve(std::size_t) { }
 };
@@ -127,6 +134,18 @@
   // Initialize with n default-constructed property values
   indexed_edge_properties(std::size_t n) : m_edge_properties(n) { }
 
+  // Get the size of the properties vector
+  std::size_t size() const
+  {
+    return m_edge_properties.size();
+  }
+
+  // Clear the properties vector
+  void clear()
+  {
+    m_edge_properties.clear();
+  }
+
   // Resize the properties vector
   void resize(std::size_t n)
   {
@@ -152,6 +171,14 @@
     m_edge_properties.push_back(prop);
   }
 
+  // Move range of properties backwards
+  void move_range(std::size_t src_begin, std::size_t src_end, std::size_t dest_begin) {
+    std::copy_backward(
+        m_edge_properties.begin() + src_begin,
+        m_edge_properties.begin() + src_end,
+        m_edge_properties.begin() + dest_begin + (src_end - src_begin));
+  }
+
  private:
   // Access to the derived object
   Derived& derived() { return *static_cast<Derived*>(this); }
@@ -174,16 +201,21 @@
   typedef void* edge_push_back_type;
 
   secret operator[](secret) { return secret(); }
+  void write_by_index(std::size_t idx, const no_property& prop) {}
 
  protected:
   // All operations do nothing.
   indexed_edge_properties() { }
   indexed_edge_properties(std::size_t) { }
+  std::size_t size() const {return 0;}
+  void clear() { }
   void resize(std::size_t) { }
   void reserve(std::size_t) { }
 
  public:
   void push_back(const edge_push_back_type&) { }
+  void move_range(std::size_t src_begin, std::size_t src_end, std::size_t dest_begin) {}
+
 };
 
 }

Modified: branches/release/boost/graph/filtered_graph.hpp
==============================================================================
--- branches/release/boost/graph/filtered_graph.hpp	(original)
+++ branches/release/boost/graph/filtered_graph.hpp	2009-06-30 13:08:49 EDT (Tue, 30 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: branches/release/boost/graph/graph_utility.hpp
==============================================================================
--- branches/release/boost/graph/graph_utility.hpp	(original)
+++ branches/release/boost/graph/graph_utility.hpp	2009-06-30 13:08:49 EDT (Tue, 30 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*/

Copied: branches/release/boost/graph/mcgregor_common_subgraphs.hpp (from r54069, /trunk/boost/graph/mcgregor_common_subgraphs.hpp)
==============================================================================
--- /trunk/boost/graph/mcgregor_common_subgraphs.hpp	(original)
+++ branches/release/boost/graph/mcgregor_common_subgraphs.hpp	2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
@@ -11,12 +11,10 @@
 #define BOOST_GRAPH_MCGREGOR_COMMON_SUBGRAPHS_HPP
 
 #include <algorithm>
-#include <map>
-#include <stack>
-#include <set>
 #include <vector>
+#include <stack>
 
-#include <boost/bind.hpp>
+#include <boost/make_shared.hpp>
 #include <boost/graph/adjacency_list.hpp>
 #include <boost/graph/filtered_graph.hpp>
 #include <boost/graph/graph_utility.hpp>
@@ -28,8 +26,8 @@
 
   namespace detail {
 
-    // Traits associated with common subgraphs, used mainly to
-    // keep a consistent type for the correspondence maps.   
+    // Traits associated with common subgraphs, used mainly to keep a
+    // consistent type for the correspondence maps.
     template <typename GraphFirst,
               typename GraphSecond,
               typename VertexIndexMapFirst,
@@ -39,18 +37,18 @@
       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;
+        correspondence_map_first_to_second_type;
   
       typedef shared_array_property_map<vertex_first_type, VertexIndexMapSecond>
-      correspondence_map_second_to_first_type;
+        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.
+  // 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 {
@@ -60,10 +58,10 @@
       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));
+    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:
@@ -85,8 +83,8 @@
             (property_map1, property_map2));
   }
 
-  // Binary function object that always returns true.  Used when vertices
-  // or edges are always equivalent (i.e. have no labels).
+  // 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,
@@ -100,10 +98,11 @@
 
   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.
+    // 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,
@@ -119,7 +118,8 @@
      typename graph_traits<GraphFirst>::vertex_descriptor new_vertex1,
      typename graph_traits<GraphSecond>::vertex_descriptor new_vertex2,
      EdgeEquivalencePredicate edges_equivalent,
-     VertexEquivalencePredicate vertices_equivalent)
+     VertexEquivalencePredicate vertices_equivalent,
+     bool only_connected_subgraphs)
     {
       typedef typename graph_traits<GraphFirst>::vertex_descriptor VertexFirst;
       typedef typename graph_traits<GraphSecond>::vertex_descriptor VertexSecond;
@@ -149,8 +149,8 @@
           continue;
         }
 
-        // NOTE: This will not work with parallel edges, since the first
-        // matching edge is always chosen.
+        // 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;
         
@@ -239,7 +239,7 @@
       } // BGL_FORALL_VERTICES_T
 
       // Make sure new vertices are connected to the existing subgraph
-      if (!has_one_edge) {
+      if (only_connected_subgraphs && !has_one_edge) {
         return (false);
       }
 
@@ -248,11 +248,12 @@
 
     // 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.
+    // 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,
@@ -273,6 +274,7 @@
      VertexStackFirst& vertex_stack1,
      EdgeEquivalencePredicate edges_equivalent,
      VertexEquivalencePredicate vertices_equivalent,
+     bool only_connected_subgraphs,
      SubGraphInternalCallback subgraph_callback)
     {
       typedef typename graph_traits<GraphFirst>::vertex_descriptor VertexFirst;
@@ -314,7 +316,8 @@
                                correspondence_map_1_to_2, correspondence_map_2_to_1,
                                (VertexSizeFirst)vertex_stack1.size(),
                                new_vertex1, new_vertex2,
-                               edges_equivalent, vertices_equivalent)) {
+                               edges_equivalent, vertices_equivalent,
+                               only_connected_subgraphs)) {
 
             // Keep track of old graph size for restoring later
             VertexSizeFirst old_graph_size = (VertexSizeFirst)vertex_stack1.size(),
@@ -344,7 +347,7 @@
                correspondence_map_1_to_2, correspondence_map_2_to_1,
                vertex_stack1,
                edges_equivalent, vertices_equivalent,
-               subgraph_callback);
+               only_connected_subgraphs, subgraph_callback);
 
             if (!continue_iteration) {
               return (false);
@@ -365,7 +368,7 @@
                   graph_traits<GraphFirst>::null_vertex());
                   
               vertex_stack1.pop();
-            }
+           }
 
           } // if can_extend_graph
 
@@ -382,8 +385,8 @@
               typename GraphSecond,
               typename VertexIndexMapFirst,
               typename VertexIndexMapSecond,
-              typename VertexEquivalencePredicate,
               typename EdgeEquivalencePredicate,
+              typename VertexEquivalencePredicate,
               typename SubGraphInternalCallback>
     inline void mcgregor_common_subgraphs_internal_init
     (const GraphFirst& graph1,
@@ -392,6 +395,7 @@
      const VertexIndexMapSecond vindex_map2,
      EdgeEquivalencePredicate edges_equivalent,
      VertexEquivalencePredicate vertices_equivalent,
+     bool only_connected_subgraphs,
      SubGraphInternalCallback subgraph_callback)
     {
       typedef mcgregor_common_subgraph_traits<GraphFirst,
@@ -425,6 +429,7 @@
          correspondence_map_1_to_2, correspondence_map_2_to_1,
          vertex_stack1,
          edges_equivalent, vertices_equivalent,
+         only_connected_subgraphs,
          subgraph_callback);
     }
     
@@ -449,6 +454,7 @@
    const VertexIndexMapSecond vindex_map2,
    EdgeEquivalencePredicate edges_equivalent,
    VertexEquivalencePredicate vertices_equivalent,
+   bool only_connected_subgraphs,
    SubGraphCallback user_callback)
   {
       
@@ -456,6 +462,7 @@
       (graph1, graph2,
        vindex_map1, vindex_map2,
        edges_equivalent, vertices_equivalent,
+       only_connected_subgraphs,
        user_callback);
   }
   
@@ -466,6 +473,7 @@
   void mcgregor_common_subgraphs
   (const GraphFirst& graph1,
    const GraphSecond& graph2,
+   bool only_connected_subgraphs,
    SubGraphCallback user_callback)
   {
       
@@ -473,7 +481,7 @@
       (graph1, graph2,
        get(vertex_index, graph1), get(vertex_index, graph2),
        always_equivalent(), always_equivalent(),
-       user_callback);
+       only_connected_subgraphs, user_callback);
   }
 
   // Named parameter variant of mcgregor_common_subgraphs
@@ -486,6 +494,7 @@
   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)
   {
@@ -500,7 +509,7 @@
                     always_equivalent()),
        choose_param(get_param(params, vertices_equivalent_t()),
                     always_equivalent()),
-       user_callback);
+       only_connected_subgraphs, user_callback);
   }
 
   // ==========================================================================
@@ -508,9 +517,9 @@
   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.
+    // 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,
@@ -518,36 +527,43 @@
               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
-        CorrespondenceMapFirstToSecond;
+        CachedCorrespondenceMapFirstToSecond;
 
       typedef typename SubGraphTraits::correspondence_map_second_to_first_type
-        CorrespondenceMapSecondToFirst;
+        CachedCorrespondenceMapSecondToFirst;
 
-      typedef std::pair<std::size_t, std::pair<CorrespondenceMapFirstToSecond,
-                                               CorrespondenceMapSecondToFirst> > SubGraph;
+      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,
+                                  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) { }
       
-      bool operator()(CorrespondenceMapFirstToSecond& correspondence_map_1_to_2,
-                      CorrespondenceMapSecondToFirst& correspondence_map_2_to_1,
-                      std::size_t subgraph_size) {
+      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 = m_subgraphs->begin();
+             subgraph_iter != m_subgraphs->end();
              ++subgraph_iter) {
 
           SubGraph subgraph_cached = *subgraph_iter;
@@ -557,11 +573,8 @@
             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,
+                                           subgraph_cached.second.first,
                                            m_graph1)) {
                                     
             // New subgraph is a duplicate
@@ -570,18 +583,25 @@
         }
   
         // 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);
+        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);
 
-        copy_vertex_property(correspondence_map_2_to_1,
-                             new_subgraph.second.second, m_graph1);
-        
-        m_subgraphs.push_back(new_subgraph);
+        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,
@@ -593,7 +613,7 @@
       const GraphFirst& m_graph2;
       const VertexIndexMapFirst m_vindex_map1;
       const VertexIndexMapSecond m_vindex_map2;
-      SubGraphList m_subgraphs;
+      shared_ptr<SubGraphList> m_subgraphs;
       SubGraphCallback m_user_callback;
     };
     
@@ -616,6 +636,7 @@
    const VertexIndexMapSecond vindex_map2,
    EdgeEquivalencePredicate edges_equivalent,
    VertexEquivalencePredicate vertices_equivalent,
+   bool only_connected_subgraphs,
    SubGraphCallback user_callback)
   {
     detail::unique_subgraph_interceptor<GraphFirst, GraphSecond,
@@ -629,23 +650,25 @@
       (graph1, graph2,
        vindex_map1, vindex_map2,
        edges_equivalent, vertices_equivalent,
-       unique_callback);
+       only_connected_subgraphs, unique_callback);
   }
 
-  // Variant of mcgregor_common_subgraphs_unique with all default parameters
+  // 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(),
-       user_callback);
+       only_connected_subgraphs, user_callback);
   }
 
   // Named parameter variant of mcgregor_common_subgraphs_unique
@@ -658,6 +681,7 @@
   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)
   {
@@ -671,7 +695,7 @@
                     always_equivalent()),
        choose_param(get_param(params, vertices_equivalent_t()),
                     always_equivalent()),
-       user_callback);
+       only_connected_subgraphs, user_callback);
   }
 
   // ==========================================================================
@@ -679,8 +703,8 @@
   namespace detail {
 
     // Binary function object that intercepts subgraphs from
-    // mcgregor_common_subgraphs_internal and maintains a cache
-    // of the largest subgraphs.
+    // mcgregor_common_subgraphs_internal and maintains a cache of the
+    // largest subgraphs.
     template <typename GraphFirst,
               typename GraphSecond,
               typename VertexIndexMapFirst,
@@ -688,63 +712,77 @@
               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
-      CorrespondenceMapFirstToSecond;
+        CachedCorrespondenceMapFirstToSecond;
 
       typedef typename SubGraphTraits::correspondence_map_second_to_first_type
-      CorrespondenceMapSecondToFirst;
+        CachedCorrespondenceMapSecondToFirst;
+
+      typedef std::pair<VertexSizeFirst,
+        std::pair<CachedCorrespondenceMapFirstToSecond,
+                  CachedCorrespondenceMapSecondToFirst> > SubGraph;
 
-      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) :                                  
+                                   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;
+        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) {
+        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);
+          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_cached_subgraphs() {
+      void output_subgraphs() {
         for (typename SubGraphList::const_iterator
-               subgraph_iter = m_subgraphs.begin();
-             subgraph_iter != m_subgraphs.end();
+               subgraph_iter = m_subgraphs->begin();
+             subgraph_iter != m_subgraphs->end();
              ++subgraph_iter) {
 
           SubGraph subgraph_cached = *subgraph_iter;
@@ -753,15 +791,15 @@
                           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;
+      shared_ptr<SubGraphList> m_subgraphs;
+      shared_ptr<VertexSizeFirst> m_largest_size_so_far;
       SubGraphCallback m_user_callback;
-      typename graph_traits<GraphFirst>::vertices_size_type m_largest_size_so_far;
     };
     
   } // namespace detail
@@ -776,13 +814,14 @@
             typename EdgeEquivalencePredicate,
             typename VertexEquivalencePredicate,
             typename SubGraphCallback>
-  void mcgregor_maximum_common_subgraphs
+  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,
@@ -794,42 +833,45 @@
       (graph1, graph2,
        vindex_map1, vindex_map2,
        edges_equivalent, vertices_equivalent,
-       max_interceptor);
+       only_connected_subgraphs, max_interceptor);
 
     // Only output the largest subgraphs
-    max_interceptor.output_cached_subgraphs();
+    max_interceptor.output_subgraphs();
   }
 
-  // Variant of mcgregor_maximum_common_subgraphs with all default parameters
+  // Variant of mcgregor_common_subgraphs_maximum with all default
+  // parameters.
   template <typename GraphFirst,
             typename GraphSecond,
             typename SubGraphCallback>
-  void mcgregor_maximum_common_subgraphs
+  void mcgregor_common_subgraphs_maximum
   (const GraphFirst& graph1,
    const GraphSecond& graph2,
+   bool only_connected_subgraphs,
    SubGraphCallback user_callback)
   {
-    mcgregor_maximum_common_subgraphs
+    mcgregor_common_subgraphs_maximum
       (graph1, graph2,
        get(vertex_index, graph1), get(vertex_index, graph2),
        always_equivalent(), always_equivalent(),
-       user_callback);
+       only_connected_subgraphs, user_callback);
   }
 
-  // Named parameter variant of mcgregor_maximum_common_subgraphs
+  // Named parameter variant of mcgregor_common_subgraphs_maximum
   template <typename GraphFirst,
             typename GraphSecond,
             typename SubGraphCallback,
             typename Param,
             typename Tag,
             typename Rest>
-  void mcgregor_maximum_common_subgraphs
+  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_maximum_common_subgraphs
+    mcgregor_common_subgraphs_maximum
       (graph1, graph2,
        choose_const_pmap(get_param(params, vertex_index1),
                          graph1, vertex_index),
@@ -839,7 +881,7 @@
                     always_equivalent()),
        choose_param(get_param(params, vertices_equivalent_t()),
                     always_equivalent()),
-       user_callback);
+       only_connected_subgraphs, user_callback);
   }
 
   // ==========================================================================
@@ -847,8 +889,8 @@
   namespace detail {
 
     // Binary function object that intercepts subgraphs from
-    // mcgregor_common_subgraphs_internal and maintains a cache
-    // of the largest, unique subgraphs.
+    // mcgregor_common_subgraphs_internal and maintains a cache of the
+    // largest, unique subgraphs.
     template <typename GraphFirst,
               typename GraphSecond,
               typename VertexIndexMapFirst,
@@ -856,19 +898,22 @@
               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
-      CorrespondenceMapFirstToSecond;
+        CachedCorrespondenceMapFirstToSecond;
 
       typedef typename SubGraphTraits::correspondence_map_second_to_first_type
-      CorrespondenceMapSecondToFirst;
+        CachedCorrespondenceMapSecondToFirst;
+
+      typedef std::pair<VertexSizeFirst,
+        std::pair<CachedCorrespondenceMapFirstToSecond,
+                  CachedCorrespondenceMapSecondToFirst> > SubGraph;
 
-      typedef std::pair<std::size_t,
-                        std::pair<CorrespondenceMapFirstToSecond,
-                                  CorrespondenceMapSecondToFirst> > SubGraph;
-                
       typedef std::vector<SubGraph> SubGraphList;
 
       unique_maximum_subgraph_interceptor(const GraphFirst& graph1,
@@ -878,33 +923,33 @@
                                           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) { }
+        m_subgraphs(make_shared<SubGraphList>()),
+        m_largest_size_so_far(make_shared<VertexSizeFirst>(0)),
+        m_user_callback(user_callback) { }        
       
-      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;
+      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) {
+        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 = 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,
+                                             subgraph_cached.second.first,
                                              m_graph1)) {
                                       
               // New subgraph is a duplicate
@@ -913,27 +958,34 @@
           }
     
           // 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);
+          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_cached_subgraphs() {
+      void output_subgraphs() {
         for (typename SubGraphList::const_iterator
-               subgraph_iter = m_subgraphs.begin();
-             subgraph_iter != m_subgraphs.end();
+               subgraph_iter = m_subgraphs->begin();
+             subgraph_iter != m_subgraphs->end();
              ++subgraph_iter) {
 
           SubGraph subgraph_cached = *subgraph_iter;
@@ -948,16 +1000,16 @@
       const GraphFirst& m_graph2;
       const VertexIndexMapFirst m_vindex_map1;
       const VertexIndexMapSecond m_vindex_map2;
-      SubGraphList m_subgraphs;
+      shared_ptr<SubGraphList> m_subgraphs;
+      shared_ptr<VertexSizeFirst> m_largest_size_so_far;
       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.
+  // 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,
@@ -965,13 +1017,14 @@
             typename EdgeEquivalencePredicate,
             typename VertexEquivalencePredicate,
             typename SubGraphCallback>
-  void mcgregor_maximum_common_subgraphs_unique
+  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,
@@ -983,43 +1036,46 @@
       (graph1, graph2,
        vindex_map1, vindex_map2,
        edges_equivalent, vertices_equivalent,
-       unique_max_interceptor);
+       only_connected_subgraphs, unique_max_interceptor);
 
     // Only output the largest, unique subgraphs
-    unique_max_interceptor.output_cached_subgraphs();
+    unique_max_interceptor.output_subgraphs();
   }
 
-  // Variant of mcgregor_maximum_common_subgraphs_unique with all default parameters
+  // Variant of mcgregor_common_subgraphs_maximum_unique with all default parameters
   template <typename GraphFirst,
             typename GraphSecond,
             typename SubGraphCallback>
-  void mcgregor_maximum_common_subgraphs_unique
+  void mcgregor_common_subgraphs_maximum_unique
   (const GraphFirst& graph1,
    const GraphSecond& graph2,
+   bool only_connected_subgraphs,
    SubGraphCallback user_callback)
   {
 
-    mcgregor_maximum_common_subgraphs_unique
+    mcgregor_common_subgraphs_maximum_unique
       (graph1, graph2,
        get(vertex_index, graph1), get(vertex_index, graph2),
        always_equivalent(), always_equivalent(),
-       user_callback);
+       only_connected_subgraphs, user_callback);
   }
 
-  // Named parameter variant of mcgregor_maximum_common_subgraphs_unique
+  // Named parameter variant of
+  // mcgregor_common_subgraphs_maximum_unique
   template <typename GraphFirst,
             typename GraphSecond,
             typename SubGraphCallback,
             typename Param,
             typename Tag,
             typename Rest>
-  void mcgregor_maximum_common_subgraphs_unique
+  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_maximum_common_subgraphs_unique
+    mcgregor_common_subgraphs_maximum_unique
       (graph1, graph2,
        choose_const_pmap(get_param(params, vertex_index1),
                          graph1, vertex_index),
@@ -1029,45 +1085,33 @@
                     always_equivalent()),
        choose_param(get_param(params, vertices_equivalent_t()),
                     always_equivalent()),
-       user_callback);
+       only_connected_subgraphs, 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,
+  // 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 CorrespondenceMapSecondToFirst,
-            typename MembershipMapFirst,
-            typename MembershipMapSecond>
-  void fill_membership_maps
+            typename MembershipMapFirst>
+  void fill_membership_map
   (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;
+   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());
     }
 
-    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.
+  // 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 {

Modified: branches/release/boost/property_map/shared_array_property_map.hpp
==============================================================================
--- branches/release/boost/property_map/shared_array_property_map.hpp	(original)
+++ branches/release/boost/property_map/shared_array_property_map.hpp	2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
@@ -25,6 +25,8 @@
   typedef T& reference;
   typedef boost::lvalue_property_map_tag category;
 
+  inline shared_array_property_map(): data(), index() {}
+
   explicit inline shared_array_property_map(
     size_t n,
     const IndexMap& _id = IndexMap())

Modified: branches/release/libs/graph/doc/compressed_sparse_row.html
==============================================================================
--- branches/release/libs/graph/doc/compressed_sparse_row.html	(original)
+++ branches/release/libs/graph/doc/compressed_sparse_row.html	2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
@@ -294,6 +294,14 @@
 template&lt;typename InputIterator, typename Graph&gt;
 void add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph&amp; g);
 
+<b>(new interface only)</b>
+template&lt;typename BidirectionalIterator, typename Graph&gt;
+void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, compressed_sparse_row_graph&amp; g);
+
+<b>(new interface only)</b>
+template&lt;typename BidirectionalIterator, typename EPIter, typename Graph&gt;
+void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, EPIter ep_iter, compressed_sparse_row_graph&amp; g);
+
 } <i>// end namespace boost</i>
    </pre>
 
@@ -918,7 +926,7 @@
 
     <pre><a name="add_edges"></a>
 template&lt;typename InputIterator&gt;
-edge_descriptor add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph&amp; g)
+void add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph&amp; g)
     </pre>
     
     <p class="indent">
@@ -932,6 +940,47 @@
     </p>
 
     <hr></hr>
+
+    <pre><a name="add_edges_sorted"></a>
+template&lt;typename BidirectionalIterator&gt;
+void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, compressed_sparse_row_graph&amp; g)
+    </pre>
+    
+    <p class="indent">
+      Add a range of edges (from <tt>first</tt> to <tt>last</tt>) to the graph.
+      The <tt>BidirectionalIterator</tt> must be a model of <a
+      href="http://www.sgi.com/tech/stl/BidirectionalIterator.html">BidirectionalIterator</a>
+      whose <code>value_type</code> is an <code>std::pair</code> of integer
+      values. These integer values are the source and target vertices of the
+      new edges.  The edges must be sorted in increasing order by source vertex
+      index.
+      <b>(This function is only provided by the new interface.)</b>
+    </p>
+
+    <hr></hr>
+
+    <pre><a name="add_edges_sorted_prop"></a>
+template&lt;typename BidirectionalIterator, typename EPIter&gt;
+void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, EPIter ep_iter, compressed_sparse_row_graph&amp; g)
+    </pre>
+    
+    <p class="indent">
+      Add a range of edges (from <tt>first</tt> to <tt>last</tt>) to the graph.
+      The <tt>BidirectionalIterator</tt> and <tt>EPIter</tt> must be models of
+      <a
+      href="http://www.sgi.com/tech/stl/BidirectionalIterator.html">BidirectionalIterator</a>.
+      The <code>value_type</code> of the <tt>BidirectionalIterator</tt> must be
+      an <code>std::pair</code> of integer
+      values. These integer values are the source and target vertices of the
+      new edges.
+      The <code>value_type</code> of the <tt>EPIter</tt> must be the edge
+      property type of the graph.
+      The edges must be sorted in increasing order by source vertex
+      index.
+      <b>(This function is only provided by the new interface.)</b>
+    </p>
+
+    <hr></hr>
     <a name="example"></a><h2>Example</h2>
 
     <br>[<a

Modified: branches/release/libs/graph/doc/table_of_contents.html
==============================================================================
--- branches/release/libs/graph/doc/table_of_contents.html	(original)
+++ branches/release/libs/graph/doc/table_of_contents.html	2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
@@ -245,6 +245,7 @@
                 <tt>make_maximal_planar</tt></a>
                 </ol>
                 <li>lengauer_tarjan_dominator_tree</li>
+                <li>mcgregor_common_subgraphs</li>
             </OL>
          </OL>
 

Modified: branches/release/libs/graph/example/Jamfile.v2
==============================================================================
--- branches/release/libs/graph/example/Jamfile.v2	(original)
+++ branches/release/libs/graph/example/Jamfile.v2	2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
@@ -18,3 +18,4 @@
 exe tiernan_girth_circumference : tiernan_girth_circumference.cpp ;
 exe bron_kerbosch_print_cliques : bron_kerbosch_print_cliques.cpp ;
 exe bron_kerbosch_clique_number : bron_kerbosch_clique_number.cpp ;
+exe mcgregor_subgraphs_example : mcgregor_subgraphs_example.cpp ;

Modified: branches/release/libs/graph/test/CMakeLists.txt
==============================================================================
--- branches/release/libs/graph/test/CMakeLists.txt	(original)
+++ branches/release/libs/graph/test/CMakeLists.txt	2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
@@ -47,6 +47,7 @@
 boost_test_run(cuthill_mckee_ordering)
 boost_test_run(king_ordering)
 boost_test_run(matching_test)
+boost_test_run(mcgregor_subgraphs_test)
 # boost_test_run(max_flow_test)
 # boost_test_run(kolmogorov_max_flow_test) TODO: Boost 1.34.x only
 

Modified: branches/release/libs/graph/test/Jamfile.v2
==============================================================================
--- branches/release/libs/graph/test/Jamfile.v2	(original)
+++ branches/release/libs/graph/test/Jamfile.v2	2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
@@ -118,6 +118,7 @@
     [ run clustering_coefficient.cpp ]
     [ run core_numbers_test.cpp ]
     [ run read_propmap.cpp ]
+    [ run mcgregor_subgraphs_test.cpp ]
 
     $(optional_tests)
     ;

Copied: branches/release/libs/graph/test/mcgregor_subgraphs_test.cpp (from r54216, /trunk/libs/graph/test/mcgregor_subgraphs_test.cpp)
==============================================================================
--- /trunk/libs/graph/test/mcgregor_subgraphs_test.cpp	(original)
+++ branches/release/libs/graph/test/mcgregor_subgraphs_test.cpp	2009-06-30 13:08:49 EDT (Tue, 30 Jun 2009)
@@ -1,7 +1,17 @@
+//=======================================================================
+// Copyright 2009 Trustees of Indiana University.
+// Authors: Michael Hansen
+//
+// 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)
+//=======================================================================
+
+#include <cmath>
 #include <iostream>
 #include <fstream>
+#include <sstream>
 #include <vector>
-#include <cmath>
 
 #include <boost/lexical_cast.hpp>
 #include <boost/random.hpp>
@@ -13,10 +23,12 @@
 #include <boost/graph/random.hpp>
 #include <boost/graph/mcgregor_common_subgraphs.hpp>
 #include <boost/property_map/shared_array_property_map.hpp>
+#include <boost/test/minimal.hpp>
 
 using namespace boost;
 
 bool was_common_subgraph_found = false, output_graphs = false;
+std::vector<std::string> simple_subgraph_list;
 
 // Callback that compares incoming graphs to the supplied common
 // subgraph.
@@ -57,9 +69,8 @@
     MembershipMap membership_map2(num_vertices(m_graph2),
                                   get(vertex_index, m_graph2));
 
-    fill_membership_maps(m_graph1, m_graph2,
-                         correspondence_map_1_to_2, correspondence_map_2_to_1,
-                         membership_map1, membership_map2);
+    fill_membership_map<Graph>(m_graph1, correspondence_map_1_to_2, membership_map1);
+    fill_membership_map<Graph>(m_graph2, correspondence_map_2_to_1, membership_map2);
 
     // Generate filtered graphs using membership maps
     typedef typename membership_filtered_graph_traits<Graph, MembershipMap>::graph_type
@@ -172,6 +183,46 @@
   Graph& m_common_subgraph;
 };
 
+template <typename Graph>
+struct simple_callback {
+
+  simple_callback(const Graph& graph1) :
+    m_graph1(graph1) { }
+
+  template <typename CorrespondenceMapFirstToSecond,
+            typename CorrespondenceMapSecondToFirst>
+  bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
+                  CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
+                  typename graph_traits<Graph>::vertices_size_type subgraph_size) {
+
+    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+    typedef typename property_map<Graph, vertex_index_t>::type VertexIndexMap;
+    typedef typename property_map<Graph, vertex_name_t>::type VertexNameMap;
+    typedef typename property_map<Graph, edge_name_t>::type EdgeNameMap;
+
+    std::stringstream subgraph_string;
+
+    BGL_FORALL_VERTICES_T(vertex1, m_graph1, Graph) {
+
+      Vertex vertex2 = get(correspondence_map_1_to_2, vertex1);
+
+      if (vertex2 != graph_traits<Graph>::null_vertex()) {
+        subgraph_string << vertex1 << "," << vertex2 << " ";
+      }
+
+    }
+
+    simple_subgraph_list.push_back(subgraph_string.str());
+
+    return (true);
+  }
+
+private:
+  const Graph& m_graph1;
+
+};
+
 template <typename Graph,
           typename RandomNumberGenerator,
           typename VertexNameMap,
@@ -199,8 +250,8 @@
        v_iter != new_vertices.end(); ++v_iter) {
 
     Vertex source_vertex = *v_iter;
-    int edges_for_vertex = std::min((generator() % max_edges_per_vertex) + 1,
-                                    (int)num_vertices(graph));
+    int edges_for_vertex = (std::min)((int)(generator() % max_edges_per_vertex) + 1,
+                                      (int)num_vertices(graph));
 
     while (edges_for_vertex > 0) {
 
@@ -224,6 +275,11 @@
   }
 }
 
+bool has_subgraph_string(std::string set_string) {
+  return (std::find(simple_subgraph_list.begin(), simple_subgraph_list.end(),
+                    set_string) != simple_subgraph_list.end());
+}
+
 int test_main (int argc, char *argv[]) {
   int vertices_to_create = 10;
   int max_edges_per_vertex = 2;
@@ -326,11 +382,89 @@
 
   test_callback<Graph> user_callback(common_subgraph, graph1, graph2);
 
-  mcgregor_common_subgraphs(graph1, graph2, user_callback,
+  mcgregor_common_subgraphs(graph1, graph2, true, user_callback,
     edges_equivalent(make_property_map_equivalent(ename_map1, ename_map2)).
     vertices_equivalent(make_property_map_equivalent(vname_map1, vname_map2)));
 
   BOOST_CHECK(was_common_subgraph_found);
 
+  // Test maximum and unique variants on known graphs
+  Graph graph_simple1, graph_simple2;
+  simple_callback<Graph> user_callback_simple(graph_simple1);
+
+  VertexNameMap vname_map_simple1 = get(vertex_name, graph_simple1);
+  VertexNameMap vname_map_simple2 = get(vertex_name, graph_simple2);
+
+  put(vname_map_simple1, add_vertex(graph_simple1), 1);
+  put(vname_map_simple1, add_vertex(graph_simple1), 2);
+  put(vname_map_simple1, add_vertex(graph_simple1), 3);
+
+  add_edge(0, 1, graph_simple1);
+  add_edge(0, 2, graph_simple1);
+  add_edge(1, 2, graph_simple1);
+
+  put(vname_map_simple2, add_vertex(graph_simple2), 1);
+  put(vname_map_simple2, add_vertex(graph_simple2), 2);
+  put(vname_map_simple2, add_vertex(graph_simple2), 3);
+  put(vname_map_simple2, add_vertex(graph_simple2), 4);
+
+  add_edge(0, 1, graph_simple2);
+  add_edge(0, 2, graph_simple2);
+  add_edge(1, 2, graph_simple2);
+  add_edge(1, 3, graph_simple2);
+
+  // Unique subgraphs
+  std::cout << "Searching for unique subgraphs" << std::endl;
+  mcgregor_common_subgraphs_unique(graph_simple1, graph_simple2,
+    true, user_callback_simple,
+    vertices_equivalent(make_property_map_equivalent(vname_map_simple1, vname_map_simple2))); 
+
+  BOOST_CHECK(has_subgraph_string("0,0 1,1 "));
+  BOOST_CHECK(has_subgraph_string("0,0 1,1 2,2 "));
+  BOOST_CHECK(has_subgraph_string("0,0 2,2 "));
+  BOOST_CHECK(has_subgraph_string("1,1 2,2 "));
+
+  if (output_graphs) {
+    std::copy(simple_subgraph_list.begin(), simple_subgraph_list.end(),
+              std::ostream_iterator<std::string>(std::cout, "\n"));
+
+    std::cout << std::endl;
+  }
+
+  simple_subgraph_list.clear();
+
+  // Maximum subgraphs
+  std::cout << "Searching for maximum subgraphs" << std::endl;
+  mcgregor_common_subgraphs_maximum(graph_simple1, graph_simple2,
+    true, user_callback_simple,
+    vertices_equivalent(make_property_map_equivalent(vname_map_simple1, vname_map_simple2))); 
+
+  BOOST_CHECK(has_subgraph_string("0,0 1,1 2,2 "));
+
+  if (output_graphs) {
+    std::copy(simple_subgraph_list.begin(), simple_subgraph_list.end(),
+              std::ostream_iterator<std::string>(std::cout, "\n"));
+
+    std::cout << std::endl;
+  }
+
+  simple_subgraph_list.clear();
+
+  // Maximum, unique subgraphs
+  std::cout << "Searching for maximum unique subgraphs" << std::endl;
+  mcgregor_common_subgraphs_maximum_unique(graph_simple1, graph_simple2,
+    true, user_callback_simple,
+    vertices_equivalent(make_property_map_equivalent(vname_map_simple1, vname_map_simple2))); 
+
+  BOOST_CHECK(simple_subgraph_list.size() == 1);
+  BOOST_CHECK(has_subgraph_string("0,0 1,1 2,2 "));
+
+  if (output_graphs) {
+    std::copy(simple_subgraph_list.begin(), simple_subgraph_list.end(),
+              std::ostream_iterator<std::string>(std::cout, "\n"));
+
+    std::cout << std::endl;
+  }
+
   return 0;
 }