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.
Планарное встраивание - это уточнениеLValuePropertyMap, которое устанавливает дополнительные ограничениязначения_типа, используемого в карте свойств.
Notation
Встраивание
Это тип, который моделирует концепцию Planar Embedding.
Встраивание
является объектом типаВведение.
График
Это тип базового графа.
е
является объектом типаgraph_traits::edge_descriptor.
против
является объектом типаgraph_traits::vertex_descriptor.
Тип итератора, используемый для итерации по упорядочиванию краев в плоском встраивании определенной вершины
Valid Expressions
Выражение
Возвращение Тип
Описание
встраивание [v].begin
бустер::value_traits<]
встраивание [v].end
бустер::property_traits<]
встраивание::property_traits]:::value_traits
возвращает итератор в конец диапазона краев в встраивании вокруг вершины
встраивание
в встраивании вокруг вершиныв встраиваниив введении
в введениив
Complexity Guarantees
Starting with an empty embedding, any mixed sequence of n calls to a
particular vertex's push_back and clear should take
O(n) time.
Models
Any LValue property map that maps vertices to a std::vector,
std::list, or std::deque models this
concept. Below is an example of using this approach to create a model of
PlanarEmbedding:
#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.
