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