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