| <!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> |
