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}