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