はじめに
本稿で扱うグラフ
「グラフ」という語を広辞苑（第5版）で引くと、載っている意味は次の3つです。
- 互いに連関する二つまたは二つ以上の量の間の関係を表す図形。例えば関数fに対し、xがfの定義域を動くときの点（x， f（x))の軌跡をfのグラフという。またx、yに関する方程式をみたす点（x， y）の軌跡をその方程式のグラフという。
- 全体に対する割合を示したり、数量の大小を比較したりするための図表。円グラフ・棒グラフなど。
- 写真を主にした雑誌。画報。
しかし、本稿で扱うグラフは、この3つのいずれでもありません。国語辞典には載っていないことが多いようですが、計算機科学や数学において「グラフ」と言えば、図のような、点（pointあるいはvertex、node）と点を結ぶ線（lineあるいはarc、edge）の集合を指します。
グラフはプログラミングにおいてよく用いられる基本的なデータ構造の一つです。「データ構造」についてまったく知らないという人はあまりいないでしょう。最も基本的なものはおそらく配列です。他に、ベクタやリスト、セット、ハッシュテーブル、木などといったデータ構造が、広く使われているプログラミング言語には用意されています。
グラフは、ここで挙げたものほど基本的とは言えないかもしれません。そのため、広く使われているプログラミング言語でも、グラフを標準ではサポートしていないものが多いです。グラフが用意されていない場合は自分で実装しなければなりません。データ自体は、隣接行列（この行列のij成分は、i番目のノードとj番目のノードがつながっているなら1、つながっていないなら0）あるいは隣接リスト（このリストのi番目の要素は、i番目のノードがつながっているノードの番号のリスト）で簡単に表せます。グラフのためのアルゴリズムを実装するのは少し面倒でしょう。
幸いなことに、PHPにはグラフが用意されています。PEAR Structures_Graphです。本稿では、Structures_Graphの使い方を確認し、グラフを用いたアルゴリズムを動かしてみます。
グラフの適用例
グラフはどのような場面で利用するのでしょうか。
地図をグラフで表現するというのは、直観的に分かりやすい例でしょう。地図上の各地点をノードに、2地点間の距離をエッジにします。このグラフ上で最短経路を求めるアルゴリズムを実行すれば、実際の地図上での最短経路が分かります。最短経路を求めるアルゴリズムには、よく知られたものがあります。参考文献を参照してください。
地図のような直接的な例以外にも、グラフはさまざまな場面で利用されます。例えば、最近よく聞く「ソーシャルグラフ」の「グラフ」は、本稿で扱っているグラフからきています。解きたい問題をグラフで表現することができれば、グラフ上で使えるさまざまなアルゴリズムを適用できるようになるのです。グラフのアルゴリズムを利用して解くパズルはたくさんあります。
全体がつながっていて閉路（ループ）のない特殊なグラフが木で、これもざまざまな場面で利用されています（例えばXML文書は木で表現できます）。木はグラフの一種なのですが、PEARではInformation:Treeという、グラフとは関係のないパッケージで実装されているので、両方を統一的に扱うのは少し面倒です。
対象読者
- PHPの基本的な使い方を知っている方
- PHPでグラフを処理する方法に興味がある方
必要な環境
PEAR Image_GraphVizとPEAR Structures_Graph、Graphvizが動作する環境が必要です。筆者はWindows XPにXAMPP 1.6.6aとGraphviz 2.18、PEAR Image_GraphViz 1.3.0 RC3をインストールし、IE 7とFirefox 2、Opera 9、Safari 3で動作を確認しました（Graphvizのインストールについては本文中で解説します）。
なお、PEAR Structures_Graph 1.0.2はXAMPP 1.6.6aに含まれています。XAMPP 1.6.6aにはPEAR Image_GraphViz 1.2.1が含まれていましたが、バグがあるようなので次のようにして1.3.0 RC3にアップグレードしました。
c: cd \xampp\php pear upgrade -f Image_GraphViz-beta
コマンドの実行前に、c:\xampp\php\pear.iniの「"\xampp」を「"C:\xampp」に修正しました（参考：PEAR error on Config.php Line 1003 in Vista (solution)）。
Graphvizのインストール
Graphvizはグラフをさまざまな形式で描画することができるソフトウェアです。ソースコードと共にhttp://www.graphviz.org/で配布されており、無料で利用することができます。
PEAR Image_GraphVizは内部でGraphvizを呼び出してグラフを描画します。ですから、PEAR Image_GraphVizを使うためには、まずGraphvizが動作するように環境を整えておく必要があります。以下に手順を示します（Windowsの場合）。
- Graphvizのダウンロードページから、インストーラをダウンロードする。
- ダウンロードしたインストーラを実行し、インストールする（オプション等はすべてデフォルトのまま）。
- システム環境変数PATHに、Graphvizの実行ファイルのディレクトリ（C:\Program Files\Graphviz\bin）を追加する。
- コンピュータを再起動する。
