From: Massimiliano Mirra <list@...>
Date: 2002-09-17T00:52:49+09:00
Subject: Dependency "trees" - suggestions?

I'm struggling with building dependency "trees" for rpkg.  What
happens (or should happen eventually) is that, given a record like:

Package: foo
Depends: bar (= 1.3), booz (> 2.0)

...installing foo will get the foo package, the matching bar package,
the matching booz package, the packages bar depends on, the packages
booz depends on...  you get the picture (if you've ever used Debian,
you also get the movie).

This is not really a tree because many packages can depend on one, so
a node can have multiple parents.  But it *is* directed and *must* be
acyclic.

And there's the rub.  I can't just trust the database that it won't
generate cycles, so if it happens I must catch that.

In other words, whenever a node is added, it must be checked that it
hasn't produced a cycle.

The million dollar question: how?

Right now, each time a node is added, an array containing all the
possible paths is updated.  If adding the node causes a cycle in one
of the paths, an exception is raised.

It works, but it's fragile, and I'm pretty sure it wouldn't scale up
very good (to put it mildly).

Suggestions?


Massimiliano