#
Using `adjacency_list`

この節では `adjacency_list` の使い方を詳しく説明する。この説明は以下の 3 つの話題に分かれている。

1. Choosing the `Edgelist` and `VertexList`
2. Directed and Undirected Adjacency Lists
3. Internal Properties
4. Customizing the Adjacency List Storage

##
Choosing the `Edgelist` and `VertexList`

この節では、様々な異なる状況で `adjacency_list` のどのバージョンを使うかに焦点を当てる。 `adjacency_list` はスイスアーミーナイフのように様々な設定が可能だ。この節で焦点を当てるパラメータは `EdgeList` と `VertexList` である。これらは、グラフを表すために使われる、裏に潜むデータ構造を制御するものだ。 `EdgeList` と `VertexList` の選択は、多くのグラフ操作の時間計算量と、グラフオブジェクトの空間計算量に影響する。

BGL では、頂点の集合とグラフの隣接構造 (入辺と出辺) を表すために STL コンテナ (`std::vector` 、 `std::list` 、 `std::set`) を使う。 `EdgeList` と `VertexList` 用のコンテナを選択するための選択子型がある。

- `vecS` は `std::vector` を選択する。
- `listS` は `std::list` を選択する。
- `slistS` は `std::slist` を選択する。
- `setS` は `std::set` を選択する。
- `multisetS` は `std::multiset` を選択する。
- `hash_setS` は `std::hash_set` を選択する。

### Choosing the `VertexList` type

`VertexList` パラメータによって、頂点リスト、又はグラフの二次元構造を表すのにどの種類のコンテナを使うのかが決まる。指定されるコンテナは Sequence か RandomAccessContainer のモデルでなければならない。一般に、高速に頂点の追加、削除をする必要が有れば、 `listS` が良い選択だ。この選択の欠点は、 `vecS` に比べて余分な空間オーバヘッドが有る事だ。

#### Space Complexity

`std::list` を使った場合の頂点あたりの空間オーバヘッドは `std::vector` より大きい。 1 頂点当たり 3 つの余分なポインタが必要だ。

#### Time Complexity

`VertexList` の選択は以下の操作の時間計算量に影響する。

-     add_vertex()

  `vecS` 、 `listS` のどちらの場合も、この操作には償却定数時間がかかる (`push_back()` で実装されている) 。しかし、 `VertexList` 型が `vecS` の場合、この操作の所要時間は時々大きくなる。ベクタが再割り当てされてグラフ全体がコピーされるからだ。

-     remove_vertex()

  この操作には `listS` では定数時間、 `vecS` では O(V + E) の時間がかかる。 `vecS` での時間計算量が大きいのは、グラフ全体の出辺の頂点記述子 (この場合は頂点リスト内での頂点の場所に対応したインデックス) を調整しなければならないからだ。

-     vertex()

  この操作には、 `vecS` でも `listS` でも定数時間がかかる。

### Choosing the `EdgeList` type

`EdgeList` パラメータによって、グラフ内の各頂点に出辺 (と場合によっては入辺) を格納するのに使うコンテナが決まる。辺リストに使うコンテナは Sequence か AssociativeContainer のどちらかの要求を満たす必要が有る。

`EdgeList` を選ぶ時にまず考えるべき事の 1 つが、 `adjacency_list` に多重辺が存在しない事を強制する (つまり、グラフが多重グラフにならない事を強制する) かどうかだ。これを強制したければ `setS` 選択子か `hash_setS` 選択子を使う。多重グラフを表現したいか、グラフに多重辺を挿入しない事が分かっている場合は、 Sequence 型の内 1 つ (`vecS` か `listS` か `slistS`) を選ぶ。様々なグラフ操作の時間計算量や空間計算量の違いも考慮に入れたい所だろう。以下で V はグラフ内の頂点の総数を、 E は辺の総数を表す。ここに記述されていない操作は定数時間だ。

#### Space Complexity

`EdgeList` の選択は、グラフオブジェクト内の辺当たりの空間オーバヘッドの量に影響する。空間が小さい方から順に選択子を並べると、 `vecS` 、 `slistS` 、 `listS` 、 `setS` である。

#### Time Complexity

以下の様々な操作の時間計算量の説明の中で、「大文字の O 」表記内の E/V は出辺のリストの長さを表す。これは厳密には正しくなく、 E/V はランダムなグラフ内の 1 頂点当たりの平均辺数を表すだけだ。 1 頂点からの出辺の最悪の場合の数は (多重グラフでなければ) V である。疎なグラフでは一般に E/V は V よりずっと小さく、定数とみなせる。

-     add_edge()

  `EdgeList` が `std::set` のような UniqueAssociativeContainer であれば、辺の追加時に多重辺が無いことが強制される。それに伴う余分な探索の時間計算量は O(log(E/V)) だ。 Sequence をモデルとする `EdgeList` 型ではこのチェックは行われず、よって `add_edge()` にかかるのは償却定数時間だ。つまり、グラフが多重辺を持つかを気にしない場合や、グラフへの入力が多重辺を持たないと分かっている場合は、シーケンス準拠の `EdgeList` を使った方がいいという事だ。 シーケンス準拠の `EdgeList` の `add_edge()` は `push_front()` か `push_back()` で実装されている。しかし一般に、時々再割り当てして全要素をコピーする `std::vector` よりは、 `std::list` や `std::slist` の方が、この操作を高速に行える。

-     remove_edge()

  シーケンス準拠の `EdgeList` 型では、この操作は `std::remove_if()` で実装されているため、平均時間は E/V だ。集合準拠の `EdgeList` 型では `erase()` メンバ関数で実装されているため、平均時間は log(E/V) だ。

-     edge()

  この操作の時間計算量は、 `EdgeList` 型が Sequence であれば O(E/V) 、 `EdgeList` 型が AssociativeContainer であれば O(log(E/V)) である。

-     clear_vertex()

  シーケンス準拠の `EdgeList` 型の有向グラフでは、時間計算量は O(V + E) だ。連想コンテナ準拠の `EdgeList` 型ではそれより速く、時間計算量は O(V log(E/V)) だ。無向グラフではこの操作は O(E2/V2) か O(E/V log(E/V)) だ。

-     remove_vertex()

  `EdgeList` 型に依らず、この操作の時間計算量は O(V + E) だ。

-     out_edge_iterator::operator++()

  全ての `OneD` 型について、この操作は定数時間だ。しかし、型によって時間の定数項は大きく異なる。この操作は多くのグラフアルゴリズムで頻用されるので、この違いは重要だ。この操作の速さは、速い物から順に `vecS` 、 `slistS` 、 `listS` 、 `setS` 、 `hash_setS` だ。

-     in_edge_iterator::operator++()

  この操作は定数時間だ。 `EdgeList` の選択に対するこの操作の速さの順序は、 `out_edge_iterator` の場合と同様だ。

-     vertex_iterator::operator++()

  この操作は定数時間であり、高速だ (ポインタのインクリメントと同じ速さだ) 。 `OneD` の選択はこの操作の速さには影響しない。

-     edge_iterator::operator++()

  この操作は定数時間だ。 `EdgeList` の選択に対するこの操作の速さの順序は、 `out_edge_iterator` の場合と同様だ。辺集合全体をトラバースする時間は O(V + E) だ。

-     adjacency_iterator::operator++()

  この操作は定数時間だ。 `EdgeList` の選択に対するこの操作の速さの順序は、 `out_edge_iterator` の場合と同様だ。

## Directed and Undirected Adjacency Lists

`adjacency_list` クラスは、 `Directed` テンプレートパラメータに渡す引数によって、有向グラフにも無向グラフにも使える。有向グラフを選ぶには `directedS` か `bidirectionalS` を使い、無向グラフを選ぶには `undirectedS` を使う。 BGL での有向グラフと無向グラフの違いについては、節 Undirected Graphs を参照。 `bidirectealS` 選択子を使うと、グラフには `out_edges()` 関数以外に `in_edges()` 関数も用意されるようになる。これによって 1 辺あたり 2 倍の空間が必要になるので、 `in_edges()` はオプションになっている。

## Internal Properties

プロパティインタフェースを使って、 `adjacency_list` グラフの頂点や辺にプロパティを付加できる。 `adjacency_list` クラスのテンプレートパラメータ `VertexProperty` と `EdgeProperty` にはプロパティクラスを指定する。プロパティクラスは以下のように宣言されている。

    template <class PropertyTag, class T, class NextProperty = no_property>
    struct property;

