NAME

Sort::TSort - topological sort; a very simple wrapper around 'tsort' command line utility.

SYNOPSIS

  use Sort::TSort qw(tsort);
  my $sorted_items = toposort($ordered_pairs);

DESCRIPTION

Sort::TSort::tsort performs a topological sort of an acyclic directed graph defined by list of edges (pairs of vertices). Sort::TSort does this by invoking external command tsort (1).

Exports one subroutine on demand: tsort.

If external program tsort is not installed, the subroutine dies.

If there are cycles in the graph, the subroutine dies.

If an item of input array has any other length than 2, the subroutine dies (this behaviour is different from external tsort, which accept any even number of items per row).

Sort::TSort tries to do its best to deal correctly with non-ASCII data (by encoding input strings in utf-8 and decoding result from utf-8).

EXAMPLE

  use Sort::TSort qw/tsort/;
  my $partial_order = [
    [ 'a', 'b' ],
    [ 'a', 'c' ],
    [ 'c', 'x' ],
    [ 'b', 'x' ],
    [ 'x', 'y' ],
    [ 'y', 'z' ],
  ];

  my $sorted = tsort($partial_order);

  # Result:
  # $sorted = [
  #     'a',
  #     'c',
  #     'b',
  #     'x',
  #     'y',
  #     'z'
  #   ];


  my $partial_order = [
    [ 'a', 'b' ],
    [ 'b', 'c' ],
    [ 'c', 'a' ],
  ];

  my $sorted = tsort($partial_order);

  # Result: tsort dies (there is a cycle 'a-b-c')


  my $partial_order = [
    [ 'a', 'b', 'c', 'd' ],
    [ 'b', 'c' ],
    [ 'c', 'a' ],
  ];

  my $sorted = tsort($partial_order);

  # Result: tsort dies (first row doesn't have exactly 2 items)

CAVEATS

Requires external tsort program to be installed.

Not tested on Windows (probably it can be made to work there with tsort from Perl Power Tools).

Not intended to sort very large arrays (input and output data are copied multiple times, join'ed and split'ed, which may lead to unnecessary memory consumption).

SEE ALSO

tsort (1), tsort from PerlPowerTools, Sort::Topological, tcsort, Algorithm::TSort

AUTHOR

Elena Bolshakova <helena@cpan.org>