main page modules namespaces classes files
Gecode home

search for 

photo.cc

Go to the documentation of this file.

/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2001
 *
 *  Last modified:
 *     $Date: 2006-08-04 16:06:52 +0200 (Fri, 04 Aug 2006) $ by $Author: schulte $
 *     $Revision: 3517 $
 *
 *  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.
 *
 */

#include "examples/support.hh"
#include "gecode/minimodel.hh"

class PhotoSpec {
public:
  const int  n_names; 
  const int  n_prefs; 
  const int* prefs;   
  PhotoSpec(const int n_n, const int n_p, const int* p)
    : n_names(n_n), n_prefs(n_p), prefs(p) {}
};

static const int s_prefs[] = {
  0,2, 1,4, 2,3, 2,4, 3,0, 4,3, 4,0, 4,1
};
static const PhotoSpec p_small(5, 8, s_prefs);

static const int l_prefs[] = {
  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
};
static const PhotoSpec p_large(9,17, l_prefs);

class Photo : public Example {
protected:
  const PhotoSpec& spec;
  IntVarArray      pos;
  IntVar           sat;

public:
  Photo(const Options& opt) :
    spec(opt.size == 0 ? p_small : p_large),
    pos(this,spec.n_names, 0, spec.n_names-1),
    sat(this,0,spec.n_prefs)
  {
    BoolVarArgs ful(spec.n_prefs);
    // Map preferences to fulfilment
    for (int i = spec.n_prefs; i--; ) {
      int pa = spec.prefs[2*i+0];
      int pb = spec.prefs[2*i+1];
      ful[i] = post(this,
                    ~(pos[pb]-pos[pa] == 1) ^
                    ~(pos[pa]-pos[pb] == 1));
    }
    // Sum of fulfilment
    {
      IntVarArgs eq(spec.n_prefs+1);
      IntArgs    c(spec.n_prefs+1);
      eq[spec.n_prefs] = sat; c[spec.n_prefs] = -1;
      for (int i = spec.n_prefs; i--; ) {
        eq[i] = ful[i]; c[i] = 1;
      }
      linear(this, c, eq, IRT_EQ, 0);
    }
    distinct(this, pos, opt.icl);

    // Break some symmetries
    rel(this, pos[0], IRT_LE, pos[1]);

    if (opt.naive) {
      branch(this, pos, BVAR_NONE, BVAL_MIN);
    } else {
      branch(this, pos, BVAR_DEGREE_MAX, BVAL_MIN);
    }
  }

  Photo(bool share, Photo& s) :
    Example(share,s), spec(s.spec) {
    pos.update(this, share, s.pos);
    sat.update(this, share, s.sat);
  }

  virtual Space*
  copy(bool share) {
    return new Photo(share,*this);
  }

  virtual void
  print(void) {
    std::cout << "\tpos[] = {";
    for (int i = 0; i < spec.n_names; i++)
      std::cout << pos[i] << ((i<spec.n_names-1)?",":"};\n");
    std::cout << "\tsat: " << sat << std::endl;
  }

  void
  constrain(Space* s) {
    rel(this, sat, IRT_GR, static_cast<Photo*>(s)->sat.val());
  }

};

int
main(int argc, char** argv) {
  Options opt("Photo");
  opt.solutions  = 0;
  opt.size       = 1;
  opt.iterations = 10;
  opt.icl        = ICL_BND;
  opt.parse(argc,argv);
  Example::run<Photo,BAB>(opt);
  return 0;
}


// STATISTICS: example-any