# Graph Concepts

Boost Graph Library (BGL) の中心となるのはインタフェース、 即ち (ジェネリックプログラミングで言うところの) コンセプトであり、 それはデータ構造に中立なやり方でグラフをいかに吟味し操作するかを定義する。 実際、多少の問題であれば、 いくつかの関数に暗黙的に基づいてグラフを定義する方がより容易であったり、 より効率的であるので新たにデータ構造を用いてBGLインタフェースを実装する必要は一切無い。

BGLインタフェースは単一のグラフ・コンセプトとして現れない。 代わりにそれは遥かに小さな要素へ分解される。 なぜならば、 コンセプトの目的は特定のアルゴリズムの要求を取りまとめることだからである。 どんなアルゴリズムもすべてのグラフ操作を必要とはしない。 概してそのごく一部だけである。 更に、 すべての操作には効率的な実装を提供することはできないが、 ある特定のアルゴリズムになら、 その必要な操作の極めて効率的な実装を提供することができる 多くのグラフ・データ構造がある。 多くのより小さなコンセプトへグラフ・インタフェースを分解することで、 我々はグラフ・アルゴリズムの作者に それらの中から、 彼らのアルゴリズムに最もよく適合するコンセプトを選ぶために有効な選択を供給するのである。

## Graph Structure Concepts Overview

図 1 にグラフ・コンセプト間の詳細な関係を示す。 グラフ・インタフェースを非常に多くのコンセプトに分解したのは、 アルゴリズムのインタフェースがグラフの最小限のインタフェースのみを要求・使用するようにし、 結果、アルゴリズムの再利用性を増加させるためである。

図 1: グラフ・コンセプトとその詳細な関係

表1 でグラフ・コンセプトへの有効な表現および対応する型を与え、 それぞれのコンセプトの詳細な記述へのリンクを提供する。 表中で使用される表記法は以下の通りである。

### Notation

`G` | Graph のモデルである型。
`g` | 型 `G` のオブジェクト。
`e` | 型 `boost::graph_traits<G>::edge_descriptor` のオブジェクト。
`e_iter` | 型 `boost::graph_traits<G>::out_edge_iterator` のオブジェクト。
`u,v` | 型 `boost::graph_traits<G>::vertex_descriptor` のオブジェクト。
`ep` | 型 `G::edge_property_type` のオブジェクト。
`vp` | 型 `G::vertex_property_type` のオブジェクト。
`Property` | 頂点、または辺のプロパティを指定するための型。
`property` | 型 `Property` のオブジェクト。

表 1: グラフ・コンセプトの要約
Expression | Return Type or Description
--- | ---
Graph
`boost::graph_traits<G>::vertex_descriptor` | 頂点を表すオブジェクトへの型。
`boost::graph_traits<G>::edge_descriptor` | 辺を表すオブジェクトへの型。
`boost::graph_traits<G>::directed_category` | 有向であるか、無向であるか?
`boost::graph_traits<G>::edge_parallel_category` | 多重辺を許可するか?
`boost::graph_traits<G>::traversal_category` | グラフ上の頂点と辺を巡回するための方法。
IncidenceGraph Graphの詳細
`boost::graph_traits<G>::out_edge_iterator` | 出力辺へのイテレータ。
`boost::graph_traits<G>::degree_size_type` | 頂点の次数を表す整数型。
`out_edges(v, g)` | `std::pair<out_edge_iterator, out_edge_iterator>`
`source(e, g)` | `vertex_descriptor`
`target(e, g)` | `vertex_descriptor`
`out_degree(v, g)` | `degree_size_type`
BidirectionalGraph IncidenceGraphの詳細
`boost::graph_traits<G>::in_edge_iterator` | 入力辺へのイテレータ。
`in_edges(v, g)` | `std::pair<in_edge_iterator, in_edge_iterator>`
`in_degree(v, g)` | `degree_size_type`
`degree(e, g)` | `degree_size_type`
AdjacencyGraph Graphの詳細
`boost::graph_traits<G>::adjacency_iterator` | 隣接する頂点へのイテレータ。
`adjacent_vertices(v, g)` | `std::pair<adjacency_iterator, adjacency_iterator>`
VertexListGraph IncidenceGraphとAdjacencyGraphの詳細
`boost::graph_traits<G>::vertex_iterator` | グラフの頂点集合へのイテレータ。
`boost::graph_traits<G>::vertices_size_type` | グラフの頂点数を表す符号無し整数型。
`vertices(g)` | `std::pair<vertex_iterator, vertex_iterator>`
`num_vertices(g)` | `vertices_size_type`
EdgeListGraph Graphの詳細
`boost::graph_traits<G>::edge_iterator` | グラフの辺集合へのイテレータ。
`boost::graph_traits<G>::edges_size_type` | グラフの辺数を表す符号無し整数型。
`edges(g)` | `std::pair<edge_iterator, edge_iterator>`
`num_edges(g)` | `edges_size_type`
`source(e, g)` | `vertex_descriptor`
`target(e, g)` | `vertex_descriptor`
AdjacencyMatrix Graphの詳細
`edge(u, v, g)` | `std::pair<edge_descriptor, bool>`
MutableGraph Graphの詳細
`add_vertex(g)` | `vertex_descriptor`
`clear_vertex(v, g)` | `void`
`remove_vertex(v, g)` | `void`
`add_edge(u, v, g)` | `std::pair<edge_descriptor, bool>`
`remove_edge(u, v, g)` | `void`
`remove_edge(e, g)` | `void`
`remove_edge(e_iter, g)` | `void`
MutablePropertyGraph Graphの詳細
`add_vertex(vp, g)` | `vertex_descriptor`
`add_edge(u, v, ep, g)` | `std::pair<edge_descriptor, bool>`
PropertyGraph Graphの詳細
`boost::property_map<G, Property>::type` | 変更可能なプロパティ・マップの型。
`boost::property_map<G, Property>::const_type` | 変更不可能なプロパティ・マップの型。
`get(property, g)` | プロパティ・マップを得るための関数。
`get(property, g, x)` | 辺、または頂点 `x`のプロパティの値を得る。
`put(property, g, x, v)` | 辺、または頂点 `x` のプロパティの値を `v` に設定する。

