CodeZine(コードジン)

特集ページ一覧

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

PEARライブラリ活用 (3)

  • LINEで送る
  • このエントリーをはてなブックマークに追加
2008/05/13 14:00

ダウンロード サンプル (3.0 KB)

目次

PEAR Image_GraphVizでグラフを描画する

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

グラフの例2(graph2.phpで描画)
グラフの例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を無向にしたもの)
グラフの例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で描画)
グラフの例4(graph4.phpで描画)

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

グラフの例5(グラフの例4を無向にしたもの)
グラフの例5(グラフの例4を無向にしたもの)

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

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

  • LINEで送る
  • このエントリーをはてなブックマークに追加

修正履歴

  • 2008/05/16 16:09 GraphvizのURLを修正しました。

バックナンバー

連載:PEARライブラリ活用

もっと読む

著者プロフィール

  • WINGSプロジェクト 矢吹 太朗(ヤブキ タロウ)

    <WINGSプロジェクトについて> 有限会社 WINGSプロジェクトが運営する、テクニカル執筆コミュニティ(代表 山田祥寛)。主にWeb開発分野の書籍/記事執筆、翻訳、講演等を幅広く手がける。2018年11月時点での登録メンバは55名で、現在も執筆メンバを募集中。興味のある方は、どしどし応募頂...

  • 山田 祥寛(ヤマダ ヨシヒロ)

    静岡県榛原町生まれ。一橋大学経済学部卒業後、NECにてシステム企画業務に携わるが、2003年4月に念願かなってフリーライターに転身。Microsoft MVP for ASP/ASP.NET。執筆コミュニティ「WINGSプロジェクト」代表。 主な著書に「入門シリーズ(サーバサイドAjax/XM...

あなたにオススメ

All contents copyright © 2005-2021 Shoeisha Co., Ltd. All rights reserved. ver.1.5