Strong dependencies and strong dominators

Historical dominance graph: KDE cluster in Debian Sarge
KDE cluster in Debian Sarge

FOSS distributions are composed of dozens of thousands packages, and hundreds of thousands of dependencies. Visualizing such huge graphs in a way that allows to identify some interesting features is a real challenge.

In Mancoosi, we propose to extract from the huge graph a much smaller one, built out of packages which are in a relationship called strong dominance (reminiscent of the notion of dominance used by compilers when analyzing control flow graphs): in practice, the resulting graph of strong dominators is much smaller and allows to visualize the architecture of the components of a distribution.

The technical definitions, as well as a detailed discussion of these notions, can be found in a technical report titled Strong Dependencies between Software Components.

This page provides pointers to the daily analysis of mainstream FOSS distributions provided by Mancoosi as a service to the FOSS community.

Debian GNU/Linux

We computed strong dominance graphs for all historical stable releases of Debian (architecture i386, section main). They are available below, in PDF format, sorted by reverse chronological order of release.


Strong dominators