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