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;
}