# The Boost Graph Library (BGL)

グラフは計算機科学の多くの種類の問題を解決するのに有用な 数学的抽象概念である。 必然的に、この抽象概念はコンピュータプログラムでも 表現されなければならない。 グラフを渡る(traverse)ための標準化されたジェネリックなインタフェースは、 グラフのアルゴリズムとデータ構造の再利用を促す上で最も重要である。 Boost Graph Library はグラフの構造へどのようにアクセスするかを定めた インタフェースである。これは、グラフのデータ構造の実装の詳細を隠す ジェネリックなインタフェースである。 これは以下のような意味に置いて``オープンな''インタフェースである。すなわち、このインタフェースを 実装したグラフライブラリはどれでも、 BGL のジェネリックなアルゴリズムや、 このインタフェースを用いる他のアルゴリズムと相互運用できるようになる。 BGL はこのインタフェースに準じたいくつかの汎用クラスを提供する。 しかし、それらは``唯一の''グラフクラスであることを意味しない; 特定の状況に応じて 他のよりよいグラフクラスがもちろんあり得るだろう。 我々は BGL の主な貢献が、このインタフェースの定式化にあると確信している。

BGL グラフインタフェースおよびグラフコンポーネントは、標準テンプレートライブラリ (STL) [2] と同じ意味で ジェネリックなインタフェースである。 続く節で、ジェネリックプログラミングが STL において演じる役割を再検討し、 我々がジェネリックプログラミングをどのようにグラフの文脈に適用したかと比較する。

もちろん、あなたがすでにジェネリックプログラミングに親しんでいるなら、 今すぐに飛び込んでくれて結構！ここが目次だ。

BGL のソースコードは Boost 配布物の一部として入手可能である。 ここからダウンロードできる。

## Genericity in STL

STL は三つの理由からジェネリックである。

### アルゴリズム / データ構造の相互運用性

第一に、各アルゴリズムはデータ構造に中立な方法で書かれており、 単一のテンプレート関数が多くの異なるコンテナクラスを操作できるようにしている。 イテレータの概念は、このアルゴリズムとデータ構造の分離において鍵となる構成要素である。 このテクニックの効果は、 STL のコード量を O(M*N) から O(M+N) へと削減する。 ここで M はアルゴリズムの数、 N はコンテナの数である。 20 種類のアルゴリズムと 5 種類のデータ構造という状況を考えると、 これは 100 の関数を書き下ろすことと 25 との差になる！ そしてその差は、アルゴリズムとデータ構造が増えるに連れて、ますます伸び続ける。

### 関数オブジェクトを通じた拡張

STL がジェネリックである二つ目の理由は、アルゴリズムとコンテナが拡張可能なことである。 ユーザは関数オブジェクトを用いて STL を改造し、カスタマイズできる。 実世界の問題を解決するにあたって STL を素晴らしいツールたらしめているのは、このフレキシビリティである。 各々のプログラミングの問題は、モデル化されなければならない固有の概念の集りや相互作用を伴う。 関数オブジェクトは、 STL を個々の問題領域の仕様を扱えるよう拡張するためのメカニズムを提供する。

### 要素型のパラメータ化

STL がジェネリックである三つ目の理由は、そのコンテナが要素の型に関してパラメータ化されていることである。 非常に重要であるにもかかわらず、これは STL がジェネリックである理由として恐らく最も``関心を引かない''ものである。 ジェネリックプログラミングは、 `std::list<T>` のようなパラメータ化されたリストの 短い記述で片づけられることがよくある。 これはせいぜい上っ面をなぞっただけに過ぎない！

## Genericity in the Boost Graph Library

STL と同様に、三つの理由から BGL はジェネリックである。

### アルゴリズム / データ構造の相互運用性

第一に、 BGL のグラフアルゴリズムは、特定のグラフのデータ構造から詳細を取り去るインタフェースに向けて書かれている。 STL と同様、 BGL はデータ構造を渡る(traversal)ためのインタフェースを定義するのにイテレータを用いる。 三つの異なるグラフの渡り方(traversal pattern)がある： グラフのすべての頂点を渡る(traversal)もの、すべての辺を通るもの、そして グラフの隣接する構造に沿って、ある頂点からその近傍の各々へと それぞれの渡り方(pattern of traversal)のために別々のイテレータが用意されている。

このジェネリックなインタフェースは、 ポインタでリンクされたノードで実装されたものから配列にエンコードされたものに至るまで、 多彩なグラフのデータ構造で働くように、 `breadth_first_search()` のようなテンプレート関数を許している。 このフレキシビリティはグラフの領域では特に重要である。 グラフのデータ構造は、特定のアプリケーションのためにしばしばカスタムメイドされる。 伝統的には、プログラマがアルゴリズムの実装を再利用したいと思えば、彼らのグラフデータを グラフライブラリの既定のグラフ構造へと変換 / コピーしなければならない。 これは LEDA 、 GTL 、 Stanford GraphBase などで起こる問題であり、 特に Fortlan で書かれたグラフアルゴリズムで真である。 (This is the case with libraries such as LEDA, GTL, Stanford GraphBase, and especially true of graph algorithms written in Fortran.) このことは、それらのグラフアルゴリズムの再利用を著しく制限する。

