Re: [Caml-list] efficient binary relations?

[yoann padioleau <padator@wanadoo.fr>]

 
> 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.