in reply to
Algorithm For Uninstalling Dependencies
That's a topological sorting of a DAG!
Graph.pm has a topological sort routine, and I'm sure you could find many other Perl implementations or even quickly roll your own (it's easy: if you can implement depthfirst search, then you are about 2 lines of code away from a topological sort algorithm).
How timely, since just yesterday I discovered the tsort unix utility. Give it a list of edges, one on each line, in the form "A B", meaning that A must come before B. It will output a topological sorting.
Re^2: Algorithm For Uninstalling Dependencies by Limbic~Region (Chancellor) on Nov 20, 2009 at 17:46 UTC 
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:
 [reply] [d/l] 

Oh, I think I see what you mean now..
Here is something that I think does what you want:
You do a DFS from the target, following edges backwards. The resulting list will tell you all of the items that depend on the target. These are all the items that we know must be removed if the target is to be removed (according to your rules). The fact that we used DFS here doesn't really matter, we just need a list of all vertices that can reach the target.
Now we have a list of items that must be removed. Before removing any item, we must first remove all of its dependents. This where the topological sort happens.
Doing a DFS (following edges forward) from some item X results in a topological sorting of the items that must be removed if you want to remove X. So we can just do a DFS from each of vertices in that list. We reuse the %seen array so that these multiple DFS calls don't repeat (similar to how you would do topological sort on an entire graph, by starting new DFSes until everything has been seen).
On a side note, it seems slightly odd that you would remove all of FOO and all of its dependencies as a result of removing BLAH. What if BAR or XYZ are required elsewhere? Are there more conditions than are captured in this small example?
 [reply] [d/l] 

blokhead,
After an hour an a half, I convinced my coworker he was full of contradictory statements and what he said he needed wasn't at all the correct definition of the problem. After figuring out what he really wanted to do, it turned out to be a simple matter of constructing a "depends on me" tree and then using the topological sort.
 [reply] [d/l] 

 [reply] 

