Re: Sorting by association, a tail of dependency resolving gone nowhere

There doesn't seem to be any sorting involved in your example.

my %depends_on = (
   1 => undef,
   2 => 4,
   3 => 5,
   4 => 3,
   5 => 1,
);

my %dependant_of;
@dependant_of{values(%depends_on)} = keys(%depends_on);

my @sorted;

foreach (grep { !defined($depends_on{$_}) } keys(%depends_on)) {
   my $next = $_;

   while (defined $next) {
      push(@sorted, $next);
      $next = $dependant_of{$next};
   }
}

print(join(', ', @sorted), "\n");  # 1, 5, 3, 4, 2
[download]

Update: Rewrite. Original solution was wrong.

Update: Fixed problem mentioned by Roy Johnson.

Comment on Re: Sorting by association, a tail of dependency resolving gone nowhere Download Code

Replies are listed 'Best First'.
Re^2: Sorting by association, a tail of dependency resolving gone nowhere by Roy Johnson (Monsignor) on Dec 12, 2005 at 17:56 UTC
That solution depends on starting with the right `$next`. I don't think that's a reasonable precondition. Caution: Contents may have been coded under pressure.	[reply] [d/l]