|Welcome to the Monastery|
Algorithm For Uninstalling Dependenciesby Limbic~Region (Chancellor)
|on Nov 20, 2009 at 14:57 UTC||Need Help??|
Limbic~Region has asked for the wisdom of the Perl Monks concerning the following question:
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.
Let's say we want to remove BLAH. The following is my own mental representation of the process.
So to remove 'BLAH', the following items must be removed:
In what order? I believe any of the following are viable.
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