001 package net.sf.cpsolver.ifs.model;
002
003 import java.util.ArrayList;
004 import java.util.Collection;
005 import java.util.Comparator;
006 import java.util.HashSet;
007 import java.util.HashMap;
008 import java.util.List;
009 import java.util.Locale;
010 import java.util.Map;
011 import java.util.Set;
012 import java.util.TreeSet;
013
014 import net.sf.cpsolver.ifs.criteria.Criterion;
015 import net.sf.cpsolver.ifs.solver.Solver;
016 import net.sf.cpsolver.ifs.util.ToolBox;
017
018 /**
019 * Generic model (definition of a problem). <br>
020 * <br>
021 * It consists of variables and constraints. It has also capability of
022 * memorizing the current and the best ever found assignment. <br>
023 * <br>
024 * Example usage:<br>
025 * <ul>
026 * <code>
027 * MyModel model = new MyModel();<br>
028 * Variable a = new MyVariable("A");<br>
029 * model.addVariable(a);<br>
030 * Variable b = new MyVariable("B");<br>
031 * model.addVariable(b);<br>
032 * Variable c = new MyVariable("C");<br>
033 * model.addVariable(c);<br>
034 * Constraint constr = MyConstraint("all-different");<br>
035 * model.addConstraint(constr);<br>
036 * constr.addVariable(a);<br>
037 * constr.addVariable(b);<br>
038 * constr.addVariable(c);<br>
039 * solver.setInitialSolution(model);
040 * </code>
041 * </ul>
042 *
043 * @see Variable
044 * @see Constraint
045 * @see net.sf.cpsolver.ifs.solution.Solution
046 * @see net.sf.cpsolver.ifs.solver.Solver
047 *
048 * @version IFS 1.2 (Iterative Forward Search)<br>
049 * Copyright (C) 2006 - 2010 Tomas Muller<br>
050 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
051 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
052 * <br>
053 * This library is free software; you can redistribute it and/or modify
054 * it under the terms of the GNU Lesser General Public License as
055 * published by the Free Software Foundation; either version 3 of the
056 * License, or (at your option) any later version. <br>
057 * <br>
058 * This library is distributed in the hope that it will be useful, but
059 * WITHOUT ANY WARRANTY; without even the implied warranty of
060 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
061 * Lesser General Public License for more details. <br>
062 * <br>
063 * You should have received a copy of the GNU Lesser General Public
064 * License along with this library; if not see
065 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
066 */
067
068 public class Model<V extends Variable<V, T>, T extends Value<V, T>> {
069 private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(Model.class);
070 protected static java.text.DecimalFormat sTimeFormat = new java.text.DecimalFormat("0.00",
071 new java.text.DecimalFormatSymbols(Locale.US));
072 protected static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.00",
073 new java.text.DecimalFormatSymbols(Locale.US));
074 protected static java.text.DecimalFormat sPercentageFormat = new java.text.DecimalFormat("0.00",
075 new java.text.DecimalFormatSymbols(Locale.US));
076
077 private List<V> iVariables = new ArrayList<V>();
078 private List<Constraint<V, T>> iConstraints = new ArrayList<Constraint<V, T>>();
079 private List<GlobalConstraint<V, T>> iGlobalConstraints = new ArrayList<GlobalConstraint<V, T>>();
080 protected Collection<V> iUnassignedVariables = new HashSet<V>();
081 protected Collection<V> iAssignedVariables = new HashSet<V>();
082 private Collection<V> iVariablesWithInitialValueCache = null;
083 protected Collection<V> iPerturbVariables = null;
084
085 private List<ModelListener<V, T>> iModelListeners = new ArrayList<ModelListener<V, T>>();
086 private List<InfoProvider<V>> iInfoProviders = new ArrayList<InfoProvider<V>>();
087 private HashMap<String, Criterion<V, T>> iCriteria = new HashMap<String, Criterion<V,T>>();
088
089 private int iBestUnassignedVariables = -1;
090 private int iBestPerturbations = 0;
091 private int iNrAssignedVariables = 0;
092
093 /** Constructor */
094 public Model() {
095 }
096
097 /** The list of variables in the model */
098 public List<V> variables() {
099 return iVariables;
100 }
101
102 /** The number of variables in the model */
103 public int countVariables() {
104 return iVariables.size();
105 }
106
107 /** Adds a variable to the model */
108 @SuppressWarnings("unchecked")
109 public void addVariable(V variable) {
110 variable.setModel(this);
111 iVariables.add(variable);
112 if (variable instanceof InfoProvider<?>)
113 iInfoProviders.add((InfoProvider<V>) variable);
114 if (variable.getAssignment() == null) {
115 if (iUnassignedVariables != null)
116 iUnassignedVariables.add(variable);
117 } else {
118 if (iAssignedVariables != null)
119 iAssignedVariables.add(variable);
120 iNrAssignedVariables++;
121 }
122 if (variable.getAssignment() != null)
123 variable.assign(0L, variable.getAssignment());
124 for (ModelListener<V, T> listener : iModelListeners)
125 listener.variableAdded(variable);
126 invalidateVariablesWithInitialValueCache();
127 }
128
129 /** Removes a variable from the model */
130 public void removeVariable(V variable) {
131 variable.setModel(null);
132 iVariables.remove(variable);
133 if (variable instanceof InfoProvider<?>)
134 iInfoProviders.remove(variable);
135 if (iUnassignedVariables != null && iUnassignedVariables.contains(variable))
136 iUnassignedVariables.remove(variable);
137 if (iAssignedVariables != null && iAssignedVariables.contains(variable))
138 iAssignedVariables.remove(variable);
139 if (variable.getAssignment() != null)
140 iNrAssignedVariables--;
141 for (ModelListener<V, T> listener : iModelListeners)
142 listener.variableRemoved(variable);
143 invalidateVariablesWithInitialValueCache();
144 }
145
146 /** The list of constraints in the model */
147 public List<Constraint<V, T>> constraints() {
148 return iConstraints;
149 }
150
151 /** The number of constraints in the model */
152 public int countConstraints() {
153 return iConstraints.size();
154 }
155
156 /** Adds a constraint to the model */
157 @SuppressWarnings("unchecked")
158 public void addConstraint(Constraint<V, T> constraint) {
159 constraint.setModel(this);
160 iConstraints.add(constraint);
161 if (constraint instanceof InfoProvider<?>)
162 iInfoProviders.add((InfoProvider<V>) constraint);
163 for (ModelListener<V, T> listener : iModelListeners)
164 listener.constraintAdded(constraint);
165 }
166
167 /** Removes a constraint from the model */
168 public void removeConstraint(Constraint<V, T> constraint) {
169 constraint.setModel(null);
170 iConstraints.remove(constraint);
171 if (constraint instanceof InfoProvider<?>)
172 iInfoProviders.remove(constraint);
173 for (ModelListener<V, T> listener : iModelListeners)
174 listener.constraintRemoved(constraint);
175 }
176
177 /** The list of global constraints in the model */
178 public List<GlobalConstraint<V, T>> globalConstraints() {
179 return iGlobalConstraints;
180 }
181
182 /** The number of global constraints in the model */
183 public int countGlobalConstraints() {
184 return iGlobalConstraints.size();
185 }
186
187 /** Adds a global constraint to the model */
188 @SuppressWarnings("unchecked")
189 public void addGlobalConstraint(GlobalConstraint<V, T> constraint) {
190 constraint.setModel(this);
191 iGlobalConstraints.add(constraint);
192 if (constraint instanceof InfoProvider<?>)
193 iInfoProviders.add((InfoProvider<V>) constraint);
194 for (ModelListener<V, T> listener : iModelListeners)
195 listener.constraintAdded(constraint);
196 }
197
198 /** Removes a global constraint from the model */
199 public void removeGlobalConstraint(GlobalConstraint<V, T> constraint) {
200 constraint.setModel(null);
201 iGlobalConstraints.remove(constraint);
202 if (constraint instanceof InfoProvider<?>)
203 iInfoProviders.remove(constraint);
204 for (ModelListener<V, T> listener : iModelListeners)
205 listener.constraintRemoved(constraint);
206 }
207
208 /** The list of unassigned variables in the model */
209 public Collection<V> unassignedVariables() {
210 if (iUnassignedVariables != null)
211 return iUnassignedVariables;
212 Collection<V> un = new ArrayList<V>(iVariables.size());
213 for (V variable : iVariables) {
214 if (variable.getAssignment() == null)
215 un.add(variable);
216 }
217 return un;
218 }
219
220 /** Number of unassigned variables */
221 public int nrUnassignedVariables() {
222 if (iUnassignedVariables != null)
223 return iUnassignedVariables.size();
224 return iVariables.size() - iNrAssignedVariables;
225 }
226
227 /** The list of assigned variables in the model */
228 public Collection<V> assignedVariables() {
229 if (iAssignedVariables != null)
230 return iAssignedVariables;
231 Collection<V> as = new ArrayList<V>(iVariables.size());
232 for (V variable : iVariables) {
233 if (variable.getAssignment() != null)
234 as.add(variable);
235 }
236 return as;
237 }
238
239 /** Number of assigned variables */
240 public int nrAssignedVariables() {
241 if (iAssignedVariables != null)
242 return iAssignedVariables.size();
243 return iNrAssignedVariables;
244 }
245
246 /**
247 * The list of perturbation variables in the model, i.e., the variables
248 * which has an initial value but which are not assigned with this value.
249 */
250 public Collection<V> perturbVariables() {
251 if (iPerturbVariables == null)
252 iPerturbVariables = perturbVariables(variablesWithInitialValue());
253 return iPerturbVariables;
254 }
255
256 /**
257 * The list of perturbation variables in the model, i.e., the variables
258 * which has an initial value but which are not assigned with this value.
259 * Only variables from the given set are considered.
260 */
261 public List<V> perturbVariables(Collection<V> variables) {
262 List<V> perturbances = new ArrayList<V>();
263 for (V variable : variables) {
264 if (variable.getInitialAssignment() == null)
265 continue;
266 if (variable.getAssignment() != null) {
267 if (!variable.getInitialAssignment().equals(variable.getAssignment()))
268 perturbances.add(variable);
269 } else {
270 boolean hasPerturbance = false;
271 for (Constraint<V, T> constraint : variable.hardConstraints()) {
272 if (constraint.inConflict(variable.getInitialAssignment())) {
273 hasPerturbance = true;
274 break;
275 }
276 }
277 if (!hasPerturbance)
278 for (GlobalConstraint<V, T> constraint : globalConstraints()) {
279 if (constraint.inConflict(variable.getInitialAssignment())) {
280 hasPerturbance = true;
281 break;
282 }
283 }
284 if (hasPerturbance)
285 perturbances.add(variable);
286 }
287 }
288 return perturbances;
289 }
290
291 /**
292 * Returns the set of conflicting variables with this value, if it is
293 * assigned to its variable
294 */
295 public Set<T> conflictValues(T value) {
296 Set<T> conflictValues = new HashSet<T>();
297 for (Constraint<V, T> constraint : value.variable().hardConstraints())
298 constraint.computeConflicts(value, conflictValues);
299 for (GlobalConstraint<V, T> constraint : globalConstraints())
300 constraint.computeConflicts(value, conflictValues);
301 return conflictValues;
302 }
303
304 /** Return true if the given value is in conflict with a hard constraint */
305 public boolean inConflict(T value) {
306 for (Constraint<V, T> constraint : value.variable().hardConstraints())
307 if (constraint.inConflict(value))
308 return true;
309 for (GlobalConstraint<V, T> constraint : globalConstraints())
310 if (constraint.inConflict(value))
311 return true;
312 return false;
313 }
314
315 /** The list of variables without initial value */
316 public Collection<V> variablesWithInitialValue() {
317 if (iVariablesWithInitialValueCache != null)
318 return iVariablesWithInitialValueCache;
319 iVariablesWithInitialValueCache = new ArrayList<V>();
320 for (V variable : iVariables) {
321 if (variable.getInitialAssignment() != null)
322 iVariablesWithInitialValueCache.add(variable);
323 }
324 return iVariablesWithInitialValueCache;
325 }
326
327 /** Invalidates cache containing all variables that possess an initial value */
328 protected void invalidateVariablesWithInitialValueCache() {
329 iVariablesWithInitialValueCache = null;
330 }
331
332 /** Called before a value is assigned to its variable */
333 public void beforeAssigned(long iteration, T value) {
334 for (ModelListener<V, T> listener : iModelListeners)
335 listener.beforeAssigned(iteration, value);
336 }
337
338 /** Called before a value is unassigned from its variable */
339 public void beforeUnassigned(long iteration, T value) {
340 for (ModelListener<V, T> listener : iModelListeners)
341 listener.beforeUnassigned(iteration, value);
342 }
343
344 /** Called after a value is assigned to its variable */
345 public void afterAssigned(long iteration, T value) {
346 if (iUnassignedVariables != null)
347 iUnassignedVariables.remove(value.variable());
348 if (iAssignedVariables != null)
349 iAssignedVariables.add(value.variable());
350 iNrAssignedVariables++;
351 iPerturbVariables = null;
352 for (ModelListener<V, T> listener : iModelListeners)
353 listener.afterAssigned(iteration, value);
354 }
355
356 /** Called after a value is unassigned from its variable */
357 public void afterUnassigned(long iteration, T value) {
358 if (iUnassignedVariables != null)
359 iUnassignedVariables.add(value.variable());
360 if (iAssignedVariables != null)
361 iAssignedVariables.remove(value.variable());
362 iNrAssignedVariables--;
363 iPerturbVariables = null;
364 for (ModelListener<V, T> listener : iModelListeners)
365 listener.afterUnassigned(iteration, value);
366 }
367
368 @Override
369 public String toString() {
370 return "Model{\n variables=" + ToolBox.col2string(variables(), 2) + ",\n constraints="
371 + ToolBox.col2string(constraints(), 2) + ",\n #unassigned=" + nrUnassignedVariables()
372 + ",\n unassigned=" + ToolBox.col2string(unassignedVariables(), 2) + ",\n #perturbations="
373 + perturbVariables().size() + "+" + (variables().size() - variablesWithInitialValue().size())
374 + ",\n perturbations=" + ToolBox.col2string(perturbVariables(), 2) + ",\n info=" + getInfo()
375 + "\n }";
376 }
377
378 protected String getPerc(double value, double min, double max) {
379 if (max == min)
380 return sPercentageFormat.format(100.0);
381 return sPercentageFormat.format(100.0 - 100.0 * (value - min) / (max - min));
382 }
383
384 protected String getPercRev(double value, double min, double max) {
385 if (max == min)
386 return sPercentageFormat.format(0.0);
387 return sPercentageFormat.format(100.0 * (value - min) / (max - min));
388 }
389
390 /**
391 * Returns information about the current solution. Information from all
392 * model listeners and constraints is also included.
393 */
394 public Map<String, String> getInfo() {
395 HashMap<String, String> ret = new HashMap<String, String>();
396 ret.put("Assigned variables", getPercRev(nrAssignedVariables(), 0, variables().size()) + "% ("
397 + nrAssignedVariables() + "/" + variables().size() + ")");
398 int nrVarsWithInitialValue = variablesWithInitialValue().size();
399 if (nrVarsWithInitialValue > 0) {
400 ret.put("Perturbation variables", getPercRev(perturbVariables().size(), 0, nrVarsWithInitialValue) + "% ("
401 + perturbVariables().size() + " + " + (variables().size() - nrVarsWithInitialValue) + ")");
402 }
403 ret.put("Overall solution value", sDoubleFormat.format(getTotalValue()));
404 for (InfoProvider<V> provider : iInfoProviders)
405 provider.getInfo(ret);
406 return ret;
407 }
408
409 /**
410 * Extended information about current solution. Similar to
411 * {@link Model#getInfo()}, but some more information (that is more
412 * expensive to compute) might be added.
413 */
414 public Map<String, String> getExtendedInfo() {
415 return getInfo();
416 }
417
418 /**
419 * Returns information about the current solution. Information from all
420 * model listeners and constraints is also included. Only variables from the
421 * given set are considered.
422 */
423 public Map<String, String> getInfo(Collection<V> variables) {
424 Map<String, String> ret = new HashMap<String, String>();
425 int assigned = 0, perturb = 0, nrVarsWithInitialValue = 0;
426 for (V variable : variables) {
427 if (variable.getAssignment() != null)
428 assigned++;
429 if (variable.getInitialAssignment() != null) {
430 nrVarsWithInitialValue++;
431 if (variable.getAssignment() != null) {
432 if (!variable.getInitialAssignment().equals(variable.getAssignment()))
433 perturb++;
434 } else {
435 boolean hasPerturbance = false;
436 for (Constraint<V, T> constraint : variable.hardConstraints()) {
437 if (constraint.inConflict(variable.getInitialAssignment())) {
438 hasPerturbance = true;
439 break;
440 }
441 }
442 if (!hasPerturbance)
443 for (GlobalConstraint<V, T> constraint : globalConstraints()) {
444 if (constraint.inConflict(variable.getInitialAssignment())) {
445 hasPerturbance = true;
446 break;
447 }
448 }
449 if (hasPerturbance)
450 perturb++;
451 }
452 }
453 }
454 ret.put("Assigned variables", getPercRev(assigned, 0, variables.size()) + "% (" + assigned + "/"
455 + variables.size() + ")");
456 if (nrVarsWithInitialValue > 0) {
457 ret.put("Perturbation variables", getPercRev(perturb, 0, nrVarsWithInitialValue) + "% (" + perturb + " + "
458 + (variables.size() - nrVarsWithInitialValue) + ")");
459 }
460 ret.put("Overall solution value", sDoubleFormat.format(getTotalValue(variables)));
461 for (InfoProvider<V> provider : iInfoProviders)
462 provider.getInfo(ret, variables);
463 return ret;
464 }
465
466 /**
467 * Returns the number of unassigned variables in the best ever found
468 * solution
469 */
470 public int getBestUnassignedVariables() {
471 return iBestUnassignedVariables;
472 }
473
474 /**
475 * Returns the number of perturbation variables in the best ever found
476 * solution
477 */
478 public int getBestPerturbations() {
479 return iBestPerturbations;
480 }
481
482 /** Save the current assignment as the best ever found assignment */
483 public void saveBest() {
484 iBestUnassignedVariables = nrUnassignedVariables();// unassignedVariables().size();
485 iBestPerturbations = perturbVariables().size();
486 for (V variable : iVariables) {
487 variable.setBestAssignment(variable.getAssignment());
488 }
489 for (Criterion<V, T> criterion: getCriteria()) {
490 criterion.bestSaved();
491 }
492 }
493
494 /** Clear the best ever found assignment */
495 public void clearBest() {
496 iBestUnassignedVariables = -1;
497 iBestPerturbations = 0;
498 for (V variable : iVariables) {
499 variable.setBestAssignment(null);
500 }
501 }
502
503 /** Restore the best ever found assignment into the current assignment */
504 @SuppressWarnings("unchecked")
505 protected void restoreBest(Comparator<V> assignmentOrder) {
506 TreeSet<V> sortedVariables = new TreeSet<V>(assignmentOrder);
507 for (V variable : iVariables) {
508 if (variable.getAssignment() == null) {
509 if (variable.getBestAssignment() != null)
510 sortedVariables.add(variable);
511 } else if (!variable.getAssignment().equals(variable.getBestAssignment())) {
512 variable.unassign(0);
513 if (variable.getBestAssignment() != null)
514 sortedVariables.add(variable);
515 }
516 }
517 Set<T> problems = new HashSet<T>();
518 for (V variable : sortedVariables) {
519 Set<T> confs = conflictValues(variable.getBestAssignment());
520 if (!confs.isEmpty()) {
521 sLogger.error("restore best problem: assignment " + variable.getName() + " = "
522 + variable.getBestAssignment().getName());
523 for (Constraint<V, T> c : variable.hardConstraints()) {
524 Set<T> x = new HashSet<T>();
525 c.computeConflicts(variable.getBestAssignment(), x);
526 if (!x.isEmpty()) {
527 if (c instanceof WeakeningConstraint) {
528 ((WeakeningConstraint<V, T>)c).weaken(variable.getBestAssignment());
529 sLogger.info(" constraint " + c.getClass().getName() + " " + c.getName() + " had to be weakened");
530 } else {
531 sLogger.error(" constraint " + c.getClass().getName() + " " + c.getName() + " causes the following conflicts " + x);
532 }
533 }
534 }
535 for (GlobalConstraint<V, T> c : globalConstraints()) {
536 Set<T> x = new HashSet<T>();
537 c.computeConflicts(variable.getBestAssignment(), x);
538 if (!x.isEmpty()) {
539 if (c instanceof WeakeningConstraint) {
540 ((WeakeningConstraint<V, T>)c).weaken(variable.getBestAssignment());
541 sLogger.info(" constraint " + c.getClass().getName() + " " + c.getName() + " had to be weakened");
542 } else {
543 sLogger.error(" global constraint " + c.getClass().getName() + " " + c.getName() + " causes the following conflicts " + x);
544 }
545 }
546 }
547 problems.add(variable.getBestAssignment());
548 } else
549 variable.assign(0, variable.getBestAssignment());
550 }
551 int attempt = 0, maxAttempts = 3 * problems.size();
552 while (!problems.isEmpty() && attempt <= maxAttempts) {
553 attempt++;
554 T value = ToolBox.random(problems);
555 problems.remove(value);
556 V variable = value.variable();
557 Set<T> confs = conflictValues(value);
558 if (!confs.isEmpty()) {
559 sLogger.error("restore best problem (again, att=" + attempt + "): assignment " + variable.getName()
560 + " = " + value.getName());
561 for (Constraint<V, T> c : variable.hardConstraints()) {
562 Set<T> x = new HashSet<T>();
563 c.computeConflicts(value, x);
564 if (!x.isEmpty())
565 sLogger.error(" constraint " + c.getClass().getName() + " " + c.getName()
566 + " causes the following conflicts " + x);
567 }
568 for (GlobalConstraint<V, T> c : globalConstraints()) {
569 Set<T> x = new HashSet<T>();
570 c.computeConflicts(value, x);
571 if (!x.isEmpty())
572 sLogger.error(" constraint " + c.getClass().getName() + " " + c.getName()
573 + " causes the following conflicts " + x);
574 }
575 for (T conf : confs)
576 conf.variable().unassign(0);
577 problems.addAll(confs);
578 }
579 variable.assign(0, value);
580 }
581 for (Criterion<V, T> criterion: getCriteria()) {
582 criterion.bestRestored();
583 }
584 }
585
586 public void restoreBest() {
587 restoreBest(new Comparator<V>() {
588 @Override
589 public int compare(V v1, V v2) {
590 if (v1.getBestAssignmentIteration() < v2.getBestAssignmentIteration()) return -1;
591 if (v1.getBestAssignmentIteration() > v2.getBestAssignmentIteration()) return 1;
592 return v1.compareTo(v2);
593 }
594 });
595 }
596
597 /** The list of unassigned variables in the best ever found solution */
598 public Collection<V> bestUnassignedVariables() {
599 if (iBestUnassignedVariables < 0)
600 return unassignedVariables();
601 Collection<V> ret = new ArrayList<V>(variables().size());
602 for (V variable : variables()) {
603 if (variable.getBestAssignment() == null)
604 ret.add(variable);
605 }
606 return ret;
607 }
608
609 /**
610 * Value of the current solution. It is the sum of all assigned values,
611 * i.e., {@link Value#toDouble()}.
612 */
613 public double getTotalValue() {
614 double ret = 0.0;
615 for (V v: assignedVariables())
616 ret += v.getAssignment().toDouble();
617 return ret;
618 }
619
620 /**
621 * Value of the current solution. It is the sum of all assigned values,
622 * i.e., {@link Value#toDouble()}. Only variables from the given set are
623 * considered.
624 **/
625 public double getTotalValue(Collection<V> variables) {
626 double ret = 0.0;
627 for (V v: variables)
628 if (v.getAssignment() != null)
629 ret += v.getAssignment().toDouble();
630 return ret;
631 }
632
633 /** Adds a model listener */
634 @SuppressWarnings("unchecked")
635 public void addModelListener(ModelListener<V, T> listener) {
636 iModelListeners.add(listener);
637 if (listener instanceof InfoProvider<?>)
638 iInfoProviders.add((InfoProvider<V>) listener);
639 for (Constraint<V, T> constraint : iConstraints)
640 listener.constraintAdded(constraint);
641 for (V variable : iVariables)
642 listener.variableAdded(variable);
643 }
644
645 /** Removes a model listener */
646 public void removeModelListener(ModelListener<V, T> listener) {
647 if (listener instanceof InfoProvider<?>)
648 iInfoProviders.remove(listener);
649 for (V variable : iVariables)
650 listener.variableRemoved(variable);
651 for (Constraint<V, T> constraint : iConstraints)
652 listener.constraintRemoved(constraint);
653 iModelListeners.remove(listener);
654 }
655
656 /** Model initialization */
657 public boolean init(Solver<V, T> solver) {
658 for (ModelListener<V, T> listener : new ArrayList<ModelListener<V, T>>(iModelListeners)) {
659 if (!listener.init(solver))
660 return false;
661 }
662 return true;
663 }
664
665 /** The list of model listeners */
666 public List<ModelListener<V, T>> getModelListeners() {
667 return iModelListeners;
668 }
669
670 /** The list of model listeners that are of the given class */
671 public ModelListener<V, T> modelListenerOfType(Class<ModelListener<V, T>> type) {
672 for (ModelListener<V, T> listener : iModelListeners) {
673 if (listener.getClass() == type)
674 return listener;
675 }
676 return null;
677 }
678
679 /**
680 * The list of constraints which are in a conflict with the given value if
681 * it is assigned to its variable. This means the constraints, which adds a
682 * value into the set of conflicting values in
683 * {@link Constraint#computeConflicts(Value, Set)}.
684 */
685 public Map<Constraint<V, T>, Set<T>> conflictConstraints(T value) {
686 Map<Constraint<V, T>, Set<T>> conflictConstraints = new HashMap<Constraint<V, T>, Set<T>>();
687 for (Constraint<V, T> constraint : value.variable().hardConstraints()) {
688 Set<T> conflicts = new HashSet<T>();
689 constraint.computeConflicts(value, conflicts);
690 if (!conflicts.isEmpty()) {
691 conflictConstraints.put(constraint, conflicts);
692 }
693 }
694 for (GlobalConstraint<V, T> constraint : globalConstraints()) {
695 Set<T> conflicts = new HashSet<T>();
696 constraint.computeConflicts(value, conflicts);
697 if (!conflicts.isEmpty()) {
698 conflictConstraints.put(constraint, conflicts);
699 }
700 }
701 return conflictConstraints;
702 }
703
704 /**
705 * The list of hard constraints which contain at least one variable that is
706 * not assigned.
707 */
708 public List<Constraint<V, T>> unassignedHardConstraints() {
709 List<Constraint<V, T>> ret = new ArrayList<Constraint<V, T>>();
710 constraints: for (Constraint<V, T> constraint : constraints()) {
711 if (!constraint.isHard())
712 continue;
713 for (V v : constraint.variables()) {
714 if (v.getAssignment() == null) {
715 ret.add(constraint);
716 continue constraints;
717 }
718 }
719 }
720 if (!unassignedVariables().isEmpty())
721 ret.addAll(globalConstraints());
722 return ret;
723 }
724
725 /** Registered info providers (see {@link InfoProvider}) */
726 protected List<InfoProvider<V>> getInfoProviders() {
727 return iInfoProviders;
728 }
729
730 /** Register a new criterion */
731 public void addCriterion(Criterion<V,T> criterion) {
732 iCriteria.put(criterion.getClass().getName(), criterion);
733 addModelListener(criterion);
734 }
735
736 /** Unregister an existing criterion */
737 public void removeCriterion(Criterion<V,T> criterion) {
738 iCriteria.remove(criterion.getClass().getName());
739 removeModelListener(criterion);
740 }
741
742 /** Unregister an existing criterion */
743 public void removeCriterion(Class<? extends Criterion<V, T>> criterion) {
744 Criterion<V,T> c = iCriteria.remove(criterion.getName());
745 if (c != null)
746 removeModelListener(c);
747 }
748
749 /** Return a registered criterion of the given type. */
750 public Criterion<V, T> getCriterion(Class<? extends Criterion<V, T>> criterion) {
751 return iCriteria.get(criterion.getName());
752 }
753
754 /** List all registered criteria */
755 public Collection<Criterion<V, T>> getCriteria() {
756 return iCriteria.values();
757 }
758
759 /**
760 * Weaken all weakening constraint so that the given value can be assigned without
761 * them creating a conflict using {@link WeakeningConstraint#weaken(Value)}.
762 * This method is handy for instance when an existing solution is being loaded
763 * into the solver.
764 */
765 @SuppressWarnings("unchecked")
766 public void weaken(T value) {
767 for (Constraint<V, T> constraint : value.variable().hardConstraints()) {
768 if (constraint instanceof WeakeningConstraint)
769 ((WeakeningConstraint<V,T>)constraint).weaken(value);
770 }
771 for (GlobalConstraint<V, T> constraint : globalConstraints()) {
772 if (constraint instanceof WeakeningConstraint)
773 ((WeakeningConstraint<V,T>)constraint).weaken(value);
774 }
775 }
776 }