123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178 |
- <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 © 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com">
- aaron.windsor@gmail.com</a>)
- </body></html>
|