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