alice
library
manual.
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
(* Exception thrown by all domain tells *)
(* if something that is no proper domain is used *)
(* Allocation of finite set variables *)
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
(* Standard Propagators *)
val cardRange : space * int * int * setvar -> unit
val superOfInter : space * setvar * setvar * setvar -> unit
val subOfUnion : space * setvar * setvar * setvar -> unit
val compl : space * setvar * setvar -> unit
val difference : space * setvar * setvar * setvar -> unit
val intersect : space * setvar * setvar * setvar -> unit
val intersectN : space * setvar vector * setvar -> unit
val union : space * setvar * setvar * setvar -> unit
val unionN : space * setvar vector * setvar -> unit
val subset : space * setvar * setvar -> unit
val noSubset : space * setvar * setvar -> unit
val disjoint : space * setvar * setvar -> unit
val distinct : space * setvar * setvar -> unit
val distinctN : space * setvar vector -> unit
val partition : space * setvar * setvar * setvar -> unit
val partitionN : space * setvar vector * setvar -> unit
val equals : space * setvar * setvar -> unit
val convex : space * setvar -> unit
val convexHull : space * setvar * setvar -> unit
val seq : space * setvar vector -> unit
val seqU : space * setvar vector * setvar -> unit
structure Value :
sig
val make : space * domain -> setvar
val empty : space -> setvar
val single : space * int -> setvar
end
structure Int :
sig
val incl : space * setvar * intvar -> unit
val excl : space * setvar * intvar -> unit
val the : space * setvar * intvar -> unit
val min : space * setvar * intvar -> unit
val max : space * setvar * intvar -> unit
val card : space * setvar * intvar -> unit
val match : space * setvar * intvar vector -> unit
end
structure Reified : sig
val isIn : space * setvar * int * boolvar -> unit
val areIn : space * (boolvar * int) vector * setvar -> unit
val incl : space * intvar * setvar * boolvar -> unit
val equal : space * setvar * setvar * boolvar -> unit
val subset : space * setvar * setvar * boolvar -> unit
end
structure Selection : sig
val setvar : space * setvar * setvar vector * intvar -> unit
val union : space * setvar * setvar vector * setvar -> unit
val inter : space * setvar * setvar vector * setvar -> 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
| FSB_RANDOM_VAR
datatype fsb_val_sel =
FSB_MAX
| FSB_MIN
| FSB_RANDOM_VAL
val setvarbranch : space * setvar vector * fsb_var_sel *
fsb_val_sel -> unit
val randomBranch : space * setvar vector * fsb_var_sel *
fsb_val_sel * int -> 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.
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 a superset of the intersection of y and z.
Creates a new propagator in s to constrain x to be a subset of the union of y and z.
Creates a new propagator in s to constrain x and y to be complements using the largest set representable as the universe.
Creates a new propagator in s so that x is y minus z.
Creates a new propagator in s to constrain x to be the intersection of y and z.
Creates a new propagator in s to constrain x to be the intersection of all vi.
Creates a new propagator in s to constrain x to be the union of y and z.
Creates a new propagator in s to constrain x to be the union of all vi.
Creates a new propagator in s to constrain x to be a subset of y.
Creates a new propagator in s to constrain x not to be a subset of y. Simply put, x must contain at least one element not present in y.
Creates a new propagator in s to constrain x and y to have no common element.
Creates a new propagator in s to constrain x and y to be separate sets, differing in at least one element.
Creates a new propagator in s to say no two sets in v can be the same.
Creates a new propagator in s to constrain x to be the disjoint union of y and z.
Creates a new propagator in s to constrain x to be the disjoint union of all vi
Creates a new propagator in s to constrain x and y to be the same set.
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 x to be the convex hull of y. Simply put, x has the same smallest and largest element as y, but also contains all integers in between.
Creates a new propagator in s to constrain the largest element of v[i] to be smaller than the smallest element of v[i+1].
Creates a new propagator in s to constrain x to be the union of all vi, while v is a seqence as defined above. 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 y is an element of x.
Creates a new propagator in s ensuring y is not an element of x.
Creates a new propagator in s ensuring y is the one and only element of x. Constrains the cardinality of x to 1.
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 v is the ordered vector of all elements of x.
Creates a new propagator in s ensuring v is the ordered vector of the smallest elements of x.
Creates a new propagator in s ensuring v is the ordered vector of the largest elements of x.
Creates a new propagator in s ensuring b is true if and only if y is an element of x
Creates a new propagator in s ensuring v2i is true if and only if v1i is an element of x
Creates a new propagator in s ensuring b is true if and only if y is an element of x
Creates a new propagator in s ensuring b is true if and only if y and x are the same set.
Creates a new propagator in s ensuring b is true if and only if x is a subset of y
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.
Creates a new propagator in s ensuring the intersection of the sets in v indexed by all elements of y is empty. y 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.
FSB_RANDOM_VAR : Pick at random.
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.
FSB_RANDOM_VAR : Pick at random.
Creates a new branching (aka distributor or labeling) in s over the setvars in v following the given strategy.
same as setvarbranch, with the possibility of pre-setting the random seed to achieve reproduceable random search trees.