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
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^2: Algorithm For Uninstalling Dependencies
by Limbic~Region (Chancellor) on Nov 20, 2009 at 17:46 UTC | |
by blokhead (Monsignor) on Nov 20, 2009 at 19:45 UTC | |
by Limbic~Region (Chancellor) on Nov 20, 2009 at 23:26 UTC | |
by Limbic~Region (Chancellor) on Nov 20, 2009 at 20:54 UTC |
In Section
Seekers of Perl Wisdom