001package net.sf.cpsolver.ifs.example.csp; 002 003import java.util.Iterator; 004import java.util.Random; 005 006import net.sf.cpsolver.ifs.model.Constraint; 007import net.sf.cpsolver.ifs.model.Model; 008 009/** 010 * Random Binary CSP with uniform distribution. <br> 011 * <br> 012 * A random CSP is defined by a four-tuple (n, d, p1, p2), where n denotes the 013 * number of variables and d denotes the domain size of each variable, p1 and p2 014 * are two probabilities. They are used to generate randomly the binary 015 * constraints among the variables. p1 represents the probability that a 016 * constraint exists between two different variables and p2 represents the 017 * probability that a pair of values in the domains of two variables connected 018 * by a constraint are incompatible. <br> 019 * <br> 020 * We use a so called model B of Random CSP (n, d, n1, n2) where n1 = 021 * p1*n*(n-1)/2 pairs of variables are randomly and uniformly selected and 022 * binary constraints are posted between them. For each constraint, n2 = p1*d^2 023 * randomly and uniformly selected pairs of values are picked as incompatible. 024 * 025 * @version IFS 1.2 (Iterative Forward Search)<br> 026 * Copyright (C) 2006 - 2010 Tomáš Müller<br> 027 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 028 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 029 * <br> 030 * This library is free software; you can redistribute it and/or modify 031 * it under the terms of the GNU Lesser General Public License as 032 * published by the Free Software Foundation; either version 3 of the 033 * License, or (at your option) any later version. <br> 034 * <br> 035 * This library is distributed in the hope that it will be useful, but 036 * WITHOUT ANY WARRANTY; without even the implied warranty of 037 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 038 * Lesser General Public License for more details. <br> 039 * <br> 040 * You should have received a copy of the GNU Lesser General Public 041 * License along with this library; if not see 042 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 043 */ 044public class CSPModel extends Model<CSPVariable, CSPValue> { 045 046 /** 047 * Constructor 048 * 049 * @param nrVariables 050 * number of variables in the problem 051 * @param nrValues 052 * number of values of each variable 053 * @param nrConstraints 054 * number of constraints in the problem 055 * @param nrCompatiblePairs 056 * number of compatible pairs of values for every constraint 057 * @param seed 058 * seed for random number generator (use 059 * {@link System#currentTimeMillis} if not bother) 060 */ 061 public CSPModel(int nrVariables, int nrValues, int nrConstraints, int nrCompatiblePairs, long seed) { 062 generate(nrVariables, nrValues, nrConstraints, nrCompatiblePairs, seed); 063 } 064 065 public CSPModel() { 066 } 067 068 private void swap(CSPVariable[][] allPairs, int first, int second) { 069 CSPVariable[] a = allPairs[first]; 070 allPairs[first] = allPairs[second]; 071 allPairs[second] = a; 072 } 073 074 private void buildBinaryConstraintGraph(Random rnd) { 075 int numberOfAllPairs = variables().size() * (variables().size() - 1) / 2; 076 CSPVariable[][] allPairs = new CSPVariable[numberOfAllPairs][]; 077 int idx = 0; 078 for (CSPVariable v1 : variables()) { 079 for (CSPVariable v2 : variables()) { 080 if (v1.getId() >= v2.getId()) 081 continue; 082 allPairs[idx++] = new CSPVariable[] { v1, v2 }; 083 } 084 } 085 idx = 0; 086 for (Iterator<Constraint<CSPVariable, CSPValue>> i = constraints().iterator(); i.hasNext();) { 087 CSPBinaryConstraint c = (CSPBinaryConstraint) i.next(); 088 swap(allPairs, idx, idx + (int) (rnd.nextDouble() * (numberOfAllPairs - idx))); 089 c.addVariable(allPairs[idx][0]); 090 c.addVariable(allPairs[idx][1]); 091 c.init(rnd); 092 idx++; 093 } 094 } 095 096 private void generate(int nrVariables, int nrValues, int nrConstraints, int nrCompatiblePairs, long seed) { 097 Random rnd = new Random(seed); 098 099 for (int i = 0; i < nrVariables; i++) { 100 CSPVariable var = new CSPVariable(i + 1, nrValues); 101 addVariable(var); 102 } 103 104 for (int i = 0; i < nrConstraints; i++) { 105 CSPBinaryConstraint c = new CSPBinaryConstraint(i + 1, nrCompatiblePairs); 106 addConstraint(c); 107 } 108 109 buildBinaryConstraintGraph(rnd); 110 } 111}