main page modules namespaces classes files
Gecode/J home

Steiner.java

Go to the documentation of this file.

/* -*- indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Mikael Lagerkvist <lagerkvist@gecode.org>
 *     Guido Tack <tack@gecode.org>
 *
 *  Copyright:
 *     Mikael Lagerkvist, 2006
 *     Guido Tack, 2006
 *
 *  Last modified:
 *     $Date: 2006-10-31 16:52:38 +0100 (Tue, 31 Oct 2006) $ by $Author: zayenz $
 *     $Revision: 3843 $
 *
 *  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.*;

public class Steiner extends Space {

  public VarArray<SetVar> root;

  static int n = 9;
  static int n1 = n+1;
  static int n1n1 = n1*n1;
  static int len = (n*(n-1)) / 6;

  public Steiner() {
    super();

    root = new VarArray<SetVar>(this, len, SetVar.class);
    for (int i=0; i<len; i++) {
      dom(this, root.get(i), SRT_SUB, 1,n);
      cardinality(this, root.get(i), 3,3);
    }

    for (int i=0; i<len; i++) {
      for (int j=i+1; j<len; j++) {
        SetVar s = new SetVar(this);
        SetVar x = root.get(i);
        SetVar y = root.get(j);

        cardinality(this, s,0,1);
        rel(this, x, SOT_INTER, y, SRT_EQ, s);

        IntVar x1 = new IntVar(this, 1, n);
        IntVar x2 = new IntVar(this, 1, n);
        IntVar x3 = new IntVar(this, 1, n);
        IntVar y1 = new IntVar(this, 1, n);
        IntVar y2 = new IntVar(this, 1, n);
        IntVar y3 = new IntVar(this, 1, n);

        /* First alternative:
         * Using "the" and sequence constraints
         * Gives best propagation
         */
        {
          SetVar temp20 = new SetVar(this);
          SetVar temp21 = new SetVar(this);
          SetVar temp22 = new SetVar(this);
          SetVar temp23 = new SetVar(this);
          SetVar temp24 = new SetVar(this);
          SetVar temp25 = new SetVar(this);
          rel(this, temp20, SRT_EQ, x1);
          rel(this, temp21, SRT_EQ, x2);
          rel(this, temp22, SRT_EQ, x3);
          rel(this, temp23, SRT_EQ, y1);
          rel(this, temp24, SRT_EQ, y2);
          rel(this, temp25, SRT_EQ, y3);
          VarArray<SetVar> xargs = new VarArray<SetVar>(temp20, temp21, temp22);
          VarArray<SetVar> yargs = new VarArray<SetVar>(temp23, temp24, temp25);

          sequentialUnion(this, xargs, x);
          sequentialUnion(this, yargs, y);
        }

        /* Breaking symmetries */

        rel(this, x1,IRT_LE,x2,ICL_DEF);
        rel(this, x2,IRT_LE,x3,ICL_DEF);
        rel(this, x1,IRT_LE,x3,ICL_DEF);
                
        rel(this, y1,IRT_LE,y2,ICL_DEF);
        rel(this, y2,IRT_LE,y3,ICL_DEF);
        rel(this, y1,IRT_LE,y3,ICL_DEF);

        int ia[] = {n1n1,n1,1,-n1n1,-n1,-1};
        VarArray<IntVar> iva = 
          new VarArray<IntVar>(x1, x2, x3, y1, y2, y3);

        linear(this, ia, iva, IRT_LE, 0, ICL_DEF);
      }
    }

    branch(this, root, SETBVAR_NONE, SETBVAL_MIN);        
  }

  public Steiner(Boolean share, Steiner steiner) {
    super(share, steiner);
    root = new VarArray<SetVar>(this, share, steiner.root);
  }

  public static void main(String[] args) {
    Options opt = new Options("Steiner");
    opt.size = 0;
    opt.gui = false;
    opt.solutions = 1;
    opt.parse(args);

    Steiner steiner = new Steiner();

    opt.doSearch(steiner);
  }
}