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