44 namespace Gecode {
namespace Int {
namespace GCC {
95 bool type(
void)
const;
106 int index(
void)
const;
125 static void*
operator new(
size_t s,
Space& home);
128 static void operator delete(
void*,
Space&) {};
130 static void operator delete(
void*) {};
227 bool sink(
void)
const;
231 int kmin(
void)
const;
233 int kmax(
void)
const;
251 int cap(
BC bc)
const;
376 static void*
operator new(
size_t s,
Space& home);
379 static void operator delete(
void*,
Space&) {};
381 static void operator delete(
void*) {};
500 void*
operator new(
size_t t,
Space& home);
502 void operator delete(
void*,
Space&) {}
515 : e(NULL), fst(NULL), lst(NULL), ie(NULL), idx(
i),
516 nf(static_cast<unsigned char>(nf0)), noe(0) {}
564 Node::operator
new(
size_t s,
Space& home) {
565 return home.ralloc(s);
579 Node(NF_NONE,
x), ubm(NULL), lbm(NULL) {}
634 int kidx,
int kshift,
int count) :
635 Node(NF_VAL,kshift), _klb(
min), _kub(
max), _kidx(kidx), _kcount(
count),
823 if (
this == x->
first()) {
829 if (
this == x->
last())
833 Edge* pv = prev_vedge;
834 Edge* nv = next_vedge;
840 if (
this == v->
first()) {
845 if (
this == v->
last())
852 next_edge(NULL), prev_edge(NULL),
853 next_vedge(NULL), prev_vedge(NULL), ef(EF_NONE) {}
872 return (ef & EF_MRKUB) != 0;
874 return (ef & EF_MRKLB) != 0;
977 return (ef & EF_UM) != 0;
979 return (ef & EF_LM) != 0;
995 return (ef & EF_DEL) != 0;
999 Edge::operator
new(
size_t s,
Space& home) {
1000 return home.ralloc(s);
1008 template<
class Card>
1014 n_node(n_var + n_val),
1018 unsigned int noe = 0;
1019 for (
int i=
x.size();
i--; )
1025 for (
int i = n_val;
i--; ) {
1026 int kmi = k[
i].min();
1027 int kma = k[
i].max();
1028 int kc = k[
i].counter();
1038 vals[
i] =
new (home)
1041 vals[
i] =
new (home)
1046 for (
int i = n_var;
i--; ) {
1054 while(vals[j]->val < xi.val())
1056 *xadjacent =
new (home)
Edge(vars[
i],vals[j]);
1058 if (vars[
i]->first() == NULL)
1059 vars[
i]->first(*xadjacent);
1061 vars[
i]->
last(*xadjacent);
1064 if (vals[j]->first() == NULL) {
1065 vals[j]->
first(*xadjacent);
1066 vals[j]->
last(*xadjacent);
1069 vals[j]->
first(*xadjacent);
1074 xadjacent = (*xadjacent)->
next_ref();
1081 template<
class Card>
1086 for (
int i = n_val;
i--; ) {
1101 assert(vrn->
noe == 1);
1103 int vi = vrn->
index();
1106 vars[vi] = vars[--n_var];
1107 vars[vi]->index(vi);
1114 int vidx = vln->
kindex();
1115 if (Card::propagate)
1118 k[vidx].counter(k[vidx].
min());
1124 if (sum_min >= k[vidx].
min())
1125 sum_min -= k[vidx].min();
1126 if (sum_max >= k[vidx].
max())
1127 sum_max -= k[vidx].max();
1130 vals[
i]->cap(
UBC,0);
1131 vals[
i]->cap(
LBC,0);
1137 if (Card::propagate && (k[
i].counter() == 0))
1141 for (
int i = n_val;
i--; )
1142 vals[
i]->index(n_var +
i);
1147 template<
class Card>
1156 if (Card::propagate) {
1157 for (
int i = n_val;
i--; ) {
1159 int inc_ubc =
v->incid_match(
UBC);
1160 int inc_lbc =
v->incid_match(
LBC);
1165 int rm =
v->kmax() - k[
i].max();
1167 if ((k[
i].
max() <
v->kmax()) || (k[
i].
min() >
v->kmin())) {
1168 if ((k[
i].
max() != k[
i].counter()) || (k[
i].
max() == 0)) {
1170 v->kmax(k[
i].
max());
1171 v->kmin(k[
i].
min());
1174 if (inc_ubc <= k[
i].
max()) {
1177 v->maxlow(k[
i].
max() - inc_lbc);
1178 if (
v->kmin() ==
v->kmax())
1179 v->cap(
LBC, k[
i].max() - inc_lbc);
1184 v->cap(
UBC,k[
i].max());
1185 v->maxlow(k[
i].
max() - (inc_lbc));
1186 if (
v->kmin() ==
v->kmax())
1187 v->cap(
LBC,k[
i].max() - (inc_lbc));
1188 v->card_conflict(rm);
1192 if (inc_lbc < k[
i].
min() &&
v->noe > 0) {
1198 for (
int i = n_var;
i--; ) {
1199 Edge* mub = vars[
i]->get_match(
UBC);
1212 assert(
x.size() == n_var);
1213 for (
int i = n_var;
i--; ) {
1216 if (static_cast<int>(
x[
i].
size()) != vrn->
noe) {
1221 if ((mub != NULL) && (
v != mub->
getVal()->
val)) {
1229 if (
v != vln->
val) {
1238 if (vln->
val !=
v) {
1255 while (e != NULL && (e->
getVal()->
val < xiter.
val())) {
1283 if ((mub != NULL) && mub->
deleted()) {
1289 if ((mlb != NULL) && mlb->
deleted()) {
1300 for (
int i = n_val;
i--; ) {
1301 if ((k[
i].
min() > vals[
i]->noe) && (k[
i].counter() == 0))
1303 vals[
i]->index(n_var +
i);
1307 while (!re.
empty()) {
1309 if (!
n->removed()) {
1311 VarNode* vrn = static_cast<VarNode*>(
n);
1312 if (!vrn->
matched(
UBC) && !augmenting_path<UBC>(home,vrn))
1315 ValNode* vln = static_cast<ValNode*>(
n);
1317 if (!augmenting_path<LBC>(home,vln))
1326 template<
class Card>
template<BC bc>
1330 for (
int i = n_var;
i--; )
1331 if (vars[
i]->noe == 1) {
1332 ValNode*
v = vars[
i]->first()->getVal();
1333 vars[
i]->first()->free(bc);
1338 for (
int i = n_val;
i--; ) {
1340 if (Card::propagate && (k[
i].counter() == 0))
1343 if (Card::propagate)
1349 if (
v->kcount() ==
v->kmax()) {
1350 int vidx =
v->kindex();
1352 k[
i].counter(
v->kcount());
1354 if (Card::propagate)
1357 bool delall =
v->card_conflict() && (
v->noe >
v->kmax());
1359 for (
Edge* e =
v->last(); e != NULL; e = e->vprev()) {
1361 if (vrn->
noe == 1) {
1364 int vi= vrn->
index();
1367 vars[vi] = vars[--n_var];
1368 vars[vi]->
index(vi);
1373 }
else if (delall) {
1384 if (sum_min >= k[vidx].
min())
1385 sum_min -= k[vidx].min();
1386 if (sum_max >= k[vidx].
max())
1387 sum_max -= k[vidx].max();
1389 }
else if (
v->kcount() > 0) {
1394 for (
int i = n_var;
i--; )
1397 for (
int i = n_val;
i--; ) {
1398 if (vals[
i]->noe == 0) {
1399 vals[
i]->cap(
UBC,0);
1400 vals[
i]->cap(
LBC,0);
1403 vals[
i]->index(n_var +
i);
1406 for (
int i = n_var;
i--; ) {
1407 if (vars[
i]->noe > 1) {
1408 for (
Edge* e = vars[
i]->first(); e != NULL; e = e->
next()) {
1409 if (!e->matched(bc) && !e->used(bc)) {
1420 template<
class Card>
template<BC bc>
1425 BitSet visited(
r,static_cast<unsigned int>(n_node));
1432 bool sp = sn->type();
1437 for (
int i = n_node;
i--; )
1439 vals[
i-n_var]->inedge(NULL);
1440 start[
i] = vals[
i-n_var]->first();
1442 vars[
i]->inedge(NULL);
1443 start[
i] = vars[
i]->first();
1448 visited.
set(static_cast<unsigned int>(
v->index()));
1449 while (!ns.
empty()) {
1452 if (
v->type() == sp) {
1453 e = start[
v->index()];
1454 while ((e != NULL) && e->
matched(bc))
1455 e = e->
next(
v->type());
1457 e = start[
v->index()];
1458 while ((e != NULL) && !e->
matched(bc))
1459 e = e->
next(
v->type());
1460 start[
v->index()] = e;
1463 start[
v->index()] = e->
next(
v->type());
1465 if (!visited.
get(static_cast<unsigned int>(w->
index()))) {
1467 bool m = w->
type() ?
1468 static_cast<ValNode*>(w)->matched(bc) :
1469 static_cast<VarNode*>(w)->matched(bc);
1470 if (!m && w->
type() != sp) {
1471 if (
v->inedge() != NULL) {
1483 visited.
set(static_cast<unsigned int>(w->
index()));
1494 bool pathfound = !ns.
empty();
1496 while (!ns.
empty()) {
1499 Edge* in =
t->inedge();
1500 if (
t->type() != sp) {
1512 template<
class Card>
template<BC bc>
1518 for (
int i = n_val;
i--; )
1519 for (
Edge* e = vals[
i]->first(); e != NULL ; e = e->
vnext())
1520 if (!e->getVar()->matched(bc) && !vals[
i]->matched(bc)) {
1521 e->match(bc); card_match++;
1527 if (card_match < sum_min) {
1531 for (
int i = n_val;
i--; )
1532 if (!vals[
i]->matched(
LBC))
1535 while (!free.
empty()) {
1537 while (!
v->matched(
LBC))
1538 if (augmenting_path<LBC>(home,
v))
1550 if (card_match < n_var) {
1554 for (
int i = n_var;
i--; )
1555 if (!vars[
i]->matched(
UBC))
1558 while (!free.
empty()) {
1560 if (!
v->matched(
UBC) && augmenting_path<UBC>(home,
v))
1576 template<
class Card>
template<BC bc>
1581 BitSet visited(
r,static_cast<unsigned int>(n_node));
1588 for (
int i = n_var;
i--; )
1589 if (!vars[
i]->matched(
LBC)) {
1591 visited.
set(static_cast<unsigned int>(vars[
i]->index()));
1593 for (
int i = n_val;
i--; )
1594 if (!vals[
i]->matched(
LBC)) {
1596 visited.
set(static_cast<unsigned int>(vals[
i]->index()));
1602 for (
int i = n_val;
i--; )
1603 if (!vals[
i]->matched(
UBC)) {
1605 visited.
set(static_cast<unsigned int>(vals[
i]->index()));
1611 while (!ns.
empty()) {
1615 ValNode* vln = static_cast<ValNode*>(node);
1617 for (
Edge* cur = vln->
first(); cur != NULL; cur = cur->
vnext()) {
1618 VarNode* mate = cur->getVar();
1621 if (cur->matched(
LBC)) {
1624 if (!visited.
get(static_cast<unsigned int>(mate->
index()))) {
1626 visited.
set(static_cast<unsigned int>(mate->
index()));
1631 if (!cur->matched(
UBC)) {
1634 if (!visited.
get(static_cast<unsigned int>(mate->
index()))) {
1636 visited.
set(static_cast<unsigned int>(mate->
index()));
1646 VarNode* vrn = static_cast<VarNode*>(node);
1651 for (
Edge* cur = vrn->
first(); cur != NULL; cur = cur->
next()) {
1652 ValNode* mate = cur->getVal();
1653 if (!cur->matched(
LBC)) {
1655 if (!visited.
get(static_cast<unsigned int>(mate->
index()))) {
1657 visited.
set(static_cast<unsigned int>(mate->
index()));
1669 if (!visited.
get(static_cast<unsigned int>(mate->
index()))) {
1671 visited.
set(static_cast<unsigned int>(mate->
index()));
1682 template<
class Card>
template<BC bc>
1689 int v_index =
v->index();
1690 dfsnum[v_index] =
count;
1691 inscc.
set(static_cast<unsigned int>(v_index));
1692 in_unfinished.
set(static_cast<unsigned int>(v_index));
1696 for (
Edge* e =
v->first(); e != NULL; e = e->next(
v->type())) {
1700 m =
v->type() ? e->matched(
LBC) : !e->matched(
LBC);
1703 m =
v->type() ? !e->matched(
UBC) : e->matched(
UBC);
1708 Node* w = e->getMate(
v->type());
1709 int w_index = w->
index();
1711 assert(w_index < n_node);
1712 if (!inscc.
get(static_cast<unsigned int>(w_index))) {
1715 dfs<bc>(w, inscc, in_unfinished, dfsnum,
1717 }
else if (in_unfinished.
get(static_cast<unsigned int>(w_index))) {
1723 assert(
roots.top()->index() < n_node);
1724 while (dfsnum[
roots.top()->index()] > dfsnum[w_index]) {
1732 while (
v != unfinished.
top()) {
1736 in_unfinished.
clear(static_cast<unsigned int>(w->
index()));
1739 assert(
v == unfinished.
top());
1740 in_unfinished.
clear(static_cast<unsigned int>(v_index));
1746 template<
class Card>
template<BC bc>
1750 BitSet inscc(
r,static_cast<unsigned int>(n_node));
1751 BitSet in_unfinished(
r,static_cast<unsigned int>(n_node));
1752 int* dfsnum =
r.alloc<
int>(n_node);
1754 for (
int i = n_node;
i--; )
1761 for (
int i = n_var;
i--; )
1762 dfs<bc>(vars[
i], inscc, in_unfinished, dfsnum,
1766 template<
class Card>
1769 return home.ralloc(
t);
BC
Bounds constraint (BC) type.
void push(const T &x)
Push element x on top of stack.
int noe
stores the number of incident edges on the node
bool get(unsigned int i) const
Access value at bit i.
ValNode(void)
Default constructor.
void unlink(void)
Unlink the edge from the linked list of edges.
ExecStatus sync(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k)
Synchronization of the graph.
Edge ** vnext_ref(void)
return the reference to the next edge incident on v
Node(void)
Default constructor.
Edge * vnext(void) const
return the pointer to the next edge incident on v
bool type(void) const
Return the type of the node (false for a variable node)
bool removed(void) const
check whether a node has been removed from the graph
bool sink(void) const
tests whether the node is a sink
int index(void) const
Get index of either variable or value.
void reset(BC bc)
Reset the edge (free the edge, and unmatch the edge)
int ub
Maximal capacity of the value node.
VarValGraph(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k, int smin, int smax)
Constructor for the variable-value-graph.
VarNode(void)
Default constructor.
void clear(unsigned int i)
Clear bit i.
Edge ** prev_ref(void)
return the reference to the previous edge incident on x
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
int lb
Minimal capacity of the value node.
bool empty(void) const
Test whether stack is empty.
int _klb
Minimal required occurence of the value as stored in k.
void roots(Home home, const IntVarArgs &x, SetVar y, SetVar z)
Post constraint .
ExecStatus maximum_matching(Space &home)
Compute a maximum matching M on the graph.
bool used(BC bc) const
Whether the edge is used.
int _kcount
Stores the current number of occurences of the value.
Edge * first(void) const
Return pointer to the first incident edge.
int noc
Store numbre of conflicting matching edges.
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...
int kcount(void) const
returns the current number of occurences of the value
Edge ** vprev_ref(void)
return the reference to the previous edge incident on v
const unsigned int card
Maximum cardinality of an integer set.
int kbound(BC bc) const
return minimal or maximal capacity
Edge * ie
Single incoming edge used for storing a path in the algorithms.
Edge * lbm
Stores the matching edge on this node in the LBC.
int val(void) const
Return current value.
void unmatch(BC bc)
Unmatch the node.
unsigned char nf
Flags for node.
ValNode * getVal(void) const
return the pointer to the value node v of this edge
void strongly_connected_components(Space &home)
Compute possible strongly connected components of the graph.
int ublow
Smallest maximal capacity of the value node.
T & top(void) const
Return element on top of stack.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Gecode::FloatVal c(-8, 8)
void inc(void)
increases the value counter
void free_alternating_paths(Space &home)
Compute possible free alternating paths in the graph.
int p
Number of positive literals for node type.
int incid_match(BC bc) const
returns the number of incident matching edges on a value node
int kmax(void) const
return the maximal node capacity as stored in k
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
int _kub
Maximal required occurence of the value as stored in k.
void match(BC bc)
Match the edge.
Execution has resulted in failure.
Node * getMate(bool t) const
return pointer to x if t = true otherwise return v
void match(BC bc)
Set node to matched.
int _kidx
Index to acces the value via cardinality array k.
unsigned int size(I &i)
Size of all ranges of range iterator i.
void unmatch(BC bc)
Unmatch the edge and the incident nodes.
int kindex(void) const
returns the index in cardinality array k
Whether node is a value node.
Base class for nodes in the variable-value-graph.
int card_conflict(void) const
Check whether the value node is conflicting.
VarNode * getVar(void) const
return the pointer to the variable node x of this edge
ExecStatus min_require(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k)
Check whether minimum requirements shrink variable domains.
bool deleted(void) const
return whether the edge has been deleted from the graph
void set(unsigned int i)
Set bit i.
void insert_edge(void)
Insert the edge again.
void free(BC bc)
Mark the edge as unused.
void unmatch(BC bc)
unmatch the node
Edge(void)
Default constructor.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
bool matched(BC bc) const
returns true if the node is matched in BC, false otherwise
Class for edges in the variable-value-graph.
int kmin(void) const
return the minimal node capacity as stored in k
Edge ** next_ref(void)
return the reference to the next edge incident on x
bool augmenting_path(Space &home, Node *)
Test whether the current maximal matching on the graph can be augmented by an alternating path starti...
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Edge ** adj(void)
Return reference to the incident edges.
Edge * inedge(void) const
Return pointer to the node's inedge.
ExecStatus narrow(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k)
Remove edges that do not belong to any maximal matching.
void reset(void)
node reset to original capacity values
void red_conflict(void)
Reduce the conflict counter.
int maxlow(void) const
get max cap for LBC
Node * x
Pointer to corresponding Boolean expression node.
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntConLevel)
Post propagator for .
void del_edge(void)
Mark the edge as deleted during synchronization.
void dec(BC bc)
decrease the node-capacity
bool assigned(View x, int v)
Whether x is assigned to value v.
Stack with fixed number of elements.
T pop(void)
Pop topmost element from stack and return it.
bool source(void) const
tests whether the node is a source
Variable-value-graph used during propagation.
Edge * prev(void) const
return the pointer to the previous edge incident on x
void match(BC bc)
match the node
Gecode toplevel namespace
void dfs(Node *, BitSet &, BitSet &, int[], NodeStack &, NodeStack &, int &)
Perform depth-first search on the graph.
int cap(BC bc) const
return the the node-capacity
Edge * next(void) const
return the pointer to the next edge incident on x
Edge * e
Stores all incident edges on the node.
void card_conflict(int c)
Mark the value node as conflicting in case of variable cardinalities.
Edge * ubm
Stores the matching edge on this node in the UBC.
bool matched(BC bc) const
return whether the edge is matched
#define GECODE_NEVER
Assert that this command is never executed.
void set_match(BC bc, Edge *m)
Set the pointer of the matching edge to m.
Edge * vprev(void) const
return the pointer to the previous edge incident on v
Edge * last(void) const
Return pointer to the last incident edge.
bool matched(BC bc) const
tests whether the node is matched or not
int val
Stores the value of the node.
Edge * get_match(BC bc) const
Return the matching edge on the node.