001    package net.sf.cpsolver.ifs.dbt;
002    
003    import java.util.HashSet;
004    import java.util.Set;
005    
006    import net.sf.cpsolver.ifs.extension.MacPropagation;
007    import net.sf.cpsolver.ifs.model.Neighbour;
008    import net.sf.cpsolver.ifs.model.Value;
009    import net.sf.cpsolver.ifs.model.Variable;
010    import net.sf.cpsolver.ifs.solution.Solution;
011    import net.sf.cpsolver.ifs.solver.Solver;
012    import net.sf.cpsolver.ifs.solver.SolverListener;
013    import 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 Tomas Muller<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     */
045    public 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    }