1

我是 boost 的新手，也是 boost 图形库的新手。谁能解释一下property_map背后的实现以及以下代码中运算符[]的时间复杂度是多少？

谢谢！

#include <string>
#include <boost/graph/adjacency_list.hpp>
int main()
{
  using namespace boost;
  typedef adjacency_list<listS, listS, directedS,
    property<vertex_name_t, std::string> > graph_t;
  graph_t g;
  graph_traits<graph_t>::vertex_descriptor u = add_vertex(g);
  property_map<graph_t, vertex_name_t>::type name_map = get(vertex_name, g);
  name_map[i] = "Joe";
  return EXIT_SUCCESS;
}
4

2 回答 2

0

您可以通过向其提供std::map来创建属性映射。所以时间和空间复杂度可能与底层的std::map相同。您可能想深入了解Sorted Associative Container的 STL 文档。

于 2013-09-20T06:44:14.937 回答
0

我自己也想知道这一点，并且发现 boost::graph 文档没有说明这一点很奇怪，因为诸如此类的问题与性能关键算法/应用程序高度相关。

总之，我相信答案是肯定的，它是 O(1) 时间复杂度。我的推理如下。

由于属性映射概念只是概念，因此不能保证复杂性。所以我们必须查看 adjacency_list 的属性映射实现来了解它的复杂性。我相信相关代码可以在boost/graph/detail/adjacency_list.hpp中找到；搜索“顶点属性映射”。

template <class Graph, class ValueType, class Reference, class Tag>
struct adj_list_vertex_property_map
  : public boost::put_get_helper<
      Reference,
      adj_list_vertex_property_map<Graph, ValueType, Reference, Tag>
    >
{
  typedef typename Graph::stored_vertex StoredVertex;
  typedef ValueType value_type;
  typedef Reference reference;
  typedef typename Graph::vertex_descriptor key_type;
  typedef boost::lvalue_property_map_tag category;
  inline adj_list_vertex_property_map(const Graph* = 0, Tag tag = Tag()): m_tag(tag) { }
  inline Reference operator[](key_type v) const {
    StoredVertex* sv = (StoredVertex*)v;
    return get_property_value(sv->m_property, m_tag);
  }
  inline Reference operator()(key_type v) const {
    return this->operator[](v);
  }
  Tag m_tag;
};

我相信这是用于使用 ListS VertexList 类型实例化的 adjacency_list 的内部属性的属性映射，如您的示例所示。您可以看到 operator[] 采用 Graph::vertex_descriptor 似乎是某个句柄，可能是一个迭代器，并直接访问属性结构而无需查找sv->m_property，因此是常数时间。当您有多个与每个顶点关联的属性时，调用get_property_value()似乎是用于属性标记解析；在你的情况下，你只有一个。标签查找通常也是常数时间。

使用 VecS VertexList 类型的属性实例化 adjacency_list 似乎也会在属性映射查找中给出 O(1) 时间复杂度。那里使用的类型似乎是vec_adj_list_vertex_property_map并且操作符 [] 使用 Graph::vector_descriptor 似乎是每个顶点属性向量的索引，因此 O(1)。

回想起来，我想我会期望，因为库非常努力地工作以保持高性能，它会确保这也是高性能的。

于 2014-11-07T17:54:58.487 回答