[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: Which packages will hold up the release?

There are some mathematical tools that might be useful in working with
some of these issues (I know them from models of social networks).

One can represent relations between packages as a matrix D.  The rows
and columns refer to packages, and the cell is 1 if a relation exists,
otherwise 0.  For example, D[i, j] is 1 if package i depends on
package j.

One can define a funny form of matrix multiplication, in which the
result can only be 0 or 1.
 Let D2 = D^2 = D*D 
Ordinary matrix multiplication says
D2[i, j] = sum_k D[i, k] * D[k, j]  (using pseudo-TeX notation)
The modified form is
D2[i, j] = or_k D[i, k] * D[k, j]  (in other words: 1 if any of the
combinations is 1)
equivalently this = max(1, sum_k D[i, k]* D[k, j])
So D captures all direct dependencies, and D^2 has all direct
dependencies and indirect dependencies of length 2 (usually D2
includes all of D, i.e., all direct relations, but if D[i, i] is not 1
that may not be so). 
D^infinity will have a stable limit, and expresses *all* direct and
indirect dependencies.

Since Björn already has a list of all indirect dependencies, I'm not
sure this contributes anything useful.  However, one can map a variety
of relations using this approach (depends on, conflicts with, is a
substitute for are some obvious ones), and then there are various tools to
look at all the relations together (they form an algebra), and there
are tools for separating individual packages into similar clusters
based on their patterns of relations.

It's also easy to make statements using this notation.  For example,
if D represents depends on (directly or indirectly) and C conflicts
with (direct or indirect), then we can say that if
D or C <> 0 (or is element by element, 0 is a 0 matrix)
a logically impossible set of relations has been specified (I think;
even if it's substantively wrong I hope you get the flavor).

I still have only a partial handle on all the substantive issues
involved in releasing packages, but throw this out on the chance it
might be useful.

More generally, it may be that taking the perspective of the overall
pattern of relations provides some value beyond looking at things
strictly from the perspective of a single package.

P.S. I'm not a Debian developer or a subscriber to this list, but
followed it on the web.  I've tried to fake my headers so it appears
properly in the thread.  I'm curious if there's a good way to do that.

Reply to: