signature FS structure FS : FS where type fd = FD.fd
The FS structure provides access to finite set variables and propagators.
Finite set variables are variables whose values are sets of integers.
import signature FS from "x-alice:/lib/gecode/FS-sig" import structure FS from "x-alice:/lib/gecode/FS"
signature FS = sig type space type intvar type boolvar type setvar type domain = (int*int) vector exception InvalidDomain val setvar : space -> setvar val setvarVec : space * int -> setvar vector val lowerBound : space * domain -> setvar val upperBound : space * domain -> setvar val bounds : space * domain * domain -> setvar datatype intrel = EQ | NQ | LQ | LE | GQ | GR datatype setrel = CMPL | DISJ | SEQ | SNQ | SUB | SUP datatype setop = DUNION | INTER | MINUS | UNION val dom : space * setvar * setrel * domain -> unit val domR : space * setvar * setrel * domain * boolvar -> unit val cardRange : space * int * int * setvar -> unit val rel : space * setvar * setrel * setvar -> unit val relR : space * setvar * setrel * setvar * boolvar -> unit val relOp : space * setvar * setop * setvar * setrel * setvar -> unit val relI : space * setvar * setrel * intvar -> unit val relIR : space * setvar * setrel * intvar * boolvar -> unit val relII : space * setvar * intrel * intvar -> unit val relN : space * setop * setvar vector * setvar -> unit val relNI : space * setop * intvar vector * setvar -> unit val relCSS : space * domain * setop * setvar * setrel * setvar -> unit val relSCS : space * setvar * setop * domain * setrel * setvar -> unit val relSSC : space * setvar * setop * setvar * setrel * domain -> unit val relCCS : space * domain * setop * domain * setrel * setvar -> unit val relCSC : space * domain * setop * setvar * setrel * domain -> unit val relSCC : space * setvar * setop * domain * setrel * domain -> unit val convex : space * setvar -> unit val convexHull : space * setvar * setvar -> unit val sequence : space * setvar vector -> unit val sequentialUnion : space * setvar vector * setvar -> unit structure Value : sig val make : space * domain -> setvar val empty : space -> setvar val single : space * int -> setvar val is : space * setvar -> bool end structure Selection : sig val setvar : space * setvar vector * intvar * setvar -> unit val union : space * setvar vector * setvar * setvar -> unit val inter : space * setvar vector * setvar * setvar -> unit val interIn : space * setvar vector * setvar * setvar * domain -> unit val disjoint : space * setvar vector * setvar -> unit end structure Reflect : sig val card : space * setvar -> (int * int) val lowerBound : space * setvar -> domain val upperBound : space * setvar -> domain val unknown : space * setvar -> domain val cardOfLowerBound : space * setvar -> int val cardOfUpperBound : space * setvar -> int val cardOfUnknown : space * setvar -> int val assigned : space * setvar -> bool end (* Branching strategies *) datatype fsb_var_sel = FSB_MAX_CARD | FSB_MIN_CARD | FSB_MIN_UNKNOWN_ELEM | FSB_NONE datatype fsb_val_sel = FSB_MAX | FSB_MIN val setvarbranch : space * setvar vector * fsb_var_sel * fsb_val_sel -> unit end
The type of first class comutational spaces. Usually equal to Space.space.
The type of finite domain variables. Usually equal to FD.intvar.
The type of boolean constraint variables. Usually equal to FD.intvar.
The type of finite set variables.
The type of domain descriptions.
Used to define set bounds at variable creation, in value
declaration, and reflection.
It is an ordered, non-overlapping, non-contingous vector of
ordered integer pairs.
For example the set of all primes between 1 and 10 is
#[(2,3),(5,5),(7,7)]
Observe that #[(1,2),(3,4)] is an invalid domain: contigous
ranges, use #[(1,4)] instead
#[(1,3),(3,4)] is even more so.
#[(3,2)] is also invalid, the range is ill-defined.
#[(4,5),(1,2)] is nonconformant in pair ordering, #[(1,2),(4,5)] is fine.
Exception thrown by all variable creation and domain tell operations on receipt of a domain description not conforming to the above rules.
Returns a freshly created, unconstrained finite set variable in s. The returned variable is only to be used in s and its decendants.
Returns a vector of n freshly cretaed, unconstrained finite set variables in s.
Returns a freshly created finite set variable in s, already constrained to be a superset of dom.
Returns a freshly created finite set variable in s, already constrained to be a subset of dom.
Returns a freshly created finite set variable in s, already constrained to be a superset of dom1 and a subset of dom2.
Type to identify an arithmetic relation in constraints. This
is the same as FD.relation.
EQ: Equal.
NQ: Not equal.
LQ: Less or equal.
LE: Less.
GQ: Greater or equal.
GR: Greater.
Type to identify a set relation in constraints.
CMPL: Complement.
DISJ: Disjointness.
SEQ: Set equality.
SNQ: Set disequality.
SUB: Subset.
SUP: Superset.
Type to identify a set operation in constraints.
DUNION: Disjoint union.
INTER: Intersection.
MINUS: Difference.
UNION: Union.
Constrains x in s to be in relation r with the set constant denoted by d.
Constrains b to be true if and only if x is in relation r with the set constant denoted by d.
Constrains x in s to have a cardinality (number of set elements) between min and max.
Creates a new propagator in s to constrain x to be in relation r with y.
Constrains b to be true if and only if x is in relation r with y.
Creates a new propagator in s to constrain z to be in relation r with x oper y.
Creates a new propagator in s to constrain x to be in relation r with {y}.
Constrains b to be true if and only if x is in relation r with {y}.
Creates a new propagator in s to constrain all elements in x to be in relation r with y.
Creates a new propagator in s to constrain y to be the result of the n-ary operation oper on the elements of xs.
Creates a new propagator in s to constrain y to be the result of the n-ary operation oper on the elements of xs, which are FD variables treated as singleton sets.
Creates a new propagator in s to constrain z to be in relation r with x oper y. Depending on which of the CSS, SCS etc. is chose, one or two of the x,y,z can be constant sets specified as domains.
Creates a new propagator in s ensuring y is the smallest element of x.
Creates a new propagator in s ensuring y is the largest element of x.
Creates a new propagator in s ensuring y is the number of elements (cardinality) of x.
Creates a new propagator in s ensuring ys is the ordered vector of all elements of x.
Creates a new propagator in s to constrain x to be a convex set, containing all integers between its smallest and largest element.
Creates a new propagator in s to constrain y to be the convex hull of x. Simply put, y has the same smallest and largest element as x, but also contains all integers in between.
Creates a new propagator in s to constrain the largest element of xs[i] to be smaller than the smallest element of xs[i+1].
Creates a new propagator in s to constrain y to be the union of all xs, while xs is a seqence as defined above for the seq constraint. This is a special case of the partitionN constraint.
Creates a determined set in s containing exactly the elements in dom.
Creates a determined, empty set in s.
Creates a determined, single element set in s containing the integer n.
Creates a new propagator in s ensuring the yth element of v is equal to x. y is constrained be in the range of valid indexes for v.
Creates a new propagator in s ensuring the union of the sets in v indexed by all elements of y is x. y is constrained to contain nothing outside the range of valid indexes for v.
Creates a new propagator in s ensuring the intersection of the sets in v indexed by all elements of y is x. y is constrained to contain nothing outside the range of valid indexes for v. If y is the empty set, x is constrained to be the universe.
Creates a new propagator in s ensuring the intersection of the sets in v indexed by all elements of y is x. y is constrained to contain nothing outside the range of valid indexes for v. If y is the empty set, x is constrained to be the universe, given as d.
Creates a new propagator in s ensuring the intersection of the sets in v indexed by all elements of x is empty. x is constrained to contain nothing outside the range of valid indexes for v.
Returns the current cardinality bounds of x in s.
Returns the currently known greatest lower bound set of x in s. Simply put, all elements known to be in the set.
Returns the currently known least upper bound set of x in s. Simply put, all elements not yet known to be excluded from the set.
Returns the elements whose membership in x is currently unknown in s. Simply put, all elements that may still be both included or excluded.
Returns the number of known elements of x in s.
Returns the number of possible elements of x in s.
Returns the number of elements whose membership in x is yet to be determined in s. Same as Reflection.cardOfUpperBound(s,x)-Reflection.cardOfLowerBound(s,x)
Returns true if x is determined in s. Simply put, same as Reflection.cardOfUnknown(x,s)=0
Identifies the variable selection strategy in branching.
FSB_MAX_CARD : Pick the variable with the largest possible cardinality.
FSB_MIN_CARD : Pick the variable with the lowest possible cardinality.
FSB_MIN_UNKNOWN_ELEM : Pick the variable with the smallest unknown element.
FSB_NONE : Pick the leftmost undetermined variable.
Identifies the value selection strategy in branching.
FSB_MAX : Pick the largest unknown value of the variable.
FSB_MIN : Pick the smallest unknown value of the variable.
Creates a new branching (aka distributor or labeling) in s over the setvars in v following the given strategy.