[ceph.git] / ceph / src / boost / libs / graph / doc / mcgregor_common_subgraphs.html

<!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 &lt;typename GraphFirst,
          typename GraphSecond,
          typename SubGraphCallback,
          typename Param,
          typename Tag,
          typename Rest&gt;
  void mcgregor_common_subgraphs
  (const GraphFirst&amp; graph1,
   const GraphSecond&amp; 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 &lt;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&gt;
  void mcgregor_common_subgraphs
  (const GraphFirst&amp; graph1,
   const GraphSecond&amp; 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&amp; 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&amp; 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 &lt;typename CorrespondenceMapFirstToSecond,
          typename CorrespondenceMapSecondToFirst&gt;
bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
                CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
                typename graph_traits&lt;GraphFirst&gt;::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&lt;GraphSecond&gt;::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&lt;GraphFirst&gt;::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&lt;GraphFirst&gt;::edge_descriptor</tt>
      and <tt>graph_traits&lt;GraphSecond&gt;::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&lt;GraphFirst&gt;::vertex_descriptor</tt>
      and <tt>graph_traits&lt;GraphSecond&gt;::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&lt;PropertyMapFirst, PropertyMapSecond&gt;<br />
&nbsp;&nbsp;make_property_map_equivalent(const PropertyMapFirst property_map1, const PropertyMapSecond property_map2);
    </tt>
    <blockquote>
      Returns a binary predicate function object
      (<tt>property_map_equivalent&lt;PropertyMapFirst,
      PropertyMapSecond&gt;</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&lt;GraphSecond&gt;<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&lt;Graph, MembershipMap&gt;::graph_type<br />
&nbsp;&nbsp;make_membership_filtered_graph(const Graph&amp; graph, MembershipMap&amp; 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 &lt;typename GraphFirst,
          typename GraphSecond&gt;
struct print_callback {

  print_callback(const GraphFirst&amp; graph1,
                 const GraphSecond&amp; graph2) :
    m_graph1(graph1), m_graph2(graph2) { }

template &lt;typename CorrespondenceMapFirstToSecond,
          typename CorrespondenceMapSecondToFirst&gt;
  bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
                  CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
                  typename graph_traits&lt;GraphFirst&gt;::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&lt;GraphSecond&gt;::null_vertex()) {
        std::cout << vertex1 << " <-> " << get(correspondence_map_1_to_2, vertex1) << std::endl;
      }

    }

    std::cout << "---" << std::endl;

    return (true);
  }

  private:
    const GraphFirst&amp; m_graph1;
    const GraphSecond&amp; m_graph2;

};

<em class="comment">// Assuming the graph types GraphFirst and GraphSecond have already been defined</em>
GraphFirst graph1;
GraphSecond graph2;

print_callback&lt;GraphFirst, GraphSecond&gt; 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&lt;GraphFirst, vertex_name_t&gt; vname_map1 = get(vertex_name, graph1);
property_map&lt;GraphSecond, vertex_name_t&gt; vname_map1 = get(vertex_name, graph2);

property_map&lt;GraphFirst, edge_name_t&gt; ename_map1 = get(edge_name, graph1);
property_map&lt;GraphSecond, edge_name_t&gt; 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&lt;GraphSecond&gt;(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&lt;GraphFirst, MembershipMap&gt;::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 &copy; 2009 Trustees of Indiana University

  </body>
</html>
Commit	Line	Data
7c673cae FG	1	<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN">
	2	<!--
	3	Copyright (c) Michael Hansen 2009
	4
	5	Distributed under the Boost Software License, Version 1.0.
	6	(See accompanying file LICENSE_1_0.txt or copy at
	7	http://www.boost.org/LICENSE_1_0.txt)
	8	-->
	9	<html>
	10	<head>
	11	<title>Boost Graph Library: McGregor Common Subgraphs</title>
	12	<style type="text/css">
	13	<!--
	14	body {
	15	color: black;
	16	background-color: white;
	17	}
	18
	19	.comment {
	20	color: #333333;
	21	}
	22
	23	a {
	24	color: blue;
	25	}
	26
	27	a:visited {
	28	color: #551A8B;
	29	}
	30	-->
	31	</style>
	32	</head>
	33	<body>
	34	<img src="../../../boost.png" alt="C++ Boost" width="277" height="86" />
	35	<br />
	36	<h1>
	37	<tt>mcgregor_common_subgraphs</tt>
	38	</h1>
	39	<pre>
	40	<em class="comment">// named parameter version</em>
	41	template <typename GraphFirst,
	42	typename GraphSecond,
	43	typename SubGraphCallback,
	44	typename Param,
	45	typename Tag,
	46	typename Rest>
	47	void mcgregor_common_subgraphs
	48	(const GraphFirst& graph1,
	49	const GraphSecond& graph2,
	50	SubGraphCallback user_callback,
	51	bool only_connected_subgraphs,
	52	const bgl_named_params<Param, Tag, Rest>& params);
	53
	54	<em class="comment">// non-named parameter version</em>
	55	template <typename GraphFirst,
	56	typename GraphSecond,
	57	typename <a href="../../property_map/doc/ReadablePropertyMap.html">VertexIndexMapFirst</a>,
	58	typename <a href="../../property_map/doc/ReadablePropertyMap.html">VertexIndexMapSecond</a>,
	59	typename <a href="http://www.sgi.com/tech/stl/BinaryFunction.html">EdgeEquivalencePredicate</a>,
	60	typename <a href="http://www.sgi.com/tech/stl/BinaryFunction.html">VertexEquivalencePredicate</a>,
	61	typename SubGraphCallback>
	62	void mcgregor_common_subgraphs
	63	(const GraphFirst& graph1,
	64	const GraphSecond& graph2,
65	const VertexIndexMapFirst vindex_map1,
66	const VertexIndexMapSecond vindex_map2,
67	EdgeEquivalencePredicate edges_equivalent,
68	VertexEquivalencePredicate vertices_equivalent,
69	bool only_connected_subgraphs,
70	SubGraphCallback user_callback);
71	</pre>
72
73	<p>
74	This algorithm finds all common subgraphs
75	between <tt>graph1</tt> and <tt>graph2</tt> and outputs them
76	to <tt>user_callback</tt>. The <tt>edges_equivalent</tt>
77	and <tt>vertices_equivalent</tt> predicates are used to
78	determine edges and vertex equivalence between the two graphs.
79	To use property maps for equivalence, look at
80	the <tt><a href="#make_property_map_equivalent">make_property_map_equivalent</a></tt>
81	function. By
82	default, <tt><a href="#always_equivalent">always_equivalent</a></tt>
83	is used, which returns true for any pair of edges or vertices.
84	</p>
85	<p>
86	McGregor's algorithm does a depth-first search on the space of
87	possible common subgraphs. At each level, every unvisited pair
88	of vertices from <tt>graph1</tt> and <tt>graph2</tt> are checked
89	to see if they can extend the current subgraph. This is done in
90	three steps (assume <tt>vertex1</tt> is
91	from <tt>graph1</tt> and <tt>vertex2</tt> is
92	from <tt>graph2</tt>):
93	<ol>
94	<li>
95	Verify that the <tt>vertex1</tt> and <tt>vertex2</tt> are
96	equivalent using the <tt>vertices_equivalent</tt> predicate.
97	</li>
98	<li>
99	For every vertex pair
100	(<tt>existing_vertex1</tt>, <tt>existing_vertex2</tt>) in
101	the current subgraph, ensure that any edges
102	between <tt>vertex1</tt> and <tt>existing_vertex1</tt>
103	in <tt>graph1</tt> and between <tt>vertex2</tt>
104	and <tt>existing_vertex2</tt> in <tt>graph2</tt> match
105	(i.e. either both exist of both don't exist). If both edges
106	exist, they are checked for equivalence using
107	the <tt>edges_equivalent</tt> predicate.
108	</li>
109	<li>
110	Lastly (and optionally), make sure that the new subgraph
111	vertex has at least one edge connecting it to the existing
112	subgraph. When the <tt>only_connected_subgraphs</tt>
113	parameter is false, this step is skipped.
114	</li>
115	</ol>
116	</p>
117
118	<h3>Where Defined</h3>
119	<a href="../../../boost/graph/mcgregor_common_subgraphs.hpp"><tt>boost/graph/mcgregor_common_subgraphs.hpp</tt></a>
120	<p>
121	All functions are defined in the boost namespace.
122	</p>
123
124	<h3>Parameters</h3>
125
126	IN: <tt>const GraphFirst& graph1</tt>
127	<blockquote>
128	The first graph of the pair to be searched. The
129	type <tt>GraphFirst</tt> must be a model of
130	<a href="./VertexListGraph.html">Vertex List Graph</a>
131	and <a href="./IncidenceGraph.html">Incidence Graph</a>. All
132	parameters with a "<tt>1</tt>"
133	(i.e. <tt>vindex_map1</tt>, <tt>correspondence_map_1_to_2</tt>)
134	use this graph's vertices as keys.
135	</blockquote>
136
137	IN: <tt>const GraphSecond& graph2</tt>
138	<blockquote>
139	The second graph of the pair to be searched. The
140	type <tt>Graphsecond</tt> must be a model of
141	<a href="./VertexListGraph.html">Vertex List Graph</a>
142	and <a href="./IncidenceGraph.html">Incidence Graph</a>. All
143	parameters with a "<tt>2</tt>"
144	(i.e. <tt>vindex_map2</tt>, <tt>correspondence_map_2_to_1</tt>)
145	use this graph's vertices as keys.
146	</blockquote>
147
148	IN: <tt>bool only_connected_subgraphs</tt>
149	<blockquote>
150	If <tt>true</tt>, subgraphs are expanded only when matching vertices
151	have at least one edge connecting them to the existing subgraph.
152	</blockquote>
153
154	OUT: <tt>SubGraphCallback user_callback</tt>
155	<blockquote>
156	A function object that will be invoked when a subgraph has been discovered. The operator() must have the following form:
157	<pre>
158	template <typename CorrespondenceMapFirstToSecond,
159	typename CorrespondenceMapSecondToFirst>
160	bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
161	CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
162	typename graph_traits<GraphFirst>::vertices_size_type subgraph_size);
163	</pre>
164	Both the <tt>CorrespondenceMapFirstToSecond</tt>
165	and <tt>CorresondenceMapSecondToFirst</tt> types are models
166	of <a href="../../property_map/doc/ReadablePropertyMap.html">Readable
167	Property Map</a> and map equivalent vertices across the two
168	graphs given to <tt>mcgregor_common_subgraphs</tt>. For
169	example, if <tt>vertex1</tt> is
170	from <tt>graph1</tt>, <tt>vertex2</tt> is from <tt>graph2</tt>,
171	and the vertices can be considered equivalent in the subgraph,
172	then <tt>get(correspondence_map_1_to_2, vertex1)</tt> will
173	be <tt>vertex2</tt> and <tt>get(correspondence_map_2_to_1,
174	vertex2)</tt> will be <tt>vertex1</tt>. If any vertex,
175	say <tt>vertex1</tt> in <tt>graph1</tt>, doesn't match a vertex
176	in the other graph (<tt>graph2</tt> in this example),
177	then <tt>get(correspondence_map_1_to_2, vertex1)</tt> will
178	be <tt>graph_traits<GraphSecond>::null_vertex()</tt>.
179	Likewise for any un-matched vertices from <tt>graph2</tt>,
180	<tt>get(correspondence_map_2_to_1, vertex2)</tt> will
181	be <tt>graph_traits<GraphFirst>::null_vertex()</tt>.
182	<br /><br /> The <tt>subgraph_size</tt> parameter is the number
183	of vertices in the subgraph, or the number of matched vertex
184	pairs contained in the correspondence maps. This can be used to
185	quickly filter out subgraphs whose sizes do not fall within the
186	desired range.<br /><br />Returning <tt>false</tt> from the
187	callback will abort the search immediately. Otherwise, the
188	entire search space will be explored [<a href="#1">1</a>].
189	</blockquote>
190
191	<h3>Named Parameters</h3>
192
193	IN: <tt>vertex_index1(VertexIndexMapFirst vindex_map1)</tt>
194	<blockquote>
195	This maps each vertex to an integer in the range <tt>[0,
196	num_vertices(graph1)]</tt>. This is necessary for efficient storage
197	of the subgraphs. The type VertexIndexMapFirst must be a model of
198	<a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>.
199	<br />
200	<b>Default:</b> <tt>get(vertex_index, graph1)</tt>
201	</blockquote>
202
203	IN: <tt>vertex_index2(VertexIndexMapsecond vindex_map2)</tt>
204	<blockquote>
205	This maps each vertex to an integer in the range <tt>[0,
206	num_vertices(graph2)]</tt>. This is necessary for efficient storage
207	of the subgraphs. The type VertexIndexMapFirst must be a model of
208	<a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>.
209	<br />
210	<b>Default:</b> <tt>get(vertex_index, graph2)</tt>
211	</blockquote>
212
213	IN: <tt>edges_equivalent(EdgeEquivalencePredicate edges_equivalent)</tt>
214	<blockquote>
215	This function is used to determine if edges
216	between <tt>graph1</tt> and <tt>graph2</tt> are equivalent.
217	The <tt>EdgeEquivalencePredicate</tt> type must be a model
218	of <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">Binary
219	Predicate</a> and have argument types
220	of <tt>graph_traits<GraphFirst>::edge_descriptor</tt>
221	and <tt>graph_traits<GraphSecond>::edge_descriptor</tt>.
222	A return value of <tt>true</tt> indicates that the edges are
223	equivalent. <br />
224	<b>Default:</b> <tt><a href="#always_equivalent">always_equivalent</a></tt>
225	</blockquote>
226
227	IN: <tt>vertices_equivalent(VertexEquivalencePredicate vertices_equivalent)</tt>
228	<blockquote>
229	This function is used to determine if vertices
230	between <tt>graph1</tt> and <tt>graph2</tt> are equivalent.
231	The <tt>VertexEquivalencePredicate</tt> type must be a model
232	of <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">Binary
233	Predicate</a> and have argument types
234	of <tt>graph_traits<GraphFirst>::vertex_descriptor</tt>
235	and <tt>graph_traits<GraphSecond>::vertex_descriptor</tt>.
236	A return value of <tt>true</tt> indicates that the vertices are
237	equivalent.<br />
238	<b>Default:</b> <tt><a href="#always_equivalent">always_equivalent</a></tt>
239	</blockquote>
240
241	<h3>Related Functions</h3>
242	<p>
243	Each <tt>mcgregor_common_subgraphs_*</tt> function below takes
244	the same parameters as <tt>mcgregor_common_subgraphs</tt>.
245	</p>
246	<tt>mcgregor_common_subgraphs_unique(...);</tt>
247	<blockquote>
248	Keeps an internal cache of all discovered subgraphs and
249	only invokes the <tt>user_callback</tt> for unique
250	subgraphs. Returning <tt>false</tt>
251	from <tt>user_callback</tt> will terminate the search as
252	expected.
253	</blockquote>
254
255	<tt>mcgregor_common_subgraphs_maximum(...);</tt>
256	<blockquote>
257	Explores the <em>entire</em> search space and invokes
258	the <tt>user_callback</tt> afterward with each of the largest
259	discovered subgraphs. Returning <tt>false</tt> from
260	the <tt>user_callback</tt> will <b>not</b> terminate the search
261	because it is invoked after the search has been completed.
262	</blockquote>
263
264	<tt>mcgregor_common_subgraphs_maximum_unique(...);</tt>
265	<blockquote>
266	Explores the <em>entire</em> search space and invokes
267	the <tt>user_callback</tt> afterward with each of the largest,
268	unique discovered subgraphs. Returning <tt>false</tt> from
269	the <tt>user_callback</tt> will <b>not</b> terminate the search
270	because it is invoked after the search has been completed.
271	</blockquote>
272
273	<h3>Utility Functions/Structs</h3>
274	<tt id="make_property_map_equivalent">
275	property_map_equivalent<PropertyMapFirst, PropertyMapSecond><br />
276	make_property_map_equivalent(const PropertyMapFirst property_map1, const PropertyMapSecond property_map2);
277	</tt>
278	<blockquote>
279	Returns a binary predicate function object
280	(<tt>property_map_equivalent<PropertyMapFirst,
281	PropertyMapSecond></tt>) that compares vertices or edges
282	between graphs using property maps. If, for
283	example, <tt>vertex1</tt> and <tt>vertex2</tt> are the two
284	parameters given when the function object is invoked,
285	the <tt>operator()</tt> is effectively:
286	<tt>return (get(m_property_map1, vertex1) == get(m_property_map2, vertex2));</tt>
287	</blockquote>
288
289	<tt id="always_equivalent">struct always_equivalent</tt>
290	<blockquote>
291	A binary function object that returns true for any pair of items.
292	</blockquote>
293
294	<tt>
295	void fill_membership_map<GraphSecond><br />
296	(const GraphFirst& graph1, const CorrespondenceMapFirstToSecond correspondence_map_1_to_2, MembershipMapFirst membership_map1);
297	</tt>
298	<blockquote>
299	Takes a subgraph (represented as a correspondence map) and fills
300	the vertex membership map (vertex -> bool) (<tt>true</tt> means
301	the vertex is present in the subgraph).
302	<tt>MembershipMapFirst</tt> must
303	model <a href="../../property_map/doc/WritablePropertyMap.html">Writable
304	Property Map</a>.
305	</blockquote>
306
307	<tt>
308	typename membership_filtered_graph_traits<Graph, MembershipMap>::graph_type<br />
309	make_membership_filtered_graph(const Graph& graph, MembershipMap& membership_map);
310	</tt>
311	<blockquote>
312	Creates a <a href="filtered_graph.html">Filtered Graph</a> from
313	a subgraph, represented here as a vertex membership map (vertex
314	-> bool where a value of <tt>true</tt> means that the vertex is
315	present in the subgraph). All edges between the included
316	vertices are preserved. See the example section for details.
317	</blockquote>
318
319	<h3>Complexity</h3>
320	<p>
321	The time complexity for searching the entire space is <em>O(V1 *
322	V2)</em> where V1 is number of vertices in the first graph and
323	V2 is the number of vertices in the second graph.
324	</p>
325
326	<h3>Examples</h3>
327	<p>
328	Before calling any of the <tt>mcregor_common_subgraphs</tt>
329	algorithms, you must create a function object to act as a callback:
330	</p>
331	<pre>
332	template <typename GraphFirst,
333	typename GraphSecond>
334	struct print_callback {
335
336	print_callback(const GraphFirst& graph1,
337	const GraphSecond& graph2) :
338	m_graph1(graph1), m_graph2(graph2) { }
339
340	template <typename CorrespondenceMapFirstToSecond,
341	typename CorrespondenceMapSecondToFirst>
342	bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
343	CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
344	typename graph_traits<GraphFirst>::vertices_size_type subgraph_size) {
345
346	<em class="comment">// Print out correspondences between vertices</em>
347	BGL_FORALL_VERTICES_T(vertex1, m_graph1, GraphFirst) {
348
349	<em class="comment">// Skip unmapped vertices</em>
350	if (get(correspondence_map_1_to_2, vertex1) != graph_traits<GraphSecond>::null_vertex()) {
351	std::cout << vertex1 << " <-> " << get(correspondence_map_1_to_2, vertex1) << std::endl;
352	}
353
354	}
355
356	std::cout << "---" << std::endl;
357
358	return (true);
359	}
360
361	private:
362	const GraphFirst& m_graph1;
363	const GraphSecond& m_graph2;
364
365	};
366
367	<em class="comment">// Assuming the graph types GraphFirst and GraphSecond have already been defined</em>
368	GraphFirst graph1;
369	GraphSecond graph2;
370
371	print_callback<GraphFirst, GraphSecond> my_callback(graph1, graph2);
372	</pre>
373
374	<h4>Example 1</h4>
375	<p>
376	If all the vertices and edges in your graph are identical, you
377	can start enumerating subgraphs immediately:
378	</p>
379	<pre>
380	<em class="comment">// Print out all connected common subgraphs between graph1 and graph2.
381	// All vertices and edges are assumed to be equivalent and both graph1 and graph2
382	// have implicit vertex index properties.</em>
383	mcgregor_common_subgraphs(graph1, graph2, true, my_callback);
384	</pre>
385
386	<h4>Example 2</h4>
387	<p>
388	If the vertices and edges of your graphs can be differentiated
389	with property maps, you can use
390	the <tt>make_property_map_equivalent</tt> function to create a
391	binary predicate for vertex or edge equivalence:
392	</p>
393
394	<pre>
395	<em class="comment">// Assume both graphs were defined with implicit vertex name,
396	// edge name, and vertex index properties</em>
397	property_map<GraphFirst, vertex_name_t> vname_map1 = get(vertex_name, graph1);
398	property_map<GraphSecond, vertex_name_t> vname_map1 = get(vertex_name, graph2);
399
400	property_map<GraphFirst, edge_name_t> ename_map1 = get(edge_name, graph1);
401	property_map<GraphSecond, edge_name_t> ename_map1 = get(edge_name, graph2);
402
403	<em class="comment">// Print out all connected common subgraphs between graph1 and graph2.</em>
404	mcgregor_common_subgraphs(graph1, graph2, true, my_callback,
405	edges_equivalent(make_property_map_equivalent(ename_map1, ename_map2)).
406	vertices_equivalent(make_property_map_equivalent(vname_map1, vname_map2)));
407	</pre>
408
409	<h4>Example 3</h4>
410	<p>
411	There are some helper functions that can be used to obtain a
412	filtered graph from the correspondence maps given in your
413	callback:
414	</p>
415	<pre>
416	<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.
417	// ...</em>
418
419	<em class="comment">// Step 1: Transform a correspondence map into a membership map. Any vertex -> bool property map will work</em>
420	typedef shared_array_property_map<bool, VertexIndexMap> MembershipMap;
421	MembershipMap membership_map1(num_vertices(m_graph1), get(vertex_index, m_graph1));
422
423	<em class="comment">// Fill the membership map for m_graph1. GraphSecond is the type of the second graph given to mcgregor_common_subgraphs.</em>
424	fill_membership_map<GraphSecond>(m_graph1, correspondence_map_1_to_2, membership_map1);
425
426	<em class="comment">// Step 2: Use the membership map from Step 1 to obtain a filtered graph</em>
427	typedef typename membership_filtered_graph_traits<GraphFirst, MembershipMap>::graph_type
428	MembershipFilteredGraph;
429
430	MembershipFilteredGraph subgraph1 = make_membership_filtered_graph(m_graph1, membership_map1);
431
432	<em class="comment">// The filtered graph can be used like a regular BGL graph...</em>
433	BGL_FORALL_VERTICES_T(vertex1, subgraph1, MembershipFilteredGraph) {
434	std::cout << vertex1 << " is present in the subgraph of graph1" << std::endl;
435	}
436	</pre>
437
438	<h3>Notes</h3>
439	<p>
440	<a name="1">[1]</a>
441	For <tt>mcgregor_common_subgraphs_maximum</tt>
442	and <tt>mcgregor_common_subgraphs_maximum_unique</tt> the entire
443	search space is always explored, so the return value of the
444	callback has no effect.
445	</p>
446
447	<hr />
448	Copyright © 2009 Trustees of Indiana University
449
450	</body>
451	</html>