Filter Class Reference

#include <Filter.h>

Inheritance diagram for Filter:

List of all members.

Public Member Functions
	Filter (const wstring &fullName, const wstring &shortName, Problem &problem, Retraction &retraction)
const wstring	name () const
	Return the filter's name.
const wstring &	fullName () const
	Return the filter's full name.
const wstring &	shortName () const
	Return the filter's short name.
const Problem &	problem () const
	Return the problem being filtered.
Problem &	problem ()
	Return the problem being filtered.
const Retraction &	retraction () const
Retraction &	retraction ()
void	recordDomainChange (Variable &victim, Variable &aggressor)
void	recordFailure (Constraint &constraint, Variable &victim, Variable &aggressor)
void	updateValueFailures (Domain &diffs)
virtual bool	restoresArcConsistency () const =0
bool	subProblemIsArcConsistent (bool debugging) const
virtual bool	isDummy () const
virtual bool	propagate (const vlist_type &uninstantiatedVariables, const vlist_type &modifiedVariables, const bool keepChanges=true)=0
const hash_set< const Variable * > &	prunedVariables () const
virtual bool	init (const vlist_type &, bool=true)
virtual void	done ()
virtual void	restrict (const vlist_type &)
virtual void	unrestrict ()
virtual wostream &	print (wostream &wos) const
Static Public Member Functions
void	saveState (const list< Variable * > &variables)
void	restoreState (const list< Variable * > &variables)
void	postponeState (const list< Variable * > &variables)
Protected Member Functions
void	clearPrunedVariables ()
	Clear the list of pruned variables. Call this early in propagate().
Protected Attributes
Problem &	m_problem
	The problem at hand.
Retraction &	m_retraction
	The retraction to which the filter reports failures.
Friends
CSP_API wostream &	operator<< (wostream &wos, const Filter &filter)

---

Detailed Description

The super class of all the filters.

---

Constructor & Destructor Documentation

Filter::Filter (  const wstring &  fullName, const wstring &  shortName, Problem &  problem, Retraction &  retraction )  [inline]

Constructor for various filters. Parameters: name  the name of the variation. problem  the problem to be solved. retraction  the retraction method to be used.

---

Member Function Documentation

virtual void Filter::done (   )  [inline, virtual]

Clean up the filter. This method can be overwritten if its default implementation (which doesn't do anything) is not suitable for a particular filter, but you should call it anyway from the derived class' done() method. Reimplemented in AC1, AC2000, AC2001, AC3, AC3d, AC3x, AC4, AC8, and FP.

virtual bool Filter::init (  const vlist_type &  , bool  = true )  [inline, virtual]

Initializate the filter. Obviously, the search can be restarted and we need to reinitialize the filter every time that happens. This method can be overwritten if its default implementation is not suitable for a particular filter, but you should call it anyway from the derived class' init() method. Parameters: uninstantiatedVariables  the list of uninstantiated variables. propagate  `true' if propagate() should be called. Returns: `true' if the initialization succeeded, `false' otherwise. Reimplemented in AC1, AC2000, AC2001, AC3, AC3d, AC3x, AC4, AC8, and FP.

virtual bool Filter::isDummy (   )  const [inline, virtual]

Return `true' if the filter performs no consistency checks whatsoever. This is important because it can lead the search to a fringe node even when a solution has not been found. Reimplemented in Dummy.

void Filter::postponeState (  const list< Variable * > &  variables  )  [static]

Postpone restauration of the state (current domain) of all the variables in the given list. That list contains all the variables that presumably the filter could have modified. Parameters: variables  the list of variables for which the state is to be postponed.

virtual wostream& Filter::print (  wostream &  wos  )  const [inline, virtual]

Print algorithm information at the given stream. Parameters: wos  the output stream to print to. Returns: the given stream. Reimplemented in AC3.

virtual bool Filter::propagate (  const vlist_type &  uninstantiatedVariables, const vlist_type &  modifiedVariables, const bool  keepChanges = true )  [pure virtual]

This method does the actual constraint propagation. The `modifiedVariables' list has a crucial role in the structure of a filter. Forward pruning removes from the domains of the uninstantiated variables all the values inconsistent with the variables that have just been instantiated/modified (which should be in `modifiedVariables'). Backward checking works by ensuring that the variables that have just been instantiated are consistent with all the variables instantiated before it. Without `modifiedVariables', none of these filters would work. Even more advanced filters (like AC-3) might use it, for instance if it is possible to restore arc consistency only locally. Note that propagate() should check constraints between instantiated variables too, if those instantiated variables are marked as current. See Decomposition::autoSelectVariables() for details. Variables whose domains get reduced to a single value in propagate() will not be considered instantiated until Decomposition::decompose() is called recursively. This function shouldn't attempt to modified instantiated variables. They can inspect them, their domains and/or constraints, but it's not allowed to change them. Finally, if propagate() is called and all the variables have their domains reduced to a single value, the filter should be able to say whether or not we have a solution. FIXME: really? This should not be a guarantee in the filter, but rather in the way it is used. Parameters: uninstantiatedVariables  the list of variables that are not yet instantiated. modifiedVariables  the list of variables whose domain has been modified since this method has last been called; the list cannot be NULL or empty, or contain NULL `Variable' pointers. keepChanges  if `false', propagate will restore the domains of all variables regardless of whether or not the propagation was successful. This can be useful when a decomposition just wants to know whether or not a successful propagation would be possible, w/o actually causing the changes immediately. Returns: `true' on success, `false' on failure. Implemented in AC1, AC2000, AC2001, AC3, AC3d, AC3x, AC4, AC8, BC, BM, Dummy, FP, and RP.

