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