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 22A planar embedding is an important intermediate representation of a drawing 23of a planar graph. Instead of specifying the absolute positions of the vertices 24and edges in the plane, a planar embedding specifies their positions relative 25to one another. A planar embedding consists of a sequence, for each vertex in 26the graph, of all of the edges incident on that vertex in the order in which 27they are to be drawn around that vertex. 28<p> 29A planar embedding is a refinement of 30<a href="../../property_map/doc/LvaluePropertyMap.html">LValuePropertyMap</a> that 31places additional restrictions the <tt>value_type</tt> used in the property 32map. 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<Graph>::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<Graph>::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<Embedding>::value_type::const_iterator 78</tt> 79</td> 80<td> The iterator type used to iterate over the ordering of the edges in the 81planar 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<Embedding>::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<Embedding>::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 128Starting with an empty embedding, any mixed sequence of <i>n</i> calls to a 129particular vertex's <tt>push_back</tt> and <tt>clear</tt> should take 130<i>O(n)</i> time. 131 132<h3>Models</h3> 133 134Any LValue property map that maps vertices to a <tt>std::vector</tt>, 135<tt>std::list</tt>, or <tt>std::deque</tt> models this 136concept. Below is an example of using this approach to create a model of 137PlanarEmbedding: 138 139<pre> 140#include <boost/property_map/property_map.hpp> 141#include <vector> 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 149typedef 150 std::vector< std::vector< graph_traits<Graph>::edge_descriptor > > 151 planar_embedding_storage_t; 152 153// A typedef for the iterator property map, assuming the graph has 154// an interior vertex index map 155typedef 156 boost::iterator_property_map< planar_embedding_storage_t::iterator, 157 property_map<Graph, vertex_index_t>::type 158 > 159 planar_embedding_t; 160 161// Create an instance of the storage and the property map 162planar_embedding_storage_t planar_embedding_storage(num_vertices(g)); 163planar_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> 175Copyright � 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com"> 176aaron.windsor@gmail.com</a>) 177 178</body></html> 179
