NAME

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

REQUIREMENTS

The following non-standard modules are used:

Carp::Assert
Class::Accessor::Fast

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');

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

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

DESCRIPTION

This module is designed to find scheduled paths between vertices in a directed graph. For scheduled paths, each edge has a time schedule, so they 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).

Methods

new

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

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

Creates a new graph, and adds edges if they are specified. (See "add_edge" for more details.)

add_edge

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

Adds edges to the graph. Arguments must either be hash references or Algorithm::ScheduledPath::Edge objects.

See Algorithm::ScheduledPath::Edge for more information.

find_paths

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

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

Returns an array reference of Algorithm::ScheduledPath::Path objects of any paths between the $origin and $dest. ($origin and $dest are assumed to be strings.)

Results are sorted by the earliest arrival time and then by the shorted travel time.

The following options are understood:

alternates

Specifies the number of alternate branches to include (defaults to 1).

earliest

The earliest departure time value included in the routes (defaults to 0).

If edges have negative departure and arrival times, then earliest must be defined.

latest

The latest arrival time value included in the routes.

max_time

The maximum travel time a route may have.

CAVEATS

The algorithm in this module is a brute-force search for all possible non-cyclic paths between vertices. No serious attempts have been made to optimize it.

It is a hand-rolled method that appears correct, but I have not attempted any formal proofs of the algorithm.

It has not been tested on huge datasets.

AUTHOR

Robert Rothenberg <rrwo at cpan.org>

Please submit bug reports and suggestions to the http://rt.cpan.org.

LICENSE

Copyright (c) 2004 Robert Rothenberg. All rights reserved. This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

SEE ALSO

If you are looking for a generic (un)directed graph module, see the Graph package. (This module does not make use of that package intentionally.)