Kurt Stephens > Data-Match-0.06 > Sort::Topological

Download:
Data-Match-0.06.tar.gz

Dependencies

Annotate this POD

CPAN RT

New  3
Open  0
View/Report Bugs
Module Version: 0.02   Source  

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 ^

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 ^

>.

syntax highlighting: