# IncidenceGraph

IncidenceGraph コンセプトはグラフ中の各頂点の出辺への効率的なアクセスの ためのインターフェースを提供する。

### Refinement of

Graph

### Notation

`G` | IncidenceGraph のモデルの型。
`g` | 型が `G` のオブジェクト
`e` | 型が `boost::graph_traits<G>::edge_descriptor` の オブジェクト。
`u, v` | 型が `boost::graph_traits<G>::vertex_descriptor` の オブジェクト。

### Associated Types

`boost::graph_traits<G>::traversal_category` このタグ型は `incidence_graph_tag` に変換可能でなければならない。
    boost::graph_traits<G>::out_edge_iterator
頂点 v のための出辺イテレータは頂点の出辺へのアクセスを提供する。 そのため出辺イテレータの値型はそのグラフの辺記述子型である。 出辺イテレータは MultiPassInputIterator の要求を満たしていなければならない。
    boost::graph_traits<G>::degree_size_type
頂点の出辺または接続辺の番号を表すのに使われる符号無し汎整数型。

### Valid Expressions

`source(e, g)` | `e` によって表される辺 (u,v) の u の頂点記述子を返す。 返却型: `vertex_descriptor`
`target(e, g)` | `e` によって表される辺 (u,v) の v の頂点記述子を返す。 返却型: `vertex_descriptor`
`out_edges(u, g)` | グラフ `g` 中の頂点 `u` の出辺 (有向グラフ) または接続辺 (無向グラフ) へのアクセスを提供するイテレータ範囲を返す。 出辺イテレータ経由で得られる辺の始点は、有向グラフと無向グラフの両方に おいて、`out_edges(u, g)` の呼び出しに用いられる頂点 `u`で あり、終点は `u` に隣接した頂点である事が保証されている。 [1] 返却型: `std::pair<out_edge_iterator, out_edge_iterator>`
`out_degree(u, g)` | グラフ `g` 中の頂点 `u` の 出辺数 (有向グラフ) または接続辺数 (無向グラフ)を返す。 返却型: `degree_size_type`

### Complexity guarantees

`source()`、`target()`、そして `out_edges()` 関数はすべて定数時間であるはずである。 `out_degree()` 関数は出辺の数による線形時間であるはずである。

### See Also

Graph concepts

### Notes

[1] 無向グラフにとって、辺 `(u,v)` は 辺 `(v,u)` と同じだから、いくつかの特別な保証がなかったら実装は出辺の頂点のペアのどの順序 付けからも開放されたであろう。例えば、もし `out_edges(u, g)` を呼び出し、 `v` が `u` への隣接頂点の一つであるとすれば、実装は非直感的で アルゴリズムにとって問題を引き起こす出辺として `(v,u)` を返す事が 自由だったろう。それゆえ `u` と `v` を接続する出辺は `(u,v)` として与えられるべきで、`(v,u)` として与えられるべき ではないという特別な要求が加えられる。

### Concept Checking Class

      template <class G>
      struct IncidenceGraphConcept
      {
        typedef typename boost::graph_traits<G>::out_edge_iterator out_edge_iterator;
        void constraints() {
          function_requires< GraphConcept<G> >();
          function_requires< MultiPassInputIteratorConcept<out_edge_iterator> >();

          p = out_edges(v, g);
          e = *p.first;
          u = source(e, g);
          v = target(e, g);
        }
        void const_constraints(const G& g) {
          p = out_edges(v, g);
          e = *p.first;
          u = source(e, g);
          v = target(e, g);
        }
        std::pair<out_edge_iterator, out_edge_iterator> p;
        typename boost::graph_traits<G>::vertex_descriptor u, v;
        typename boost::graph_traits<G>::edge_descriptor e;
        G g;
      };

Copyright © 2000-2001 | Jeremy Siek, Indiana University (jsiek@osl.iu.edu) Lie-Quan Lee, Indiana University (llee@cs.indiana.edu) Andrew Lumsdaine, Indiana University (lums@osl.iu.edu)

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

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