Main Page | Class Hierarchy | Class List | File List | Class Members

Variable Class Reference

#include <Variable.h>

Inheritance diagram for Variable:

Double Float Int Long List of all members.

Public Types

typedef FastVector< Constraint
* >::const_iterator 		constraint_iterator
 Iterator through a vector of constraints.

Public Member Functions

 Variable (const Problem &problem, int min, int max, int index)
int index () const
 Variable (const Problem &problem, int min, int max, int row, int column)
 Variable (const Problem &problem, const vector< csp::values::Int > &values, int row, int column)
int row () const
int column () const
virtual wstring color () const
virtual wstring textColor () const
virtual wstring shape () const
virtual void setBackdoorStatus (bool status)
virtual void setBackdoorKeyStatus (bool status)
virtual void setBranchingStatus (bool status)
 Variable (const Problem &problem, int min, int max, int index)
int index () const
virtual wstring color () const
virtual wstring textColor () const
virtual wstring shape () const
virtual void setBackdoorStatus (bool status)
virtual void setBackdoorKeyStatus (bool status)
virtual void setBranchingStatus (bool status)
 Variable (const Problem &problem, const int min, const int max)
double weight () const
double minWeight () const
double maxWeight () const
Value & value () const
virtual wostream & print (wostream &wos) const
virtual wstring color () const
virtual wstring textColor () const
virtual wstring shape () const
virtual void setBackdoorStatus (bool status)
virtual void setBackdoorKeyStatus (bool status)
virtual void setBranchingStatus (bool status)
 Variable (const Problem &problem, const vector< csp::values::Int > &array, const wstring &name)
virtual wstring name () const
int index () const
void setColor (const wstring &color)
virtual wstring color () const
virtual wstring textColor () const
virtual wstring shape () const
virtual void setBackdoorStatus (bool status)
virtual void setBackdoorKeyStatus (bool status)
virtual void setBranchingStatus (bool status)
 Variable (const Problem &problem)
virtual ~Variable ()
 Destructor.
id_t id () const
 Return the variable's id.
virtual wstring name () const
virtual wstring color () const
virtual wstring textColor () const
virtual wstring shape () const
void setId (id_t id)
 Set the variable's id.
virtual void setBackdoorStatus (bool)
virtual void setBackdoorKeyStatus (bool)
virtual void setBranchingStatus (bool)
const Problem & problem () const
 Return the problem to which this variable belongs to.
constraint_iterator add (Constraint &constraint)
 Add a new constraint to this variable.
void remove (Constraint &constraint, bool recursive=false)
 Remove constraint `c' from this variable.
size_t values () const
 Return the number of values in the domain of the variable.
Value & value () const
Value & value (id_t id) const
Domain::iterator beginValues ()
 Return an iterator to the first value.
Domain::iterator endValues ()
 Return an iterator past the last value.
Domain::const_iterator beginValues () const
 Return an iterator to the first value.
Domain::const_iterator endValues () const
 Return an iterator past the last value.
constraint_iterator beginConstraints () const
 Return an iterator to the first active constraint.
constraint_iterator endConstraints () const
 Return an iterator past the last active constraint.
constraint_iterator beginInactiveConstraints () const
 Return an iterator to the first inactive constraint.
constraint_iterator endInactiveConstraints () const
 Return an iterator past the last inactive constraint.
Domain & domain ()
 Get the domain of a variable.
const Domain & domain () const
 Get the domain of a variable.
size_t constraints () const
 Return the number of active constraints in this variable.
size_t inactiveConstraints () const
 Return the number of inactive constraints in this variable.
size_t hiddenConstraints () const
 Return the number of hidden constraints in this variable.
size_t degree () const
ulonglong weightedDegree () const
void incrementDomainWipeouts ()
 Increment the number of domain wipe-outs for this variable.
ulonglong domainWipeouts () const
 Return the number of domain wipe-outs for this variable.
bool isPast () const
 Return `true' if this is a `past' variable.
