Generated on Sat Jun 2 2018 07:17:44 for Gecode by doxygen 1.8.13
steiner.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Guido Tack <tack@gecode.org>
5  *
6  * Copyright:
7  * Guido Tack, 2004
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include <gecode/driver.hh>
35 #include <gecode/int.hh>
36 #include <gecode/set.hh>
37 
38 using namespace Gecode;
39 
48 class Steiner : public Script {
49 public:
51  enum {
54  MODEL_SEQ
55  };
57  int n;
60 
63 
66  : Script(opt), n(opt.size()), noOfTriples((n*(n-1))/6),
67  triples(*this, noOfTriples, IntSet::empty, 1, n, 3U, 3U) {
68 
69  for (int i=0; i<noOfTriples; i++) {
70  for (int j=i+1; j<noOfTriples; j++) {
71  SetVar x = triples[i];
72  SetVar y = triples[j];
73 
74  SetVar atmostOne(*this,IntSet::empty,1,n,0U,1U);
75  rel(*this, (x & y) == atmostOne);
76 
77  IntVar x1(*this,1,n);
78  IntVar x2(*this,1,n);
79  IntVar x3(*this,1,n);
80  IntVar y1(*this,1,n);
81  IntVar y2(*this,1,n);
82  IntVar y3(*this,1,n);
83 
84  if (opt.model() == MODEL_NONE) {
85  /* Naive alternative:
86  * just including the ints in the set
87  */
88  rel(*this, singleton(x1) <= x);
89  rel(*this, singleton(x2) <= x);
90  rel(*this, singleton(x3) <= x);
91  rel(*this, singleton(y1) <= y);
92  rel(*this, singleton(y2) <= y);
93  rel(*this, singleton(y3) <= y);
94 
95  } else if (opt.model() == MODEL_MATCHING) {
96  /* Smart alternative:
97  * Using matching constraints
98  */
99 
100  channelSorted(*this, IntVarArgs()<<x1<<x2<<x3, x);
101  channelSorted(*this, IntVarArgs()<<y1<<y2<<y3, y);
102  } else if (opt.model() == MODEL_SEQ) {
103  SetVar sx1 = expr(*this, singleton(x1));
104  SetVar sx2 = expr(*this, singleton(x2));
105  SetVar sx3 = expr(*this, singleton(x3));
106  SetVar sy1 = expr(*this, singleton(y1));
107  SetVar sy2 = expr(*this, singleton(y2));
108  SetVar sy3 = expr(*this, singleton(y3));
109  sequence(*this,SetVarArgs()<<sx1<<sx2<<sx3,x);
110  sequence(*this,SetVarArgs()<<sy1<<sy2<<sy3,y);
111  }
112 
113  /* Breaking symmetries */
114  rel(*this, x1 < x2);
115  rel(*this, x2 < x3);
116  rel(*this, x1 < x3);
117 
118  rel(*this, y1 < y2);
119  rel(*this, y2 < y3);
120  rel(*this, y1 < y3);
121 
122  linear(*this, IntArgs(6,(n+1)*(n+1),n+1,1,-(n+1)*(n+1),-(n+1),-1),
123  IntVarArgs()<<x1<<x2<<x3<<y1<<y2<<y3, IRT_LE, 0);
124  }
125  }
126 
127  branch(*this, triples, SET_VAR_NONE(), SET_VAL_MIN_INC());
128  }
130  virtual void
131  print(std::ostream& os) const {
132  for (int i=0; i<noOfTriples; i++) {
133  os << "\t[" << i << "] = " << triples[i] << std::endl;
134  }
135  }
137  Steiner(Steiner& s) : Script(s), n(s.n), noOfTriples(s.noOfTriples) {
138  triples.update(*this, s.triples);
139  }
141  virtual Space*
142  copy(void) {
143  return new Steiner(*this);
144  }
145 };
146 
150 int
151 main(int argc, char* argv[]) {
152  SizeOptions opt("Steiner");
154  opt.model(Steiner::MODEL_NONE, "rel", "Use simple relation constraints");
155  opt.model(Steiner::MODEL_MATCHING, "matching", "Use matching constraints");
156  opt.model(Steiner::MODEL_SEQ, "sequence", "Use sequence constraints");
157  opt.size(9);
158  opt.iterations(20);
159  opt.parse(argc,argv);
160  Script::run<Steiner,DFS,SizeOptions>(opt);
161  return 0;
162 }
163 
164 
165 // STATISTICS: example-any
166 
Steiner(const SizeOptions &opt)
Actual model.
Definition: steiner.cpp:65
void size(unsigned int s)
Set default size.
Definition: options.hpp:586
void channelSorted(Home home, const IntVarArgs &x, SetVar y)
Definition: channel.cpp:45
SetExpr singleton(const LinIntExpr &e)
Singleton expression.
Definition: set-expr.cpp:690
Options for scripts with additional size parameter
Definition: driver.hh:675
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel)
Post propagator for .
Definition: sequence.cpp:47
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf, FloatVarValPrint vvp)
Branch over x with variable selection vars and value selection vals.
Definition: branch.cpp:39
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1056
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:666
int n
Order of the Steiner problem.
Definition: steiner.cpp:57
int main(int argc, char *argv[])
Main-function.
Definition: steiner.cpp:151
Use simple relation constraint.
Definition: steiner.cpp:52
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition: linear.cpp:41
virtual void print(std::ostream &os) const
Print solution.
Definition: steiner.cpp:131
Steiner(Steiner &s)
Constructor for copying s.
Definition: steiner.cpp:137
SetVarBranch SET_VAR_NONE(void)
Definition: var.hpp:96
Computation spaces.
Definition: core.hpp:1701
Parametric base-class for scripts.
Definition: driver.hh:729
void iterations(unsigned int i)
Set default number of iterations.
Definition: options.hpp:461
Gecode::IntArgs i(4, 1, 2, 3, 4)
Options opt
The options.
Definition: test.cpp:97
Use matching constraints.
Definition: steiner.cpp:53
SetVarArray triples
The steiner triples.
Definition: steiner.cpp:62
Use sequence constraints.
Definition: steiner.cpp:54
unsigned int size(I &i)
Size of all ranges of range iterator i.
Less ( )
Definition: int.hh:904
Integer sets.
Definition: int.hh:170
Passing integer variables.
Definition: int.hh:633
Passing integer arguments.
Definition: int.hh:604
SetValBranch SET_VAL_MIN_INC(void)
Definition: val.hpp:55
static const IntSet empty
Empty set.
Definition: int.hh:259
BoolVar expr(Home home, const BoolExpr &e, IntPropLevel ipl)
Post Boolean expression and return its value.
Definition: bool-expr.cpp:628
void atmostOne(Home home, const SetVarArgs &xa, unsigned int c)
Definition: distinct.cpp:41
Passing set variables.
Definition: set.hh:488
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:765
Set variables
Definition: set.hh:127
virtual Space * copy(void)
Copy during cloning.
Definition: steiner.cpp:142
Integer variables.
Definition: int.hh:347
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
int noOfTriples
Number of Steiner triples.
Definition: steiner.cpp:59
Post propagator for SetVar x
Definition: set.hh:765
Set variable array
Definition: set.hh:568
void model(int v)
Set default model value.
Definition: options.hpp:177
Gecode toplevel namespace
Example: Steiner triples
Definition: steiner.cpp:48