Generated on Thu Mar 22 10:39:49 2012 for Gecode by doxygen 1.6.3

Extensional constraints
[Using finite domain integers]

Classes

class  Gecode::DFA
 Deterministic finite automaton (DFA). More...
class  Gecode::TupleSet
 Class represeting a set of tuples. More...

Enumerations

enum  Gecode::ExtensionalPropKind { Gecode::EPK_DEF, Gecode::EPK_SPEED, Gecode::EPK_MEMORY }
 

Extensional propagation kind.

More...

Functions

void Gecode::extensional (Home home, const IntVarArgs &x, DFA d, IntConLevel icl=ICL_DEF)
 Post domain consistent propagator for extensional constraint described by a DFA.
void Gecode::extensional (Home home, const BoolVarArgs &x, DFA d, IntConLevel icl=ICL_DEF)
 Post domain consistent propagator for extensional constraint described by a DFA.
void Gecode::extensional (Home home, const IntVarArgs &x, const TupleSet &t, ExtensionalPropKind epk=EPK_DEF, IntConLevel icl=ICL_DEF)
 Post propagator for $x\in t$.
void Gecode::extensional (Home home, const BoolVarArgs &x, const TupleSet &t, ExtensionalPropKind epk=EPK_DEF, IntConLevel icl=ICL_DEF)
 Post propagator for $x\in t$.

Detailed Description

Extensional constraints support different ways of how the extensionally defined relation between the variables is defined. Examples include specification by a DFA or a table.

A DFA can be defined by a regular expression, for regular expressions see the module MiniModel.


Enumeration Type Documentation

Extensional propagation kind.

Signals that a particular kind is used in propagation for the implementation of a extensional constraint.

Enumerator:
EPK_DEF 

Make a default decision.

EPK_SPEED 

Prefer speed over memory consumption.

EPK_MEMORY 

Prefer little memory over speed.

Definition at line 1845 of file int.hh.


Function Documentation

void Gecode::extensional ( Home  home,
const IntVarArgs &  x,
DFA  d,
IntConLevel  icl = ICL_DEF 
)

Post domain consistent propagator for extensional constraint described by a DFA.

The elements of x must be a word of the language described by the DFA d.

Throws an exception of type Int::ArgumentSame, if x contains the same unassigned variable multiply. If shared occurences of variables are required, unshare should be used.

void Gecode::extensional ( Home  home,
const BoolVarArgs &  x,
DFA  d,
IntConLevel  icl = ICL_DEF 
)

Post domain consistent propagator for extensional constraint described by a DFA.

The elements of x must be a word of the language described by the DFA d.

Throws an exception of type Int::ArgumentSame, if x contains the same unassigned variable multiply. If shared occurences of variables are required, unshare should be used.

void Gecode::extensional ( Home  home,
const IntVarArgs &  x,
const TupleSet &  t,
ExtensionalPropKind  epk = EPK_DEF,
IntConLevel  icl = ICL_DEF 
)

Post propagator for $x\in t$.

  • Supports implementations optimized for memory (epk = EPK_MEMORY, default) and speed (epk = EPK_SPEED).
  • Supports domain consistency (icl = ICL_DOM, default) only.
  • Throws an exception of type Int::ArgumentSizeMismatch, if x and t are of different size.
  • Throws an exception of type Int::NotYetFinalized, if the tuple set t has not been finalized.
Warning:
If the domains for the $x_i$ are not dense and have similar bounds, lots of memory will be wasted (memory consumption is in $ O\left(|x|\cdot\min_i(\underline{x_i})\cdot\max_i(\overline{x_i})\right)$ for the basic algorithm (epk = EPK_MEMORY) and additionally $ O\left(|x|^2\cdot\min_i(\underline{x_i})\cdot\max_i(\overline{x_i})\right)$ for the incremental algorithm (epk = EPK_SPEED).
void Gecode::extensional ( Home  home,
const BoolVarArgs &  x,
const TupleSet &  t,
ExtensionalPropKind  epk = EPK_DEF,
IntConLevel  icl = ICL_DEF 
)

Post propagator for $x\in t$.

  • Supports implementations optimized for memory (epk = EPK_MEMORY, default) and speed (epk = EPK_SPEED).
  • Supports domain consistency (icl = ICL_DOM, default) only.
  • Throws an exception of type Int::ArgumentSizeMismatch, if x and t are of different size.
  • Throws an exception of type Int::NotYetFinalized, if the tuple set t has not been finalized.