dependencies with alternatives
 skaller
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20060701 (04:25) 
From:  skaller <skaller@u...> 
Subject:  dependencies with alternatives 
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 (allof, oneof) is required. Any hints on this?  John Skaller <skaller at users dot sf dot net> Felix, successor to C++: http://felix.sf.net