Generated on Sat Feb 7 2015 02:01:13 for Gecode by doxygen 1.8.9.1
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  * Last modified:
14  * $Date: 2013-07-08 14:22:40 +0200 (Mon, 08 Jul 2013) $ by $Author: schulte $
15  * $Revision: 13820 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 #include <gecode/driver.hh>
43 #include <gecode/int.hh>
44 #include <gecode/minimodel.hh>
45 
46 #include <algorithm>
47 #include <iomanip>
48 
49 using namespace Gecode;
50 
52 class Play {
53 public:
54  int h;
55  int a;
56  int g;
57  Play(void) : h(0), a(0), g(0) {}
59 };
60 
62 class RRS {
63 protected:
65  const int teams;
69  int weeks(void) const {
70  return teams-1;
71  }
73  int periods(void) const {
74  return teams/2;
75  }
77  int gn(int h, int a) const {
78  return teams*(h-1) + a;
79  }
81  Play& play(int p, int w) {
82  return plays[p*weeks() + w];
83  }
84 public:
110  RRS(int t) : teams(t), plays(new Play[periods()*weeks()]) {
111  // Determine the first game (week 0 period 0)
112  play(0,0).h = 1;
113  play(0,0).a = 2;
114  play(0,0).g = 2;
115 
116  // Determine the other games of the first week
117  for (int p=1; p<periods(); p++) {
118  play(p,0).h = (p + 1) + 1;
119  play(p,0).a = teams - (p + 1 - 2);
120  play(p,0).g = gn(play(p,0).h,play(p,0).a);
121  }
122 
123  // Compute the games for the subsequent weeks
124  for (int w=1; w<weeks(); w++) {
125  for (int p=0; p<periods(); p++) {
126  if (play(p,w-1).h == teams)
127  play(p,w).h = 2;
128  else if (play(p,w-1).h == 1)
129  play(p,w).h = 1;
130  else
131  play(p,w).h = play(p,w-1).h + 1;
132  if (play(p,w-1).a == teams)
133  play(p,w).a = 2;
134  else
135  play(p,w).a = play(p,w-1).a + 1;
136 
137  // maintain symmetry for (h,a): h < a
138  if (play(p,w).h > play(p,w).a)
139  std::swap(play(p,w).h,play(p,w).a);
140 
141  play(p,w).g = gn(play(p,w).h,play(p,w).a);
142  }
143  }
144 
145  }
147  void hag(int w, IntArgs& h, IntArgs& a, IntArgs& g) {
148  for (int p=0; p<periods(); p++) {
149  h[p] = play(p,w).h;
150  a[p] = play(p,w).a;
151  g[p] = play(p,w).g;
152  }
153  }
155  ~RRS(void) {
156  delete [] plays;
157  }
158 };
159 
160 
161 
178 class SportsLeague : public Script {
179 protected:
180  const int teams;
184 
186  int weeks(void) const {
187  return teams-1;
188  }
190  int periods(void) const {
191  return teams/2;
192  }
194  IntVar& h(int p, int w) {
195  return home[p*teams + w];
196  }
198  const IntVar& h(int p, int w) const {
199  return home[p*teams + w];
200  }
202  IntVar& a(int p, int w) {
203  return away[p*teams + w];
204  }
206  const IntVar& a(int p, int w) const {
207  return away[p*teams + w];
208  }
210  IntVar& g(int p, int w) {
211  return game[p*weeks() + w];
212  }
214  const IntVar& g(int p, int w) const {
215  return game[p*weeks() + w];
216  }
217 
218 public:
221  teams(opt.size()),
222  home(*this, periods() * teams, 1, weeks()),
223  away(*this, periods() * teams, 2, weeks()+1),
224  game(*this, weeks()*periods(), 2, teams*weeks())
225  {
226  // Initialize round robin schedule
227  RRS r(teams);
228 
229  // Domain for gamenumber of period
230  for (int w=0; w<weeks(); w++) {
231  IntArgs rh(periods()), ra(periods()), rg(periods());
232  IntVarArgs n(*this,periods(),0,periods()-1);
233 
234  distinct(*this, n, opt.icl());
235 
236  r.hag(w,rh,ra,rg);
237 
238  for (int p=0; p<periods(); p++) {
239  element(*this, rh, n[p], h(p,w));
240  element(*this, ra, n[p], a(p,w));
241  element(*this, rg, n[p], g(p,w));
242  }
243  }
244 
246  for (int p=0; p<periods(); p++)
247  for (int w=0; w<teams; w++)
248  rel(*this, h(p,w), IRT_LE, a(p,w));
249 
250  // Home teams in first week are ordered
251  {
252  IntVarArgs h0(periods());
253  for (int p=0; p<periods(); p++)
254  h0[p] = h(p,0);
255  rel(*this, h0, IRT_LE);
256  }
257 
258  // Fix first pair
259  rel(*this, h(0,0), IRT_EQ, 1);
260  rel(*this, a(0,0), IRT_EQ, 2);
261 
263  for (int w=0; w<teams; w++) {
264  IntVarArgs c(teams);
265  for (int p=0; p<periods(); p++) {
266  c[2*p] = h(p,w); c[2*p+1] = a(p,w);
267  }
268  distinct(*this, c, opt.icl());
269  }
270 
272  for (int p=0; p<periods(); p++) {
273  IntVarArgs r(2*teams);
274  for (int t=0; t<teams; t++) {
275  r[2*t] = h(p,t);
276  r[2*t+1] = a(p,t);
277  }
278  IntArgs values(teams);
279  for (int i=1; i<=teams; i++)
280  values[i-1] = i;
281  count(*this, r, IntSet(2,2), values, opt.icl());
282  }
283 
284  // Redundant constraint
285  for (int p=0; p<periods(); p++)
286  for (int w=0; w<weeks(); w ++)
287  rel(*this, teams * h(p,w) + a(p,w) - g(p,w) == teams);
288 
289  distinct(*this, game, opt.icl());
290 
291  branch(*this, game, INT_VAR_NONE(), INT_VAL_SPLIT_MIN());
292  }
294  SportsLeague(bool share, SportsLeague& s)
295  : Script(share, s), teams(s.teams) {
296  home.update(*this, share, s.home);
297  away.update(*this, share, s.away);
298  game.update(*this, share, s.game);
299  }
301  virtual Space*
302  copy(bool share) {
303  return new SportsLeague(share, *this);
304  }
306  virtual void print(std::ostream& os) const {
307  // print period index
308  os << "\t ";
309  for (int p=0; p<periods(); p++) {
310  os << "P[";
311  os.width(2);
312  os << p << "] ";
313  }
314  os << std::endl;
315  // print entries
316  for (int w=0; w<weeks(); w++) {
317  os << "\tW[";
318  os.width(2);
319  os << w+1 << "]: ";
320  for (int p=0; p<periods(); p++) {
321  os.width(2);
322  os << h(p,w).val() << '-';
323  os.width(2);
324  os << a(p,w).val() << " ";
325  }
326  os << std::endl;
327  }
328  }
329 };
330 
331 
335 int
336 main(int argc, char* argv[]) {
337  SizeOptions opt("Sports League Scheduling");
338  opt.icl(ICL_DOM);
339  opt.size(18);
340  opt.parse(argc,argv);
341  if (opt.size() < 5) {
342  std::cerr<< "No Solution for less than 5 teams!" << std::endl;
343  return 1;
344  }
345  if (opt.size() % 2 != 0) {
346  std::cerr << "Number of teams has to be even!" << std::endl;
347  return 1;
348  }
349  Script::run<SportsLeague, DFS,SizeOptions>(opt);
350  return 0;
351 }
352 
353 // STATISTICS: example-any
const int teams
Number of teams.
void size(unsigned int s)
Set default size.
Definition: options.hpp:467
Round robin schedule.
Options for scripts with additional size parameter
Definition: driver.hh:567
NodeType t
Type of node.
Definition: bool-expr.cpp:234
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:108
int periods(void) const
Return number of periods.
Play * plays
Play information.
IntVarArray away
away teams
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:435
IntVar & a(int p, int w)
Away team in period p and week w.
int main(int argc, char *argv[])
Main-function.
virtual Space * copy(bool share)
Copy during cloning.
RRS(int t)
Build a feasible schedule.
int weeks(void) const
Return number of weeks.
Integer variable array.
Definition: int.hh:741
int gn(int h, int a) const
Game number for game between home team h and away team a.
Computation spaces.
Definition: core.hpp:1362
Parametric base-class for scripts.
Definition: driver.hh:622
IntVar & g(int p, int w)
Return game number for game in period p and week w.
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1072
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
Entry in round robin schedule.
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Equality ( )
Definition: int.hh:904
Options opt
The options.
Definition: test.cpp:101
const IntVar & g(int p, int w) const
Return game number for game in period p and week w.
const IntVar & a(int p, int w) const
Away team in period p and week w.
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
virtual void print(std::ostream &os) const
Print solution.
unsigned int size(I &i)
Size of all ranges of range iterator i.
int periods(void) const
Return number of periods.
SportsLeague(bool share, SportsLeague &s)
Constructor for cloning s.
const IntVar & h(int p, int w) const
Home team in period p and week w.
SportsLeague(const SizeOptions &opt)
Setup model.
Less ( )
Definition: int.hh:907
Integer sets.
Definition: int.hh:171
Example: Sports league scheduling
void element(Home home, IntSharedArray c, IntVar x0, IntVar x1, IntConLevel)
Post domain consistent propagator for .
Definition: element.cpp:43
~RRS(void)
Delete schedule.
Passing integer variables.
Definition: int.hh:636
Passing integer arguments.
Definition: int.hh:607
int h
home team
void values(Home home, const IntVarArgs &x, IntSet y, IntConLevel icl=ICL_DEF)
Post constraint .
Definition: minimodel.hh:1869
int a
away team
int g
game number Default constructor
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntConLevel)
Post propagator for .
Definition: count.cpp:44
Integer variables.
Definition: int.hh:350
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
int weeks(void) const
Return number of weeks.
Play & play(int p, int w)
Play for period p and week w.
void distinct(Home home, const IntVarArgs &x, IntConLevel icl)
Post propagator for for all .
Definition: distinct.cpp:47
void hag(int w, IntArgs &h, IntArgs &a, IntArgs &g)
Home, away, and game information.
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:88
Gecode toplevel namespace
BrancherHandle 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:43
IntVarArray game
game numbers
void icl(IntConLevel i)
Set default integer consistency level.
Definition: options.hpp:194
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
Domain propagation or consistency.
Definition: int.hh:940
T * a
Element array.
Definition: array.hpp:528
IntVarArray home
home teams
IntVar & h(int p, int w)
Home team in period p and week w.