001    package net.sf.cpsolver.ifs.extension;
002    
003    import java.util.ArrayList;
004    import java.util.HashSet;
005    import java.util.HashMap;
006    import java.util.List;
007    import java.util.Map;
008    import java.util.Set;
009    
010    import net.sf.cpsolver.ifs.model.Constraint;
011    import net.sf.cpsolver.ifs.model.Value;
012    import net.sf.cpsolver.ifs.model.Variable;
013    import net.sf.cpsolver.ifs.solver.Solver;
014    import 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 Tomas Muller<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     */
046    public 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    }