| //======================================================================= | |
| // 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 |