123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451 |
- <!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.boost.org/sgi/stl/BinaryFunction.html">EdgeEquivalencePredicate</a>,
- typename <a href="http://www.boost.org/sgi/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.boost.org/sgi/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.boost.org/sgi/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>
|