http://qs321.pair.com?node_id=808458


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 depth-first 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.

blokhead