Go to the documentation of this file.
40 namespace Gecode {
namespace Int {
namespace GCC {
91 bool type(
void)
const;
102 int index(
void)
const;
121 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;
372 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) {}
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)
1036 vals[
i] =
new (home)
1041 for (
int i = n_var;
i--; ) {
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--; ) {
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()) {
1264 v->maxlow(k[
i].
max() - inc_lbc);
1265 if (
v->kmin() ==
v->kmax())
1266 v->cap(
LBC, k[
i].max() - inc_lbc);
1271 v->cap(
UBC,k[
i].max());
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) {
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) {
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()) {
1400 VarNode* vrn = static_cast<VarNode*>(
n);
1401 if (!vrn->
matched(
UBC) && !augmenting_path<UBC>(vrn))
1404 ValNode* vln = static_cast<ValNode*>(
n);
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()) {
1612 ValNode* vln = static_cast<ValNode*>(node);
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()));
1643 VarNode* vrn = static_cast<VarNode*>(node);
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]) {
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);
void unlink(void)
Unlink the edge from the linked list of edges.
Edge ** vprev_ref(void)
return the reference to the previous edge incident on v
Post propagator for SetVar x
void set(unsigned int i)
Set bit i.
ExecStatus maximum_matching(void)
Compute a maximum matching M on the graph.
VarValGraph(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k, int smin, int smax)
Constructor for the variable-value-graph.
void set_match(BC bc, Edge *m)
Set the pointer of the matching edge to m.
void strongly_connected_components(void)
Compute possible strongly connected components of the graph.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
void inc(void)
increases the value counter
bool source(void) const
tests whether the node is a source
int incid_match(BC bc) const
returns the number of incident matching edges on a value node
void unmatch(BC bc)
Unmatch the edge and the incident nodes.
unsigned int size(I &i)
Size of all ranges of range iterator i.
int ub
Maximal capacity of the value node.
bool assigned(View x, int v)
Whether x is assigned to value v.
bool deleted(void) const
return whether the edge has been deleted from the graph
Edge ** vnext_ref(void)
return the reference to the next edge incident on v
Edge ** adj(void)
Return reference to the incident edges.
Edge * vprev(void) const
return the pointer to the previous edge incident on v
Stack with fixed number of elements.
int kmax(void) const
return the maximal node capacity as stored in k
bool used(BC bc) const
Whether the edge is used.
bool sink(void) const
tests whether the node is a sink
int kindex(void) const
returns the index in cardinality array k
void unmatch(BC bc)
unmatch the node
Edge * last(void) const
Return pointer to the last incident edge.
ValNode * getVal(void) const
return the pointer to the value node v of this edge
int val(void) const
Return current value.
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...
Edge * inedge(void) const
Return pointer to the node's inedge.
bool matched(BC bc) const
returns true if the node is matched in BC, false otherwise
Edge(void)
Default constructor.
ExecStatus sync(ViewArray< IntView > &x, ViewArray< Card > &k)
Synchronization of the graph.
void match(BC bc)
match the node
Edge * e
Stores all incident edges on the node.
Gecode toplevel namespace
Edge ** next_ref(void)
return the reference to the next edge incident on x
VarNode(void)
Default constructor.
void card_conflict(int c)
Mark the value node as conflicting in case of variable cardinalities.
void reset(void)
node reset to original capacity values
const unsigned int card
Maximum cardinality of an integer set.
Node * x
Pointer to corresponding Boolean expression node.
void clear(unsigned int i)
Clear bit i.
bool removed(void) const
check whether a node has been removed from the graph
Edge * get_match(BC bc) const
Return the matching edge on the node.
bool augmenting_path(Node *)
Test whether the current maximal matching on the graph can be augmented by an alternating path starti...
Variable-value-graph used during propagation.
BC
Bounds constraint (BC) type.
int _kub
Maximal required occurence of the value as stored in k.
int val
Stores the value of the node.
Edge ** prev_ref(void)
return the reference to the previous edge incident on x
Post propagator for SetVar SetOpType SetVar SetRelType r
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
int index(void) const
Get index of either variable or value.
bool empty(void) const
Test whether stack is empty.
int _kidx
Index to acces the value via cardinality array k.
Node * getMate(bool t) const
return pointer to x if t = true otherwise return v
int cap(BC bc) const
return the the node-capacity
void red_conflict(void)
Reduce the conflict counter.
int kmin(void) const
return the minimal node capacity as stored in k
T pop(void)
Pop topmost element from stack and return it.
T & top(void) const
Return element on top of stack.
ExecStatus min_require(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k)
Check whether minimum requirements shrink variable domains.
int noc
Store numbre of conflicting matching edges.
ExecStatus narrow(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k)
Remove edges that do not belong to any maximal matching.
Edge * first(void) const
Return pointer to the first incident edge.
#define GECODE_NEVER
Assert that this command is never executed.
bool type(void) const
Return the type of the node (false for a variable node)
int kcount(void) const
returns the current number of occurences of the value
VarNode * getVar(void) const
return the pointer to the variable node x of this edge
int noe
stores the number of incident edges on the node
void dec(BC bc)
decrease the node-capacity
Base class for nodes in the variable-value-graph.
Node(void)
Default constructor.
int lb
Minimal capacity of the value node.
bool get(unsigned int i) const
Access value at bit i.
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
void match(BC bc)
Set node to matched.
Class for edges in the variable-value-graph.
int _klb
Minimal required occurence of the value as stored in k.
void reset(BC bc)
Reset the edge (free the edge, and unmatch the edge)
Edge * ie
Single incoming edge used for storing a path in the algorithms.
int _kcount
Stores the current number of occurences of the value.
void free_alternating_paths(void)
Compute possible free alternating paths in the graph.
Edge * next(void) const
return the pointer to the next edge incident on x
void match(BC bc)
Match the edge.
void push(const T &x)
Push element x on top of stack.
Whether node is a value node.
Edge * prev(void) const
return the pointer to the previous edge incident on x
bool matched(BC bc) const
tests whether the node is matched or not
int ublow
Smallest maximal capacity of the value node.
void unmatch(BC bc)
Unmatch the node.
int maxlow(void) const
get max cap for LBC
void dfs(Node *, BitSet &, BitSet &, int[], NodeStack &, NodeStack &, int &)
Perform depth-first search on the graph.
void del_edge(void)
Mark the edge as deleted during synchronization.
Edge * ubm
Stores the matching edge on this node in the UBC.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
unsigned char nf
Flags for node.
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
Gecode::FloatVal c(-8, 8)
void roots(Home home, const IntVarArgs &x, SetVar y, SetVar z)
Post constraint .
int n
Number of negative literals for node type.
Execution has resulted in failure.
void insert_edge(void)
Insert the edge again.
void free(BC bc)
Mark the edge as unused.
Gecode::IntArgs i({1, 2, 3, 4})
Edge * vnext(void) const
return the pointer to the next edge incident on v
int card_conflict(void) const
Check whether the value node is conflicting.
int p
Number of positive literals for node type.
bool matched(BC bc) const
return whether the edge is matched
ValNode(void)
Default constructor.
int kbound(BC bc) const
return minimal or maximal capacity
Edge * lbm
Stores the matching edge on this node in the LBC.
#define GECODE_ASSUME(p)
Assert certain property.