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