BGL で SGB グラフを使用する方法
Boost グラフ・ライブラリ (BGL) ヘッダ <boost/graph/stanford_graph.hpp>
は、Stanford GraphBase (SGB) のグラフ・ポインタを BGL 互換な VertexListGraph に適合する。ただし、グラフ・アダプタ・クラスは使用されない。
SGB の Graph* それ自身は VertexListGraph のモデルから設計されている。VertexListGraph
コンセプトは、 Graph* のための適切な非メンバ関数から定義されることにより構成されている。
スタンフォード・グラフベース（The Stanford GraphBase）
"Stanford GraphBase
(SGB) は、非常に多様なグラフやネットワークを生成したり調査したりするコンピュータ・プログラムとデータセットの集まりである" SGB
は、１９９３年に Donald E. Knuth （クヌース先生）により開発され公開された。完全に文書化されたソースコードは
Stanford University
（スタンフォード大学） の anonymous ftp から入手でき、"The Stanford GraphBase, A Platform
for Combinatorial Computing," という本の中にも書かれている。この本は ACM Press と Addison-Wesley
Publishing Company により１９９３年に共同出版された（この本は電子媒体ではないが、付加的な情報として幾らかの章を含んでいる）。
必要環境
SGB のソースコードは、調和のとれた規則を持つ Literate
Programming
（文芸的プログラミング）パラダイムにより書かれている。従って、あなたのコンピュータが
CWEB システムをサポートしているかを確認する必要がある。CWEB ソースコードは
Stanford University （スタンフォード大学） の anonymous ftp から入手できる。Unix システムにおける
CWEB の立ち上げは、CWEB
ディストリビューション（配布パッケージ）により基本として存在し文書化されている。コンパイル済みバイナリ・パッケージである実行可能な Win32 環境の
CWEB ツールは、以下の URL: www.literateprogramming.com
から入手できる。
SGB のインストール
SGB ソースを入手し、実際に動作する CWEB システム（少なくとも
"ctangle" プロセッサが必要）をインストールできたならば、ほとんど SGB ソースをコンパイルする準備ができている。SGB は”古い表記スタイルの
C”で書かれている。しかし、Boost グラフ・ライブラリでは "新しい表記スタイルの C" と "C++" で扱うことを期待している。幸運なことに SGB
ディストリビューションには、"K&R（カーニハン＆リッチ）スタイルの C" から "ANSI スタイルの C"
に全てのソースコードを変換する適切なパッチが付属している。従って、スタンフォード・グラフベース
(SGB) を Boost
グラフ・ライブラリにスムーズに統合することができる。
-
Unix: SGB 書庫を解凍した後に、それらファイルを解凍したルート・ディレクトリの場所で "make tests" と "make
install" を実行する前に "ln -s PROTOTYPES/*.ch ." を実行する（或いは、単純に SGB
ソースファイルの隣にチェンジファイルをコピーしてもよい）。 Unix の SGB Makefile
は、都合よく SGB ソースファイルに "チェンジファイル" をマッチさせて、自動的に "ctangle" プロセッサにかけてくれる。生成された C
のファイルは、スムーズにコンパイラの実行をパスするであろう。
-
Win32: SGB ディストリビューションの "MSVC" サブディレクトリに "デベロッパ・スタジオ・プロジェクト" （そして、単体の
"ワークスペース・ファイル"）のセットが含まれており、 Microsoft Developer Studio 6
に適用できる。インストール方法は付属するファイル README.MSVC に書かれている。 "MSVC"
のコントリビューション（処理系依存パッケージ）は、"プロトタイプ（試作品）"がうまく動作するように更新され続けてきたので、うまく動作するか心配する必要はない。
SGB の使用
SGB のインストール を終えたならば、SGB Graph* を
<boost/graph/stanford_graph.hpp>（これについては次
で説明する）と共に使用して BGL グラフ・インタフェースを利用できる。残りのすべき事は C++ コンパイラに SGB
ヘッダファイルの場所（デフォルトでは、Unix の場合 /usr/local/sgb/include で、Win32 の場合 SGB
をインストールした "MSVC" サブディレクトリ）を指定し、リンカに SGB スタティック・ライブラリの場所（Unix では libgb.a
で、Win32 では libgb.lib ）を指定するのみである。これらの具体的な方法については、個別のコンパイラに付属する説明文書を参照せよ。
技術詳細
-
ヘッダファイルに関して: ２つの SGB モジュール gb_graph と gb_io は、プリプロセッサでスイッチ
SYSV を使用する。このスイッチで SYSV が定義されている場合（#if defined(SYSV)
）には <string.h>
が include され、SYSV が定義されていない場合（ #if !defined(SYSV) ）には <strings.h>
が include される。いくらかのコンパイラでは、例えば gcc/g++ であるが、この事を考慮する必要は無い（ gcc
は <string.h> を参照すること無しに "string" 関数を呼べる）、しかし他のコンパイラでは、例えば Win32
の MSVC であるが、この事を考慮する必要がある（ゆえに全ての SGB ディストリビューションの
"MSVC" サブディレクトリにおける "デベロッパ・スタジオ・プロジェクト" には、SYSV が適切に定義されている）。コンパイラの環境に合わせて慎重に
SYSV を定義するか定義しないかを選択する必要がある。
-
二重インクルード防止の失敗: どの SGB ヘッダファイルも複数回のインクルードを防止するための "internal include
guards"（二重インクルード防止）を施していない。問題回避のためにも、コンパイル・ユニット（*.h; *.cpp; *.hpp; *.inc 等）で
BGL ラッパ
の前後に SGB ヘッダファイルを #include してはならない。BGL インタフェースは、そのようにしても十分使用できる。
-
プリプロセッサのマクロ : SGB
ヘッダファイルでは、マクロに則した記法（全部大文字にするとか、マクロを表す接頭辞をつけるといった事）をしないで、気ままなプリプロセッサの使い方がされている。これらプリプロセッサのマクロにおいて、既に３箇所で、次のいずれか
C++、g++、BGL における記法と名前衝突がコードを書くときに発生しており、この問題は BGL ラッパ
内で修正済である。このようなプリプロセッサのマクロから誘発される問題が、今後起こらないと断言することはできない（しかしながら私たちは、このような衝突問題に関して積極的に対処するつもりである）。
SGB のための BGL インタフェース
定義場所
<boost/graph/stanford_graph.hpp>
この BGL ヘッダファイルの主目的は SGB の一般的な機能を利用するための全てのグローバル定義や SGB
ヘッダファイル （２節の "test_sample
" [*1] プログラムのような）様々なグラフ生成関数を #include することである。
BGL stanford_graph.hpp
ヘッダは、SGB ソース上に BGL の枠組内で SGB
グラフを使用するための適切な機能と型を定義したり加えたりする。
改善されたインタフェースとは別に、SGB
（スタティック）ライブラリ は BGL
のドキュメントで示されるのと同じ "as-is"
「あるがままに」のライセンスが使われている。
モデル
Vertex List Graph と Property Graph 。プロパティ・タグのセットは、SGB
グラフと共に使用できるが、それは以降の頂点プロパティと辺プロパティという節に記述されている
例
サンプル・プログラム <example/miles_span.cpp>
は、BGL から SGB
グラフへのジェネリックなフレームワークをよく表す最初のアプリケーションである。
このアプリケーションは "最小流域木"
問題を解くための Prim のアルゴリズムを使用する。加えて、<example/girth.cpp>
と
<example/roget_components.cpp>
のプログラムは、SGB
から作成された。わたしたちは、SGB 中にある一般的な形式のものから、より多くのアルゴリズムを実装し、BGL
フレームワークのための残る SGB
サンプルを供給する予定である。
もし、あなたがこれらの支援を行いたいなら、軽い気持ちで成果を送ってください！関連型
graph_traits<Graph*>::vertex_descriptor
Graph* に関連した頂点記述子の型。頂点記述子は Vertex*
型と等価である。
graph_traits<Graph*>::edge_descriptor
Graph* に関連した辺記述子の型。これは boost::sgb_edge.
型である。BGL
辺記述子の必要なオペレーションすべてのサポートに加えて、boost::sgb_edge
クラスは以下のようなコンストラクタを持っている。
sgb_edge::sgb_edge(Arc* arc, Vertex* source)
graph_traits<Graph*>::vertex_iterator
vertices() 関数の戻り値として使用されるイテレータの型。
graph_traits<Graph*>::out_edge_iterator
out_edges() 関数の戻り値として使用されるイテレータの型。
graph_traits<Graph*>::adjacency_iterator
adjacent_vertices() 関数の戻り値として使用されるイテレータの型
graph_traits<Graph*>::vertices_size_type
グラフ中の頂点数を表すための型
graph_traits<Graph*>::edge_size_type
グラフ中の辺数を表すための型
graph_traits<Graph*>::degree_size_type
グラフ中の頂点に対する辺を表すための型
graph_traits<Graph*>::directed_category
グラフが有向か無向かを示すための情報。SGB の Graph*
は有向なので、この型は directed_tag である。
graph_traits<Graph*>::traversal_category
SGB の Graph*
は頂点集合，出辺，隣接頂点のアクセスを供給しており、アクセスの種別タグは以下のように定義されている。
struct sgb_traversal_tag :
public virtual vertex_list_graph_tag,
public virtual incidence_graph_tag,
public virtual adjacency_graph_tag { };
graph_traits<Graph*>::edge_parallel_category
これはグラフ・クラスが平行な辺（同じ始点と終点からなる辺）の挿入を許可しているかどうかを示す。SGB Graph*
は平行な辺の追加を妨げないので、この型は allow_parallel_edge_tag
である。
非メンバ関数
std::pair<vertex_iterator, vertex_iterator>
vertices(Graph* g)
グラフ g の頂点集合にアクセスするための範囲イテレータを返す。
std::pair<out_edge_iterator, out_edge_iterator>
out_edges(vertex_descriptor v, Graph* g)
グラフ g 中の頂点 v
の出辺にアクセスするための範囲イテレータを返す。
入辺数にアクセスするための
in_edges 関数に相当するものはない。
std::pair<adjacency_iterator, adjacency_iterator>
adjacent_vertices(vertex_descriptor v, Graph* g)
グラフ g 中の頂点 v
の隣接頂点にアクセスするための範囲イテレータを返す。
vertex_descriptor
source(edge_descriptor e, Graph* g)
辺 e の始点である頂点を返す。
vertex_descriptor
target(edge_descriptor e, Graph* g)
辺 e の終点である頂点を返す。
degree_size_type
out_degree(vertex_descriptor v, Graph* g)
頂点 v の出辺数を返す。
入辺数を返す in_degree
関数に相当するものはない。
vertices_size_type
num_vertices(Graph* g)
グラフ g 中の頂点数を返す。
edge_size_type
num_edges(Graph* g)
グラフ g 中の辺数を返す。
vertex_descriptor
vertex(vertices_size_type n, Graph* g)
グラフの頂点リストから（０を基準として）Ｎ番目の頂点を返す。
template <class PropertyTag>
property_map<Graph*, PropertyTag>::type
get(PropertyTag, Graph*& g)
template <class PropertyTag>
property_map<Graph*, Tag>::const_type
get(PropertyTag, const Graph*& g)
PropertyTag で指定された頂点，辺のプロパティを保持するプロパティ・マップを返す。PropertyTag
は次節で書かれているものでなければならない。
頂点プロパティと辺プロパティ
SGB
の頂点と辺の構造体は、特別な情報を保持するための
"utility" というフィールドを持っている。BGL
ラッパでは、 property maps
を通じてこれらのフィールドへのアクセスを提供している。加えて、頂点インデックスと辺長に対するマップも提供している。プロパティ・マップ・オブジェクトは、Property
Graph （プロパティ・グラフ） コンセプト中の get()
関数を使用することにより SGB Graph*
から取り出すことができる。以下のプロパティ・タグのリストは、どのユーティリティ・フィールドをプロパティ・マップのために使用したいか特殊化（明示）するために使用することができる。
// vertex properties
template <class T> u_property;
template <class T> v_property;
template <class T> w_property;
template <class T> x_property;
template <class T> y_property;
template <class T> z_property;
// edge properties
template <class T> a_property;
template <class T> b_property;
これらのタグのためのテンプレート・パラメータ T
は、SGB ヘッダ gb_graph.h 中の util
共用体で定義されている型（ Vertex*,
Arc*, Graph*, char*, long ）に制限されている。utility
フィールドを利用するプロパティ・マップは、Lvalue Property
Map （左辺値プロパティ・マップ）
というモデルである。
頂点インデックスのプロパティ・マップは、vertex_index_t
タグを使用することにより利用でき、このプロパティ・マップは
Readable Property
Map （読み取り可能プロパティ・マップ）
である。辺長のプロパティ・マップは、edge_length_t
タグを使用することにより利用でき、このプロパティ・マップは
Lvalue Property Map （左辺値プロパティ・マップ）
で、value type （値型）は long である。
プロパティ・マップ・オブジェクトは、Property
Graph （プロパティ・グラフ） コンセプト中の get()
関数を使用することにより利用できる。プロパティ・マップの型は
property_map
特性クラスから与えられる。
[*1] 原文を見ても、どこを示すのか不明。Boost 内のあらゆる文書に "test_sample" というキーワードは、この文書以外に登場しない。
Japanese Translation Copyright (C) 2003 OKI
Miyuki
オリジナルの、及びこの著作権表示が全ての複製の中に現れる限り、この文書の複製、利用、変更、販売そして配布を認める。このドキュメントは「あるがまま」に提供されており、いかなる明示的、暗黙的保証も行わない。また、いかなる目的に対しても、その利用が適していることを関知しない。