    001package org.cpsolver.ifs.extension;
    002
    003import java.util.ArrayList;
    004import java.util.Collection;
    005import java.util.HashSet;
    006import java.util.HashMap;
    007import java.util.Iterator;
    008import java.util.LinkedList;
    009import java.util.List;
    010import java.util.Map;
    011import java.util.Queue;
    012import java.util.Set;
    013
    014import org.cpsolver.ifs.assignment.Assignment;
    015import org.cpsolver.ifs.assignment.context.AssignmentContext;
    016import org.cpsolver.ifs.assignment.context.ExtensionWithContext;
    017import org.cpsolver.ifs.model.Constraint;
    018import org.cpsolver.ifs.model.Value;
    019import org.cpsolver.ifs.model.Variable;
    020import org.cpsolver.ifs.solver.Solver;
    021import org.cpsolver.ifs.util.DataProperties;
    022import org.cpsolver.ifs.util.Progress;
    023
    024
    025/**
    026 * MAC propagation. <br>
    027 * <br>
    028 * During the arc consistency maintenance, when a value is deleted from a
    029 * variable's domain, the reason (forming an explanation) can be computed and
    030 * attached to the deleted value. Once a variable (say Vx with the assigned
    031 * value vx) is unassigned during the search, all deleted values which contain a
    032 * pair Vx = vx in their explanations need to be recomputed. Such value can be
    033 * either still inconsistent with the current (partial) solution (a different
    034 * explanation is attached to it in this case) or it can be returned back to its
    035 * variable's domain. Arc consistency is maintained after each iteration step,
    036 * i.e., the selected assignment is propagated into the not yet assigned
    037 * variables. When a value vx is assigned to a variable Vx, an explanation Vx !=
    038 * vx' &#8592; Vx = vx is attached to all values vx' of the variable Vx,
    039 * different from vx. <br>
    040 * <br>
    041 * In the case of forward checking (only constraints going from assigned
    042 * variables to unassigned variables are revised), computing explanations is
    043 * rather easy. A value vx is deleted from the domain of the variable Vx only if
    044 * there is a constraint which prohibits the assignment Vx=vx because of the
    045 * existing assignments (e.g., Vy = vy, Vz = vz). An explanation for the
    046 * deletion of this value vx is then Vx != vx &#8592; (Vy = vy &amp; ... Vz = vz),
    047 * where Vy = vy &amp; ... Vz = vz are assignments contained in the prohibiting
    048 * constraint. In case of arc consistency, a value vx is deleted from the domain
    049 * of the variable Vx if there is a constraint which does not permit the
    050 * assignment Vx = vx with other possible assignments of the other variables in
    051 * the constraint. This means that there is no support value (or combination of
    052 * values) for the value vx of the variable Vx in the constraint. An explanation
    053 * is then a union of explanations of all possible support values for the
    054 * assignment Vx = vx of this constraint which were deleted. The reason is that
    055 * if one of these support values is returned to its variable's domain, this
    056 * value vx may be returned as well (i.e., the reason for its deletion has
    057 * vanished, a new reason needs to be computed). <br>
    058 * <br>
    059 * As for the implementation, we only need to enforce arc consistency of the
    060 * initial solution and to extend unassign and assign methods. Procedure
    061 * {@link MacPropagation#afterAssigned(Assignment, long, Value)} enforces arc consistency of
    062 * the solution with the selected assignment variable = value and the procedure
    063 * {@link MacPropagation#afterUnassigned(Assignment, long, Value)} "undoes" the assignment
    064 * variable = value. It means that explanations of all values which were deleted
    065 * and which contain assignment variable = value in their explanations need to
    066 * be recomputed. This can be done via returning all these values into their
    067 * variables' domains followed by arc consistency maintenance over their
    068 * variables. <br>
    069 * <br>
    070 * Parameters:
    071 * <table border='1'><caption>Related Solver Parameters</caption>
    072 * <tr>
    073 * <th>Parameter</th>
    074 * <th>Type</th>
    075 * <th>Comment</th>
    076 * </tr>
    077 * <tr>
    078 * <td>MacPropagation.JustForwardCheck</td>
    079 * <td>{@link Boolean}</td>
    080 * <td>If true, only forward checking instead of full arc consistency is
    081 * maintained during the search.</td>
    082 * </tr>
    083 * </table>
    084 *
    085 * @author  Tomáš Müller
    086 * @version IFS 1.3 (Iterative Forward Search)<br>
    087 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
    088 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    089 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    090 * <br>
    091 *          This library is free software; you can redistribute it and/or modify
    092 *          it under the terms of the GNU Lesser General Public License as
    093 *          published by the Free Software Foundation; either version 3 of the
    094 *          License, or (at your option) any later version. <br>
    095 * <br>
    096 *          This library is distributed in the hope that it will be useful, but
    097 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    098 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    099 *          Lesser General Public License for more details. <br>
    100 * <br>
    101 *          You should have received a copy of the GNU Lesser General Public
    102 *          License along with this library; if not see
    103 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    104 * @param <V> Variable
    105 * @param <T> Value
    106 */
    107public class MacPropagation<V extends Variable<V, T>, T extends Value<V, T>> extends ExtensionWithContext<V, T, MacPropagation<V, T>.NoGood> {
    108    private static org.apache.logging.log4j.Logger sLogger = org.apache.logging.log4j.LogManager.getLogger(MacPropagation.class);
    109    private boolean iJustForwardCheck = false;
    110    private Progress iProgress;
    111
    112    /** List of constraints on which arc-consistency is to be maintained */
    113    protected List<Constraint<V, T>> iConstraints = null;
    114    /** Current iteration */
    115    protected long iIteration = 0;
    116
    117    /** Constructor
    118     * @param solver current solver
    119     * @param properties solver configuration
    120     **/
    121    public MacPropagation(Solver<V, T> solver, DataProperties properties) {
    122        super(solver, properties);
    123        iJustForwardCheck = properties.getPropertyBoolean("MacPropagation.JustForwardCheck", false);
    124    }
    125
    126    /** Adds a constraint on which arc-consistency is to be maintained
    127     * @param constraint a hard constraint
    128     **/
    129    public void addConstraint(Constraint<V, T> constraint) {
    130        if (iConstraints == null)
    131            iConstraints = new ArrayList<Constraint<V, T>>();
    132        iConstraints.add(constraint);
    133    }
    134
    135    /**
    136     * Returns true, if arc-consistency is to be maintained on the given
    137     * constraint
    138     * @param constraint a constraint
    139     * @return true if in the set
    140     */
    141    public boolean contains(Constraint<V, T> constraint) {
    142        if (iConstraints == null)
    143            return true;
    144        return iConstraints.contains(constraint);
    145    }
    146
    147    /**
    148     * Before a value is unassigned: until the value is inconsistent with the
    149     * current solution, an assignment from its explanation is picked and
    150     * unassigned.
    151     */
    152    @Override
    153    public void beforeAssigned(Assignment<V, T> assignment, long iteration, T value) {
    154        iIteration = iteration;
    155        if (value == null)
    156            return;
    157        if (!isGood(assignment, value)) {
    158            while (!isGood(assignment, value) && !noGood(assignment, value).isEmpty()) {
    159                T noGoodValue = noGood(assignment, value).iterator().next();
    160                assignment.unassign(iteration, noGoodValue.variable());
    161            }
    162        }
    163        if (!isGood(assignment, value)) {
    164            sLogger.warn("Going to assign a bad value " + value + " with empty no-good.");
    165        }
    166    }
    167
    168    /**
    169     * After a value is assigned: explanations of other values of the value's
    170     * variable are reset (to contain only the assigned value), propagation over
    171     * the assigned variable takes place.
    172     */
    173    @Override
    174    public void afterAssigned(Assignment<V, T> assignment, long iteration, T value) {
    175        iIteration = iteration;
    176        if (!isGood(assignment, value)) {
    177            sLogger.warn(value.variable().getName() + " = " + value.getName() + " -- not good value assigned (noGood:" + noGood(assignment, value) + ")");
    178            setGood(assignment, value);
    179        }
    180
    181        HashSet<T> noGood = new HashSet<T>(1);
    182        noGood.add(value);
    183        for (Iterator<T> i = value.variable().values(assignment).iterator(); i.hasNext();) {
    184            T anotherValue = i.next();
    185            if (anotherValue.equals(value))
    186                continue;
    187            setNoGood(assignment, anotherValue, noGood);
    188        }
    189        getContext(assignment).propagate(assignment, value.variable());
    190    }
    191
    192    /**
    193     * After a value is unassigned: explanations of all values of unassigned
    194     * variable are recomputed ({@link Value#conflicts(Assignment)}), propagation undo
    195     * over the unassigned variable takes place.
    196     */
    197    @Override
    198    public void afterUnassigned(Assignment<V, T> assignment, long iteration, T value) {
    199        iIteration = iteration;
    200        if (!isGood(assignment, value))
    201            sLogger.error(value.variable().getName() + " = " + value.getName()
    202                    + " -- not good value unassigned (noGood:" + noGood(assignment, value) + ")");
    203        for (Iterator<T> i = value.variable().values(assignment).iterator(); i.hasNext();) {
    204            T anotherValue = i.next();
    205            if (!isGood(assignment, anotherValue)) {
    206                Set<T> noGood = anotherValue.conflicts(assignment);
    207                if (noGood == null)
    208                    setGood(assignment, anotherValue);
    209                else
    210                    setNoGood(assignment, anotherValue, noGood);
    211            }
    212        }
    213        getContext(assignment).undoPropagate(assignment, value.variable());
    214    }
    215
    216    /** good values of a variable (values not removed from variables domain)
    217     * @param assignment current assignment
    218     * @param variable given variable
    219     * @return set of good values
    220     **/
    221    public Set<T> goodValues(Assignment<V, T> assignment, V variable) {
    222        return getContext(assignment).goodValues(variable);
    223    }
    224
    225    /** notification that a nogood value becomes good or vice versa */
    226    private void goodnessChanged(Assignment<V, T> assignment, T value) {
    227        if (isGood(assignment, value)) {
    228            goodValues(assignment, value.variable()).add(value);
    229        } else {
    230            goodValues(assignment, value.variable()).remove(value);
    231        }
    232    }
    233
    234    /** removes support of a variable */
    235    private void removeSupport(Assignment<V, T> assignment, V variable, T value) {
    236        getContext(assignment).supportValues(variable).remove(value);
    237    }
    238
    239    /** adds support of a variable */
    240    private void addSupport(Assignment<V, T> assignment, V variable, T value) {
    241        getContext(assignment).supportValues(variable).add(value);
    242    }
    243
    244    /** variables explanation
    245     * @param assignment current assignment
    246     * @param value given value
    247     * @return no-good for the value
    248     **/
    249    public Set<T> noGood(Assignment<V, T> assignment, T value) {
    250        return getContext(assignment).getNoGood(value);
    251    }
    252
    253    /** is variable good
    254     * @param assignment current assignment
    255     * @param value given value
    256     * @return true if there is no no-good set for the value
    257     **/
    258    public boolean isGood(Assignment<V, T> assignment, T value) {
    259        return getContext(assignment).getNoGood(value) == null;
    260    }
    261
    262    /** sets value to be good
    263     * @param assignment current assignment
    264     * @param value given value
    265     **/
    266    protected void setGood(Assignment<V, T> assignment, T value) {
    267        Set<T> noGood = getContext(assignment).getNoGood(value);
    268        if (noGood != null)
    269            for (T v : noGood)
    270                removeSupport(assignment, v.variable(), value);
    271        getContext(assignment).setNoGood(value, null);
    272        goodnessChanged(assignment, value);
    273    }
    274
    275    /** sets value's explanation
    276     * @param assignment current assignment
    277     * @param value given value
    278     * @param reason no-good set for the value
    279     **/
    280    public void setNoGood(Assignment<V, T> assignment, T value, Set<T> reason) {
    281        Set<T> noGood = noGood(assignment, value);
    282        if (noGood != null)
    283            for (T v : noGood)
    284                removeSupport(assignment, v.variable(), value);
    285        getContext(assignment).setNoGood(value, reason);
    286        for (T aValue : reason)
    287            addSupport(assignment, aValue.variable(), value);
    288        goodnessChanged(assignment, value);
    289    }
    290
    291    private Set<T> reason(Assignment<V, T> assignment, Constraint<V, T> constraint, V aVariable, T aValue) {
    292        Set<T> ret = new HashSet<T>();
    293
    294        for (Iterator<T> i = aVariable.values(assignment).iterator(); i.hasNext();) {
    295            T value = i.next();
    296            if (constraint.isConsistent(aValue, value)) {
    297                if (noGood(assignment, value) == null)
    298                    sLogger.error("Something went wrong: value " + value + " cannot participate in a reason.");
    299                else
    300                    ret.addAll(noGood(assignment, value));
    301            }
    302        }
    303        return ret;
    304    }
    305
    306    @Override
    307    public NoGood createAssignmentContext(Assignment<V, T> assignment) {
    308        return new NoGood(assignment);
    309    }
    310
    311    /** Propagation over the given variable.
    312     * @param assignment current assignment
    313     * @param variable given variable
    314     **/
    315    protected void propagate(Assignment<V, T> assignment, V variable) {
    316        getContext(assignment).propagate(assignment, variable);
    317    }
    318
    319    /**
    320     * Propagation undo over the given variable. All values having given
    321     * variable in their explanations needs to be recomputed. This is done in
    322     * two phases: 1) values that contain this variable in explanation are
    323     * returned back to domains (marked as good) 2) propagation over variables
    324     * which contains a value that was marked as good takes place
    325     * @param assignment current assignment
    326     * @param variable given variable
    327     */
    328    public void undoPropagate(Assignment<V, T> assignment, V variable) {
    329        getContext(assignment).undoPropagate(assignment, variable);
    330    }
    331
    332    /**
    333     * Assignment context
    334     */
    335    public class NoGood implements AssignmentContext {
    336        private Map<V, Set<T>[]> iNoGood = new HashMap<V, Set<T>[]>();
    337        private Map<V, Map<T, Set<T>>> iNoGoodVal = new HashMap<V, Map<T, Set<T>>>();
    338
    339        /**
    340         * Initialization. Enforce arc-consistency over the current (initial)
    341         * solution. AC3 algorithm is used.
    342         */
    343        public NoGood(Assignment<V, T> assignment) {
    344            iProgress = Progress.getInstance(getModel());
    345            iProgress.save();
    346            iProgress.setPhase("Initializing propagation:", 3 * getModel().variables().size());
    347            for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) {
    348                V aVariable = i.next();
    349                supportValues(aVariable).clear();
    350                goodValues(aVariable).clear();
    351            }
    352            for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) {
    353                V aVariable = i.next();
    354                for (Iterator<T> j = aVariable.values(assignment).iterator(); j.hasNext();) {
    355                    T aValue = j.next();
    356                    Set<T> noGood = aValue.conflicts(assignment);
    357                    setNoGood(aValue, noGood);
    358                    if (noGood == null) {
    359                        goodValues(aVariable).add(aValue);
    360                    } else {
    361                    }
    362                }
    363                iProgress.incProgress();
    364            }
    365            Queue<V> queue = new LinkedList<V>();
    366            for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) {
    367                V aVariable = i.next();
    368                for (Constraint<V, T> constraint : aVariable.hardConstraints()) {
    369                    propagate(assignment, constraint, aVariable, queue);
    370                }
    371                iProgress.incProgress();
    372            }
    373            if (!iJustForwardCheck)
    374                propagate(assignment, queue);
    375            for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) {
    376                V aVariable = i.next();
    377                List<T> values2delete = new ArrayList<T>();
    378                for (Iterator<T> j = aVariable.values(assignment).iterator(); j.hasNext();) {
    379                    T aValue = j.next();
    380                    if (getNoGood(aValue) != null && getNoGood(aValue).isEmpty()) {
    381                        values2delete.add(aValue);
    382                    }
    383                }
    384                for (T val : values2delete)
    385                    aVariable.removeValue(0, val);
    386                if (aVariable.values(assignment).isEmpty()) {
    387                    sLogger.error(aVariable.getName() + " has empty domain!");
    388                }
    389                iProgress.incProgress();
    390            }
    391            iProgress.restore();
    392        }
    393
    394        public Set<T>[] getNoGood(V variable) {
    395            return iNoGood.get(variable);
    396        }
    397
    398        public void setNoGood(V variable, Set<T>[] noGood) {
    399            if (noGood == null)
    400                iNoGood.remove(variable);
    401            else
    402                iNoGood.put(variable, noGood);
    403        }
    404
    405        public Set<T> getNoGood(T value) {
    406            Map<T, Set<T>> ng = iNoGoodVal.get(value.variable());
    407            if (ng == null) return null;
    408            return ng.get(value);
    409        }
    410
    411        public void setNoGood(T value, Set<T> noGood) {
    412            Map<T, Set<T>> ng = iNoGoodVal.get(value.variable());
    413            if (ng == null) {
    414                ng = new HashMap<T, Set<T>>();
    415                iNoGoodVal.put(value.variable(), ng);
    416            }
    417            if (noGood == null)
    418                ng.remove(value);
    419            else
    420                ng.put(value, noGood);
    421        }
    422
    423        /** support values of a variable */
    424        @SuppressWarnings("unchecked")
    425        private Set<T> supportValues(V variable) {
    426            Set<T>[] ret = getNoGood(variable);
    427            if (ret == null) {
    428                ret = new Set[] { new HashSet<T>(1000), new HashSet<T>() };
    429                setNoGood(variable, ret);
    430            }
    431            return ret[0];
    432        }
    433
    434        /** good values of a variable (values not removed from variables domain)
    435         * @param variable given variable
    436         * @return set of good values
    437         **/
    438        @SuppressWarnings("unchecked")
    439        private Set<T> goodValues(V variable) {
    440            Set<T>[] ret = getNoGood(variable);
    441            if (ret == null) {
    442                ret = new Set[] { new HashSet<T>(1000), new HashSet<T>() };
    443                setNoGood(variable, ret);
    444            }
    445            return ret[1];
    446        }
    447
    448        /** propagation over a constraint */
    449        private void propagate(Assignment<V, T> assignment, Constraint<V, T> constraint, V aVariable, Queue<V> queue) {
    450            if (goodValues(aVariable).isEmpty())
    451                return;
    452            List<T> conflicts = conflictValues(assignment, constraint, aVariable);
    453
    454            if (conflicts != null && !conflicts.isEmpty()) {
    455                for (T conflictValue : conflicts) {
    456                    if (!queue.contains(conflictValue.variable()))
    457                        queue.add(conflictValue.variable());
    458                    Set<T> reason = reason(assignment, constraint, aVariable, conflictValue);
    459                    // sLogger.debug("  "+conflictValue+" become nogood (c:"+constraint.getName()+", r:"+reason+")");
    460                    setNoGood(conflictValue, reason);
    461                    if (reason.isEmpty())
    462                        (conflictValue.variable()).removeValue(iIteration, conflictValue);
    463                }
    464            }
    465        }
    466
    467        protected boolean propagate(Assignment<V, T> assignment, V aVariable, V anotherVariable, List<T> adepts) {
    468            if (goodValues(aVariable).isEmpty())
    469                return false;
    470            boolean ret = false;
    471            List<T> conflicts = null;
    472            for (Constraint<V, T> constraint : anotherVariable.constraintVariables().get(aVariable)) {
    473                for (T aValue : goodValues(aVariable)) {
    474                    if (conflicts == null)
    475                        conflicts = conflictValues(constraint, aValue, adepts);
    476                    else
    477                        conflicts = conflictValues(constraint, aValue, conflicts);
    478                    if (conflicts == null || conflicts.isEmpty())
    479                        break;
    480                }
    481                if (conflicts != null && !conflicts.isEmpty())
    482                    for (T conflictValue : conflicts) {
    483                        Set<T> reason = reason(assignment, constraint, aVariable, conflictValue);
    484                        // sLogger.debug("  "+conflictValue+" become nogood (c:"+constraint.getName()+", r:"+reason+")");
    485                        setNoGood(conflictValue, reason);
    486                        adepts.remove(conflictValue);
    487                        if (reason.isEmpty())
    488                            (conflictValue.variable()).removeValue(iIteration, conflictValue);
    489                        ret = true;
    490                    }
    491            }
    492            return ret;
    493        }
    494
    495        protected boolean propagate(Assignment<V, T> assignment, V aVariable, V anotherVariable) {
    496            if (goodValues(anotherVariable).isEmpty())
    497                return false;
    498            return propagate(assignment, aVariable, anotherVariable, new ArrayList<T>(goodValues(anotherVariable)));
    499        }
    500
    501        /** Propagation over the given variable.
    502         * @param assignment current assignment
    503         * @param variable given variable
    504         **/
    505        protected void propagate(Assignment<V, T> assignment, V variable) {
    506            Queue<V> queue = new LinkedList<V>();
    507            if (assignment.getValue(variable) != null) {
    508                for (Constraint<V, T> constraint : variable.hardConstraints()) {
    509                    if (contains(constraint))
    510                        propagate(assignment, constraint, assignment.getValue(variable), queue);
    511                }
    512            } else {
    513                for (Constraint<V, T> constraint : variable.hardConstraints()) {
    514                    if (contains(constraint))
    515                        propagate(assignment, constraint, variable, queue);
    516                }
    517            }
    518            if (!iJustForwardCheck && !queue.isEmpty())
    519                propagate(assignment, queue);
    520        }
    521
    522        /** Propagation over the queue of variables.
    523         * @param assignment current assignment
    524         * @param queue variable queue
    525         **/
    526        protected void propagate(Assignment<V, T> assignment, Queue<V> queue) {
    527            while (!queue.isEmpty()) {
    528                V aVariable = queue.poll();
    529                for (Constraint<V, T> constraint : aVariable.hardConstraints()) {
    530                    if (contains(constraint))
    531                        propagate(assignment, constraint, aVariable, queue);
    532                }
    533            }
    534        }
    535
    536        /** propagation over a constraint */
    537        private void propagate(Assignment<V, T> assignment, Constraint<V, T> constraint, T anAssignedValue, Queue<V> queue) {
    538            Set<T> reason = new HashSet<T>(1);
    539            reason.add(anAssignedValue);
    540            Collection<T> conflicts = conflictValues(assignment, constraint, anAssignedValue);
    541            if (conflicts != null && !conflicts.isEmpty())
    542                for (T conflictValue : conflicts) {
    543                    // sLogger.debug("  "+conflictValue+" become nogood (c:"+constraint.getName()+", r:"+reason+")");
    544                    setNoGood(conflictValue, reason);
    545                    if (!queue.contains(conflictValue.variable()))
    546                        queue.add(conflictValue.variable());
    547                }
    548        }
    549
    550        /**
    551         * Propagation undo over the given variable. All values having given
    552         * variable in thair explanations needs to be recomputed. This is done in
    553         * two phases: 1) values that contain this variable in explanation are
    554         * returned back to domains (marked as good) 2) propagation over variables
    555         * which contains a value that was marked as good takes place
    556         * @param assignment current assignment
    557         * @param variable given variable
    558         */
    559        public void undoPropagate(Assignment<V, T> assignment, V variable) {
    560            Map<V, List<T>> undoVars = new HashMap<V, List<T>>();
    561            NoGood context = getContext(assignment);
    562            while (!context.supportValues(variable).isEmpty()) {
    563                T value = context.supportValues(variable).iterator().next();
    564                Set<T> noGood = value.conflicts(assignment);
    565                if (noGood == null) {
    566                    setGood(assignment, value);
    567                    List<T> values = undoVars.get(value.variable());
    568                    if (values == null) {
    569                        values = new ArrayList<T>();
    570                        undoVars.put(value.variable(), values);
    571                    }
    572                    values.add(value);
    573                } else {
    574                    setNoGood(value, noGood);
    575                    if (noGood.isEmpty())
    576                        (value.variable()).removeValue(iIteration, value);
    577                }
    578            }
    579
    580            Queue<V> queue = new LinkedList<V>();
    581            for (V aVariable : undoVars.keySet()) {
    582                List<T> values = undoVars.get(aVariable);
    583                boolean add = false;
    584                for (V x : aVariable.constraintVariables().keySet()) {
    585                    if (propagate(assignment, x, aVariable, values))
    586                        add = true;
    587                }
    588                if (add)
    589                    queue.add(aVariable);
    590            }
    591            for (V x : variable.constraintVariables().keySet()) {
    592                if (propagate(assignment, x, variable) && !queue.contains(variable))
    593                    queue.add(variable);
    594            }
    595            if (!iJustForwardCheck)
    596                propagate(assignment, queue);
    597        }
    598
    599        private List<T> conflictValues(Assignment<V, T> assignment, Constraint<V, T> constraint, T aValue) {
    600            List<T> ret = new ArrayList<T>();
    601
    602            for (V variable : constraint.variables()) {
    603                if (variable.equals(aValue.variable()))
    604                    continue;
    605                if (assignment.getValue(variable) != null)
    606                    continue;
    607
    608                for (T value : goodValues(variable))
    609                    if (!constraint.isConsistent(aValue, value))
    610                        ret.add(value);
    611            }
    612            return ret;
    613        }
    614
    615        private List<T> conflictValues(Constraint<V, T> constraint, T aValue, List<T> values) {
    616            List<T> ret = new ArrayList<T>(values.size());
    617            for (T value : values)
    618                if (!constraint.isConsistent(aValue, value))
    619                    ret.add(value);
    620            return ret;
    621        }
    622
    623        private List<T> conflictValues(Assignment<V, T> assignment, Constraint<V, T> constraint, V aVariable) {
    624            List<T> conflicts = null;
    625            for (T aValue : goodValues(aVariable)) {
    626                if (conflicts == null)
    627                    conflicts = conflictValues(assignment, constraint, aValue);
    628                else
    629                    conflicts = conflictValues(constraint, aValue, conflicts);
    630                if (conflicts == null || conflicts.isEmpty())
    631                    return null;
    632            }
    633            return conflicts;
    634        }
    635    }
    636
    637}