dependencies with alternatives

dependencies with alternatives

[skaller]

More a math than ocaml question but .. we know with a dependency graph
we can find the transitive closure of a set of nodes. 

This set represents the conjunction of initial requirements:
"this package requires package A, package B, AND package C".

What happens if a new constructor for alternatives is introduced?
Assume first inclusive or (introducing exclusive or seems equivalent
to introducing negation, i.e. conflicts).

As far as I can see this problem doesn't have a unique solution,
we're looking for a minimal set of nodes such that at least
one alternative of each (reachable) alternation is reachable 
from the root. It's looking remarkably like an Earley style 
algorithm is actually needed to compute such a minimal set.

If conflicts are introduced, it seems even harder.

The model for this thing is no longer a graph, rather at least
a graph labelled with the constructor (all-of, one-of) is required.

Any hints on this?

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net