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