From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 4460DBC20 for ; Sat, 1 Jul 2006 06:25:38 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.13.6/8.13.6) with ESMTP id k614Pdsj013682 for ; Sat, 1 Jul 2006 06:25:39 +0200 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id GAA32612 for ; Sat, 1 Jul 2006 06:25:38 +0200 (MET DST) Received: from ash25e.internode.on.net (ash25e.internode.on.net [203.16.214.182]) by nez-perce.inria.fr (8.13.6/8.13.6) with ESMTP id k614PaoG013658 for ; Sat, 1 Jul 2006 06:25:37 +0200 Received: from rosella (ppp28-237.lns1.syd2.internode.on.net [59.167.28.237] (may be forged)) by ash25e.internode.on.net (8.13.6/8.13.5) with ESMTP id k614PCEg060284 for ; Sat, 1 Jul 2006 13:55:12 +0930 (CST) (envelope-from skaller@users.sourceforge.net) Subject: dependencies with alternatives From: skaller To: caml-list@inria.fr Content-Type: text/plain Date: Sat, 01 Jul 2006 14:25:11 +1000 Message-Id: <1151727911.6032.36.camel@rosella.wigram> Mime-Version: 1.0 X-Mailer: Evolution 2.6.1 Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 44A5F943.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 44A5F940.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; dependencies:01 ocaml:01 nodes:01 negation:01 nodes:01 model:01 sourceforge:01 dependency:01 graph:01 graph:01 constructor:01 constructor:01 conflicts:01 conflicts:01 algorithm:01 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 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 Felix, successor to C++: http://felix.sf.net