`PropertyTag` テンプレートパラメータは、プロパティに唯一の名前を付けるためだけに存在するタグクラスだ。あらかじめいくつかのタグが定義されているし、タグを追加するのも簡単だ。

      struct vertex_index_t { };
      struct vertex_index1_t { };
      struct vertex_index2_t { };
      struct edge_index_t { };
      struct graph_name_t { };
      struct vertex_name_t { };
      struct edge_name_t { };
      struct edge_weight_t { };
      struct edge_weight2_t { };
      struct edge_capacity_t { };
      struct edge_residual_capacity_t { };
      struct edge_reverse_t { };
      struct vertex_distance_t { };
      struct vertex_root_t { };
      struct vertex_all_t { };
      struct edge_all_t { };
      struct graph_all_t { };
      struct vertex_color_t { };
      struct vertex_rank_t { };
      struct vertex_predecessor_t { };
      struct vertex_isomorphism_t { };
      struct vertex_invariant_t { };
      struct vertex_invariant1_t { };
      struct vertex_invariant2_t { };
      struct vertex_degree_t { };
      struct vertex_out_degree_t { };
      struct vertex_in_degree_t { };
      struct vertex_discover_time_t { };
      struct vertex_finish_time_t { };

`property` の `T` テンプレートパラメータはプロパティの値型を指定する。型 `T` は Default Constructible 、 Assignable 、 Copy Constructible でなければならない。 C++ 標準ライブラリのコンテナのように、型 `T` のプロパティオブジェクトはグラフ内に値形式で保持される。

`NextProperty` パラメータを使えば、 `property` 型をネストさせる事ができる。これによって、同じグラフに任意の数のプロパティを付加できる。

頂点プロパティ型や辺プロパティ型をどうやって組み立て、グラフ型の作成に使うのかを、以下のコードで示す。ここでは、グラフの頂点に `float` 型の値を持つ距離プロパティと、 `std::string` 型の値を持つ名前プロパティを付加した。グラフの辺には `float` 型の値を持つ重みプロパティを付加した。

      typedef property<vertex_distance_t, float,
                property<vertex_name_t, std::string> > VertexProperty;
      typedef property<edge_weight_t, float> EdgeProperty;

      typedef adjacency_list<mapS, vecS, undirectedS,
                             VertexProperty, EdgeProperty> Graph;

      Graph g(num_vertices); // グラフオブジェクトを構築

プロパティの値はプロパティマップを使って読み書きされる。グラフからプロパティマップを得る方法については節 Interior Properties を、プロパティマップの使い方は節 Property Maps を参照。

### Custom Edge Properties

独自のプロパティ型やプロパティを作るのは簡単だ。新しいプロパティのためのタグクラスを定義するだけで良い。プロパティタグクラスには `num` と `kind` を定義しなければならない。 `num` は唯一の整数 ID 、 `kind` は `edge_property_tag` 、 `vertex_property_tag` 、 `graph_property_tag` のどれかである。

    struct flow_t {
      typedef edge_property_tag kind;
    };

    struct capacity_t {
      typedef edge_property_tag kind;
    };

タグ型を作るのに、 struct の代わりに enum を使う事もできる。まず、各プロパティについて列挙型を作る。列挙型の名前は `edge_` か `vertex_` か `graph_` で始まり、 `_t` で終わらなければならない。 enum の中で、列挙型の名前から `_t` を除いた名前を持つ値を定義する。そして `BOOST_INSTALL_PROPERTY` マクロを呼び出す。

    enum edge_myflow_t { edge_myflow };
    enum edge_mycapacity_t { edge_mycapacity };

    namespace boost {
      BOOST_INSTALL_PROPERTY(edge, myflow);
      BOOST_INSTALL_PROPERTY(edge, mycapacity);
    }

これでプロパティの定義の中で、組み込みのタグと同様に新しいプロパティタグを使える。

      typedef property<capacity_t, int> Cap;
      typedef property<flow_t, int, Cap> EdgeProperty;
      typedef adjacency_list<vecS, vecS, no_property, EdgeProperty> Graph;

