PEAR Structures_Graphでグラフを操作する
もちろん、グラフは描いて終わりではありません。地図をグラフで表現すれば、2地点間の最短経路や最短時間などを求めることができます（場所をノードとし、距離あるいは時間をエッジの重み属性にします）。部品の依存関係をグラフで表せば、生産のプランニングを行うことができます（部品をノードとし、その依存関係をエッジで表現します）。
残念なことにグラフを描画するのに利用したImage_GraphVizは、グラフのための高度なアルゴリズムを持っていません。別のパッケージStructures_Graphを使います（逆に、Structures_Graphには描画機能はありません）。悪いことに、この2つのパッケージはどちらもグラフ・オブジェクトを生成するのですが、両者に直接の互換性はありません。本格的に使う場合は、何かしらの変換メカニズムや、抽象化が必要になるでしょう。
グラフの生成
次のようなグラフを生成します（ここでは描画は行いません）。これ自体は抽象的なグラフととらえてもらってかまわないのですが、具体的なイメージがないと理解しにくい場合には、ある製品の製造工程において、「1」という部品を材料にして、「node #2」という部品と「第3ノード」という部品を作っているとでも考えてください。
まず、グラフを生成します（添付ファイルの「graph7b.php」を参照）。
require_once 'Structures/Graph.php'; $graph = new Structures_Graph();
デフォルトでは有向グラフが生成されます。Structures_Graph(false)とすれば無向グラフになります。
ノードの生成
3つのノードを生成し、名前を付けます。名前は何でもかまいません。
$nodeOne = new Structures_Graph_Node(); $nodeTwo = new Structures_Graph_Node(); $nodeThree = new Structures_Graph_Node(); $nodeOne->setData(1); $nodeTwo->setData('node #2'); $nodeThree->setData('第3ノード');
生成したノードをグラフに追加します。
$graph->addNode(&$nodeOne); $graph->addNode(&$nodeTwo); $graph->addNode(&$nodeThree);
エッジの生成
nodeOneとnodeTwo、nodeOneとnodeThreeの間にエッジを生成します。
$nodeOne->connectTo($nodeTwo); $nodeOne->connectTo($nodeThree);
ノードの性質
グラフのノードが持つエッジの数を次数(degree)と言います。次のようにして、ノードに入るエッジとノードから出るエッジの数が分かります。
echo "<p>NodeOne's inDegree: " . $nodeOne->inDegree()."</p>"; // 0 echo "<p>NodeOne's outDegree: " . $nodeOne->outDegree()."</p>"; // 2
あるノードにつながっているノードはgetNeighbours()で取得できます。
echo '<ul>'; foreach($nodeOne->getNeighbours() as $node) echo '<li>'.$node->getData().'</li>'; echo '</ul>';
結果は次のとおりです。
- node #2
- 第3ノード
トポロジカル・ソート
少し高度なアルゴリズムを実行してみましょう。トポロジカル・ソートです。トポロジカル・ソートの結果はノードの列です。グラフのすべてのエッジについて、そのヘッド（矢印の起点）のノードの順番が、テール（矢印の終点）のノードの順番よりも小さくなっていなければなりません。これは、ノードが部品、エッジがその依存関係であるときに、製品を完成させることができる部品の作成順序を与えます。
例えば下のグラフでは、ノード1、7、9がノード3のテールになっているので、トポロジカル・ソートの結果において、1、7、9は3より後に来なければなりません。当然ですが、グラフにループがあると、トポロジカル・ソートはできません。
グラフの生成
有向グラフを生成します（添付ファイルの「graph8.php」を参照）。
require_once 'Structures/Graph/Manipulator/TopologicalSorter.php'; $graph=new Structures_Graph();
ノードとエッジの生成
エッジの配列からノードとエッジを生成しましょう。
//エッジを配列に格納しておく $edges=array( array(3,9), array(3,7), array(3,1), array(9,2), array(9,8), array(7,8), array(7,6), array(8,4), array(8,5) ); foreach($edges as $edge){//$edgesのすべてのエッジについて for($i=0;$i<2;++$i){//ノードを処理する if(!$nodes[$edge[$i]]){//ノードが生成されていなければ $nodes[$edge[$i]]=new Structures_Graph_Node();//ノードを生成し、 $nodes[$edge[$i]]->setData($edge[$i]);//名前を付け $graph->addNode(&$nodes[$edge[$i]]);//グラフに追加する } } $nodes[$edge[0]]->connectTo($nodes[$edge[1]]);//ノード同士をつなぐ }
ループの検出
Structures_Graphにはループを検出するためのメソッドStructures_Graph_Manipulator_AcyclicTest::isAcyclicが用意されています。先に述べたように、グラフにループがあるとトポロジカル・ソートはできないので、まず、このメソッドを使って、ループがないことを確かめましょう。
トポロジカル・ソートの実行・結果の表示
トポロジカル・ソートを実行し、結果を変数に格納します。
if(Structures_Graph_Manipulator_AcyclicTest::isAcyclic($graph)){
$result=@Structures_Graph_Manipulator_TopologicalSorter::sort($graph);
結果はノードの配列の配列になっているので、次のように表示させることができます。
echo '<p>'; foreach($result as $level) foreach($level as $node) echo $node->getData().' '; // 3 9 7 1 2 8 6 4 5 echo '</p>'; }
グラフの画像と照らし合わせると、トポロジカル・ソートの条件を満たしていることが分かります。
他には？
残念なことに、Structures_Graphはまだ発展途上のパッケージで、グラフのための高度なアルゴリズムは、トポロジカル・ソート以外には実装されていません。とはいえ、ノードやエッジの基本的な操作は実装されているので、必要なものを自分で実装することはもちろん可能です。高度で高性能なグラフ・アルゴリズムが必要な場合には、PHPの標準的な枠組みにとらわれるべきではないでしょう。例えば、標準になりつつあるC++ Boostには、Boost Graph Library (BGL)というライブラリが用意されています。このライブラリは、グラフに関する基本的なアルゴリズムを網羅している上に、C++なので性能も高いです。
おわりに
PEAR Image_GraphVizを使ってグラフを描画する方法と、PEAR Structures_Graphを使ってグラフを使ったアルゴリズムを実行する方法を紹介しました。
Image_GraphVizを使えば、グラフを簡単に描画することができます。このライブラリは、広く使われているグラフ描画ツールであるGraphvizを内部で利用しており、Graphvizについて調べることで、描画方法をさまざまにカスタマイズすることができます。
Structures_Graphはまだ発展途上と言えるライブラリですが、PHP上でグラフを扱う方法と、簡単なアルゴリズムを提供してくれます。
注意しなければならないことは、この2つのライブラリのグラフ・オブジェクトに、直接の互換性がないことです。将来、PEARの名の下に、両者が統一されることを期待しましょう。
参考文献
- R. ブランデンベルク, P. グリッツマン著, 石田基広訳. 最短経路の本. シュプリンガー・ジャパン, 2007.
- トマス・H. コルメンほか著, 浅野哲夫ほか訳. アルゴリズムイントロダクション（第2巻）. 近代科学社, 改訂2版, 2007.
- ドナルド・E・クヌース著, 有澤誠ほか訳. The Art of Computer Programming Volume1 Fundamental Algorithms, アスキー, 原著第3版, 2004.
- 加納幹雄. 情報科学のためのグラフ理論. 朝倉書店, 2001.
