## MutableGraph

MutableGraph は辺と頂点の追加または削除によって変化させる事ができる。

### Refinement of

Graph

### Notation

`G` | Graph のモデルの型。
`g` | 型が `G` のオブジェクト。
`e` | 型が `boost::graph_traits<G>::edge_descriptor` のオブジェクト。
`u,v` | 型が `boost::graph_traits<G>::vertex_descriptor` のオブジェクト。
`iter` | 型が `boost::graph_traits<G>::out_edge_iterator` のオブジェクト。
`p` | Predicate をモデルとし、引数型が `edge_descriptor` 型に一致する型のオブジェクト。

### Valid Expressions

`add_edge(u, v, g)` | 辺 (u,v) をグラフ中に挿入し、新しい辺を指す辺記述子を返す。 もしグラフが多重辺を禁じていて、辺 (u,v) が既にグラフ中にあるなら、 返された `bool` フラグは `false` であり、返された辺記述子は 既に存在する辺を指す。無向グラフにとって辺 (u,v) は辺 (v,u) に 等しいので、`add_edge()` 関数を呼んだ後、これは辺 (u,v) が u の出辺に現れ、辺 (u,v) (同様に辺 (v,u)) が vの 出辺に現れるであろう事を暗示する事に注意せよ。言い換えると、vは u に隣接しており、u は v に隣接しているであろう。 返却値型: `std::pair<edge_descriptor, bool>`
`remove_edge(u, v, g)` | 辺 (u,v) をグラフから削除する。もしグラフが多重辺を許可しているなら、 これは (u,v) のすべての存在を削除する。 返却値型: `void` 事前条件: u と v はグラフ中の頂点である。 事後条件: (u,v) はもはや `g` の辺集合中にない。
`remove_edge(e, g)` | 辺 e をグラフから削除する。 返却値型: `void` 事前条件: e はグラフ中の辺である。 事後条件: e はもはや `g` の辺集合中にない。
`remove_edge(iter, g)` | iter によって指される辺をグラフから削除する。 この式はグラフが IncidenceGraph のモデルでもある場合にのみ必要である。 返却値型: `void` 事前条件: `*iter` はグラフ中の辺である。 事後条件: `*iter` はもはや `g` の辺集合中にない。
`remove_edge_if(p, g)` | 述語 `p` が true を返す全ての辺をグラフ `g` から削除する。 返却値型: `void`
`remove_out_edge_if(u, p, g)` | 述語 `p` が true を返す全ての頂点 `u` の出辺を削除する。 この式はグラフが IncidenceGraph のモデルでもある場合にのみ必要である。 返却値型: `void`
`remove_in_edge_if(u, p, g)` | 述語 `p` が true を返す全ての頂点 `u` の入辺を削除する。 この式はグラフが BidirectionalGraph のモデルでもある場合にのみ必要である。 返却値型: `void`
`add_vertex(g)` | 新しい頂点をグラフに追加する。新しい頂点のための `vertex_descriptor` が返される。 返却値型: `vertex_descriptor`
`clear_vertex(u, g)` | 頂点 `u` への、そして頂点 `u` からの全ての辺をグラフから削除する。 返却値型: `void` 事前条件: `u` は `g` の有効な頂点記述子である。 事後条件: `u` は `g` 中のどの辺の始点としても終点としても 現れない。
`remove_vertex(u, g)` | u をグラフの頂点集合から削除する。グラフ中に終点が u の 辺が残っていると未定義のふるまいとなるかもしれない事に注意せよ。一般的に `clear_vertex()` 関数を最初に呼ぶべきである。 返却値型: `void` 事前条件: `u` は `g` の有効な頂点記述子である。 事後条件: `num_vertices(g)` は一つ減り、`u` はもはやグラフの 頂点集合中に現れず、そしてもはや有効な頂点記述子ではない。

### Complexity Guarantees

- 辺の挿入は償却定数時間か、または多重辺 (いくつかのグラフ・タイプの“特徴”で ある) の追加を防ぐ事も調べているなら O(log(E/V)) になり得る。
- 辺の除去は O(E) である事が保証される。
- 頂点の挿入は償却定数時間である事が保証される。
- 頂点の消去は O(E + V) である。
- 頂点の除去は O(E + V) である。

### Models

- `adjacency_list`

### Concept Checking Class

      template <class G>
      struct MutableGraphConcept
      {
        typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor;
        void constraints() {
          v = add_vertex(g);
          clear_vertex(v, g);
          remove_vertex(v, g);
          e_b = add_edge(u, v, g);
          remove_edge(u, v, g);
          remove_edge(e, g);
        }
        G g;
        edge_descriptor e;
        std::pair<edge_descriptor, bool> e_b;
        typename boost::graph_traits<G>::vertex_descriptor u, v;
        typename boost::graph_traits<G>::out_edge_iterator iter;
      };

      template <class edge_descriptor>
      struct dummy_edge_predicate {
        bool operator()(const edge_descriptor& e) const {
          return false;
        }
      };

      template <class G>
      struct MutableIncidenceGraphConcept
      {
        void constraints() {
          function_requires< MutableGraph<G> >();
          remove_edge(iter, g);
          remove_out_edge_if(u, p, g);
        }
        G g;
        typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor;
        dummy_edge_predicate<edge_descriptor> p;
        typename boost::graph_traits<G>::vertex_descriptor u;
        typename boost::graph_traits<G>::out_edge_iterator iter;
      };

      template <class G>
      struct MutableBidirectionalGraphConcept
      {
        void constraints() {
          function_requires< MutableIncidenceGraph<G> >();
          remove_in_edge_if(u, p, g);
        }
        G g;
        typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor;
        dummy_edge_predicate<edge_descriptor> p;
        typename boost::graph_traits<G>::vertex_descriptor u;
      };

      template <class G>
      struct MutableEdgeListGraphConcept
      {
        void constraints() {
          function_requires< MutableGraph<G> >();
          remove_edge_if(p, g);
        }
        G g;
        typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor;
        dummy_edge_predicate<edge_descriptor> p;
      };

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

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

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