    001package net.sf.cpsolver.ifs.example.csp;
    002
    003import java.util.Random;
    004import java.util.Set;
    005
    006import 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 Tomáš Müller<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 */
    033public 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}