    001    package ifs.example.csp;
    002
    003    import ifs.model.*;
    004    import java.util.*;
    005
    006    /**
    007     * CSP binary constraint.
    008     * <br><br>
    009     * This class only implements the generation of a binary CSP constraint and the consistency check.
    010     *
    011     * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomáš Müller</a>
    012     * @version 1.0
    013     */
    014    public class CSPBinaryConstraint extends BinaryConstraint {
    015        private int iId = 0;
    016        private boolean iIsConsistent[][] = null;
    017        private int iNrCompatiblePairs;
    018
    019        /** Constructor
    020         * @param nrCompatiblePairs number of compatible pairs of values in the constraint
    021         */
    022        public CSPBinaryConstraint(int id, int nrCompatiblePairs) {
    023            super();
    024            iId = id;
    025            iNrCompatiblePairs = nrCompatiblePairs;
    026        }
    027
    028        private void swap(int[][] allPairs, int first, int second) {
    029            int[] a = allPairs[first];
    030            allPairs[first] = allPairs[second];
    031            allPairs[second] = a;
    032        }
    033
    034        /**
    035         * Initializes the constraint. Randomly generates the given number of compatible pairs of values.
    036         * @param rndNumGen random number generator
    037         */
    038        public void init(Random rndNumGen) {
    039            int numberOfAllPairs = first().values().size() * second().values().size();
    040            int[][] allPairs = new int[numberOfAllPairs][];
    041            int idx = 0;
    042
    043            iIsConsistent = new boolean[first().values().size()][second().values().size()];
    044
    045            for (Enumeration i1=first().values().elements();
    046            i1.hasMoreElements();) {
    047                CSPValue v1 = (CSPValue)i1.nextElement();
    048                for (Enumeration i2=second().values().elements();
    049                i2.hasMoreElements();) {
    050                    CSPValue v2 = (CSPValue)i2.nextElement();
    051                    iIsConsistent[v1.toInt()][v2.toInt()] = false;
    052                    allPairs[idx++] = new int[] {v1.toInt(), v2.toInt()};
    053                }
    054            }
    055
    056            for (int i=0; i<iNrCompatiblePairs; i++) {
    057                swap(allPairs, i, i+(int)(rndNumGen.nextDouble()*(numberOfAllPairs-i)));
    058                iIsConsistent[allPairs[i][0]][allPairs[i][1]] = true;
    059            }
    060        }
    061
    062        /**
    063         * True if the pair of given values is compatible.
    064         */
    065        public boolean isConsistent(Value value1, Value value2) {
    066            if (value1==null || value2==null) return true;
    067            if (isFirst(value1.variable())) {
    068                return iIsConsistent[value1.toInt()][value2.toInt()];
    069            } else {
    070                return iIsConsistent[value2.toInt()][value1.toInt()];
    071            }
    072        }
    073
    074        /**
    075         * Add the other variable to the set of conflicts, if it is not compatible with the given value.
    076         */
    077        public void computeConflicts(Value aValue, Set conflicts) {
    078            if (isFirst(aValue.variable())) {
    079                if (!isConsistent(aValue, second().getAssignment())) {
    080                    conflicts.add(second().getAssignment());
    081                }
    082            } else {
    083                if (!isConsistent(first().getAssignment(), aValue)) {
    084                    conflicts.add(first().getAssignment());
    085                }
    086            }
    087        }
    088
    089        public String getName() { return "C"+getId(); }
    090    }