bool isCurrent () const
 Return `true' if this is a `current' variable.
bool isFuture () const
 Return `true' if this is a `future' variable.
bool isInstantiated () const
 Return `true' if the variable is instantiated.
int instantiationDepth () const
 Return the instantiation depth.
const vector< Domain * > & diffs () const
void saveDiffs ()
void restoreDiffs ()
void postponeDiffs ()
void addDiffs (Domain &diffs)
Value * findSupport (Value &value, const Constraint &constraint, Variable &pair)
size_t prune (const Constraint &constraint, Domain &diffs, bool consistent=false)
void sortDomain ()
virtual wostream & print (wostream &wos) const
 Print the variable at the given stream.

Protected Member Functions

void add (Value &v)
 Add a new value to this variable's domain.
void remove (Value &v)
 Remove a value from this variable's domain.

Friends

class Decomposition
class Problem
 The Problem class needs access to some of the Variable's internals.
CSP_API wostream & operator<< (wostream &wos, const Variable &variable)
 Print the variable at the given stream.

Detailed Description

The super class of all the CSP variables.

Constructor & Destructor Documentation

Variable::Variable (  const Problem &  problem  ) 
 

Create a variable object.

Parameters:
problem the problem in which the variable is involved.
name the name of the variable.

Member Function Documentation

void Variable::addDiffs (  Domain &  diffs  ) 
 

This method does the actual saving of the domain of the variable. It should be called only when the variable is actually modified, to avoid unnecessary save/restore operations. The `domain' passed as an argument contains the values that have been removed from the variable's domain in the current modification. We only save the difference between the old state of the domain and the new one, to keep memory usage within reasonable limits. `addDiffs()' can be called multiple times - the values are merged with the previously saved values. `addDiffs()' will _move_ the values from the domain specified as a parameter to its stack of removed values.

Parameters:
diffs a domain containing the values removed.

virtual wstring Variable::color (   )  const [inline, virtual]
 

Return the variable's drawing color, if the derived class decided to assign it one. The default color is "gray".

Returns:
the variable's color.

size_t Variable::degree (   )  const [inline]
 

Return the current degree of this variable. Note that this is the same as constraints(), since the degree of the variable is given by the number of active constraints related to it.

const vector<Domain*>& Variable::diffs (   )  const [inline]
 

Return the set of values that have been removed from the current variable (per depth).

Value * Variable::findSupport (  Value &  value,
const Constraint &  constraint,
Variable &  pair
) 
 

Given a value from the domain of this variable and a constraint in which this variable is involved, this function looks for a support on that constraint. This is done by temporary setting the domain of this variable to `value' and the domain of its pair, in turn, to all its values.

Parameters:
value the value requiring a support.
constraint the constraint related to this variable.
pair the pair of this variable on the given constraint, for efficiency reasons.
Returns:
pointer to a value in pair's domain supporting `value', or 0 if no such value exists.

virtual wstring Variable::name (   )  const [virtual]
 

Return the variable's name, if the derived class decided to assign it one. The default is to return the variable's id as a string.

Returns:
the variable's name.

void Variable::postponeDiffs (   ) 
 

Postpone the latest saved differences for the domain of this variable. This usually happens when the algorithm can succesfully propagate the constraints on a variable. The differencess are merged into the previous level differences on the stack of saved domain differences.

size_t Variable::prune (  const Constraint &  constraint,
Domain &  diffs,
bool  consistent = false
) 
 

Move from the domain of the variable into `diffs' all the values that are `consistent' or `inconsistent' with the given constraint. Beware that it is possible for this method to empty the domain of the current variable. Such a situation is normal and should be taken care of by the calling method.

Parameters:
constraint the constraint to be checked.
diffs the `Domain' object where changes should be stored.
consistent `true' if you want to prune consistent values, `false' otherwise.
Returns:
the number of values removed (i.e. diffs.size()).

void Variable::restoreDiffs (   ) 
 

