Re^2: Algorithm For Uninstalling Dependencies

in reply to Re: Algorithm For Uninstalling Dependencies
in thread Algorithm For Uninstalling Dependencies

blokhead,
The proof of concept you offered on your scratch of a TS is producing the same result as Algorithm::Dependency::Ordered (the wrong thing). I am not saying a TS isn't what I need, just that I am not seeing how to convince it to give me the list I want.

In my example above, your code gave me LA -> XYZ -> BLAH which only satisfies rule 1 above. To satisfy rule 2, FOO and 3 other items must also be removed. In other words, it only appears to go down (DFS) not back up. I am honestly not trying to be dense here. The code I am using is below:

#!/usr/bin/perl
use strict;
use warnings;

my %tree = (
    FOO   => [qw/BAR BLAH ASDF/],
    BAR   => [qw/LA/],
    BLAH  => [qw/XYZ/],
    ASDF  => [qw/OOOOO/],
    LA    => [],
    XYZ   => [qw/LA/],
    OOOOO => []
);
{
  my %seen;
  my %onstack;
  my @list;

  sub how_to_uninstall {
      my $target = shift;
      (@list, %seen, %onstack) = ();

      _traverse($target);

      return @list;
  } 

  sub _traverse {
      my $x = shift;
      $seen{$x} = $onstack{$x} = 1;
      for my $y (@{$tree{$x}}) {
          die "cyclic!" if $onstack{$y};    # back edge
          _traverse($y) unless $seen{$y};
      }
      push @list, $x;
      $onstack{$x} = 0;
  }
}
my @order = how_to_uninstall('BLAH');
print "@order\n";
[download]

Cheers - L~R

In Section Seekers of Perl Wisdom