sports-league.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Patrick Pekczynski <pekczynski@ps.uni-sb.de>
*
* Contributing authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Patrick Pekczynski, 2004
* Christian Schulte, 2007
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <gecode/driver.hh>
#include <gecode/int.hh>
#include <gecode/minimodel.hh>
#include <algorithm>
#include <iomanip>
using namespace Gecode;
class Play {
public:
int h;
int a;
int g;
Play(void) : h(0), a(0), g(0) {}
};
class RRS {
protected:
const int teams;
Play* plays;
int weeks(void) const {
return teams-1;
}
int periods(void) const {
return teams/2;
}
int gn(int h, int a) const {
return teams*(h-1) + a;
}
Play& play(int p, int w) {
return plays[p*weeks() + w];
}
public:
RRS(int t) : teams(t), plays(new Play[periods()*weeks()]) {
// Determine the first game (week 0 period 0)
play(0,0).h = 1;
play(0,0).a = 2;
play(0,0).g = 2;
// Determine the other games of the first week
for (int p=1; p<periods(); p++) {
play(p,0).h = (p + 1) + 1;
play(p,0).a = teams - (p + 1 - 2);
play(p,0).g = gn(play(p,0).h,play(p,0).a);
}
// Compute the games for the subsequent weeks
for (int w=1; w<weeks(); w++) {
for (int p=0; p<periods(); p++) {
if (play(p,w-1).h == teams)
play(p,w).h = 2;
else if (play(p,w-1).h == 1)
play(p,w).h = 1;
else
play(p,w).h = play(p,w-1).h + 1;
if (play(p,w-1).a == teams)
play(p,w).a = 2;
else
play(p,w).a = play(p,w-1).a + 1;
// maintain symmetry for (h,a): h < a
if (play(p,w).h > play(p,w).a)
std::swap(play(p,w).h,play(p,w).a);
play(p,w).g = gn(play(p,w).h,play(p,w).a);
}
}
}
void hag(int w, IntArgs& h, IntArgs& a, IntArgs& g) {
for (int p=0; p<periods(); p++) {
h[p] = play(p,w).h;
a[p] = play(p,w).a;
g[p] = play(p,w).g;
}
}
~RRS(void) {
delete [] plays;
}
};
class SportsLeague : public Script {
protected:
const int teams;
IntVarArray home;
IntVarArray away;
IntVarArray game;
int weeks(void) const {
return teams-1;
}
int periods(void) const {
return teams/2;
}
IntVar& h(int p, int w) {
return home[p*teams + w];
}
const IntVar& h(int p, int w) const {
return home[p*teams + w];
}
IntVar& a(int p, int w) {
return away[p*teams + w];
}
const IntVar& a(int p, int w) const {
return away[p*teams + w];
}
IntVar& g(int p, int w) {
return game[p*weeks() + w];
}
const IntVar& g(int p, int w) const {
return game[p*weeks() + w];
}
public:
SportsLeague(const SizeOptions& opt) :
Script(opt),
teams(opt.size()),
home(*this, periods() * teams, 1, weeks()),
away(*this, periods() * teams, 2, weeks()+1),
game(*this, weeks()*periods(), 2, teams*weeks())
{
// Initialize round robin schedule
RRS r(teams);
// Domain for gamenumber of period
for (int w=0; w<weeks(); w++) {
IntArgs rh(periods()), ra(periods()), rg(periods());
IntVarArgs n(*this,periods(),0,periods()-1);
distinct(*this, n, opt.ipl());
r.hag(w,rh,ra,rg);
for (int p=0; p<periods(); p++) {
element(*this, rh, n[p], h(p,w));
element(*this, ra, n[p], a(p,w));
element(*this, rg, n[p], g(p,w));
}
}
for (int p=0; p<periods(); p++)
for (int w=0; w<teams; w++)
rel(*this, h(p,w), IRT_LE, a(p,w));
// Home teams in first week are ordered
{
IntVarArgs h0(periods());
for (int p=0; p<periods(); p++)
h0[p] = h(p,0);
rel(*this, h0, IRT_LE);
}
// Fix first pair
rel(*this, h(0,0), IRT_EQ, 1);
rel(*this, a(0,0), IRT_EQ, 2);
for (int w=0; w<teams; w++) {
IntVarArgs c(teams);
for (int p=0; p<periods(); p++) {
c[2*p] = h(p,w); c[2*p+1] = a(p,w);
}
distinct(*this, c, opt.ipl());
}
for (int p=0; p<periods(); p++) {
IntVarArgs r(2*teams);
for (int t=0; t<teams; t++) {
r[2*t] = h(p,t);
r[2*t+1] = a(p,t);
}
IntArgs values(teams);
for (int i=1; i<=teams; i++)
values[i-1] = i;
count(*this, r, IntSet(2,2), values, opt.ipl());
}
// Redundant constraint
for (int p=0; p<periods(); p++)
for (int w=0; w<weeks(); w ++)
rel(*this, teams * h(p,w) + a(p,w) - g(p,w) == teams);
distinct(*this, game, opt.ipl());
branch(*this, game, INT_VAR_NONE(), INT_VAL_SPLIT_MIN());
}
SportsLeague(SportsLeague& s)
: Script(s), teams(s.teams) {
home.update(*this, s.home);
away.update(*this, s.away);
game.update(*this, s.game);
}
virtual Space*
copy(void) {
return new SportsLeague(*this);
}
virtual void print(std::ostream& os) const {
// print period index
os << "\t ";
for (int p=0; p<periods(); p++) {
os << "P[";
os.width(2);
os << p << "] ";
}
os << std::endl;
// print entries
for (int w=0; w<weeks(); w++) {
os << "\tW[";
os.width(2);
os << w+1 << "]: ";
for (int p=0; p<periods(); p++) {
os.width(2);
os << h(p,w).val() << '-';
os.width(2);
os << a(p,w).val() << " ";
}
os << std::endl;
}
}
};
int
main(int argc, char* argv[]) {
SizeOptions opt("Sports League Scheduling");
opt.ipl(IPL_DOM);
opt.size(18);
opt.parse(argc,argv);
if (opt.size() < 5) {
std::cerr<< "No Solution for less than 5 teams!" << std::endl;
return 1;
}
if (opt.size() % 2 != 0) {
std::cerr << "Number of teams has to be even!" << std::endl;
return 1;
}
Script::run<SportsLeague, DFS,SizeOptions>(opt);
return 0;
}
// STATISTICS: example-any
Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< Space > >::run
static void run(const Options &opt, Script *s=NULL)
Gecode::IntArgs
Passing integer arguments.
Definition int.hh:628
Gecode::IntSet
Integer sets.
Definition int.hh:174
Gecode::IntVarArgs
Passing integer variables.
Definition int.hh:656
Gecode::IntVarArray
Integer variable array.
Definition int.hh:763
Gecode::IntVar
Integer variables.
Definition int.hh:371
Gecode::IntVar::val
int val(void) const
Return assigned value.
Definition int.hpp:56
Gecode::SizeOptions
Options for scripts with additional size parameter
Definition driver.hh:675
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Play
Entry in round robin schedule.
Definition sports-league.cpp:48
Play::a
int a
away team
Definition sports-league.cpp:51
Play::g
int g
game number Default constructor
Definition sports-league.cpp:52
Play::h
int h
home team
Definition sports-league.cpp:50
Play::Play
Play(void)
Definition sports-league.cpp:54
RRS
Round robin schedule.
Definition sports-league.cpp:58
RRS::hag
void hag(int w, IntArgs &h, IntArgs &a, IntArgs &g)
Home, away, and game information.
Definition sports-league.cpp:143
RRS::RRS
RRS(int t)
Build a feasible schedule.
Definition sports-league.cpp:106
RRS::teams
const int teams
Number of teams.
Definition sports-league.cpp:61
RRS::play
Play & play(int p, int w)
Play for period p and week w.
Definition sports-league.cpp:77
RRS::weeks
int weeks(void) const
Return number of weeks.
Definition sports-league.cpp:65
RRS::~RRS
~RRS(void)
Delete schedule.
Definition sports-league.cpp:151
RRS::gn
int gn(int h, int a) const
Game number for game between home team h and away team a.
Definition sports-league.cpp:73
RRS::plays
Play * plays
Play information.
Definition sports-league.cpp:63
RRS::periods
int periods(void) const
Return number of periods.
Definition sports-league.cpp:69
SportsLeague::a
IntVar & a(int p, int w)
Away team in period p and week w.
Definition sports-league.cpp:198
SportsLeague::main
int main(int argc, char *argv[])
Main-function.
Definition sports-league.cpp:333
SportsLeague::weeks
int weeks(void) const
Return number of weeks.
Definition sports-league.cpp:182
SportsLeague::SportsLeague
SportsLeague(const SizeOptions &opt)
Setup model.
Definition sports-league.cpp:216
SportsLeague::copy
virtual Space * copy(void)
Copy during cloning.
Definition sports-league.cpp:299
SportsLeague::print
virtual void print(std::ostream &os) const
Print solution.
Definition sports-league.cpp:303
SportsLeague::h
const IntVar & h(int p, int w) const
Home team in period p and week w.
Definition sports-league.cpp:194
SportsLeague::SportsLeague
SportsLeague(SportsLeague &s)
Constructor for cloning s.
Definition sports-league.cpp:291
SportsLeague::g
IntVar & g(int p, int w)
Return game number for game in period p and week w.
Definition sports-league.cpp:206
SportsLeague::periods
int periods(void) const
Return number of periods.
Definition sports-league.cpp:186
SportsLeague::a
const IntVar & a(int p, int w) const
Away team in period p and week w.
Definition sports-league.cpp:202
SportsLeague::h
IntVar & h(int p, int w)
Home team in period p and week w.
Definition sports-league.cpp:190
SportsLeague::g
const IntVar & g(int p, int w) const
Return game number for game in period p and week w.
Definition sports-league.cpp:210
SportsLeague::teams
const int teams
number of teams
Definition sports-league.cpp:176
SportsLeague::away
IntVarArray away
away teams
Definition sports-league.cpp:178
SportsLeague::game
IntVarArray game
game numbers
Definition sports-league.cpp:179
SportsLeague::home
IntVarArray home
home teams
Definition sports-league.cpp:177
Test::Options::parse
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:120
driver.hh
int.hh
Gecode::Script
Driver::ScriptBase< Driver::IgnoreStepOption< Space > > Script
Base-class for scripts.
Definition driver.hh:801
Gecode::branch
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
Gecode::rel
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
Gecode::IRT_EQ
@ IRT_EQ
Equality ( ).
Definition int.hh:926
Gecode::IRT_LE
@ IRT_LE
Less ( ).
Definition int.hh:929
Gecode::IPL_DOM
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:979
minimodel.hh
Gecode
Gecode toplevel namespace
Gecode::INT_VAL_SPLIT_MIN
IntValBranch INT_VAL_SPLIT_MIN(void)
Select values not greater than mean of smallest and largest value.
Definition val.hpp:75
Gecode::count
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition count.cpp:40
Gecode::distinct
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator for for all .
Definition distinct.cpp:46
Gecode::INT_VAR_NONE
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
Gecode::element
void element(Home home, IntSharedArray n, IntVar x0, IntVar x1, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for .
Definition element.cpp:39
Gecode::values
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
Definition aliases.hpp:143