    001    package ifs.dbt;
    002
    003
    004    import ifs.extension.*;
    005    import ifs.model.*;
    006    import ifs.solver.*;
    007    import ifs.util.*;
    008    import java.util.*;
    009
    010    /**
    011     * Maintenance of arc consistency in dynamic backtracking.
    012     * <br><br>
    013     * The difference between {@link MacPropagation} and this DBT propagation is that all not-assigned values
    014     * of an assigned variable are marked as nogood. Also, when a dead end is reached, unassignment or failure
    015     * takes place.
    016     * <br><br>
    017     * This IFS solver extension is to be used only in case of dynamic backtracking and it has no parameters.
    018     *
    019     *
    020     * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomáš Müller</a>
    021     * @version 1.0
    022     */
    023    public class DbtPropagation extends MacPropagation implements SolverListener {
    024        private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(DbtPropagation.class);
    025
    026        /**
    027         * Constructor. No parameter is taken from properties.
    028         */
    029        public DbtPropagation(Solver solver, DataProperties properties) {
    030            super(solver, properties);
    031            solver.addSolverListener(this);
    032        }
    033
    034        /**
    035         * Propagation takes place every time a value is assigned to a variable.
    036         * <br><br>
    037         * <li>Prints a warning if the value is nogood (should not never happen),
    038         * <li>sets all other values of the variable to nogood (explanation is the assigned value itself),
    039         * <li>runs propagation.
    040         *
    041         * @see MacPropagation#propagate(Variable)
    042         */
    043        public void afterAssigned(long iteration, Value value) {
    044            iIteration = iteration;
    045            if (!isGood(value)) {
    046                sLogger.warn(value.variable().getName()+" = "+value.getName()+" -- not good value assigned (noGood:"+noGood(value)+")");
    047                setGood(value);
    048            }
    049
    050            HashSet noGood = new HashSet(1);
    051
    052            noGood.add(value);
    053            for (Enumeration i = value.variable().values().elements(); i.hasMoreElements();) {
    054                Value anotherValue = (Value) i.nextElement();
    055                if (anotherValue.equals(value) || !isGood(anotherValue)) continue;
    056                setNoGood(anotherValue, noGood);
    057            }
    058            propagate(value.variable());
    059        }
    060
    061        /**
    062         * Undo propagation when a value is unassigned.
    063         * <br><br>
    064         * <li>Prints an error if the value is nogood (should not never happen),
    065         * <li>runs propagation undo.
    066         *
    067         * @see MacPropagation#undoPropagate(Variable)
    068         */
    069        public void afterUnassigned(long iteration, Value value) {
    070            iIteration = iteration;
    071            if (!isGood(value)) {
    072                sLogger.error(value.variable().getName()+" = "+value.getName()+" -- not good value unassigned (noGood:"+noGood(value)+")");
    073            }
    074            undoPropagate(value.variable());
    075        }
    076
    077        /**
    078         * If no variable is selected (all variables are assinged), unassign the last assigned variable.
    079         * <br><br>
    080         * Do not allow to select an assigned variable.
    081         * <br><br>
    082         * If no variable is selected (because all variables are assigned, see {@link DbtVariableSelection}):
    083         * <ul>
    084         * <li> find the last assigned variable and
    085         * <li> unassign it (explanation is a union of assignments of all other variables).
    086         * </ul>
    087         *
    088         * @see DbtVariableSelection#selectVariable(Solution)
    089         */
    090        public boolean variableSelected(long iteration, Variable variable) {
    091            if (variable == null) {
    092                sLogger.debug("No variable selected -> backtrack.");
    093                Variable lastVariable = null;
    094
    095                for (Enumeration i = getModel().assignedVariables().elements(); i.hasMoreElements();) {
    096                    Variable var = (Variable) i.nextElement();
    097
    098                    if (lastVariable == null || lastVariable.getAssignment().lastAssignmentIteration()<var.getAssignment().lastAssignmentIteration()) {
    099                        lastVariable = var;
    100                    }
    101                }
    102                if (lastVariable == null) {
    103                    sLogger.error("No assignment -> fail");
    104                    getSolver().stopSolver();
    105                    return false;
    106                }
    107                sLogger.debug("Unassign:" + lastVariable.getName());
    108                HashSet noGoods = new HashSet();
    109
    110                for (Enumeration i = getModel().assignedVariables().elements(); i.hasMoreElements();) {
    111                    Variable var = (Variable) i.nextElement();
    112
    113                    if (!var.equals(lastVariable)) {
    114                        noGoods.add(var.getAssignment());
    115                    }
    116                }
    117                Value value = lastVariable.getAssignment();
    118
    119                lastVariable.unassign(iteration);
    120                setNoGood(value, noGoods);
    121                return false;
    122            }
    123            if (variable.getAssignment() != null) {
    124                sLogger.error("Assigned value selected -- not supported by DBT.");
    125                return false;
    126            }
    127            return true;
    128        }
    129
    130        /**
    131         * If no value is selected (because of a dead end), make some unassignments.
    132         * <br><br>
    133         * If no value is selected
    134         * (e.g., because the selected variable has all values marked as nogood, see {@link DbtValueSelection}),
    135         * <ul>
    136         * <li> compute a union of explanations of all values,
    137         * <ul><li> if it is empty fail (inconsistency is found),</ul>
    138         * <li> otherwise pick the last assigned variable from the computed union of explanation and unassign it
    139         * <ul>(explanation for that is the computed union of explanations without the last assignment).</ul>
    140         * </ul>
    141         *
    142         * @see DbtVariableSelection#selectVariable(Solution)
    143         */
    144        public boolean valueSelected(long iteration, Variable variable, Value value) {
    145            if (variable != null && value == null) {
    146                HashSet noGoods = new HashSet();
    147
    148                for (Enumeration i = variable.values().elements(); i.hasMoreElements();) {
    149                    Value val = (Value) i.nextElement();
    150                    if (noGood(val) != null) {
    151                        noGoods.addAll(noGood(val));
    152                    }
    153                }
    154                if (noGoods.isEmpty()) {
    155                    sLogger.debug("Fail");
    156                    getSolver().stopSolver();
    157                    return false;
    158                }
    159                Variable lastVariable = null;
    160
    161                for (Iterator i = noGoods.iterator(); i.hasNext();) {
    162                    Value val = (Value) i.next();
    163                    Variable var = val.variable();
    164
    165                    if (lastVariable == null || lastVariable.getAssignment().lastAssignmentIteration()<var.getAssignment().lastAssignmentIteration()) {
    166                        lastVariable = var;
    167                    }
    168                }
    169                Value assignment = lastVariable.getAssignment();
    170
    171                noGoods.remove(assignment);
    172                lastVariable.unassign(iteration);
    173                setNoGood(assignment, noGoods);
    174            }
    175            return true;
    176        }
    177    }