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