グラフライブラリ

グラフ構造に対するアルゴリズムを実装するには、グラフを表現するデータ構造を選択する必要があります。ノード間の関係は行列によりあらわすことができます。これは隣接行列と呼ばれ、例えば、i,j要素が1のときノードiとノードjの間にエッジがあり、0のとき無いといった具合に表現できます。当然、スパースなネットワークの場合、0だらけの行列となりメモリ効率が悪くなります。別の表現方法としてリスト構造があります。ポインタで数珠つなぎすることによって表現します。今は、グラフに関するライブラリが充実しているため、グラフ理論の多くのアルゴリズムの恩恵を受けることができます。私はC／C++系のコーディングではboost graph libraryを、perlではGraphモジュールをよく用います。例えば以下のような２項関係を記述したファイルがあるとします。

>example.txt

nodeA<tab>nodeB
nodeB<tab>nodeC
nodeC<tab>nodeA

この２項関係をグラフで表すと"nodeA->nodeB->nodeC->nodeA"とcyclicなグラフとなります。このようなファイルを入力としてDAG (Directed Acyclic Graph : 非巡回有向グラフ)かどうかを判定するプログラムは以下のように簡単に書けます。

> isDag.pl

#!/usr/bin/perl

use Graph;
use Getopt::Std;
getopt('i');

$file=$opt_i;

$g=Graph->new(%directed);
open(IN,"$file");
$n=0;
while($line=<IN>){
  $line=~s/\n//;
  ($n1,$n2)=split("\t",$line);
  $g->add_edge("$n1","$n2");
}
close(IN);

$isdag="ndag";
if($g->is_dag()){$isdag="dag";}
print "$isdag\n";

-----------------------

プログラムを実行してみる (実行にはGraphモジュールが必要です。CPANからgetしてください) 。

./isDag.pl -i example.txt

ndag

入力グラフは巡回 (あるノードを起点として同じノードへ戻ってくるパスがある) グラフなのでDAGではないので"ndag"と表示される（はず）。