前の例と同様、これらのプロパティ用のプロパティマップを `get(Property, g)` 関数を使って取得できる。

      property_map<Graph, capacity_t>::type capacity
        = get(capacity_t(), G);
      property_map<Graph, flow_t>::type flow
        = get(flow_t(), G);

この例の完全なソースコードはファイル `edge_property.cpp` に有る。

###
Custom Vertex Properties

頂点に付加する独自のプロパティを作る事は、辺の場合と同じく簡単だ。ここでは、グラフの頂点に人の名前を付加したいとする。

      struct first_vertex_name_t {
        typedef vertex_property_tag kind;
      };

これで新しいタグを `property` クラスで使えるようになり、それをグラフ型の組み立てに使えるようになる。以下のコードではグラフ型とグラフオブジェクトを作っている。ここでは辺を書き込み、頂点に名前を割り当てている。辺は「誰が誰に借金をしているか」を表している。

      typedef property<first_vertex_name_t, std::string> FirstNameProperty;
      typedef adjacency_list<vecS, vecS, directedS,
                             FirstNameProperty> MyGraphType;

      typedef pair<int,int> Pair;
      Pair edge_array[11] = { Pair(0,1), Pair(0,2), Pair(0,3),
                              Pair(0,4), Pair(2,0), Pair(3,0),
                              Pair(2,4), Pair(3,1), Pair(3,4),
                              Pair(4,0), Pair(4,1) };

      MyGraphType G(5);
      for (int i = 0; i < 11; ++i)
        add_edge(edge_array[i].first, edge_array[i].second, G);

      property_map<MyGraphType, first_vertex_name_t>::type
        name = get(first_vertex_name_t(), G);

      boost::put(name, 0, "Jeremy");
      boost::put(name, 1, "Rich");
      boost::put(name, 2, "Andrew");
      boost::put(name, 3, "Jeff");
      name[4] = "Kinis"; // operator[] も使える

      who_owes_who(edges(G).first, edges(G).second, G);

