3 ms·

I didn't understand why it would be NP-complete, dependencies represent an acyclic graph. However, this is the killer: "Two different versions of a package ca

I didn't understand why it would be NP-complete, dependencies represent an acyclic graph. However, this is the killer: "Two different versions of a package cannot be installed simultaneously." Get rid of that, and your problems disappear. Which is why my linux server has: 1 gcc-4.8-base:amd64 2 gcc-4.9-base:amd64 3 gcc-5-base:amd64 4 gcc-6-base:amd64

amelius 10y ago
> "Two different versions of a package cannot be installed simultaneously." It seems that the problem then might not even have a solution in all cases. So perhaps we should rethink the problem.
- Dylan16807 10y ago
  It's easy to turn an acyclic graph into a bunch of directories, or to turn a cyclic graph into a bunch of directories and symlinks. If you allow side-by-side versions then the only remaining failure case is a dependency that doesn't exist. Nothing to rethink there.
lazyjones 10y ago
> dependencies represent an acyclic graph AFAICT that's not always true. Several scripting languages allow circular dependencies (Node.js, Perl) and so do some popular package managers (with specific workarounds, but the point is that such dependency constellations exist): https://www.debian.org/doc/debian-policy/ch-relationships.html https://www.debian.org/doc/debian-policy/ch-relationships.ht... Perhaps the problem needs to be examined differently depending on allowed/existing-in-the-wild circular dependencies.
- dozzie 10y ago
  >> dependencies represent an acyclic graph > AFAICT that's not always true. And you are right. apt-get has "upgrade" and "dist-upgrade" commands for a long, long time for a reason (the latter allows to upgrade packages in the presence of dependency cycles and some other cases that would be nasty if left in the middle of upgrade; obviously, no changes that need dist-upgrade land in Debian stable).

3 ms·

I didn't understand why it would be NP-complete, dependencies represent an acyclic graph. However, this is the killer: "Two different versions of a package ca

by jpollock 10y ago

amelius 10y ago
> "Two different versions of a package cannot be installed simultaneously." It seems that the problem then might not even have a solution in all cases. So perhaps we should rethink the problem.
- Dylan16807 10y ago
  It's easy to turn an acyclic graph into a bunch of directories, or to turn a cyclic graph into a bunch of directories and symlinks. If you allow side-by-side versions then the only remaining failure case is a dependency that doesn't exist. Nothing to rethink there.
lazyjones 10y ago
> dependencies represent an acyclic graph AFAICT that's not always true. Several scripting languages allow circular dependencies (Node.js, Perl) and so do some popular package managers (with specific workarounds, but the point is that such dependency constellations exist): https://www.debian.org/doc/debian-policy/ch-relationships.html https://www.debian.org/doc/debian-policy/ch-relationships.ht... Perhaps the problem needs to be examined differently depending on allowed/existing-in-the-wild circular dependencies.
- dozzie 10y ago
  >> dependencies represent an acyclic graph > AFAICT that's not always true. And you are right. apt-get has "upgrade" and "dist-upgrade" commands for a long, long time for a reason (the latter allows to upgrade packages in the presence of dependency cycles and some other cases that would be nasty if left in the middle of upgrade; obviously, no changes that need dist-upgrade land in Debian stable).