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

Xavier shiningxc at gmail.com
Sun Jun 10 18:03:37 EDT 2007

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 :

Anyway, also applied it to my tree :


More information about the pacman-dev mailing list