Generated on Mon Aug 25 11:35:51 2008 for Gecode by doxygen 1.5.6
Gecode::Int::GCC::Dom

Gecode::Int::GCC::Dom< View, Card, isView > Class Template Reference
[Integer propagators]

#include <gcc.hh>

Inherits Gecode::Propagator.

List of all members.

Detailed Description

template<class View, class Card, bool isView>
class Gecode::Int::GCC::Dom< View, Card, isView >

Domain consistent global cardinality propagator.

[Reference]
The algorithm is taken from: 
     @PROCEEDINGS{improvedgcc,
     title     = {Improved Algorithms for the
                  Global Cardinality Constraint},
     year      = {2004},
     volume    = {3528},
     address   = {Toronto, Canada},
     month     = {September},
     author    = {Claude-Guy Quimper and Peter van Beek and
                  Alejandro López-Ortiz and Alexander Golynski},
     booktitle = {Proceedings of the 10th International
                  Conference on Principles and Practice of
                  Constraint Programming},
     url       = {http://ai.uwaterloo.ca/~vanbeek/publications},
     }
Requires 
 #include "gecode/int/gcc.hh"

Definition at line 207 of file gcc.hh.


Public Member Functions

virtual size_t dispose (Space *home)
 Destructor including deallocation of variable-value graph.
virtual size_t allocated (void) const
 Return how much extra memory is allocated by the propagator.
virtual Actor * copy (Space *home, bool share)
 Copy propagator during cloning.
virtual PropCost cost (ModEventDelta med) const
 Cost function.
virtual ExecStatus propagate (Space *home, ModEventDelta med)
 Perform propagation.
virtual Reflection::ActorSpec spec (const Space *home, Reflection::VarMap &m) const
 Specification for this propagator.

Static Public Member Functions

static void post (Space *home, Reflection::VarMap &vars, const Reflection::ActorSpec &spec)
 Post propagator according to specification.
static Support::Symbol ati (void)
 Name of this propagator.
static ExecStatus post (Space *home, ViewArray< View > &x, ViewArray< Card > &k)
 Post propagator for views x and cardinalities k.

Protected Member Functions

 Dom (Space *home, bool share, Dom< View, Card, isView > &p)
 Constructor for cloning p.
 Dom (Space *home, ViewArray< View > &, ViewArray< Card > &, bool)
 Constructor for posting.

Protected Attributes

ViewArray< View > x
 Views on which to perform domain-propagation.
ViewArray< View > y
 Views used to channel information between x and k ($ x \subseteq y $).
ViewArray< Card > k
 Array containing either fixed cardinalities or CardViews.
VarValGraph< View, Card, isView > * vvg
 Propagation is performed on a variable-value graph (used as cache).
bool card_fixed
 Stores whether cardinalities are all assigned.

Constructor & Destructor Documentation

template<class View, class Card, bool isView>
Gecode::Int::GCC::Dom< View, Card, isView >::Dom ( Space *  home,
bool  share,
Dom< View, Card, isView > &  p 
) [inline, protected]

Constructor for cloning p.

Definition at line 79 of file dom.icc.

template<class View, class Card, bool isView>
Gecode::Int::GCC::Dom< View, Card, isView >::Dom ( Space *  home,
ViewArray< View > &  x0,
ViewArray< Card > &  k0,
bool  cf 
) [inline, protected]

Constructor for posting.

Definition at line 66 of file dom.icc.

Member Function Documentation

template<class View, class Card, bool isView>
size_t Gecode::Int::GCC::Dom< View, Card, isView >::dispose ( Space *  home  )  [inline, virtual]

Destructor including deallocation of variable-value graph.

Reimplemented from Gecode::Actor.

Definition at line 89 of file dom.icc.

template<class View, class Card, bool isView>
size_t Gecode::Int::GCC::Dom< View, Card, isView >::allocated ( void   )  const [inline, virtual]

Return how much extra memory is allocated by the propagator.

Reimplemented from Gecode::Actor.

Definition at line 102 of file dom.icc.

template<class View, class Card, bool isView>
Actor * Gecode::Int::GCC::Dom< View, Card, isView >::copy ( Space *  home,
bool  share 
) [inline, virtual]

Copy propagator during cloning.

Implements Gecode::Actor.

Definition at line 108 of file dom.icc.

template<class View, class Card, bool isView>
PropCost Gecode::Int::GCC::Dom< View, Card, isView >::cost ( ModEventDelta  med  )  const [inline, virtual]

Cost function.

As the propagation stronlgy depends on the domain size of the views on which propagation is performed, the propagation costs are computed as follows, where d denotes the size of the largest domain of a view in x:

  • dynamic PC_LINEAR_LO ( $ d < 6$ )
  • dynamic PC_LINEAR_HI ( $ 6 \leq d < \frac{n}{2} $ )
  • dynamic PC_QUADRATIC_LO ( $ \frac{n}{2} \leq d < n^2 $)
  • dynamic PC_CUBIC_LO ( $ n^2 \leq d $)

Implements Gecode::Propagator.

Definition at line 114 of file dom.icc.

template<class View, class Card, bool isView>
ExecStatus Gecode::Int::GCC::Dom< View, Card, isView >::propagate ( Space *  home,
ModEventDelta  med 
) [inline, virtual]

Perform propagation.

Perform domain propagation.

Implements Gecode::Propagator.

Definition at line 171 of file dom.icc.

template<class View, class Card, bool isView>
Reflection::ActorSpec Gecode::Int::GCC::Dom< View, Card, isView >::spec ( const Space *  home,
Reflection::VarMap &  m 
) const [inline, virtual]

Specification for this propagator.

Reimplemented from Gecode::Actor.

Definition at line 151 of file dom.icc.

template<class View, class Card, bool isView>
void Gecode::Int::GCC::Dom< View, Card, isView >::post ( Space *  home,
Reflection::VarMap &  vars,
const Reflection::ActorSpec &  spec 
) [inline, static]

Post propagator according to specification.

Definition at line 159 of file dom.icc.

template<class View, class Card, bool isView>
Support::Symbol Gecode::Int::GCC::Dom< View, Card, isView >::ati ( void   )  [inline, static]

Name of this propagator.

Definition at line 145 of file dom.icc.

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

Post propagator for views x and cardinalities k.

all denotes whether the propagator uses all values occuring in the domains of the problem views specified in x.

Definition at line 515 of file dom.icc.

Member Data Documentation

template<class View, class Card, bool isView>
ViewArray<View> Gecode::Int::GCC::Dom< View, Card, isView >::x [protected]

Views on which to perform domain-propagation.

Definition at line 210 of file gcc.hh.

template<class View, class Card, bool isView>
ViewArray<View> Gecode::Int::GCC::Dom< View, Card, isView >::y [protected]

Views used to channel information between x and k ($ x \subseteq y $).

Definition at line 215 of file gcc.hh.

template<class View, class Card, bool isView>
ViewArray<Card> Gecode::Int::GCC::Dom< View, Card, isView >::k [protected]

Array containing either fixed cardinalities or CardViews.

Definition at line 217 of file gcc.hh.

template<class View, class Card, bool isView>
VarValGraph<View, Card, isView>* Gecode::Int::GCC::Dom< View, Card, isView >::vvg [protected]

Propagation is performed on a variable-value graph (used as cache).

Definition at line 219 of file gcc.hh.

template<class View, class Card, bool isView>
bool Gecode::Int::GCC::Dom< View, Card, isView >::card_fixed [protected]

Stores whether cardinalities are all assigned.

If all cardinalities are assigned the propagation algorithm only has to perform propagation for the upper bounds.

Definition at line 226 of file gcc.hh.

The documentation for this class was generated from the following files: