PHPにおけるグラフ描画とアルゴリズム

PEARライブラリ活用 (3)

PEAR Image_GraphVizでグラフを描画する

　ここでは、図のようなグラフを生成／描画します。

グラフの例2（graph2.phpで描画）

グラフの生成

　まず、グラフを生成します。

require_once 'Image/GraphViz.php';

$graph = new Image_GraphViz();

　デフォルトでは有向グラフ（エッジに向きの概念があるグラフ）が生成されます。new Image_GraphViz(false)とすると無向グラフになります。

ノードの生成

　次にノードを生成します。

$graph->addNode(
  'Node1',
  array(
    'URL'   => 'http://link1',
    'label' => 'ボックス',
    'shape' => 'box',
    'fontname' => 'Arial Unicode MS'
  )
);

　ノードにはさまざまな属性を与えることができます。この例では、URLは「http://link1」、ラベルは「ボックス」、形は「box」にしています。URLで指定した場所にはクリックで移動できるようになります。ラベルには日本語が使えます。日本語を使う際には、日本語を表示可能なフォントを指定し、PHPのファイルはUTF-8（BOMなし）で記述するようにしてください。形は「box」の他にも、circleやellipseなど、さまざまなものが用意されています。Node Shapesを参照してください。

　もう少しノードを追加しましょう。

$graph->addNode(
  'Node2',
  array(
    'URL'      => 'http://link2',
    'fontsize' => '14'
  )
);

$graph->addNode(
  'Node3',
  array(
    'URL'      => 'http://link3',
    'fontsize' => '20'
  )
);

　ラベルのフォントサイズを設定して、ノードを追加しています。先の場合と違って、ラベルを明示していないので、addNodeの最初の引数（つまりNode2やNode3）がラベルになります。属性には、ここで使ったURLやlabel、shape、fontsizeのほかにさまざまなものが用意されています。Node, Edge and Graph Attributesを参照してください。

エッジの生成

　先に作成したノードNode1とNode2を結ぶエッジを生成します。

$graph->addEdge(
  array(
    'Node1' => 'Node2'
  ),
  array(
    'color' => 'red',
    'label' => 'Edge Label'
  )
);

　ここで作成しているのは有向グラフなので、Node1からNode2に向かって矢印が描かれることになります。矢印の色は赤、「Edge Label」というラベルが付くように属性を設定しています。エッジのための属性もNode, Edge and Graph Attributesを参照してください（Used Byに「E」とあるものがエッジで使える属性です。「dot」とあるものは有向グラフのもの、「neato」とあるものは無向グラフのものです）。

グラフの描画

　ノードとエッジを生成すれば、グラフは定義できたことになります。描画してみましょう。

$graph->image();

　はじめに示したようなグラフが表示されれば成功です。うまくいかない場合、Graphvizの実行ファイルが見つかっていない可能性があります。Apacheのerror.logを参照してください。

　先に述べたように、new Image_GraphViz(false)とすると無向グラフになるので、描画結果は下のようになります（エッジに矢印がありません）。

グラフの例3（グラフの例2を無向にしたもの）

　ウェブサーバからのレスポンスはimage/svg+xmlとして送られてきます（つまりSVG形式です）。HTML文書中にグラフを埋め込みたいときは、次のようにするといいでしょう（graph2.html）。

<object type='image/svg+xml' data='graph2.php' style='width:197pt; height:143pt' />

エッジの配列からのグラフ生成

　これまで紹介した方法で毎回グラフを生成するのは面倒なので、エッジの配列（各要素がエッジを表す2次元配列）からグラフを生成する方法を紹介しましょう。

require_once 'Image/GraphViz.php';

$graph = new Image_GraphViz();//グラフを生成する

// エッジの配列。この例は、
// 3番目のノードと9番目のノードがつながっている
// 3番目のノードと7番目のノードがつながっている
// 以下略
$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]]=true;//ノードを追加したことを記憶する
      $graph->addNode($edge[$i]);//グラフにノードを追加する
    }
  }
  $graph->addEdge(array($edge[0]=>$edge[1]));//グラフにエッジを追加
}

$graph->image();//グラフを描画する

　変数$nodesでノードをグラフに追加したかどうかを管理しています。描画結果は次のようになります。

グラフの例4（graph4.phpで描画）

　new Image_GraphViz(false)として無向グラフにすると、次のようになります。

グラフの例5（グラフの例4を無向にしたもの）

　これまで見てきたように、Graphvizは、適当なアルゴリズムに基づいてノードを自動的に配置してくれるので、自分で座標を設定する必要はありません。アルゴリズムを指定することもできますが、詳細はGraphvizのドキュメントを参照してください。例えば、Image_GraphViz(false,array('mode'=>'KK'))としてグラフを生成すると、結果が変わります（配置の最適化に最速降下法を使うようになります）。

グラフの例6（グラフの例5のアルゴリズムを変更した結果）