001package net.sf.cpsolver.ifs.extension; 002 003import java.util.ArrayList; 004import java.util.HashSet; 005import java.util.HashMap; 006import java.util.List; 007import java.util.Map; 008import java.util.Set; 009 010import net.sf.cpsolver.ifs.model.Constraint; 011import net.sf.cpsolver.ifs.model.Value; 012import net.sf.cpsolver.ifs.model.Variable; 013import net.sf.cpsolver.ifs.solver.Solver; 014import net.sf.cpsolver.ifs.util.DataProperties; 015 016/** 017 * Computation of violated initial values (minimal perturbation problem). <br> 018 * <br> 019 * It is using {@link Constraint#isConsistent(Value, Value)} to find out what 020 * initial values (of different variables) cannot be assigned when an arbitrary 021 * value is assigned to a variable. This information is computed in advance, 022 * before the solver is executed. It is used for better estimation of 023 * perturbation penalty (see 024 * {@link net.sf.cpsolver.ifs.perturbations.PerturbationsCounter}) when a value 025 * is to be assigned to a variable. 026 * 027 * @version IFS 1.2 (Iterative Forward Search)<br> 028 * Copyright (C) 2006 - 2010 Tomáš Müller<br> 029 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 030 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 031 * <br> 032 * This library is free software; you can redistribute it and/or modify 033 * it under the terms of the GNU Lesser General Public License as 034 * published by the Free Software Foundation; either version 3 of the 035 * License, or (at your option) any later version. <br> 036 * <br> 037 * This library is distributed in the hope that it will be useful, but 038 * WITHOUT ANY WARRANTY; without even the implied warranty of 039 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 040 * Lesser General Public License for more details. <br> 041 * <br> 042 * You should have received a copy of the GNU Lesser General Public 043 * License along with this library; if not see 044 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 045 */ 046public class ViolatedInitials<V extends Variable<V, T>, T extends Value<V, T>> extends Extension<V, T> { 047 private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(ViolatedInitials.class); 048 private Map<T, Set<T>> iViolatedInitials = new HashMap<T, Set<T>>(); 049 050 public ViolatedInitials(Solver<V, T> solver, DataProperties properties) { 051 super(solver, properties); 052 } 053 054 /** Compute the violations between any value and all other initial values */ 055 public boolean init() { 056 sLogger.info("Computation of violated initials enabled."); 057 for (V variable : getModel().variables()) { 058 if (variable.getInitialAssignment() == null) 059 continue; 060 for (Constraint<V, T> constraint : variable.hardConstraints()) { 061 for (T value : conflictValues(constraint, variable.getInitialAssignment())) { 062 addViolatedInitial(value, variable.getInitialAssignment()); 063 } 064 } 065 } 066 return true; 067 } 068 069 /** Initial values that cannot be assigned when the given value is assigned */ 070 public Set<T> getViolatedInitials(T value) { 071 return iViolatedInitials.get(value); 072 } 073 074 private void addViolatedInitial(T value, T anotherValue) { 075 Set<T> violations = iViolatedInitials.get(value); 076 if (violations == null) { 077 violations = new HashSet<T>(); 078 iViolatedInitials.put(value, violations); 079 } 080 violations.add(anotherValue); 081 } 082 083 private List<T> conflictValues(Constraint<V, T> constraint, T aValue) { 084 List<T> ret = new ArrayList<T>(); 085 for (V variable : constraint.variables()) { 086 if (variable.equals(aValue.variable())) 087 continue; 088 if (variable.getAssignment() != null) 089 continue; 090 for (T value : variable.values()) { 091 if (!constraint.isConsistent(aValue, value)) 092 ret.add(value); 093 } 094 } 095 return ret; 096 } 097}