Generated on Wed Jan 4 17:49:21 2006 for Gecode by doxygen 1.4.6

Gecode::Int::GCC Namespace Reference


Detailed Description

Global cardinality propagators.


Classes

class  Rank
 Maps domain bounds to their position in hall[].bounds. More...
class  MaxInc
 Compares two indeces i, j of two views $ x_i $ $ x_j$ according to the ascending order of the views upper bounds. More...
class  MinInc
 Compares two indeces i, j of two views $ x_i $ $ x_j$ according to the ascending order of the views lower bounds. More...
class  PartialSum
 Partial sum structure for constant time computation of the maximal capacity of an interval. More...
class  HallInfo
 Container class provding information about the Hall structure of the problem variables. More...
class  VVGNode
 Base class for nodes in the variable-value-graph. More...
class  VarNode
 Variable Node More...
class  ValNode
 Value node. More...
class  Edge
 Class for edges $ e(x,v) $ in the variable-value-graph. More...
class  VarValGraph
 Variable-value-graph used during propagation. More...
class  OccurBnds
 Tuple conataining the lower and upper cardinality bounds. More...
class  OccurArray
 Array of OccurBnds mimicking cardinality variables. More...
class  CardView
 Card integer view. More...
class  CardArray
 Array containing CardView and supporting lookup operation. More...
class  IdxView
 Card integer view. More...
class  Bnd
 Bounds-consistent global cardinality propagator. More...
class  BndImp
 Implementation of bounds-consistent global cardinality propagator. More...
class  Dom
 Domain-consistent global cardinality propagator. More...
class  Val
 Value consistent global cardinality propagator. More...

Path compression

Each of the nodes on the path from start to end becomes a direct child of to.

void pathset_ps (HallInfo hall[], int start, int end, int to)
 Path compression for potentially stable set structure.
void pathset_s (HallInfo hall[], int start, int end, int to)
 Path compression for stable set structure.
void pathset_t (HallInfo hall[], int start, int end, int to)
 Path compression for capacity pointer structure.
void pathset_h (HallInfo hall[], int start, int end, int to)
 Path compression for hall pointer structure.

Path minimum

returns the smalles reachable index starting from i

int pathmin_h (const HallInfo hall[], int i)
 Path minimum for hall pointer structure.
int pathmin_t (const HallInfo hall[], int i)
 Path minimum for capacity pointer structure.

Path maximum

returns the greatest reachable index starting from i

int pathmax_h (const HallInfo hall[], int i)
 Path maximum for hall pointer structure.
int pathmax_t (const HallInfo hall[], int i)
 Path maximum for capacity pointer structure.
int pathmax_s (const HallInfo hall[], int i)
 Path maximum for stable set pointer structure.
int pathmax_ps (const HallInfo hall[], int i)
 Path maximum for potentially stable set pointer structure.

Enumerations

enum  BC { UBC = 1, LBC = 0 }
 Bounds constraint (BC) type. More...

Functions

template<class View, class Card, bool shared, bool isView>
ExecStatus prop_bnd (Space *home, ViewArray< View > &x, Card &k, PartialSum< Card > *lps, PartialSum< Card > *ups)
template<class Card>
void reduce_card (int cmin, int cmax, Card &k)
 Assert consistency in the cardinality specification for bounds propagation.
template<class View>
void pview (View &v)
 Debugging: Print a View.
std::ostream & operator<< (std::ostream &os, Edge *e)
 Edge.
template<class View, class Card, bool shared>
ExecStatus lbc (Space *home, ViewArray< View > &x, int &nb, HallInfo hall[], Rank rank[], PartialSum< Card > *lps, int mu[], int nu[])
template<class T, unsigned int n>
std::ostream & operator<< (std::ostream &os, const OccurBnds< T, n > &xy)
template<class View, class Card, bool shared>
ExecStatus ubc (Space *home, ViewArray< View > &x, int &nb, HallInfo hall[], Rank rank[], PartialSum< Card > *ups, int mu[], int nu[])
 Upper Bounds constraint (UBC) stating $ \forall j \in \{0, \dots, |k|-1\}: \#\{i\in\{0, \dots, |x| - 1\} | x_i = card(k_j)\} \leq max(k_j)$ Hence the ubc constraints the variables such that no value occurs more often than specified by its upper cardinality bound.
