NAME

Sort::Topological - Topological Sort

SYNOPSIS

  use Sort::Topological qw(toposort);
  my @result = toposort($item_direct_sub, @items);

DESCRIPTION

Sort::Topological does a topological sort of an acyclical directed graph.

EXAMPLE

  my %children = (
                  'a' => [ 'b', 'c' ],
                  'c' => [ 'x' ],
                  'b' => [ 'x' ],
                  'x' => [ 'y' ],
                  'y' => [ 'z' ],
                  'z' => [ ],
                  );
  sub children { @{$children{$_[0]} || []}; } 
  my @unsorted = ( 'z', 'a', 'x', 'c', 'b', 'y' );
  my @sorted = toposort(\&children, \@unsorted);

In the above example %children is the graph, &children($x) returns a list of targets of the directed graph from $x.

@sorted is sorted such that:

for any $x in @sorted:

i.e.: 'y' is not reachable by 'z', 'x' is not reachable by 'y' or 'z', and so on.

CAVEATS

• Does not handle cyclical graphs.

STATUS

If you find this to be useful please contact the author. This is alpha software; all APIs, semantics and behavors are subject to change.

INTERFACE

This section describes the external interface of this module.

VERSION

Version 0.01, $Revision: 1.2 $.

AUTHOR

Kurt A. Stephens <ks.perl@kurtstephens.com>

COPYRIGHT

Copyright (c) 2001, 2002, Kurt A. Stephens and ION, INC.

SEE ALSO

>.