NAME

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

DESCRIPTION

This module is designed to find scheduled paths in directed graph.

In less technical parlance, it 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_leg" for more details.)

add_leg

$graph->add_leg(
  Algorithm::ScheduledPath::Edge->new({
    id          =>   0, path_id => 1,
    origin      => 'C', depart_time => 300,
    destination => 'D', arrive_time => 400,
  })
);

Adds an edge (leg) to the graph. Arguments must be Algorithm::ScheduledPath::Edge objects.

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

find_routes

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

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

$routes = $graph->find_routes( $origin, $dest, $count, $earliest );

Returns an array reference of Algorithm::ScheduledPath::Path objects. Results are sorted in the earliest arrival time first.

$count specifies the number of alternate branches to include (it defaults to 1).

$earliest is the earliest time value included in the routes.

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.