# This is essentially a copy of an old writeup of mine on Everything2.
#
# Here's an implementation of a [topological sort] in Perl.
# It's reasonably terse, and even has some comments!
#
# Pass it as input a list of array [reference]s; these
# specify that that index into the list must come before all
# elements of its array. Output is a topologically sorted
# list of indices, or undef if input contains a cycle. Note
# that you <em>must</em> pass an array ref for every input
# elements (if necessary, by adding an empty list
# reference)!
#
# For instance, tsort ([1,2,3], [3], [3], []) returns
# (0,2,1,3).

sub tsort {
  my @out = @_;
  my @ret;

  # Compute initial in degrees
  my @ind;
  for my $l (@out) {
    ++$ind[$_] for (@$l)
  }

  # Work queue
  my @q;
  @q = grep { ! $ind[$_] } 0..$#out;

  # Loop
  while (@q) {
    my $el = pop @q;
    $ret[@ret] = $el;
    for (@{$out[$el]}) {
      push @q, $_ if (! --$ind[$_]);
    }
  }

  @ret == @out ? @ret : undef;
}