    001package net.sf.cpsolver.ifs.extension;
    002
    003import java.util.ArrayList;
    004import java.util.HashSet;
    005import java.util.Iterator;
    006import java.util.List;
    007import java.util.Set;
    008
    009import net.sf.cpsolver.ifs.model.Constraint;
    010import net.sf.cpsolver.ifs.model.Value;
    011import net.sf.cpsolver.ifs.model.Variable;
    012import net.sf.cpsolver.ifs.solver.Solver;
    013import net.sf.cpsolver.ifs.util.DataProperties;
    014import net.sf.cpsolver.ifs.util.Progress;
    015
    016/**
    017 * Another implementation of MAC propagation.
    018 *
    019 * @see MacPropagation
    020 *
    021 * @version IFS 1.2 (Iterative Forward Search)<br>
    022 *          Copyright (C) 2006 - 2010 Tomáš Müller<br>
    023 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    024 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    025 * <br>
    026 *          This library is free software; you can redistribute it and/or modify
    027 *          it under the terms of the GNU Lesser General Public License as
    028 *          published by the Free Software Foundation; either version 3 of the
    029 *          License, or (at your option) any later version. <br>
    030 * <br>
    031 *          This library is distributed in the hope that it will be useful, but
    032 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    033 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    034 *          Lesser General Public License for more details. <br>
    035 * <br>
    036 *          You should have received a copy of the GNU Lesser General Public
    037 *          License along with this library; if not see
    038 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    039 */
    040
    041public class MacRevised<V extends Variable<V, T>, T extends Value<V, T>> extends Extension<V, T> {
    042    private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(MacRevised.class);
    043    private boolean iDbt = false;
    044    private Progress iProgress;
    045
    046    /** List of constraints on which arc-consistency is to be maintained */
    047    protected List<Constraint<V, T>> iConstraints = null;
    048    /** Current iteration */
    049    protected long iIteration = 0;
    050
    051    /** Constructor */
    052    public MacRevised(Solver<V, T> solver, DataProperties properties) {
    053        super(solver, properties);
    054        iDbt = properties.getPropertyBoolean("MacRevised.Dbt", false);
    055    }
    056
    057    /** Adds a constraint on which arc-consistency is to be maintained */
    058    public void addConstraint(Constraint<V, T> constraint) {
    059        if (iConstraints == null)
    060            iConstraints = new ArrayList<Constraint<V, T>>();
    061        iConstraints.add(constraint);
    062    }
    063
    064    /**
    065     * Returns true, if arc-consistency is to be maintained on the given
    066     * constraint
    067     */
    068    public boolean contains(Constraint<V, T> constraint) {
    069        if (iConstraints == null)
    070            return true;
    071        return iConstraints.contains(constraint);
    072    }
    073
    074    /**
    075     * Before a value is unassigned: until the value is inconsistent with the
    076     * current solution, an assignment from its explanation is picked and
    077     * unassigned.
    078     */
    079    @Override
    080    public void beforeAssigned(long iteration, T value) {
    081        if (value == null)
    082            return;
    083        sLogger.debug("Before assign " + value.variable().getName() + " = " + value.getName());
    084        iIteration = iteration;
    085        while (!isGood(value) && !noGood(value).isEmpty()) {
    086            if (iDbt)
    087                sLogger.warn("Going to assign a no-good value " + value + " (noGood:" + noGood(value) + ").");
    088            T noGoodValue = noGood(value).iterator().next();
    089            noGoodValue.variable().unassign(iteration);
    090        }
    091        if (!isGood(value)) {
    092            sLogger.warn("Going to assign a bad value " + value + " with empty no-good.");
    093        }
    094    }
    095
    096    /**
    097     * After a value is assigned: explanations of other values of the value's
    098     * variable are reset (to contain only the assigned value), propagation over
    099     * the assigned variable takes place.
    100     */
    101    @Override
    102    public void afterAssigned(long iteration, T value) {
    103        sLogger.debug("After assign " + value.variable().getName() + " = " + value.getName());
    104        iIteration = iteration;
    105        if (!isGood(value)) {
    106            sLogger.warn(value.variable().getName() + " = " + value.getName() + " -- not good value assigned (noGood:"
    107                    + noGood(value) + ")");
    108            setGood(value);
    109        }
    110
    111        Set<T> noGood = new HashSet<T>(1);
    112        noGood.add(value);
    113        List<T> queue = new ArrayList<T>();
    114        for (Iterator<T> i = value.variable().values().iterator(); i.hasNext();) {
    115            T anotherValue = i.next();
    116            if (anotherValue.equals(value) || !isGood(anotherValue))
    117                continue;
    118            setNoGood(anotherValue, noGood);
    119            queue.add(anotherValue);
    120        }
    121        propagate(queue);
    122    }
    123
    124    /**
    125     * After a value is unassigned: explanations of all values of unassigned
    126     * variable are recomputed ({@link Value#conflicts()}), propagation undo
    127     * over the unassigned variable takes place.
    128     */
    129    @Override
    130    public void afterUnassigned(long iteration, T value) {
    131        sLogger.debug("After unassign " + value.variable().getName() + " = " + value.getName());
    132        iIteration = iteration;
    133        if (!isGood(value))
    134            sLogger.error(value.variable().getName() + " = " + value.getName()
    135                    + " -- not good value unassigned (noGood:" + noGood(value) + ")");
    136
    137        List<T> back = new ArrayList<T>(supportValues(value.variable()));
    138        for (T aValue : back) {
    139            if (aValue.variable().getAssignment() != null) {
    140                Set<T> noGood = new HashSet<T>(1);
    141                noGood.add(aValue.variable().getAssignment());
    142                setNoGood(aValue, noGood);
    143            } else
    144                setGood(aValue);
    145        }
    146
    147        List<T> queue = new ArrayList<T>();
    148        for (T aValue : back) {
    149            if (!isGood(aValue) || revise(aValue))
    150                queue.add(aValue);
    151        }
    152
    153        propagate(queue);
    154    }
    155
    156    public void propagate(List<T> queue) {
    157        int idx = 0;
    158        while (queue.size() > idx) {
    159            T value = queue.get(idx++);
    160            sLogger.debug("  -- propagate " + value.variable().getName() + " = " + value.getName() + " (noGood:"
    161                    + noGood(value) + ")");
    162            if (goodValues(value.variable()).isEmpty()) {
    163                sLogger.info("Empty domain detected for variable " + value.variable().getName());
    164                continue;
    165            }
    166            for (Constraint<V, T> constraint : value.variable().hardConstraints()) {
    167                if (!contains(constraint))
    168                    continue;
    169                propagate(constraint, value, queue);
    170            }
    171        }
    172    }
    173
    174    public void propagate(Constraint<V, T> constraint, T noGoodValue, List<T> queue) {
    175        for (V aVariable : constraint.variables()) {
    176            if (aVariable.equals(noGoodValue.variable()))
    177                continue;
    178            for (Iterator<T> j = aVariable.values().iterator(); j.hasNext();) {
    179                T aValue = j.next();
    180                if (isGood(aValue) && constraint.isConsistent(noGoodValue, aValue)
    181                        && !hasSupport(constraint, aValue, noGoodValue.variable())) {
    182                    setNoGood(aValue, explanation(constraint, aValue, noGoodValue.variable()));
    183                    queue.add(aValue);
    184                }
    185            }
    186        }
    187    }
    188
    189    public boolean revise(T value) {
    190        sLogger.debug("  -- revise " + value.variable().getName() + " = " + value.getName());
    191        for (Constraint<V, T> constraint : value.variable().hardConstraints()) {
    192            if (!contains(constraint))
    193                continue;
    194            if (revise(constraint, value))
    195                return true;
    196        }
    197        return false;
    198    }
    199
    200    public boolean revise(Constraint<V, T> constraint, T value) {
    201        for (V aVariable : constraint.variables()) {
    202            if (aVariable.equals(value.variable()))
    203                continue;
    204            if (!hasSupport(constraint, value, aVariable)) {
    205                setNoGood(value, explanation(constraint, value, aVariable));
    206                return true;
    207            }
    208        }
    209        return false;
    210    }
    211
    212    public Set<T> explanation(Constraint<V, T> constraint, T value, V variable) {
    213        Set<T> expl = new HashSet<T>();
    214        for (T aValue : variable.values()) {
    215            if (constraint.isConsistent(aValue, value)) {
    216                expl.addAll(noGood(aValue));
    217            }
    218        }
    219        return expl;
    220    }
    221
    222    public Set<T> supports(Constraint<V, T> constraint, T value, V variable) {
    223        Set<T> sup = new HashSet<T>();
    224        for (T aValue : variable.values()) {
    225            if (!isGood(aValue))
    226                continue;
    227            if (!constraint.isConsistent(aValue, value))
    228                continue;
    229            sup.add(aValue);
    230        }
    231        return sup;
    232    }
    233
    234    public boolean hasSupport(Constraint<V, T> constraint, T value, V variable) {
    235        for (T aValue : variable.values()) {
    236            if (isGood(aValue) && constraint.isConsistent(aValue, value)) {
    237                // sLogger.debug("    -- "+variable.getName()+" = "+aValue.getName()+" supports "
    238                // +
    239                // value.variable().getName()+" = "+value.getName()+" (constraint:"+constraint.getName()+")");
    240                return true;
    241            }
    242        }
    243        // sLogger.debug("    -- value "+value.variable().getName()+" = " +
    244        // value.getName()+" has no support from values of variable "+variable.getName()+" (constraint:"+constraint.getName()+")");
    245        /*
    246         * for (Enumeration e=variable.values().elements();e.hasMoreElements();)
    247         * { T aValue = (T)e.nextElement(); if
    248         * (constraint.isConsistent(aValue,value)) {
    249         * //sLogger.debug("      -- support "
    250         * +aValue.getName()+" is not good: "+expl2str(noGood(aValue))); } }
    251         */
    252        return false;
    253    }
    254
    255    /**
    256     * Initialization. Enforce arc-consistency over the current (initial)
    257     * solution. AC3 algorithm is used.
    258     */
    259    @Override
    260    public boolean init(Solver<V, T> solver) {
    261        boolean isOk = true;
    262        iProgress = Progress.getInstance(getModel());
    263        iProgress.save();
    264        iProgress.setPhase("Initializing propagation:", getModel().variables().size());
    265        for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) {
    266            V aVariable = i.next();
    267            supportValues(aVariable).clear();
    268            goodValues(aVariable).clear();
    269        }
    270        List<T> queue = new ArrayList<T>();
    271        for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) {
    272            V aVariable = i.next();
    273            for (Iterator<T> j = aVariable.values().iterator(); j.hasNext();) {
    274                T aValue = j.next();
    275                initNoGood(aValue, null);
    276                goodValues(aVariable).add(aValue);
    277                if (revise(aValue)) {
    278                    queue.add(aValue);
    279                } else if (aVariable.getAssignment() != null && !aValue.equals(aVariable.getAssignment())) {
    280                    Set<T> noGood = new HashSet<T>();
    281                    noGood.add(aVariable.getAssignment());
    282                    setNoGood(aValue, noGood);
    283                    queue.add(aValue);
    284                }
    285            }
    286            iProgress.incProgress();
    287        }
    288        propagate(queue);
    289        iProgress.restore();
    290        return isOk;
    291    }
    292
    293    /** support values of a variable */
    294    @SuppressWarnings("unchecked")
    295    private Set<T> supportValues(V variable) {
    296        Set<T>[] ret = (Set<T>[]) variable.getExtra();
    297        if (ret == null) {
    298            ret = new Set[] { new HashSet<T>(1000), new HashSet<T>() };
    299            variable.setExtra(ret);
    300        }
    301        return ret[0];
    302    }
    303
    304    /** good values of a variable (values not removed from variables domain) */
    305    @SuppressWarnings("unchecked")
    306    public Set<T> goodValues(V variable) {
    307        Set<T>[] ret = (Set<T>[]) variable.getExtra();
    308        if (ret == null) {
    309            ret = new Set[] { new HashSet<T>(1000), new HashSet<T>() };
    310            variable.setExtra(ret);
    311        }
    312        return ret[1];
    313    }
    314
    315    /** notification that a nogood value becomes good or vice versa */
    316    private void goodnessChanged(T value) {
    317        if (isGood(value)) {
    318            goodValues(value.variable()).add(value);
    319        } else {
    320            goodValues(value.variable()).remove(value);
    321        }
    322    }
    323
    324    /** removes support of a variable */
    325    private void removeSupport(V variable, T value) {
    326        supportValues(variable).remove(value);
    327    }
    328
    329    /** adds support of a variable */
    330    private void addSupport(V variable, T value) {
    331        supportValues(variable).add(value);
    332    }
    333
    334    /** variables explanation */
    335    @SuppressWarnings("unchecked")
    336    public Set<T> noGood(T value) {
    337        return (Set<T>) value.getExtra();
    338    }
    339
    340    /** is variable good */
    341    public boolean isGood(T value) {
    342        return (value.getExtra() == null);
    343    }
    344
    345    /** sets value to be good */
    346    protected void setGood(T value) {
    347        sLogger.debug("    -- set good " + value.variable().getName() + " = " + value.getName());
    348        Set<T> noGood = noGood(value);
    349        if (noGood != null)
    350            for (T v : noGood)
    351                removeSupport(v.variable(), value);
    352        value.setExtra(null);
    353        goodnessChanged(value);
    354    }
    355
    356    /** sets values explanation (initialization) */
    357    private void initNoGood(T value, Set<T> reason) {
    358        value.setExtra(reason);
    359    }
    360
    361    private String expl2str(Set<T> expl) {
    362        StringBuffer sb = new StringBuffer("[");
    363        for (Iterator<T> i = expl.iterator(); i.hasNext();) {
    364            T value = i.next();
    365            sb.append(value.variable().getName() + "=" + value.getName());
    366            if (i.hasNext())
    367                sb.append(", ");
    368        }
    369        sb.append("]");
    370        return sb.toString();
    371    }
    372
    373    private void checkExpl(Set<T> expl) {
    374        sLogger.debug("    -- checking explanation: " + expl2str(expl));
    375        for (Iterator<T> i = expl.iterator(); i.hasNext();) {
    376            T value = i.next();
    377            if (!value.equals(value.variable().getAssignment())) {
    378                if (value.variable().getAssignment() == null)
    379                    sLogger.warn("      -- variable " + value.variable().getName() + " unassigned");
    380                else
    381                    sLogger.warn("      -- variable " + value.variable().getName() + " assigned to a different value "
    382                            + value.variable().getAssignment().getName());
    383            }
    384        }
    385    }
    386
    387    private void printAssignments() {
    388        sLogger.debug("    -- printing assignments: ");
    389        for (Iterator<V> i = getModel().variables().iterator(); i.hasNext();) {
    390            V variable = i.next();
    391            if (variable.getAssignment() != null)
    392                sLogger.debug("      -- " + variable.getName() + " = " + variable.getAssignment().getName());
    393        }
    394    }
    395
    396    /** sets value's explanation */
    397    public void setNoGood(T value, Set<T> reason) {
    398        sLogger.debug("    -- set nogood " + value.variable().getName() + " = " + value.getName() + "(expl:"
    399                + expl2str(reason) + ")");
    400        if (value.equals(value.variable().getAssignment())) {
    401            try {
    402                throw new Exception("An assigned value " + value.variable().getName() + " = " + value.getName()
    403                        + " become no good (noGood:" + reason + ")!!");
    404            } catch (Exception e) {
    405                sLogger.warn(e.getMessage(), e);
    406            }
    407            checkExpl(reason);
    408            printAssignments();
    409        }
    410        Set<T> noGood = noGood(value);
    411        if (noGood != null)
    412            for (T v : noGood)
    413                removeSupport(v.variable(), value);
    414        value.setExtra(reason);
    415        for (T aValue : reason) {
    416            addSupport(aValue.variable(), value);
    417        }
    418        goodnessChanged(value);
    419    }
    420}