#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