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