40namespace Gecode {
namespace Int {
namespace GCC {
92 bool type(
void)
const;
102 int index(
void)
const;
122 static void*
operator new(
size_t s,
Space& home);
124 static void operator delete(
void*,
Space&) {};
126 static void operator delete(
void*) {};
223 bool sink(
void)
const;
227 int kmin(
void)
const;
229 int kmax(
void)
const;
247 int cap(
BC bc)
const;
249 void cap(
BC bc,
int c);
373 static void*
operator new(
size_t s,
Space& home);
375 static void operator delete(
void*,
Space&) {};
377 static void operator delete(
void*) {};
495 void*
operator new(
size_t t,
Space& home);
497 void operator delete(
void*,
Space&) {}
510 : e(NULL), fst(NULL), lst(NULL), ie(NULL), idx(i),
511 nf(static_cast<unsigned char>(nf0)), noe(0) {}
559 Node::operator
new(
size_t s,
Space& home) {
560 return home.ralloc(s);
574 Node(NF_NONE,
x), ubm(NULL), lbm(NULL) {}
603 nf &= ~NF_M_UBC;
ubm = NULL;
605 nf &= ~NF_M_LBC;
lbm = NULL;
629 int kidx,
int kshift,
int count) :
630 Node(NF_VAL,kshift), _klb(
min), _kub(
max), _kidx(kidx), _kcount(
count),
818 if (
this == x->
first()) {
824 if (
this == x->
last())
828 Edge* pv = prev_vedge;
829 Edge* nv = next_vedge;
835 if (
this == v->
first()) {
840 if (
this == v->
last())
847 next_edge(NULL), prev_edge(NULL),
848 next_vedge(NULL), prev_vedge(NULL), ef(EF_NONE) {}
867 return (ef & EF_MRKUB) != 0;
869 return (ef & EF_MRKLB) != 0;
972 return (ef & EF_UM) != 0;
974 return (ef & EF_LM) != 0;
990 return (ef & EF_DEL) != 0;
994 Edge::operator
new(
size_t s,
Space& home) {
995 return home.ralloc(s);
1003 template<
class Card>
1009 n_node(n_var + n_val),
1013 unsigned int noe = 0;
1014 for (
int i=
x.size(); i--; )
1020 for (
int i = n_val; i--; ) {
1021 int kmi = k[i].min();
1022 int kma = k[i].max();
1023 int kc = k[i].counter();
1033 vals[i] =
new (home)
1034 ValNode(kmi, kma, k[i].card(), i, i + n_var, kc);
1036 vals[i] =
new (home)
1037 ValNode(0, 0, k[i].card(), i, i + n_var, kc);
1041 for (
int i = n_var; i--; ) {
1042 vars[i] =
new (home)
VarNode(i);
1044 Edge** xadjacent = vars[i]->
adj();
1049 while(vals[j]->val < xi.
val())
1051 *xadjacent =
new (home)
Edge(vars[i],vals[j]);
1053 if (vars[i]->first() == NULL)
1054 vars[i]->
first(*xadjacent);
1056 vars[i]->
last(*xadjacent);
1059 if (vals[j]->first() == NULL) {
1060 vals[j]->
first(*xadjacent);
1061 vals[j]->
last(*xadjacent);
1064 vals[j]->
first(*xadjacent);
1069 xadjacent = (*xadjacent)->
next_ref();
1076 template<
class Card>
1081 for (
int i = n_val; i--; ) {
1084 if (k[i].
min() == vln->
noe) {
1096 assert(vrn->
noe == 1);
1098 int vi = vrn->
index();
1101 vars[vi] = vars[--n_var];
1102 vars[vi]->index(vi);
1109 int vidx = vln->
kindex();
1110 if (Card::propagate)
1113 k[vidx].counter(k[vidx].
min());
1119 if (sum_min >= k[vidx].
min())
1120 sum_min -= k[vidx].min();
1121 if (sum_max >= k[vidx].
max())
1122 sum_max -= k[vidx].max();
1125 vals[i]->cap(
UBC,0);
1126 vals[i]->cap(
LBC,0);
1132 if (Card::propagate && (k[i].counter() == 0))
1136 for (
int i = n_val; i--; )
1137 vals[i]->index(n_var + i);
1142 template<
class Card>
template<BC bc>
1147 BitSet visited(
r,
static_cast<unsigned int>(n_node));
1154 bool sp = sn->type();
1159 for (
int i = n_node; i--; )
1161 vals[i-n_var]->inedge(NULL);
1162 start[i] = vals[i-n_var]->first();
1164 vars[i]->inedge(NULL);
1165 start[i] = vars[i]->first();
1170 visited.
set(
static_cast<unsigned int>(v->index()));
1171 while (!ns.
empty()) {
1174 if (vv->
type() == sp) {
1175 e = start[vv->
index()];
1176 while ((e != NULL) && e->
matched(bc))
1179 e = start[vv->
index()];
1180 while ((e != NULL) && !e->
matched(bc))
1182 start[vv->
index()] = e;
1187 if (!visited.
get(
static_cast<unsigned int>(w->
index()))) {
1189 bool m = w->
type() ?
1190 static_cast<ValNode*
>(w)->matched(bc) :
1191 static_cast<VarNode*
>(w)->matched(bc);
1192 if (!m && w->
type() != sp) {
1193 if (vv->
inedge() != NULL) {
1205 visited.
set(
static_cast<unsigned int>(w->
index()));
1216 bool pathfound = !ns.
empty();
1218 while (!ns.
empty()) {
1221 Edge* in =
t->inedge();
1222 if (
t->type() != sp) {
1235 template<
class Card>
1243 if (Card::propagate) {
1244 for (
int i = n_val; i--; ) {
1246 int inc_ubc = v->incid_match(
UBC);
1247 int inc_lbc = v->incid_match(
LBC);
1252 int rm = v->kmax() - k[i].max();
1254 if ((k[i].
max() < v->kmax()) || (k[i].min() > v->kmin())) {
1255 if ((k[i].
max() != k[i].counter()) || (k[i].
max() == 0)) {
1257 v->kmax(k[i].
max());
1258 v->kmin(k[i].
min());
1261 if (inc_ubc <= k[i].
max()) {
1263 v->cap(
UBC, k[i].
max() - inc_ubc);
1264 v->maxlow(k[i].
max() - inc_lbc);
1265 if (v->kmin() == v->kmax())
1266 v->cap(
LBC, k[i].
max() - inc_lbc);
1272 v->maxlow(k[i].
max() - (inc_lbc));
1273 if (v->kmin() == v->kmax())
1274 v->cap(
LBC,k[i].
max() - (inc_lbc));
1275 v->card_conflict(rm);
1279 if (inc_lbc < k[i].
min() && v->noe > 0) {
1280 v->cap(
LBC, k[i].
min() - inc_lbc);
1285 for (
int i = n_var; i--; ) {
1286 Edge* mub = vars[i]->get_match(
UBC);
1299 assert(
x.size() == n_var);
1300 for (
int i = n_var; i--; ) {
1303 if (
static_cast<int>(
x[i].size()) != vrn->
noe) {
1305 if (
x[i].assigned()) {
1308 if ((mub != NULL) && (v != mub->
getVal()->
val)) {
1316 if (v != vln->
val) {
1325 if (vln->
val != v) {
1343 while ((e != NULL) && (e->
getVal()->
val < xiter.
val())) {
1372 if ((mub != NULL) && mub->
deleted()) {
1378 if ((mlb != NULL) && mlb->
deleted()) {
1389 for (
int i = n_val; i--; ) {
1390 if ((k[i].
min() > vals[i]->noe) && (k[i].counter() == 0))
1392 vals[i]->index(n_var + i);
1396 while (!re.
empty()) {
1398 if (!
n->removed()) {
1401 if (!vrn->
matched(
UBC) && !augmenting_path<UBC>(vrn))
1406 if (!augmenting_path<LBC>(vln))
1415 template<
class Card>
template<BC bc>
1419 for (
int i = n_var; i--; )
1420 if (vars[i]->noe == 1) {
1421 ValNode* v = vars[i]->first()->getVal();
1422 vars[i]->first()->free(bc);
1427 for (
int i = n_val; i--; ) {
1429 if (Card::propagate && (k[i].counter() == 0))
1432 if (Card::propagate)
1438 if (v->kcount() == v->kmax()) {
1439 int vidx = v->kindex();
1441 k[i].counter(v->kcount());
1443 if (Card::propagate)
1446 bool delall = v->card_conflict() && (v->noe > v->kmax());
1448 for (
Edge* e = v->last(); e != NULL; e = e->vprev()) {
1450 if (vrn->
noe == 1) {
1453 int vi= vrn->
index();
1456 vars[vi] = vars[--n_var];
1457 vars[vi]->index(vi);
1462 }
else if (delall) {
1473 if (sum_min >= k[vidx].
min())
1474 sum_min -= k[vidx].min();
1475 if (sum_max >= k[vidx].
max())
1476 sum_max -= k[vidx].max();
1478 }
else if (v->kcount() > 0) {
1483 for (
int i = n_var; i--; )
1486 for (
int i = n_val; i--; ) {
1487 if (vals[i]->noe == 0) {
1488 vals[i]->cap(
UBC,0);
1489 vals[i]->cap(
LBC,0);
1492 vals[i]->index(n_var + i);
1495 for (
int i = n_var; i--; ) {
1496 if (vars[i]->noe > 1) {
1497 for (
Edge* e = vars[i]->first(); e != NULL; e = e->
next()) {
1498 if (!e->matched(bc) && !e->used(bc)) {
1509 template<
class Card>
template<BC bc>
1515 for (
int i = n_val; i--; )
1516 for (
Edge* e = vals[i]->first(); e != NULL ; e = e->
vnext())
1517 if (!e->getVar()->matched(bc) && !vals[i]->matched(bc)) {
1518 e->match(bc); card_match++;
1524 if (card_match < sum_min) {
1528 for (
int i = n_val; i--; )
1529 if (!vals[i]->matched(
LBC))
1532 while (!free.
empty()) {
1534 while (!v->matched(
LBC))
1535 if (augmenting_path<LBC>(v))
1547 if (card_match < n_var) {
1551 for (
int i = n_var; i--; )
1552 if (!vars[i]->matched(
UBC))
1555 while (!free.
empty()) {
1557 if (!v->matched(
UBC) && augmenting_path<UBC>(v))
1573 template<
class Card>
template<BC bc>
1578 BitSet visited(
r,
static_cast<unsigned int>(n_node));
1585 for (
int i = n_var; i--; )
1586 if (!vars[i]->matched(
LBC)) {
1588 visited.
set(
static_cast<unsigned int>(vars[i]->index()));
1590 for (
int i = n_val; i--; )
1591 if (!vals[i]->matched(
LBC)) {
1593 visited.
set(
static_cast<unsigned int>(vals[i]->index()));
1599 for (
int i = n_val; i--; )
1600 if (!vals[i]->matched(
UBC)) {
1602 visited.
set(
static_cast<unsigned int>(vals[i]->index()));
1608 while (!ns.
empty()) {
1614 for (
Edge* cur = vln->
first(); cur != NULL; cur = cur->
vnext()) {
1615 VarNode* mate = cur->getVar();
1618 if (cur->matched(
LBC)) {
1621 if (!visited.
get(
static_cast<unsigned int>(mate->
index()))) {
1623 visited.
set(
static_cast<unsigned int>(mate->
index()));
1628 if (!cur->matched(
UBC)) {
1631 if (!visited.
get(
static_cast<unsigned int>(mate->
index()))) {
1633 visited.
set(
static_cast<unsigned int>(mate->
index()));
1648 for (
Edge* cur = vrn->
first(); cur != NULL; cur = cur->
next()) {
1649 ValNode* mate = cur->getVal();
1650 if (!cur->matched(
LBC)) {
1652 if (!visited.
get(
static_cast<unsigned int>(mate->
index()))) {
1654 visited.
set(
static_cast<unsigned int>(mate->
index()));
1666 if (!visited.
get(
static_cast<unsigned int>(mate->
index()))) {
1668 visited.
set(
static_cast<unsigned int>(mate->
index()));
1679 template<
class Card>
template<BC bc>
1686 int v_index = v->index();
1687 dfsnum[v_index] =
count;
1688 inscc.
set(
static_cast<unsigned int>(v_index));
1689 in_unfinished.
set(
static_cast<unsigned int>(v_index));
1693 for (
Edge* e = v->first(); e != NULL; e = e->next(v->type())) {
1697 m = v->type() ? e->matched(
LBC) : !e->matched(
LBC);
1700 m = v->type() ? !e->matched(
UBC) : e->matched(
UBC);
1705 Node* w = e->getMate(v->type());
1706 int w_index = w->
index();
1708 assert(w_index < n_node);
1709 if (!inscc.
get(
static_cast<unsigned int>(w_index))) {
1712 dfs<bc>(w, inscc, in_unfinished, dfsnum,
1714 }
else if (in_unfinished.
get(
static_cast<unsigned int>(w_index))) {
1720 assert(
roots.top()->index() < n_node);
1721 while (dfsnum[
roots.top()->index()] > dfsnum[w_index]) {
1728 if (v ==
roots.top()) {
1729 while (v != unfinished.
top()) {
1733 in_unfinished.
clear(
static_cast<unsigned int>(w->
index()));
1736 assert(v == unfinished.
top());
1737 in_unfinished.
clear(
static_cast<unsigned int>(v_index));
1743 template<
class Card>
template<BC bc>
1747 BitSet inscc(
r,
static_cast<unsigned int>(n_node));
1748 BitSet in_unfinished(
r,
static_cast<unsigned int>(n_node));
1749 int* dfsnum =
r.alloc<
int>(n_node);
1751 for (
int i = n_node; i--; )
1758 for (
int i = n_var; i--; )
1759 dfs<bc>(vars[i], inscc, in_unfinished, dfsnum,
1763 template<
class Card>
1766 return home.ralloc(
t);
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
Class for edges in the variable-value-graph.
void free(BC bc)
Mark the edge as unused.
Edge * vprev(void) const
return the pointer to the previous edge incident on v
Edge * vnext(void) const
return the pointer to the next edge incident on v
void del_edge(void)
Mark the edge as deleted during synchronization.
Edge ** prev_ref(void)
return the reference to the previous edge incident on x
bool deleted(void) const
return whether the edge has been deleted from the graph
void match(BC bc)
Match the edge.
void unmatch(BC bc)
Unmatch the edge and the incident nodes.
Edge ** vprev_ref(void)
return the reference to the previous edge incident on v
Edge * prev(void) const
return the pointer to the previous edge incident on x
void unlink(void)
Unlink the edge from the linked list of edges.
void insert_edge(void)
Insert the edge again.
Edge ** vnext_ref(void)
return the reference to the next edge incident on v
Edge(void)
Default constructor.
ValNode * getVal(void) const
return the pointer to the value node v of this edge
Node * getMate(bool t) const
return pointer to x if t = true otherwise return v
bool matched(BC bc) const
return whether the edge is matched
void reset(BC bc)
Reset the edge (free the edge, and unmatch the edge)
bool used(BC bc) const
Whether the edge is used.
Edge * next(void) const
return the pointer to the next edge incident on x
Edge ** next_ref(void)
return the reference to the next edge incident on x
VarNode * getVar(void) const
return the pointer to the variable node x of this edge
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...
Base class for nodes in the variable-value-graph.
Edge * e
Stores all incident edges on the node.
bool type(void) const
Return the type of the node (false for a variable node)
Edge * last(void) const
Return pointer to the last incident edge.
bool removed(void) const
check whether a node has been removed from the graph
Node(void)
Default constructor.
int noe
stores the number of incident edges on the node
@ NF_M_UBC
Whether matched for UBC.
@ NF_VAL
Whether node is a value node.
@ NF_M_LBC
Whether matched for LBC.
Edge * inedge(void) const
Return pointer to the node's inedge.
Edge * first(void) const
Return pointer to the first incident edge.
unsigned char nf
Flags for node.
Edge * ie
Single incoming edge used for storing a path in the algorithms.
Edge ** adj(void)
Return reference to the incident edges.
int index(void) const
Get index of either variable or value.
int lb
Minimal capacity of the value node.
int _kidx
Index to acces the value via cardinality array k.
void unmatch(BC bc)
unmatch the node
int kmin(void) const
return the minimal node capacity as stored in k
int kbound(BC bc) const
return minimal or maximal capacity
void match(BC bc)
match the node
int incid_match(BC bc) const
returns the number of incident matching edges on a value node
int _klb
Minimal required occurence of the value as stored in k.
int _kcount
Stores the current number of occurences of the value.
int ublow
Smallest maximal capacity of the value node.
bool matched(BC bc) const
returns true if the node is matched in BC, false otherwise
bool source(void) const
tests whether the node is a source
int maxlow(void) const
get max cap for LBC
int card_conflict(void) const
Check whether the value node is conflicting.
int noc
Store numbre of conflicting matching edges.
void card_conflict(int c)
Mark the value node as conflicting in case of variable cardinalities.
void dec(BC bc)
decrease the node-capacity
void reset(void)
node reset to original capacity values
int val
Stores the value of the node.
int kmax(void) const
return the maximal node capacity as stored in k
void red_conflict(void)
Reduce the conflict counter.
int kcount(void) const
returns the current number of occurences of the value
bool sink(void) const
tests whether the node is a sink
int _kub
Maximal required occurence of the value as stored in k.
int ub
Maximal capacity of the value node.
int cap(BC bc) const
return the the node-capacity
int kindex(void) const
returns the index in cardinality array k
ValNode(void)
Default constructor.
void inc(void)
increases the value counter
Edge * ubm
Stores the matching edge on this node in the UBC.
void match(BC bc)
Set node to matched.
VarNode(void)
Default constructor.
bool matched(BC bc) const
tests whether the node is matched or not
void set_match(BC bc, Edge *m)
Set the pointer of the matching edge to m.
Edge * get_match(BC bc) const
Return the matching edge on the node.
void unmatch(BC bc)
Unmatch the node.
Edge * lbm
Stores the matching edge on this node in the LBC.
Variable-value-graph used during propagation.
ExecStatus maximum_matching(void)
Compute a maximum matching M on the graph.
ExecStatus min_require(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k)
Check whether minimum requirements shrink variable domains.
void strongly_connected_components(void)
Compute possible strongly connected components of the graph.
ExecStatus narrow(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k)
Remove edges that do not belong to any maximal matching.
void dfs(Node *, BitSet &, BitSet &, int[], NodeStack &, NodeStack &, int &)
Perform depth-first search on the graph.
void free_alternating_paths(void)
Compute possible free alternating paths in the graph.
bool augmenting_path(Node *)
Test whether the current maximal matching on the graph can be augmented by an alternating path starti...
ExecStatus sync(ViewArray< IntView > &x, ViewArray< Card > &k)
Synchronization of the graph.
VarValGraph(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k, int smin, int smax)
Constructor for the variable-value-graph.
Value iterator for integer views.
int val(void) const
Return current value.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
bool get(unsigned int i) const
Access value at bit i.
void clear(unsigned int i)
Clear bit i.
void set(unsigned int i)
Set bit i.
Stack with fixed number of elements.
void push(const T &x)
Push element x on top of stack.
T pop(void)
Pop topmost element from stack and return it.
bool empty(void) const
Test whether stack is empty.
T & top(void) const
Return element on top of stack.
Base * next(void) const
Return next test.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
BC
Bounds constraint (BC) type.
Gecode toplevel namespace
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Post propagator for SetVar SetOpType SetVar SetRelType r
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
void roots(Home home, const IntVarArgs &x, SetVar y, SetVar z)
Post constraint .
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.
@ ES_OK
Execution is okay.
@ ES_FAILED
Execution has resulted in failure.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
#define GECODE_NEVER
Assert that this command is never executed.
#define GECODE_ASSUME(p)
Assert certain property.