Re: [Camllist] efficient binary relations?
 yoann padioleau
[
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:  20060331 (12:40) 
From:  yoann padioleau <padator@w...> 
Subject:  Re: [Camllist] efficient binary relations? 
> 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 > highlevel 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 reorder the intersection operations, for instance starting with the sets which have the less elements. I think that in constraint programming they have such problems.