532 lines
22 KiB
HTML
532 lines
22 KiB
HTML
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
|
|
"http://www.w3.org/TR/html4/strict.dtd">
|
|
<!--
|
|
Copyright (C) Flavio De Lorenzi 2012
|
|
|
|
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>
|
|
<meta http-equiv="content-type" content="text/html; charset=iso-8859-15">
|
|
<title>Boost Graph Library: VF2 (Sub)Graph Isomorphism</title>
|
|
<style type="text/css">
|
|
<!--
|
|
body {
|
|
color: black;
|
|
background-color: white;
|
|
}
|
|
|
|
.comment {
|
|
color: #333333;
|
|
}
|
|
|
|
a {
|
|
color: blue;
|
|
}
|
|
|
|
a:visited {
|
|
color: #551A8B;
|
|
}
|
|
-->
|
|
</style>
|
|
</head>
|
|
<body>
|
|
<p><img src="../../../boost.png" alt="C++ Boost" width="277" height="86"></p>
|
|
<h1>
|
|
<tt>vf2_subgraph_iso</tt>
|
|
</h1>
|
|
<pre>
|
|
<em class="comment">// All defaults interface</em>
|
|
template <typename GraphSmall,
|
|
typename GraphLarge,
|
|
typename SubGraphIsoMapCallback>
|
|
bool vf2_subgraph_iso(const GraphSmall& graph_small,
|
|
const GraphLarge& graph_large,
|
|
SubGraphIsoMapCallback user_callback)
|
|
|
|
|
|
<em class="comment">// Named parameter version</em>
|
|
template <typename GraphSmall,
|
|
typename GraphLarge,
|
|
typename VertexOrderSmall,
|
|
typename SubGraphIsoMapCallback,
|
|
typename Param,
|
|
typename Tag,
|
|
typename Rest>
|
|
bool vf2_subgraph_iso(const GraphSmall& graph_small,
|
|
const GraphLarge& graph_large,
|
|
SubGraphIsoMapCallback user_callback,
|
|
const VertexOrderSmall& vertex_order_small,
|
|
const bgl_named_params<Param, Tag, Rest>& params)
|
|
|
|
|
|
<em class="comment">// Non-named parameter version</em>
|
|
template <typename GraphSmall,
|
|
typename GraphLarge,
|
|
typename <a href="../../property_map/doc/ReadablePropertyMap.html">IndexMapSmall</a>,
|
|
typename <a href="../../property_map/doc/ReadablePropertyMap.html">IndexMapLarge</a>,
|
|
typename VertexOrderSmall,
|
|
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 SubGraphIsoMapCallback>
|
|
bool vf2_subgraph_iso(const GraphSmall& graph_small,
|
|
const GraphLarge& graph_large,
|
|
SubGraphIsoMapCallback user_callback,
|
|
IndexMapSmall index_map_small,
|
|
IndexMapLarge index_map_large,
|
|
const VertexOrderSmall& vertex_order_small,
|
|
EdgeEquivalencePredicate edge_comp,
|
|
VertexEquivalencePredicate vertex_comp)
|
|
</pre>
|
|
<p>
|
|
An isomorphism between two graphs <em>G<sub>1</sub>=(V<sub>1</sub>, E<sub>1</sub>)</em>
|
|
and <em>G<sub>2</sub>=(V<sub>2</sub>, E<sub>2</sub>)</em> is a
|
|
bijective mapping <em>M</em> of the vertices of one graph to vertices of the other
|
|
graph that preserves the edge structure of the graphs. <em>M</em> is said to be a
|
|
graph-subgraph isomorphism if and only if <em>M</em> is an isomorphism between
|
|
<em>G<sub>1</sub></em> and a subgraph of <em>G<sub>2</sub></em>.
|
|
An induced subgraph of a graph <em>G = (V, E)</em> is a normal subgraph
|
|
<em>G' = (V', E')</em> with the extra condition that all edges of <em>G</em>
|
|
which have both endpoints in <em>V'</em> are in <em>E'</em>.
|
|
</p>
|
|
|
|
<p>
|
|
This function finds all induced subgraph isomorphisms between
|
|
graphs <tt>graph_small</tt> and <tt>graph_large</tt> and outputs them to
|
|
<tt>user_callback</tt>. It continues until <tt>user_callback</tt>
|
|
returns false or the search space has been fully explored. <tt>vf2_subgraph_iso</tt>
|
|
returns true if a graph-subgraph isomorphism exists and false otherwise.
|
|
<tt>EdgeEquivalencePredicate</tt> and
|
|
<tt>VertexEquivalencePredicate</tt> predicates are used to test whether
|
|
edges and vertices are equivalent. To use property maps for equivalence,
|
|
see
|
|
<tt><a href="./mcgregor_common_subgraphs.html#make_property_map_equivalent">
|
|
make_property_map_equivalent</a></tt>
|
|
function. By default <tt><a href="./mcgregor_common_subgraphs.html#always_equivalent">
|
|
always_equivalent</a></tt> is used, which returns
|
|
true for any pair of vertices or edges.
|
|
</p>
|
|
<p>
|
|
The current implementation is based on the <em>VF2</em> algorithm,
|
|
introduced by Cordella et al. An in-depth description of the algorithm is
|
|
given in [<a href="#cordella2001">1</a>] and [<a href="#cordella2004">2</a>]
|
|
and references therein. The original code by P. Foggia and collaborators can
|
|
be found at [<a href="#foggia_etal">3</a>]. In brief, the process of
|
|
finding a mapping between the two graphs <em>G<sub>1</sub></em> and
|
|
<em>G<sub>2</sub></em> determines the isomorphism mapping <em>M</em>,
|
|
which associates vertices <em>G<sub>1</sub></em> with vertices of
|
|
<em>G<sub>2</sub></em> and vice versa. It can be described by means of a
|
|
state space representation which is created by the algorithm
|
|
while exploring the search graph in depth-first fashion.
|
|
Each state <em>s</em> of the matching process
|
|
can be associated with a partial mapping <em>M(s)</em>. At each level,
|
|
the algorithm computes the set of the vertex pairs that are candidates to
|
|
be added to the current state <em>s</em>. If a pair of vertices
|
|
(<em>v, w</em>) is feasible, the mapping is extended and the associated
|
|
successor state <em>s'</em> is computed.
|
|
The whole procedure is then repeated for state <em>s'</em>.
|
|
</p>
|
|
|
|
<h3>Where Defined</h3>
|
|
<p>
|
|
<a href="../../../boost/graph/vf2_sub_graph_iso.hpp">
|
|
<tt>boost/graph/vf2_sub_graph_iso.hpp</tt></a><br>
|
|
All functions are defined in the boost namespace.
|
|
</p>
|
|
|
|
<h3>Parameters</h3>
|
|
|
|
<p>IN: <tt>const GraphSmall& graph_small</tt></p>
|
|
<blockquote>
|
|
<p>
|
|
The (first) smaller graph (fewer vertices) of the pair to be tested for
|
|
isomorphism. The type <tt>GraphSmall</tt> must be a
|
|
model of
|
|
<a href="./VertexListGraph.html">Vertex List Graph</a>,
|
|
<a href="./EdgeListGraph.html">Edge List Graph</a>,
|
|
<a href="./BidirectionalGraph.html">Bidirectional Graph</a> and
|
|
<a href="./AdjacencyMatrix.html">Adjacency Matrix</a>.
|
|
The edge descriptors <tt>graph_traits<GraphSmall>::edge_descriptor</tt>
|
|
must be <a href="http://www.boost.org/sgi/stl/LessThanComparable.html">
|
|
LessThan Comparable</a>, cf. also the remark <a href="#notes">below</a>.
|
|
</p>
|
|
</blockquote>
|
|
|
|
<p>IN: <tt>const GraphLarge& graph_large</tt></p>
|
|
<blockquote>
|
|
<p>
|
|
The (second) larger graph to be tested.
|
|
Type <tt>GraphLarge</tt> must be a model of
|
|
<a href="./VertexListGraph.html">Vertex List Graph</a>,
|
|
<a href="./EdgeListGraph.html">Edge List Graph</a>,
|
|
<a href="./BidirectionalGraph.html">Bidirectional Graph</a> and
|
|
<a href="./AdjacencyMatrix.html">Adjacency Matrix</a>.
|
|
The edge descriptors <tt>graph_traits<GraphLarge>::edge_descriptor</tt>
|
|
must be <a href="http://www.boost.org/sgi/stl/LessThanComparable.html">
|
|
LessThan Comparable</a>, cf. also the remark <a href="#notes">below</a>.
|
|
</p>
|
|
</blockquote>
|
|
|
|
<p>OUT: <tt>SubGraphIsoMapCallback user_callback</tt></p>
|
|
<blockquote>
|
|
<p>
|
|
A function object to be called when a graph-subgraph isomorphism has been discovered. The
|
|
<tt>operator()</tt> must have following form:
|
|
</p>
|
|
<pre>
|
|
template <typename CorrespondenceMap1To2,
|
|
typename CorrespondenceMap2To1>
|
|
bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1 g) const
|
|
</pre>
|
|
<p>
|
|
Both the <tt>CorrespondenceMap1To2</tt>
|
|
and <tt>CorresondenceMap2To1</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>vf2_subgraph_iso</tt> (or <tt>vf2_graph_iso</tt> or
|
|
<tt>vf2_subgraph_mono</tt>). For instance, if <tt>v</tt> is
|
|
from <tt>graph_small</tt>, <tt>w</tt> is from <tt>graph_large</tt>,
|
|
and the vertices can be considered equivalent,
|
|
then <tt>get(f, v)</tt> will be <tt>w</tt> and <tt>get(g, w)</tt>
|
|
will be <tt>v</tt>. If any vertex, say <tt>v</tt> in <tt>graph_small</tt>,
|
|
does not match a vertex in <tt>graph_large</tt> ,
|
|
then <tt>get(f, v)</tt> will be <tt>graph_traits<GraphLarge>::null_vertex()</tt>.
|
|
Likewise for any unmatched vertices from <tt>graph_large</tt>,
|
|
<tt>get(g, w)</tt> will be <tt>graph_traits<GraphSmall>::null_vertex()</tt>.
|
|
|
|
Returning false from the callback will abort the search immediately. Otherwise,
|
|
the entire search space will be explored. A "default" print callback
|
|
is provided as a <a href="#vf2_callback">utility function</a>.
|
|
</p>
|
|
</blockquote>
|
|
|
|
<p>IN: <tt>const VertexOrderSmall& vertex_order_small</tt></p>
|
|
<blockquote>
|
|
<p>
|
|
The ordered vertices of the smaller (first) graph <tt>graph_small</tt>.
|
|
During the matching process the vertices are examined in the order given by
|
|
<tt>vertex_order_small</tt>. Type <tt>VertexOrderSmall</tt> must be a model
|
|
of <a href="http://www.boost.org/sgi/stl/Container.html">ContainerConcept</a>
|
|
with value type
|
|
<tt>graph_traits<GraphSmall>::vertex_descriptor</tt>.
|
|
<br>
|
|
<b>Default</b> The vertices are ordered by multiplicity of
|
|
in/out degrees.
|
|
</p>
|
|
</blockquote>
|
|
|
|
<h3>Named Parameters</h3>
|
|
|
|
<p>IN: <tt>vertex_index1(IndexMapSmall index_map_small)</tt></p>
|
|
<blockquote>
|
|
<p>
|
|
This maps each vertex to an integer in the range <tt>[0, num_vertices(graph_small))</tt>.
|
|
Type <tt>IndexMapSmall</tt> must be a model of
|
|
<a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>.
|
|
<br>
|
|
<b>Default:</b> <tt>get(vertex_index, graph_small)</tt>
|
|
</p>
|
|
</blockquote>
|
|
|
|
<p>IN: <tt>vertex_index2(IndexMapLarge index_map_large)</tt></p>
|
|
<blockquote>
|
|
<p>
|
|
This maps each vertex to an integer in the range <tt>[0, num_vertices(graph_large))</tt>.
|
|
Type <tt>IndexMapLarge</tt> must be a model of
|
|
<a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>.
|
|
<br>
|
|
<b>Default:</b> <tt>get(vertex_index, graph_large)</tt>
|
|
</p>
|
|
</blockquote>
|
|
|
|
<p>IN: <tt>edges_equivalent(EdgeEquivalencePredicate edge_comp)</tt></p>
|
|
<blockquote>
|
|
<p>
|
|
This function object is used to determine if edges between the two graphs
|
|
<tt>graph_small</tt> and <tt>graph_large</tt> are equivalent.
|
|
Type <tt>EdgeEquivalencePredicate</tt> 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<GraphSmall>::edge_descriptor</tt> and
|
|
<tt>graph_traits<GraphLarge>::edge_descriptor</tt>.
|
|
The edge descriptors must be <a href="http://www.boost.org/sgi/stl/LessThanComparable.html">
|
|
LessThan Comparable</a>. A return value of true indicates that the edges are equivalent.
|
|
<br>
|
|
<b>Default:</b> <tt><a href="./mcgregor_common_subgraphs.html#always_equivalent">
|
|
always_equivalent</a></tt>
|
|
</p>
|
|
</blockquote>
|
|
|
|
<p>IN: <tt>vertices_equivalent(VertexEquivalencePredicate vertex_comp)</tt></p>
|
|
<blockquote>
|
|
<p>
|
|
This function object is used to determine if vertices between the two graphs
|
|
<tt>graph_small</tt> and <tt>graph_large</tt> are equivalent.
|
|
Type <tt>VertexEquivalencePredicate</tt> 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<GraphSmall>::vertex_descriptor</tt> and
|
|
<tt>graph_traits<GraphLarge>::vertex_descriptor</tt>. A return value of true
|
|
indicates that the vertices are equivalent.
|
|
<br>
|
|
<b>Default:</b> <tt><a href="./mcgregor_common_subgraphs.html#always_equivalent">
|
|
always_equivalent</a></tt>
|
|
</p>
|
|
</blockquote>
|
|
|
|
<h3>Related Functions</h3>
|
|
<p>
|
|
Non-named parameter, named-parameter and all default parameter versions of
|
|
function
|
|
</p>
|
|
<p><tt>vf2_graph_iso(...)</tt></p>
|
|
<p><tt>vf2_subgraph_mono(...)</tt></p>
|
|
<p>
|
|
for isomorphism and (not necessarily induced) subgraph isomorphism testing,
|
|
taking the same parameters as the corresponding functions <tt>vf2_subgraph_iso</tt>
|
|
for induced subgraph isomorphism testing.
|
|
For <tt>vf2_graph_iso</tt> the algorithm finds all isomorphism mappings between
|
|
graphs <tt>graph1</tt> and <tt>graph2</tt> and outputs them to
|
|
<tt>user_callback</tt>.
|
|
For <tt>vf2_graph_mono</tt> the algorithm finds all mappings of <tt>graph_small</tt>
|
|
to subgraphs of <tt>graph_large</tt>.
|
|
Note that, as opposed to <tt>vf2_subgraph_iso</tt>,
|
|
these subgraphs need not to be induced subgraphs.
|
|
</p>
|
|
<p>
|
|
Both algorithms continues until <tt>user_callback</tt>
|
|
returns false or the search space has been fully explored. As before,
|
|
<tt>EdgeEquivalencePredicate</tt> and
|
|
<tt>VertexEquivalencePredicate</tt> predicates are used to test
|
|
whether edges and vertices are equivalent. By default
|
|
<tt>always_equivalent</tt> is used.
|
|
</p>
|
|
|
|
<h3>Utility Functions and Structs</h3>
|
|
<p>
|
|
<tt id="vf2_callback">
|
|
template<typename Graph1,
|
|
typename Graph2>
|
|
struct vf2_print_callback
|
|
</tt>
|
|
</p>
|
|
<blockquote>
|
|
<p>
|
|
Callback function object that prints out the correspondences between vertices
|
|
of <tt>Graph1</tt> and <tt>Graph2</tt>. The constructor takes
|
|
the two graphs <em>G<sub>1</sub></em> and <em>G<sub>2</sub></em>.
|
|
</p>
|
|
</blockquote>
|
|
|
|
<pre>
|
|
template<typename Graph>
|
|
std::vector<typename graph_traits<Graph>::vertex_descriptor>
|
|
vertex_order_by_mult(const Graph& graph)
|
|
</pre>
|
|
<blockquote>
|
|
<p>
|
|
Returns a vector containing the vertices of a graph, sorted
|
|
by multiplicity of in/out degrees.
|
|
</p>
|
|
</blockquote>
|
|
|
|
<pre>
|
|
<em class="comment">// Variant of verify_subgraph_iso with all default parameters</em>
|
|
template<typename Graph1,
|
|
typename Graph2,
|
|
typename CorresponenceMap1To2>
|
|
inline bool verify_vf2_subgraph_iso(const Graph1& graph1, const Graph2& graph2,
|
|
const CorresponenceMap1To2 f)
|
|
|
|
|
|
<em class="comment">// Verifies a graph (sub)graph isomorphism map</em>
|
|
template<typename Graph1,
|
|
typename Graph2,
|
|
typename CorresponenceMap1To2,
|
|
typename EdgeEquivalencePredicate,
|
|
typename VertexEquivalencePredicate>
|
|
inline bool verify_vf2_subgraph_iso(const Graph1& graph1, const Graph2& graph2,
|
|
const CorresponenceMap1To2 f,
|
|
EdgeEquivalencePredicate edge_comp,
|
|
VertexEquivalencePredicate vertex_comp)
|
|
</pre>
|
|
<blockquote>
|
|
<p>
|
|
This function can be used to verify a (sub)graph isomorphism
|
|
mapping <em>f</em>. The parameters are analogous to
|
|
function <tt>vf2_subgraph_iso</tt> (<tt>vf2_graph_iso</tt>).
|
|
</p>
|
|
</blockquote>
|
|
|
|
|
|
<h3>Complexity</h3>
|
|
<p>
|
|
Spatial and time complexity are given in [<a href="#cordella2004">2</a>]. The spatial
|
|
complexity of VF2 is of order <em>O(V)</em>, where V is the (maximum) number
|
|
of vertices of the two graphs. Time complexity is <em>O(V<sup>2</sup>)</em> in the best case and
|
|
<em>O(V!·V)</em> in the worst case.
|
|
</p>
|
|
|
|
<h3>Examples</h3>
|
|
|
|
<h4>Example 1</h4>
|
|
<p>
|
|
In the example below, a small graph <tt>graph1</tt> and a larger graph
|
|
<tt>graph2</tt> are defined. Here small and large refers to the number of
|
|
vertices of the graphs. <tt>vf2_subgraph_iso</tt> computes all the
|
|
subgraph isomorphism mappings between the two graphs and outputs them
|
|
via <tt>callback</tt>.
|
|
</p>
|
|
<pre>
|
|
typedef adjacency_list<setS, vecS, bidirectionalS> graph_type;
|
|
|
|
<em class="comment">// Build graph1</em>
|
|
int num_vertices1 = 8; graph_type graph1(num_vertices1);
|
|
add_edge(0, 6, graph1); add_edge(0, 7, graph1);
|
|
add_edge(1, 5, graph1); add_edge(1, 7, graph1);
|
|
add_edge(2, 4, graph1); add_edge(2, 5, graph1); add_edge(2, 6, graph1);
|
|
add_edge(3, 4, graph1);
|
|
|
|
<em class="comment">// Build graph2</em>
|
|
int num_vertices2 = 9; graph_type graph2(num_vertices2);
|
|
add_edge(0, 6, graph2); add_edge(0, 8, graph2);
|
|
add_edge(1, 5, graph2); add_edge(1, 7, graph2);
|
|
add_edge(2, 4, graph2); add_edge(2, 7, graph2); add_edge(2, 8, graph2);
|
|
add_edge(3, 4, graph2); add_edge(3, 5, graph2); add_edge(3, 6, graph2);
|
|
<em class="comment">
|
|
// Create callback to print mappings</em>
|
|
vf2_print_callback<graph_type, graph_type> callback(graph1, graph2);
|
|
|
|
<em class="comment">
|
|
// Print out all subgraph isomorphism mappings between graph1 and graph2.
|
|
// Vertices and edges are assumed to be always equivalent.</em>
|
|
vf2_subgraph_iso(graph1, graph2, callback);
|
|
</pre>
|
|
<p>
|
|
The complete example can be found under
|
|
<a href="../example/vf2_sub_graph_iso_example.cpp"><tt>examples/vf2_sub_graph_iso_example.cpp</tt></a>.
|
|
<br>
|
|
</p>
|
|
|
|
<h4>Example 2</h4>
|
|
<p>
|
|
In this example, the subgraph isomorphism mappings between multi-graphs are computed. The vertices
|
|
and edges of the multi-graphs are distinguished using property maps.
|
|
</p>
|
|
<pre>
|
|
<em class="comment">// Define edge and vertex properties</em>
|
|
typedef property<edge_name_t, char> edge_property;
|
|
typedef property<vertex_name_t, char, property<vertex_index_t, int> > vertex_property;
|
|
|
|
<em class="comment">// Using a vecS graphs => the index maps are implicit.</em>
|
|
typedef adjacency_list<vecS, vecS, bidirectionalS, vertex_property, edge_property> graph_type;
|
|
|
|
<em class="comment">// Create graph1</em>
|
|
graph_type graph1;
|
|
<em class="comment">// Add vertices... </em>
|
|
add_vertex(vertex_property('a'), graph1);
|
|
...
|
|
<em class="comment">//... and edges </em>
|
|
add_edge(0, 1, edge_property('b'), graph1);
|
|
add_edge(0, 1, edge_property('b'), graph1);
|
|
...
|
|
|
|
<em class="comment">// Create graph2 </em>
|
|
graph_type graph2;
|
|
add_vertex(vertex_property('a'), graph2);
|
|
...
|
|
add_edge(0, 1, edge_property('a'), graph2);
|
|
...
|
|
</pre>
|
|
|
|
<p>
|
|
To distinguish vertices and edges with property maps, binary predicates are created using the
|
|
<tt><a href="./mcgregor_common_subgraphs.html#make_property_map_equivalent">
|
|
make_property_map_equivalent</a></tt> function:
|
|
</p>
|
|
|
|
<pre>
|
|
<em class="comment">// Create the vertex binary predicate</em>
|
|
typedef property_map<graph_type, vertex_name_t>::type vertex_name_map_t;
|
|
typedef property_map_equivalent<vertex_name_map_t, vertex_name_map_t> vertex_comp_t;
|
|
vertex_comp_t vertex_comp =
|
|
make_property_map_equivalent(get(vertex_name, graph1), get(vertex_name, graph2));
|
|
|
|
<em class="comment">// Create the vertex binary predicate</em>
|
|
typedef property_map<graph_type, edge_name_t>::type edge_name_map_t;
|
|
typedef property_map_equivalent<edge_name_map_t, edge_name_map_t> edge_comp_t;
|
|
edge_comp_t edge_comp =
|
|
make_property_map_equivalent(get(edge_name, graph1), get(edge_name, graph2));
|
|
</pre>
|
|
|
|
<p>
|
|
Finally, a callback function object is created and the subgraph isomorphism mappings are
|
|
computed:
|
|
</p>
|
|
<pre>
|
|
<em class="comment">// Create callback</em>
|
|
vf2_print_callback<graph_type, graph_type> callback(graph1, graph2);
|
|
|
|
<em class="comment">
|
|
// Print out all subgraph isomorphism mappings between graph1 and graph2.
|
|
// Function vertex_order_by_mult is used to compute the order of
|
|
// vertices of graph1. This is the order in which the vertices are examined
|
|
// during the matching process.</em>
|
|
vf2_subgraph_iso(graph1, graph2, callback, vertex_order_by_mult(graph1),
|
|
edges_equivalent(edge_comp).vertices_equivalent(vertex_comp));
|
|
</pre>
|
|
|
|
<p>
|
|
For the complete example, see
|
|
<a href="../example/vf2_sub_graph_iso_multi_example.cpp">
|
|
<tt>examples/vf2_sub_graph_iso_multi_example.cpp</tt></a>.
|
|
<br>
|
|
</p>
|
|
|
|
<h3 id="notes">Notes</h3>
|
|
<p>
|
|
If the <tt>EdgeList</tt> allows for parallel edges, e.g. <tt>vecS</tt>, the
|
|
algorithm does some bookkeeping of already identified edges. Matched edges
|
|
are temporarily stored using <tt>std::set</tt> as container, requiring that
|
|
<tt>edge_descriptor</tt> are <a href="http://www.boost.org/sgi/stl/LessThanComparable.html">
|
|
LessThan Comparable</a>. In contrast, if instead you enforce the absence of
|
|
parallel edges, e.g. by using <tt>setS</tt>, the lookup function falls back
|
|
to <tt>edge()</tt> without performing any bookkeeping.
|
|
</p>
|
|
|
|
<h3>Bibliography</h3>
|
|
|
|
<dl>
|
|
<dt><a name="cordella2001">1</a></dt>
|
|
<dd>
|
|
L. P. Cordella, P. Foggia, C. Sansone, and M. Vento.
|
|
<br><em>An improved algorithm for matching large graphs</em>.
|
|
<br>In: 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, pp. 149-159, Cuen, 2001.
|
|
<p></p>
|
|
</dd>
|
|
<dt><a name="cordella2004">2</a></dt>
|
|
<dd>
|
|
L. P. Cordella, P. Foggia, C. Sansone, and M. Vento.
|
|
<br><em>A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs</em>.
|
|
<br>IEEE Trans. Pattern Anal. Mach. Intell., vol. 26, no. 10, pp. 1367-1372, 2004.
|
|
<p></p>
|
|
</dd>
|
|
<dt><a name="foggia_etal">3</a></dt>
|
|
<dd>
|
|
<a href="http://www.cs.sunysb.edu/~algorith/implement/vflib/implement.shtml">
|
|
<tt>http://www.cs.sunysb.edu/~algorith/implement/vflib/implement.shtml</tt></a>
|
|
<p></p>
|
|
</dd>
|
|
</dl>
|
|
<hr>
|
|
<p>
|
|
Copyright © 2012, Flavio De Lorenzi
|
|
(<a href="mailto:fdlorenzi@gmail.com">fdlorenzi@gmail.com</a>) <br />
|
|
Copyright © 2013, Jakob Lykke Andersen, University of Southern Denmark
|
|
(<a href="mailto:jlandersen@imada.sdu.dk">jlandersen@imada.sdu.dk</a>)
|
|
</p>
|
|
</body>
|
|
</html>
|