    001    package ifs.example.csp;
    002
    003    import ifs.util.*;
    004    import ifs.model.*;
    005    import java.util.*;
    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     * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomáš Müller</a>
    021     * @version 1.0
    022     */
    023    public class CSPModel extends Model {
    024
    025        /**
    026         * Constructor
    027         * @param nrVariables number of variables in the problem
    028         * @param nrValues number of values of each variable
    029         * @param nrConstraints number of constraints in the problem
    030         * @param nrCompatiblePairs number of compatible pairs of values for every constraint
    031         * @param seed seed for random number generator (use {@link System#currentTimeMillis} if not bother)
    032         */
    033        public CSPModel(int nrVariables, int nrValues, int nrConstraints, int nrCompatiblePairs, long seed) {
    034            generate(nrVariables, nrValues, nrConstraints, nrCompatiblePairs, seed);
    035        }
    036
    037        private void swap(Variable[][] allPairs, int first, int second) {
    038            Variable[] a = allPairs[first];
    039            allPairs[first]=allPairs[second];
    040            allPairs[second]=a;
    041        }
    042
    043        private void buildBinaryConstraintGraph(Random rnd) {
    044            int numberOfAllPairs = variables().size()*(variables().size()-1)/2;
    045            Variable[][] allPairs = new Variable[numberOfAllPairs][];
    046            int idx=0;
    047            for (Enumeration i1=variables().elements();i1.hasMoreElements();) {
    048                Variable v1 = (Variable)i1.nextElement();
    049                for (Enumeration i2=variables().elements();i2.hasMoreElements();) {
    050                    Variable v2 = (Variable)i2.nextElement();
    051                    if (v1.getId()>=v2.getId()) continue;
    052                    allPairs[idx++]=new Variable[] {v1,v2};
    053                }
    054            }
    055            idx = 0;
    056            for (Enumeration i1=constraints().elements();i1.hasMoreElements();) {
    057                CSPBinaryConstraint c = (CSPBinaryConstraint) i1.nextElement();
    058                swap(allPairs, idx, idx+(int)(rnd.nextDouble()*(numberOfAllPairs-idx)));
    059                c.addVariable(allPairs[idx][0]);
    060                c.addVariable(allPairs[idx][1]);
    061                c.init(rnd);
    062                idx++;
    063            }
    064        }
    065
    066        private void generate(int nrVariables, int nrValues, int nrConstraints, int nrCompatiblePairs, long seed) {
    067            Random rnd = new Random(seed);
    068
    069            for (int i=0;i<nrVariables;i++) {
    070                CSPVariable var = new CSPVariable(i+1,nrValues);
    071                addVariable(var);
    072            }
    073
    074            for (int i=0;i<nrConstraints;i++) {
    075                CSPBinaryConstraint c = new CSPBinaryConstraint(i+1,nrCompatiblePairs);
    076                addConstraint(c);
    077            }
    078
    079            buildBinaryConstraintGraph(rnd);
    080        }
    081    }