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 reply to Re^2: Algorithm For Uninstalling Dependencies by Limbic~Region
in thread Algorithm For Uninstalling Dependencies by Limbic~Region

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.