NAME

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

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(
  Algorithm::ScheduledPath::Edge->new({
    id          =>   0, path_id => 1,
    origin      => 'C', depart_time => 300,
    destination => 'D', arrive_time => 400,
  })
);

Adds an edge to the graph. Arguments must be 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 in the earliest arrival time first.

The following options are understood:

alternates

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

earliest

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

CAVEATS

This module does not do any kind of sophisticated searching techniques for finding paths or determining the most efficient schedule. It is a hand-rolled recursive method that appears correct but I have not done any proofs of the method. The sorting techniques are certainly not optimized. It has not been tested on huge datasets.

AUTHOR

Robert Rothenberg <rrwo at 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.)