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 references; 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 must 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[$_]);
    }
  }

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

Log in or register to write something here or to contact authors.