User-defined constraints

To define constraints based on set domains one needs to access the properties of a set term like its domain, its cardinality, its possible weight. As the set variable is a metaterm i.e. an abstract data structure, some built-in predicates allow the user to process the set variables and their domains, modify them and write new constraint predicates.

The abstract set data structure

A set domain variable is a metaterm. The conjunto.pl library defines a metaterm attribute

set with [setdom : [Glb,Lub], card: C, weight: W, del_inst: Dinst, del_glb: Dglb, del_lub: Dlub, del_any: Dany]

This attribute stores information regarding the set domain, its cardinality, and weight (null if undefined) and together with four suspension lists. The attribute arguments have the following meaning:

• setdom The representation of the domain itself. As set domains are treated as abstract data types, the users should not access them directly, but only using built-in access and modification predicates presented hereafter.
• card The representation of the set cardinality. The cardinality is initialized as soon as a set domain is attached to a set variable. It is either a finite domain or an integer. It can be accessed and modified in the same way as set domains (using specific built-in predicates).
• weight The representation of the set weight. The weight is intialized to zero if the domain is not a weighted set domain, otherwise it is computed as soon as a weighted set domain is attached to a set variable. it can be accessed and modified in the same way as set domains (using specific built-in predicates).
• del_inst A suspension list that should be woken when the domain is reduced to a single set value.
• del_glb A suspension list that should be woken when the lower bound of the set domain is updated.
• del_lub a suspension list that should be woken when the upper bound of the set domain is updated.
• del_any a suspension list that should be woken when any reduction of the domain is inferred.

The attribute of a set domain variable can be accessed with the predicate svar_attribute/2 or by unification in a matching clause:

get_attribute(_{set: Attr}, A) :- -?-> nonvar(Attr), Attr = A.

The attribute arguments can be accessed by macros from the ECLiPSe structures.pl library, if e.g. Attr is the attribute of a set domain variable, the del_inst list can be obtained by:

arg(del_inst of set, Attr, Dinst)

or by using a unification:

Attr = set with del_inst: Dinst

Set Domain access

The domains are represented as abstract data types, and the users are not supposed to access them directly. So we provide a number of predicates to allow operations on set domains.

set_range(?Svar,?Glb,?Lub)

If Svar is a set domain variable, it returns the lower and upper bounds of its domain. Otherwise it fails.

glb(?Svar,?Glb)

If Svar is a set domain variable, it returns the lower bound of its domain. Otherwise it fails.

lub(?Svar, ?Lub)

If Svar is a set domain variable, it returns the upper bound of its domain. Otherwise it fails.

el_weight(++E, ?We)

If E is element of a weighted domain, it returns the weight associated to E. Otherwise it fails.

max_weight(?Svar,?E)

If Svar is a set variable, it returns the element of its domain which belongs to the set resulting from the difference of the upper bound and the lower bound and which has the greatest weight. If Svar is a ground set, it returns the element with the biggest weight. Otherwise it fails.

Two specific predicates make a link between a ground set and a list.

set2list(++S, ?L)

If S is a ground set, it returns the corresponding list. If L is also ground it checks if it is the corresponding list. If not, or if S is not ground, it fails.

list2set(++L, ?S)

If L is a ground list, it returns the corresponding set. If S is also ground it checks if it is the corresponding set. If not, or if L is not ground, it fails.

Set variable modification

A specific predicate operate on the set domain variables. When a set domain is reduced, some suspension lists have to be scheduled and woken depending on the bound modified.

NOTE: Their are 4 suspension lists in the conjunto.pl library, which are woken precisely when the event associated with each list occurs. For example, if the lower bound of a set variable is modified, two suspension lists will be woken: the one associated to a glb modification and the one associated to any modification. This allows user-defined constraints to be handled efficiently.

modify_bound(Ind, ?S, ++Newbound)

Ind is a flag which should take the value lub or glb, otherwise it fails ! If S is a ground set, it succeeds if we have Newbound equal to S. If S is a set variable, its new lower or upper bound will be updated. For monotonicity reasons, domains can only get reduced. So a new upper bound has to be contained in the old one and a new lower bound has to contain the old one. Otherwise it fails.