BM Class Reference

#include <BM.h>

Inheritance diagram for BM:

List of all members.

Public Member Functions
	BM (Problem &problem, Retraction &retraction)
virtual bool	restoresArcConsistency () const
	FIXME: !?
virtual bool	propagate (const vlist_type &uninstantiatedVariables, const vlist_type &modifiedVariables, const bool keepChanges=true)

---

Detailed Description

The back marking filter.

See also:

Filter

---

Member Function Documentation

bool BM::propagate (  const vlist_type &  uninstantiatedVariables, const vlist_type &  modifiedVariables, const bool  keepChanges = true )  [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. Implements Filter.

---

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

• BM.h
• BM.cc

---