平面嵌入概念 - Boost C++ 函数库

平面嵌入概念

平面嵌入是平面图绘制的重要中间表示。平面嵌入不指定顶点和边在平面中的绝对位置，而是指定它们之间的相对位置。平面嵌入由一个序列组成，对于图中的每个顶点，包含所有与该顶点相连的边，并按围绕该顶点绘制的顺序排列。

平面嵌入是对 LValuePropertyMap 的细化，它对value_type在属性映射中使用。

符号约定

`嵌入`	是一个对平面嵌入概念进行建模的类型。
`embedding`	是一个对象，类型为`嵌入`.
`图`	是底层图的类型。
`e`	是一个对象，类型为`graph_traits<Graph>::edge_descriptor`.
`v`	是一个对象，类型为`graph_traits<Graph>::vertex_descriptor`.

关联类型

常量迭代器 boost::property_traits<Embedding>::value_type::const_iterator 用于迭代特定顶点平面嵌入中的边顺序的迭代器类型

有效表达式

表达式	返回类型	描述
`embedding[v].begin()`	`boost::property_traits<Embedding>::value_type::const_iterator`	返回指向顶点 v 周围嵌入中的边范围开始的迭代器
`embedding[v].end()`	`boost::property_traits<Embedding>::value_type::const_iterator`	返回指向顶点 v 周围嵌入中的边范围结束的迭代器
`embedding[v].clear()`	`void`	清除顶点周围嵌入中的所有边`v`
`embedding[v].push_back(e)`	`void`	添加一条边`e`到顶点周围嵌入边序列的末尾`v`

复杂性保证

从一个空嵌入开始，对特定顶点的任何混合调用序列 n 次push_backandclear应花费 O(n) 时间。

模型

任何将顶点映射到std::vector, std::list或std::deque的 LValue 属性映射都对这个概念进行建模。下面是一个使用这种方法创建 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.

Boost C++ 库

平面嵌入概念

符号约定

关联类型

有效表达式

复杂性保证

模型