]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" |
2 | "http://www.w3.org/TR/html4/strict.dtd"> | |
3 | <!-- | |
4 | Copyright (C) Flavio De Lorenzi 2012 | |
5 | ||
6 | Distributed under the Boost Software License, Version 1.0. | |
7 | (See accompanying file LICENSE_1_0.txt or copy at | |
8 | http://www.boost.org/LICENSE_1_0.txt) | |
9 | --> | |
10 | <html> | |
11 | <head> | |
12 | <meta http-equiv="content-type" content="text/html; charset=iso-8859-15"> | |
13 | <title>Boost Graph Library: VF2 (Sub)Graph Isomorphism</title> | |
14 | <style type="text/css"> | |
15 | <!-- | |
16 | body { | |
17 | color: black; | |
18 | background-color: white; | |
19 | } | |
20 | ||
21 | .comment { | |
22 | color: #333333; | |
23 | } | |
24 | ||
25 | a { | |
26 | color: blue; | |
27 | } | |
28 | ||
29 | a:visited { | |
30 | color: #551A8B; | |
31 | } | |
32 | --> | |
33 | </style> | |
34 | </head> | |
35 | <body> | |
36 | <p><img src="../../../boost.png" alt="C++ Boost" width="277" height="86"></p> | |
37 | <h1> | |
38 | <tt>vf2_subgraph_iso</tt> | |
39 | </h1> | |
40 | <pre> | |
41 | <em class="comment">// All defaults interface</em> | |
42 | template <typename GraphSmall, | |
43 | typename GraphLarge, | |
44 | typename SubGraphIsoMapCallback> | |
45 | bool vf2_subgraph_iso(const GraphSmall& graph_small, | |
46 | const GraphLarge& graph_large, | |
47 | SubGraphIsoMapCallback user_callback) | |
48 | ||
49 | ||
50 | <em class="comment">// Named parameter version</em> | |
51 | template <typename GraphSmall, | |
52 | typename GraphLarge, | |
53 | typename VertexOrderSmall, | |
54 | typename SubGraphIsoMapCallback, | |
55 | typename Param, | |
56 | typename Tag, | |
57 | typename Rest> | |
58 | bool vf2_subgraph_iso(const GraphSmall& graph_small, | |
59 | const GraphLarge& graph_large, | |
60 | SubGraphIsoMapCallback user_callback, | |
61 | const VertexOrderSmall& vertex_order_small, | |
62 | const bgl_named_params<Param, Tag, Rest>& params) | |
63 | ||
64 | ||
65 | <em class="comment">// Non-named parameter version</em> | |
66 | template <typename GraphSmall, | |
67 | typename GraphLarge, | |
68 | typename <a href="../../property_map/doc/ReadablePropertyMap.html">IndexMapSmall</a>, | |
69 | typename <a href="../../property_map/doc/ReadablePropertyMap.html">IndexMapLarge</a>, | |
70 | typename VertexOrderSmall, | |
71 | typename <a href="http://www.sgi.com/tech/stl/BinaryFunction.html">EdgeEquivalencePredicate</a>, | |
72 | typename <a href="http://www.sgi.com/tech/stl/BinaryFunction.html">VertexEquivalencePredicate</a>, | |
73 | typename SubGraphIsoMapCallback> | |
74 | bool vf2_subgraph_iso(const GraphSmall& graph_small, | |
75 | const GraphLarge& graph_large, | |
76 | SubGraphIsoMapCallback user_callback, | |
77 | IndexMapSmall index_map_small, | |
78 | IndexMapLarge index_map_large, | |
79 | const VertexOrderSmall& vertex_order_small, | |
80 | EdgeEquivalencePredicate edge_comp, | |
81 | VertexEquivalencePredicate vertex_comp) | |
82 | </pre> | |
83 | <p> | |
84 | An isomorphism between two graphs <em>G<sub>1</sub>=(V<sub>1</sub>, E<sub>1</sub>)</em> | |
85 | and <em>G<sub>2</sub>=(V<sub>2</sub>, E<sub>2</sub>)</em> is a | |
86 | bijective mapping <em>M</em> of the vertices of one graph to vertices of the other | |
87 | graph that preserves the edge structure of the graphs. <em>M</em> is said to be a | |
88 | graph-subgraph isomorphism if and only if <em>M</em> is an isomorphism between | |
89 | <em>G<sub>1</sub></em> and a subgraph of <em>G<sub>2</sub></em>. | |
90 | An induced subgraph of a graph <em>G = (V, E)</em> is a normal subgraph | |
91 | <em>G' = (V', E')</em> with the extra condition that all edges of <em>G</em> | |
92 | which have both endpoints in <em>V'</em> are in <em>E'</em>. | |
93 | </p> | |
94 | ||
95 | <p> | |
96 | This function finds all induced subgraph isomorphisms between | |
97 | graphs <tt>graph_small</tt> and <tt>graph_large</tt> and outputs them to | |
98 | <tt>user_callback</tt>. It continues until <tt>user_callback</tt> | |
99 | returns false or the search space has been fully explored. <tt>vf2_subgraph_iso</tt> | |
100 | returns true if a graph-subgraph isomorphism exists and false otherwise. | |
101 | <tt>EdgeEquivalencePredicate</tt> and | |
102 | <tt>VertexEquivalencePredicate</tt> predicates are used to test whether | |
103 | edges and vertices are equivalent. To use property maps for equivalence, | |
104 | see | |
105 | <tt><a href="./mcgregor_common_subgraphs.html#make_property_map_equivalent"> | |
106 | make_property_map_equivalent</a></tt> | |
107 | function. By default <tt><a href="./mcgregor_common_subgraphs.html#always_equivalent"> | |
108 | always_equivalent</a></tt> is used, which returns | |
109 | true for any pair of vertices or edges. | |
110 | </p> | |
111 | <p> | |
112 | The current implementation is based on the <em>VF2</em> algorithm, | |
113 | introduced by Cordella et al. An in-depth description of the algorithm is | |
114 | given in [<a href="#cordella2001">1</a>] and [<a href="#cordella2004">2</a>] | |
115 | and references therein. The original code by P. Foggia and collaborators can | |
116 | be found at [<a href="#foggia_etal">3</a>]. In brief, the process of | |
117 | finding a mapping between the two graphs <em>G<sub>1</sub></em> and | |
118 | <em>G<sub>2</sub></em> determines the isomorphism mapping <em>M</em>, | |
119 | which associates vertices <em>G<sub>1</sub></em> with vertices of | |
120 | <em>G<sub>2</sub></em> and vice versa. It can be described by means of a | |
121 | state space representation which is created by the algorithm | |
122 | while exploring the search graph in depth-first fashion. | |
123 | Each state <em>s</em> of the matching process | |
124 | can be associated with a partial mapping <em>M(s)</em>. At each level, | |
125 | the algorithm computes the set of the vertex pairs that are candidates to | |
126 | be added to the current state <em>s</em>. If a pair of vertices | |
127 | (<em>v, w</em>) is feasible, the mapping is extended and the associated | |
128 | successor state <em>s'</em> is computed. | |
129 | The whole procedure is then repeated for state <em>s'</em>. | |
130 | </p> | |
131 | ||
132 | <h3>Where Defined</h3> | |
133 | <p> | |
134 | <a href="../../../boost/graph/vf2_sub_graph_iso.hpp"> | |
135 | <tt>boost/graph/vf2_sub_graph_iso.hpp</tt></a><br> | |
136 | All functions are defined in the boost namespace. | |
137 | </p> | |
138 | ||
139 | <h3>Parameters</h3> | |
140 | ||
141 | <p>IN: <tt>const GraphSmall& graph_small</tt></p> | |
142 | <blockquote> | |
143 | <p> | |
144 | The (first) smaller graph (fewer vertices) of the pair to be tested for | |
145 | isomorphism. The type <tt>GraphSmall</tt> must be a | |
146 | model of | |
147 | <a href="./VertexListGraph.html">Vertex List Graph</a>, | |
148 | <a href="./EdgeListGraph.html">Edge List Graph</a>, | |
149 | <a href="./BidirectionalGraph.html">Bidirectional Graph</a> and | |
150 | <a href="./AdjacencyMatrix.html">Adjacency Matrix</a>. | |
151 | The edge descriptors <tt>graph_traits<GraphSmall>::edge_descriptor</tt> | |
152 | must be <a href="http://www.sgi.com/tech/stl/LessThanComparable.html"> | |
153 | LessThan Comparable</a>, cf. also the remark <a href="#notes">below</a>. | |
154 | </p> | |
155 | </blockquote> | |
156 | ||
157 | <p>IN: <tt>const GraphLarge& graph_large</tt></p> | |
158 | <blockquote> | |
159 | <p> | |
160 | The (second) larger graph to be tested. | |
161 | Type <tt>GraphLarge</tt> must be a model of | |
162 | <a href="./VertexListGraph.html">Vertex List Graph</a>, | |
163 | <a href="./EdgeListGraph.html">Edge List Graph</a>, | |
164 | <a href="./BidirectionalGraph.html">Bidirectional Graph</a> and | |
165 | <a href="./AdjacencyMatrix.html">Adjacency Matrix</a>. | |
166 | The edge descriptors <tt>graph_traits<GraphLarge>::edge_descriptor</tt> | |
167 | must be <a href="http://www.sgi.com/tech/stl/LessThanComparable.html"> | |
168 | LessThan Comparable</a>, cf. also the remark <a href="#notes">below</a>. | |
169 | </p> | |
170 | </blockquote> | |
171 | ||
172 | <p>OUT: <tt>SubGraphIsoMapCallback user_callback</tt></p> | |
173 | <blockquote> | |
174 | <p> | |
175 | A function object to be called when a graph-subgraph isomorphism has been discovered. The | |
176 | <tt>operator()</tt> must have following form: | |
177 | </p> | |
178 | <pre> | |
179 | template <typename CorrespondenceMap1To2, | |
180 | typename CorrespondenceMap2To1> | |
181 | bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1 g) const | |
182 | </pre> | |
183 | <p> | |
184 | Both the <tt>CorrespondenceMap1To2</tt> | |
185 | and <tt>CorresondenceMap2To1</tt> types are models | |
186 | of <a href="../../property_map/doc/ReadablePropertyMap.html">Readable | |
187 | Property Map</a> and map equivalent vertices across the two | |
188 | graphs given to <tt>vf2_subgraph_iso</tt> (or <tt>vf2_graph_iso</tt> or | |
189 | <tt>vf2_subgraph_mono</tt>). For instance, if <tt>v</tt> is | |
190 | from <tt>graph_small</tt>, <tt>w</tt> is from <tt>graph_large</tt>, | |
191 | and the vertices can be considered equivalent, | |
192 | then <tt>get(f, v)</tt> will be <tt>w</tt> and <tt>get(g, w)</tt> | |
193 | will be <tt>v</tt>. If any vertex, say <tt>v</tt> in <tt>graph_small</tt>, | |
194 | does not match a vertex in <tt>graph_large</tt> , | |
195 | then <tt>get(f, v)</tt> will be <tt>graph_traits<GraphLarge>::null_vertex()</tt>. | |
196 | Likewise for any unmatched vertices from <tt>graph_large</tt>, | |
197 | <tt>get(g, w)</tt> will be <tt>graph_traits<GraphSmall>::null_vertex()</tt>. | |
198 | ||
199 | Returning false from the callback will abort the search immediately. Otherwise, | |
200 | the entire search space will be explored. A "default" print callback | |
201 | is provided as a <a href="#vf2_callback">utility function</a>. | |
202 | </p> | |
203 | </blockquote> | |
204 | ||
205 | <p>IN: <tt>const VertexOrderSmall& vertex_order_small</tt></p> | |
206 | <blockquote> | |
207 | <p> | |
208 | The ordered vertices of the smaller (first) graph <tt>graph_small</tt>. | |
209 | During the matching process the vertices are examined in the order given by | |
210 | <tt>vertex_order_small</tt>. Type <tt>VertexOrderSmall</tt> must be a model | |
211 | of <a href="http://www.sgi.com/tech/stl/Container.html">ContainerConcept</a> | |
212 | with value type | |
213 | <tt>graph_traits<GraphSmall>::vertex_descriptor</tt>. | |
214 | <br> | |
215 | <b>Default</b> The vertices are ordered by multiplicity of | |
216 | in/out degrees. | |
217 | </p> | |
218 | </blockquote> | |
219 | ||
220 | <h3>Named Parameters</h3> | |
221 | ||
222 | <p>IN: <tt>vertex_index1(IndexMapSmall index_map_small)</tt></p> | |
223 | <blockquote> | |
224 | <p> | |
225 | This maps each vertex to an integer in the range <tt>[0, num_vertices(graph_small))</tt>. | |
226 | Type <tt>IndexMapSmall</tt> must be a model of | |
227 | <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. | |
228 | <br> | |
229 | <b>Default:</b> <tt>get(vertex_index, graph_small)</tt> | |
230 | </p> | |
231 | </blockquote> | |
232 | ||
233 | <p>IN: <tt>vertex_index2(IndexMapLarge index_map_large)</tt></p> | |
234 | <blockquote> | |
235 | <p> | |
236 | This maps each vertex to an integer in the range <tt>[0, num_vertices(graph_large))</tt>. | |
237 | Type <tt>IndexMapLarge</tt> must be a model of | |
238 | <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. | |
239 | <br> | |
240 | <b>Default:</b> <tt>get(vertex_index, graph_large)</tt> | |
241 | </p> | |
242 | </blockquote> | |
243 | ||
244 | <p>IN: <tt>edges_equivalent(EdgeEquivalencePredicate edge_comp)</tt></p> | |
245 | <blockquote> | |
246 | <p> | |
247 | This function object is used to determine if edges between the two graphs | |
248 | <tt>graph_small</tt> and <tt>graph_large</tt> are equivalent. | |
249 | Type <tt>EdgeEquivalencePredicate</tt> must be a model of | |
250 | <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">Binary | |
251 | Predicate</a> and have argument types of | |
252 | <tt>graph_traits<GraphSmall>::edge_descriptor</tt> and | |
253 | <tt>graph_traits<GraphLarge>::edge_descriptor</tt>. | |
254 | The edge descriptors must be <a href="http://www.sgi.com/tech/stl/LessThanComparable.html"> | |
255 | LessThan Comparable</a>. A return value of true indicates that the edges are equivalent. | |
256 | <br> | |
257 | <b>Default:</b> <tt><a href="./mcgregor_common_subgraphs.html#always_equivalent"> | |
258 | always_equivalent</a></tt> | |
259 | </p> | |
260 | </blockquote> | |
261 | ||
262 | <p>IN: <tt>vertices_equivalent(VertexEquivalencePredicate vertex_comp)</tt></p> | |
263 | <blockquote> | |
264 | <p> | |
265 | This function object is used to determine if vertices between the two graphs | |
266 | <tt>graph_small</tt> and <tt>graph_large</tt> are equivalent. | |
267 | Type <tt>VertexEquivalencePredicate</tt> must be a model of | |
268 | <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">Binary Predicate</a> | |
269 | and have argument types of | |
270 | <tt>graph_traits<GraphSmall>::vertex_descriptor</tt> and | |
271 | <tt>graph_traits<GraphLarge>::vertex_descriptor</tt>. A return value of true | |
272 | indicates that the vertices are equivalent. | |
273 | <br> | |
274 | <b>Default:</b> <tt><a href="./mcgregor_common_subgraphs.html#always_equivalent"> | |
275 | always_equivalent</a></tt> | |
276 | </p> | |
277 | </blockquote> | |
278 | ||
279 | <h3>Related Functions</h3> | |
280 | <p> | |
281 | Non-named parameter, named-parameter and all default parameter versions of | |
282 | function | |
283 | </p> | |
284 | <p><tt>vf2_graph_iso(...)</tt></p> | |
285 | <p><tt>vf2_subgraph_mono(...)</tt></p> | |
286 | <p> | |
287 | for isomorphism and (not necessarily induced) subgraph isomorphism testing, | |
288 | taking the same parameters as the corresponding functions <tt>vf2_subgraph_iso</tt> | |
289 | for induced subgraph isomorphism testing. | |
290 | For <tt>vf2_graph_iso</tt> the algorithm finds all isomorphism mappings between | |
291 | graphs <tt>graph1</tt> and <tt>graph2</tt> and outputs them to | |
292 | <tt>user_callback</tt>. | |
293 | For <tt>vf2_graph_mono</tt> the algorithm finds all mappings of <tt>graph_small</tt> | |
294 | to subgraphs of <tt>graph_large</tt>. | |
295 | Note that, as opposed to <tt>vf2_subgraph_iso</tt>, | |
296 | these subgraphs need not to be induced subgraphs. | |
297 | </p> | |
298 | <p> | |
299 | Both algorithms continues until <tt>user_callback</tt> | |
300 | returns false or the search space has been fully explored. As before, | |
301 | <tt>EdgeEquivalencePredicate</tt> and | |
302 | <tt>VertexEquivalencePredicate</tt> predicates are used to test | |
303 | whether edges and vertices are equivalent. By default | |
304 | <tt>always_equivalent</tt> is used. | |
305 | </p> | |
306 | ||
307 | <h3>Utility Functions and Structs</h3> | |
308 | <p> | |
309 | <tt id="vf2_callback"> | |
310 | template<typename Graph1, | |
311 | typename Graph2> | |
312 | struct vf2_print_callback | |
313 | </tt> | |
314 | </p> | |
315 | <blockquote> | |
316 | <p> | |
317 | Callback function object that prints out the correspondences between vertices | |
318 | of <tt>Graph1</tt> and <tt>Graph2</tt>. The constructor takes | |
319 | the two graphs <em>G<sub>1</sub></em> and <em>G<sub>2</sub></em>. | |
320 | </p> | |
321 | </blockquote> | |
322 | ||
323 | <pre> | |
324 | template<typename Graph> | |
325 | std::vector<typename graph_traits<Graph>::vertex_descriptor> | |
326 | vertex_order_by_mult(const Graph& graph) | |
327 | </pre> | |
328 | <blockquote> | |
329 | <p> | |
330 | Returns a vector containing the vertices of a graph, sorted | |
331 | by multiplicity of in/out degrees. | |
332 | </p> | |
333 | </blockquote> | |
334 | ||
335 | <pre> | |
336 | <em class="comment">// Variant of verify_subgraph_iso with all default parameters</em> | |
337 | template<typename Graph1, | |
338 | typename Graph2, | |
339 | typename CorresponenceMap1To2> | |
340 | inline bool verify_vf2_subgraph_iso(const Graph1& graph1, const Graph2& graph2, | |
341 | const CorresponenceMap1To2 f) | |
342 | ||
343 | ||
344 | <em class="comment">// Verifies a graph (sub)graph isomorphism map</em> | |
345 | template<typename Graph1, | |
346 | typename Graph2, | |
347 | typename CorresponenceMap1To2, | |
348 | typename EdgeEquivalencePredicate, | |
349 | typename VertexEquivalencePredicate> | |
350 | inline bool verify_vf2_subgraph_iso(const Graph1& graph1, const Graph2& graph2, | |
351 | const CorresponenceMap1To2 f, | |
352 | EdgeEquivalencePredicate edge_comp, | |
353 | VertexEquivalencePredicate vertex_comp) | |
354 | </pre> | |
355 | <blockquote> | |
356 | <p> | |
357 | This function can be used to verify a (sub)graph isomorphism | |
358 | mapping <em>f</em>. The parameters are analogous to | |
359 | function <tt>vf2_subgraph_iso</tt> (<tt>vf2_graph_iso</tt>). | |
360 | </p> | |
361 | </blockquote> | |
362 | ||
363 | ||
364 | <h3>Complexity</h3> | |
365 | <p> | |
366 | Spatial and time complexity are given in [<a href="#cordella2004">2</a>]. The spatial | |
367 | complexity of VF2 is of order <em>O(V)</em>, where V is the (maximum) number | |
368 | of vertices of the two graphs. Time complexity is <em>O(V<sup>2</sup>)</em> in the best case and | |
369 | <em>O(V!·V)</em> in the worst case. | |
370 | </p> | |
371 | ||
372 | <h3>Examples</h3> | |
373 | ||
374 | <h4>Example 1</h4> | |
375 | <p> | |
376 | In the example below, a small graph <tt>graph1</tt> and a larger graph | |
377 | <tt>graph2</tt> are defined. Here small and large refers to the number of | |
378 | vertices of the graphs. <tt>vf2_subgraph_iso</tt> computes all the | |
379 | subgraph isomorphism mappings between the two graphs and outputs them | |
380 | via <tt>callback</tt>. | |
381 | </p> | |
382 | <pre> | |
383 | typedef adjacency_list<setS, vecS, bidirectionalS> graph_type; | |
384 | ||
385 | <em class="comment">// Build graph1</em> | |
386 | int num_vertices1 = 8; graph_type graph1(num_vertices1); | |
387 | add_edge(0, 6, graph1); add_edge(0, 7, graph1); | |
388 | add_edge(1, 5, graph1); add_edge(1, 7, graph1); | |
389 | add_edge(2, 4, graph1); add_edge(2, 5, graph1); add_edge(2, 6, graph1); | |
390 | add_edge(3, 4, graph1); | |
391 | ||
392 | <em class="comment">// Build graph2</em> | |
393 | int num_vertices2 = 9; graph_type graph2(num_vertices2); | |
394 | add_edge(0, 6, graph2); add_edge(0, 8, graph2); | |
395 | add_edge(1, 5, graph2); add_edge(1, 7, graph2); | |
396 | add_edge(2, 4, graph2); add_edge(2, 7, graph2); add_edge(2, 8, graph2); | |
397 | add_edge(3, 4, graph2); add_edge(3, 5, graph2); add_edge(3, 6, graph2); | |
398 | <em class="comment"> | |
399 | // Create callback to print mappings</em> | |
400 | vf2_print_callback<graph_type, graph_type> callback(graph1, graph2); | |
401 | ||
402 | <em class="comment"> | |
403 | // Print out all subgraph isomorphism mappings between graph1 and graph2. | |
404 | // Vertices and edges are assumed to be always equivalent.</em> | |
405 | vf2_subgraph_iso(graph1, graph2, callback); | |
406 | </pre> | |
407 | <p> | |
408 | The complete example can be found under | |
409 | <a href="../example/vf2_sub_graph_iso_example.cpp"><tt>examples/vf2_sub_graph_iso_example.cpp</tt></a>. | |
410 | <br> | |
411 | </p> | |
412 | ||
413 | <h4>Example 2</h4> | |
414 | <p> | |
415 | In this example, the subgraph isomorphism mappings between multi-graphs are computed. The vertices | |
416 | and edges of the multi-graphs are distinguished using property maps. | |
417 | </p> | |
418 | <pre> | |
419 | <em class="comment">// Define edge and vertex properties</em> | |
420 | typedef property<edge_name_t, char> edge_property; | |
421 | typedef property<vertex_name_t, char, property<vertex_index_t, int> > vertex_property; | |
422 | ||
423 | <em class="comment">// Using a vecS graphs => the index maps are implicit.</em> | |
424 | typedef adjacency_list<vecS, vecS, bidirectionalS, vertex_property, edge_property> graph_type; | |
425 | ||
426 | <em class="comment">// Create graph1</em> | |
427 | graph_type graph1; | |
428 | <em class="comment">// Add vertices... </em> | |
429 | add_vertex(vertex_property('a'), graph1); | |
430 | ... | |
431 | <em class="comment">//... and edges </em> | |
432 | add_edge(0, 1, edge_property('b'), graph1); | |
433 | add_edge(0, 1, edge_property('b'), graph1); | |
434 | ... | |
435 | ||
436 | <em class="comment">// Create graph2 </em> | |
437 | graph_type graph2; | |
438 | add_vertex(vertex_property('a'), graph2); | |
439 | ... | |
440 | add_edge(0, 1, edge_property('a'), graph2); | |
441 | ... | |
442 | </pre> | |
443 | ||
444 | <p> | |
445 | To distinguish vertices and edges with property maps, binary predicates are created using the | |
446 | <tt><a href="./mcgregor_common_subgraphs.html#make_property_map_equivalent"> | |
447 | make_property_map_equivalent</a></tt> function: | |
448 | </p> | |
449 | ||
450 | <pre> | |
451 | <em class="comment">// Create the vertex binary predicate</em> | |
452 | typedef property_map<graph_type, vertex_name_t>::type vertex_name_map_t; | |
453 | typedef property_map_equivalent<vertex_name_map_t, vertex_name_map_t> vertex_comp_t; | |
454 | vertex_comp_t vertex_comp = | |
455 | make_property_map_equivalent(get(vertex_name, graph1), get(vertex_name, graph2)); | |
456 | ||
457 | <em class="comment">// Create the vertex binary predicate</em> | |
458 | typedef property_map<graph_type, edge_name_t>::type edge_name_map_t; | |
459 | typedef property_map_equivalent<edge_name_map_t, edge_name_map_t> edge_comp_t; | |
460 | edge_comp_t edge_comp = | |
461 | make_property_map_equivalent(get(edge_name, graph1), get(edge_name, graph2)); | |
462 | </pre> | |
463 | ||
464 | <p> | |
465 | Finally, a callback function object is created and the subgraph isomorphism mappings are | |
466 | computed: | |
467 | </p> | |
468 | <pre> | |
469 | <em class="comment">// Create callback</em> | |
470 | vf2_print_callback<graph_type, graph_type> callback(graph1, graph2); | |
471 | ||
472 | <em class="comment"> | |
473 | // Print out all subgraph isomorphism mappings between graph1 and graph2. | |
474 | // Function vertex_order_by_mult is used to compute the order of | |
475 | // vertices of graph1. This is the order in which the vertices are examined | |
476 | // during the matching process.</em> | |
477 | vf2_subgraph_iso(graph1, graph2, callback, vertex_order_by_mult(graph1), | |
478 | edges_equivalent(edge_comp).vertices_equivalent(vertex_comp)); | |
479 | </pre> | |
480 | ||
481 | <p> | |
482 | For the complete example, see | |
483 | <a href="../example/vf2_sub_graph_iso_multi_example.cpp"> | |
484 | <tt>examples/vf2_sub_graph_iso_multi_example.cpp</tt></a>. | |
485 | <br> | |
486 | </p> | |
487 | ||
488 | <h3 id="notes">Notes</h3> | |
489 | <p> | |
490 | If the <tt>EdgeList</tt> allows for parallel edges, e.g. <tt>vecS</tt>, the | |
491 | algorithm does some bookkeeping of already identified edges. Matched edges | |
492 | are temporarily stored using <tt>std::set</tt> as container, requiring that | |
493 | <tt>edge_descriptor</tt> are <a href="http://www.sgi.com/tech/stl/LessThanComparable.html"> | |
494 | LessThan Comparable</a>. In contrast, if instead you enforce the absence of | |
495 | parallel edges, e.g. by using <tt>setS</tt>, the lookup function falls back | |
496 | to <tt>edge()</tt> without performing any bookkeeping. | |
497 | </p> | |
498 | ||
499 | <h3>Bibliography</h3> | |
500 | ||
501 | <dl> | |
502 | <dt><a name="cordella2001">1</a></dt> | |
503 | <dd> | |
504 | L. P. Cordella, P. Foggia, C. Sansone, and M. Vento. | |
505 | <br><em>An improved algorithm for matching large graphs</em>. | |
506 | <br>In: 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, pp. 149-159, Cuen, 2001. | |
507 | <p></p> | |
508 | </dd> | |
509 | <dt><a name="cordella2004">2</a></dt> | |
510 | <dd> | |
511 | L. P. Cordella, P. Foggia, C. Sansone, and M. Vento. | |
512 | <br><em>A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs</em>. | |
513 | <br>IEEE Trans. Pattern Anal. Mach. Intell., vol. 26, no. 10, pp. 1367-1372, 2004. | |
514 | <p></p> | |
515 | </dd> | |
516 | <dt><a name="foggia_etal">3</a></dt> | |
517 | <dd> | |
518 | <a href="http://www.cs.sunysb.edu/~algorith/implement/vflib/implement.shtml"> | |
519 | <tt>http://www.cs.sunysb.edu/~algorith/implement/vflib/implement.shtml</tt></a> | |
520 | <p></p> | |
521 | </dd> | |
522 | </dl> | |
523 | <hr> | |
524 | <p> | |
525 | Copyright © 2012, Flavio De Lorenzi | |
526 | (<a href="mailto:fdlorenzi@gmail.com">fdlorenzi@gmail.com</a>) <br /> | |
527 | Copyright © 2013, Jakob Lykke Andersen, University of Southern Denmark | |
528 | (<a href="mailto:jlandersen@imada.sdu.dk">jlandersen@imada.sdu.dk</a>) | |
529 | </p> | |
530 | </body> | |
531 | </html> |