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.
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";
Cheers - L~R
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^3: Algorithm For Uninstalling Dependencies
by blokhead (Monsignor) on Nov 20, 2009 at 19:45 UTC | |
by Limbic~Region (Chancellor) on Nov 20, 2009 at 23:26 UTC | |
by Limbic~Region (Chancellor) on Nov 20, 2009 at 20:54 UTC |
In Section
Seekers of Perl Wisdom