## Undirected Graphs

BGLの提供する、無向グラフにアクセスし、 操作するためのインタフェースは 次の章で述べる有向グラフのインタフェースと同様である。 しかしながら、 振る舞いと意味においていくつかの違いが見られる。 例えば、 有向グラフでは、頂点の出力辺と入力辺について議論することができる。 無向グラフでは、``入力'' と ``出力'' は無く、 ただ頂点に接続する辺があるのみである。 とは言っても、 BGLでは無向グラフの接続辺にアクセスするためにも、 `out_edges()`(または `in_edges()`) 関数を用いる。 同様にして、 無向辺は、``始点''と``終点''は持たず、 単に順序付けされていない頂点の組を持つのみであるが、 BGLでは、それら頂点にアクセスするためにも、 `source()` と `target()` を用いる。 BGLが無向グラフへの別個のインタフェースを提供しない理由は、 有向グラフ上で有効な多くのアルゴリズムが無向グラフ上でも有効であるからであり、 別個のインタフェースを提供すれば、 だた単にインタフェースが違うという理由で アルゴリズムを重複させなければならず、 それによって利便性を欠いてしまうからである。 無向グラフを使用する際には、暗黙のうちにその有向性を無視するのである。 下記の例で無向グラフでの `out_edges()`、`source()` と `target()` の使用方法を説明する。 この例のソースコードと後のコードは`examples/undirected.cpp` で見つけることが出来る。

      const int V = 2;
      typedef ... UndirectedGraph;
      UndirectedGraph undigraph(V);

      std::cout << "the edges incident to v: ";
      boost::graph_traits<UndirectedGraph>::out_edge_iterator e, e_end;
      boost::graph_traits<UndirectedGraph>::vertex_descriptor
        s = vertex(0, undigraph);
      for (tie(e, e_end) = out_edges(s, undigraph); e != e_end; ++e)
        std::cout << "(" << source(*e, undigraph)
                  << "," << target(*e, undigraph) << ")" << endl;

たとえ無向グラフへのインタフェースが同じでも、 辺の同値性の定義が異なるため、 いくつか振る舞いにおいて違いが見られる。 有向グラフでは、 辺 (u,v) は 辺 (v,u) と決して等しくなることは無いが、 無向グラフでは、 それらは等しくなることがある。 無向グラフが多重グラフであるならば、 (u,v) と (v,u) は多重辺でもよいが、 多重グラフで無いならば、 (u,v) と (v,u) は同じ辺でなくてはならない。

下記の例で辺の同値性を調べると、 有向グラフでは`false`を返すであろうし、 無向グラフでは`true`を返すであろう。 その違いは更に `add_edge()` の意味にも影響する。 下記の例において、更に `add_add(v, u, undigraph)` と書いていたならば、 u と v の間に(グラフの型が多重辺を許可すれば)多重辺を追加していたであろう。 この辺の同値性における違いは辺のプロパティの関連性にも影響する。 例における有向グラフで、 (u,v) と (v,u) は別個の重みを持つことができるのに対して、 一方の無向グラフでは、 (u,v) の重みと (v,u)のそれは、 両者は同じ辺であるから、等しいのである。

      typedef ... DirectedGraph;
      DirectedGraph digraph(V);
      {
        boost::graph_traits<DirectedGraph>::vertex_descriptor u, v;
        u = vertex(0, digraph);
        v = vertex(1, digraph);
        add_edge(digraph, u, v, Weight(1.2));
        add_edge(digraph, v, u, Weight(2.4));
        boost::graph_traits<DirectedGraph>::edge_descriptor e1, e2;
        bool found;
        tie(e1, found) = edge(u, v, digraph);
        tie(e2, found) = edge(v, u, digraph);
        std::cout << "in a directed graph is ";
        std::cout << "(u,v) == (v,u) ? " << (e1 == e2) << std::endl;

        property_map<DirectedGraph, edge_weight_t>::type
          weight = get(edge_weight, digraph);
        cout << "weight[(u,v)] = " << get(weight, e1) << endl;
        cout << "weight[(v,u)] = " << get(weight, e2) << endl;
      }
      {
        boost::graph_traits<UndirectedGraph>::vertex_descriptor u, v;
        u = vertex(0, undigraph);
        v = vertex(1, undigraph);
        add_edge(undigraph, u, v, Weight(3.1));
        boost::graph_traits<UndirectedGraph>::edge_descriptor e1, e2;
        bool found;
        tie(e1, found) = edge(u, v, undigraph);
        tie(e2, found) = edge(v, u, undigraph);
        std::cout << "in an undirected graph is ";
        std::cout << "(u,v) == (v,u) ? " << (e1 == e2) << std::endl;

        property_map<UndirectedGraph, edge_weight_t>::type
          weight = get(edge_weight, undigraph);
        cout << "weight[(u,v)] = " << get(weight, e1) << endl;
        cout << "weight[(v,u)] = " << get(weight, e2) << endl;
      }

The output is:

    in a directed graph is (u,v) == (v,u) ? 0
    weight[(u,v)] = 1.2
    weight[(v,u)] = 2.4
    in an undirected graph is (u,v) == (v,u) ? 1
    weight[(u,v)] = 3.1
    weight[(v,u)] = 3.1

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

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