2007/6/10, Nagy Gabor <ngaba@petra.hos.u-szeged.hu>:
Hi! Some comments: 1. This is a simple topological sort algorithm, based on the "depth first search" algorithm, for more info plz visit: http://en.wikipedia.org/wiki/Topological_sorting (An alternative algorithm for...) Usually this is done by a recursive way but I not prefer that, because this version is more expressive to me (however this looks more difficult, because we need some extra variables to precisely store the current state). 2. As I noted in the patch (TODO), the most CPU-cost part of the algorithm is to build the graph, so this should somehow combined with depcheck (because that function does this too...) So, here is the patch:
Thanks for submitting this again, I love it :) I really didn't like the sqrt(n) speed hack which produced totally wrong result. btw look at this : http://bugs.archlinux.org/task/7229 Anyway, also applied it to my tree : http://chantry.homelinux.org/~xav/git/gitweb.cgi?p=pacman.git;a=commit;h=9bf... Thanks