dom-sup.hpp
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>
* Guido Tack <tack@gecode.org>
*
* Copyright:
* Patrick Pekczynski, 2005
* Christian Schulte, 2009
* Guido Tack, 2009
*
* 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.
*
*/
namespace Gecode { namespace Int { namespace GCC {
enum BC {UBC = 1, LBC = 0};
class Edge;
class Node {
protected:
Edge* e;
Edge* fst;
Edge* lst;
Edge* ie;
int idx;
enum NodeFlag {
NF_NONE = 0,
NF_VAL = 1 << 0,
NF_M_LBC = 1 << 1,
NF_M_UBC = 1 << 2
};
unsigned char nf;
public:
int noe;
Node(void);
Node(NodeFlag nf, int i);
bool type(void) const;
Edge** adj(void);
Edge* first(void) const;
Edge* last(void) const;
Edge* inedge(void) const;
int index(void) const;
bool removed(void) const;
void first(Edge* p);
void last(Edge* p);
void inedge(Edge* p);
void index(int i);
static void* operator new(size_t s, Space& home);
static void operator delete(void*, Space&) {};
static void operator delete(void*) {};
};
class VarNode : public Node {
protected:
Edge* ubm;
Edge* lbm;
public:
VarNode(void);
VarNode(int i);
Edge* get_match(BC bc) const;
bool matched(BC bc) const;
void set_match(BC bc, Edge* m);
void match(BC bc);
void unmatch(BC bc);
};
class ValNode : public Node {
protected:
int _klb;
int _kub;
int _kidx;
int _kcount;
int noc;
int lb;
int ublow;
int ub;
public:
int val;
ValNode(void);
ValNode(int min, int max, int value, int kidx, int kshift, int count);
int maxlow(void) const;
void card_conflict(int c);
int card_conflict(void) const;
void red_conflict(void);
void inc(void);
int kcount(void) const;
int incid_match(BC bc) const;
int kindex(void) const;
bool matched(BC bc) const;
bool sink(void) const;
bool source(void) const;
int kmin(void) const;
int kmax(void) const;
int kbound(BC bc) const;
void maxlow(int i);
void kcount(int);
void kindex(int);
void dec(BC bc);
void inc(BC bc);
int cap(BC bc) const;
void cap(BC bc, int c);
void match(BC bc);
void unmatch(BC bc);
void reset(void);
void kmin(int min);
void kmax(int max);
};
class Edge {
private:
VarNode* x;
ValNode* v;
Edge* next_edge;
Edge* prev_edge;
Edge* next_vedge;
Edge* prev_vedge;
enum EdgeFlag {
EF_NONE = 0,
EF_MRKLB = 1 << 0,
EF_MRKUB = 1 << 1,
EF_LM = 1 << 2,
EF_UM = 1 << 3,
EF_DEL = 1 << 4
};
unsigned char ef;
public:
Edge(void) {}
Edge(VarNode* x, ValNode* v);
bool used(BC bc) const;
bool matched(BC bc) const;
bool deleted(void) const;
Edge* next(bool t) const;
Edge* next(void) const;
Edge* prev(void) const;
Edge* vnext(void) const;
Edge* vprev(void) const;
VarNode* getVar(void) const;
ValNode* getVal(void) const;
Node* getMate(bool t) const;
void use(BC bc);
void free(BC bc);
void reset(BC bc);
void match(BC bc);
void unmatch(BC bc);
void unmatch(BC bc, bool t);
void unlink(void);
void del_edge(void);
void insert_edge(void);
Edge** next_ref(void);
Edge** prev_ref(void);
Edge** vnext_ref(void);
Edge** vprev_ref(void);
static void* operator new(size_t s, Space& home);
static void operator delete(void*, Space&) {};
static void operator delete(void*) {};
};
template<class Card>
class VarValGraph {
private:
typedef Support::StaticStack<Node*,Region> NodeStack;
typedef Support::BitSet<Region> BitSet;
VarNode** vars;
ValNode** vals;
int n_var;
int n_val;
int n_node;
int sum_min;
int sum_max;
public:
VarValGraph(Space& home,
ViewArray<IntView>& x, ViewArray<Card>& k,
int smin, int smax);
ExecStatus min_require(Space& home,
ViewArray<IntView>& x, ViewArray<Card>& k);
ExecStatus sync(ViewArray<IntView>& x, ViewArray<Card>& k);
template<BC>
ExecStatus narrow(Space& home,
ViewArray<IntView>& x, ViewArray<Card>& k);
template<BC>
ExecStatus maximum_matching(void);
template<BC>
void free_alternating_paths(void);
template<BC>
void strongly_connected_components(void);
template<BC>
bool augmenting_path(Node*);
protected:
template<BC>
void dfs(Node*, BitSet&, BitSet&, int[],
NodeStack&, NodeStack&, int&);
public:
void* operator new(size_t t, Space& home);
void operator delete(void*, Space&) {}
};
/*
* Nodes
*
*/
forceinline
Node::Node(void) {}
forceinline
Node::Node(NodeFlag nf0, int i)
: e(NULL), fst(NULL), lst(NULL), ie(NULL), idx(i),
nf(static_cast<unsigned char>(nf0)), noe(0) {}
forceinline Edge**
Node::adj(void) {
return &e;
}
forceinline Edge*
Node::first(void) const {
return fst;
}
forceinline Edge*
Node::last(void) const {
return lst;
}
forceinline void
Node::first(Edge* p) {
fst = p;
}
forceinline void
Node::last(Edge* p) {
lst = p;
}
forceinline bool
Node::type(void) const {
return (nf & NF_VAL) != 0;
}
forceinline Edge*
Node::inedge(void) const {
return ie;
}
forceinline void
Node::inedge(Edge* p) {
ie = p;
}
forceinline bool
Node::removed(void) const {
return noe == 0;
}
forceinline void
Node::index(int i) {
idx = i;
}
forceinline int
Node::index(void) const {
return idx;
}
forceinline void*
Node::operator new(size_t s, Space& home) {
return home.ralloc(s);
}
/*
* Variable nodes
*
*/
forceinline
VarNode::VarNode(void) {}
forceinline
VarNode::VarNode(int x) :
Node(NF_NONE,x), ubm(NULL), lbm(NULL) {}
forceinline bool
VarNode::matched(BC bc) const {
if (bc == UBC)
return (nf & NF_M_UBC) != 0;
else
return (nf & NF_M_LBC) != 0;
}
forceinline void
VarNode::match(BC bc) {
if (bc == UBC)
nf |= NF_M_UBC;
else
nf |= NF_M_LBC;
}
forceinline void
VarNode::set_match(BC bc, Edge* p) {
if (bc == UBC)
ubm = p;
else
lbm = p;
}
forceinline void
VarNode::unmatch(BC bc) {
if (bc == UBC) {
nf &= ~NF_M_UBC; ubm = NULL;
} else {
nf &= ~NF_M_LBC; lbm = NULL;
}
}
forceinline Edge*
VarNode::get_match(BC bc) const {
if (bc == UBC)
return ubm;
else
return lbm;
}
/*
* Value nodes
*
*/
forceinline
ValNode::ValNode(void) {}
forceinline
ValNode::ValNode(int min, int max, int value,
int kidx, int kshift, int count) :
Node(NF_VAL,kshift), _klb(min), _kub(max), _kidx(kidx), _kcount(count),
noc(0),
lb(min), ublow(max), ub(max),
val(value) {}
forceinline void
ValNode::maxlow(int i) {
assert(i >= lb);
ublow = i;
}
forceinline int
ValNode::maxlow(void) const {
if (_klb == _kub) {
assert(ublow == lb);
}
return ublow;
}
forceinline void
ValNode::card_conflict(int c) {
noc = c;
}
forceinline void
ValNode::red_conflict(void) {
noc--;
assert(noc >= 0);
}
forceinline int
ValNode::card_conflict(void) const {
return noc;
}
forceinline int
ValNode::cap(BC bc) const {
if (bc == UBC)
return ub;
else
return lb;
}
forceinline bool
ValNode::matched(BC bc) const {
return cap(bc) == 0;
}
forceinline void
ValNode::reset(void) {
lb = _klb;
ublow = _kub;
ub = _kub;
noe = 0;
}
forceinline int
ValNode::kbound(BC bc) const {
if (bc == UBC) {
return _kub;
} else {
return _klb;
}
}
forceinline int
ValNode::kmax(void) const {
return _kub;
}
forceinline int
ValNode::kmin(void) const {
return _klb;
}
forceinline void
ValNode::kmin(int klb) {
_klb = klb;
}
forceinline void
ValNode::kmax(int kub) {
_kub = kub;
}
forceinline void
ValNode::dec(BC bc) {
if (bc == UBC) {
ub--;
} else {
lb--; ublow--;
}
}
forceinline void
ValNode::inc(BC bc) {
if (bc == UBC) {
ub++;
} else {
lb++; ublow++;
}
}
forceinline void
ValNode::match(BC bc) {
dec(bc);
}
forceinline void
ValNode::unmatch(BC bc) {
inc(bc);
}
forceinline void
ValNode::cap(BC bc, int c) {
if (bc == UBC)
ub = c;
else
lb = c;
}
forceinline void
ValNode::inc(void) {
_kcount++;
}
forceinline int
ValNode::kcount(void) const {
return _kcount;
}
forceinline void
ValNode::kcount(int c) {
_kcount = c;
}
forceinline void
ValNode::kindex(int i) {
_kidx = i;
}
forceinline int
ValNode::kindex(void) const {
return _kidx;
}
forceinline int
ValNode::incid_match(BC bc) const {
if (bc == LBC)
return _kub - ublow + _kcount;
else
return _kub - ub + _kcount;
}
forceinline bool
ValNode::sink(void) const {
// there are only incoming edges
// in case of the UBC-matching
return _kub - ub == noe;
}
forceinline bool
ValNode::source(void) const {
// there are only incoming edges
// in case of the UBC-matching
return _klb - lb == noe;
}
/*
* Edges
*
*/
forceinline void
Edge::unlink(void) {
// unlink from variable side
Edge* p = prev_edge;
Edge* n = next_edge;
if (p != NULL)
*p->next_ref() = n;
if (n != NULL)
*n->prev_ref() = p;
if (this == x->first()) {
Edge** ref = x->adj();
*ref = n;
x->first(n);
}
if (this == x->last())
x->last(p);
// unlink from value side
Edge* pv = prev_vedge;
Edge* nv = next_vedge;
if (pv != NULL)
*pv->vnext_ref() = nv;
if (nv != NULL)
*nv->vprev_ref() = pv;
if (this == v->first()) {
Edge** ref = v->adj();
*ref = nv;
v->first(nv);
}
if (this == v->last())
v->last(pv);
}
forceinline
Edge::Edge(VarNode* var, ValNode* val) :
x(var), v(val),
next_edge(NULL), prev_edge(NULL),
next_vedge(NULL), prev_vedge(NULL), ef(EF_NONE) {}
forceinline void
Edge::use(BC bc) {
if (bc == UBC)
ef |= EF_MRKUB;
else
ef |= EF_MRKLB;
}
forceinline void
Edge::free(BC bc) {
if (bc == UBC)
ef &= ~EF_MRKUB;
else
ef &= ~EF_MRKLB;
}
forceinline bool
Edge::used(BC bc) const {
if (bc == UBC)
return (ef & EF_MRKUB) != 0;
else
return (ef & EF_MRKLB) != 0;
}
forceinline Edge*
Edge::next(void) const {
return next_edge;
}
forceinline Edge*
Edge::next(bool t) const {
if (t) {
return next_vedge;
} else {
return next_edge;
}
}
forceinline Edge*
Edge::vnext(void) const {
return next_vedge;
}
forceinline Edge**
Edge::vnext_ref(void) {
return &next_vedge;
}
forceinline Edge*
Edge::prev(void) const {
return prev_edge;
}
forceinline Edge**
Edge::prev_ref(void) {
return &prev_edge;
}
forceinline Edge*
Edge::vprev(void) const {
return prev_vedge;
}
forceinline Edge**
Edge::vprev_ref(void) {
return &prev_vedge;
}
forceinline Edge**
Edge::next_ref(void) {
return &next_edge;
}
forceinline VarNode*
Edge::getVar(void) const {
assert(x != NULL);
return x;
}
forceinline ValNode*
Edge::getVal(void) const {
assert(v != NULL);
return v;
}
forceinline Node*
Edge::getMate(bool type) const {
if (type)
return x;
else
return v;
}
forceinline void
Edge::unmatch(BC bc) {
if (bc == UBC)
ef &= ~EF_UM;
else
ef &= ~EF_LM;
x->unmatch(bc); v->unmatch(bc);
}
forceinline void
Edge::unmatch(BC bc, bool node) {
if (bc == UBC)
ef &= ~EF_UM;
else
ef &= ~EF_LM;
if (node)
v->unmatch(bc);
else
x->unmatch(bc);
}
forceinline void
Edge::reset(BC bc) {
free(bc); unmatch(bc);
}
forceinline void
Edge::match(BC bc) {
if (bc == UBC)
ef |= EF_UM;
else
ef |= EF_LM;
x->match(bc);
x->set_match(bc,this);
v->match(bc);
}
forceinline bool
Edge::matched(BC bc) const {
if (bc == UBC)
return (ef & EF_UM) != 0;
else
return (ef & EF_LM) != 0;
}
forceinline void
Edge::del_edge(void) {
ef |= EF_DEL;
}
forceinline void
Edge::insert_edge(void) {
ef &= ~EF_DEL;
}
forceinline bool
Edge::deleted(void) const {
return (ef & EF_DEL) != 0;
}
forceinline void*
Edge::operator new(size_t s, Space& home) {
return home.ralloc(s);
}
/*
* Variable value graph
*
*/
template<class Card>
VarValGraph<Card>::VarValGraph(Space& home,
ViewArray<IntView>& x, ViewArray<Card>& k,
int smin, int smax)
: n_var(x.size()),
n_val(k.size()),
n_node(n_var + n_val),
sum_min(smin),
sum_max(smax) {
unsigned int noe = 0;
for (int i=x.size(); i--; )
noe += x[i].size();
vars = home.alloc<VarNode*>(n_var);
vals = home.alloc<ValNode*>(n_val);
for (int i = n_val; i--; ) {
int kmi = k[i].min();
int kma = k[i].max();
int kc = k[i].counter();
if (kc != kma) {
if (kmi >= kc) {
kmi -=kc;
assert(kmi >=0);
} else {
kmi = 0;
}
kma -= kc;
assert (kma > 0);
vals[i] = new (home)
ValNode(kmi, kma, k[i].card(), i, i + n_var, kc);
} else {
vals[i] = new (home)
ValNode(0, 0, k[i].card(), i, i + n_var, kc);
}
}
for (int i = n_var; i--; ) {
vars[i] = new (home) VarNode(i);
// get the space for the edges of the varnode
Edge** xadjacent = vars[i]->adj();
int j = 0;
for (ViewValues<IntView> xi(x[i]); xi(); ++xi) {
// get the correct index for the value
while(vals[j]->val < xi.val())
j++;
*xadjacent = new (home) Edge(vars[i],vals[j]);
vars[i]->noe++;
if (vars[i]->first() == NULL)
vars[i]->first(*xadjacent);
Edge* oldprev = vars[i]->last();
vars[i]->last(*xadjacent);
*vars[i]->last()->prev_ref() = oldprev;
if (vals[j]->first() == NULL) {
vals[j]->first(*xadjacent);
vals[j]->last(*xadjacent);
} else {
Edge* old = vals[j]->first();
vals[j]->first(*xadjacent);
*vals[j]->first()->vnext_ref() = old;
*old->vprev_ref() = vals[j]->first();
}
vals[j]->noe++;
xadjacent = (*xadjacent)->next_ref();
}
*xadjacent = NULL;
}
}
template<class Card>
inline ExecStatus
VarValGraph<Card>::min_require(Space& home,
ViewArray<IntView>& x,
ViewArray<Card>& k) {
for (int i = n_val; i--; ) {
ValNode* vln = vals[i];
if (vln->noe > 0) {
if (k[i].min() == vln->noe) {
// all variable nodes reachable from vln should be equal to vln->val
for (Edge* e = vln->first(); e != NULL; e = e->vnext()) {
VarNode* vrn = e->getVar();
for (Edge* f = vrn->first(); f != NULL; f = f->next())
if (f != e) {
ValNode* w = f->getVal();
w->noe--;
vrn->noe--;
f->del_edge();
f->unlink();
}
assert(vrn->noe == 1);
int vi = vrn->index();
GECODE_ME_CHECK(x[vi].eq(home, vln->val));
vars[vi] = vars[--n_var];
vars[vi]->index(vi);
x.move_lst(vi);
n_node--;
vln->noe--;
}
int vidx = vln->kindex();
if (Card::propagate)
GECODE_ME_CHECK(k[vidx].eq(home, k[vidx].min()));
k[vidx].counter(k[vidx].min());
vln->cap(UBC,0);
vln->cap(LBC,0);
vln->maxlow(0);
if (sum_min >= k[vidx].min())
sum_min -= k[vidx].min();
if (sum_max >= k[vidx].max())
sum_max -= k[vidx].max();
}
} else {
vals[i]->cap(UBC,0);
vals[i]->cap(LBC,0);
vals[i]->maxlow(0);
vals[i]->kmax(0);
vals[i]->kmin(0);
}
if (Card::propagate && (k[i].counter() == 0))
GECODE_ME_CHECK(k[i].lq(home, vals[i]->noe));
}
for (int i = n_val; i--; )
vals[i]->index(n_var + i);
return ES_OK;
}
template<class Card> template<BC bc>
forceinline bool
VarValGraph<Card>::augmenting_path(Node* v) {
Region r;
NodeStack ns(r,n_node);
BitSet visited(r,static_cast<unsigned int>(n_node));
Edge** start = r.alloc<Edge*>(n_node);
// keep track of the nodes that have already been visited
Node* sn = v;
// mark the start partition
bool sp = sn->type();
// nodes in sp only follow free edges
// nodes in V - sp only follow matched edges
for (int i = n_node; i--; )
if (i >= n_var) {
vals[i-n_var]->inedge(NULL);
start[i] = vals[i-n_var]->first();
} else {
vars[i]->inedge(NULL);
start[i] = vars[i]->first();
}
v->inedge(NULL);
ns.push(v);
visited.set(static_cast<unsigned int>(v->index()));
while (!ns.empty()) {
Node* vv = ns.top();
Edge* e = NULL;
if (vv->type() == sp) {
e = start[vv->index()];
while ((e != NULL) && e->matched(bc))
e = e->next(vv->type());
} else {
e = start[vv->index()];
while ((e != NULL) && !e->matched(bc))
e = e->next(vv->type());
start[vv->index()] = e;
}
if (e != NULL) {
start[vv->index()] = e->next(vv->type());
Node* w = e->getMate(vv->type());
if (!visited.get(static_cast<unsigned int>(w->index()))) {
// unexplored path
bool m = w->type() ?
static_cast<ValNode*>(w)->matched(bc) :
static_cast<VarNode*>(w)->matched(bc);
if (!m && w->type() != sp) {
if (vv->inedge() != NULL) {
// augmenting path of length l > 1
e->match(bc);
break;
} else {
// augmenting path of length l = 1
e->match(bc);
ns.pop();
return true;
}
} else {
w->inedge(e);
visited.set(static_cast<unsigned int>(w->index()));
// find matching edge m incident with w
ns.push(w);
}
}
} else {
// tried all outgoing edges without finding an augmenting path
ns.pop();
}
}
bool pathfound = !ns.empty();
while (!ns.empty()) {
Node* t = ns.pop();
if (t != sn) {
Edge* in = t->inedge();
if (t->type() != sp) {
in->match(bc);
} else if (!sp) {
in->unmatch(bc,!sp);
} else {
in->unmatch(bc);
}
}
}
return pathfound;
}
template<class Card>
inline ExecStatus
VarValGraph<Card>::sync(ViewArray<IntView>& x, ViewArray<Card>& k) {
Region r;
// A node can be pushed twice (once when checking cardinality and later again)
NodeStack re(r,2*n_node);
// synchronize cardinality variables
if (Card::propagate) {
for (int i = n_val; i--; ) {
ValNode* v = vals[i];
int inc_ubc = v->incid_match(UBC);
int inc_lbc = v->incid_match(LBC);
if (v->noe == 0) {
inc_ubc = 0;
inc_lbc = 0;
}
int rm = v->kmax() - k[i].max();
// the cardinality bounds have been modified
if ((k[i].max() < v->kmax()) || (k[i].min() > v->kmin())) {
if ((k[i].max() != k[i].counter()) || (k[i].max() == 0)) {
// update the bounds
v->kmax(k[i].max());
v->kmin(k[i].min());
//everything is fine
if (inc_ubc <= k[i].max()) {
// adjust capacities
v->cap(UBC, k[i].max() - inc_ubc);
v->maxlow(k[i].max() - inc_lbc);
if (v->kmin() == v->kmax())
v->cap(LBC, k[i].max() - inc_lbc);
} else {
// set cap to max and resolve conflicts on view side
// set to full capacity for later rescheduling
if (v->cap(UBC))
v->cap(UBC,k[i].max());
v->maxlow(k[i].max() - (inc_lbc));
if (v->kmin() == v->kmax())
v->cap(LBC,k[i].max() - (inc_lbc));
v->card_conflict(rm);
}
}
}
if (inc_lbc < k[i].min() && v->noe > 0) {
v->cap(LBC, k[i].min() - inc_lbc);
re.push(v);
}
}
for (int i = n_var; i--; ) {
Edge* mub = vars[i]->get_match(UBC);
if (mub != NULL) {
ValNode* vu = mub->getVal();
if ((vars[i]->noe != 1) && vu->card_conflict()) {
vu->red_conflict();
mub->unmatch(UBC,vars[i]->type());
re.push(vars[i]);
}
}
}
}
// go on with synchronization
assert(x.size() == n_var);
for (int i = n_var; i--; ) {
VarNode* vrn = vars[i];
if (static_cast<int>(x[i].size()) != vrn->noe) {
// if the variable is already assigned
if (x[i].assigned()) {
int v = x[i].val();
Edge* mub = vrn->get_match(UBC);
if ((mub != NULL) && (v != mub->getVal()->val)) {
mub->unmatch(UBC);
re.push(vars[i]);
}
Edge* mlb = vrn->get_match(LBC);
if (mlb != NULL) {
ValNode* vln = mlb->getVal();
if (v != vln->val) {
mlb->unmatch(LBC);
if (vln->incid_match(LBC) < vln->kmin())
re.push(vln);
}
}
for (Edge* e = vrn->first(); e != NULL; e = e->next()) {
ValNode* vln = e->getVal();
if (vln->val != v) {
vrn->noe--;
e->getVal()->noe--;
e->del_edge();
e->unlink();
}
}
} else {
// delete the edge
ViewValues<IntView> xiter(x[i]);
Edge* mub = vrn->get_match(UBC);
Edge* mlb = vrn->get_match(LBC);
Edge** p = vrn->adj();
Edge* e = *p;
GECODE_ASSUME(e != NULL);
do {
// search the edge that has to be deleted
while ((e != NULL) && (e->getVal()->val < xiter.val())) {
// Skip edge
e->getVal()->noe--;
vrn->noe--;
e->del_edge();
e->unlink();
e = e ->next();
*p = e;
}
GECODE_ASSUME(e != NULL);
assert(xiter.val() == e->getVal()->val);
// This edge must be kept
e->free(UBC);
e->free(LBC);
++xiter;
p = e->next_ref();
e = e->next();
} while (xiter());
*p = NULL;
while (e != NULL) {
e->getVar()->noe--;
e->getVal()->noe--;
e->del_edge();
e->unlink();
e = e->next();
}
if ((mub != NULL) && mub->deleted()) {
mub->unmatch(UBC);
re.push(vars[i]);
}
//lower bound matching can be zero
if ((mlb != NULL) && mlb->deleted()) {
ValNode* vln = mlb->getVal();
mlb->unmatch(LBC);
if (vln->incid_match(LBC) < vln->kmin())
re.push(vln);
}
}
}
vars[i]->index(i);
}
for (int i = n_val; i--; ) {
if ((k[i].min() > vals[i]->noe) && (k[i].counter() == 0))
return ES_FAILED;
vals[i]->index(n_var + i);
}
// start repair
while (!re.empty()) {
Node* n = re.pop();
if (!n->removed()) {
if (!n->type()) {
VarNode* vrn = static_cast<VarNode*>(n);
if (!vrn->matched(UBC) && !augmenting_path<UBC>(vrn))
return ES_FAILED;
} else {
ValNode* vln = static_cast<ValNode*>(n);
while (!vln->matched(LBC))
if (!augmenting_path<LBC>(vln))
return ES_FAILED;
}
}
}
return ES_OK;
}
template<class Card> template<BC bc>
inline ExecStatus
VarValGraph<Card>::narrow(Space& home,
ViewArray<IntView>& x, ViewArray<Card>& k) {
for (int i = n_var; i--; )
if (vars[i]->noe == 1) {
ValNode* v = vars[i]->first()->getVal();
vars[i]->first()->free(bc);
GECODE_ME_CHECK(x[i].eq(home, v->val));
v->inc();
}
for (int i = n_val; i--; ) {
ValNode* v = vals[i];
if (Card::propagate && (k[i].counter() == 0))
GECODE_ME_CHECK(k[i].lq(home, v->noe));
if (v->noe > 0) {
if (Card::propagate)
GECODE_ME_CHECK(k[i].lq(home, v->noe));
// If the maximum number of occurences of a value is reached
// it cannot be consumed by another view
if (v->kcount() == v->kmax()) {
int vidx = v->kindex();
k[i].counter(v->kcount());
if (Card::propagate)
GECODE_ME_CHECK(k[i].eq(home, k[i].counter()));
bool delall = v->card_conflict() && (v->noe > v->kmax());
for (Edge* e = v->last(); e != NULL; e = e->vprev()) {
VarNode* vrn = e->getVar();
if (vrn->noe == 1) {
vrn->noe--;
v->noe--;
int vi= vrn->index();
x.move_lst(vi);
vars[vi] = vars[--n_var];
vars[vi]->index(vi);
n_node--;
e->del_edge();
e->unlink();
} else if (delall) {
GECODE_ME_CHECK(x[vrn->index()].nq(home, v->val));
vrn->noe--;
v->noe--;
e->del_edge();
e->unlink();
}
}
v->cap(UBC,0);
v->cap(LBC,0);
v->maxlow(0);
if (sum_min >= k[vidx].min())
sum_min -= k[vidx].min();
if (sum_max >= k[vidx].max())
sum_max -= k[vidx].max();
} else if (v->kcount() > 0) {
v->kcount(0);
}
}
}
for (int i = n_var; i--; )
vars[i]->index(i);
for (int i = n_val; i--; ) {
if (vals[i]->noe == 0) {
vals[i]->cap(UBC,0);
vals[i]->cap(LBC,0);
vals[i]->maxlow(0);
}
vals[i]->index(n_var + i);
}
for (int i = n_var; i--; ) {
if (vars[i]->noe > 1) {
for (Edge* e = vars[i]->first(); e != NULL; e = e->next()) {
if (!e->matched(bc) && !e->used(bc)) {
GECODE_ME_CHECK(x[i].nq(home, e->getVal()->val));
} else {
e->free(bc);
}
}
}
}
return ES_OK;
}
template<class Card> template<BC bc>
inline ExecStatus
VarValGraph<Card>::maximum_matching(void) {
int card_match = 0;
// find an intial matching in O(n*d)
// greedy algorithm
for (int i = n_val; i--; )
for (Edge* e = vals[i]->first(); e != NULL ; e = e->vnext())
if (!e->getVar()->matched(bc) && !vals[i]->matched(bc)) {
e->match(bc); card_match++;
}
Region r;
switch (bc) {
case LBC:
if (card_match < sum_min) {
Support::StaticStack<ValNode*,Region> free(r,n_val);
// find failed nodes
for (int i = n_val; i--; )
if (!vals[i]->matched(LBC))
free.push(vals[i]);
while (!free.empty()) {
ValNode* v = free.pop();
while (!v->matched(LBC))
if (augmenting_path<LBC>(v))
card_match++;
else
break;
}
return (card_match >= sum_min) ? ES_OK : ES_FAILED;
} else {
return ES_OK;
}
break;
case UBC:
if (card_match < n_var) {
Support::StaticStack<VarNode*,Region> free(r,n_var);
// find failed nodes
for (int i = n_var; i--; )
if (!vars[i]->matched(UBC))
free.push(vars[i]);
while (!free.empty()) {
VarNode* v = free.pop();
if (!v->matched(UBC) && augmenting_path<UBC>(v))
card_match++;
}
return (card_match >= n_var) ? ES_OK : ES_FAILED;
} else {
return ES_OK;
}
break;
default: GECODE_NEVER;
}
GECODE_NEVER;
return ES_FAILED;
}
template<class Card> template<BC bc>
forceinline void
VarValGraph<Card>::free_alternating_paths(void) {
Region r;
NodeStack ns(r,n_node);
BitSet visited(r,static_cast<unsigned int>(n_node));
switch (bc) {
case LBC:
// after a maximum matching on the value nodes there still can be
// free value nodes, hence we have to consider ALL nodes whether
// they are the starting point of an even alternating path in G
for (int i = n_var; i--; )
if (!vars[i]->matched(LBC)) {
ns.push(vars[i]);
visited.set(static_cast<unsigned int>(vars[i]->index()));
}
for (int i = n_val; i--; )
if (!vals[i]->matched(LBC)) {
ns.push(vals[i]);
visited.set(static_cast<unsigned int>(vals[i]->index()));
}
break;
case UBC:
// clearly, after a maximum matching on the x variables
// corresponding to a set cover on x there are NO free var nodes
for (int i = n_val; i--; )
if (!vals[i]->matched(UBC)) {
ns.push(vals[i]);
visited.set(static_cast<unsigned int>(vals[i]->index()));
}
break;
default: GECODE_NEVER;
}
while (!ns.empty()) {
Node* node = ns.pop();
if (node->type()) {
// ValNode
ValNode* vln = static_cast<ValNode*>(node);
for (Edge* cur = vln->first(); cur != NULL; cur = cur->vnext()) {
VarNode* mate = cur->getVar();
switch (bc) {
case LBC:
if (cur->matched(LBC)) {
// mark the edge
cur->use(LBC);
if (!visited.get(static_cast<unsigned int>(mate->index()))) {
ns.push(mate);
visited.set(static_cast<unsigned int>(mate->index()));
}
}
break;
case UBC:
if (!cur->matched(UBC)) {
// mark the edge
cur->use(UBC);
if (!visited.get(static_cast<unsigned int>(mate->index()))) {
ns.push(mate);
visited.set(static_cast<unsigned int>(mate->index()));
}
}
break;
default: GECODE_NEVER;
}
}
} else {
// VarNode
VarNode* vrn = static_cast<VarNode*>(node);
switch (bc) {
case LBC:
// after LBC-matching we can follow every unmatched edge
for (Edge* cur = vrn->first(); cur != NULL; cur = cur->next()) {
ValNode* mate = cur->getVal();
if (!cur->matched(LBC)) {
cur->use(LBC);
if (!visited.get(static_cast<unsigned int>(mate->index()))) {
ns.push(mate);
visited.set(static_cast<unsigned int>(mate->index()));
}
}
}
break;
case UBC:
// after UBC-matching we can only follow a matched edge
{
Edge* cur = vrn->get_match(UBC);
if (cur != NULL) {
cur->use(UBC);
ValNode* mate = cur->getVal();
if (!visited.get(static_cast<unsigned int>(mate->index()))) {
ns.push(mate);
visited.set(static_cast<unsigned int>(mate->index()));
}
}
}
break;
default: GECODE_NEVER;
}
}
}
}
template<class Card> template<BC bc>
void
VarValGraph<Card>::dfs(Node* v,
BitSet& inscc, BitSet& in_unfinished, int dfsnum[],
NodeStack& roots, NodeStack& unfinished,
int& count) {
count++;
int v_index = v->index();
dfsnum[v_index] = count;
inscc.set(static_cast<unsigned int>(v_index));
in_unfinished.set(static_cast<unsigned int>(v_index));
unfinished.push(v);
roots.push(v);
for (Edge* e = v->first(); e != NULL; e = e->next(v->type())) {
bool m;
switch (bc) {
case LBC:
m = v->type() ? e->matched(LBC) : !e->matched(LBC);
break;
case UBC:
m = v->type() ? !e->matched(UBC) : e->matched(UBC);
break;
default: GECODE_NEVER;
}
if (m) {
Node* w = e->getMate(v->type());
int w_index = w->index();
assert(w_index < n_node);
if (!inscc.get(static_cast<unsigned int>(w_index))) {
// w is an uncompleted scc
w->inedge(e);
dfs<bc>(w, inscc, in_unfinished, dfsnum,
roots, unfinished, count);
} else if (in_unfinished.get(static_cast<unsigned int>(w_index))) {
// even alternating cycle found mark the edge closing the cycle,
// completing the scc
e->use(bc);
// if w belongs to an scc we detected earlier
// merge components
assert(roots.top()->index() < n_node);
while (dfsnum[roots.top()->index()] > dfsnum[w_index]) {
roots.pop();
}
}
}
}
if (v == roots.top()) {
while (v != unfinished.top()) {
// w belongs to the scc with root v
Node* w = unfinished.top();
w->inedge()->use(bc);
in_unfinished.clear(static_cast<unsigned int>(w->index()));
unfinished.pop();
}
assert(v == unfinished.top());
in_unfinished.clear(static_cast<unsigned int>(v_index));
roots.pop();
unfinished.pop();
}
}
template<class Card> template<BC bc>
forceinline void
VarValGraph<Card>::strongly_connected_components(void) {
Region r;
BitSet inscc(r,static_cast<unsigned int>(n_node));
BitSet in_unfinished(r,static_cast<unsigned int>(n_node));
int* dfsnum = r.alloc<int>(n_node);
for (int i = n_node; i--; )
dfsnum[i]=0;
int count = 0;
NodeStack roots(r,n_node);
NodeStack unfinished(r,n_node);
for (int i = n_var; i--; )
dfs<bc>(vars[i], inscc, in_unfinished, dfsnum,
roots, unfinished, count);
}
template<class Card>
forceinline void*
VarValGraph<Card>::operator new(size_t t, Space& home) {
return home.ralloc(t);
}
}}}
// STATISTICS: int-prop
Gecode::Int::GCC::Edge
Class for edges in the variable-value-graph.
Definition dom-sup.hpp:264
Gecode::Int::GCC::Edge::use
void use(BC bc)
Update.
Definition dom-sup.hpp:851
Gecode::Int::GCC::Edge::free
void free(BC bc)
Mark the edge as unused.
Definition dom-sup.hpp:858
Gecode::Int::GCC::Edge::vprev
Edge * vprev(void) const
return the pointer to the previous edge incident on v
Definition dom-sup.hpp:901
Gecode::Int::GCC::Edge::vnext
Edge * vnext(void) const
return the pointer to the next edge incident on v
Definition dom-sup.hpp:885
Gecode::Int::GCC::Edge::del_edge
void del_edge(void)
Mark the edge as deleted during synchronization.
Definition dom-sup.hpp:978
Gecode::Int::GCC::Edge::prev_ref
Edge ** prev_ref(void)
return the reference to the previous edge incident on x
Definition dom-sup.hpp:897
Gecode::Int::GCC::Edge::deleted
bool deleted(void) const
return whether the edge has been deleted from the graph
Definition dom-sup.hpp:989
Gecode::Int::GCC::Edge::match
void match(BC bc)
Match the edge.
Definition dom-sup.hpp:959
Gecode::Int::GCC::Edge::unmatch
void unmatch(BC bc)
Unmatch the edge and the incident nodes.
Definition dom-sup.hpp:933
Gecode::Int::GCC::Edge::vprev_ref
Edge ** vprev_ref(void)
return the reference to the previous edge incident on v
Definition dom-sup.hpp:905
Gecode::Int::GCC::Edge::prev
Edge * prev(void) const
return the pointer to the previous edge incident on x
Definition dom-sup.hpp:893
Gecode::Int::GCC::Edge::unlink
void unlink(void)
Unlink the edge from the linked list of edges.
Definition dom-sup.hpp:808
Gecode::Int::GCC::Edge::insert_edge
void insert_edge(void)
Insert the edge again.
Definition dom-sup.hpp:983
Gecode::Int::GCC::Edge::vnext_ref
Edge ** vnext_ref(void)
return the reference to the next edge incident on v
Definition dom-sup.hpp:889
Gecode::Int::GCC::Edge::Edge
Edge(void)
Default constructor.
Definition dom-sup.hpp:299
Gecode::Int::GCC::Edge::getVal
ValNode * getVal(void) const
return the pointer to the value node v of this edge
Definition dom-sup.hpp:919
Gecode::Int::GCC::Edge::getMate
Node * getMate(bool t) const
return pointer to x if t = true otherwise return v
Definition dom-sup.hpp:925
Gecode::Int::GCC::Edge::matched
bool matched(BC bc) const
return whether the edge is matched
Definition dom-sup.hpp:970
Gecode::Int::GCC::Edge::reset
void reset(BC bc)
Reset the edge (free the edge, and unmatch the edge).
Definition dom-sup.hpp:954
Gecode::Int::GCC::Edge::used
bool used(BC bc) const
Whether the edge is used.
Definition dom-sup.hpp:865
Gecode::Int::GCC::Edge::next
Edge * next(void) const
return the pointer to the next edge incident on x
Definition dom-sup.hpp:872
Gecode::Int::GCC::Edge::next_ref
Edge ** next_ref(void)
return the reference to the next edge incident on x
Definition dom-sup.hpp:909
Gecode::Int::GCC::Edge::getVar
VarNode * getVar(void) const
return the pointer to the variable node x of this edge
Definition dom-sup.hpp:913
Gecode::Int::GCC::Edge::next
Edge * next(bool t) const
return a pointer to the next edge If t is false the function returns the next edge incident on x othe...
Definition dom-sup.hpp:876
Gecode::Int::GCC::Node
Base class for nodes in the variable-value-graph.
Definition dom-sup.hpp:52
Gecode::Int::GCC::Node::e
Edge * e
Stores all incident edges on the node.
Definition dom-sup.hpp:55
Gecode::Int::GCC::Node::lst
Edge * lst
Last edge.
Definition dom-sup.hpp:59
Gecode::Int::GCC::Node::type
bool type(void) const
Return the type of the node (false for a variable node).
Definition dom-sup.hpp:534
Gecode::Int::GCC::Node::idx
int idx
Index.
Definition dom-sup.hpp:63
Gecode::Int::GCC::Node::last
Edge * last(void) const
Return pointer to the last incident edge.
Definition dom-sup.hpp:522
Gecode::Int::GCC::Node::removed
bool removed(void) const
check whether a node has been removed from the graph
Definition dom-sup.hpp:546
Gecode::Int::GCC::Node::fst
Edge * fst
First edge.
Definition dom-sup.hpp:57
Gecode::Int::GCC::Node::Node
Node(void)
Default constructor.
Definition dom-sup.hpp:507
Gecode::Int::GCC::Node::noe
int noe
stores the number of incident edges on the node
Definition dom-sup.hpp:79
Gecode::Int::GCC::Node::NodeFlag
NodeFlag
Flags for nodes.
Definition dom-sup.hpp:65
Gecode::Int::GCC::Node::NF_M_UBC
@ NF_M_UBC
Whether matched for UBC.
Definition dom-sup.hpp:73
Gecode::Int::GCC::Node::NF_VAL
@ NF_VAL
Whether node is a value node.
Definition dom-sup.hpp:69
Gecode::Int::GCC::Node::NF_NONE
@ NF_NONE
No flags set.
Definition dom-sup.hpp:67
Gecode::Int::GCC::Node::NF_M_LBC
@ NF_M_LBC
Whether matched for LBC.
Definition dom-sup.hpp:71
Gecode::Int::GCC::Node::inedge
Edge * inedge(void) const
Return pointer to the node's inedge.
Definition dom-sup.hpp:538
Gecode::Int::GCC::Node::first
Edge * first(void) const
Return pointer to the first incident edge.
Definition dom-sup.hpp:518
Gecode::Int::GCC::Node::nf
unsigned char nf
Flags for node.
Definition dom-sup.hpp:76
Gecode::Int::GCC::Node::ie
Edge * ie
Single incoming edge used for storing a path in the algorithms.
Definition dom-sup.hpp:61
Gecode::Int::GCC::Node::adj
Edge ** adj(void)
Return reference to the incident edges.
Definition dom-sup.hpp:514
Gecode::Int::GCC::Node::index
int index(void) const
Get index of either variable or value.
Definition dom-sup.hpp:554
Gecode::Int::GCC::ValNode
Value node.
Definition dom-sup.hpp:166
Gecode::Int::GCC::ValNode::lb
int lb
Minimal capacity of the value node.
Definition dom-sup.hpp:179
Gecode::Int::GCC::ValNode::_kidx
int _kidx
Index to acces the value via cardinality array k.
Definition dom-sup.hpp:173
Gecode::Int::GCC::ValNode::unmatch
void unmatch(BC bc)
unmatch the node
Definition dom-sup.hpp:740
Gecode::Int::GCC::ValNode::kmin
int kmin(void) const
return the minimal node capacity as stored in k
Definition dom-sup.hpp:701
Gecode::Int::GCC::ValNode::kbound
int kbound(BC bc) const
return minimal or maximal capacity
Definition dom-sup.hpp:687
Gecode::Int::GCC::ValNode::match
void match(BC bc)
match the node
Definition dom-sup.hpp:735
Gecode::Int::GCC::ValNode::incid_match
int incid_match(BC bc) const
returns the number of incident matching edges on a value node
Definition dom-sup.hpp:779
Gecode::Int::GCC::ValNode::_klb
int _klb
Minimal required occurence of the value as stored in k.
Definition dom-sup.hpp:169
Gecode::Int::GCC::ValNode::_kcount
int _kcount
Stores the current number of occurences of the value.
Definition dom-sup.hpp:175
Gecode::Int::GCC::ValNode::ublow
int ublow
Smallest maximal capacity of the value node.
Definition dom-sup.hpp:181
Gecode::Int::GCC::ValNode::matched
bool matched(BC bc) const
returns true if the node is matched in BC, false otherwise
Definition dom-sup.hpp:674
Gecode::Int::GCC::ValNode::source
bool source(void) const
tests whether the node is a source
Definition dom-sup.hpp:795
Gecode::Int::GCC::ValNode::maxlow
int maxlow(void) const
get max cap for LBC
Definition dom-sup.hpp:642
Gecode::Int::GCC::ValNode::card_conflict
int card_conflict(void) const
Check whether the value node is conflicting.
Definition dom-sup.hpp:662
Gecode::Int::GCC::ValNode::noc
int noc
Store numbre of conflicting matching edges.
Definition dom-sup.hpp:177
Gecode::Int::GCC::ValNode::card_conflict
void card_conflict(int c)
Mark the value node as conflicting in case of variable cardinalities.
Definition dom-sup.hpp:651
Gecode::Int::GCC::ValNode::dec
void dec(BC bc)
decrease the node-capacity
Definition dom-sup.hpp:717
Gecode::Int::GCC::ValNode::reset
void reset(void)
node reset to original capacity values
Definition dom-sup.hpp:679
Gecode::Int::GCC::ValNode::val
int val
Stores the value of the node.
Definition dom-sup.hpp:186
Gecode::Int::GCC::ValNode::kmax
int kmax(void) const
return the maximal node capacity as stored in k
Definition dom-sup.hpp:696
Gecode::Int::GCC::ValNode::red_conflict
void red_conflict(void)
Reduce the conflict counter.
Definition dom-sup.hpp:656
Gecode::Int::GCC::ValNode::kcount
int kcount(void) const
returns the current number of occurences of the value
Definition dom-sup.hpp:758
Gecode::Int::GCC::ValNode::sink
bool sink(void) const
tests whether the node is a sink
Definition dom-sup.hpp:788
Gecode::Int::GCC::ValNode::_kub
int _kub
Maximal required occurence of the value as stored in k.
Definition dom-sup.hpp:171
Gecode::Int::GCC::ValNode::ub
int ub
Maximal capacity of the value node.
Definition dom-sup.hpp:183
Gecode::Int::GCC::ValNode::cap
int cap(BC bc) const
return the the node-capacity
Definition dom-sup.hpp:667
Gecode::Int::GCC::ValNode::kindex
int kindex(void) const
returns the index in cardinality array k
Definition dom-sup.hpp:773
Gecode::Int::GCC::ValNode::ValNode
ValNode(void)
Default constructor.
Definition dom-sup.hpp:625
Gecode::Int::GCC::ValNode::inc
void inc(void)
increases the value counter
Definition dom-sup.hpp:753
Gecode::Int::GCC::VarNode
Variable node
Definition dom-sup.hpp:131
Gecode::Int::GCC::VarNode::ubm
Edge * ubm
Stores the matching edge on this node in the UBC.
Definition dom-sup.hpp:134
Gecode::Int::GCC::VarNode::match
void match(BC bc)
Set node to matched.
Definition dom-sup.hpp:585
Gecode::Int::GCC::VarNode::VarNode
VarNode(void)
Default constructor.
Definition dom-sup.hpp:570
Gecode::Int::GCC::VarNode::matched
bool matched(BC bc) const
tests whether the node is matched or not
Definition dom-sup.hpp:577
Gecode::Int::GCC::VarNode::set_match
void set_match(BC bc, Edge *m)
Set the pointer of the matching edge to m.
Definition dom-sup.hpp:593
Gecode::Int::GCC::VarNode::get_match
Edge * get_match(BC bc) const
Return the matching edge on the node.
Definition dom-sup.hpp:610
Gecode::Int::GCC::VarNode::unmatch
void unmatch(BC bc)
Unmatch the node.
Definition dom-sup.hpp:601
Gecode::Int::GCC::VarNode::lbm
Edge * lbm
Stores the matching edge on this node in the LBC.
Definition dom-sup.hpp:136
Gecode::Int::GCC::VarValGraph::maximum_matching
ExecStatus maximum_matching(void)
Compute a maximum matching M on the graph.
Definition dom-sup.hpp:1511
Gecode::Int::GCC::VarValGraph::min_require
ExecStatus min_require(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k)
Check whether minimum requirements shrink variable domains.
Definition dom-sup.hpp:1078
Gecode::Int::GCC::VarValGraph::strongly_connected_components
void strongly_connected_components(void)
Compute possible strongly connected components of the graph.
Definition dom-sup.hpp:1745
Gecode::Int::GCC::VarValGraph::narrow
ExecStatus narrow(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k)
Remove edges that do not belong to any maximal matching.
Definition dom-sup.hpp:1417
Gecode::Int::GCC::VarValGraph::dfs
void dfs(Node *, BitSet &, BitSet &, int[], NodeStack &, NodeStack &, int &)
Perform depth-first search on the graph.
Definition dom-sup.hpp:1681
Gecode::Int::GCC::VarValGraph::free_alternating_paths
void free_alternating_paths(void)
Compute possible free alternating paths in the graph.
Definition dom-sup.hpp:1575
Gecode::Int::GCC::VarValGraph::augmenting_path
bool augmenting_path(Node *)
Test whether the current maximal matching on the graph can be augmented by an alternating path starti...
Definition dom-sup.hpp:1144
Gecode::Int::GCC::VarValGraph::sync
ExecStatus sync(ViewArray< IntView > &x, ViewArray< Card > &k)
Synchronization of the graph.
Definition dom-sup.hpp:1237
Gecode::Int::GCC::VarValGraph::VarValGraph
VarValGraph(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k, int smin, int smax)
Constructor for the variable-value-graph.
Definition dom-sup.hpp:1004
Gecode::Int::ViewValues
Value iterator for integer views.
Definition view.hpp:94
Gecode::Iter::Ranges::ToValues::val
int val(void) const
Return current value.
Definition ranges-values.hpp:129
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Space::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition core.hpp:2837
Gecode::Support::BitSetBase::get
bool get(unsigned int i) const
Access value at bit i.
Definition bitset-base.hpp:590
Gecode::Support::BitSetBase::clear
void clear(unsigned int i)
Clear bit i.
Definition bitset-base.hpp:600
Gecode::Support::BitSetBase::set
void set(unsigned int i)
Set bit i.
Definition bitset-base.hpp:595
Gecode::Support::BitSet
Simple bitsets.
Definition bitset.hpp:45
Gecode::Support::StaticStack
Stack with fixed number of elements.
Definition static-stack.hpp:42
Gecode::Support::StaticStack::push
void push(const T &x)
Push element x on top of stack.
Definition static-stack.hpp:137
Gecode::Support::StaticStack::pop
T pop(void)
Pop topmost element from stack and return it.
Definition static-stack.hpp:116
Gecode::Support::StaticStack::empty
bool empty(void) const
Test whether stack is empty.
Definition static-stack.hpp:98
Gecode::Support::StaticStack::top
T & top(void) const
Return element on top of stack.
Definition static-stack.hpp:123
Gecode::ViewArray
View arrays.
Definition array.hpp:253
Gecode::ViewArray::move_lst
void move_lst(int i)
Move view from position size()-1 to position i (truncate array by one).
Definition array.hpp:1236
Gecode::ViewArray::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1156
Test::Base::next
Base * next(void) const
Return next test.
Definition test.hpp:58
GECODE_ME_CHECK
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
Gecode::Int::GCC
Global cardinality propagators (Counting).
Gecode::Int::GCC::BC
BC
Bounds constraint (BC) type.
Definition dom-sup.hpp:48
Gecode::Int::GCC::UBC
@ UBC
Definition dom-sup.hpp:48
Gecode::Int::GCC::LBC
@ LBC
Definition dom-sup.hpp:48
Gecode::Int
Finite domain integers.
Gecode
Gecode toplevel namespace
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::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:67
Gecode::roots
void roots(Home home, const IntVarArgs &x, SetVar y, SetVar z)
Post constraint .
Definition aliases.hpp:163
Gecode::dfs
T * dfs(T *s, const Search::Options &o=Search::Options::def)
Invoke depth-first search engine for subclass T of space s with options o.
Definition dfs.hpp:73
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition core.hpp:476
Gecode::ES_FAILED
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:49
forceinline
#define forceinline
Definition config.hpp:187
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56
GECODE_ASSUME
#define GECODE_ASSUME(p)
Assert certain property.
Definition macros.hpp:114