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> 41template <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> 55template <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.boost.org/sgi/stl/BinaryFunction.html">EdgeEquivalencePredicate</a>, 60 typename <a href="http://www.boost.org/sgi/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> 158template <typename CorrespondenceMapFirstToSecond, 159 typename CorrespondenceMapSecondToFirst> 160bool 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.boost.org/sgi/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.boost.org/sgi/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"> 275property_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> 295void 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> 308typename 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> 332template <typename GraphFirst, 333 typename GraphSecond> 334struct print_callback { 335 336 print_callback(const GraphFirst& graph1, 337 const GraphSecond& graph2) : 338 m_graph1(graph1), m_graph2(graph2) { } 339 340template <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> 368GraphFirst graph1; 369GraphSecond graph2; 370 371print_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> 383mcgregor_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> 397property_map<GraphFirst, vertex_name_t> vname_map1 = get(vertex_name, graph1); 398property_map<GraphSecond, vertex_name_t> vname_map1 = get(vertex_name, graph2); 399 400property_map<GraphFirst, edge_name_t> ename_map1 = get(edge_name, graph1); 401property_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> 404mcgregor_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> 420typedef shared_array_property_map<bool, VertexIndexMap> MembershipMap; 421MembershipMap 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> 424fill_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> 427typedef typename membership_filtered_graph_traits<GraphFirst, MembershipMap>::graph_type 428 MembershipFilteredGraph; 429 430MembershipFilteredGraph 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> 433BGL_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> 452
