Subject: [Boost-commit] svn:boost r54341 - trunk/libs/graph/doc
From: jewillco_at_[hidden]
Date: 2009-06-25 12:29:58
Author: jewillco
Date: 2009-06-25 12:29:57 EDT (Thu, 25 Jun 2009)
New Revision: 54341
URL: http://svn.boost.org/trac/boost/changeset/54341
Log:
Added documentation from Michael Hansen; refs #3134
Added:
trunk/libs/graph/doc/mcgregor_common_subgraphs.html (contents, props changed)
Added: trunk/libs/graph/doc/mcgregor_common_subgraphs.html
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/mcgregor_common_subgraphs.html 2009-06-25 12:29:57 EDT (Thu, 25 Jun 2009)
@@ -0,0 +1,446 @@
+<!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 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)
+ </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>make_property_map_equivalent</tt>
+ function. By
+ default, <tt>always_equivalent</tt>
+ tt 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>
+ boost/graph/mcgregor_common_subgraphs.hpp
+
+ <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
+ Vertex List Graph
+ and Incidence Graph. 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
+ Vertex List Graph
+ and Incidence Graph. 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 [1].
+ </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
+ Readable Property Map.
+ <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
+ Readable Property Map.
+ <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>always_equivalent</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>always_equivalent</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> afterwards 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> afterwards 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 Filtered Graph 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 is <em>O(?)</em>.
+ </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>
+ <b>NOTE</b>: 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>