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}