Suppose you have a dependency graph of "packages" registered in the ecosystem of a given programming language. We can model each package as a tuple
(name, version) where
name is the package name (like
version is a semantic version number (like
Each package has a set of dependencies, which may include constraints. Perhaps
Plot-1.2.3 depends on
JSON with a constraint
>= 1.0 && < 3.0. Thus, there could be a number of
JSON-X.Y.Z versions that are compatible with
The goal of this problem is to construct a "minimal" set of nodes to form a useful package snapshot.
Let's define a "useful" package snapshot as following:
- It contains the latest version of every package.
- Every package in the snapshot is "resolvable" (EDIT: as long as it's resolvable in the original ecosystem), i.e. the snapshot must include a compatible version of every necessary dependency of that package.
- Every two packages in the snapshot are "pairwise resolvable," meaning that if there is a working set of dependencies to install them simultaneously in the original ecosystem, then there is also such a working set in the snapshot. (EDIT: note that when you're installing a set of packages, you only get to choose one version of a particular dependency package. Thus, if packages P and Q both depend on dependency D, pairwise resolvability means that there must be one single version of D compatible with both P and Q in the snapshot, as long as such is true in the full ecosystem.)
By this definition the full ecosystem is a useful snapshot. But the key part of this goal is "minimal." I want to find the smallest useful package snapshot that satisfies the rules above. I feel like there must be some prior art or theory that can help here. Graph coloring? Satisfiability? Please help :)
In case it's of interest, this is a real problem -- I want to package such a snapshot in the Nix package manager, so that a user can express something like "Please give me an environment with packages A, B, and C" and get a working environment with the latest version of those packages, as long as such is possible. There are about 80,000 nodes in the real graph. The solution doesn't need to be perfectly optimal but the smaller I can get it, the better.