dependency check algorithms (was Re: "task" and beyond)
On Wed, 12 Feb 2003 14:58:32 +0100, Lionel Elie Mamane wrote:
> On Wed, Feb 05, 2003 at 11:12:41PM +0900, Oohara Yuuma wrote:
>> On Wed, 5 Feb 2003 03:29:22 -0800,
>> Osamu Aoki <osamu@debian.org> wrote:
>>> (dependency check is N^2 problem and started to stress system
>>> badly.)
>> If someone implements an algorithm which splits a given set of
>> packages into 2 sets A and B so that no package in A depends on any
>> package in B and no package in B depends on any package in A,
>> dependency check can be a NlogN problem.
> This looks impossible to me: I conjecture that by walking the
> dependency graph from any package, you'll end up in libc; the
> (non-oriented) dependency graph is connected.
Certain packages are not depended on due to them being part of the
standard required base installation (base?). It's part of policy. If there
were any other such package, then it should very likely be in base and
thus would not have a dependency on it set.
Actually, when taking an algorithms related course I was taught an
algorithm that may be useful. I'm going to have to look it up, but the way
that it worked was that it built up a tree into more optimum form every
time it was searched. Back then I assumed that if the algorithm would have
been useful for Debian, that someone would have pit it in. Now, I'm not so
sure. If anyone recalls such an algorithm before I find it, please comment
as to it's usefulness in package dependency checking and alike.
Drew Daniels
Reply to: