IIRC, Conda (BSD License) takes a SAT solving (e.g. Sudoku) approach: http://continuum.io/blog/new-advances-in-conda (such as installing "pycosat" (MIT License) when I install conda). Some links to the source: * https://github.com/conda/conda/blob/master/conda/logic.py * https://github.com/conda/conda/blob/master/tests/test_logic.py' * https://github.com/conda/conda/blob/master/conda/resolve.py * https://github.com/conda/conda/blob/master/tests/test_resolve.py ... https://github.com/conda/conda/blob/master/conda/toposort.py On Apr 15, 2015 6:14 AM, "Robin Becker" <robin@reportlab.com> wrote:
After again finding that pip doesn't have a correct dependency resolution solution a colleage and I discussed the nature of the problem. We examined the script capture of our install and it seems as though when presented with
level 0 A A level 1 1.4<= C
level 0 B B level 1 1.6<= C <1.7
pip manages to download version 1.8 of C(Django) using A's requirement, but never even warns us that the B requirement of C was violated. Surely even in the absence of a resolution pip could raise a warning at the end.
Anyhow after some discussion I realize I don't even know the name of the problem that pip should try to solve, is there some tree / graph problem that corresponds? Searching on dependency seems to lead to topological sorts of one kind or another, but here we seem to have nodes with discrete values attached so in the above example we might have (assuming only singleton A & B)
R --> A R --> B
A --> C-1.4 A --> C-1.6 A --> C-1.6.11 A --> C-1.7 A --> C-1.8
B --> C-1.6 B --> C-1.6.11
so looking at C equivalent nodes seems to allow a solution set. Are there any real problem descriptions / solutions to this kind of problem? -- Robin Becker _______________________________________________ Distutils-SIG maillist - Distutils-SIG@python.org https://mail.python.org/mailman/listinfo/distutils-sig