この例のために書いた `who_owes_who()` 関数はジェネリックな形式で実装されている。入力がテンプレート化されているので、実際のグラフ型を知る必要がない。名前プロパティのプロパティマップ型を求めるためには、 `property_map` 特性クラスを使う必要が有る。グラフパラメータが const なので、 `const_type` を使う。プロパティマップ型が求まれば、 `property_traits` クラスを使ってプロパティの値型を推論できる。この例では、プロパティの値型が `std::string` である事が分かっているが、このようにジェネリック流に書く事で、 `who_owes_who()` 関数は他のプロパティ値型でも使えるようになる。

      template <class EdgeIter, class Graph>
      void who_owes_who(EdgeIter first, EdgeIter last, const Graph& G)
      {
        // このグラフのプロパティアクセサ型にアクセス
        typedef typename property_map<Graph,
          first_vertex_name_t>::const_type NameMap;
        NameMap name = get(first_vertex_name, G);

        typedef typename boost::property_traits<NameMap>
          ::value_type NameType;

        NameType src_name, targ_name;

        while (first != last) {
          src_name = boost::get(name, source(*first, G));
          targ_name = boost::get(name, target(*first, G));
          cout << src_name << " owes "
               << targ_name << " some money" << endl;
          ++first;
        }

出力はこうなる。

    Jeremy owes Rich some money
    Jeremy owes Andrew some money
    Jeremy owes Jeff some money
    Jeremy owes Kinis some money
    Andrew owes Jeremy some money
    Andrew owes Kinis some money
    Jeff owes Jeremy some money
    Jeff owes Rich some money
    Jeff owes Kinis some money
    Kinis owes Jeremy some money
    Kinis owes Rich some money

この例の完全なソースコードは `interior_property_map.cpp` に有る。

## Customizing the Adjacency List Storage

`adjacency_list` は 2 種類のコンテナによって構築される。グラフ内の全頂点を保持するコンテナ型と、各頂点の出辺リスト (と場合によっては入辺リスト) を保持するコンテナだ。 BGL では、 STL のいくつかのコンテナからユーザが選択できるように、選択子クラスが用意されている。独自のコンテナ型を使う事も可能だ。 `VertexList` をカスタマイズする時は、以下に説明されるコンテナジェネレータを定義する必要が有る。 `EdgeList` をカスタマイズする時は、コンテナジェネレータと並列辺特性を定義する必要が有る。 `container_gen.cpp` に、カスタム記憶域型の使い方の例が有る。

### Container Generator

`adjacency_list` クラスは、 `EdgeList` 選択子と `VertexList` 選択子を、グラフの記憶域に使う実際のコンテナ型にマップするために、 `container_gen` という特性クラスを使う。この特性クラスのデフォルト版と、このクラスを `listS` 選択子用に特殊化する例を示す。

    namespace boost {
      template <class Selector, class ValueType>
      struct container_gen { };

      template <class ValueType>
      struct container_gen<listS, ValueType> {
        typedef std::list<ValueType> type;
      };
    }

他のコンテナを使うには、選択子クラスを定義し、 `container_gen` を自分の選択子用に特殊化する。

      struct custom_containerS { }; // 独自の選択子

      namespace boost {
        // 独自の選択子用の特殊化版
        template <class ValueType>
        struct container_gen<custom_containerS, ValueType> {
          typedef custom_container<ValueType> type;
        };
      }

`ValueType` 以外にもテンプレートパラメータを持つコンテナを使いたいという状況も有るだろう。例えば、アロケータ型を与えたい事も有るだろう。これを実現する 1 つの方法は、 `container_gen` の特殊化版の中で余分なパラメータを{直接与える/hard-code}事だ。もっと柔軟にしたければ、選択子クラスにテンプレートパラメータを加えればよい。以下のコードで、 `std::list` に使うアロケータを指定できる選択子の作り方を示す。

      template <class Allocator>
      struct list_with_allocatorS { };

      namespace boost {
        template <class Alloc, class ValueType>
        struct container_gen<list_with_allocatorS<Alloc>, ValueType>
        {
          typedef typename Alloc::template rebind<ValueType>::other Allocator;
          typedef std::list<ValueType, Allocator> type;
        };
      }

      // これで std::list と指定のアロケータを使うグラフを定義できる
      typedef adjacency_list< list_with_allocatorS< std::allocator<int> >, vecS, directedS> MyGraph;

### Parallel Edge Traits

`container_gen` クラスの特殊化版に加えて、 `parallel_edge_traits` クラスの特殊化版も作る必要が有る。これはコンテナ型が並列辺を認める (そしてコンテナが Sequence である) か、コンテナ型が並列辺を認めない (そしてコンテナが AssociativeContainer である) かを指定する。

      template <class StorageSelector>
      struct parallel_edge_traits { };

      template <>
      struct parallel_edge_traits<vecS> {
        typedef allow_parallel_edge_tag type;
      };
      template <>
      struct parallel_edge_traits<setS> {
        typedef disallow_parallel_edge_tag type;
      };
      ...

### Push and Erase for the Edge List Container

更に `adjacency_list` に、辺リストコンテナに辺を効率的に追加、削除する方法を教えなければならない。そのためには、カスタムコンテナ型の `push()` 関数と `erase()` 関数をオーバロードすれば良い。 `push()` 関数は、新しく挿入された要素を指すイテレータと、辺が挿入されたかを示す `bool` 型のフラグを返す必要が有る。全ての STL コンテナ型には、以下のようにデフォルトの `push()` 関数と `erase()` 関数が用意されている。 `push_dispatch()` 、 `erase_dispatch()` 関数オーバロード群では、標準コンテナに対する様々な挿入、削除の方法を使い分けている。

      template <class Container, class T>
      std::pair<typename Container::iterator, bool>
      push(Container& c, const T& v)
      {
        return push_dispatch(c, v, container_category(c));
      }

      template <class Container, class T>
      void erase(Container& c, const T& x)
      {
        erase_dispatch(c, x, container_category(c));
      }

Copyright © 2000-2001 | Jeremy Siek, Indiana University (jsiek@osl.iu.edu)

Japanese Translation Copyright © 2003 Hiroshi Ichikawa
オリジナルの、及びこの著作権表示が全ての複製の中に現れる限り、この文書の複製、利用、変更、販売そして配布を認める。このドキュメントは「あるがまま」に提供されており、いかなる明示的、暗黙的保証も行わない。また、いかなる目的に対しても、その利用が適していることを関知しない。

このドキュメントの対象: Boost Version 1.30.0
最新版ドキュメント (英語)