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 5E807BBBB for ; Fri, 31 Mar 2006 14:40:00 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id k2VCdx0n024136 for ; Fri, 31 Mar 2006 14:40:00 +0200 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id OAA23435 for ; Fri, 31 Mar 2006 14:39:59 +0200 (MET DST) Received: from smtp16.wanadoo.fr (smtp16.wanadoo.fr [193.252.23.89]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id k2VCdxBr032708 for ; Fri, 31 Mar 2006 14:39:59 +0200 Received: from me-wanadoo.net (localhost [127.0.0.1]) by mwinf1604.wanadoo.fr (SMTP Server) with ESMTP id 1C5A67000086 for ; Fri, 31 Mar 2006 14:39:59 +0200 (CEST) Received: from wwinf1603 (wwinf1603 [172.22.147.30]) by mwinf1604.wanadoo.fr (SMTP Server) with ESMTP id 115BB7000081 for ; Fri, 31 Mar 2006 14:39:59 +0200 (CEST) X-ME-UUID: 20060331123959711.115BB7000081@mwinf1604.wanadoo.fr Message-ID: <23781441.1143808799061.JavaMail.www@wwinf1603> From: yoann padioleau Reply-To: padator@wanadoo.fr To: caml-list@inria.fr Subject: Re: [Caml-list] efficient binary relations? Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Originating-IP: [193.54.76.165] X-Wum-Nature: EMAIL-NATURE X-WUM-FROM: |~| X-WUM-TO: |~| X-WUM-REPLYTO: |~| Date: Fri, 31 Mar 2006 14:39:59 +0200 (CEST) X-Miltered: at nez-perce with ID 442D231F.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 442D231F.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; binary:01 binary:01 ocaml:01 bitvectors:01 high-level:01 computed:01 intersection:01 bitvectors:01 integers:01 integers:01 intersection:01 functionnal:01 re-order:01 caml-list:01 imperative: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 > I am looking for an efficient representation of binary relations in > OCaml. I have used bitvectors in the past but would like to use a more > high-level and less imperative data structure. > > The most important operation is the following. For a binary relation R > over \X x \Y compute for a set X the set X' = { y | (x,y) in R for all > x in X}. In other words, X' is the set of y that are common to all x in > X. Likewise, Y' must be computed. This operation requires to compute > the intersection of sets and was the main reason I chose bitvectors. If > you know about a suitable data structure I would glad to hear about it. If you can represent the y by integers, and that the binary relation have good property, such as the set of y related to a x (the extension of x in concept analysis ?) often follows each other, then you can represent sets by list of intervals. For instance the set of integers from 200 to 400 and 500 to 550 by [(200,400);(500;550)]. Computing intersection with such sets can be quite fast. You can also represent such sets by tree of intervals (there is a pearl on this in journal of functionnal programming if I remember). Then, when you want to compute the intersection of an important number of set, maybe you have to re-order the intersection operations, for instance starting with the sets which have the less elements. I think that in constraint programming they have such problems.