const hash_set<const Variable*>& Filter::prunedVariables (   )  const [inline]

Return the list of variables whose domains have been modified in the most recent call to propagate(). Returns: the list of variables whose domains have been modified in the most recent call to propagate().

void Filter::recordDomainChange (  Variable &  victim, Variable &  aggressor )

Record a domain change. Report it to the retraction, if any. Parameters: victim  the variable whose domain has been changed. aggressor  the variable that caused the domain change.

void Filter::recordFailure (  Constraint &  constraint, Variable &  victim, Variable &  aggressor )

Record a filter failure. Report it to the retraction, if any. Also update the domain wipe-out counter associated with `victim'. Parameters: constraint  the constraint causing the failure. victim  the variable whose domain has been wiped out. aggressor  the variable that caused the domain wipe-out.

virtual bool Filter::restoresArcConsistency (   )  const [pure virtual]

Return `true' if this is an `AC' filter, i.e. it always restores full arc consistency. This is a very important characteristic of a filter, mainly because the decomposition needs to know whether or not the filter does that. If the filter restores arc consistency, the decomposition can deactivate constraints that connect current variables with past ones (thus avoiding unnecessary constraint checks). To better understand the problem, you have to remember that the library allows the decomposition to modify more than one variable at a given depth. That is, there is no guarantee that there will be a unique `current' variable at any given depth. One could presumably write a decomposition where at every depth it instantiates an arbitrary number of variables. The reason backward constraints cannot be deactivated in filters that do not restore full arc consistency has to do with the case when more than one variable is modified at a given depth (and the filter is ran with `modified' containing more than one variable. Take `forward pruning' for an example. In theory, it is a forward filter, so we don't need to look back at the past variables. But if more than one variable is modified at a given depth, then we can come up with a small example where forward prunning would allow the decomposition to add to the partial solution instantiations that are not consistent with each other (even though they are consistent with all the past and future variables). This can happen for instance if at depth `d' we select variable X and Y, run the `forward pruning' filter and if that succedes, we add X and Y to the partial solution. If X and Y are indirectly linked one iteration through (X Y) might not make the subproblem consistent. `backward checking' works by verifying after each instantiation that the instantiation of the currently selected variable is consistent with the instantiations of all the previously instantiated variables. Thus, if we remove the back constraints, `backward checking' will not work. `backward checking' and `forward pruning' are not `AC' filters. filters because they do not restore arc consistency. Implemented in AC1, AC2000, AC2001, AC3, AC3d, AC3x, AC4, AC8, BC, BM, Dummy, FP, and RP.

void Filter::restoreState (  const list< Variable * > &  variables  )  [static]

Restore the state (current domain) of all the variables in the given list. That list contains all the variables that presumably the filter could have modified. Parameters: variables  the list of variables for which the state is to be restored.

virtual void Filter::restrict (  const vlist_type &   )  [inline, virtual]

Notify the filter that the decomposition decided to restrict the problem to a certain subset of variables (in addition to the variables that have already been instantiated, of course). Parameters: variables  the set of uninstantiated variables to restrict the search to.

Retraction& Filter::retraction (   )  [inline]

Return the retraction method to which the filter reports domain changes and failures.

const Retraction& Filter::retraction (   )  const [inline]

Return the retraction method to which the filter reports domain changes and failures.

void Filter::saveState (  const list< Variable * > &  variables  )  [static]

Save the state (current domain) of all the variables in the given list. That list contains all the variables that presumably the filter can modify. Parameters: variables  the list of variables for which the state is to be saved.

bool Filter::subProblemIsArcConsistent (  bool  debugging  )  const

Return `true' if the current subproblem is arc consistent. Parameters: debugging  set to `true' if called in debug-only code so that constraints that are not normally called in production code are not counted.

virtual void Filter::unrestrict (   )  [inline, virtual]

Notify the filter that the effects of the latest call to `restrict()' are to be undone.

void Filter::updateValueFailures (  Domain &  diffs  )

Update the number of failures for all the values involved in the constraint check that caused the filter to fail. Their presence in the domain of their corresponding variable was insufficient to keep the problem consistent. Parameters: diffs  the values that caused trouble.

---

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

• Filter.h
• src/kernel/Filter.cc

---