1 <!DOCTYPE HTML PUBLIC
"-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
4 Copyright (C) Flavio De Lorenzi 2012
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)
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">
18 background-color: white;
36 <p><img src=
"../../../boost.png" alt=
"C++ Boost" width=
"277" height=
"86"></p>
38 <tt>vf2_subgraph_iso
</tt>
41 <em class=
"comment">// All defaults interface
</em>
42 template
<typename GraphSmall,
44 typename SubGraphIsoMapCallback
>
45 bool vf2_subgraph_iso(const GraphSmall
& graph_small,
46 const GraphLarge
& graph_large,
47 SubGraphIsoMapCallback user_callback)
50 <em class=
"comment">// Named parameter version
</em>
51 template
<typename GraphSmall,
53 typename VertexOrderSmall,
54 typename SubGraphIsoMapCallback,
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)
65 <em class=
"comment">// Non-named parameter version
</em>
66 template
<typename GraphSmall,
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)
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>.
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,
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.
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>.
132 <h3>Where Defined
</h3>
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.
141 <p>IN:
<tt>const GraphSmall
& graph_small
</tt></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
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>.
157 <p>IN:
<tt>const GraphLarge
& graph_large
</tt></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>.
172 <p>OUT:
<tt>SubGraphIsoMapCallback user_callback
</tt></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:
179 template
<typename CorrespondenceMap1To2,
180 typename CorrespondenceMap2To1
>
181 bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1 g) const
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>.
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>.
205 <p>IN:
<tt>const VertexOrderSmall
& vertex_order_small
</tt></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>
213 <tt>graph_traits
<GraphSmall
>::vertex_descriptor
</tt>.
215 <b>Default
</b> The vertices are ordered by multiplicity of
220 <h3>Named Parameters
</h3>
222 <p>IN:
<tt>vertex_index1(IndexMapSmall index_map_small)
</tt></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>.
229 <b>Default:
</b> <tt>get(vertex_index, graph_small)
</tt>
233 <p>IN:
<tt>vertex_index2(IndexMapLarge index_map_large)
</tt></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>.
240 <b>Default:
</b> <tt>get(vertex_index, graph_large)
</tt>
244 <p>IN:
<tt>edges_equivalent(EdgeEquivalencePredicate edge_comp)
</tt></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.
257 <b>Default:
</b> <tt><a href=
"./mcgregor_common_subgraphs.html#always_equivalent">
258 always_equivalent
</a></tt>
262 <p>IN:
<tt>vertices_equivalent(VertexEquivalencePredicate vertex_comp)
</tt></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.
274 <b>Default:
</b> <tt><a href=
"./mcgregor_common_subgraphs.html#always_equivalent">
275 always_equivalent
</a></tt>
279 <h3>Related Functions
</h3>
281 Non-named parameter, named-parameter and all default parameter versions of
284 <p><tt>vf2_graph_iso(...)
</tt></p>
285 <p><tt>vf2_subgraph_mono(...)
</tt></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.
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.
307 <h3>Utility Functions and Structs
</h3>
309 <tt id=
"vf2_callback">
310 template
<typename Graph1,
312 struct vf2_print_callback
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>.
324 template
<typename Graph
>
325 std::vector
<typename graph_traits
<Graph
>::vertex_descriptor
>
326 vertex_order_by_mult(const Graph
& graph)
330 Returns a vector containing the vertices of a graph, sorted
331 by multiplicity of in/out degrees.
336 <em class=
"comment">// Variant of verify_subgraph_iso with all default parameters
</em>
337 template
<typename Graph1,
339 typename CorresponenceMap1To2
>
340 inline bool verify_vf2_subgraph_iso(const Graph1
& graph1, const Graph2
& graph2,
341 const CorresponenceMap1To2 f)
344 <em class=
"comment">// Verifies a graph (sub)graph isomorphism map
</em>
345 template
<typename Graph1,
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)
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>).
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.
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>.
383 typedef adjacency_list
<setS, vecS, bidirectionalS
> graph_type;
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);
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);
399 // Create callback to print mappings
</em>
400 vf2_print_callback
<graph_type, graph_type
> callback(graph1, graph2);
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);
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>.
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.
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;
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;
426 <em class=
"comment">// Create graph1
</em>
428 <em class=
"comment">// Add vertices...
</em>
429 add_vertex(vertex_property('a'), graph1);
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);
436 <em class=
"comment">// Create graph2
</em>
438 add_vertex(vertex_property('a'), graph2);
440 add_edge(
0,
1, edge_property('a'), graph2);
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:
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));
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));
465 Finally, a callback function object is created and the subgraph isomorphism mappings are
469 <em class=
"comment">// Create callback
</em>
470 vf2_print_callback
<graph_type, graph_type
> callback(graph1, graph2);
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));
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>.
488 <h3 id=
"notes">Notes
</h3>
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.
499 <h3>Bibliography
</h3>
502 <dt><a name=
"cordella2001">1</a></dt>
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.
509 <dt><a name=
"cordella2004">2</a></dt>
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.
516 <dt><a name=
"foggia_etal">3</a></dt>
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>
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>)