circuit.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* 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 "test/int.hh"
#include <gecode/minimodel.hh>
namespace Test { namespace Int {
namespace Circuit {
class Circuit : public Test {
private:
int offset;
public:
Circuit(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
: Test("Circuit::" + str(ipl) + "::" + str(n) + "::" + str(off),
n,min,max,false,ipl), offset(off) {
contest = CTL_NONE;
testfix = false;
}
virtual bool solution(const Assignment& x) const {
for (int i=x.size(); i--; )
if ((x[i] < 0) || (x[i] > x.size()-1))
return false;
int reachable = 0;
{
int j=0;
for (int i=x.size(); i--; ) {
j=x[j]; reachable |= (1 << j);
}
}
for (int i=x.size(); i--; )
if (!(reachable & (1 << i)))
return false;
return true;
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
if (offset > 0) {
Gecode::IntVarArgs xx(x.size());
for (int i=x.size(); i--;)
xx[i] = Gecode::expr(home, x[i]+offset);
Gecode::circuit(home, offset, xx, ipl);
} else {
Gecode::circuit(home, x, ipl);
}
}
};
class Path : public Test {
private:
int offset;
public:
Path(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
: Test("Path::" + str(ipl) + "::" + str(n) + "::" + str(off),
n+2,min,max,false,ipl), offset(off) {
contest = CTL_NONE;
testfix = false;
}
virtual bool solution(const Assignment& x) const {
int n = x.size() - 2;
int s = x[n];
int e = x[n+1];
if ((s < 0) || (s > n) || (e < 0) || (e > n) || (x[e] != n))
return false;
for (int i=n; i--; )
if ((i != e) && ((x[i] < 0) || (x[i] > n)))
return false;
int reachable = (1 << s);
{
int j=s;
for (int i=n; i--; ) {
j=x[j]; reachable |= (1 << j);
}
}
for (int i=n; i--; )
if (!(reachable & (1 << i)))
return false;
return true;
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
int n = x.size() - 2;
Gecode::IntVarArgs xx(n);
if (offset > 0) {
for (int i=n; i--;)
xx[i] = Gecode::expr(home, x[i]+offset);
Gecode::path(home, offset, xx,
Gecode::expr(home, x[n]+offset),
Gecode::expr(home, x[n+1]+offset),ipl);
} else {
for (int i=n; i--;)
xx[i] = x[i];
Gecode::path(home, xx, x[n], x[n+1], ipl);
}
}
};
class CircuitCost : public Test {
private:
int offset;
public:
CircuitCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
: Test("Circuit::Cost::"+str(ipl)+"::"+str(n)+"::"+str(off),
n+1,min,max,false,ipl), offset(off) {
contest = CTL_NONE;
testfix = false;
}
virtual bool solution(const Assignment& x) const {
int n=x.size()-1;
for (int i=n; i--; )
if ((x[i] < 0) || (x[i] > n-1))
return false;
int reachable = 0;
{
int j=0;
for (int i=n; i--; ) {
j=x[j]; reachable |= (1 << j);
}
}
for (int i=n; i--; )
if (!(reachable & (1 << i)))
return false;
int c=0;
for (int i=n; i--; )
c += x[i];
return c == x[n];
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
using namespace Gecode;
int n=x.size()-1;
IntArgs c(n*n);
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
c[i*n+j]=j;
IntVarArgs y(n);
if (offset > 0) {
for (int i=n; i--;)
y[i] = Gecode::expr(home, x[i]+offset);
Gecode::circuit(home, c, offset, y, x[n], ipl);
} else {
for (int i=0; i<n; i++)
y[i]=x[i];
circuit(home, c, y, x[n], ipl);
}
}
};
class PathCost : public Test {
private:
int offset;
public:
PathCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
: Test("Path::Cost::"+str(ipl)+"::"+str(n)+"::"+str(off),
n+3,min,max,false,ipl), offset(off) {
contest = CTL_NONE;
testfix = false;
}
virtual bool solution(const Assignment& x) const {
int n = x.size() - 3;
int s = x[n];
int e = x[n+1];
int c = x[n+2] + n;
if ((s < 0) || (s > n) || (e < 0) || (e > n) || (x[e] != n))
return false;
for (int i=n; i--; )
if ((i != e) && ((x[i] < 0) || (x[i] > n)))
return false;
int reachable = (1 << s);
{
int j=s;
for (int i=n; i--; ) {
j=x[j]; reachable |= (1 << j);
}
}
for (int i=n; i--; )
if (!(reachable & (1 << i)))
return false;
for (int i=n; i--; )
c -= x[i];
return c == 0;
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
using namespace Gecode;
int n=x.size()-3;
IntArgs c(n*n);
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
c[i*n+j]=j;
IntVarArgs y(n);
if (offset > 0) {
for (int i=n; i--;)
y[i] = Gecode::expr(home, x[i]+offset);
path(home, c, offset, y,
expr(home, x[n]+offset),
expr(home, x[n+1]+offset),
x[n+2], ipl);
} else {
for (int i=0; i<n; i++)
y[i]=x[i];
path(home, c, y, x[n], x[n+1], x[n+2], ipl);
}
}
};
class CircuitFullCost : public Test {
private:
int offset;
public:
CircuitFullCost(int n, int min, int max, int off,
Gecode::IntPropLevel ipl)
: Test("Circuit::FullCost::" + str(ipl)+"::"+str(n)+"::"+str(off),
2*n+1,min,max,false,ipl), offset(off) {
contest = CTL_NONE;
testfix = false;
}
virtual bool solution(const Assignment& x) const {
int n=(x.size()-1) / 2;
for (int i=n; i--; )
if ((x[i] < 0) || (x[i] > n-1))
return false;
int reachable = 0;
{
int j=0;
for (int i=n; i--; ) {
j=x[j]; reachable |= (1 << j);
}
}
for (int i=n; i--; )
if (!(reachable & (1 << i)))
return false;
for (int i=n; i--; )
if ((x[i]/2) != x[n+i])
return false;
int c=0;
for (int i=n; i--; )
c += x[n+i];
return c == x[2*n];
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
using namespace Gecode;
int n=(x.size()-1)/2;
IntArgs c(n*n);
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
c[i*n+j]=(j/2);
IntVarArgs y(n), z(n);
for (int i=0; i<n; i++) {
z[i]=x[n+i];
}
if (offset > 0) {
for (int i=n; i--;)
y[i] = Gecode::expr(home, x[i]+offset);
Gecode::circuit(home, c, offset, y, z, x[2*n], ipl);
} else {
for (int i=0; i<n; i++)
y[i]=x[i];
circuit(home, c, y, z, x[2*n], ipl);
}
}
};
class Create {
public:
Create(void) {
for (int i=1; i<=6; i++) {
(void) new Circuit(i,0,i-1,0,Gecode::IPL_VAL);
(void) new Circuit(i,0,i-1,0,Gecode::IPL_DOM);
(void) new Circuit(i,0,i-1,5,Gecode::IPL_VAL);
(void) new Circuit(i,0,i-1,5,Gecode::IPL_DOM);
}
for (int i=1; i<=4; i++) {
(void) new Path(i,0,i-1,0,Gecode::IPL_VAL);
(void) new Path(i,0,i-1,0,Gecode::IPL_DOM);
(void) new Path(i,0,i-1,5,Gecode::IPL_VAL);
(void) new Path(i,0,i-1,5,Gecode::IPL_DOM);
}
(void) new CircuitCost(4,0,9,0,Gecode::IPL_VAL);
(void) new CircuitCost(4,0,9,0,Gecode::IPL_DOM);
(void) new CircuitFullCost(3,0,3,0,Gecode::IPL_VAL);
(void) new CircuitFullCost(3,0,3,0,Gecode::IPL_DOM);
(void) new CircuitCost(4,0,9,5,Gecode::IPL_VAL);
(void) new CircuitCost(4,0,9,5,Gecode::IPL_DOM);
(void) new CircuitFullCost(3,0,3,5,Gecode::IPL_VAL);
(void) new CircuitFullCost(3,0,3,5,Gecode::IPL_DOM);
(void) new PathCost(3,0,5,0,Gecode::IPL_VAL);
(void) new PathCost(3,0,5,0,Gecode::IPL_DOM);
(void) new PathCost(3,0,5,5,Gecode::IPL_VAL);
(void) new PathCost(3,0,5,5,Gecode::IPL_DOM);
}
};
Create c;
}
}}
// STATISTICS: test-int
Gecode::IntArgs
Passing integer arguments.
Definition int.hh:628
Gecode::IntVarArgs
Passing integer variables.
Definition int.hh:656
Gecode::IntVarArray
Integer variable array.
Definition int.hh:763
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::VarArray::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:926
Test::Int::Assignment
Base class for assignments
Definition int.hh:59
Test::Int::Assignment::size
int size(void) const
Return number of variables.
Definition int.hpp:46
Test::Int::Circuit::CircuitCost
Simple test for circuit constraint with total cost.
Definition circuit.cpp:144
Test::Int::Circuit::CircuitCost::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post circuit constraint on x.
Definition circuit.cpp:178
Test::Int::Circuit::CircuitCost::CircuitCost
CircuitCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
Create and register test.
Definition circuit.cpp:150
Test::Int::Circuit::CircuitCost::solution
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition circuit.cpp:157
Test::Int::Circuit::CircuitFullCost
Simple test for circuit constraint with full cost information.
Definition circuit.cpp:261
Test::Int::Circuit::CircuitFullCost::CircuitFullCost
CircuitFullCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
Create and register test.
Definition circuit.cpp:267
Test::Int::Circuit::CircuitFullCost::solution
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition circuit.cpp:275
Test::Int::Circuit::CircuitFullCost::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post circuit constraint on x.
Definition circuit.cpp:299
Test::Int::Circuit::Circuit
Simple test for circuit constraint.
Definition circuit.cpp:48
Test::Int::Circuit::Circuit::Circuit
Circuit(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
Create and register test.
Definition circuit.cpp:54
Test::Int::Circuit::Circuit::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post circuit constraint on x.
Definition circuit.cpp:78
Test::Int::Circuit::Circuit::solution
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition circuit.cpp:61
Test::Int::Circuit::Create
Help class to create and register tests.
Definition circuit.cpp:323
Test::Int::Circuit::Create::Create
Create(void)
Perform creation and registration.
Definition circuit.cpp:326
Test::Int::Circuit::PathCost
Simple test for path constraint with total cost.
Definition circuit.cpp:199
Test::Int::Circuit::PathCost::solution
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition circuit.cpp:212
Test::Int::Circuit::PathCost::PathCost
PathCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
Create and register test.
Definition circuit.cpp:205
Test::Int::Circuit::PathCost::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post circuit constraint on x.
Definition circuit.cpp:237
Test::Int::Circuit::Path
Simple test for Hamiltonian path constraint.
Definition circuit.cpp:91
Test::Int::Circuit::Path::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post path constraint on x.
Definition circuit.cpp:126
Test::Int::Circuit::Path::Path
Path(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
Create and register test.
Definition circuit.cpp:97
Test::Int::Circuit::Path::solution
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition circuit.cpp:104
Test::Int::Test::testfix
bool testfix
Whether to perform fixpoint test.
Definition int.hh:240
Test::Int::Test::ipl
Gecode::IntPropLevel ipl
Propagation level.
Definition int.hh:234
Test::Int::Test::str
static std::string str(Gecode::IntPropLevel ipl)
Map integer propagation level to string.
Definition int.hpp:209
Test::Int::Test::contest
ConTestLevel contest
Whether to test for certain consistency.
Definition int.hh:236
Gecode::IntPropLevel
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:974
Gecode::IPL_DOM
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:979
Gecode::IPL_VAL
@ IPL_VAL
Value propagation.
Definition int.hh:977
minimodel.hh
Gecode
Gecode toplevel namespace
Gecode::expr
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:915
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:67
Gecode::path
void path(Home home, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl=IPL_DEF)
Post propagator such that x forms a Hamiltonian path.
Definition circuit.cpp:169
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:49
Gecode::circuit
void circuit(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator such that x forms a circuit.
Definition circuit.cpp:73
Test::Int::Circuit::c
Create c
Definition circuit.cpp:354
Test::Int
Testing finite domain integers.
Definition int.cpp:40
Test::Int::CTL_NONE
@ CTL_NONE
No consistency-test.
Definition int.hh:140
Test
General test support.
Definition afc.cpp:39
int.hh