Algorithm::ScheduledPath - Find scheduled paths in a directed graph

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

　Algorithm::ScheduledPath - 有向グラフでスケジュールされたパスを探索

　以下の標準的でないモジュールを使用している。

Carp::Assert
Class::Meta
Data::Types
Scalar::Util

use Algorithm::ScheduledPath;
use Algorithm::ScheduledPath::Path;

$graph = new Algorithm::ScheduledPath();

$graph->add_edge(
   {
    path_id     => 'R',
    origin      => 'A', depart_time =>   1,
    destination => 'B', arrive_time =>   4,
   },
   {
    path_id     => 'R',
    origin      => 'B', depart_time =>   5,
    destination => 'C', arrive_time =>   9,
   },
   {
    path_id     => 'D',
    origin      => 'A', depart_time =>   2,
    destination => 'C', arrive_time =>   7,
   }
);

my $paths = $graph->find_paths('A', 'C');

foreach my $path (@$paths) {
   print join(" ", map { $path->$_ } (qw(
   origin depart_time destination arrive_time ))), "\n";
}

# 出力は以下の通り
#  A 2 C 7
#  A 1 C 9

説明

　本モジュールは有向グラフにおける頂点間のスケジュール化されたパスを探索するよう設計されている。各辺は後続するスケジュールを持つ辺を含んだパスとなるよう time schedule を持っている。循環的なパスはないものとする（頂点を通るパスは２度は通らない）。

　専門的な説明を抜きにすると、本モジュールでは相互に結び付けられたバスルートのシリーズをとり、点 'A' から点 'B' （間の乗り換えはないものとする）までのスケジュールを取得することができる。

メソッド

new

$graph = Algorithm::ScheduledPath->new();

$graph = Algorithm::ScheduledPath->new(
   {
    path_id => 1, origin      => 'A', depart_time => 100,
                  destination => 'B', arrive_time => 200,
   },
   {
    path_id => 1, origin      => 'B', depart_time => 200,
                  destination => 'C', arrive_time => 300,
   },
);

　新しいグラフを生成し、ユーザが特定すれば辺を追加する。（詳しくは add_edge を見よ。）

add_edge

$graph->add_edge( {
   id          =>   0, path_id => 1,
   origin      => 'C', depart_time => 300,
   destination => 'D', arrive_time => 400,
   }
);

　グラフに辺を追加する。引数はハッシュ参照または Algorithm::ScheduledPath::Edge オブジェクトでなければならない。更なる情報は Algorithm::ScheduledPath::Edge を見よ。

find_paths

$routes = $graph->find_paths( $origin, $dest );

$routes = $graph->find_paths( $origin, $dest, \%options );

　$origin と $dest の間のパスの Algorithm::ScheduledPath::Path オブジェクトの配列参照を返す。（$origin と $dest は文字列であること）
　結果は最速到着時刻順に、その次に短縮移動時間順に格納される。以下のオプションが利用可能。

alternates：
あるパスに対する代替の枝の数（デフォルトは 1 ）。
earliest：
ルートに含まれる最速出発時刻（デフォルトは 0 ）。もし短点が負の出発時刻及び到着時刻になれば最速出発時刻は定義されなければならない。
latest：
ルートにおける最遅到着時刻。
max_time：
ルートにおける最大移動時間。
callback：
パスを評価するためのコールバックルーチン。ルーチンが真値を返せばパスは採択。そうでなければ却下。コールバックは３つの値を渡される。
$path

　フィルタに架けられるパスを含む Algorithm::ScheduledPath::Path オブジェクト。

$options

　find_paths に渡されるオプションを含む。ユーザ定義のコールバックへのオプションを特定してもよい。しかしながら将来のバージョンで追加されるかもしれないパラメータとコンフリクトを起こさないためには、ユーザ定義のパラメータ名には工夫が必要である。たとえばアンダースコアを使うなど（_name）。

$index
　２つのパスが追加されたパスにおけるインデクス。
```
if ($index > 0) {
   my $last = $path->get_edges->[$index-1];
   my $edge = $path->get_edges->[$index];
   ...
}
```
　単一の端点のパスではインデクスは 0 である。

　以下は与えられた頂点を通る全てのパスを要請する "pass through" オプションを実装し例である。

callback => sub {
   my ($path, $options, $index) = @_;
   return ( ($index == 0) ||
            (!defined $options->{pass_through}) ||
              $path->has_vertex($options->{pass_through})
   );
},

　上の例はある頂点を通る全てのサブパスを要請するような長いパスには適切に動作はしないことに注意すること。
　フィルタ結果をコールバックする例は配布した中の eg/bus.pl スクリプトにある。
　コールバックは端点の各集合に対して呼び出されることに注意すること。探索時に望まないパスまで探索しないことで速度を上げることと、計算的に能力の必要なフィルタリングをおこなって探索の速度を落とすのかの間にはバランスがある。

注釈

　本モジュールのアルゴリズムは頂点間の非循環的なあらゆる可能なパスに対してしらみつぶしで探索している。これを最適化する試みは行っていない。
　これを正すのは手作業となるが、アルゴリズムの公式な証明が無い。
　巨大なデータセットに対するテストは行っていない。

著者

　Robert Rothenberg, <rrwo at cpan.org>

　http://rt.cpan.org でバグ報告や示唆を行って欲しい。

謝辞

　 "string-like" や "number-like" オブジェクトについて示唆してくれた http://www.perlmonks.org のポスターに感謝。

ライセンス

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

参考資料

　一般の（非）有向グラフモジュールを探しているなら Graph パッケージを見よ。（本モジュールは意図的にそれを使っていない。）

Updated : 2008/08/30