I got the O(N^2) from the edge computation. If the package hierarchy could be stored as a forest of trees or DAGs then the topo sort would be O(N). A straight tree/DAG implementation would be an interesting project if I had the time. k On Tue, 2007-06-12 at 19:53 +0200, Xavier wrote:
I also find recursive algorithm more natural for recursive structure. Maybe Nagy is the only one who doesn't :) But as far as I can tell, this is a correct implementation of the topo sort, so O(n+e) for the sort part. Did you also include the computation of the edges, which is O(n^2), or is there something else that I overlooked ? This was already observed by Nagy here : http://archlinux.org/pipermail/pacman-dev/2007-April/008135.html
Though when I first looked at this part, I find it odd, because O(n^2) shouldn't be needed there either, it's just a matter of : for t in targets do for d in deps(t) do add(d, t.children) But the problem is we don't have constant time access to the vertices.
_______________________________________________ pacman-dev mailing list pacman-dev@archlinux.org http://archlinux.org/mailman/listinfo/pacman-dev