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