main page modules namespaces classes files
Gecode/J home

Photo.java

Go to the documentation of this file.

/*
 *  Main authors:
 *     Mikael Lagerkvist <lagerkvist@gecode.org>
 *     Guido Tack <tack@gecode.org>
 *
 *  Copyright:
 *     Mikael Lagerkvist, 2006
 *     Guido Tack, 2006
 *
 *  Last modified:
 *     $Date: 2006-09-26 16:26:14 +0200 (Tue, 26 Sep 2006) $ by $Author: zayenz $
 *     $Revision: 3704 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  See the file "LICENSE" for information on usage and
 *  redistribution of this file, and for a
 *     DISCLAIMER OF ALL WARRANTIES.
 *
 */

package examples;

import static org.gecode.Gecode.*;
import static org.gecode.GecodeEnumConstants.*;

import org.gecode.*;
import org.gecode.explorer.Explorer;

public class Photo extends Space {

    public VarArray<IntVar> pos;
    public IntVar sat;
    private PhotoSpec spec;

    public void constrain(Space oldSol) {
        rel(this, sat, IRT_GR, ((Photo)oldSol).sat.val(), ICL_DEF);
    }


    public Photo(PhotoSpec s) {
        super();
        spec = s;
        pos  = new VarArray<IntVar>(this, s.n_names(), IntVar.class, 0, spec.n_names()-1);
        sat  = new IntVar(this, new IntSet(0, spec.n_prefs()));

        VarArray<BoolVar> ful = new VarArray<BoolVar>(this, spec.n_prefs(), BoolVar.class);

        // Map preferences to fulfilment
        for (int i = 0; i<spec.n_prefs(); i++) {
            // Preferences
            int pa = spec.prefs[2*i+0];
            int pb = spec.prefs[2*i+1];
            // True iff pos(pb)-pos(pa)==1
            BoolVar b0 = new BoolVar(this);
            // True iff pos(pa)-pos(pb)==1
            BoolVar b1 = new BoolVar(this);            

            int coeffs[] = {1,-1};
            VarArray<IntVar> args1 = 
                new VarArray<IntVar>(pos.get(pb),
                                     pos.get(pa));

            VarArray<IntVar> args2 = 
                new VarArray<IntVar>(pos.get(pa),
                                     pos.get(pb));

            linear(this, coeffs,args1,
                   IRT_EQ, 1, b0, ICL_DEF);
            linear(this, coeffs,args2,
                          IRT_EQ, 1, b1, ICL_DEF);
            // ful.get(i) true iff |pos(pa)-pos(pb)|==1
            bool_xor(this, b0,b1,ful.get(i));
        }
        // Sum of fulfilment
        {
            VarArray<IntVar> eq = new VarArray<IntVar>(ful);
            int c[]= new int[spec.n_prefs()+1];
            for (int i = 0; i<spec.n_prefs(); i++ ) {
                c[i] = 1;
            }
            eq.add(spec.n_prefs(), sat); c[spec.n_prefs()] = -1;
            linear(this, c, eq, IRT_EQ, 0, ICL_DEF);
        }
        distinct(this, pos, ICL_DEF);
        rel(this, pos.get(0), IRT_LE, pos.get(1), ICL_DEF);
        branch(this, pos, BVAR_NONE, BVAL_MIN);
    }

    public Photo(Boolean share, Photo photo) {
        super(share, photo);

        spec = photo.spec;
        
        pos = new VarArray<IntVar>(this, share, photo.pos);
        sat = photo.sat.copy(this, share);
    }

    public static void main(String []args) {
        Options opt = new Options("Photo");
        opt.size = 0;
        opt.bab = true;
        opt.gui = true;
        opt.solutions = 0;
        opt.parse(args, specs.length);

        Photo p = new Photo(specs[opt.size]);   
        opt.doSearch(p);
    }



    // Specifications
    private static PhotoSpec[] specs;
    static {
        specs = new PhotoSpec[2];
        specs[0] = new Small();
        specs[1] = new Large();
    }

    static class PhotoSpec {
        public int n_names() {
            int n = -1;
            for (int i: prefs) n = Math.max(n, i);
            return n+1;
        }
        public int n_prefs() {
            return prefs.length / 2;
        }
        public int prefs[];
    }
    
    static class Small extends PhotoSpec {
        public Small() {
            int tmp[] = {
                0,2, 1,4, 2,3, 2,4, 3,0, 4,3, 4,0, 4,1
            };
            prefs = tmp;
        }
    }
    
    static class Large extends PhotoSpec {
        public Large() {
            int tmp[] = {
                0,2, 0,4, 0,7, 1,4, 1,8, 2,3, 2,4, 3,0, 3,4, 
                4,5, 4,0, 5,0, 5,8, 6,2, 6,7, 7,8, 7,6
            };
            prefs = tmp;
        }
    }
}