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*) {};
148 Edge* get_match(
BC bc)
const;
151 bool matched(
BC bc)
const;
156 void set_match(
BC bc,
Edge* m);
204 int maxlow(
void)
const;
207 void card_conflict(
int c);
209 int card_conflict(
void)
const;
211 void red_conflict(
void);
215 int kcount(
void)
const;
217 int incid_match(
BC bc)
const;
219 int kindex(
void)
const;
221 bool matched(
BC bc)
const;
223 bool sink(
void)
const;
225 bool source(
void)
const;
227 int kmin(
void)
const;
229 int kmax(
void)
const;
231 int kbound(
BC bc)
const;
247 int cap(
BC bc)
const;
249 void cap(
BC bc,
int c);
309 bool used(
BC bc)
const;
312 bool matched(
BC bc)
const;
314 bool deleted(
void)
const;
320 Edge* next(
bool t)
const;
322 Edge* next(
void)
const;
324 Edge* prev(
void)
const;
326 Edge* vnext(
void)
const;
328 Edge* vprev(
void)
const;
337 Node* getMate(
bool t)
const;
353 void unmatch(
BC bc,
bool t);
359 void insert_edge(
void);
361 Edge** next_ref(
void);
363 Edge** prev_ref(
void);
365 Edge** vnext_ref(
void);
367 Edge** vprev_ref(
void);
372 static void*
operator new(
size_t s,
Space& home);
375 static void operator delete(
void*,
Space&) {};
377 static void operator delete(
void*) {};
469 void free_alternating_paths(
void);
472 void strongly_connected_components(
void);
479 bool augmenting_path(
Node*);
489 void dfs(
Node*, BitSet&, BitSet&,
int[],
490 NodeStack&, NodeStack&,
int&);
495 void*
operator new(
size_t t,
Space& home);
497 void operator delete(
void*,
Space&) {}
511 nf(static_cast<unsigned char>(nf0)),
noe(0) {}
559 Node::operator
new(
size_t s,
Space& home) {
560 return home.ralloc(s);
629 int kidx,
int kshift,
int count) :
630 Node(
NF_VAL,kshift), _klb(min), _kub(max), _kidx(kidx), _kcount(count),
632 lb(min), ublow(max), ub(max),
818 if (
this ==
x->first()) {
819 Edge** ref =
x->adj();
824 if (
this ==
x->last())
828 Edge* pv = prev_vedge;
829 Edge* nv = next_vedge;
835 if (
this ==
v->first()) {
836 Edge** ref =
v->adj();
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();
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--; )
1162 start[
i] = vals[
i-n_var]->
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()) {
1222 if (t->
type() != sp) {
1235 template<
class Card>
1243 if (Card::propagate) {
1244 for (
int i = n_val;
i--; ) {
1252 int rm = v->
kmax() - k[
i].max();
1255 if ((k[
i].
max() != k[
i].counter()) || (k[
i].
max() == 0)) {
1261 if (inc_ubc <= k[
i].
max()) {
1266 v->
cap(
LBC, k[
i].max() - inc_lbc);
1274 v->
cap(
LBC,k[
i].max() - (inc_lbc));
1279 if (inc_lbc < k[
i].
min() && v->
noe > 0) {
1285 for (
int i = n_var;
i--; ) {
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))
1396 while (!re.
empty()) {
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) {
1427 for (
int i = n_val;
i--; ) {
1429 if (Card::propagate && (k[
i].counter() == 0))
1432 if (Card::propagate)
1443 if (Card::propagate)
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) {
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()) {
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()) {
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));
1697 m = v->
type() ? e->matched(
LBC) : !e->matched(
LBC);
1700 m = v->
type() ? !e->matched(
UBC) : e->matched(
UBC);
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,
1760 roots, unfinished, count);
1763 template<
class Card>
1766 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.
#define GECODE_ASSUME(p)
Assert certain property.
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.