[pacman-dev] [patch] patch IV rewritten for git

[Xavier]

2007/6/10, Nagy Gabor <ngaba at 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=9bfc5c23f40153ebbab4d33b5d1381ba11726a06

Thanks