対照的に、 external adaptation (How to Convert Existing Graphs to BGLを 参照) を用いた BGL のジェネリックなグラフアルゴリズムでは、 カスタムメイドな (あるいはレガシーですらある) グラフ構造を利用することができる。 external adaptation は、データ構造を新しいインタフェースでラップする。 その際にアダプタオブジェクトの内側のデータをコピーしたり置いたりることはない。 BGL のインタフェースはこの適応が容易になるように注意深く設計されている。 このことを示すために、 LEDA のグラフや Stanford GraphBase のグラフ、さらには Fortlan スタイルの配列ですら BGL のグラフアルゴリズムで使えるようにインタフェースするコードを作成した。

### Visitor による拡張

第二に、 BGL のグラフアルゴリズムは拡張可能である。 BGL は visitor の概念を導入している。これはただの多数のメソッドを持つ関数オブジェクトである。 グラフアルゴリズムには、多くの場合、鍵となる``イベントポイント(event point)''がいくつか用意されている。 これらはユーザ定義操作を挿入するのに用いられる。 visitor オブジェクトは各イベントポイントで呼び出される異なるメソッドを持つ。 特定のイベントポイントと対応する visitor のメソッドは特定のアルゴリズムに依存する。 それらはしばしば `start_vertex()` 、 `discover_vertex()` 、 `examine_edge()` 、 `tree_edge()` ないし `finish_vertex()` といったメソッドを含む。

### 頂点と辺のプロパティの多重パラメータ化

BGL がジェネリックである第三の理由は、 STL コンテナにおける要素型のパラメータ化に類するものである。 しかし、グラフでは、話はまた少しばかり複雑になる。 我々は値をグラフと頂点と辺の両方に関連づける必要がある（関連づけられた値をプロパティと呼ぶ）。 加えて、複数のプロパティを各々の頂点と辺に関連づける必要がよく出てくる。 我々はこれを多重パラメータ化と呼ぶ。 `std::list<T>` クラスが要素型として `T` パラメータを持つのと同様に、 BGL のグラフクラスは頂点と辺の``プロパティ''に関するテンプレートパラメータを持つ。 あるプロパティはそのプロパティのパラメータ化された型を定義し、 またそのプロパティを識別するタグを割り当てる。このタグは複数のプロパティを 識別できるようにする為に用いられる。 特定の頂点または辺に付随するプロパティ値は、 各々のプロパティについて一つずつ存在する プロパティマップ によって 取得される。

伝統的なグラフライブラリとグラフ構造は、グラフのプロパティをパラメータ化しようとした時に破綻する。 これは、グラフのデータ構造がアプリケーションに対してカスタムビルドされなければならない主要な理由の一つである。 BGL グラフクラスにおけるプロパティのパラメータ化は、それらを再利用に適すようにしてくれる。

## Algorithms

BGL のアルゴリズムは中核となる（ジェネリックアルゴリズムで実装された）アルゴリズムパターンのセットと、 より大きなグラフアルゴリズムのセットからなる。中核となるアルゴリズムパターンは

- 幅優先探索
- 深さ優先探索
- 均一コスト探索(Uniform Cost Search)

アルゴリズムパターンそれ自身は、グラフ上の意味のある値を計算することはない。 それらはグラフアルゴリズムを構築するためのビルディングブロックでしかない。 現在のところ BGL に含まれるのグラフアルゴリズムは

- Dijkstraの最短経路(Dijkstra's Shortest Paths)
- Bellman-Fordの最短経路(Bellman-Ford Shortest Paths)
- Johnsonの全点対間最短路 (Johnson's All-Pairs Shortest Paths)
- Kruskalの最短距離木(Kruskal's Minimum Spanning Tree)
- Primの最短距離木(Prim's Minimum Spanning Tree)
- 連結構成要素(Connected Components)
- 強連結構成要素(Strongly Connected Components)
- 動的連結構成要素（互いに素な集合を用いる）(Dynamic Connected Components (using Disjoint Sets))
- トポロジカルソート(Topological Sort)
- 転置(Transpose)
- 逆Cuthill Mckee順序(Reverse Cuthill Mckee Ordering)
- 最小最終頂点順序(Smallest Last Vertex Ordering)
- シーケンシャルな頂点色づけ(Sequential Vertex Coloring)

## Data Structures

現在のところ BGL は二つのクラスを提供している。 一つは一般化された連接リストを実装し、もう一つは辺リストアダプタを実装している。

- `adjacency_list`
- `adjacency_matrix`
- `edge_list`

`adjacency_list` クラスは汎用なグラフクラスの``スイスアーミーナイフ[訳注：十徳ナイフ]''である。 これは高度にパラメータ化されており、異なる状況に対して最適化する事ができる： 有向グラフか無向グラフか、 並行辺を許すかどうか、 出辺のみに効果的にアクセスするようにするか、それとも入辺にもそうするか、 余計な容量のオーバーヘッドのコストを支払っても頂点の挿入と削除を高速に行うか、 等々。

`edge_list` クラスはあらゆる種類の辺イテレータを取るアダプタである。 このクラスは EdgeListGraph を実装している。

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