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}