Generated on Wed Nov 1 15:05:18 2006 for Gecode by doxygen 1.4.5
Gecode::Int::GCC

Gecode::Int::GCC Namespace Reference

Detailed Description

Global cardinality propagators.

Note:
The global cardinality propagator with fixed cardinalities does not not support sharing!


Classes

class  SharingTest
 Sharing test for the bounds-consistent global cardinality propagator. More...
class  SharingTest< IntView, OccurBndsView >
 Specialization of class SharingTest for the case of fixed cardinalities using IntView as View1 and OccurBndsView as View2. More...
class  UnReachable
 Class for computing unreachable values in the value GCC propagator. More...
class  Rank
 Maps domain bounds to their position in hall[].bounds. More...
class  MaxInc
 Compares two indices i, j of two views $ x_i $ $ x_j$ according to the ascending order of the views upper bounds. More...
class  MinInc
 Compares two indices 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  OccurBndsView
 Tuple conataining the lower and upper cardinality bounds. More...
class  CardView
 Card integer view. More...
class  Bnd
 Bounds-consistent global cardinality propagator. More...
class  BndImp
 Implementation of the bounds consistent global cardinality propagator. More...
class  Dom
 Domain-consistent global cardinality propagator. More...
class  Val
 Value consistent global cardinality propagator. More...

GCC-Bnd-Support

template<class View, class Card, bool shared>
ExecStatus prop_card (Space *home, ViewArray< View > &x, ViewArray< Card > &k, bool &mod)
 Bounds consistency check for cardinality variables.
template<class View, class Card>
bool card_consistent (int &smin, int &smax, ViewArray< View > &x, ViewArray< Card > &k, bool &all)
 Consistency check, whether the cardinality values are feasible.

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 isView, bool shared>
ExecStatus prop_bnd (Space *home, ViewArray< View > &x, ViewArray< Card > &k, PartialSum< Card > *&lps, PartialSum< Card > *&ups, bool card_fixed, bool card_all, bool nolbc)
 Performs bounds-consistent global cardinality propagation.
template<class Card>
void reduce_card (int cmin, int cmax, ViewArray< Card > &k)
 Assert consistency in the cardinality specification for bounds propagation.
std::ostream & operator<< (std::ostream &os, VarNode *v)
 Debugging: print a variable node.
std::ostream & operator<< (std::ostream &os, ValNode *v)
 Debugging: print a value node.
std::ostream & operator<< (std::ostream &os, Edge *e)
 Debugging: print an 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[])
 Lower Bounds constraint (LBC) stating $ \forall j \in \{0, \dots, |k|-1\}: \#\{i\in\{0, \dots, |x| - 1\} | x_i = card(k_j)\} \geq min(k_j)$ Hence the lbc constraints the variables such that every value occurs at least as often as specified by its lower cardinality bound.
std::ostream & operator<< (std::ostream &os, OccurBndsView &xs)
 Debugging: print a fixed cardinality.
template<class T>
int lookupValue (T &a, int v)
 Return the index of v in the array.
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, ViewArray< Card > &k, bool &_cardall)
 Performs value-consistent global cardinality propagation.
template<class Card>
bool check_alldiff (int n, ViewArray< Card > &k)
 Check whether gcc can be rewritten to distinct.
template<class View>
int x_card (ViewArray< View > &x, IntConLevel icl)
 Compute the cardinality of the union of all variable domains in x.
template<class Card, class View>
void initcard (Space *home, ViewArray< View > &x, ViewArray< Card > &k, int lb, int ub, IntConLevel icl)
 Initialize the cardinalities for the values in k.
template<class Card, class View, bool isView>
void setcard (Space *home, ViewArray< View > &x, ViewArray< Card > &k, int xmin, int xmax)
 Reset already existing cardinalities to zero.
template<class Card, bool isView>
ExecStatus card_cons (Space *home, ViewArray< Card > &k, int n, bool all)
 Check whether the cardinalities are consistent.
template<class View, class Card, bool isView>
void post_template (Space *home, ViewArray< View > &x, ViewArray< Card > &k, IntConLevel &icl, bool &all)
 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 30 of file graphsup.icc.

Function Documentation

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

Performs bounds-consistent global cardinality propagation.

This function implements the propagation algorithm for the bounds-consistent global cardinality propagator implemented in GCC::Bnd. It is available as seperate function in order to allow staging for GCC::Dom and GCC::Bnd though staging is currently not used due to technical difficulties.

Definition at line 27 of file bnd.icc.

template<class View, class Card, bool shared>
ExecStatus Gecode::Int::GCC::prop_card (  Space *  home,
ViewArray< View > &  x,
ViewArray< Card > &  k,
bool &  mod
)  [inline]
 

Bounds consistency check for cardinality variables.

Definition at line 47 of file gccbndsup.icc.

template<class View, class Card>
bool Gecode::Int::GCC::card_consistent (  int &  smin,
int &  smax,
ViewArray< View > &  x,
ViewArray< Card > &  k,
bool &  all
)  [inline]
 

Consistency check, whether the cardinality values are feasible.

Definition at line 136 of file gccbndsup.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 577 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 586 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 595 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 604 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 621 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 628 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 643 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 652 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 661 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 669 of file gccbndsup.icc.

template<class Card>
void Gecode::Int::GCC::reduce_card (  int  cmin,
int  cmax,
ViewArray< 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 688 of file gccbndsup.icc.

std::ostream& Gecode::Int::GCC::operator<< (  std::ostream &  os,
VarNode *  v
)  [inline]
 

Debugging: print a variable node.

Definition at line 423 of file graphsup.icc.

std::ostream& Gecode::Int::GCC::operator<< (  std::ostream &  os,
ValNode *  v
)  [inline]
 

Debugging: print a value node.

Definition at line 435 of file graphsup.icc.

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

Debugging: print an edge.

Definition at line 985 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]
 

Lower Bounds constraint (LBC) stating $ \forall j \in \{0, \dots, |k|-1\}: \#\{i\in\{0, \dots, |x| - 1\} | x_i = card(k_j)\} \geq min(k_j)$ Hence the lbc constraints the variables such that every value occurs at least as often as specified by its lower 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)
lps partial sum structure for the lower 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 lbc.icc.

std::ostream& Gecode::Int::GCC::operator<< (  std::ostream &  os,
OccurBndsView &  xs
)  [inline]
 

Debugging: print a fixed cardinality.

Definition at line 167 of file occur.icc.

template<class T>
int Gecode::Int::GCC::lookupValue (  T &  a,
int  v
)  [inline]
 

Return the index of v in the array.

Complexity is $O(log(|k|))$

Definition at line 188 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 46 of file ubc.icc.

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

Performs value-consistent global cardinality propagation.

This function implements the propagation algorithm for the value-consistent global cardinality propagator implemented in GCC::Val.

Definition at line 25 of file val.icc.

template<class Card>
bool Gecode::Int::GCC::check_alldiff (  int  n,
ViewArray< 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 37 of file gcc.cc.

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

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

Definition at line 84 of file gcc.cc.

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

Initialize the cardinalities for the values in k.

Definition at line 122 of file gcc.cc.

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

Reset already existing cardinalities to zero.

Definition at line 160 of file gcc.cc.

template<class Card, bool isView>
ExecStatus Gecode::Int::GCC::card_cons (  Space *  home,
ViewArray< Card > &  k,
int  n,
bool  all
)  [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 203 of file gcc.cc.

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

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

Definition at line 260 of file gcc.cc.