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