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