Generated on Sat Oct 20 2018 12:43:45 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, {x1,x2,x3}, x);
101  channelSorted(*this, {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,{sx1,sx2,sx3},x);
110  sequence(*this,{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,
123  {(n+1)*(n+1), n+1, 1, -(n+1)*(n+1), -(n+1), -1},
124  {x1, x2, x3, y1, y2, y3},
125  IRT_LE, 0);
126  }
127  }
128 
129  branch(*this, triples, SET_VAR_NONE(), SET_VAL_MIN_INC());
130  }
132  virtual void
133  print(std::ostream& os) const {
134  for (int i=0; i<noOfTriples; i++) {
135  os << "\t[" << i << "] = " << triples[i] << std::endl;
136  }
137  }
139  Steiner(Steiner& s) : Script(s), n(s.n), noOfTriples(s.noOfTriples) {
140  triples.update(*this, s.triples);
141  }
143  virtual Space*
144  copy(void) {
145  return new Steiner(*this);
146  }
147 };
148 
152 int
153 main(int argc, char* argv[]) {
154  SizeOptions opt("Steiner");
156  opt.model(Steiner::MODEL_NONE, "rel", "Use simple relation constraints");
157  opt.model(Steiner::MODEL_MATCHING, "matching", "Use matching constraints");
158  opt.model(Steiner::MODEL_SEQ, "sequence", "Use sequence constraints");
159  opt.size(9);
160  opt.iterations(20);
161  opt.parse(argc,argv);
162  Script::run<Steiner,DFS,SizeOptions>(opt);
163  return 0;
164 }
165 
166 
167 // STATISTICS: example-any
168 
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:691
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:995
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:153
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:133
Steiner(Steiner &s)
Constructor for copying s.
Definition: steiner.cpp:139
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
Options opt
The options.
Definition: test.cpp:97
Use matching constraints.
Definition: steiner.cpp:53
SetVarArray triples
The steiner triples.
Definition: steiner.cpp:62
Gecode::IntArgs i({1, 2, 3, 4})
Use sequence constraints.
Definition: steiner.cpp:54
unsigned int size(I &i)
Size of all ranges of range iterator i.
Less ( )
Definition: int.hh:929
Integer sets.
Definition: int.hh:174
SetValBranch SET_VAL_MIN_INC(void)
Definition: val.hpp:55
static const IntSet empty
Empty set.
Definition: int.hh:283
BoolVar expr(Home home, const BoolExpr &e, IntPropLevel ipl)
Post Boolean expression and return its value.
Definition: bool-expr.cpp:627
void atmostOne(Home home, const SetVarArgs &xa, unsigned int c)
Definition: distinct.cpp:41
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
Set variables
Definition: set.hh:127
virtual Space * copy(void)
Copy during cloning.
Definition: steiner.cpp:144
Integer variables.
Definition: int.hh:371
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:767
Set variable array
Definition: set.hh:570
void model(int v)
Set default model value.
Definition: options.hpp:177
Gecode toplevel namespace
Example: Steiner triples
Definition: steiner.cpp:48