179 lines
4.7 KiB
HTML
179 lines
4.7 KiB
HTML
<html><head><!-- Copyright 2007 Aaron Windsor
|
||
|
||
Distributed under the Boost Software License, Version 1.0.
|
||
(See accompanying file LICENSE_1_0.txt or copy at
|
||
http://www.boost.org/LICENSE_1_0.txt)
|
||
|
||
-->
|
||
<title>Planar Embedding Concept</title>
|
||
</head>
|
||
<body alink="#ff0000"
|
||
bgcolor="#ffffff"
|
||
link="#0000ee"
|
||
text="#000000"
|
||
vlink="#551a8b">
|
||
<img src="../../../boost.png" alt="C++ Boost" height="86" width="277">
|
||
|
||
<br clear="">
|
||
|
||
<h1>Planar Embedding Concept</h1>
|
||
|
||
|
||
A planar embedding is an important intermediate representation of a drawing
|
||
of a planar graph. Instead of specifying the absolute positions of the vertices
|
||
and edges in the plane, a planar embedding specifies their positions relative
|
||
to one another. A planar embedding consists of a sequence, for each vertex in
|
||
the graph, of all of the edges incident on that vertex in the order in which
|
||
they are to be drawn around that vertex.
|
||
<p>
|
||
A planar embedding is a refinement of
|
||
<a href="../../property_map/doc/LvaluePropertyMap.html">LValuePropertyMap</a> that
|
||
places additional restrictions the <tt>value_type</tt> used in the property
|
||
map.
|
||
|
||
</p><h3>Notation</h3>
|
||
|
||
<table>
|
||
<tbody>
|
||
|
||
<tr>
|
||
<td> <tt>Embedding</tt> </td>
|
||
<td> is a type that models the Planar Embedding concept.</td>
|
||
</tr>
|
||
|
||
<tr>
|
||
<td> <tt>embedding</tt> </td>
|
||
<td> is an object of type <tt>Embedding</tt>. </td>
|
||
</tr>
|
||
|
||
<tr>
|
||
<td> <tt>Graph</tt> </td>
|
||
<td> is the type of the underlying graph.</td>
|
||
</tr>
|
||
|
||
<tr>
|
||
<td> <tt>e</tt> </td>
|
||
<td> is an object of type <tt>graph_traits<Graph>::edge_descriptor</tt>.
|
||
</td>
|
||
</tr>
|
||
|
||
<tr>
|
||
<td> <tt>v</tt> </td>
|
||
<td> is an object of type <tt>graph_traits<Graph>::vertex_descriptor
|
||
</tt>.</td>
|
||
|
||
</tr><tr>
|
||
<td>
|
||
|
||
</td></tr></tbody></table>
|
||
|
||
|
||
<h3>Associated Types</h3>
|
||
|
||
<table border="1">
|
||
|
||
<tbody><tr>
|
||
<td> Const Iterator </td>
|
||
<td> <tt>boost::property_traits<Embedding>::value_type::const_iterator
|
||
</tt>
|
||
</td>
|
||
<td> The iterator type used to iterate over the ordering of the edges in the
|
||
planar embedding of a particular vertex
|
||
</td>
|
||
</tr>
|
||
|
||
</tbody></table>
|
||
|
||
<h3>Valid Expressions</h3>
|
||
|
||
<p>
|
||
|
||
<table border="1">
|
||
|
||
<tbody><tr><th>Expression</th><th>Return Type</th><th>Description</th>
|
||
|
||
</tr><tr>
|
||
<td> <tt>embedding[v].begin()</tt> </td>
|
||
<td> <tt>boost::property_traits<Embedding>::value_type::const_iterator
|
||
</tt></td>
|
||
<td> Returns an iterator to the beginning of the range of edges in the
|
||
embedding around vertex v</td>
|
||
</tr>
|
||
|
||
<tr>
|
||
<td> <tt>embedding[v].end()</tt> </td>
|
||
<td> <tt>boost::property_traits<Embedding>::value_type::const_iterator
|
||
</tt></td>
|
||
<td> Returns an iterator to the end of the range of edges in the
|
||
embedding around vertex v</td>
|
||
</tr>
|
||
|
||
<tr>
|
||
<td> <tt>embedding[v].clear()</tt> </td>
|
||
<td> <tt>void</tt></td>
|
||
<td> Clears all edges in the embedding around a vertex <tt>v</tt></td>
|
||
</tr>
|
||
|
||
<tr>
|
||
<td> <tt>embedding[v].push_back(e)</tt> </td>
|
||
<td> <tt>void</tt></td>
|
||
<td> Adds an edge <tt>e</tt> to the end of the sequence of embedded edges
|
||
around the vertex <tt>v</tt> </td>
|
||
</tr>
|
||
|
||
</tbody></table>
|
||
|
||
</p><h3>Complexity Guarantees</h3>
|
||
|
||
Starting with an empty embedding, any mixed sequence of <i>n</i> calls to a
|
||
particular vertex's <tt>push_back</tt> and <tt>clear</tt> should take
|
||
<i>O(n)</i> time.
|
||
|
||
<h3>Models</h3>
|
||
|
||
Any LValue property map that maps vertices to a <tt>std::vector</tt>,
|
||
<tt>std::list</tt>, or <tt>std::deque</tt> models this
|
||
concept. Below is an example of using this approach to create a model of
|
||
PlanarEmbedding:
|
||
|
||
<pre>
|
||
#include <boost/property_map/property_map.hpp>
|
||
#include <vector>
|
||
|
||
...
|
||
|
||
// Assume a graph type "Graph" defined somewhere above and
|
||
// an instance of Graph in a variable g.
|
||
|
||
// A typedef for the storage - a vector of vectors of edge descriptors
|
||
typedef
|
||
std::vector< std::vector< graph_traits<Graph>::edge_descriptor > >
|
||
planar_embedding_storage_t;
|
||
|
||
// A typedef for the iterator property map, assuming the graph has
|
||
// an interior vertex index map
|
||
typedef
|
||
boost::iterator_property_map< planar_embedding_storage_t::iterator,
|
||
property_map<Graph, vertex_index_t>::type
|
||
>
|
||
planar_embedding_t;
|
||
|
||
// Create an instance of the storage and the property map
|
||
planar_embedding_storage_t planar_embedding_storage(num_vertices(g));
|
||
planar_embedding_t planar_embedding(planar_embedding_storage.begin(),
|
||
get(vertex_index, g)
|
||
);
|
||
|
||
// planar_embedding can now be passed to any function expecting a model
|
||
// of PlanarEmbedding.
|
||
</pre>
|
||
|
||
<p>
|
||
|
||
<br>
|
||
</p><hr>
|
||
Copyright <20> 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com">
|
||
aaron.windsor@gmail.com</a>)
|
||
|
||
</body></html>
|