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

Hackage trac at galois.com
Sat Feb 14 19:28:32 EST 2009

```#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. [-&infin;,&infin;]) 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.

--