Location : Home > Languages > Perl > Package
Title : Algorithms::Graphs::TransitiveClosure
 		Toolbox Logo

名称

　Algorithms::Graphs::TransitiveClosure - 推移閉包を計算

概要

use Algorithms::Graphs::TransitiveClosure qw /floyd_warshall/;

my $graph = [[1, 0, 0, 0], [0, 1, 1, 1], [0, 1, 1, 0], [1, 0, 1, 1]];
floyd_warshall $graph;
print "There is a path from 2 to 0.\n" if $graph -> [2] -> [0];

my $graph2 = {one   => {one => 1},
              two   => {two => 1, three => 1, four => 1},
              three => {two => 1, three => 1},
              four  => {one => 1, four  => 1}};
floyd_warshall $graph2;
print "There is a path from three to one.\n" if
    $graph2 -> {three} -> {one};

説明

　これはよく知られた Floyd-Warshall アルゴリズムの実装である。[1,2]
　サブルーティン floyd_warshal は有向グラフを入力とし、推移閉包（transitive closure）を計算して返す。入力したグラフを変更するので最初のグラフが必要であればあらかじめコピーをしておく必要がある。
　サブルーティンは以下の２つの方法で入力として渡すことができる。

floyd_warshall ARRAYREF

　グラフ G = (V, E) は V x V を表すリストのリスト $graph として記述される。頂点 $i と $j の間に端点があれば（または $i == $j であれば） $graph -> [$i] -> [$j] == 1 である。その他の V x V の点の組み合わせ ($k, $l) について $graph -> [$k] -> [$l] == 0 である。
　結果の $graph は、 $i == $j または G において $i から $j へ経路が存在する場合 $graph -> [$i] -> [$j] == 1 となり、それ以外は $graph -> [$i] -> [$j] == 0 となる。

floyd_warshall HASHREF

　グラフ G = (V, E) はラベル付けされた頂点により V x V を表すハッシュのハッシュ $graph として記述される。頂点 $label1 と $label2 の間に端点があれば（または $label1 eq $label2 であれば） $graph -> {$label1} -> {$label2} == 1 である。その他の V x V の点の組み合わせ ($label3, $label4) については $graph -> {$label3} -> {$label4} は存在しない。
　結果の $graph は、$label1 eq $label2 または G において $label1 から $label2 への経路が存在する場合 $graph -> {$label1} -> {$label2} == 1 となり、それ以外は存在しない。

使用例

    my $graph = [[1, 0, 0, 0],
                 [0, 1, 1, 1],
                 [0, 1, 1, 0],
                 [1, 0, 1, 1]];
    floyd_warshall $graph;
    foreach my $row (@$graph) {print "@$row\n"}

    1 0 0 0
    1 1 1 1
    1 1 1 1
    1 1 1 1

    my $graph = {one   => {one => 1},
                 two   => {two => 1, three => 1, four => 1},
                 three => {two => 1, three => 1},
                 four  => {one => 1, three => 1, four => 1}};
    floyd_warshall $graph;
    foreach my $l1 (qw /one two three four/) {
        print "$l1: ";
        foreach my $l2 (qw /one two three four/) {
            next if $l1 eq $l2;
            print "$l2 " if $graph -> {$l1} -> {$l2};
        }
        print "\n";
    }

    one: 
    two: one three four 
    three: one two four 
    four: one two three

複雑性

　アルゴリズムの計算時間はグラフに含まれる頂点の数の３乗に比例する。本パッケージの著者は他のもっと速いアルゴリズムを知らないし、これが最適であるという証明も見たことがない。ただし特殊なケース、たとえば有界な種数（bounded genus）を持つ面に埋め込まれたグラフや疎な接続行列を持つグラフの場合には、頂点の数の３乗よりも高速なアルゴリズムが存在することに留意すること。
　本アルゴリズムにより利用されるスペースは、結果の推移閉包が端点の２乗の数の点を含むように高々頂点の数の２乗程度である。グラフがリストのリストで記述されている場合には２乗の限界は達成されており、リストのリストは既にその大きさとなっている。しかしながらハッシュのハッシュで記述されている場合には結果の推移閉包のサイズに線形のスペースしか使わない。

文献

　Floyd-Warshall アルゴリズムは Warshall の定理 [3] に基づく Floyd [2] による。本パッケージの実装は Cormen, Leiserson and Rivest [1] にある Floyd-Warshall のアルゴリズムに基づく。

参照

  1. Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest: Introduction to Algorithms. Cambridge: MIT Press, 1990. ISBN 0-262-03141-8.
  2. Robert W. Floyd: "Algorithm 97 (SHORTEST PATH)". Communications of the ACM, 5(6):345, 1962.
  3. Stephan Warshall: "A theorem on boolean matrices." Journal of the ACM, 9(1):11-12, 1962.

履歴

$Date: 1999/03/01 19:51:11 $

$Log: TransitiveClosure.pm,v $
Revision 1.3  1999/03/01 19:51:11  abigail
名前空間を Algorithm:: に変更

Revision 1.2  1998/03/23 04:00:37  abigail
ARRAYREF におけるループ変数の順序を修正。
i, j, k ではなく k, i, j となっていた。

Revision 1.1  1998/03/22 06:54:42  abigail
Initial revision

著者

　本パッケージはAbigail によって書かれた。

著作権

　Copyright 1998 by Abigail.

ライセンス

　本パッケージはフリーかつオープンなソフトウェアである。
　本パッケージを利用・複製・修正・再配布・販売してもよく、以下の条件に触れない限りいかなる修正品を作成してもよい。

　本パッケージは「現状のまま」で、明示であるか暗黙であるかを問わず、何らの保証もなく提供される。ここでいう保証とは、商品性・特定の目的への適合性及び権利非侵害についての保証も含む。

Toolbox Logo
 Updated : 2006/07/28