colored-matrix.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Mikael Lagerkvist <lagerkvist@gecode.org>
*
* Copyright:
* Mikael Lagerkvist, 2012
*
* 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 <fstream>
using namespace Gecode;
class ColoredMatrixOptions : public Options {
private:
Driver::UnsignedIntOption _height;
Driver::UnsignedIntOption _width;
Driver::UnsignedIntOption _size;
Driver::UnsignedIntOption _colors;
Driver::StringOption _not_all_equal;
Driver::StringOption _same_or_0;
Driver::StringOption _distinct_except_0;
Driver::StringOption _no_monochrome_rectangle;
public:
ColoredMatrixOptions(const char* n);
void parse(int& argc, char* argv[]) {
Options::parse(argc,argv);
}
int height(void) const {
if (_size.value() == 0U)
return static_cast<int>(_height.value());
else
return static_cast<int>(_size.value());
}
int width(void) const {
if (_size.value() == 0U)
return static_cast<int>(_width.value());
else
return static_cast<int>(_size.value());
}
int colors(void) const { return static_cast<int>(_colors.value()); }
int not_all_equal(void) const { return _not_all_equal.value(); }
int same_or_0(void) const { return _same_or_0.value(); }
int distinct_except_0(void) const { return _distinct_except_0.value(); }
int no_monochrome_rectangle(void) const {
return _no_monochrome_rectangle.value();
}
};
namespace {
DFA same_or_0_dfa(int colors);
TupleSet same_or_0_tuple_set(int colors);
DFA distinct_except_0_dfa(int colors);
DFA no_monochrome_rectangle_dfa(int colors);
IntSetArgs distinct_except_0_counts(int colors, int size);
DFA not_all_equal_dfa(int colors);
}
class ColoredMatrix : public IntMinimizeScript {
protected:
const ColoredMatrixOptions& opt;
const int height;
const int width;
const int colors;
IntVarArray x;
IntVar max_color;
IntVar same_or_0(const IntVar& a, const IntVar& b)
{
switch (opt.same_or_0()) {
case SAME_OR_0_REIFIED: {
IntVar result(*this, 0, colors);
BoolVar same = expr(*this, (a == b));
rel(*this, result, IRT_EQ, a, same);
// Redundant (implied by previous), but improves efficiency
rel(*this, result, IRT_NQ, 0, same);
return result;
}
case SAME_OR_0_TUPLE_SET: {
static TupleSet table = same_or_0_tuple_set(colors);
IntVar result(*this, 0, colors);
extensional(*this, IntVarArgs() << a << b << result, table);
return result;
}
case SAME_OR_0_DFA: {
static const DFA automaton = same_or_0_dfa(colors);
IntVar result(*this, 0, colors);
extensional(*this, IntVarArgs() << a << b << result, automaton);
return result;
}
default:
GECODE_NEVER;
return IntVar(*this, 0, 0);
}
}
void distinct_except_0(const IntVarArgs& v)
{
switch (opt.distinct_except_0()) {
case DISTINCT_EXCEPT_0_REIFIED:
for (int i = v.size(); i--; ) {
BoolVar viIsZero = expr(*this, v[i] == 0);
for (int j = i; j--; ) {
rel(*this, viIsZero || (v[i] != v[j]));
}
}
break;
case DISTINCT_EXCEPT_0_DFA: {
static const DFA automaton = distinct_except_0_dfa(colors);
extensional(*this, v, automaton);
break;
}
case DISTINCT_EXCEPT_0_COUNT: {
static const IntSetArgs counts = distinct_except_0_counts(colors, std::max(width, height));
count(*this, v, counts, opt.ipl());
break;
}
}
}
void not_all_equal(const IntVarArgs& v)
{
switch (opt.not_all_equal()) {
case NOT_ALL_EQUAL_NQ: {
rel(*this, v, IRT_NQ);
break;
}
case NOT_ALL_EQUAL_NAIVE: {
// At least one pair must be different.
// Bad decomposition since too many disjuncts are created.
BoolVarArgs disequalities;
for (int i = v.size(); i--; )
for (int j = i; j--; )
disequalities << expr(*this, v[i] != v[j]);
rel(*this, BOT_OR, disequalities, 1);
break;
}
case NOT_ALL_EQUAL_REIFIED: {
// It must not be the case that all are equal
BoolVarArgs equalities;
for (int i = 0; i < v.size()-1; ++i)
equalities << expr(*this, v[i] == v[i+1]);
rel(*this, BOT_AND, equalities, 0);
break;
}
case NOT_ALL_EQUAL_NVALUES:
// More than one number
nvalues(*this, v, IRT_GR, 1);
break;
case NOT_ALL_EQUAL_COUNT:
// No number in all positions
count(*this, v, IntSet(0, v.size()-1), IntArgs::create(colors, 1), opt.ipl());
break;
case NOT_ALL_EQUAL_DFA: {
static const DFA automaton = not_all_equal_dfa(colors);
extensional(*this, v, automaton);
break;
}
}
}
void no_monochrome_rectangle(IntVarArgs v1, IntVarArgs v2) {
const int length = v1.size();
switch (opt.no_monochrome_rectangle()) {
case NO_MONOCHROME_DECOMPOSITION: {
IntVarArgs z(length);
for (int i = 0; i < length; ++i) {
z[i] = same_or_0(v1[i], v2[i]);
}
distinct_except_0(z);
break;
}
case NO_MONOCHROME_DFA: {
static const DFA automaton = no_monochrome_rectangle_dfa(colors);
IntVarArgs z(2*length);
for (int i = length; i--; ) {
z[2*i + 0] = v1[i];
z[2*i + 1] = v2[i];
}
extensional(*this, z, automaton);
break;
}
}
}
public:
enum {
SEARCH_DFS,
SEARCH_BAB,
};
enum {
SYMMETRY_NONE = 0,
SYMMETRY_MATRIX = 1,
SYMMETRY_VALUES = 2,
};
enum {
MODEL_CORNERS = 1,
MODEL_ROWS = 2,
MODEL_COLUMNS = 4,
};
enum {
NOT_ALL_EQUAL_NQ,
NOT_ALL_EQUAL_NAIVE,
NOT_ALL_EQUAL_REIFIED,
NOT_ALL_EQUAL_NVALUES,
NOT_ALL_EQUAL_COUNT,
NOT_ALL_EQUAL_DFA,
};
enum {
SAME_OR_0_REIFIED,
SAME_OR_0_DFA,
SAME_OR_0_TUPLE_SET,
};
enum {
DISTINCT_EXCEPT_0_REIFIED,
DISTINCT_EXCEPT_0_DFA,
DISTINCT_EXCEPT_0_COUNT,
};
enum {
NO_MONOCHROME_DECOMPOSITION,
NO_MONOCHROME_DFA,
};
ColoredMatrix(const ColoredMatrixOptions& opt0)
: IntMinimizeScript(opt0),
opt(opt0), height(opt.height()), width(opt.width()), colors(opt.colors()),
x(*this, height*width, 1, colors),
max_color(*this, 1, colors)
{
max(*this, x, max_color);
Matrix<IntVarArray> m(x, width, height);
// For each pair of columns and rows, the intersections may not be equal.
if (opt.model() & MODEL_CORNERS) {
for (int c1 = 0; c1 < width; ++c1) {
for (int c2 = c1+1; c2 < width; ++c2) {
for (int r1 = 0; r1 < height; ++r1) {
for (int r2 = r1+1; r2 < height; ++r2) {
not_all_equal(IntVarArgs() << m(c1,r1) << m(c1,r2) << m(c2,r1) << m(c2,r2));
}
}
}
}
}
// Given two rows/columns, construct variables representing if
// the corresponding places are equal (and if so, what value).
// For the new values, no non-zero value may appear more than
// once.
if (opt.model() & MODEL_ROWS) {
for (int r1 = 0; r1 < height; ++r1) {
for (int r2 = r1+1; r2 < height; ++r2) {
no_monochrome_rectangle(m.row(r1), m.row(r2));
}
}
}
if (opt.model() & MODEL_COLUMNS) {
for (int c1 = 0; c1 < width; ++c1) {
for (int c2 = c1+1; c2 < width; ++c2) {
no_monochrome_rectangle(m.col(c1), m.col(c2));
}
}
}
// Symmetry breaking constraints.
{
// Lexical order for all columns and rows (all are interchangable)
if (opt.symmetry() & SYMMETRY_MATRIX) {
for (int r = 0; r < height-1; ++r) {
rel(*this, m.row(r), IRT_LE, m.row(r+1));
}
for (int c = 0; c < width-1; ++c) {
rel(*this, m.col(c), IRT_LE, m.col(c+1));
}
}
// Value precedence. Compatible with row/column ordering
if (opt.symmetry() & SYMMETRY_VALUES) {
precede(*this, x, IntArgs::create(colors, 1));
}
}
branch(*this, x, tiebreak(INT_VAR_MIN_MIN(), INT_VAR_SIZE_MIN()), INT_VAL_MIN());
}
virtual IntVar cost(void) const {
return max_color;
}
virtual void
print(std::ostream& os) const {
Matrix<IntVarArray> m(x, width, height);
for (int r = 0; r < height; ++r) {
os << "\t";
for (int c = 0; c < width; ++c) {
os << m(c, r) << " ";
}
os << std::endl;
}
os << std::endl;
os << "\tmax color: " << max_color << std::endl;
os << std::endl;
}
ColoredMatrix(ColoredMatrix& s)
: IntMinimizeScript(s), opt(s.opt),
height(s.height), width(s.width), colors(s.colors) {
x.update(*this, s.x);
max_color.update(*this, s.max_color);
}
virtual Space*
copy(void) {
return new ColoredMatrix(*this);
}
};
ColoredMatrixOptions::ColoredMatrixOptions(const char* n)
: Options(n),
_height("height", "Height of matrix", 8),
_width("width", "Width of matrix", 8),
_size("size", "If different from 0, used as both width and height", 0),
_colors("colors", "Maximum number of colors", 4),
_not_all_equal("not-all-equal", "How to implement the not all equals constraint (used in corners model)",
ColoredMatrix::NOT_ALL_EQUAL_NQ),
_same_or_0("same-or-0", "How to implement the same or 0 constraint (used in the decomposed no monochrome rectangle constraint)",
ColoredMatrix::SAME_OR_0_DFA),
_distinct_except_0("distinct-except-0", "How to implement the distinct except 0 constraint (used in the decomposed no monochrome rectangle constraint)",
ColoredMatrix::DISTINCT_EXCEPT_0_DFA),
_no_monochrome_rectangle("no-monochrome-rectangle", "How to implement no monochrome rectangle (used in the rows model)",
ColoredMatrix::NO_MONOCHROME_DFA)
{
add(_height);
add(_width);
add(_size);
add(_colors);
add(_not_all_equal);
add(_same_or_0);
add(_distinct_except_0);
add(_no_monochrome_rectangle);
// Add search options
_search.add(ColoredMatrix::SEARCH_DFS, "dfs", "Find a solution.");
_search.add(ColoredMatrix::SEARCH_BAB, "bab", "Find an optimal solution.");
_search.value(ColoredMatrix::SEARCH_DFS);
// Add symmetry options
_symmetry.add(ColoredMatrix::SYMMETRY_NONE, "none", "Don't use symmetry breaking.");
_symmetry.add(ColoredMatrix::SYMMETRY_MATRIX, "matrix", "Order matrix rows and columns");
_symmetry.add(ColoredMatrix::SYMMETRY_VALUES, "values", "Order values");
_symmetry.add(ColoredMatrix::SYMMETRY_MATRIX | ColoredMatrix::SYMMETRY_VALUES,
"both", "Order both rows/columns and values");
_symmetry.value(ColoredMatrix::SYMMETRY_MATRIX);
// Add model options
_model.add(ColoredMatrix::MODEL_CORNERS, "corner", "Use direct corners model with not-all-equal constraints.");
_model.add(ColoredMatrix::MODEL_ROWS, "rows", "Use model on pairs of rows (same_or_0 and distinct_except_0 constraints).");
_model.add(ColoredMatrix::MODEL_ROWS | ColoredMatrix::MODEL_CORNERS,
"both", "Use both rows and corners model");
_model.add(ColoredMatrix::MODEL_COLUMNS, "columns", "Use model on pairs of columns (same_or_0 and distinct_except_0 constraints).");
_model.add(ColoredMatrix::MODEL_ROWS | ColoredMatrix::MODEL_COLUMNS,
"matrix", "Use both rows and columns model");
_model.value(ColoredMatrix::MODEL_CORNERS);
// Add not all equal variants
_not_all_equal.add(ColoredMatrix::NOT_ALL_EQUAL_NQ, "nq", "Use nq constraint.");
_not_all_equal.add(ColoredMatrix::NOT_ALL_EQUAL_NAIVE, "naive", "Use naive reified decomposition.");
_not_all_equal.add(ColoredMatrix::NOT_ALL_EQUAL_REIFIED, "reified", "Use reified decomposition.");
_not_all_equal.add(ColoredMatrix::NOT_ALL_EQUAL_NVALUES, "nvalues", "Use nvalues.");
_not_all_equal.add(ColoredMatrix::NOT_ALL_EQUAL_COUNT, "count", "Use count.");
_not_all_equal.add(ColoredMatrix::NOT_ALL_EQUAL_DFA, "dfa", "Use dfa.");
// Add same or 0 variants
_same_or_0.add(ColoredMatrix::SAME_OR_0_REIFIED, "reified", "Use reified decomposition.");
_same_or_0.add(ColoredMatrix::SAME_OR_0_TUPLE_SET, "tuple-set", "Use tuple set representation.");
_same_or_0.add(ColoredMatrix::SAME_OR_0_DFA, "dfa", "Use dfa representation.");
// Add distinct except 0 variants
_distinct_except_0.add(ColoredMatrix::DISTINCT_EXCEPT_0_REIFIED, "reified", "Use reified decomposition.");
_distinct_except_0.add(ColoredMatrix::DISTINCT_EXCEPT_0_DFA, "dfa", "Use dfa decomposition.");
_distinct_except_0.add(ColoredMatrix::DISTINCT_EXCEPT_0_COUNT, "count", "Use global cardinality.");
// Add no monochrome rectangle variants
_no_monochrome_rectangle.add(ColoredMatrix::NO_MONOCHROME_DECOMPOSITION,
"decompositions",
"Use decompositions into same_or_0 and distinct_except_0.");
_no_monochrome_rectangle.add(ColoredMatrix::NO_MONOCHROME_DFA,
"dfa",
"Use DFA as direct implementation.");
}
int
main(int argc, char* argv[]) {
ColoredMatrixOptions opt("Colored matrix");
opt.parse(argc,argv);
if (opt.search() == ColoredMatrix::SEARCH_DFS) {
Script::run<ColoredMatrix,DFS,ColoredMatrixOptions>(opt);
} else {
Script::run<ColoredMatrix,BAB,ColoredMatrixOptions>(opt);
}
return 0;
}
namespace {
DFA same_or_0_dfa(int colors)
{
/* DFA over variable sequences (x,y,z) where z equals x/y if x and
* y are equal, and z equals 0 otherwise.
*
* DFA is constructed to contain paths
* start -- c --> node -- c --> node' -- c --> end
* for all colors c representing the case when x and y
* are equal.
*
* For the cases where x and y are non-equal (c and c'), paths
* start -- c --> node -- c' --> not-equal -- 0 --> end
* are added.
*/
const int start_state = 0;
const int not_equal_state = 2*colors+1;
const int final_state = 2*colors+2;
int n_transitions = colors*colors + 2*colors + 2;
DFA::Transition* trans =
new DFA::Transition[static_cast<size_t>(n_transitions)];
int current_transition = 0;
// From start state
for (int color = 1; color <= colors; ++color) {
trans[current_transition++] =
DFA::Transition(start_state, color, color);
}
// From first level states (indices [1..color])
// To second-level if same color, otherwise to not_equal_state
for (int state = 1; state <= colors; ++state) {
for (int color = 1; color <= colors; ++color) {
if (color == state) {
trans[current_transition++] =
DFA::Transition(state, color, colors+state);
} else {
trans[current_transition++] =
DFA::Transition(state, color, not_equal_state);
}
}
}
// From second level states (indices [colors+1..colors+colors])
// To final state with the same color
for (int color = 1; color <= colors; ++color) {
trans[current_transition++] =
DFA::Transition(colors+color, color, final_state);
}
// From not equal state to final state
trans[current_transition++] =
DFA::Transition(not_equal_state, 0, final_state);
// End sentinel
trans[current_transition++] =
DFA::Transition(-1, 0, -1);
int final_states[] = {final_state, -1};
DFA result(start_state, trans, final_states, true);
delete[] trans;
return result;
}
TupleSet same_or_0_tuple_set(int colors) {
TupleSet result(3);
for (int i = 1; i <= colors; ++i) {
for (int j = 1; j <= colors; ++j) {
if (i == j) {
result.add({i, j, i});
} else {
result.add({i, j, 0});
}
}
}
result.finalize();
return result;
}
DFA distinct_except_0_dfa(int colors)
{
/* DFA for a sequence that may use each color only once (and all
* others are zero).
*
* For n colors, 2^n nodes are used. For each node, if bit b is one, then
* that color has not been used yet. All nodes have self-loops for zero, and
* edges for still usable colors to the node with the corresponding bit un-set.
* All nodes are final nodes.
*/
const int nstates = 1 << colors;
const int start_state = nstates-1;
DFA::Transition* trans =
new DFA::Transition[static_cast<size_t>(nstates*colors + 1)];
int current_transition = 0;
for (int state = nstates; state--; ) {
trans[current_transition++] = DFA::Transition(state, 0, state);
for (int color = 1; color <= colors; ++color) {
const int color_bit = (1 << (color-1));
if (state & color_bit) {
trans[current_transition++] =
DFA::Transition(state, color, state & ~color_bit);
}
}
}
trans[current_transition++] = DFA::Transition(-1, 0, -1);
int* final_states = new int[nstates+1];
final_states[nstates] = -1;
for (int i = nstates; i--; ) {
final_states[i] = i;
}
DFA result(start_state, trans, final_states);
delete[] trans;
delete[] final_states;
return result;
}
DFA no_monochrome_rectangle_dfa(int colors)
{
/* DFA for a sequence of pairs, where each monochromatic pair may
* only appear once.
*
* For n colors, there are 2^n base states representing which
* monochromatic pairs are still available. For each base state s,
* the color seen goes to a new intermediate state. A different
* color will go back to state s. Seeing the same color will move
* to the next base state with that color combination removed (if
* it is still allowed).
*
* In essence, this DFA represents the combination of same_or_0
* and distinct_except_0 as a single constraint.
*/
const int base_states = 1 << colors;
const int start_state = base_states-1;
const int nstates = base_states + colors*base_states;
DFA::Transition* trans = new DFA::Transition[nstates*colors + 1];
int current_transition = 0;
for (int state = base_states; state--; ) {
for (int color = 1; color <= colors; ++color) {
const int color_bit = (1 << (color-1));
const int color_remembered_state = state + color*base_states;
trans[current_transition++] =
DFA::Transition(state, color, color_remembered_state);
for (int next_color = 1; next_color <= colors; ++next_color) {
if (next_color == color) {
// Two equal adjacent, only transition if color still allowed
if (state & color_bit) {
trans[current_transition++] =
DFA::Transition(color_remembered_state, color, state & ~color_bit);
}
} else {
trans[current_transition++] =
DFA::Transition(color_remembered_state, next_color, state);
}
}
}
}
trans[current_transition++] = DFA::Transition(-1, 0, -1);
assert(current_transition <= nstates*colors+1);
int* final_states = new int[base_states+1];
final_states[base_states] = -1;
for (int i = base_states; i--; ) {
final_states[i] = i;
}
DFA result(start_state, trans, final_states);
delete[] trans;
delete[] final_states;
return result;
}
IntSetArgs distinct_except_0_counts(int colors, int size)
{
IntSetArgs result(colors+1);
result[0] = IntSet(0, size);
for (int i = 1; i <= colors; ++i) {
result[i] = IntSet(0, 1);
}
return result;
}
DFA not_all_equal_dfa(int colors)
{
/* DFA for not all equal.
*
* From the start state, there is a transition for each color to
* that colors state. As long as the same color is seen, the
* automaton stays in that state. If a different color is seen,
* then it goes to the accepting state.
*/
const int nstates = 1 + colors + 1;
const int start_state = 0;
const int final_state = nstates-1;
DFA::Transition* trans = new DFA::Transition[2*colors + colors*colors + 1];
int current_transition = 0;
// Each color to its own state
for (int color = 1; color <= colors; ++color) {
trans[current_transition++] = DFA::Transition(start_state, color, color);
}
// Each colors state loops on itself, and goes to final on all others
for (int state = 1; state <= colors; ++state) {
for (int color = 1; color <= colors; ++color) {
if (state == color) {
trans[current_transition++] = DFA::Transition(state, color, state);
} else {
trans[current_transition++] = DFA::Transition(state, color, final_state);
}
}
}
// Loop on all colors in final state
for (int color = 1; color <= colors; ++color) {
trans[current_transition++] = DFA::Transition(final_state, color, final_state);
}
trans[current_transition++] = DFA::Transition(-1, 0, -1);
int final_states[] = {final_state, -1};
DFA result(start_state, trans, final_states);
delete[] trans;
return result;
}
}
// STATISTICS: example-any
ColoredMatrixOptions
ColoredMatrixOptions.
Definition colored-matrix.cpp:46
ColoredMatrixOptions::parse
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc).
Definition colored-matrix.cpp:70
ColoredMatrixOptions::colors
int colors(void) const
Return number of colors.
Definition colored-matrix.cpp:89
ColoredMatrixOptions::distinct_except_0
int distinct_except_0(void) const
Return how to implement distinct except 0.
Definition colored-matrix.cpp:95
ColoredMatrixOptions::same_or_0
int same_or_0(void) const
Return how to implement same or 0.
Definition colored-matrix.cpp:93
ColoredMatrixOptions::height
int height(void) const
Return height.
Definition colored-matrix.cpp:75
ColoredMatrixOptions::width
int width(void) const
Return width.
Definition colored-matrix.cpp:82
ColoredMatrixOptions::no_monochrome_rectangle
int no_monochrome_rectangle(void) const
Return how to implement distinct except 0.
Definition colored-matrix.cpp:97
ColoredMatrixOptions::ColoredMatrixOptions
ColoredMatrixOptions(const char *n)
Initialize options for example with name n.
Definition colored-matrix.cpp:457
ColoredMatrixOptions::not_all_equal
int not_all_equal(void) const
Return how to implement not all equals.
Definition colored-matrix.cpp:91
ColoredMatrix
Example: Colored matrix example.
Definition colored-matrix.cpp:164
ColoredMatrix::same_or_0
IntVar same_or_0(const IntVar &a, const IntVar &b)
Definition colored-matrix.cpp:186
ColoredMatrix::main
int main(int argc, char *argv[])
Main-function.
Definition colored-matrix.cpp:535
ColoredMatrix::distinct_except_0
void distinct_except_0(const IntVarArgs &v)
Definition colored-matrix.cpp:217
ColoredMatrix::opt
const ColoredMatrixOptions & opt
Options for model.
Definition colored-matrix.cpp:169
ColoredMatrix::not_all_equal_dfa
DFA not_all_equal_dfa(int colors)
ColoredMatrix::no_monochrome_rectangle_dfa
DFA no_monochrome_rectangle_dfa(int colors)
ColoredMatrix::distinct_except_0_counts
IntSetArgs distinct_except_0_counts(int colors, int size)
ColoredMatrix::print
virtual void print(std::ostream &os) const
Print solution.
Definition colored-matrix.cpp:429
ColoredMatrix::SYMMETRY_MATRIX
@ SYMMETRY_MATRIX
Order rows and columns of matrix.
Definition colored-matrix.cpp:321
ColoredMatrix::SYMMETRY_NONE
@ SYMMETRY_NONE
No symmetry breaking.
Definition colored-matrix.cpp:320
ColoredMatrix::SYMMETRY_VALUES
@ SYMMETRY_VALUES
Order value occurences.
Definition colored-matrix.cpp:322
ColoredMatrix::colors
const int colors
Number of colors to use.
Definition colored-matrix.cpp:172
ColoredMatrix::not_all_equal
void not_all_equal(const IntVarArgs &v)
Definition colored-matrix.cpp:243
ColoredMatrix::ColoredMatrix
ColoredMatrix(ColoredMatrix &s)
Constructor for cloning s.
Definition colored-matrix.cpp:444
ColoredMatrix::no_monochrome_rectangle
void no_monochrome_rectangle(IntVarArgs v1, IntVarArgs v2)
Definition colored-matrix.cpp:287
ColoredMatrix::DISTINCT_EXCEPT_0_DFA
@ DISTINCT_EXCEPT_0_DFA
Use dfa for distinct except 0.
Definition colored-matrix.cpp:348
ColoredMatrix::DISTINCT_EXCEPT_0_COUNT
@ DISTINCT_EXCEPT_0_COUNT
Use count for distinct except 0.
Definition colored-matrix.cpp:349
ColoredMatrix::DISTINCT_EXCEPT_0_REIFIED
@ DISTINCT_EXCEPT_0_REIFIED
Use reification for distinct except 0.
Definition colored-matrix.cpp:347
ColoredMatrix::SEARCH_DFS
@ SEARCH_DFS
Find solution.
Definition colored-matrix.cpp:315
ColoredMatrix::SEARCH_BAB
@ SEARCH_BAB
Find optimal solution.
Definition colored-matrix.cpp:316
ColoredMatrix::copy
virtual Space * copy(void)
Copy during cloning.
Definition colored-matrix.cpp:452
ColoredMatrix::NO_MONOCHROME_DFA
@ NO_MONOCHROME_DFA
Use dfa for no monochrome rectangle.
Definition colored-matrix.cpp:354
ColoredMatrix::NO_MONOCHROME_DECOMPOSITION
@ NO_MONOCHROME_DECOMPOSITION
Use decomposition for no monochrome rectangle.
Definition colored-matrix.cpp:353
ColoredMatrix::distinct_except_0_dfa
DFA distinct_except_0_dfa(int colors)
ColoredMatrix::MODEL_COLUMNS
@ MODEL_COLUMNS
Use model on pairs of columns.
Definition colored-matrix.cpp:328
ColoredMatrix::MODEL_ROWS
@ MODEL_ROWS
Use model on pairs of rows.
Definition colored-matrix.cpp:327
ColoredMatrix::MODEL_CORNERS
@ MODEL_CORNERS
Use model on corner combinations.
Definition colored-matrix.cpp:326
ColoredMatrix::same_or_0_tuple_set
TupleSet same_or_0_tuple_set(int colors)
ColoredMatrix::SAME_OR_0_DFA
@ SAME_OR_0_DFA
Use dfa for same or 0.
Definition colored-matrix.cpp:342
ColoredMatrix::SAME_OR_0_TUPLE_SET
@ SAME_OR_0_TUPLE_SET
Use tuple set for same or 0.
Definition colored-matrix.cpp:343
ColoredMatrix::SAME_OR_0_REIFIED
@ SAME_OR_0_REIFIED
Use reification for same or 0.
Definition colored-matrix.cpp:341
ColoredMatrix::cost
virtual IntVar cost(void) const
Return cost.
Definition colored-matrix.cpp:423
ColoredMatrix::x
IntVarArray x
Array for matrix variables.
Definition colored-matrix.cpp:179
ColoredMatrix::ColoredMatrix
ColoredMatrix(const ColoredMatrixOptions &opt0)
Actual model.
Definition colored-matrix.cpp:359
ColoredMatrix::same_or_0_dfa
DFA same_or_0_dfa(int colors)
ColoredMatrix::width
const int width
Width of matrix.
Definition colored-matrix.cpp:171
ColoredMatrix::max_color
IntVar max_color
Maximum color used.
Definition colored-matrix.cpp:181
ColoredMatrix::NOT_ALL_EQUAL_NQ
@ NOT_ALL_EQUAL_NQ
Use direct constraint for implemeting not all equals.
Definition colored-matrix.cpp:332
ColoredMatrix::NOT_ALL_EQUAL_REIFIED
@ NOT_ALL_EQUAL_REIFIED
Use reification for implemeting not all equals.
Definition colored-matrix.cpp:334
ColoredMatrix::NOT_ALL_EQUAL_NVALUES
@ NOT_ALL_EQUAL_NVALUES
Use nvalues for implementing not all equals.
Definition colored-matrix.cpp:335
ColoredMatrix::NOT_ALL_EQUAL_NAIVE
@ NOT_ALL_EQUAL_NAIVE
Use naive reification for implemeting not all equals.
Definition colored-matrix.cpp:333
ColoredMatrix::NOT_ALL_EQUAL_COUNT
@ NOT_ALL_EQUAL_COUNT
Use count for implementing not all equals.
Definition colored-matrix.cpp:336
ColoredMatrix::NOT_ALL_EQUAL_DFA
@ NOT_ALL_EQUAL_DFA
Use dfa for implementing not all equals.
Definition colored-matrix.cpp:337
ColoredMatrix::height
const int height
Height of matrix.
Definition colored-matrix.cpp:170
Gecode::ArgArrayBase::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1607
Gecode::BaseOptions::add
void add(Driver::BaseOption &o)
Add new option o.
Definition options.cpp:474
Gecode::BaseOptions::parse
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc).
Definition options.cpp:548
Gecode::BoolVarArgs
Passing Boolean variables.
Definition int.hh:712
Gecode::BoolVar
Boolean integer variables.
Definition int.hh:512
Gecode::DFA::Transition
Specification of a DFA transition.
Definition int.hh:2058
Gecode::DFA
Deterministic finite automaton (DFA).
Definition int.hh:2049
Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< Space > >::run
static void run(const Options &opt, Script *s=NULL)
Gecode::Driver::StringOption
String-valued option (integer value defined by strings).
Definition driver.hh:174
Gecode::Driver::UnsignedIntOption
Unsigned integer option.
Definition driver.hh:229
Gecode::IntArgs::create
static IntArgs create(int n, int start, int inc=1)
Allocate array with n elements such that for all .
Definition array.hpp:76
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::Matrix
Matrix-interface for arrays.
Definition minimodel.hh:2161
Gecode::Matrix::col
Slice< A > col(int c) const
Access column c.
Definition matrix.hpp:183
Gecode::Matrix::row
Slice< A > row(int r) const
Access row r.
Definition matrix.hpp:177
Gecode::Options::_model
Driver::StringOption _model
General model options.
Definition driver.hh:370
Gecode::Options::_search
Driver::StringOption _search
Search options.
Definition driver.hh:382
Gecode::Options::Options
Options(const char *s)
Initialize options for script with name s.
Definition options.cpp:576
Gecode::Options::_symmetry
Driver::StringOption _symmetry
General symmetry options.
Definition driver.hh:371
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::TupleSet
Class represeting a set of tuples.
Definition int.hh:2191
driver.hh
int.hh
Gecode::IntMinimizeScript
Driver::ScriptBase< Driver::IgnoreStepOption< IntMinimizeSpace > > IntMinimizeScript
Base-class for scripts for finding solution of lowest integer cost.
Definition driver.hh:808
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::extensional
void extensional(Home home, const IntVarArgs &x, DFA d, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for extensional constraint described by a DFA.
Definition extensional-regular.cpp:39
Gecode::precede
void precede(Home home, const IntVarArgs &x, int s, int t, IntPropLevel=IPL_DEF)
Post propagator that s precedes t in x.
Definition precede.cpp:43
Gecode::IRT_EQ
@ IRT_EQ
Equality ( ).
Definition int.hh:926
Gecode::IRT_NQ
@ IRT_NQ
Disequality ( ).
Definition int.hh:927
Gecode::IRT_LE
@ IRT_LE
Less ( ).
Definition int.hh:929
Gecode::IRT_GR
@ IRT_GR
Greater ( ).
Definition int.hh:931
Gecode::BOT_OR
@ BOT_OR
Disjunction.
Definition int.hh:952
Gecode::BOT_AND
@ BOT_AND
Conjunction.
Definition int.hh:951
minimodel.hh
Gecode
Gecode toplevel namespace
Gecode::IntSetArgs
ArgArray< IntSet > IntSetArgs
Passing set arguments.
Definition int.hh:619
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::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::tiebreak
TieBreak< VarBranch > tiebreak(VarBranch a, VarBranch b)
Combine variable selection criteria a and b for tie-breaking.
Definition tiebreak.hpp:80
Gecode::same
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Definition array.hpp:1937
Gecode::INT_VAL_MIN
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:49
Gecode::nvalues
void nvalues(Home home, const IntVarArgs &x, IntRelType irt, int y, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition nvalues.cpp:40
Gecode::INT_VAR_SIZE_MIN
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl=nullptr)
Select variable with smallest domain size.
Definition var.hpp:206
Gecode::INT_VAR_MIN_MIN
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl=nullptr)
Select variable with smallest min.
Definition var.hpp:186
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56