<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN">
<!--
Copyright (c) Michael Hansen 2009
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)
-->
<html>
<head>
<title>Boost Graph Library: McGregor Common Subgraphs</title>
<style type="text/css">
<!--
body {
color: black;
background-color: white;
}
.comment {
color: #333333;
}
a {
color: blue;
}
a:visited {
color: #551A8B;
}
-->
</style>
</head>
<body>
<img src="../../../boost.png" alt="C++ Boost" width="277" height="86" />
<br />
<h1>
<tt>mcgregor_common_subgraphs</tt>
</h1>
<pre>
<em class="comment">// named parameter version</em>
template <typename GraphFirst,
typename GraphSecond,
typename SubGraphCallback,
typename Param,
typename Tag,
typename Rest>
void mcgregor_common_subgraphs
(const GraphFirst& graph1,
const GraphSecond& graph2,
SubGraphCallback user_callback,
bool only_connected_subgraphs,
const bgl_named_params<Param, Tag, Rest>& params);
<em class="comment">// non-named parameter version</em>
template <typename GraphFirst,
typename GraphSecond,
typename <a href="../../property_map/doc/ReadablePropertyMap.html">VertexIndexMapFirst</a>,
typename <a href="../../property_map/doc/ReadablePropertyMap.html">VertexIndexMapSecond</a>,
typename <a href="http://www.sgi.com/tech/stl/BinaryFunction.html">EdgeEquivalencePredicate</a>,
typename <a href="http://www.sgi.com/tech/stl/BinaryFunction.html">VertexEquivalencePredicate</a>,
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);
</pre>
<p>
This algorithm finds all common subgraphs
between <tt>graph1</tt> and <tt>graph2</tt> and outputs them
to <tt>user_callback</tt>. The <tt>edges_equivalent</tt>
and <tt>vertices_equivalent</tt> predicates are used to
determine edges and vertex equivalence between the two graphs.
To use property maps for equivalence, look at
the <tt><a href="#make_property_map_equivalent">make_property_map_equivalent</a></tt>
function. By
default, <tt><a href="#always_equivalent">always_equivalent</a></tt>
is used, which returns true for any pair of edges or vertices.
</p>
<p>
McGregor's algorithm does a depth-first search on the space of
possible common subgraphs. At each level, every unvisited pair
of vertices from <tt>graph1</tt> and <tt>graph2</tt> are checked
to see if they can extend the current subgraph. This is done in
three steps (assume <tt>vertex1</tt> is
from <tt>graph1</tt> and <tt>vertex2</tt> is
from <tt>graph2</tt>):
<ol>
<li>
Verify that the <tt>vertex1</tt> and <tt>vertex2</tt> are
equivalent using the <tt>vertices_equivalent</tt> predicate.
</li>
<li>
For every vertex pair
(<tt>existing_vertex1</tt>, <tt>existing_vertex2</tt>) in
the current subgraph, ensure that any edges
between <tt>vertex1</tt> and <tt>existing_vertex1</tt>
in <tt>graph1</tt> and between <tt>vertex2</tt>
and <tt>existing_vertex2</tt> in <tt>graph2</tt> match
(i.e. either both exist of both don't exist). If both edges
exist, they are checked for equivalence using
the <tt>edges_equivalent</tt> predicate.
</li>
<li>
Lastly (and optionally), make sure that the new subgraph
vertex has at least one edge connecting it to the existing
subgraph. When the <tt>only_connected_subgraphs</tt>
parameter is false, this step is skipped.
</li>
</ol>
</p>
<h3>Where Defined</h3>
<a href="../../../boost/graph/mcgregor_common_subgraphs.hpp"><tt>boost/graph/mcgregor_common_subgraphs.hpp</tt></a>
<p>
All functions are defined in the boost namespace.
</p>
<h3>Parameters</h3>
IN: <tt>const GraphFirst& graph1</tt>
<blockquote>
The first graph of the pair to be searched. The
type <tt>GraphFirst</tt> must be a model of
<a href="./VertexListGraph.html">Vertex List Graph</a>
and <a href="./IncidenceGraph.html">Incidence Graph</a>. All
parameters with a "<tt>1</tt>"
(i.e. <tt>vindex_map1</tt>, <tt>correspondence_map_1_to_2</tt>)
use this graph's vertices as keys.
</blockquote>
IN: <tt>const GraphSecond& graph2</tt>
<blockquote>
The second graph of the pair to be searched. The
type <tt>Graphsecond</tt> must be a model of
<a href="./VertexListGraph.html">Vertex List Graph</a>
and <a href="./IncidenceGraph.html">Incidence Graph</a>. All
parameters with a "<tt>2</tt>"
(i.e. <tt>vindex_map2</tt>, <tt>correspondence_map_2_to_1</tt>)
use this graph's vertices as keys.
</blockquote>
IN: <tt>bool only_connected_subgraphs</tt>
<blockquote>
If <tt>true</tt>, subgraphs are expanded only when matching vertices
have at least one edge connecting them to the existing subgraph.
</blockquote>
OUT: <tt>SubGraphCallback user_callback</tt>
<blockquote>
A function object that will be invoked when a subgraph has been discovered. The operator() must have the following form:
<pre>
template <typename CorrespondenceMapFirstToSecond,
typename CorrespondenceMapSecondToFirst>
bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
typename graph_traits<GraphFirst>::vertices_size_type subgraph_size);
</pre>
Both the <tt>CorrespondenceMapFirstToSecond</tt>
and <tt>CorresondenceMapSecondToFirst</tt> types are models
of <a href="../../property_map/doc/ReadablePropertyMap.html">Readable
Property Map</a> and map equivalent vertices across the two
graphs given to <tt>mcgregor_common_subgraphs</tt>. For
example, if <tt>vertex1</tt> is
from <tt>graph1</tt>, <tt>vertex2</tt> is from <tt>graph2</tt>,
and the vertices can be considered equivalent in the subgraph,
then <tt>get(correspondence_map_1_to_2, vertex1)</tt> will
be <tt>vertex2</tt> and <tt>get(correspondence_map_2_to_1,
vertex2)</tt> will be <tt>vertex1</tt>. If any vertex,
say <tt>vertex1</tt> in <tt>graph1</tt>, doesn't match a vertex
in the other graph (<tt>graph2</tt> in this example),
then <tt>get(correspondence_map_1_to_2, vertex1)</tt> will
be <tt>graph_traits<GraphSecond>::null_vertex()</tt>.
Likewise for any un-matched vertices from <tt>graph2</tt>,
<tt>get(correspondence_map_2_to_1, vertex2)</tt> will
be <tt>graph_traits<GraphFirst>::null_vertex()</tt>.
<br /><br /> The <tt>subgraph_size</tt> parameter is the number
of vertices in the subgraph, or the number of matched vertex
pairs contained in the correspondence maps. This can be used to
quickly filter out subgraphs whose sizes do not fall within the
desired range.<br /><br />Returning <tt>false</tt> from the
callback will abort the search immediately. Otherwise, the
entire search space will be explored [<a href="#1">1</a>].
</blockquote>
<h3>Named Parameters</h3>
IN: <tt>vertex_index1(VertexIndexMapFirst vindex_map1)</tt>
<blockquote>
This maps each vertex to an integer in the range <tt>[0,
num_vertices(graph1)]</tt>. This is necessary for efficient storage
of the subgraphs. The type VertexIndexMapFirst must be a model of
<a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>.
<br />
<b>Default:</b> <tt>get(vertex_index, graph1)</tt>
</blockquote>
IN: <tt>vertex_index2(VertexIndexMapsecond vindex_map2)</tt>
<blockquote>
This maps each vertex to an integer in the range <tt>[0,
num_vertices(graph2)]</tt>. This is necessary for efficient storage
of the subgraphs. The type VertexIndexMapFirst must be a model of
<a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>.
<br />
<b>Default:</b> <tt>get(vertex_index, graph2)</tt>
</blockquote>
IN: <tt>edges_equivalent(EdgeEquivalencePredicate edges_equivalent)</tt>
<blockquote>
This function is used to determine if edges
between <tt>graph1</tt> and <tt>graph2</tt> are equivalent.
The <tt>EdgeEquivalencePredicate</tt> type must be a model
of <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">Binary
Predicate</a> and have argument types
of <tt>graph_traits<GraphFirst>::edge_descriptor</tt>
and <tt>graph_traits<GraphSecond>::edge_descriptor</tt>.
A return value of <tt>true</tt> indicates that the edges are
equivalent. <br />
<b>Default:</b> <tt><a href="#always_equivalent">always_equivalent</a></tt>
</blockquote>
IN: <tt>vertices_equivalent(VertexEquivalencePredicate vertices_equivalent)</tt>
<blockquote>
This function is used to determine if vertices
between <tt>graph1</tt> and <tt>graph2</tt> are equivalent.
The <tt>VertexEquivalencePredicate</tt> type must be a model
of <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">Binary
Predicate</a> and have argument types
of <tt>graph_traits<GraphFirst>::vertex_descriptor</tt>
and <tt>graph_traits<GraphSecond>::vertex_descriptor</tt>.
A return value of <tt>true</tt> indicates that the vertices are
equivalent.<br />
<b>Default:</b> <tt><a href="#always_equivalent">always_equivalent</a></tt>
</blockquote>
<h3>Related Functions</h3>
<p>
Each <tt>mcgregor_common_subgraphs_*</tt> function below takes
the same parameters as <tt>mcgregor_common_subgraphs</tt>.
</p>
<tt>mcgregor_common_subgraphs_unique(...);</tt>
<blockquote>
Keeps an internal cache of all discovered subgraphs and
only invokes the <tt>user_callback</tt> for unique
subgraphs. Returning <tt>false</tt>
from <tt>user_callback</tt> will terminate the search as
expected.
</blockquote>
<tt>mcgregor_common_subgraphs_maximum(...);</tt>
<blockquote>
Explores the <em>entire</em> search space and invokes
the <tt>user_callback</tt> afterward with each of the largest
discovered subgraphs. Returning <tt>false</tt> from
the <tt>user_callback</tt> will <b>not</b> terminate the search
because it is invoked after the search has been completed.
</blockquote>
<tt>mcgregor_common_subgraphs_maximum_unique(...);</tt>
<blockquote>
Explores the <em>entire</em> search space and invokes
the <tt>user_callback</tt> afterward with each of the largest,
unique discovered subgraphs. Returning <tt>false</tt> from
the <tt>user_callback</tt> will <b>not</b> terminate the search
because it is invoked after the search has been completed.
</blockquote>
<h3>Utility Functions/Structs</h3>
<tt id="make_property_map_equivalent">
property_map_equivalent<PropertyMapFirst, PropertyMapSecond><br />
make_property_map_equivalent(const PropertyMapFirst property_map1, const PropertyMapSecond property_map2);
</tt>
<blockquote>
Returns a binary predicate function object
(<tt>property_map_equivalent<PropertyMapFirst,
PropertyMapSecond></tt>) that compares vertices or edges
between graphs using property maps. If, for
example, <tt>vertex1</tt> and <tt>vertex2</tt> are the two
parameters given when the function object is invoked,
the <tt>operator()</tt> is effectively:
<tt>return (get(m_property_map1, vertex1) == get(m_property_map2, vertex2));</tt>
</blockquote>
<tt id="always_equivalent">struct always_equivalent</tt>
<blockquote>
A binary function object that returns true for any pair of items.
</blockquote>
<tt>
void fill_membership_map<GraphSecond><br />
(const GraphFirst& graph1, const CorrespondenceMapFirstToSecond correspondence_map_1_to_2, MembershipMapFirst membership_map1);
</tt>
<blockquote>
Takes a subgraph (represented as a correspondence map) and fills
the vertex membership map (vertex -> bool) (<tt>true</tt> means
the vertex is present in the subgraph).
<tt>MembershipMapFirst</tt> must
model <a href="../../property_map/doc/WritablePropertyMap.html">Writable
Property Map</a>.
</blockquote>
<tt>
typename membership_filtered_graph_traits<Graph, MembershipMap>::graph_type<br />
make_membership_filtered_graph(const Graph& graph, MembershipMap& membership_map);
</tt>
<blockquote>
Creates a <a href="filtered_graph.html">Filtered Graph</a> from
a subgraph, represented here as a vertex membership map (vertex
-> bool where a value of <tt>true</tt> means that the vertex is
present in the subgraph). All edges between the included
vertices are preserved. See the example section for details.
</blockquote>
<h3>Complexity</h3>
<p>
The time complexity for searching the entire space is <em>O(V1 *
V2)</em> where V1 is number of vertices in the first graph and
V2 is the number of vertices in the second graph.
</p>
<h3>Examples</h3>
<p>
Before calling any of the <tt>mcregor_common_subgraphs</tt>
algorithms, you must create a function object to act as a callback:
</p>
<pre>
template <typename GraphFirst,
typename GraphSecond>
struct print_callback {
print_callback(const GraphFirst& graph1,
const GraphSecond& graph2) :
m_graph1(graph1), m_graph2(graph2) { }
template <typename CorrespondenceMapFirstToSecond,
typename CorrespondenceMapSecondToFirst>
bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
typename graph_traits<GraphFirst>::vertices_size_type subgraph_size) {
<em class="comment">// Print out correspondences between vertices</em>
BGL_FORALL_VERTICES_T(vertex1, m_graph1, GraphFirst) {
<em class="comment">// Skip unmapped vertices</em>
if (get(correspondence_map_1_to_2, vertex1) != graph_traits<GraphSecond>::null_vertex()) {
std::cout << vertex1 << " <-> " << get(correspondence_map_1_to_2, vertex1) << std::endl;
}
}
std::cout << "---" << std::endl;
return (true);
}
private:
const GraphFirst& m_graph1;
const GraphSecond& m_graph2;
};
<em class="comment">// Assuming the graph types GraphFirst and GraphSecond have already been defined</em>
GraphFirst graph1;
GraphSecond graph2;
print_callback<GraphFirst, GraphSecond> my_callback(graph1, graph2);
</pre>
<h4>Example 1</h4>
<p>
If all the vertices and edges in your graph are identical, you
can start enumerating subgraphs immediately:
</p>
<pre>
<em class="comment">// Print out all connected common subgraphs between graph1 and graph2.
// All vertices and edges are assumed to be equivalent and both graph1 and graph2
// have implicit vertex index properties.</em>
mcgregor_common_subgraphs(graph1, graph2, true, my_callback);
</pre>
<h4>Example 2</h4>
<p>
If the vertices and edges of your graphs can be differentiated
with property maps, you can use
the <tt>make_property_map_equivalent</tt> function to create a
binary predicate for vertex or edge equivalence:
</p>
<pre>
<em class="comment">// Assume both graphs were defined with implicit vertex name,
// edge name, and vertex index properties</em>
property_map<GraphFirst, vertex_name_t> vname_map1 = get(vertex_name, graph1);
property_map<GraphSecond, vertex_name_t> vname_map1 = get(vertex_name, graph2);
property_map<GraphFirst, edge_name_t> ename_map1 = get(edge_name, graph1);
property_map<GraphSecond, edge_name_t> ename_map1 = get(edge_name, graph2);
<em class="comment">// Print out all connected common subgraphs between graph1 and graph2.</em>
mcgregor_common_subgraphs(graph1, graph2, true, my_callback,
edges_equivalent(make_property_map_equivalent(ename_map1, ename_map2)).
vertices_equivalent(make_property_map_equivalent(vname_map1, vname_map2)));
</pre>
<h4>Example 3</h4>
<p>
There are some helper functions that can be used to obtain a
filtered graph from the correspondence maps given in your
callback:
</p>
<pre>
<em class="comment">// Assuming we're inside the operator() of the callback with a member variable m_graph1 representing the first graph passed to mcgregor_common_subgraphs.
// ...</em>
<em class="comment">// Step 1: Transform a correspondence map into a membership map. Any vertex -> bool property map will work</em>
typedef shared_array_property_map<bool, VertexIndexMap> MembershipMap;
MembershipMap membership_map1(num_vertices(m_graph1), get(vertex_index, m_graph1));
<em class="comment">// Fill the membership map for m_graph1. GraphSecond is the type of the second graph given to mcgregor_common_subgraphs.</em>
fill_membership_map<GraphSecond>(m_graph1, correspondence_map_1_to_2, membership_map1);
<em class="comment">// Step 2: Use the membership map from Step 1 to obtain a filtered graph</em>
typedef typename membership_filtered_graph_traits<GraphFirst, MembershipMap>::graph_type
MembershipFilteredGraph;
MembershipFilteredGraph subgraph1 = make_membership_filtered_graph(m_graph1, membership_map1);
<em class="comment">// The filtered graph can be used like a regular BGL graph...</em>
BGL_FORALL_VERTICES_T(vertex1, subgraph1, MembershipFilteredGraph) {
std::cout << vertex1 << " is present in the subgraph of graph1" << std::endl;
}
</pre>
<h3>Notes</h3>
<p>
<a name="1">[1]</a>
For <tt>mcgregor_common_subgraphs_maximum</tt>
and <tt>mcgregor_common_subgraphs_maximum_unique</tt> the entire
search space is always explored, so the return value of the
callback has no effect.
</p>
<hr />
Copyright © 2009 Trustees of Indiana University
</body>
</html>
