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

   1 <html><head><!-- Copyright 2007 Aaron Windsor
   2
   3      Distributed under the Boost Software License, Version 1.0.
   4      (See accompanying file LICENSE_1_0.txt or copy at
   5      http://www.boost.org/LICENSE_1_0.txt)
   6
   7   -->
   8 <title>Boost Graph Library: is_kuratowski_subgraph</title>
   9 </head>
  10 <body alink="#ff0000"
  11       bgcolor="#ffffff"
  12       link="#0000ee"
  13       text="#000000"
  14       vlink="#551a8b">
  15 <img src="../../../boost.png" alt="C++ Boost" height="86" width="277">
  16
  17 <br clear="">
  18
  19 <h1><tt>is_kuratowski_subgraph</tt></h1>
  20
  21 <pre>template &lt;typename Graph, typename ForwardIterator, typename VertexIndexMap&gt;
  22 bool is_kuratowski_subgraph(const Graph&amp; g, ForwardIterator begin, ForwardIterator end, VertexIndexMap vm)
  23 </pre>
  24
  25 <p>
  26
  27 <tt>is_kuratowski_subgraph(g, begin, end)</tt> returns <tt>true</tt> exactly
  28 when the sequence of edges defined by the range <tt>[begin, end)</tt> forms a
  29 <a href="./planar_graphs.html#kuratowskisubgraphs"> Kuratowski subgraph</a> in
  30 the graph <tt>g</tt>. If you need to verify that an arbitrary graph has a
  31 <i>K<sub>5</sub></i> or <i>K<sub>3,3</sub></i> minor,  you should use the
  32 function <tt><a href="boyer_myrvold.html">boyer_myrvold_planarity_test</a></tt>
  33 to isolate such a minor instead of this function. <tt>is_kuratowski_subgraph
  34 </tt> exists to aid in testing and verification of the function
  35 <tt>boyer_myrvold_planarity_test</tt>, and for that reason, it expects its
  36 input to be a restricted set of edges forming a Kuratowski subgraph, as
  37 described in detail below.
  38 <p>
  39 <tt>is_kuratowski_subgraph</tt> creates a temporary graph out of the sequence
  40 of edges given and repeatedly contracts edges until it ends up with a graph
  41 with either all edges of degree 3 or all edges of degree 4. The final
  42 contracted graph is then checked against <i>K<sub>5</sub></i> or
  43 <i>K<sub>3,3</sub></i> using the Boost Graph Library's
  44 <a href="isomorphism.html">isomorphism</a>
  45 function. The contraction process starts by choosing edges adjacent to a vertex
  46 of degree 1 and contracting those. When none are left, it moves on to edges
  47 adjacent to a vertex of degree 2. If only degree 3 vertices are left after this
  48 stage, the graph is checked against <i>K<sub>3,3</sub></i>. Otherwise, if
  49 there's at least one degree 4 vertex, edges adjacent to degree 3 vertices are
  50 contracted as neeeded and the final graph is compared to <i>K<sub>5</sub></i>.
  51 <p>
  52 In order for this process to be deterministic, we make the following two
  53 restrictions on the input graph given to <tt>is_kuratowski_subgraph</tt>:
  54 <ol>
  55 <li>No edge contraction needed to produce a kuratowski subgraph results in
  56 multiple edges between the same pair of vertices (No edge <i>{a,b}</i> will be
  57 contracted at any point in the contraction process if <i>a</i> and <i>b</i>
  58 share a common neighbor.)
  59 </li><li>If the graph contracts to a <i>K<sub>5</sub></i>, once the graph has
  60 been contracted to only vertices of degree at least 3, no cycles exist that
  61 contain solely degree 3 vertices.
  62 </li></ol>
  63 The second restriction is needed both to discriminate between targeting a
  64 <i>K<sub>5</sub></i> or a <i>K<sub>3,3</sub></i> and to determinstically
  65 contract the vertices of degree 4 once the <i>K<sub>5</sub></i> has been
  66 targeted. The Kuratowski subgraph output by the function <tt>
  67 <a href="boyer_myrvold.html">boyer_myrvold_planarity_test</a></tt> is
  68 guaranteed to meet both of the above requirements.
  69
  70
  71 <h3>Complexity</h3>
  72
  73 On a graph with <i>n</i> vertices, this function runs in time <i>O(n)</i>.
  74
  75 <h3>Where Defined</h3>
  76
  77 <p>
  78 <a href="../../../boost/graph/is_kuratowski_subgraph.hpp">
  79 <tt>boost/graph/is_kuratowski_subgraph.hpp</tt>
  80 </a>
  81
  82 </p><h3>Parameters</h3>
  83
  84 IN: <tt>Graph&amp; g</tt>
  85
  86 <blockquote>
  87 An undirected graph with no self-loops or parallel edges. The graph type must
  88 be a model of <a href="VertexListGraph.html">Vertex List Graph</a>.
  89 </blockquote>
  90
  91 IN: <tt>ForwardIterator</tt>
  92
  93 <blockquote>
  94 A ForwardIterator with value_type
  95 <tt>graph_traits&lt;Graph&gt;::edge_descriptor</tt>.
  96 </blockquote>
  97
  98 IN: <tt>VertexIndexMap vm</tt>
  99
 100 <blockquote>
 101 A <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map
 102 </a> that maps vertices from <tt>g</tt> to distinct integers in the range
 103 <tt>[0, num_vertices(g) )</tt><br>
 104 <b>Default</b>: <tt>get(vertex_index,g)</tt><br>
 105 </blockquote>
 106
 107
 108 <h3>Example</h3>
 109
 110 <p>
 111 <a href="../example/kuratowski_subgraph.cpp">
 112 <tt>examples/kuratowski_subgraph.cpp</tt>
 113 </a>
 114
 115 </p><h3>See Also</h3>
 116
 117 <p>
 118 <a href="planar_graphs.html">Planar Graphs in the Boost Graph Library</a>
 119
 120
 121 <br>
 122 </p><hr>
 123 Copyright © 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com">
 124 aaron.windsor@gmail.com</a>)
 125
 126 </body></html>