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";
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.
|