    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}