template<class View, class Card, bool isView>
ExecStatus prop_val (Space *home, ViewArray< View > &x, Card &k)
template<class Card>
bool check_alldiff (int n, Card &k)
 Check whether gcc can be rewritten to distinct.
template<class View>
void x_setidx (ViewArray< View > &x)
 Set the index of every variable to its initial position in x.
template<class View>
int x_card (ViewArray< View > &x)
 Compute the cardinality of the union of all variable domains in x.
template<class Card, class View>
void initcard (Space *home, ViewArray< View > &x, Card &k, int lb, int ub)
 Initialize the cardinalities for the values in k.
template<class Card, class View, bool isView>
void setcard (Space *home, ViewArray< View > &x, Card &k, int xmin, int xmax)
 Reset already existing cardinalities to zero.
template<class Card, bool isView>
ExecStatus card_cons (Space *home, Card &k, int n)
 Check whether the cardinalities are consistent.
template<class View, class Card, bool isView>
void post_template (Space *home, ViewArray< View > &x, Card &k, IntConLevel &icl)
 Template to post the global cardinality constraint for the different interfaces.


Enumeration Type Documentation

enum Gecode::Int::GCC::BC
 

Bounds constraint (BC) type.

If BC = UBC, then we argue about the Upper Bounds Constraint else we use the functions for the Lower Bounds Constraint

Enumerator:
UBC 
LBC 

Definition at line 50 of file graphsup.icc.


Function Documentation

template<class View, class Card, bool shared, bool isView>
ExecStatus Gecode::Int::GCC::prop_bnd Space *  home,
ViewArray< View > &  x,
Card &  k,
PartialSum< Card > *  lps,
PartialSum< Card > *  ups
[inline]
 

Definition at line 26 of file bnd.icc.

void Gecode::Int::GCC::pathset_ps HallInfo  hall[],
int  start,
int  end,
int  to
[inline]
 

Path compression for potentially stable set structure.

Definition at line 417 of file gccbndsup.icc.

void Gecode::Int::GCC::pathset_s HallInfo  hall[],
int  start,
int  end,
int  to
[inline]
 

Path compression for stable set structure.

Definition at line 427 of file gccbndsup.icc.

void Gecode::Int::GCC::pathset_t HallInfo  hall[],
int  start,
int  end,
int  to
[inline]
 

Path compression for capacity pointer structure.

Definition at line 437 of file gccbndsup.icc.

void Gecode::Int::GCC::pathset_h HallInfo  hall[],
int  start,
int  end,
int  to
[inline]
 

Path compression for hall pointer structure.

Definition at line 447 of file gccbndsup.icc.

int Gecode::Int::GCC::pathmin_h const HallInfo  hall[],
int  i
[inline]
 

Path minimum for hall pointer structure.

Definition at line 465 of file gccbndsup.icc.

int Gecode::Int::GCC::pathmin_t const HallInfo  hall[],
int  i
[inline]
 

Path minimum for capacity pointer structure.

Definition at line 472 of file gccbndsup.icc.

int Gecode::Int::GCC::pathmax_h const HallInfo  hall[],
int  i
[inline]
 

Path maximum for hall pointer structure.

Definition at line 487 of file gccbndsup.icc.

int Gecode::Int::GCC::pathmax_t const HallInfo  hall[],
int  i
[inline]
 

Path maximum for capacity pointer structure.

Definition at line 496 of file gccbndsup.icc.

int Gecode::Int::GCC::pathmax_s const HallInfo  hall[],
int  i
[inline]
 

Path maximum for stable set pointer structure.

Definition at line 504 of file gccbndsup.icc.

int Gecode::Int::GCC::pathmax_ps const HallInfo  hall[],
int  i
[inline]
 

Path maximum for potentially stable set pointer structure.

Definition at line 512 of file gccbndsup.icc.

template<class Card>
void Gecode::Int::GCC::reduce_card int  cmin,
int  cmax,
Card &  k
 

Assert consistency in the cardinality specification for bounds propagation.

This is done by ensuring that only those values are specified with cardinalities, which are not smaller than the smallest value of all variable domains and not greater than the greatest value of all variable domains.

Definition at line 530 of file gccbndsup.icc.

template<class View>
void Gecode::Int::GCC::pview View &  v  ) 
 

Debugging: Print a View.

Definition at line 26 of file graphsup.icc.

