On Wed, 28 Dec 2005 16:36:28 +0100 Paul de Vrieze <[EMAIL PROTECTED]> wrote: | The problem is caused by packages being dependencies from multiple | sides. The trick is that if a package is pulled in by one side it | should be taken for granted by the other side if it satisfies it's | dependencies. Detecting that can be done by hashtables which have | O(log n) complexity on the number of packages in the tree. In any | case not that expensive.
Lookups against the tree can be done in O(1) time. That isn't the issue. The issue is that as soon as you introduce backtracking, you go to O(n!) with a general "try stuff in order" algorithm like the one you proposed, which for 1000 packages is utterly unusable. -- Ciaran McCreesh : Gentoo Developer (I can kill you with my brain) Mail : ciaranm at gentoo.org Web : http://dev.gentoo.org/~ciaranm
signature.asc
Description: PGP signature
