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 }