[pacman-dev] _alpm_sortbydeps is slow and buggy

[Aaron Griffin]

On 4/16/07, Nagy Gabor <ngaba at petra.hos.u-szeged.hu> wrote:
> > how Aaron uses to say? "patches are welcome" :)
> OK. I may do it, but
> 1. I think it's more difficult to understand an other
> person's thought than "doing it yourself". And I hope that developers
> check my patches before committing because I don't trust on myself ;-)
> 2. First I collect opinions because I don't want to do needless work
> (again :-). I think that almost whole deps.c should be rewritten (and
> most of the function should be merged: _alpm_checkdeps,
> _alpm_resolvedeps and _alpm_sortbydeps for example)

Yes, sort-by-deps is slow.  The easiest fix is to convert it from a
set of nested loops to a  topological sort algorithm.  This is
mentioned in a few places.

As it stands, it works well enough (that's the reason for the sqrt -
VMiklos pointed this out a while back when I actually wanted to remove
it for n/2 - it's "good enough").

Tolopogical sort is a simple algorithm, but the problem is that it's
hard to convert a list with chained lists as the dependencies into a
graph structure.  Feel free to try any option, but, for correctness's
sake, I'd rather convert the dep list itself to a list of packages
(all from the package cache, loaded on demand), which makes the topo
sort much easier.