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}