History of largest strongly connected component in Debian bootstrap

I'll take a shot. If I understand it correctly, basically components have dependencies. For example, A depends on B and B depends on C, etc. If you have A depends on B... and somehow along the path you have a cycle, eg. E depends on A, you have a problem because in order to install A, you need to install B, C,... E. But in order to install E you need to install A first. So you have to break the dependency cycle.

On top of what somerandomone said (which is already correct) imagine you have source packages A, B, C and D which depend on each other through the binary packages they build and the binary packages they build depend on like this: A->B->C->D->A

This would then form a simple cycle where a dependency has to be broken to make it acyclic. A strongly connected component now is a graph where every vertex is in the cycle with every other vertex in the graph.

So for example if we add a package E to the above simple cycle where B depends on E and E depends on D, then we would not have a simple cycle anymore. Now imagine scaling this up to a couple of hundred vertices and you see how this quickly becomes a hideous mess.

I once tried to visualize such a strongly connected component and it looks like this:

http://blog.mister-muffin.de/images/hideous_mess.png

you might be interested in following this thread: http://lists.debian.org/87r3qurhhm.fsf@deep-thought.43-1.org

here is another thing:

Instead of using debootstrap to create your chroot environment, try using multistrap. Multistrap uses apt to do package selection and not the "stupid" dependency resolver that debootstrap uses. Thus, you have much more freedom in selecting which packages you want. For example with multistrap it is possible to create a chroot that only contains Essential:yes packages (that means no apt).

This graph does not speak to that specifically at all.

I don't know how big the strongly connected component has to become so that you might call bootstrapping Debian "nearly impossible" but last year there were just two new Debian ports: arm64 and ppc64el. So apparently it is still within human reach to build Debian as a whole from scratch. I think what the graph shows is just that it's getting harder and that we need automateable tools to do the whole thing for us. This is what the new "build profile" syntax is for that was introduced with Jessie.

The utility is quantifying a "gut feeling". More can probably be found in this thread: https://lists.debian.org/debian-qa/2014/07/msg00234.html

The purpose is, to have a somehow quantifiable measure how hard it becomes to bootstrap Debian. Because the larger the central strongly connected component, the more software is involved in the bootstrap process and has to either be cross compiled or compiled with fewer build dependencies to break cycles.

Ultimately I thought this graph to support the introduction of build profiles into Debian (now so happened with the Jessie release) as well as to promote that a tool like "botch" (you can `apt-get install` it) is necessary to automatically make this graph acyclic for you instead of doing this through year long manual work.

The larger that component is, the more work is needed to make it acyclic (to derive a linear build order). Ideally this "work" is done automatically but for that, more meta data has to be added. In Debian, source package dependencies can be annotated with "build profiles" to mark dependencies which are optional and can thus be used to break cycles. But more source packages need this information. The graph is supposed to be a visualization to convince people that it becomes increasingly hard to break cycles manually and that an automated way (using build profiles) is needed.