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

Installation
    Installation can be done using the traditional Makefile.PL or the
    newer Build.PL methods.

    Using Makefile.PL:

      perl Makefile.PL
      make
      make test
      make install

    (On Windows platforms you should use nmake instead.)

    Using Build.PL (if you have Module::Build installed):

      perl Build.PL
      perl Build
      perl Build test
      perl Build install    

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

    More details can be found in the module documentation and example
    scripts.

REVISION HISTORY
    Changes since v0.40 (possibly incompatible changes marked with
    an asterisk):

0.41   Sat Jan 22 2005
	- commented-out passthrough option in bus.pl since it will
          filter valid subpaths incorrectly
	- corrected inaccurate REQUIREMENTS section in POD, README
	- explicitly uses Data::Types module
	* uses Scalar::Util module
	- fixed bugs in strinklike and numberlike test functions
	- added more tests
	- more documentation updates
	- callback is called for unjoined paths returned by find_paths
	- callback option for find_paths is passed the split index
	- path_id, origin and destination can be objects so long as they
	  have string conversion and comparison overloaded; likewise,
	  depart_time and arrive_time can be objects so long as they too
          have numeric conversion and comparison overloaded.
	* copy methods renamed to clone
	* uses Clone module
	- more documentation updates
	- when copying edge, warning when data contains a reference
	* interface for Edge::new constructor is changed: it no longer
          accepts hash references for arguments
	* uses Class::Meta instead of Class::Accessor
	- modules register warnings (warnings only when enabled)
	- added more tests
	- Path::add_edge checks that arrive_time >= depart_time
	* requires Test::Exception and Test::Warn for tests
	- added use of callback in eg/bus.pl demo
	- added callback option in find_paths
	- corrected typos in documentation

    A complete revision history can be found in the Changes file.

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>

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
    Graph package.