Restore the domain of the variable to the domain it had at the time `saveDiffs()' was called for it.

void Variable::saveDiffs (   )  [inline]
 

This method doesn't actually save the current state of the variable, it just records the fact that the corresponding `restoreDiffs()' call should restore the domain of the variable to the state it was in at the time `saveDiffs()' was called. Note however that this should not be thought of as a general mechanism for saving/restoring variables - it is just a mechanism that allows the library to control the modifications done by filters to the domains of uninstantiated variables.

The basic idea is this. In the decomposition algorithm a variable is selected according to the heuristics in place and instantiated, then the state of all the remaining (uninstantiated) variables is saved. The next thing to do is check whether or not the instantiation breaks any constraint, so the filter gets called. It saves the current state of all the uninstantiated variables and then attempts to restore consistency by trying to eliminate all the values that are no longer supported, potentially modifying the domains of the variables.

If the filter fails to restore consistency, then it undoes all the changes to the domains of the variables. However, if the filter succeeds, the restauration of the domain of the variables has to be postponed until the resulting subproblem is solved because the subproblem has to be solved with the filter modifications in place.

Note that the mechanism for saving/restoring/postponing the state of variables is capable of figuring out the exact state that needs to be restored. That is, a call to restoreDiffs() does not necessarily match a call to saveDiffs() - it can restore the changes performed by a number of addDiffs()s at different depths, such that the state matches the previous state at that depth. That's because a filter can modify a variable several times during a single call, since the values of a variable can be inconsistent with different constraints.

virtual void Variable::setBackdoorKeyStatus (  bool   )  [inline, virtual]
 

Hook to allow the decomposition to mark this variable as a backdoor key. This can be used to change the variable's graphical attributes for more useful graphs. The Decomposition object calls this hook to update the variable's status whenever a new solution is found.

Parameters:
status `true' if the variable is a backdoor key, `false' otherwise.

virtual void Variable::setBackdoorStatus (  bool   )  [inline, virtual]
 

Hook to allow the decomposition to mark this variable as belonging to a backdoor. This can be used to change the variable's graphical attributes for more useful graphs. The Decomposition object calls this hook to update the variable's status whenever a new solution is found.

Parameters:
status `true' if the variable is a backdoor, `false' otherwise.

virtual void Variable::setBranchingStatus (  bool   )  [inline, virtual]
 

Hook to allow the decomposition to mark this variable as a branching variable. This can be used to change the variable's graphical attributes for more useful graphs. The Decomposition object calls this hook to update the variable's status whenever a new solution is found.

Parameters:
status `true' if the variable is a branching variable, `false' otherwise.

virtual wstring Variable::shape (   )  const [inline, virtual]
 

Return the variable's drawing shape, if the derived class decided to assign it one. The default color is "ellipse".

Returns:
the variable's shape.

void Variable::sortDomain (   )  [inline]
 

Sort the domain of the variable in increasing order of ID of the values.

virtual wstring Variable::textColor (   )  const [inline, virtual]
 

Return the variable's text color, if the derived class decided to assign it one. The default color is "black".

Returns:
the variable's text color.

Value & Variable::value (  id_t  id  )  const
 

Return the value with the given id.

Parameters:
id the id of the value to be looked for.
Returns:
a reference to the value found.

Value& Variable::value (   )  const [inline]
 

Return the value of the variable. Should only be used after the variable has been instantiated.

ulonglong Variable::weightedDegree (   )  const
 

Return the current weighted degree of this variable. The weight of a constraint is 1 plus the number of times that constraint has failed. The weighted degree of a variable is the sum of all the weights of all the constraints involving that variable and at least one other unassigned variable.

Friends And Related Function Documentation

friend class Decomposition [friend]
 

We give the Decomposition class access to this, to simplify the interface. This used to be part of Decomposition anyway, and it is only used there.

The documentation for this class was generated from the following files:
Generated on Wed May 25 12:21:23 2005 for csp.kdevelop by  doxygen 1.3.9.1