1

私はグラフライブラリをブーストし、ブーストするのも初めてです。次のコードで、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()各頂点に複数のプロパティが関連付けられている場合、への呼び出しはプロパティ タグの解決のためのように見えます。あなたの場合、あなたは1つしか持っていません。通常、タグ検索も一定時間です。

VecS VertexList タイプのプロパティを使用して adjacency_list をインスタンス化すると、プロパティ マップのルックアップで O(1) 時間の複雑さが生じるようにも見えます。そこで使用されている型は存在するようでvec_adj_list_vertex_property_mapあり、opearator[] は Graph::vector_descriptor を、頂点ごとのプロパティのベクトルへのインデックスのように見えるもの、つまり O(1) で使用します。

振り返ってみると、ライブラリはパフォーマンスを向上させるために非常に熱心に機能するため、これも確実にパフォーマンスが向上することを期待していると思います。

于 2014-11-07T17:54:58.487 に答える