    001package net.sf.cpsolver.ifs.dbt;
    002
    003import java.util.HashSet;
    004import java.util.Set;
    005
    006import net.sf.cpsolver.ifs.extension.MacPropagation;
    007import net.sf.cpsolver.ifs.model.Neighbour;
    008import net.sf.cpsolver.ifs.model.Value;
    009import net.sf.cpsolver.ifs.model.Variable;
    010import net.sf.cpsolver.ifs.solution.Solution;
    011import net.sf.cpsolver.ifs.solver.Solver;
    012import net.sf.cpsolver.ifs.solver.SolverListener;
    013import net.sf.cpsolver.ifs.util.DataProperties;
    014
    015/**
    016 * Maintenance of arc consistency in dynamic backtracking. <br>
    017 * <br>
    018 * The difference between {@link MacPropagation} and this DBT propagation is
    019 * that all not-assigned values of an assigned variable are marked as nogood.
    020 * Also, when a dead end is reached, unassignment or failure takes place. <br>
    021 * <br>
    022 * This IFS solver extension is to be used only in case of dynamic backtracking
    023 * and it has no parameters.
    024 *
    025 *
    026 * @version IFS 1.2 (Iterative Forward Search)<br>
    027 *          Copyright (C) 2006 - 2010 Tomáš Müller<br>
    028 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    029 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    030 * <br>
    031 *          This library is free software; you can redistribute it and/or modify
    032 *          it under the terms of the GNU Lesser General Public License as
    033 *          published by the Free Software Foundation; either version 3 of the
    034 *          License, or (at your option) any later version. <br>
    035 * <br>
    036 *          This library is distributed in the hope that it will be useful, but
    037 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    038 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    039 *          Lesser General Public License for more details. <br>
    040 * <br>
    041 *          You should have received a copy of the GNU Lesser General Public
    042 *          License along with this library; if not see <http://www.gnu.org/licenses/>.
    043 *
    044 */
    045public class DbtPropagation<V extends Variable<V, T>, T extends Value<V, T>> extends MacPropagation<V, T> implements
    046        SolverListener<V, T> {
    047    private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(DbtPropagation.class);
    048
    049    /**
    050     * Constructor. No parameter is taken from properties.
    051     */
    052    public DbtPropagation(Solver<V, T> solver, DataProperties properties) {
    053        super(solver, properties);
    054        solver.addSolverListener(this);
    055    }
    056
    057    /**
    058     * Propagation takes place every time a value is assigned to a variable. <br>
    059     * <br>
    060     * <li>Prints a warning if the value is nogood (should not never happen),
    061     * <li>sets all other values of the variable to nogood (explanation is the
    062     * assigned value itself), <li>runs propagation.
    063     *
    064     * @see MacPropagation#propagate(Variable)
    065     */
    066    @Override
    067    public void afterAssigned(long iteration, T value) {
    068        iIteration = iteration;
    069        if (!isGood(value)) {
    070            sLogger.warn(value.variable().getName() + " = " + value.getName() + " -- not good value assigned (noGood:"
    071                    + noGood(value) + ")");
    072            setGood(value);
    073        }
    074
    075        Set<T> noGood = new HashSet<T>(1);
    076
    077        noGood.add(value);
    078        for (T anotherValue : value.variable().values()) {
    079            if (anotherValue.equals(value) || !isGood(anotherValue))
    080                continue;
    081            setNoGood(anotherValue, noGood);
    082        }
    083        propagate(value.variable());
    084    }
    085
    086    /**
    087     * Undo propagation when a value is unassigned. <br>
    088     * <br>
    089     * <li>Prints an error if the value is nogood (should not never happen), <li>
    090     * runs propagation undo.
    091     *
    092     * @see MacPropagation#undoPropagate(Variable)
    093     */
    094    @Override
    095    public void afterUnassigned(long iteration, T value) {
    096        iIteration = iteration;
    097        if (!isGood(value)) {
    098            sLogger.error(value.variable().getName() + " = " + value.getName()
    099                    + " -- not good value unassigned (noGood:" + noGood(value) + ")");
    100        }
    101        undoPropagate(value.variable());
    102    }
    103
    104    /**
    105     * If no variable is selected (all variables are assinged), unassign the
    106     * last assigned variable. <br>
    107     * <br>
    108     * Do not allow to select an assigned variable. <br>
    109     * <br>
    110     * If no variable is selected (because all variables are assigned, see
    111     * {@link DbtVariableSelection}):
    112     * <ul>
    113     * <li>find the last assigned variable and
    114     * <li>unassign it (explanation is a union of assignments of all other
    115     * variables).
    116     * </ul>
    117     *
    118     * @see DbtVariableSelection#selectVariable(Solution)
    119     */
    120    @Override
    121    public boolean variableSelected(long iteration, V variable) {
    122        if (variable == null) {
    123            sLogger.debug("No variable selected -> backtrack.");
    124            V lastVariable = null;
    125
    126            for (V var : getModel().assignedVariables()) {
    127                if (lastVariable == null
    128                        || lastVariable.getAssignment().lastAssignmentIteration() < var.getAssignment()
    129                                .lastAssignmentIteration()) {
    130                    lastVariable = var;
    131                }
    132            }
    133            if (lastVariable == null) {
    134                sLogger.error("No assignment -> fail");
    135                getSolver().stopSolver();
    136                return false;
    137            }
    138            sLogger.debug("Unassign:" + lastVariable.getName());
    139            Set<T> noGoods = new HashSet<T>();
    140
    141            for (V var : getModel().assignedVariables()) {
    142                if (!var.equals(lastVariable)) {
    143                    noGoods.add(var.getAssignment());
    144                }
    145            }
    146            T value = lastVariable.getAssignment();
    147
    148            lastVariable.unassign(iteration);
    149            setNoGood(value, noGoods);
    150            return false;
    151        }
    152        if (variable.getAssignment() != null) {
    153            sLogger.error("Assigned value selected -- not supported by DBT.");
    154            return false;
    155        }
    156        return true;
    157    }
    158
    159    /**
    160     * If no value is selected (because of a dead end), make some unassignments. <br>
    161     * <br>
    162     * If no value is selected (e.g., because the selected variable has all
    163     * values marked as nogood, see {@link DbtValueSelection}),
    164     * <ul>
    165     * <li>compute a union of explanations of all values,
    166     * <ul>
    167     * <li>if it is empty fail (inconsistency is found),
    168     * </ul>
    169     * <li>otherwise pick the last assigned variable from the computed union of
    170     * explanation and unassign it
    171     * <ul>
    172     * (explanation for that is the computed union of explanations without the
    173     * last assignment).
    174     * </ul>
    175     * </ul>
    176     *
    177     * @see DbtVariableSelection#selectVariable(Solution)
    178     */
    179    @Override
    180    public boolean valueSelected(long iteration, V variable, T value) {
    181        if (variable != null && value == null) {
    182            Set<T> noGoods = new HashSet<T>();
    183
    184            for (T val : variable.values()) {
    185                if (noGood(val) != null) {
    186                    noGoods.addAll(noGood(val));
    187                }
    188            }
    189            if (noGoods.isEmpty()) {
    190                sLogger.debug("Fail");
    191                getSolver().stopSolver();
    192                return false;
    193            }
    194            V lastVariable = null;
    195
    196            for (T val : noGoods) {
    197                V var = val.variable();
    198
    199                if (lastVariable == null
    200                        || lastVariable.getAssignment().lastAssignmentIteration() < var.getAssignment()
    201                                .lastAssignmentIteration()) {
    202                    lastVariable = var;
    203                }
    204            }
    205            T assignment = lastVariable.getAssignment();
    206
    207            noGoods.remove(assignment);
    208            lastVariable.unassign(iteration);
    209            setNoGood(assignment, noGoods);
    210        }
    211        return true;
    212    }
    213
    214    @Override
    215    public boolean neighbourSelected(long iteration, Neighbour<V, T> neighbour) {
    216        return true;
    217    }
    218}