Location : Home > Languages > Perl > Package Title : Algorithm::SixDegrees

名称

　Algorithm::SixDegrees - 要素間リンクのパス探索

バージョン

　Version 0.03

概要

use Algorithm::SixDegrees;

my $sd1 = Algorithm::SixDegrees->new();
$sd1->data_source( actors => \&starred_in );
$sd1->data_source( movies => \&stars_of );
@elems = $sd1->make_link('actors', 'Tom Cruise', 'Kevin Bacon');

my $sd2 = Algorithm::SixDegrees->new();
$sd2->forward_data_source( friends => \&friends, @args );
$sd2->reverse_data_source( friends => \&friend_of, @args );
@elems = $sd2->make_link('friends', 'Bob', 'Mark');

説明

　Algorithm::SixDegrees は２つの特定の要素間の最短の経路を探索する横型探索の実装である。すなわち、本モジュールは要素を束にし、その中の２つの関係を探索しようとするものである。

コンストラクタ

new()

　Algorithm::SixDegrees はオブジェクトとしての利用を要請する。（まだ）スタンドアロンとして使用されることはない。new は１つの引数もとらない。

関数

forward_data_source( name => \&sub, @args );

　sub を呼び出すことにより取得される name に関係するデータ集合の中のすべての要素を Algorithm::SixDegrees に与える。サブルーチン規則を見よ。
　私の友人で例を言えば、Bob が Mark を友人だと思っているが Mark は Bob を友人だと思っていない場合、"Bob" を引数として sub を呼び出すと "Mark" を返すが、"Mark" を引数にして sub を呼び出しても "Bob" を返さない。

reverse_data_source( name => \&sub, @args );

　sub を呼び出すことにより取得される name に関係するデータ集合の中のすべての要素を Algorithm::SixDegrees に与える。サブルーチン規則を見よ。
　上と同じ例で言えば"Bob" を引数として sub を呼び出しても "Mark" を返さないが、"Mark" を引数にして sub を呼び出すと "Bob" を返す。

data_source( name => \&sub, @args );

　forward 及び reverse の双方で用いることのできるようデータ集合を設定する。データソースが相互関係的であるときには有用である。すなわち、俳優／映画作品 という例では Kevin Bacon は Mystic River に出ており、Mystic River は常に Kevin Bacon を持つ。

make_link

　リンクを生成する。呼び出し時のコンテキストによってリストまたは配列参照を返す。

error

　$Algorithm::SixDegrees::ERROR の現在の値を返す。サブルーチン規則を見よ。

サブルーチン規則

　サブルーチンは少なくとも１つの引数を持たねばならない。この引数には固有の識別子を含む必要があり、引数に関係した固有の識別子のリストを返す。この固有の識別子は eq で比較される。
　識別子はデータタイプにおいてユニークでなければならない。俳優／映画作品という関係では "Kevin Bacon" は俳優の名称にも映画の名称にもなれる。
　リンクされたデータタイプはリンクを通して関係する識別子を返す。俳優／映画作品という関係では actor サブルーチンは映画作品を返すべきであるし、 movie サブルーチンは俳優を帰すべきである。
　追加的な引数を用いてもよいが、これらはオブジェクト内に格納され、サブルーチンに２つめ以降の引数として渡される。たとえば結果のキャッシュを用いて tie ハンドルなどに渡す必要がある場合には有用である。
　明示的な undef を返したい場合、$Algorithm::SixDegrees::ERROR にエラーコードを設定すること。明示的 undef はそこで探索を終了することを意味する。1要素のリストを返すべきである。

著者

　Pete Krawczyk, <petek@cpan.org>

バグ

　バグ報告や機能の要望は bug-algorithm-sixdegrees@rt.cpan.org または http://rt.cpan.org のウェブインタフェースを通じて。
　知らせていただければ、バグに関する進展や変更事項を連絡する。

謝辞

　フレームワークを提供しかなり高速になる手助けをしてくれた Module::Starter を書いたAndy Lester と Ricardo Signes。
　いったん削除したアルゴリズムを再度導入することを可能にした、http://livejournal.com のサイト情報を知らせてくれた Brad Fitzpatrick。

著作権とライセンス

　Copyright 2005 Pete Krawczyk, All Rights Reserved.

　本プログラムはフリーソフトウェアであり、Perl 本体と同等の条件で修正／再配布してもよい。

Updated : 2007/09/01