    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}