*To*: debian-devel@lists.debian.org*Cc*: Ross Boylan <RossBoylan@stanfordalumni.org>, Björn Stenberg <bjorn@haxx.se>*Subject*: Re: Which packages will hold up the release?*From*: Ross Boylan <RossBoylan@stanfordalumni.org>*Date*: Thu, 9 Oct 2003 23:37:22 -0700*Message-id*: <[🔎] 20031010063722.GF2341@wheat.boylan.org>*In-reply-to*: <[🔎] 20031009030436.GC1000@quetzlcoatl.dodds.net>

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.

**Follow-Ups**:**Re: Which packages will hold up the release?***From:*Tom <tb.31009.nospam@comcast.net>

**References**:**Re: Which packages will hold up the release?***From:*Steve Langasek <vorlon@netexpress.net>

- Prev by Date:
**Re: mozilla-firebird in testing** - Next by Date:
**Re: testing packages at build** - Previous by thread:
**Re: Which packages will hold up the release?** - Next by thread:
**Re: Which packages will hold up the release?** - Index(es):