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*) {};
152 Edge* get_match(
BC bc)
const;
155 bool matched(
BC bc)
const;
160 void set_match(
BC bc,
Edge* m);
208 int maxlow(
void)
const;
211 void card_conflict(
int c);
213 int card_conflict(
void)
const;
215 void red_conflict(
void);
219 int kcount(
void)
const;
221 int incid_match(
BC bc)
const;
223 int kindex(
void)
const;
225 bool matched(
BC bc)
const;
227 bool sink(
void)
const;
229 bool source(
void)
const;
231 int kmin(
void)
const;
233 int kmax(
void)
const;
235 int kbound(
BC bc)
const;
251 int cap(
BC bc)
const;
253 void cap(
BC bc,
int c);
313 bool used(
BC bc)
const;
316 bool matched(
BC bc)
const;
318 bool deleted(
void)
const;
324 Edge* next(
bool t)
const;
326 Edge* next(
void)
const;
328 Edge* prev(
void)
const;
330 Edge* vnext(
void)
const;
332 Edge* vprev(
void)
const;
341 Node* getMate(
bool t)
const;
357 void unmatch(
BC bc,
bool t);
363 void insert_edge(
void);
365 Edge** next_ref(
void);
367 Edge** prev_ref(
void);
369 Edge** vnext_ref(
void);
371 Edge** vprev_ref(
void);
376 static void*
operator new(
size_t s,
Space& home);
379 static void operator delete(
void*,
Space&) {};
381 static void operator delete(
void*) {};
473 void free_alternating_paths(
void);
476 void strongly_connected_components(
void);
483 bool augmenting_path(
Node*);
493 void dfs(
Node*, BitSet&, BitSet&,
int[],
494 NodeStack&, NodeStack&,
int&);
499 void*
operator new(
size_t t,
Space& home);
501 void operator delete(
void*,
Space&) {}
515 nf(static_cast<unsigned char>(nf0)),
noe(0) {}
563 Node::operator
new(
size_t s,
Space& home) {
564 return home.ralloc(s);
633 int kidx,
int kshift,
int count) :
634 Node(
NF_VAL,kshift), _klb(min), _kub(max), _kidx(kidx), _kcount(count),
636 lb(min), ublow(max), ub(max),
822 if (
this ==
x->first()) {
823 Edge** ref =
x->adj();
828 if (
this ==
x->last())
832 Edge* pv = prev_vedge;
833 Edge* nv = next_vedge;
839 if (
this ==
v->first()) {
840 Edge** ref =
v->adj();
844 if (
this ==
v->last())
851 next_edge(NULL), prev_edge(NULL),
852 next_vedge(NULL), prev_vedge(NULL), ef(EF_NONE) {}
871 return (ef & EF_MRKUB) != 0;
873 return (ef & EF_MRKLB) != 0;
976 return (ef & EF_UM) != 0;
978 return (ef & EF_LM) != 0;
994 return (ef & EF_DEL) != 0;
998 Edge::operator
new(
size_t s,
Space& home) {
999 return home.ralloc(s);
1007 template<
class Card>
1013 n_node(n_var + n_val),
1017 unsigned int noe = 0;
1018 for (
int i=x.
size();
i--; )
1024 for (
int i = n_val;
i--; ) {
1025 int kmi = k[
i].min();
1026 int kma = k[
i].max();
1027 int kc = k[
i].counter();
1037 vals[
i] =
new (home)
1040 vals[
i] =
new (home)
1045 for (
int i = n_var;
i--; ) {
1053 while(vals[j]->val < xi.val())
1055 *xadjacent =
new (home)
Edge(vars[i],vals[j]);
1057 if (vars[i]->first() == NULL)
1058 vars[i]->first(*xadjacent);
1060 vars[
i]->
last(*xadjacent);
1063 if (vals[j]->first() == NULL) {
1064 vals[j]->
first(*xadjacent);
1065 vals[j]->
last(*xadjacent);
1068 vals[j]->
first(*xadjacent);
1073 xadjacent = (*xadjacent)->
next_ref();
1080 template<
class Card>
1085 for (
int i = n_val;
i--; ) {
1100 assert(vrn->
noe == 1);
1102 int vi = vrn->
index();
1105 vars[vi] = vars[--n_var];
1106 vars[vi]->
index(vi);
1113 int vidx = vln->
kindex();
1114 if (Card::propagate)
1117 k[vidx].counter(k[vidx].
min());
1123 if (sum_min >= k[vidx].
min())
1124 sum_min -= k[vidx].min();
1125 if (sum_max >= k[vidx].
max())
1126 sum_max -= k[vidx].max();
1136 if (Card::propagate && (k[
i].counter() == 0))
1140 for (
int i = n_val;
i--; )
1141 vals[
i]->index(n_var +
i);
1146 template<
class Card>
template<BC bc>
1151 BitSet visited(r,static_cast<unsigned int>(n_node));
1158 bool sp = sn->type();
1163 for (
int i = n_node;
i--; )
1166 start[
i] = vals[
i-n_var]->
first();
1174 visited.
set(static_cast<unsigned int>(v->
index()));
1175 while (!ns.
empty()) {
1178 if (vv->
type() == sp) {
1179 e = start[vv->
index()];
1180 while ((e != NULL) && e->
matched(bc))
1183 e = start[vv->
index()];
1184 while ((e != NULL) && !e->
matched(bc))
1186 start[vv->
index()] = e;
1191 if (!visited.
get(static_cast<unsigned int>(w->
index()))) {
1193 bool m = w->
type() ?
1194 static_cast<ValNode*
>(w)->matched(bc) :
1195 static_cast<VarNode*
>(w)->matched(bc);
1196 if (!m && w->
type() != sp) {
1197 if (vv->
inedge() != NULL) {
1209 visited.
set(static_cast<unsigned int>(w->
index()));
1220 bool pathfound = !ns.
empty();
1222 while (!ns.
empty()) {
1226 if (t->
type() != sp) {
1239 template<
class Card>
1247 if (Card::propagate) {
1248 for (
int i = n_val;
i--; ) {
1256 int rm = v->
kmax() - k[
i].max();
1259 if ((k[
i].
max() != k[
i].counter()) || (k[
i].
max() == 0)) {
1265 if (inc_ubc <= k[
i].
max()) {
1270 v->
cap(
LBC, k[
i].max() - inc_lbc);
1278 v->
cap(
LBC,k[
i].max() - (inc_lbc));
1283 if (inc_lbc < k[
i].
min() && v->
noe > 0) {
1289 for (
int i = n_var;
i--; ) {
1303 assert(x.
size() == n_var);
1304 for (
int i = n_var;
i--; ) {
1307 if (static_cast<int>(x[
i].
size()) != vrn->
noe) {
1312 if ((mub != NULL) && (v != mub->
getVal()->
val)) {
1320 if (v != vln->
val) {
1329 if (vln->
val != v) {
1346 while (e != NULL && (e->
getVal()->
val < xiter.
val())) {
1374 if ((mub != NULL) && mub->
deleted()) {
1380 if ((mlb != NULL) && mlb->
deleted()) {
1391 for (
int i = n_val;
i--; ) {
1392 if ((k[
i].
min() > vals[
i]->noe) && (k[
i].counter() == 0))
1398 while (!re.
empty()) {
1403 if (!vrn->
matched(
UBC) && !augmenting_path<UBC>(vrn))
1408 if (!augmenting_path<LBC>(vln))
1417 template<
class Card>
template<BC bc>
1421 for (
int i = n_var;
i--; )
1422 if (vars[
i]->noe == 1) {
1429 for (
int i = n_val;
i--; ) {
1431 if (Card::propagate && (k[
i].counter() == 0))
1434 if (Card::propagate)
1445 if (Card::propagate)
1452 if (vrn->
noe == 1) {
1455 int vi= vrn->
index();
1458 vars[vi] = vars[--n_var];
1459 vars[vi]->
index(vi);
1464 }
else if (delall) {
1475 if (sum_min >= k[vidx].
min())
1476 sum_min -= k[vidx].min();
1477 if (sum_max >= k[vidx].
max())
1478 sum_max -= k[vidx].max();
1480 }
else if (v->
kcount() > 0) {
1485 for (
int i = n_var;
i--; )
1488 for (
int i = n_val;
i--; ) {
1489 if (vals[
i]->noe == 0) {
1497 for (
int i = n_var;
i--; ) {
1498 if (vars[
i]->noe > 1) {
1499 for (
Edge* e = vars[
i]->first(); e != NULL; e = e->next()) {
1500 if (!e->matched(bc) && !e->used(bc)) {
1511 template<
class Card>
template<BC bc>
1517 for (
int i = n_val;
i--; )
1518 for (
Edge* e = vals[
i]->first(); e != NULL ; e = e->vnext())
1519 if (!e->getVar()->matched(bc) && !vals[
i]->
matched(bc)) {
1520 e->match(bc); card_match++;
1526 if (card_match < sum_min) {
1530 for (
int i = n_val;
i--; )
1531 if (!vals[
i]->matched(
LBC))
1534 while (!free.
empty()) {
1537 if (augmenting_path<LBC>(v))
1549 if (card_match < n_var) {
1553 for (
int i = n_var;
i--; )
1554 if (!vars[
i]->matched(
UBC))
1557 while (!free.
empty()) {
1575 template<
class Card>
template<BC bc>
1580 BitSet visited(r,static_cast<unsigned int>(n_node));
1587 for (
int i = n_var;
i--; )
1588 if (!vars[
i]->matched(
LBC)) {
1590 visited.
set(static_cast<unsigned int>(vars[i]->index()));
1592 for (
int i = n_val;
i--; )
1593 if (!vals[
i]->matched(
LBC)) {
1595 visited.
set(static_cast<unsigned int>(vals[i]->index()));
1601 for (
int i = n_val;
i--; )
1602 if (!vals[
i]->matched(
UBC)) {
1604 visited.
set(static_cast<unsigned int>(vals[i]->index()));
1610 while (!ns.
empty()) {
1616 for (
Edge* cur = vln->
first(); cur != NULL; cur = cur->
vnext()) {
1617 VarNode* mate = cur->getVar();
1620 if (cur->matched(
LBC)) {
1623 if (!visited.
get(static_cast<unsigned int>(mate->
index()))) {
1625 visited.
set(static_cast<unsigned int>(mate->
index()));
1630 if (!cur->matched(
UBC)) {
1633 if (!visited.
get(static_cast<unsigned int>(mate->
index()))) {
1635 visited.
set(static_cast<unsigned int>(mate->
index()));
1650 for (
Edge* cur = vrn->
first(); cur != NULL; cur = cur->
next()) {
1651 ValNode* mate = cur->getVal();
1652 if (!cur->matched(
LBC)) {
1654 if (!visited.
get(static_cast<unsigned int>(mate->
index()))) {
1656 visited.
set(static_cast<unsigned int>(mate->
index()));
1668 if (!visited.
get(static_cast<unsigned int>(mate->
index()))) {
1670 visited.
set(static_cast<unsigned int>(mate->
index()));
1681 template<
class Card>
template<BC bc>
1688 int v_index = v->
index();
1689 dfsnum[v_index] =
count;
1690 inscc.
set(static_cast<unsigned int>(v_index));
1691 in_unfinished.
set(static_cast<unsigned int>(v_index));
1699 m = v->
type() ? e->matched(
LBC) : !e->matched(
LBC);
1702 m = v->
type() ? !e->matched(
UBC) : e->matched(
UBC);
1708 int w_index = w->
index();
1710 assert(w_index < n_node);
1711 if (!inscc.
get(static_cast<unsigned int>(w_index))) {
1714 dfs<bc>(w, inscc, in_unfinished, dfsnum,
1716 }
else if (in_unfinished.
get(static_cast<unsigned int>(w_index))) {
1722 assert(roots.
top()->index() < n_node);
1723 while (dfsnum[roots.
top()->index()] > dfsnum[w_index]) {
1730 if (v == roots.
top()) {
1731 while (v != unfinished.
top()) {
1735 in_unfinished.
clear(static_cast<unsigned int>(w->
index()));
1738 assert(v == unfinished.
top());
1739 in_unfinished.
clear(static_cast<unsigned int>(v_index));
1745 template<
class Card>
template<BC bc>
1749 BitSet inscc(r,static_cast<unsigned int>(n_node));
1750 BitSet in_unfinished(r,static_cast<unsigned int>(n_node));
1751 int* dfsnum = r.
alloc<
int>(n_node);
1753 for (
int i = n_node;
i--; )
1760 for (
int i = n_var;
i--; )
1761 dfs<bc>(vars[
i], inscc, in_unfinished, dfsnum,
1762 roots, unfinished, count);
1765 template<
class Card>
1768 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.
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.
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
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.
void strongly_connected_components(void)
Compute possible strongly connected components of the graph.
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 .
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 .
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
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
ExecStatus sync(ViewArray< IntView > &x, ViewArray< Card > &k)
Synchronization of 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
bool augmenting_path(Node *)
Test whether the current maximal matching on the graph can be augmented by an alternating path starti...
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
T * dfs(T *s, const Search::Options &o)
Invoke depth-first search engine for subclass T of space s with options o.
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.
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
Post propagator for SetVar SetOpType SetVar SetRelType r
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.
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
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
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.
Post propagator for SetVar x
bool source(void) const
tests whether the node is a source
Variable-value-graph used during propagation.
void free_alternating_paths(void)
Compute possible free alternating paths in the graph.
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.
int size(void) const
Return size of array (number of elements)
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.
ExecStatus maximum_matching(void)
Compute a maximum matching M on the graph.