#include <boost/graph/properties.hpp>
#include <boost/property_map/shared_array_property_map.hpp>
-namespace boost {
+namespace boost
+{
- namespace detail {
+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 {
-
+ 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));
+ const PropertyMapSecond property_map2)
+ : m_property_map1(property_map1), m_property_map2(property_map2)
+ {
}
-
- private:
+
+ 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);
+};
+
+// 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 {
+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)
+ 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);
- }
+ typedef typename graph_traits< GraphSecond >::vertex_descriptor
+ VertexSecond;
- bool has_one_edge = false;
+ typedef typename graph_traits< GraphFirst >::edge_descriptor EdgeFirst;
+ typedef
+ typename graph_traits< GraphSecond >::edge_descriptor EdgeSecond;
- // 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;
- }
+ // Check vertex equality
+ if (!vertices_equivalent(new_vertex1, new_vertex2))
+ {
+ return (false);
}
- // 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);
+ // Vertices match and graph is empty, so we can extend the subgraph
+ if (subgraph_size == 0)
+ {
+ return (true);
}
- bool is_undirected1 = is_undirected(graph1),
- is_undirected2 = is_undirected(graph2);
+ bool has_one_edge = false;
- if (is_undirected1 && is_undirected2) {
+ // Verify edges with existing sub-graph
+ BGL_FORALL_VERTICES_T(existing_vertex1, graph1, GraphFirst)
+ {
- // Edge in both graphs exists and both graphs are undirected
- if (edge_to_new_exists1 && edge_to_new_exists2) {
- has_one_edge = true;
- }
+ VertexSecond existing_vertex2
+ = get(correspondence_map_1_to_2, existing_vertex1);
- continue;
- }
- else {
+ // Skip unassociated vertices
+ if (existing_vertex2 == graph_traits< GraphSecond >::null_vertex())
+ {
+ continue;
+ }
- if (!is_undirected1) {
+ // 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 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;
- }
+ // 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;
+ }
}
- }
- if (!is_undirected2) {
+ // 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)))
+ {
- // 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;
- }
+ return (false);
}
- }
- // 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;
- }
+ bool is_undirected1 = is_undirected(graph1),
+ is_undirected2 = is_undirected(graph2);
- } // else
+ if (is_undirected1 && is_undirected2)
+ {
- } // BGL_FORALL_VERTICES_T
+ // Edge in both graphs exists and both graphs are undirected
+ if (edge_to_new_exists1 && edge_to_new_exists2)
+ {
+ has_one_edge = true;
+ }
- // Make sure new vertices are connected to the existing subgraph
- if (only_connected_subgraphs && !has_one_edge) {
- return (false);
- }
+ 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);
- }
+ return (true);
+ }
// Recursive method that does a depth-first search in the space of
// potential subgraphs. At each level, every new vertex pair from
// 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)
+ 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);
+ 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;
}
-
- // 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);
+
+ 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)
+ 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);
+ 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 {
+
+} // 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));
+ 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)
+ {
}
- BGL_FORALL_VERTICES_T(vertex2, m_graph2, GraphFirst) {
- put(new_subgraph_2_to_1, vertex2, get(correspondence_map_2_to_1, vertex2));
+ 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));
}
- 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;
+ 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 {
+
+} // 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;
+ 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)
+ {
}
- 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);
+ 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);
+ 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(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));
- }
+ 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)));
+ m_subgraphs->push_back(std::make_pair(subgraph_size,
+ std::make_pair(new_subgraph_1_to_2, new_subgraph_2_to_1)));
+ }
+
+ return (true);
}
- 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);
+ 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;
+ 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);
+
+} // 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 {
+}
+
+// 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;
+ 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)
+ {
}
- 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);
+ 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)));
}
- }
-
- // 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);
}
-
- 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);
+
+ 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;
+ 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);
+
+} // 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());
+}
+
+// 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;
+}
+
+// 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
projects / ceph.git / blobdiff