Limbic~Region has asked for the wisdom of the Perl Monks concerning the following question:
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:
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:
- All dependencies must be removed first
- Any item that depends on a removed item, must be removed after that item is removed
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
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
So to remove 'BLAH', the following items must be removed:
In what order? I believe any of the following are viable.BLAH XYZ LA BAR FOO ASDF OOOOO
LA -> XYZ -> BLAH -> BAR -> OOOOO -> ASDF -> FOO LA -> XYZ -> BLAH -> OOOOO -> ASDF -> BAR -> FOO LA -> XYZ -> BLAH -> OOOOO -> BAR -> ASDF -> FOO
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
|
---|
Back to
Seekers of Perl Wisdom