<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Apr 15, 2015 at 11:32 AM, Trishank Karthik Kuppusamy <span dir="ltr"><<a href="mailto:trishank@nyu.edu" target="_blank">trishank@nyu.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><span class="">On 15 April 2015 at 11:15, David Cournapeau <span dir="ltr"><<a href="mailto:cournape@gmail.com" target="_blank">cournape@gmail.com</a>></span> wrote:<br></span><div class="gmail_extra"><div class="gmail_quote"><span class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><div class="gmail_quote">This is indeed the case. If you want to solve dependencies in a way that works well, you want an index that describes all your available package versions.<div><br></div><div>While solving dependencies is indeed NP complete, they can be fairly fast in practice because of various specificities : each rule is generally only a few variables, and the rules have a specific form allowing for more efficient rule representation (e.g. "at most one of variable", etc...). In my experience, it is not more difficult than using graph-based algorithms, and</div><div><br></div><div>FWIW, at Enthought, we are working on a pure python SAT solver for resolving dependencies, to solve some of those issues. I am actually hacking on it right at PyCon, we hope to have a first working version end of Q2, at which point it will be OSS, and reintegrated in my older project depsolver (<a href="https://github.com/enthought/depsolver" target="_blank">https://github.com/enthought/depsolver</a>).</div><span><font color="#888888"><div><br></div><div></div></font></span></div></div></div></blockquote><div><br></div></span><div>Awesome! Then pip could use that in the near future :)<br></div></div></div></div></blockquote><div><br></div><div>That's the goal. For various reasons, it ended up easier to develop the solver within our own package manager enstaller, but once done, extracting it as a separate library should not be too hard. It is for example designed to support various versioning schemes (for legacy reasons we can't use PEP440 just yet).</div><div><br></div><div>Regarding speed, initial experiments showed that even for relatively deep graphs, the running time is taken outside the SAT solver (e.g. to generate the rules, you need to parse the version of every package you want to consider, and parsing 1000s of PEP440 versions is slow :) ).</div><div><br></div><div>David</div></div><br></div></div>