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 }