ceph/src/boost/libs/graph/doc/vf2_sub_graph_iso.html

   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 &lt;typename GraphSmall,
  43           typename GraphLarge,
  44           typename SubGraphIsoMapCallback&gt;
  45 bool vf2_subgraph_iso(const GraphSmall&amp; graph_small,
  46                       const GraphLarge&amp; graph_large,
  47                       SubGraphIsoMapCallback user_callback)
  48
  49
  50 <em class="comment">// Named parameter version</em>
  51 template &lt;typename GraphSmall,
  52           typename GraphLarge,
  53           typename VertexOrderSmall,
  54           typename SubGraphIsoMapCallback,
  55           typename Param,
  56           typename Tag,
  57           typename Rest&gt;
  58 bool vf2_subgraph_iso(const GraphSmall&amp; graph_small,
  59                       const GraphLarge&amp; graph_large,
  60                       SubGraphIsoMapCallback user_callback,
  61                       const VertexOrderSmall&amp; vertex_order_small,
  62                       const bgl_named_params&lt;Param, Tag, Rest&gt;&amp; params)
  63
  64
  65 <em class="comment">// Non-named parameter version</em>
  66 template &lt;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&gt;
  74 bool vf2_subgraph_iso(const GraphSmall&amp; graph_small,
  75                       const GraphLarge&amp; graph_large,
  76                       SubGraphIsoMapCallback user_callback,
  77                       IndexMapSmall index_map_small,
  78                       IndexMapLarge index_map_large,
  79                       const VertexOrderSmall&amp; 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&amp; 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&lt;GraphSmall&gt;::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&amp; 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&lt;GraphLarge&gt;::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 &lt;typename CorrespondenceMap1To2,
 180           typename CorrespondenceMap2To1&gt;
 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&lt;GraphLarge&gt;::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&lt;GraphSmall&gt;::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&amp; 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&lt;GraphSmall&gt;::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&lt;GraphSmall&gt;::edge_descriptor</tt> and
 253         <tt>graph_traits&lt;GraphLarge&gt;::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&lt;GraphSmall&gt;::vertex_descriptor</tt> and
 271         <tt>graph_traits&lt;GraphLarge&gt;::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&lt;typename Graph1,
 311           typename Graph2&gt;
 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&lt;typename Graph&gt;
 325 std::vector&lt;typename graph_traits&lt;Graph&gt;::vertex_descriptor&gt;
 326   vertex_order_by_mult(const Graph&amp; 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&lt;typename Graph1,
 338          typename Graph2,
 339          typename CorresponenceMap1To2&gt;
 340 inline bool verify_vf2_subgraph_iso(const Graph1&amp; graph1, const Graph2&amp; graph2,
 341                                     const CorresponenceMap1To2 f)
 342
 343
 344 <em class="comment">// Verifies a graph (sub)graph isomorphism map</em>
 345 template&lt;typename Graph1,
 346          typename Graph2,
 347          typename CorresponenceMap1To2,
 348          typename EdgeEquivalencePredicate,
 349          typename VertexEquivalencePredicate&gt;
 350 inline bool verify_vf2_subgraph_iso(const Graph1&amp; graph1, const Graph2&amp; 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!&middot;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&lt;setS, vecS, bidirectionalS&gt; 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&lt;graph_type, graph_type&gt; 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&lt;edge_name_t, char&gt; edge_property;
 421 typedef property&lt;vertex_name_t, char, property&lt;vertex_index_t, int&gt; &gt; vertex_property;
 422
 423 <em class="comment">// Using a vecS graphs => the index maps are implicit.</em>
 424 typedef adjacency_list&lt;vecS, vecS, bidirectionalS, vertex_property, edge_property&gt; 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&lt;graph_type, vertex_name_t&gt;::type vertex_name_map_t;
 453 typedef property_map_equivalent&lt;vertex_name_map_t, vertex_name_map_t&gt; 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&lt;graph_type, edge_name_t&gt;::type edge_name_map_t;
 459 typedef property_map_equivalent&lt;edge_name_map_t, edge_name_map_t&gt; 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&lt;graph_type, graph_type&gt; 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.&nbsp;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.&nbsp;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 &copy; 2012, Flavio De Lorenzi
 526       (<a href="mailto:fdlorenzi@gmail.com">fdlorenzi@gmail.com</a>) <br />
 527       Copyright &copy; 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>