Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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
45using namespace Gecode;
46
48class Play {
49public:
50 int h;
51 int a;
52 int g;
54 Play(void) : h(0), a(0), g(0) {}
55};
56
58class RRS {
59protected:
61 const int teams;
65 int weeks(void) const {
66 return teams-1;
67 }
68
69 int periods(void) const {
70 return teams/2;
71 }
72
73 int gn(int h, int a) const {
74 return teams*(h-1) + a;
75 }
76
77 Play& play(int p, int w) {
78 return plays[p*weeks() + w];
79 }
80public:
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 }
142
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 }
150
151 ~RRS(void) {
152 delete [] plays;
153 }
154};
155
156
157
174class SportsLeague : public Script {
175protected:
176 const int teams;
180
182 int weeks(void) const {
183 return teams-1;
184 }
185
186 int periods(void) const {
187 return teams/2;
188 }
189
190 IntVar& h(int p, int w) {
191 return home[p*teams + w];
192 }
193
194 const IntVar& h(int p, int w) const {
195 return home[p*teams + w];
196 }
197
198 IntVar& a(int p, int w) {
199 return away[p*teams + w];
200 }
201
202 const IntVar& a(int p, int w) const {
203 return away[p*teams + w];
204 }
205
206 IntVar& g(int p, int w) {
207 return game[p*weeks() + w];
208 }
209
210 const IntVar& g(int p, int w) const {
211 return game[p*weeks() + w];
212 }
213
214public:
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 }
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
289 }
290
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 }
297
298 virtual Space*
299 copy(void) {
300 return new SportsLeague(*this);
301 }
302
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
332int
333main(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 }
347 return 0;
348}
349
350// STATISTICS: example-any
static void run(const Options &opt, Script *s=NULL)
Passing integer arguments.
Definition int.hh:634
Integer sets.
Definition int.hh:174
Passing integer variables.
Definition int.hh:662
Integer variable array.
Definition int.hh:772
Integer variables.
Definition int.hh:371
int val(void) const
Return assigned value.
Definition int.hpp:56
Options for scripts with additional size parameter
Definition driver.hh:675
Computation spaces.
Definition core.hpp:1744
Entry in round robin schedule.
int a
away team
int g
game number Default constructor
int h
home team
Play(void)
Round robin schedule.
void hag(int w, IntArgs &h, IntArgs &a, IntArgs &g)
Home, away, and game information.
RRS(int t)
Build a feasible schedule.
const int teams
Number of teams.
Play & play(int p, int w)
Play for period p and week w.
int weeks(void) const
Return number of weeks.
~RRS(void)
Delete schedule.
int gn(int h, int a) const
Game number for game between home team h and away team a.
Play * plays
Play information.
int periods(void) const
Return number of periods.
IntVar & a(int p, int w)
Away team in period p and week w.
int main(int argc, char *argv[])
Main-function.
int weeks(void) const
Return number of weeks.
SportsLeague(const SizeOptions &opt)
Setup model.
virtual Space * copy(void)
Copy during cloning.
virtual void print(std::ostream &os) const
Print solution.
const IntVar & h(int p, int w) const
Home team in period p and week w.
SportsLeague(SportsLeague &s)
Constructor for cloning s.
IntVar & g(int p, int w)
Return game number for game in period p and week w.
int periods(void) const
Return number of periods.
const IntVar & a(int p, int w) const
Away team in period p and week w.
IntVar & h(int p, int w)
Home team in period p and week w.
const IntVar & g(int p, int w) const
Return game number for game in period p and week w.
const int teams
number of teams
IntVarArray away
away teams
IntVarArray game
game numbers
IntVarArray home
home teams
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:120
Driver::ScriptBase< Driver::IgnoreStepOption< Space > > Script
Base-class for scripts.
Definition driver.hh:801
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
@ IRT_EQ
Equality ( )
Definition int.hh:941
@ IRT_LE
Less ( )
Definition int.hh:944
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:994
Gecode toplevel namespace
IntValBranch INT_VAL_SPLIT_MIN(void)
Select values not greater than mean of smallest and largest value.
Definition val.hpp:75
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition count.cpp:40
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator for for all .
Definition distinct.cpp:46
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
void element(Home home, IntSharedArray n, IntVar x0, IntVar x1, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for .
Definition element.cpp:39
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
Definition aliases.hpp:143