Generated on Sat Jan 12 2019 20:58:51 for Gecode by doxygen 1.8.13
sports-league.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5  *
6  * Contributing authors:
7  * Christian Schulte <schulte@gecode.org>
8  *
9  * Copyright:
10  * Patrick Pekczynski, 2004
11  * Christian Schulte, 2007
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <gecode/driver.hh>
39 #include <gecode/int.hh>
40 #include <gecode/minimodel.hh>
41 
42 #include <algorithm>
43 #include <iomanip>
44 
45 using namespace Gecode;
46 
48 class Play {
49 public:
50  int h;
51  int a;
52  int g;
53  Play(void) : h(0), a(0), g(0) {}
55 };
56 
58 class RRS {
59 protected:
61  const int teams;
65  int weeks(void) const {
66  return teams-1;
67  }
69  int periods(void) const {
70  return teams/2;
71  }
73  int gn(int h, int a) const {
74  return teams*(h-1) + a;
75  }
77  Play& play(int p, int w) {
78  return plays[p*weeks() + w];
79  }
80 public:
106  RRS(int t) : teams(t), plays(new Play[periods()*weeks()]) {
107  // Determine the first game (week 0 period 0)
108  play(0,0).h = 1;
109  play(0,0).a = 2;
110  play(0,0).g = 2;
111 
112  // Determine the other games of the first week
113  for (int p=1; p<periods(); p++) {
114  play(p,0).h = (p + 1) + 1;
115  play(p,0).a = teams - (p + 1 - 2);
116  play(p,0).g = gn(play(p,0).h,play(p,0).a);
117  }
118 
119  // Compute the games for the subsequent weeks
120  for (int w=1; w<weeks(); w++) {
121  for (int p=0; p<periods(); p++) {
122  if (play(p,w-1).h == teams)
123  play(p,w).h = 2;
124  else if (play(p,w-1).h == 1)
125  play(p,w).h = 1;
126  else
127  play(p,w).h = play(p,w-1).h + 1;
128  if (play(p,w-1).a == teams)
129  play(p,w).a = 2;
130  else
131  play(p,w).a = play(p,w-1).a + 1;
132 
133  // maintain symmetry for (h,a): h < a
134  if (play(p,w).h > play(p,w).a)
135  std::swap(play(p,w).h,play(p,w).a);
136 
137  play(p,w).g = gn(play(p,w).h,play(p,w).a);
138  }
139  }
140 
141  }
143  void hag(int w, IntArgs& h, IntArgs& a, IntArgs& g) {
144  for (int p=0; p<periods(); p++) {
145  h[p] = play(p,w).h;
146  a[p] = play(p,w).a;
147  g[p] = play(p,w).g;
148  }
149  }
151  ~RRS(void) {
152  delete [] plays;
153  }
154 };
155 
156 
157 
174 class SportsLeague : public Script {
175 protected:
176  const int teams;
180 
182  int weeks(void) const {
183  return teams-1;
184  }
186  int periods(void) const {
187  return teams/2;
188  }
190  IntVar& h(int p, int w) {
191  return home[p*teams + w];
192  }
194  const IntVar& h(int p, int w) const {
195  return home[p*teams + w];
196  }
198  IntVar& a(int p, int w) {
199  return away[p*teams + w];
200  }
202  const IntVar& a(int p, int w) const {
203  return away[p*teams + w];
204  }
206  IntVar& g(int p, int w) {
207  return game[p*weeks() + w];
208  }
210  const IntVar& g(int p, int w) const {
211  return game[p*weeks() + w];
212  }
213 
214 public:
217  Script(opt),
218  teams(opt.size()),
219  home(*this, periods() * teams, 1, weeks()),
220  away(*this, periods() * teams, 2, weeks()+1),
221  game(*this, weeks()*periods(), 2, teams*weeks())
222  {
223  // Initialize round robin schedule
224  RRS r(teams);
225 
226  // Domain for gamenumber of period
227  for (int w=0; w<weeks(); w++) {
228  IntArgs rh(periods()), ra(periods()), rg(periods());
229  IntVarArgs n(*this,periods(),0,periods()-1);
230 
231  distinct(*this, n, opt.ipl());
232 
233  r.hag(w,rh,ra,rg);
234 
235  for (int p=0; p<periods(); p++) {
236  element(*this, rh, n[p], h(p,w));
237  element(*this, ra, n[p], a(p,w));
238  element(*this, rg, n[p], g(p,w));
239  }
240  }
241 
243  for (int p=0; p<periods(); p++)
244  for (int w=0; w<teams; w++)
245  rel(*this, h(p,w), IRT_LE, a(p,w));
246 
247  // Home teams in first week are ordered
248  {
249  IntVarArgs h0(periods());
250  for (int p=0; p<periods(); p++)
251  h0[p] = h(p,0);
252  rel(*this, h0, IRT_LE);
253  }
254 
255  // Fix first pair
256  rel(*this, h(0,0), IRT_EQ, 1);
257  rel(*this, a(0,0), IRT_EQ, 2);
258 
260  for (int w=0; w<teams; w++) {
261  IntVarArgs c(teams);
262  for (int p=0; p<periods(); p++) {
263  c[2*p] = h(p,w); c[2*p+1] = a(p,w);
264  }
265  distinct(*this, c, opt.ipl());
266  }
267 
269  for (int p=0; p<periods(); p++) {
270  IntVarArgs r(2*teams);
271  for (int t=0; t<teams; t++) {
272  r[2*t] = h(p,t);
273  r[2*t+1] = a(p,t);
274  }
275  IntArgs values(teams);
276  for (int i=1; i<=teams; i++)
277  values[i-1] = i;
278  count(*this, r, IntSet(2,2), values, opt.ipl());
279  }
280 
281  // Redundant constraint
282  for (int p=0; p<periods(); p++)
283  for (int w=0; w<weeks(); w ++)
284  rel(*this, teams * h(p,w) + a(p,w) - g(p,w) == teams);
285 
286  distinct(*this, game, opt.ipl());
287 
288  branch(*this, game, INT_VAR_NONE(), INT_VAL_SPLIT_MIN());
289  }
292  : Script(s), teams(s.teams) {
293  home.update(*this, s.home);
294  away.update(*this, s.away);
295  game.update(*this, s.game);
296  }
298  virtual Space*
299  copy(void) {
300  return new SportsLeague(*this);
301  }
303  virtual void print(std::ostream& os) const {
304  // print period index
305  os << "\t ";
306  for (int p=0; p<periods(); p++) {
307  os << "P[";
308  os.width(2);
309  os << p << "] ";
310  }
311  os << std::endl;
312  // print entries
313  for (int w=0; w<weeks(); w++) {
314  os << "\tW[";
315  os.width(2);
316  os << w+1 << "]: ";
317  for (int p=0; p<periods(); p++) {
318  os.width(2);
319  os << h(p,w).val() << '-';
320  os.width(2);
321  os << a(p,w).val() << " ";
322  }
323  os << std::endl;
324  }
325  }
326 };
327 
328 
332 int
333 main(int argc, char* argv[]) {
334  SizeOptions opt("Sports League Scheduling");
335  opt.ipl(IPL_DOM);
336  opt.size(18);
337  opt.parse(argc,argv);
338  if (opt.size() < 5) {
339  std::cerr<< "No Solution for less than 5 teams!" << std::endl;
340  return 1;
341  }
342  if (opt.size() % 2 != 0) {
343  std::cerr << "Number of teams has to be even!" << std::endl;
344  return 1;
345  }
346  Script::run<SportsLeague, DFS,SizeOptions>(opt);
347  return 0;
348 }
349 
350 // STATISTICS: example-any
const int teams
Number of teams.
void size(unsigned int s)
Set default size.
Definition: options.hpp:586
Round robin schedule.
Options for scripts with additional size parameter
Definition: driver.hh:675
int periods(void) const
Return number of periods.
NodeType t
Type of node.
Definition: bool-expr.cpp:230
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:96
Play * plays
Play information.
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 count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
Definition: count.cpp:40
IntVarArray away
away teams
const IntVar & g(int p, int w) const
Return game number for game in period p and week w.
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:995
const IntVar & a(int p, int w) const
Away team in period p and week w.
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:666
IntVar & a(int p, int w)
Away team in period p and week w.
int main(int argc, char *argv[])
Main-function.
RRS(int t)
Build a feasible schedule.
Integer variable array.
Definition: int.hh:763
void ipl(IntPropLevel i)
Set default integer propagation level.
Definition: options.hpp:216
virtual void print(std::ostream &os) const
Print solution.
Computation spaces.
Definition: core.hpp:1701
Parametric base-class for scripts.
Definition: driver.hh:729
IntVar & g(int p, int w)
Return game number for game in period p and week w.
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
Entry in round robin schedule.
const IntVar & h(int p, int w) const
Home team in period p and week w.
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Equality ( )
Definition: int.hh:926
Options opt
The options.
Definition: test.cpp:97
Gecode::IntArgs i({1, 2, 3, 4})
unsigned int size(I &i)
Size of all ranges of range iterator i.
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl)
Post propagator for for all .
Definition: distinct.cpp:46
SportsLeague(const SizeOptions &opt)
Setup model.
Less ( )
Definition: int.hh:929
Integer sets.
Definition: int.hh:174
Example: Sports league scheduling
~RRS(void)
Delete schedule.
Passing integer variables.
Definition: int.hh:656
Passing integer arguments.
Definition: int.hh:628
int h
home team
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
int a
away team
int g
game number Default constructor
int periods(void) const
Return number of periods.
Integer variables.
Definition: int.hh:371
SportsLeague(SportsLeague &s)
Constructor for cloning s.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
Domain propagation Options: basic versus advanced propagation.
Definition: int.hh:979
Play & play(int p, int w)
Play for period p and week w.
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
Definition: minimodel.hh:1993
void hag(int w, IntArgs &h, IntArgs &a, IntArgs &g)
Home, away, and game information.
int gn(int h, int a) const
Game number for game between home team h and away team a.
const int teams
number of teams
IntValBranch INT_VAL_SPLIT_MIN(void)
Select values not greater than mean of smallest and largest value.
Definition: val.hpp:75
Gecode toplevel namespace
IntVarArray game
game numbers
virtual Space * copy(void)
Copy during cloning.
int weeks(void) const
Return number of weeks.
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.
void element(Home home, IntSharedArray c, IntVar x0, IntVar x1, IntPropLevel)
Post domain consistent propagator for .
Definition: element.cpp:39
int weeks(void) const
Return number of weeks.
T * a
Element array.
Definition: array.hpp:526
IntVarArray home
home teams
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
Definition: irt.hpp:37
IntVar & h(int p, int w)
Home team in period p and week w.