NAME

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

REQUIREMENTS

The following non-standard modules are used:

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

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

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 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).

Methods

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,
    },
  );

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 the Algorithm::ScheduledPath::Edge manpage for more information.

find_paths

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

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

Returns an array reference of the Algorithm::ScheduledPath::Path manpage 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) for a path.

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.

callback

Define a callback routine to evaluate a path. If the routine returns a true value, the path is accepted; otherwise it is rejected.

The callback is passed three values:

$path

This is a the Algorithm::ScheduledPath::Path manpage object which contains the path to be filtered.

$options

This contains the options passed to find_paths. You may specify custom options for your callback. However, to ensure that your parameter names do not conflict with parameters that may be added in future versions, you should start them with an underscore (e.g. "_name").

$index

This is the index in the path where two paths were joined:

  if ($index > 0) {
    my $last = $path->get_edges->[$index-1];
    my $edge = $path->get_edges->[$index];
    ...
  }

It the index is 0, then it contains paths with a single edge.

The following example implements a "pass through" option that requires all paths to pass through a given vertex:

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

Note that the above example will not work properly for long paths as it requires all subpaths to pass through a vertex.

An example of using callbacks to filter results is in the eg/bus.pl script included with the distribution.

Remember that the callback is called for each set of edges. There is a balance between improving the search speed by filtering out unwanted paths during the search and slowing down the search by computationally expensive filtering.

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.

Acknowledgements

Thanks to posters on http://www.perlmonks.org for suggestions on type checking for "string-like" and "number-like" objects.

LICENSE

Copyright (c) 2004-2005 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 the Graph manpage package. (This module does not make use of that package intentionally.)