Just another Perl shrine | |
PerlMonks |
Re^3: Algorithm For Uninstalling Dependenciesby blokhead (Monsignor) |
on Nov 20, 2009 at 19:45 UTC ( [id://808515]=note: print w/replies, xml ) | Need Help?? |
Oh, I think I see what you mean now..
Here is something that I think does what you want:
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 re-use 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? blokhead
In Section
Seekers of Perl Wisdom
|
|