All,
A co-worker has posed a problem to me. I haven't had time to work on it myself, but I think it is interesting and thought I would share. Given a dependency tree and a selected item, generate the ordered list of items that must be removed in order to remove the selected item. The rules are easy:

Consider the data below. The left most token is the item and all tokens to the right of it are the dependencies. 

FOO BAR BLAH ASDF
BAR LA
BLAH XYZ
ASDF OOOOO
LA
XYZ LA
OOOOO

[download]

Let's say we want to remove BLAH. The following is my own mental representation of the process. 

Simple path down:
BLAH -> XYZ -> LA

But now we look back up:

LA   <- BAR  <- FOO
XYZ  <- BLAH <- FOO
BLAH <- FOO

And now we look back down again
FOO -> ASDF -> OOOOO

And finally back up
ASDF <- FOO

[download]

So to remove 'BLAH', the following items must be removed: 

BLAH
XYZ
LA
BAR
FOO
ASDF
OOOOO

[download]
In what order? I believe any of the following are viable. 
LA -> XYZ -> BLAH -> BAR -> OOOOO -> ASDF -> FOO
LA -> XYZ -> BLAH -> OOOOO -> ASDF -> BAR -> FOO
LA -> XYZ -> BLAH -> OOOOO -> BAR -> ASDF -> FOO

[download]

I have looked at Algorithm::Dependency::Ordered but it doesn't do the right thing. Now assuming you have a valid tree (doesn't have an item that must be removed both before and after another item), can you come up with an algorithm that solves the problem?

UPDATE: It turns out these are the wrong requirements (though it is an interesting problem). For the actual (more boring) - see Re^4: Algorithm For Uninstalling Dependencies.

Cheers - L~R

In reply to 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.