[Hackage] #500: develop a tool to find the maximal consistent set of hackage packages

[Hackage]

#500: develop a tool to find the maximal consistent set of hackage packages
----------------------------+-----------------------------------------------
  Reporter:  duncan         |        Owner:                 
      Type:  enhancement    |       Status:  new            
  Priority:  normal         |    Milestone:                 
 Component:  miscellaneous  |      Version:                 
  Severity:  normal         |   Resolution:                 
  Keywords:                 |   Difficulty:  project(> week)
Ghcversion:                 |     Platform:                 
----------------------------+-----------------------------------------------
Comment (by michiexile):

 If we assume that we can have "installable with..." as a primitive
 operation (and package THAT instance of NP in there), then it should be
 easy to build a graph with vertices the packages and edges given by an
 edge package1 -- package2 precisely when there is some set of dependency
 fulfillment that is fulfilled by all of them.

 We can label each edge with the dependency intervals under which it
 exists.

 This graph can be extended to a simplicial complex by inserting a simplex
 (you can view it as a distinguished clique) whenever all the edges of it
 have a nontrivial intersection of their labels.

 A dependency list, here, will end up being a sequence of intervals - one
 for each package in the dependency list. Simultaneous dependencies are
 given as intersections of these intervals; with an absent interval being
 replaced, when needed, by a full (i.e. [-∞,∞]) interval.

 As a worked example, consider packages p1 through p5, and with the
 following dependencies:

 p1: none[[BR]]
 p2: 1 in [1.0,1.5][[BR]]
 p3: 1 in [1.0,1.0], 2 in [1.0,2.0][[BR]]
 p4: 1 in [1.5,1.5][[BR]]
 p5: 1 in [1.5,1.5], 4 in [1.0,2.0][[BR]]

 We find all edges between these packages:
 12: 1 in [1.0,1.5][[BR]]
 13: 1 in [1.0,1.0], 2 in [1.0,2.0][[BR]]
 14: 1 in [1.5,1.5][[BR]]
 15: 1 in [1.5,1.5], 4 in [1.0,2.0][[BR]]
 23: 1 in [1.0,1.0], 2 in [1.0,2.0][[BR]]
 24: 1 in [1.5,1.5][[BR]]
 25: 1 in [1.5,1.5], 4 in [1.0,2.0][[BR]]
 34: conflicting dependencies for 1 - edge absent[[BR]]
 35: conflicting dependencies for 1 - edge absent[[BR]]
 45: 1 in [1.5,1.5], 4 in [1.0,2.0][[BR]]

 Now, we can look at 3-cliques in the resulting graph:
 123: 1 in [1.0,1.0], 2 in [1.0,2.0][[BR]]
 124: 1 in [1.5,1.5][[BR]]
 125: 1 in [1.5,1.5], 4 in [1.0,2.0][[BR]]
 145: 1 in [1.5,1.5], 4 in [1.0,2.0][[BR]]
 245: 1 in [1.5,1.5], 4 in [1.0,2.0][[BR]]

 And 4-cliques - all of which should avoid any already disqualified edges:
 1245: 1 in [1.5,1.5], 4 in [1.0,2.0]

 and that's it for this example.

 Now, there is a polynomial time clique-finding graph; and intersections of
 intervals is reasonably easy to do as well - so this looks like a possible
 way to structure something like this.

-- 
Ticket URL: <http://hackage.haskell.org/trac/hackage/ticket/500#comment:1>
Hackage <http://haskell.org/cabal/>
Hackage: Cabal and related projects