Algorithm::ScheduledPath is a Perl module that helps you to find scheduled paths in a directed graph.

SYNOPSIS

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";
}

# Outputs the following:
# A 2 C 7
# A 1 C 9

This module is designed to find scheduled paths between vertices in a directed graph. For scheduled paths, each edge has a time schedule, so that a path must contain edges with successivly later schedules. It will not return cyclic paths (paths which pass through a vertex more than once).

In less technical parlance, this module lets you do things like take a series of interconnected bus routes and determine a schedule of how to get from point A to point B (noting any transfers in between).