Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Topological Sort in Perl

by ariels (Curate)
on May 30, 2001 at 12:32 UTC ( #84192=perlcraft: print w/ replies, xml ) Need Help??

   1: # This is essentially a copy of an old writeup of mine on Everything2.
   2: #
   3: # Here's an implementation of a [topological sort] in Perl.
   4: # It's reasonably terse, and even has some comments!
   5: #
   6: # Pass it as input a list of array [reference]s; these
   7: # specify that that index into the list must come before all
   8: # elements of its array. Output is a topologically sorted
   9: # list of indices, or undef if input contains a cycle. Note
  10: # that you <em>must</em> pass an array ref for every input
  11: # elements (if necessary, by adding an empty list
  12: # reference)!
  13: #
  14: # For instance, tsort ([1,2,3], [3], [3], []) returns
  15: # (0,2,1,3).
  16: 
  17: sub tsort {
  18:   my @out = @_;
  19:   my @ret;
  20: 
  21:   # Compute initial in degrees
  22:   my @ind;
  23:   for my $l (@out) {
  24:     ++$ind[$_] for (@$l)
  25:   }
  26: 
  27:   # Work queue
  28:   my @q;
  29:   @q = grep { ! $ind[$_] } 0..$#out;
  30: 
  31:   # Loop
  32:   while (@q) {
  33:     my $el = pop @q;
  34:     $ret[@ret] = $el;
  35:     for (@{$out[$el]}) {
  36:       push @q, $_ if (! --$ind[$_]);
  37:     }
  38:   }
  39: 
  40:   @ret == @out ? @ret : undef;
  41: }
  42: 

Comment on Topological Sort in Perl
Download Code
Re: Topological Sort in Perl
by larsen (Parson) on May 30, 2001 at 12:40 UTC

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlcraft [id://84192]
Approved by root
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (10)
As of 2015-03-03 07:29 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    When putting a smiley right before a closing parenthesis, do you:









    Results (65 votes), past polls