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*) {};
494 void dfs(
Node*, BitSet&, BitSet&,
int[],
495 NodeStack&, NodeStack&,
int&);
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),
637 lb(min), ublow(max), ub(max),
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--; ) {
1165 int rm = v->
kmax() - k[
i].max();
1168 if ((k[
i].
max() != k[
i].counter()) || (k[
i].
max() == 0)) {
1174 if (inc_ubc <= k[
i].
max()) {
1179 v->
cap(
LBC, k[
i].max() - inc_lbc);
1187 v->
cap(
LBC,k[
i].max() - (inc_lbc));
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()) {
1312 if (!vrn->
matched(
UBC) && !augmenting_path<UBC>(home,vrn))
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)
1354 if (Card::propagate)
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))
1457 e = start[v->
index()];
1458 while ((e != NULL) && !e->
matched(bc))
1460 start[v->
index()] = e;
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()) {
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()) {
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()) {
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()));
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));
1700 m = v->
type() ? e->matched(
LBC) : !e->matched(
LBC);
1703 m = v->
type() ? !e->matched(
UBC) : e->matched(
UBC);
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]) {
1731 if (v == roots.
top()) {
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,
1763 roots, unfinished, count);
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.
int kbound(BC bc) const
return minimal or maximal capacity
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.
T & top(void) const
Return element on top of stack.
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
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
bool matched(BC bc) const
return whether the edge is matched
int lb
Minimal capacity of the value node.
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 _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.
int _kcount
Stores the current number of occurences of the value.
int noc
Store numbre of conflicting matching edges.
Edge ** vprev_ref(void)
return the reference to the previous edge incident on v
const unsigned int card
Maximum cardinality of an integer set.
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.
Edge * get_match(BC bc) const
Return the matching edge on the node.
void unmatch(BC bc)
Unmatch the node.
unsigned char nf
Flags for node.
void strongly_connected_components(Space &home)
Compute possible strongly connected components of the graph.
int ublow
Smallest maximal capacity of the value node.
bool type(void) const
Return the type of the node (false for a variable node)
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.
bool matched(BC bc) const
returns true if the node is matched in BC, false otherwise
int p
Number of positive literals for node type.
bool empty(void) const
Test whether stack is empty.
Edge * prev(void) const
return the pointer to the previous edge incident on x
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.
Edge * last(void) const
Return pointer to the last incident edge.
bool source(void) const
tests whether the node is a source
Edge * first(void) const
Return pointer to the first incident edge.
void match(BC bc)
Set node to matched.
int maxlow(void) const
get max cap for LBC
int incid_match(BC bc) const
returns the number of incident matching edges on a value node
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.
Whether node is a value node.
Edge * vprev(void) const
return the pointer to the previous edge incident on v
Base class for nodes in the variable-value-graph.
Edge * next(void) const
return the pointer to the next edge incident on x
Edge * inedge(void) const
Return pointer to the node's inedge.
ExecStatus min_require(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k)
Check whether minimum requirements shrink variable domains.
bool sink(void) const
tests whether the node is a sink
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.
bool used(BC bc) const
Whether the edge is used.
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 removed(void) const
check whether a node has been removed from the graph
void move_lst(int i)
Move view from position size()-1 to position i (truncate array by one)
Class for edges in the variable-value-graph.
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...
Edge * vnext(void) const
return the pointer to the next edge incident on v
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Edge ** adj(void)
Return reference to the incident edges.
int index(void) const
Get index of either variable or value.
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.
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
ValNode * getVal(void) const
return the pointer to the value node v of this edge
bool matched(BC bc) const
tests whether the node is matched or not
bool assigned(View x, int v)
Whether x is assigned to value v.
Node * getMate(bool t) const
return pointer to x if t = true otherwise return v
int kmin(void) const
return the minimal node capacity as stored in k
Stack with fixed number of elements.
T pop(void)
Pop topmost element from stack and return it.
Variable-value-graph used during propagation.
int cap(BC bc) const
return the the node-capacity
int val(void) const
Return current value.
bool deleted(void) const
return whether the edge has been deleted from the graph
int size(void) const
Return size of array (number of elements)
void match(BC bc)
match the node
VarNode * getVar(void) const
return the pointer to the variable node x of this edge
int kcount(void) const
returns the current number of occurences of the value
Gecode toplevel namespace
void dfs(Node *, BitSet &, BitSet &, int[], NodeStack &, NodeStack &, int &)
Perform depth-first search on the graph.
int kmax(void) const
return the maximal node capacity as stored in k
int card_conflict(void) const
Check whether the value node is conflicting.
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.
#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.
int kindex(void) const
returns the index in cardinality array k
int val
Stores the value of the node.