001    package net.sf.cpsolver.ifs.extension;
002    
003    import java.util.ArrayList;
004    import java.util.HashSet;
005    import java.util.Iterator;
006    import java.util.List;
007    import java.util.Set;
008    
009    import net.sf.cpsolver.ifs.model.Constraint;
010    import net.sf.cpsolver.ifs.model.Value;
011    import net.sf.cpsolver.ifs.model.Variable;
012    import net.sf.cpsolver.ifs.solver.Solver;
013    import net.sf.cpsolver.ifs.util.DataProperties;
014    import 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 Tomas Muller<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    
041    public 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    }