ceph/src/boost/libs/graph/doc/PlanarEmbedding.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>Planar Embedding Concept</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>Planar Embedding Concept</h1>
  20
  21
  22 A planar embedding is an important intermediate representation of a drawing
  23 of a planar graph. Instead of specifying the absolute positions of the vertices
  24 and edges in the plane, a planar embedding specifies their positions relative
  25 to one another. A planar embedding consists of a sequence, for each vertex in
  26 the graph, of all of the edges incident on that vertex in the order in which
  27 they are to be drawn around that vertex.
  28 <p>
  29 A planar embedding is a refinement of
  30 <a href="../../property_map/doc/LvaluePropertyMap.html">LValuePropertyMap</a> that
  31 places additional restrictions the <tt>value_type</tt> used in the property
  32 map.
  33
  34 </p><h3>Notation</h3>
  35
  36 <table>
  37 <tbody>
  38
  39 <tr>
  40 <td> <tt>Embedding</tt> </td>
  41 <td> is a type that models the Planar Embedding concept.</td>
  42 </tr>
  43
  44 <tr>
  45 <td> <tt>embedding</tt> </td>
  46 <td> is an object of type <tt>Embedding</tt>. </td>
  47 </tr>
  48
  49 <tr>
  50 <td> <tt>Graph</tt> </td>
  51 <td> is the type of the underlying graph.</td>
  52 </tr>
  53
  54 <tr>
  55 <td> <tt>e</tt> </td>
  56 <td> is an object of type <tt>graph_traits&lt;Graph&gt;::edge_descriptor</tt>.
  57 </td>
  58 </tr>
  59
  60 <tr>
  61 <td> <tt>v</tt> </td>
  62 <td> is an object of type <tt>graph_traits&lt;Graph&gt;::vertex_descriptor
  63 </tt>.</td>
  64
  65 </tr><tr>
  66 <td>
  67
  68 </td></tr></tbody></table>
  69
  70
  71 <h3>Associated Types</h3>
  72
  73 <table border="1">
  74
  75 <tbody><tr>
  76 <td> Const Iterator  </td>
  77 <td> <tt>boost::property_traits&lt;Embedding&gt;::value_type::const_iterator
  78 </tt>
  79 </td>
  80 <td> The iterator type used to iterate over the ordering of the edges in the
  81 planar embedding of a particular vertex
  82 </td>
  83 </tr>
  84
  85 </tbody></table>
  86
  87 <h3>Valid Expressions</h3>
  88
  89 <p>
  90
  91 <table border="1">
  92
  93 <tbody><tr><th>Expression</th><th>Return Type</th><th>Description</th>
  94
  95 </tr><tr>
  96 <td> <tt>embedding[v].begin()</tt>  </td>
  97 <td> <tt>boost::property_traits&lt;Embedding&gt;::value_type::const_iterator
  98      </tt></td>
  99 <td> Returns an iterator to the beginning of the range of edges in the
 100      embedding around vertex v</td>
 101 </tr>
 102
 103 <tr>
 104 <td> <tt>embedding[v].end()</tt>  </td>
 105 <td> <tt>boost::property_traits&lt;Embedding&gt;::value_type::const_iterator
 106      </tt></td>
 107 <td> Returns an iterator to the end of the range of edges in the
 108      embedding around vertex v</td>
 109 </tr>
 110
 111 <tr>
 112 <td> <tt>embedding[v].clear()</tt>  </td>
 113 <td> <tt>void</tt></td>
 114 <td> Clears all edges in the embedding around a vertex <tt>v</tt></td>
 115 </tr>
 116
 117 <tr>
 118 <td> <tt>embedding[v].push_back(e)</tt>  </td>
 119 <td> <tt>void</tt></td>
 120 <td> Adds an edge <tt>e</tt> to the end of the sequence of embedded edges
 121      around the vertex <tt>v</tt> </td>
 122 </tr>
 123
 124 </tbody></table>
 125
 126 </p><h3>Complexity Guarantees</h3>
 127
 128 Starting with an empty embedding, any mixed sequence of <i>n</i> calls to a
 129 particular vertex's <tt>push_back</tt> and <tt>clear</tt> should take
 130 <i>O(n)</i> time.
 131
 132 <h3>Models</h3>
 133
 134 Any LValue property map that maps vertices to a <tt>std::vector</tt>,
 135 <tt>std::list</tt>, or <tt>std::deque</tt> models this
 136 concept. Below is an example of using this approach to create a model of
 137 PlanarEmbedding:
 138
 139 <pre>
 140 #include &lt;boost/property_map/property_map.hpp&gt;
 141 #include &lt;vector&gt;
 142
 143 ...
 144
 145 // Assume a graph type "Graph" defined somewhere above and
 146 // an instance of Graph in a variable g.
 147
 148 // A typedef for the storage - a vector of vectors of edge descriptors
 149 typedef
 150     std::vector&lt; std::vector&lt; graph_traits&lt;Graph&gt;::edge_descriptor &gt; &gt;
 151     planar_embedding_storage_t;
 152
 153 // A typedef for the iterator property map, assuming the graph has
 154 // an interior vertex index map
 155 typedef
 156     boost::iterator_property_map&lt; planar_embedding_storage_t::iterator,
 157                                   property_map&lt;Graph, vertex_index_t&gt;::type
 158                                 &gt;
 159     planar_embedding_t;
 160
 161 // Create an instance of the storage and the property map
 162 planar_embedding_storage_t planar_embedding_storage(num_vertices(g));
 163 planar_embedding_t planar_embedding(planar_embedding_storage.begin(),
 164                                     get(vertex_index, g)
 165                                     );
 166
 167 // planar_embedding can now be passed to any function expecting a model
 168 // of PlanarEmbedding.
 169 </pre>
 170
 171 <p>
 172
 173 <br>
 174 </p><hr>
 175 Copyright © 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com">
 176 aaron.windsor@gmail.com</a>)
 177
 178 </body></html>