title: Algorithm for dependency resolution
body: <p>I'm in the process of writing a package manager, and for that I want the dependency resolution to be as powerful as possible.</p>
  
  <p>Each package has a list of versions, and each version contains the following information:</p>
  
  <ul>
  <li>A comparable ID</li>
  <li><strong>Dependencies</strong> (a list of packages and for each package a set of acceptable versions)</li>
  <li><strong>Conflicts</strong> (a list of packages and for each package a set of versions that cause issues together with this version)</li>
  <li><strong>Provides</strong> (a list of packages and for each package a set of versions that this package also provides/contains)</li>
  </ul>
  
  <p>For the current state I have a list of packages and their current versions.</p>
  
  <p>I now want to, given the list of available packages and the current state, be able to get a version for each package in a list of packages, taking the given constraints into account (dependencies, conflicting packages, packages provided by other packages) and get back a list of versions for each of these packages. Circular dependencies are possible.</p>
  
  <p>If no valid state can be reached, the versions of the existing packages may be changed, though this should only be done if necessary. Should it not be possible to reach a valid state as much information to the reason should be available (to tell the user "it could work if you remove X" etc.). </p>
  
  <p>If possible it should also be possible to "lock" packages to a specific version, in which case the version of the package may NOT be changed.</p>
  
  <p>What I'm trying to accomplish is very similar to what existing package managers already do, with the difference that not necessarily the latest version of a package needs to be used (an assumption which most package managers seem to do).</p>
  
  <p>The only idea I have so far is building a structure of all possible states, for all possible versions of the packages in question, and then removing invalid states. I really hope this is not the only solution, since it feels very "brute force"-ish. Staying under a few seconds for ~500 available packages with ~100 versions each, and ~150 installed packages would be a good goal (though the faster the better).</p>
  
  <p>I don't believe this is a language-specific question, but to better illustrate it, here is a bit of pseudecode:</p>
  
  <pre><code>struct Version
      integer id
      list&lt;Package, set&lt;integer&gt;&gt; dependencies
      list&lt;Package, set&lt;integer&gt;&gt; conflicts
      list&lt;Package, set&lt;integer&gt;&gt; provides
  
  struct Package
      string id
      list&lt;Version&gt; versions
  
  struct State
      map&lt;Package, Version&gt; packages
      map&lt;Package, boolean&gt; isVersionLocked
  
  State resolve(State initialState, list&lt;Package&gt; availablePackages, list&lt;Package&gt; newPackages)
  {
      // do stuff here
  }
  </code></pre>
  
  <p>(if you should have actual code or know about an existing implementation of something that does this (in any language, C++ preferred) feel free to mention it anyway)</p>