1 <html><head><!-- Copyright 2007 Aaron Windsor
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)
8 <title>Planar Embedding Concept
</title>
15 <img src=
"../../../boost.png" alt=
"C++ Boost" height=
"86" width=
"277">
19 <h1>Planar Embedding Concept
</h1>
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.
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
40 <td> <tt>Embedding
</tt> </td>
41 <td> is a type that models the Planar Embedding concept.
</td>
45 <td> <tt>embedding
</tt> </td>
46 <td> is an object of type
<tt>Embedding
</tt>.
</td>
50 <td> <tt>Graph
</tt> </td>
51 <td> is the type of the underlying graph.
</td>
56 <td> is an object of type
<tt>graph_traits
<Graph
>::edge_descriptor
</tt>.
62 <td> is an object of type
<tt>graph_traits
<Graph
>::vertex_descriptor
68 </td></tr></tbody></table>
71 <h3>Associated Types
</h3>
76 <td> Const Iterator
</td>
77 <td> <tt>boost::property_traits
<Embedding
>::value_type::const_iterator
80 <td> The iterator type used to iterate over the ordering of the edges in the
81 planar embedding of a particular vertex
87 <h3>Valid Expressions
</h3>
93 <tbody><tr><th>Expression
</th><th>Return Type
</th><th>Description
</th>
96 <td> <tt>embedding[v].begin()
</tt> </td>
97 <td> <tt>boost::property_traits
<Embedding
>::value_type::const_iterator
99 <td> Returns an iterator to the beginning of the range of edges in the
100 embedding around vertex v
</td>
104 <td> <tt>embedding[v].end()
</tt> </td>
105 <td> <tt>boost::property_traits
<Embedding
>::value_type::const_iterator
107 <td> Returns an iterator to the end of the range of edges in the
108 embedding around vertex v
</td>
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>
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>
126 </p><h3>Complexity Guarantees
</h3>
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
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
140 #include
<boost/property_map/property_map.hpp
>
141 #include
<vector
>
145 // Assume a graph type
"Graph" defined somewhere above and
146 // an instance of Graph in a variable g.
148 // A typedef for the storage - a vector of vectors of edge descriptors
150 std::vector
< std::vector
< graph_traits
<Graph
>::edge_descriptor
> >
151 planar_embedding_storage_t;
153 // A typedef for the iterator property map, assuming the graph has
154 // an interior vertex index map
156 boost::iterator_property_map
< planar_embedding_storage_t::iterator,
157 property_map
<Graph, vertex_index_t
>::type
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(),
167 // planar_embedding can now be passed to any function expecting a model
168 // of PlanarEmbedding.
175 Copyright ©
2007 Aaron Windsor (
<a href=
"mailto:aaron.windsor@gmail.com">
176 aaron.windsor@gmail.com
</a>)