# 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" に全てのソースコードを変換する適切なパッチが付属している。従って、Boost グラフ・ライブラリにおいて、スタンフォード・グラフベース (SGB) のスムーズな集積化を可能にしている。

- 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 インタフェースは、そのようにしても十分使用できる。
- プリプロセッサのマクロ: The SGB headerfiles make liberal use of the preprocessor without sticking to a particular convention (like all-uppercase names or a particular prefix). At the time of writing, already three of these preprocessor macros collide with the conventions of either C++, g++, or BGL, and are fixed in the BGL wrapper. We can not guarantee that no other preprocessor-induced problems may arise (but we are willing to learn about any such collisions).

## SGB のための BGL インタフェース

### 定義場所

`<boost/graph/stanford_graph.hpp>`

The main purpose of this Boost Graph Library (BGL) headerfile is to `#include` all global definitions for the general stuff of the Stanford GraphBase (SGB) and its various graph generator functions by reading all SGB headerfiles as in section 2 of the "`test_sample`" program.

On top of the SGB stuff, the BGL `stanford_graph.hpp` header adds and defines appropriate types and functions for using the SGB graphs in the BGL framework. Apart from the improved interface, the SGB (static) library is used "as is" in the context of BGL.

### モデル

Vertex List Graph and Property Graph. The set of property tags that can be used with the SGB graph is described in the Vertex and Edge Properties section below.

### 例

The example program `<example/miles_span.cpp>` represents the first application of the generic framework of BGL to an SGB graph. It uses Prim's algorithm to solve the "minimum spanning tree" problem. In addition, the programs `<example/girth.cpp>` and `<example/roget_components.cpp>` have been ported from the SGB. We intend to implement more algorithms from SGB in a generic fashion and to provide the remaining example programs of SGB for the BGL framework. If you would like to help, feel free to submit your contributions!

### 関連型

`graph_traits<Graph*>::vertex_descriptor`
The type for the vertex descriptors associated with the `Graph*`. We use the type `Vertex*` as the vertex descriptor.

`graph_traits<Graph*>::edge_descriptor`
The type for the edge descriptors associated with the `Graph*`. This is the type `boost::sgb_edge`. In addition to supporting all the required operations of a BGL edge descriptor, the `boost::sgb_edge` class has the following constructor.

       sgb_edge::sgb_edge(Arc* arc, Vertex* source)

`graph_traits<Graph*>::vertex_iterator`
The type for the iterators returned by `vertices()`.

`graph_traits<Graph*>::out_edge_iterator`
The type for the iterators returned by `out_edges()`.

`graph_traits<Graph*>::adjacency_iterator`
The type for the iterators returned by `adjacent_vertices()`.

`graph_traits<Graph*>::vertices_size_type`
The type used for dealing with the number of vertices in the graph.

`graph_traits<Graph*>::edge_size_type`
The type used for dealing with the number of edges in the graph.

`graph_traits<Graph*>::degree_size_type`
The type used for dealing with the number of edges incident to a vertex in the graph.

`graph_traits<Graph*>::directed_category`
Provides information about whether the graph is directed or undirected. An SGB `Graph*` is directed so this type is `directed_tag`.

`graph_traits<Graph*>::traversal_category`
An SGB `Graph*` provides traversal of the vertex set, out edges, and adjacent vertices. Therefore the traversal category tag is defined as follows:

    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`
This describes whether the graph class allows the insertion of parallel edges (edges with the same source and target). The SGB `Graph*` does not prevent addition of parallel edges, so this type is `allow_parallel_edge_tag`.

### 非メンバ関数

    std::pair<vertex_iterator, vertex_iterator>
    vertices(Graph* g)

Returns an iterator-range providing access to the vertex set of graph `g`.

    std::pair<out_edge_iterator, out_edge_iterator>
    out_edges(vertex_descriptor v, Graph* g)

Returns an iterator-range providing access to the out-edges of vertex `v` in graph `g`.
There is no corresponding `in_edges` function.

    std::pair<adjacency_iterator, adjacency_iterator>
    adjacent_vertices(vertex_descriptor v, Graph* g)

Returns an iterator-range providing access to the adjacent vertices of vertex `v` in graph `g`.

    vertex_descriptor
    source(edge_descriptor e, Graph* g)

Returns the source vertex of edge `e`.

    vertex_descriptor
    target(edge_descriptor e, Graph* g)

Returns the target vertex of edge `e`.

    degree_size_type
    out_degree(vertex_descriptor v, Graph* g)

Returns the number of edges leaving vertex `v`.
There is no corresponding `in_degree` function.

    vertices_size_type
    num_vertices(Graph* g)

Returns the number of vertices in the graph `g`.

    edge_size_type
    num_edges(Graph* g)

Returns the number of edges in the graph `g`.

    vertex_descriptor
    vertex(vertices_size_type n, Graph* g)

Returns the (0-based) nth vertex in the graph's vertex list.

    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)

Returns the property map object for the vertex property specified by `PropertyTag`. The `PropertyTag` must be one of the described below.

### 頂点プロパティと辺プロパティ

The SGB `Vertex` and `Arc` structures provide "utility" fields for storing extra information. We provide BGL wrappers that provide access to these fields through property maps. In addition, vertex index and edge length maps are provided. A property map object can be obtained from a SGB `Graph*` using the `get()` function described in the Property Graph concept.

The following list of property tags can be used to specify which utility field you would like a property map for.

    // 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;

The template parameter `T` for these tags is limited to the types in the `util` union declared in the SGB header `gb_graph.h`, which are `Vertex*`, `Arc*`, `Graph*`, `char*`, and `long`. The property maps for the utility fields are models of Lvalue Property Map.

The property map for vertex indices can be obtained using the `vertex_index_t` tag, and this property map is a Readable Property Map. A property map for edge length's can be obtained using the `edge_length_t` tag, and this property map is a Lvalue Property Map whose value type is `long`.

Property map objects can be obtained via the `get()` function of the Property Graph concept. The type of the property map is given by the `property_map` traits class.

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