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}