001 package net.sf.cpsolver.ifs.example.csp;
002
003 import java.util.Iterator;
004 import java.util.Random;
005
006 import net.sf.cpsolver.ifs.model.Constraint;
007 import 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 Tomas Muller<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 */
044 public 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 }