std::ostream& Gecode::Int::GCC::operator<< std::ostream &  os,
Edge *  e
[inline]
 

Edge.

Definition at line 968 of file graphsup.icc.

template<class View, class Card, bool shared>
ExecStatus Gecode::Int::GCC::lbc Space *  home,
ViewArray< View > &  x,
int &  nb,
HallInfo  hall[],
Rank  rank[],
PartialSum< Card > *  lps,
int  mu[],
int  nu[]
[inline]
 

Definition at line 26 of file lbc.icc.

template<class T, unsigned int n>
std::ostream & Gecode::Int::GCC::operator<< std::ostream &  os,
const OccurBnds< T, n > &  xy
[inline]
 

Definition at line 187 of file occur.icc.

template<class View, class Card, bool shared>
ExecStatus Gecode::Int::GCC::ubc Space *  home,
ViewArray< View > &  x,
int &  nb,
HallInfo  hall[],
Rank  rank[],
PartialSum< Card > *  ups,
int  mu[],
int  nu[]
[inline]
 

Upper Bounds constraint (UBC) stating $ \forall j \in \{0, \dots, |k|-1\}: \#\{i\in\{0, \dots, |x| - 1\} | x_i = card(k_j)\} \leq max(k_j)$ Hence the ubc constraints the variables such that no value occurs more often than specified by its upper cardinality bound.

Parameters:
home current space
x the problem variables
nb denotes number of unique bounds
hall contains information about the hall structure of the problem (cf. HallInfo)
rank ranking information about the variable bounds (cf. Rank)
ups partial sum structure for the upper cardinality bounds (cf. PartialSum)
mu permutation $ \mu $ such that $ \forall i\in \{0, \dots, |x|-2\}: max(x_{\mu(i)}) \leq max(x_{\mu(i+1)})$
nu permutation $ \nu $ such that $ \forall i\in \{0, \dots, |x|-2\}: min(x_{\mu(i)}) \leq min(x_{\mu(i+1)})$

Definition at line 47 of file ubc.icc.

template<class View, class Card, bool isView>
ExecStatus Gecode::Int::GCC::prop_val Space *  home,
ViewArray< View > &  x,
Card &  k
[inline]
 

Definition at line 25 of file val.icc.

template<class Card>
bool Gecode::Int::GCC::check_alldiff int  n,
Card &  k
[inline]
 

Check whether gcc can be rewritten to distinct.

If the number of available values equals $ |x| $, we can rewrite gcc to distinct if every value occurs exactly once. If the number of available values is greater than $ |x| $, we can rewrite gcc to distinct if every value occurs at least zero times and atmost once, otherwise, there is no rewriting possible.

Definition at line 40 of file gcc.cc.

template<class View>
void Gecode::Int::GCC::x_setidx ViewArray< View > &  x  )  [inline]
 

Set the index of every variable to its initial position in x.

Definition at line 86 of file gcc.cc.

template<class View>
int Gecode::Int::GCC::x_card ViewArray< View > &  x  )  [inline]
 

Compute the cardinality of the union of all variable domains in x.

Definition at line 99 of file gcc.cc.

template<class Card, class View>
void Gecode::Int::GCC::initcard Space *  home,
ViewArray< View > &  x,
Card &  k,
int  lb,
int  ub
[inline]
 

Initialize the cardinalities for the values in k.

Definition at line 126 of file gcc.cc.

template<class Card, class View, bool isView>
void Gecode::Int::GCC::setcard Space *  home,
ViewArray< View > &  x,
Card &  k,
int  xmin,
int  xmax
[inline]
 

Reset already existing cardinalities to zero.

Definition at line 150 of file gcc.cc.

template<class Card, bool isView>
ExecStatus Gecode::Int::GCC::card_cons Space *  home,
Card &  k,
int  n
[inline]
 

Check whether the cardinalities are consistent.

  1. $\forall i\in\{0, \dots, |k| - 1\}: max(k_i) \leq |x|$
  2. $\neg\exists i\in\{0, \dots, |k| - 1\}: min(k_i) > |x|$

Definition at line 192 of file gcc.cc.

template<class View, class Card, bool isView>
void Gecode::Int::GCC::post_template Space *  home,
ViewArray< View > &  x,
Card &  k,
IntConLevel icl
[inline]
 

Template to post the global cardinality constraint for the different interfaces.

Definition at line 212 of file gcc.cc.