Generated on Mon Aug 25 11:35:51 2008 for Gecode by doxygen 1.5.6
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)
 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 Card>
void reduce_card (int cmin, int cmax, ViewArray< Card > &k)
 Assert consistency in the cardinality specification for bounds propagation.
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.
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 Card, bool isView>
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)
 Compute the cardinality of the union of all variable domains in x.
template<class Card, bool isView>
ExecStatus card_cons (Space *home, ViewArray< Card > &k, int n)
 Check whether the cardinalities are consistent.
template<class Card, bool isView>
void post_template (Space *home, ViewArray< IntView > &x, ViewArray< 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 46 of file graphsup.icc.

Function Documentation

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 63 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 
) [inline]

Consistency check, whether the cardinality values are feasible.

Definition at line 149 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 598 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 607 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 616 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 625 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 642 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 649 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 664 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 673 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 682 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 690 of file gccbndsup.icc.

template<class Card>
void Gecode::Int::GCC::reduce_card ( int  cmin,
int  cmax,
ViewArray< Card > &  k 
) [inline]

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 709 of file gccbndsup.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 63 of file lbc.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 231 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 62 of file ubc.icc.

template<class Card, bool isView>
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 57 of file gcc.cc.

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

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

Definition at line 80 of file gcc.cc.

template<class Card, bool isView>
ExecStatus Gecode::Int::GCC::card_cons ( Space *  home,
ViewArray< 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 102 of file gcc.cc.

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

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

Definition at line 150 of file gcc.cc.