001    package net.sf.cpsolver.ifs.example.csp;
002    
003    import java.util.Random;
004    import java.util.Set;
005    
006    import net.sf.cpsolver.ifs.model.BinaryConstraint;
007    
008    /**
009     * CSP binary constraint. <br>
010     * <br>
011     * This class only implements the generation of a binary CSP constraint and the
012     * consistency check.
013     * 
014     * @version IFS 1.2 (Iterative Forward Search)<br>
015     *          Copyright (C) 2006 - 2010 Tomas Muller<br>
016     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
017     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
018     * <br>
019     *          This library is free software; you can redistribute it and/or modify
020     *          it under the terms of the GNU Lesser General Public License as
021     *          published by the Free Software Foundation; either version 3 of the
022     *          License, or (at your option) any later version. <br>
023     * <br>
024     *          This library is distributed in the hope that it will be useful, but
025     *          WITHOUT ANY WARRANTY; without even the implied warranty of
026     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
027     *          Lesser General Public License for more details. <br>
028     * <br>
029     *          You should have received a copy of the GNU Lesser General Public
030     *          License along with this library; if not see
031     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
032     */
033    public class CSPBinaryConstraint extends BinaryConstraint<CSPVariable, CSPValue> {
034        private boolean iIsConsistent[][] = null;
035        private int iNrCompatiblePairs;
036    
037        /**
038         * Constructor
039         * 
040         * @param nrCompatiblePairs
041         *            number of compatible pairs of values in the constraint
042         */
043        public CSPBinaryConstraint(int id, int nrCompatiblePairs) {
044            super();
045            iId = id;
046            iNrCompatiblePairs = nrCompatiblePairs;
047        }
048    
049        private void swap(int[][] allPairs, int first, int second) {
050            int[] a = allPairs[first];
051            allPairs[first] = allPairs[second];
052            allPairs[second] = a;
053        }
054    
055        /**
056         * Initializes the constraint. Randomly generates the given number of
057         * compatible pairs of values.
058         * 
059         * @param rndNumGen
060         *            random number generator
061         */
062        public void init(Random rndNumGen) {
063            int numberOfAllPairs = first().values().size() * second().values().size();
064            int[][] allPairs = new int[numberOfAllPairs][];
065            int idx = 0;
066    
067            iIsConsistent = new boolean[first().values().size()][second().values().size()];
068    
069            for (CSPValue v1 : first().values()) {
070                for (CSPValue v2 : second().values()) {
071                    iIsConsistent[(int) v1.toDouble()][(int) v2.toDouble()] = false;
072                    allPairs[idx++] = new int[] { (int) v1.toDouble(), (int) v2.toDouble() };
073                }
074            }
075    
076            for (int i = 0; i < iNrCompatiblePairs; i++) {
077                swap(allPairs, i, i + (int) (rndNumGen.nextDouble() * (numberOfAllPairs - i)));
078                iIsConsistent[allPairs[i][0]][allPairs[i][1]] = true;
079            }
080        }
081    
082        /**
083         * True if the pair of given values is compatible.
084         */
085        @Override
086        public boolean isConsistent(CSPValue value1, CSPValue value2) {
087            if (value1 == null || value2 == null)
088                return true;
089            if (isFirst(value1.variable())) {
090                return iIsConsistent[(int) value1.toDouble()][(int) value2.toDouble()];
091            } else {
092                return iIsConsistent[(int) value2.toDouble()][(int) value1.toDouble()];
093            }
094        }
095    
096        /**
097         * Add the other variable to the set of conflicts, if it is not compatible
098         * with the given value.
099         */
100        @Override
101        public void computeConflicts(CSPValue aValue, Set<CSPValue> conflicts) {
102            if (isFirst(aValue.variable())) {
103                if (!isConsistent(aValue, second().getAssignment())) {
104                    conflicts.add(second().getAssignment());
105                }
106            } else {
107                if (!isConsistent(first().getAssignment(), aValue)) {
108                    conflicts.add(first().getAssignment());
109                }
110            }
111        }
112    
113        @Override
114        public String getName() {
115            return "C" + getId();
116        }
117    }