Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
dom-sup.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5 *
6 * Contributing authors:
7 * Christian Schulte <schulte@gecode.org>
8 * Guido Tack <tack@gecode.org>
9 *
10 * Copyright:
11 * Patrick Pekczynski, 2005
12 * Christian Schulte, 2009
13 * Guido Tack, 2009
14 *
15 * This file is part of Gecode, the generic constraint
16 * development environment:
17 * http://www.gecode.org
18 *
19 * Permission is hereby granted, free of charge, to any person obtaining
20 * a copy of this software and associated documentation files (the
21 * "Software"), to deal in the Software without restriction, including
22 * without limitation the rights to use, copy, modify, merge, publish,
23 * distribute, sublicense, and/or sell copies of the Software, and to
24 * permit persons to whom the Software is furnished to do so, subject to
25 * the following conditions:
26 *
27 * The above copyright notice and this permission notice shall be
28 * included in all copies or substantial portions of the Software.
29 *
30 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37 *
38 */
39
40namespace Gecode { namespace Int { namespace GCC {
41
48 enum BC {UBC = 1, LBC = 0};
49
50 class Edge;
52 class Node {
53 protected:
63 int idx;
65 enum NodeFlag {
69 NF_VAL = 1 << 0,
71 NF_M_LBC = 1 << 1,
73 NF_M_UBC = 1 << 2
74 };
75
76 unsigned char nf;
77 public:
79 int noe;
80
82
83
84 Node(void);
86 Node(NodeFlag nf, int i);
88
90
91
92 bool type(void) const;
94 Edge** adj(void);
96 Edge* first(void) const;
98 Edge* last(void) const;
100 Edge* inedge(void) const;
102 int index(void) const;
104 bool removed(void) const;
106
108
109
110 void first(Edge* p);
112 void last(Edge* p);
114 void inedge(Edge* p);
116 void index(int i);
118
120
121
122 static void* operator new(size_t s, Space& home);
124 static void operator delete(void*, Space&) {};
126 static void operator delete(void*) {};
128 };
129
131 class VarNode : public Node {
132 protected:
137 public:
139
140
141 VarNode(void);
143 VarNode(int i);
145
147
148
149 Edge* get_match(BC bc) const;
151 bool matched(BC bc) const;
153
155
156
157 void set_match(BC bc, Edge* m);
159 void match(BC bc);
161 void unmatch(BC bc);
163 };
164
166 class ValNode : public Node {
167 protected:
169 int _klb;
171 int _kub;
173 int _kidx;
177 int noc;
179 int lb;
181 int ublow;
183 int ub;
184 public:
186 int val;
187
189
190
191 ValNode(void);
199 ValNode(int min, int max, int value, int kidx, int kshift, int count);
201
203
204
205 int maxlow(void) const;
207 void card_conflict(int c);
209 int card_conflict(void) const;
211 void red_conflict(void);
213 void inc(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;
233
235
236
237 void maxlow(int i);
239 void kcount(int);
241 void kindex(int);
243 void dec(BC bc);
245 void inc(BC bc);
247 int cap(BC bc) const;
249 void cap(BC bc, int c);
251 void match(BC bc);
253 void unmatch(BC bc);
255 void reset(void);
257 void kmin(int min);
259 void kmax(int max);
261 };
262
264 class Edge {
265 private:
267 VarNode* x;
269 ValNode* v;
271 Edge* next_edge;
273 Edge* prev_edge;
275 Edge* next_vedge;
277 Edge* prev_vedge;
279 enum EdgeFlag {
281 EF_NONE = 0,
283 EF_MRKLB = 1 << 0,
285 EF_MRKUB = 1 << 1,
287 EF_LM = 1 << 2,
289 EF_UM = 1 << 3,
291 EF_DEL = 1 << 4
292 };
294 unsigned char ef;
295 public:
297
298
299 Edge(void) {}
304 Edge(VarNode* x, ValNode* v);
306
308
309
310 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;
330 VarNode* getVar(void) const;
332 ValNode* getVal(void) const;
337 Node* getMate(bool t) const;
339
341
342
343 void use(BC bc);
345 void free(BC bc);
347 void reset(BC bc);
349 void match(BC bc);
351 void unmatch(BC bc);
353 void unmatch(BC bc, bool t);
355 void unlink(void);
357 void del_edge(void);
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);
369
371
372
373 static void* operator new(size_t s, Space& home);
375 static void operator delete(void*, Space&) {};
377 static void operator delete(void*) {};
379 };
380
381
386 template<class Card>
388 private:
390 typedef Support::StaticStack<Node*,Region> NodeStack;
392 typedef Support::BitSet<Region> BitSet;
394 VarNode** vars;
402 ValNode** vals;
404 int n_var;
410 int n_val;
412 int n_node;
418 int sum_min;
424 int sum_max;
425 public:
427
428
434 VarValGraph(Space& home,
436 int smin, int smax);
438
440
443
454 template<BC>
455 ExecStatus narrow(Space& home,
457
464 template<BC>
466
468 template<BC>
469 void free_alternating_paths(void);
471 template<BC>
478 template<BC>
479 bool augmenting_path(Node*);
480
481 protected:
488 template<BC>
489 void dfs(Node*, BitSet&, BitSet&, int[],
490 NodeStack&, NodeStack&, int&);
491
493 public:
495 void* operator new(size_t t, Space& home);
497 void operator delete(void*, Space&) {}
498 };
499
500
501
502 /*
503 * Nodes
504 *
505 */
507 Node::Node(void) {}
510 : e(NULL), fst(NULL), lst(NULL), ie(NULL), idx(i),
511 nf(static_cast<unsigned char>(nf0)), noe(0) {}
512
514 Node::adj(void) {
515 return &e;
516 }
518 Node::first(void) const {
519 return fst;
520 }
522 Node::last(void) const {
523 return lst;
524 }
525 forceinline void
527 fst = p;
528 }
529 forceinline void
531 lst = p;
532 }
533 forceinline bool
534 Node::type(void) const {
535 return (nf & NF_VAL) != 0;
536 }
538 Node::inedge(void) const {
539 return ie;
540 }
541 forceinline void
543 ie = p;
544 }
545 forceinline bool
546 Node::removed(void) const {
547 return noe == 0;
548 }
549 forceinline void
550 Node::index(int i) {
551 idx = i;
552 }
553 forceinline int
554 Node::index(void) const {
555 return idx;
556 }
557
558 forceinline void*
559 Node::operator new(size_t s, Space& home) {
560 return home.ralloc(s);
561 }
562
563
564
565 /*
566 * Variable nodes
567 *
568 */
571
574 Node(NF_NONE,x), ubm(NULL), lbm(NULL) {}
575
576 forceinline bool
578 if (bc == UBC)
579 return (nf & NF_M_UBC) != 0;
580 else
581 return (nf & NF_M_LBC) != 0;
582 }
583
584 forceinline void
586 if (bc == UBC)
587 nf |= NF_M_UBC;
588 else
589 nf |= NF_M_LBC;
590 }
591
592 forceinline void
594 if (bc == UBC)
595 ubm = p;
596 else
597 lbm = p;
598 }
599
600 forceinline void
602 if (bc == UBC) {
603 nf &= ~NF_M_UBC; ubm = NULL;
604 } else {
605 nf &= ~NF_M_LBC; lbm = NULL;
606 }
607 }
608
611 if (bc == UBC)
612 return ubm;
613 else
614 return lbm;
615 }
616
617
618
619
620 /*
621 * Value nodes
622 *
623 */
626
628 ValNode::ValNode(int min, int max, int value,
629 int kidx, int kshift, int count) :
630 Node(NF_VAL,kshift), _klb(min), _kub(max), _kidx(kidx), _kcount(count),
631 noc(0),
632 lb(min), ublow(max), ub(max),
633 val(value) {}
634
635 forceinline void
637 assert(i >= lb);
638 ublow = i;
639 }
640
641 forceinline int
642 ValNode::maxlow(void) const {
643 if (_klb == _kub) {
644 assert(ublow == lb);
645 }
646 return ublow;
647 }
648
649
650 forceinline void
652 noc = c;
653 }
654
655 forceinline void
657 noc--;
658 assert(noc >= 0);
659 }
660
661 forceinline int
663 return noc;
664 }
665
666 forceinline int
667 ValNode::cap(BC bc) const {
668 if (bc == UBC)
669 return ub;
670 else
671 return lb;
672 }
673 forceinline bool
675 return cap(bc) == 0;
676 }
677
678 forceinline void
680 lb = _klb;
681 ublow = _kub;
682 ub = _kub;
683 noe = 0;
684 }
685
686 forceinline int
687 ValNode::kbound(BC bc) const {
688 if (bc == UBC) {
689 return _kub;
690 } else {
691 return _klb;
692 }
693 }
694
695 forceinline int
696 ValNode::kmax(void) const {
697 return _kub;
698 }
699
700 forceinline int
701 ValNode::kmin(void) const {
702 return _klb;
703 }
704
705 forceinline void
706 ValNode::kmin(int klb) {
707 _klb = klb;
708 }
709
710 forceinline void
711 ValNode::kmax(int kub) {
712 _kub = kub;
713 }
714
715
716 forceinline void
718 if (bc == UBC) {
719 ub--;
720 } else {
721 lb--; ublow--;
722 }
723 }
724
725 forceinline void
727 if (bc == UBC) {
728 ub++;
729 } else {
730 lb++; ublow++;
731 }
732 }
733
734 forceinline void
736 dec(bc);
737 }
738
739 forceinline void
741 inc(bc);
742 }
743
744 forceinline void
745 ValNode::cap(BC bc, int c) {
746 if (bc == UBC)
747 ub = c;
748 else
749 lb = c;
750 }
751
752 forceinline void
754 _kcount++;
755 }
756
757 forceinline int
758 ValNode::kcount(void) const {
759 return _kcount;
760 }
761
762 forceinline void
764 _kcount = c;
765 }
766
767 forceinline void
769 _kidx = i;
770 }
771
772 forceinline int
773 ValNode::kindex(void) const {
774 return _kidx;
775 }
776
778 forceinline int
780 if (bc == LBC)
781 return _kub - ublow + _kcount;
782 else
783 return _kub - ub + _kcount;
784 }
785
786
787 forceinline bool
788 ValNode::sink(void) const {
789 // there are only incoming edges
790 // in case of the UBC-matching
791 return _kub - ub == noe;
792 }
793
794 forceinline bool
795 ValNode::source(void) const {
796 // there are only incoming edges
797 // in case of the UBC-matching
798 return _klb - lb == noe;
799 }
800
801
802
803 /*
804 * Edges
805 *
806 */
807 forceinline void
809 // unlink from variable side
810 Edge* p = prev_edge;
811 Edge* n = next_edge;
812
813 if (p != NULL)
814 *p->next_ref() = n;
815 if (n != NULL)
816 *n->prev_ref() = p;
817
818 if (this == x->first()) {
819 Edge** ref = x->adj();
820 *ref = n;
821 x->first(n);
822 }
823
824 if (this == x->last())
825 x->last(p);
826
827 // unlink from value side
828 Edge* pv = prev_vedge;
829 Edge* nv = next_vedge;
830
831 if (pv != NULL)
832 *pv->vnext_ref() = nv;
833 if (nv != NULL)
834 *nv->vprev_ref() = pv;
835 if (this == v->first()) {
836 Edge** ref = v->adj();
837 *ref = nv;
838 v->first(nv);
839 }
840 if (this == v->last())
841 v->last(pv);
842 }
843
846 x(var), v(val),
847 next_edge(NULL), prev_edge(NULL),
848 next_vedge(NULL), prev_vedge(NULL), ef(EF_NONE) {}
849
850 forceinline void
852 if (bc == UBC)
853 ef |= EF_MRKUB;
854 else
855 ef |= EF_MRKLB;
856 }
857 forceinline void
859 if (bc == UBC)
860 ef &= ~EF_MRKUB;
861 else
862 ef &= ~EF_MRKLB;
863 }
864 forceinline bool
865 Edge::used(BC bc) const {
866 if (bc == UBC)
867 return (ef & EF_MRKUB) != 0;
868 else
869 return (ef & EF_MRKLB) != 0;
870 }
872 Edge::next(void) const {
873 return next_edge;
874 }
876 Edge::next(bool t) const {
877 if (t) {
878 return next_vedge;
879 } else {
880 return next_edge;
881 }
882 }
883
885 Edge::vnext(void) const {
886 return next_vedge;
887 }
890 return &next_vedge;
891 }
893 Edge::prev(void) const {
894 return prev_edge;
895 }
898 return &prev_edge;
899 }
901 Edge::vprev(void) const {
902 return prev_vedge;
903 }
906 return &prev_vedge;
907 }
910 return &next_edge;
911 }
913 Edge::getVar(void) const {
914 assert(x != NULL);
915 return x;
916 }
917
919 Edge::getVal(void) const {
920 assert(v != NULL);
921 return v;
922 }
923
925 Edge::getMate(bool type) const {
926 if (type)
927 return x;
928 else
929 return v;
930 }
931
932 forceinline void
934 if (bc == UBC)
935 ef &= ~EF_UM;
936 else
937 ef &= ~EF_LM;
938 x->unmatch(bc); v->unmatch(bc);
939 }
940
941 forceinline void
942 Edge::unmatch(BC bc, bool node) {
943 if (bc == UBC)
944 ef &= ~EF_UM;
945 else
946 ef &= ~EF_LM;
947 if (node)
948 v->unmatch(bc);
949 else
950 x->unmatch(bc);
951 }
952
953 forceinline void
955 free(bc); unmatch(bc);
956 }
957
958 forceinline void
960 if (bc == UBC)
961 ef |= EF_UM;
962 else
963 ef |= EF_LM;
964 x->match(bc);
965 x->set_match(bc,this);
966 v->match(bc);
967 }
968
969 forceinline bool
970 Edge::matched(BC bc) const {
971 if (bc == UBC)
972 return (ef & EF_UM) != 0;
973 else
974 return (ef & EF_LM) != 0;
975 }
976
977 forceinline void
979 ef |= EF_DEL;
980 }
981
982 forceinline void
984 ef &= ~EF_DEL;
985 }
986
987
988 forceinline bool
989 Edge::deleted(void) const {
990 return (ef & EF_DEL) != 0;
991 }
992
993 forceinline void*
994 Edge::operator new(size_t s, Space& home) {
995 return home.ralloc(s);
996 }
997
998
999 /*
1000 * Variable value graph
1001 *
1002 */
1003 template<class Card>
1006 int smin, int smax)
1007 : n_var(x.size()),
1008 n_val(k.size()),
1009 n_node(n_var + n_val),
1010 sum_min(smin),
1011 sum_max(smax) {
1012
1013 unsigned int noe = 0;
1014 for (int i=x.size(); i--; )
1015 noe += x[i].size();
1016
1017 vars = home.alloc<VarNode*>(n_var);
1018 vals = home.alloc<ValNode*>(n_val);
1019
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();
1024 if (kc != kma) {
1025 if (kmi >= kc) {
1026 kmi -=kc;
1027 assert(kmi >=0);
1028 } else {
1029 kmi = 0;
1030 }
1031 kma -= kc;
1032 assert (kma > 0);
1033 vals[i] = new (home)
1034 ValNode(kmi, kma, k[i].card(), i, i + n_var, kc);
1035 } else {
1036 vals[i] = new (home)
1037 ValNode(0, 0, k[i].card(), i, i + n_var, kc);
1038 }
1039 }
1040
1041 for (int i = n_var; i--; ) {
1042 vars[i] = new (home) VarNode(i);
1043 // get the space for the edges of the varnode
1044 Edge** xadjacent = vars[i]->adj();
1045
1046 int j = 0;
1047 for (ViewValues<IntView> xi(x[i]); xi(); ++xi) {
1048 // get the correct index for the value
1049 while(vals[j]->val < xi.val())
1050 j++;
1051 *xadjacent = new (home) Edge(vars[i],vals[j]);
1052 vars[i]->noe++;
1053 if (vars[i]->first() == NULL)
1054 vars[i]->first(*xadjacent);
1055 Edge* oldprev = vars[i]->last();
1056 vars[i]->last(*xadjacent);
1057 *vars[i]->last()->prev_ref() = oldprev;
1058
1059 if (vals[j]->first() == NULL) {
1060 vals[j]->first(*xadjacent);
1061 vals[j]->last(*xadjacent);
1062 } else {
1063 Edge* old = vals[j]->first();
1064 vals[j]->first(*xadjacent);
1065 *vals[j]->first()->vnext_ref() = old;
1066 *old->vprev_ref() = vals[j]->first();
1067 }
1068 vals[j]->noe++;
1069 xadjacent = (*xadjacent)->next_ref();
1070 }
1071 *xadjacent = NULL;
1072 }
1073 }
1074
1075
1076 template<class Card>
1077 inline ExecStatus
1080 ViewArray<Card>& k) {
1081 for (int i = n_val; i--; ) {
1082 ValNode* vln = vals[i];
1083 if (vln->noe > 0) {
1084 if (k[i].min() == vln->noe) {
1085 // all variable nodes reachable from vln should be equal to vln->val
1086 for (Edge* e = vln->first(); e != NULL; e = e->vnext()) {
1087 VarNode* vrn = e->getVar();
1088 for (Edge* f = vrn->first(); f != NULL; f = f->next())
1089 if (f != e) {
1090 ValNode* w = f->getVal();
1091 w->noe--;
1092 vrn->noe--;
1093 f->del_edge();
1094 f->unlink();
1095 }
1096 assert(vrn->noe == 1);
1097
1098 int vi = vrn->index();
1099 GECODE_ME_CHECK(x[vi].eq(home, vln->val));
1100
1101 vars[vi] = vars[--n_var];
1102 vars[vi]->index(vi);
1103 x.move_lst(vi);
1104 n_node--;
1105 vln->noe--;
1106 }
1107
1108
1109 int vidx = vln->kindex();
1110 if (Card::propagate)
1111 GECODE_ME_CHECK(k[vidx].eq(home, k[vidx].min()));
1112
1113 k[vidx].counter(k[vidx].min());
1114
1115 vln->cap(UBC,0);
1116 vln->cap(LBC,0);
1117 vln->maxlow(0);
1118
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();
1123 }
1124 } else {
1125 vals[i]->cap(UBC,0);
1126 vals[i]->cap(LBC,0);
1127 vals[i]->maxlow(0);
1128 vals[i]->kmax(0);
1129 vals[i]->kmin(0);
1130 }
1131
1132 if (Card::propagate && (k[i].counter() == 0))
1133 GECODE_ME_CHECK(k[i].lq(home, vals[i]->noe));
1134 }
1135
1136 for (int i = n_val; i--; )
1137 vals[i]->index(n_var + i);
1138
1139 return ES_OK;
1140 }
1141
1142 template<class Card> template<BC bc>
1143 forceinline bool
1145 Region r;
1146 NodeStack ns(r,n_node);
1147 BitSet visited(r,static_cast<unsigned int>(n_node));
1148 Edge** start = r.alloc<Edge*>(n_node);
1149
1150 // keep track of the nodes that have already been visited
1151 Node* sn = v;
1152
1153 // mark the start partition
1154 bool sp = sn->type();
1155
1156 // nodes in sp only follow free edges
1157 // nodes in V - sp only follow matched edges
1158
1159 for (int i = n_node; i--; )
1160 if (i >= n_var) {
1161 vals[i-n_var]->inedge(NULL);
1162 start[i] = vals[i-n_var]->first();
1163 } else {
1164 vars[i]->inedge(NULL);
1165 start[i] = vars[i]->first();
1166 }
1167
1168 v->inedge(NULL);
1169 ns.push(v);
1170 visited.set(static_cast<unsigned int>(v->index()));
1171 while (!ns.empty()) {
1172 Node* vv = ns.top();
1173 Edge* e = NULL;
1174 if (vv->type() == sp) {
1175 e = start[vv->index()];
1176 while ((e != NULL) && e->matched(bc))
1177 e = e->next(vv->type());
1178 } else {
1179 e = start[vv->index()];
1180 while ((e != NULL) && !e->matched(bc))
1181 e = e->next(vv->type());
1182 start[vv->index()] = e;
1183 }
1184 if (e != NULL) {
1185 start[vv->index()] = e->next(vv->type());
1186 Node* w = e->getMate(vv->type());
1187 if (!visited.get(static_cast<unsigned int>(w->index()))) {
1188 // unexplored path
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) {
1194 // augmenting path of length l > 1
1195 e->match(bc);
1196 break;
1197 } else {
1198 // augmenting path of length l = 1
1199 e->match(bc);
1200 ns.pop();
1201 return true;
1202 }
1203 } else {
1204 w->inedge(e);
1205 visited.set(static_cast<unsigned int>(w->index()));
1206 // find matching edge m incident with w
1207 ns.push(w);
1208 }
1209 }
1210 } else {
1211 // tried all outgoing edges without finding an augmenting path
1212 ns.pop();
1213 }
1214 }
1215
1216 bool pathfound = !ns.empty();
1217
1218 while (!ns.empty()) {
1219 Node* t = ns.pop();
1220 if (t != sn) {
1221 Edge* in = t->inedge();
1222 if (t->type() != sp) {
1223 in->match(bc);
1224 } else if (!sp) {
1225 in->unmatch(bc,!sp);
1226 } else {
1227 in->unmatch(bc);
1228 }
1229 }
1230 }
1231 return pathfound;
1232 }
1233
1234
1235 template<class Card>
1236 inline ExecStatus
1238 Region r;
1239 // A node can be pushed twice (once when checking cardinality and later again)
1240 NodeStack re(r,2*n_node);
1241
1242 // synchronize cardinality variables
1243 if (Card::propagate) {
1244 for (int i = n_val; i--; ) {
1245 ValNode* v = vals[i];
1246 int inc_ubc = v->incid_match(UBC);
1247 int inc_lbc = v->incid_match(LBC);
1248 if (v->noe == 0) {
1249 inc_ubc = 0;
1250 inc_lbc = 0;
1251 }
1252 int rm = v->kmax() - k[i].max();
1253 // the cardinality bounds have been modified
1254 if ((k[i].max() < v->kmax()) || (k[i].min() > v->kmin())) {
1255 if ((k[i].max() != k[i].counter()) || (k[i].max() == 0)) {
1256 // update the bounds
1257 v->kmax(k[i].max());
1258 v->kmin(k[i].min());
1259
1260 //everything is fine
1261 if (inc_ubc <= k[i].max()) {
1262 // adjust capacities
1263 v->cap(UBC, k[i].max() - inc_ubc);
1264 v->maxlow(k[i].max() - inc_lbc);
1265 if (v->kmin() == v->kmax())
1266 v->cap(LBC, k[i].max() - inc_lbc);
1267 } else {
1268 // set cap to max and resolve conflicts on view side
1269 // set to full capacity for later rescheduling
1270 if (v->cap(UBC))
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);
1276 }
1277 }
1278 }
1279 if (inc_lbc < k[i].min() && v->noe > 0) {
1280 v->cap(LBC, k[i].min() - inc_lbc);
1281 re.push(v);
1282 }
1283 }
1284
1285 for (int i = n_var; i--; ) {
1286 Edge* mub = vars[i]->get_match(UBC);
1287 if (mub != NULL) {
1288 ValNode* vu = mub->getVal();
1289 if ((vars[i]->noe != 1) && vu->card_conflict()) {
1290 vu->red_conflict();
1291 mub->unmatch(UBC,vars[i]->type());
1292 re.push(vars[i]);
1293 }
1294 }
1295 }
1296 }
1297
1298 // go on with synchronization
1299 assert(x.size() == n_var);
1300 for (int i = n_var; i--; ) {
1301
1302 VarNode* vrn = vars[i];
1303 if (static_cast<int>(x[i].size()) != vrn->noe) {
1304 // if the variable is already assigned
1305 if (x[i].assigned()) {
1306 int v = x[i].val();
1307 Edge* mub = vrn->get_match(UBC);
1308 if ((mub != NULL) && (v != mub->getVal()->val)) {
1309 mub->unmatch(UBC);
1310 re.push(vars[i]);
1311 }
1312
1313 Edge* mlb = vrn->get_match(LBC);
1314 if (mlb != NULL) {
1315 ValNode* vln = mlb->getVal();
1316 if (v != vln->val) {
1317 mlb->unmatch(LBC);
1318 if (vln->incid_match(LBC) < vln->kmin())
1319 re.push(vln);
1320 }
1321 }
1322
1323 for (Edge* e = vrn->first(); e != NULL; e = e->next()) {
1324 ValNode* vln = e->getVal();
1325 if (vln->val != v) {
1326 vrn->noe--;
1327 e->getVal()->noe--;
1328 e->del_edge();
1329 e->unlink();
1330 }
1331 }
1332 } else {
1333
1334 // delete the edge
1335 ViewValues<IntView> xiter(x[i]);
1336 Edge* mub = vrn->get_match(UBC);
1337 Edge* mlb = vrn->get_match(LBC);
1338 Edge** p = vrn->adj();
1339 Edge* e = *p;
1340 GECODE_ASSUME(e != NULL);
1341 do {
1342 // search the edge that has to be deleted
1343 while ((e != NULL) && (e->getVal()->val < xiter.val())) {
1344 // Skip edge
1345 e->getVal()->noe--;
1346 vrn->noe--;
1347 e->del_edge();
1348 e->unlink();
1349 e = e ->next();
1350 *p = e;
1351 }
1352 GECODE_ASSUME(e != NULL);
1353
1354 assert(xiter.val() == e->getVal()->val);
1355
1356 // This edge must be kept
1357 e->free(UBC);
1358 e->free(LBC);
1359 ++xiter;
1360 p = e->next_ref();
1361 e = e->next();
1362 } while (xiter());
1363 *p = NULL;
1364 while (e != NULL) {
1365 e->getVar()->noe--;
1366 e->getVal()->noe--;
1367 e->del_edge();
1368 e->unlink();
1369 e = e->next();
1370 }
1371
1372 if ((mub != NULL) && mub->deleted()) {
1373 mub->unmatch(UBC);
1374 re.push(vars[i]);
1375 }
1376
1377 //lower bound matching can be zero
1378 if ((mlb != NULL) && mlb->deleted()) {
1379 ValNode* vln = mlb->getVal();
1380 mlb->unmatch(LBC);
1381 if (vln->incid_match(LBC) < vln->kmin())
1382 re.push(vln);
1383 }
1384 }
1385 }
1386 vars[i]->index(i);
1387 }
1388
1389 for (int i = n_val; i--; ) {
1390 if ((k[i].min() > vals[i]->noe) && (k[i].counter() == 0))
1391 return ES_FAILED;
1392 vals[i]->index(n_var + i);
1393 }
1394
1395 // start repair
1396 while (!re.empty()) {
1397 Node* n = re.pop();
1398 if (!n->removed()) {
1399 if (!n->type()) {
1400 VarNode* vrn = static_cast<VarNode*>(n);
1401 if (!vrn->matched(UBC) && !augmenting_path<UBC>(vrn))
1402 return ES_FAILED;
1403 } else {
1404 ValNode* vln = static_cast<ValNode*>(n);
1405 while (!vln->matched(LBC))
1406 if (!augmenting_path<LBC>(vln))
1407 return ES_FAILED;
1408 }
1409 }
1410 }
1411
1412 return ES_OK;
1413 }
1414
1415 template<class Card> template<BC bc>
1416 inline ExecStatus
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);
1423 GECODE_ME_CHECK(x[i].eq(home, v->val));
1424 v->inc();
1425 }
1426
1427 for (int i = n_val; i--; ) {
1428 ValNode* v = vals[i];
1429 if (Card::propagate && (k[i].counter() == 0))
1430 GECODE_ME_CHECK(k[i].lq(home, v->noe));
1431 if (v->noe > 0) {
1432 if (Card::propagate)
1433 GECODE_ME_CHECK(k[i].lq(home, v->noe));
1434
1435 // If the maximum number of occurences of a value is reached
1436 // it cannot be consumed by another view
1437
1438 if (v->kcount() == v->kmax()) {
1439 int vidx = v->kindex();
1440
1441 k[i].counter(v->kcount());
1442
1443 if (Card::propagate)
1444 GECODE_ME_CHECK(k[i].eq(home, k[i].counter()));
1445
1446 bool delall = v->card_conflict() && (v->noe > v->kmax());
1447
1448 for (Edge* e = v->last(); e != NULL; e = e->vprev()) {
1449 VarNode* vrn = e->getVar();
1450 if (vrn->noe == 1) {
1451 vrn->noe--;
1452 v->noe--;
1453 int vi= vrn->index();
1454
1455 x.move_lst(vi);
1456 vars[vi] = vars[--n_var];
1457 vars[vi]->index(vi);
1458 n_node--;
1459 e->del_edge();
1460 e->unlink();
1461
1462 } else if (delall) {
1463 GECODE_ME_CHECK(x[vrn->index()].nq(home, v->val));
1464 vrn->noe--;
1465 v->noe--;
1466 e->del_edge();
1467 e->unlink();
1468 }
1469 }
1470 v->cap(UBC,0);
1471 v->cap(LBC,0);
1472 v->maxlow(0);
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();
1477
1478 } else if (v->kcount() > 0) {
1479 v->kcount(0);
1480 }
1481 }
1482 }
1483 for (int i = n_var; i--; )
1484 vars[i]->index(i);
1485
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);
1490 vals[i]->maxlow(0);
1491 }
1492 vals[i]->index(n_var + i);
1493 }
1494
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)) {
1499 GECODE_ME_CHECK(x[i].nq(home, e->getVal()->val));
1500 } else {
1501 e->free(bc);
1502 }
1503 }
1504 }
1505 }
1506 return ES_OK;
1507 }
1508
1509 template<class Card> template<BC bc>
1510 inline ExecStatus
1512 int card_match = 0;
1513 // find an intial matching in O(n*d)
1514 // greedy algorithm
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++;
1519 }
1520
1521 Region r;
1522 switch (bc) {
1523 case LBC:
1524 if (card_match < sum_min) {
1526
1527 // find failed nodes
1528 for (int i = n_val; i--; )
1529 if (!vals[i]->matched(LBC))
1530 free.push(vals[i]);
1531
1532 while (!free.empty()) {
1533 ValNode* v = free.pop();
1534 while (!v->matched(LBC))
1535 if (augmenting_path<LBC>(v))
1536 card_match++;
1537 else
1538 break;
1539 }
1540
1541 return (card_match >= sum_min) ? ES_OK : ES_FAILED;
1542 } else {
1543 return ES_OK;
1544 }
1545 break;
1546 case UBC:
1547 if (card_match < n_var) {
1549
1550 // find failed nodes
1551 for (int i = n_var; i--; )
1552 if (!vars[i]->matched(UBC))
1553 free.push(vars[i]);
1554
1555 while (!free.empty()) {
1556 VarNode* v = free.pop();
1557 if (!v->matched(UBC) && augmenting_path<UBC>(v))
1558 card_match++;
1559 }
1560
1561 return (card_match >= n_var) ? ES_OK : ES_FAILED;
1562 } else {
1563 return ES_OK;
1564 }
1565 break;
1566 default: GECODE_NEVER;
1567 }
1569 return ES_FAILED;
1570 }
1571
1572
1573 template<class Card> template<BC bc>
1574 forceinline void
1576 Region r;
1577 NodeStack ns(r,n_node);
1578 BitSet visited(r,static_cast<unsigned int>(n_node));
1579
1580 switch (bc) {
1581 case LBC:
1582 // after a maximum matching on the value nodes there still can be
1583 // free value nodes, hence we have to consider ALL nodes whether
1584 // they are the starting point of an even alternating path in G
1585 for (int i = n_var; i--; )
1586 if (!vars[i]->matched(LBC)) {
1587 ns.push(vars[i]);
1588 visited.set(static_cast<unsigned int>(vars[i]->index()));
1589 }
1590 for (int i = n_val; i--; )
1591 if (!vals[i]->matched(LBC)) {
1592 ns.push(vals[i]);
1593 visited.set(static_cast<unsigned int>(vals[i]->index()));
1594 }
1595 break;
1596 case UBC:
1597 // clearly, after a maximum matching on the x variables
1598 // corresponding to a set cover on x there are NO free var nodes
1599 for (int i = n_val; i--; )
1600 if (!vals[i]->matched(UBC)) {
1601 ns.push(vals[i]);
1602 visited.set(static_cast<unsigned int>(vals[i]->index()));
1603 }
1604 break;
1605 default: GECODE_NEVER;
1606 }
1607
1608 while (!ns.empty()) {
1609 Node* node = ns.pop();
1610 if (node->type()) {
1611 // ValNode
1612 ValNode* vln = static_cast<ValNode*>(node);
1613
1614 for (Edge* cur = vln->first(); cur != NULL; cur = cur->vnext()) {
1615 VarNode* mate = cur->getVar();
1616 switch (bc) {
1617 case LBC:
1618 if (cur->matched(LBC)) {
1619 // mark the edge
1620 cur->use(LBC);
1621 if (!visited.get(static_cast<unsigned int>(mate->index()))) {
1622 ns.push(mate);
1623 visited.set(static_cast<unsigned int>(mate->index()));
1624 }
1625 }
1626 break;
1627 case UBC:
1628 if (!cur->matched(UBC)) {
1629 // mark the edge
1630 cur->use(UBC);
1631 if (!visited.get(static_cast<unsigned int>(mate->index()))) {
1632 ns.push(mate);
1633 visited.set(static_cast<unsigned int>(mate->index()));
1634 }
1635 }
1636 break;
1637 default: GECODE_NEVER;
1638 }
1639 }
1640
1641 } else {
1642 // VarNode
1643 VarNode* vrn = static_cast<VarNode*>(node);
1644
1645 switch (bc) {
1646 case LBC:
1647 // after LBC-matching we can follow every unmatched edge
1648 for (Edge* cur = vrn->first(); cur != NULL; cur = cur->next()) {
1649 ValNode* mate = cur->getVal();
1650 if (!cur->matched(LBC)) {
1651 cur->use(LBC);
1652 if (!visited.get(static_cast<unsigned int>(mate->index()))) {
1653 ns.push(mate);
1654 visited.set(static_cast<unsigned int>(mate->index()));
1655 }
1656 }
1657 }
1658 break;
1659 case UBC:
1660 // after UBC-matching we can only follow a matched edge
1661 {
1662 Edge* cur = vrn->get_match(UBC);
1663 if (cur != NULL) {
1664 cur->use(UBC);
1665 ValNode* mate = cur->getVal();
1666 if (!visited.get(static_cast<unsigned int>(mate->index()))) {
1667 ns.push(mate);
1668 visited.set(static_cast<unsigned int>(mate->index()));
1669 }
1670 }
1671 }
1672 break;
1673 default: GECODE_NEVER;
1674 }
1675 }
1676 }
1677 }
1678
1679 template<class Card> template<BC bc>
1680 void
1682 BitSet& inscc, BitSet& in_unfinished, int dfsnum[],
1683 NodeStack& roots, NodeStack& unfinished,
1684 int& count) {
1685 count++;
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));
1690
1691 unfinished.push(v);
1692 roots.push(v);
1693 for (Edge* e = v->first(); e != NULL; e = e->next(v->type())) {
1694 bool m;
1695 switch (bc) {
1696 case LBC:
1697 m = v->type() ? e->matched(LBC) : !e->matched(LBC);
1698 break;
1699 case UBC:
1700 m = v->type() ? !e->matched(UBC) : e->matched(UBC);
1701 break;
1702 default: GECODE_NEVER;
1703 }
1704 if (m) {
1705 Node* w = e->getMate(v->type());
1706 int w_index = w->index();
1707
1708 assert(w_index < n_node);
1709 if (!inscc.get(static_cast<unsigned int>(w_index))) {
1710 // w is an uncompleted scc
1711 w->inedge(e);
1712 dfs<bc>(w, inscc, in_unfinished, dfsnum,
1713 roots, unfinished, count);
1714 } else if (in_unfinished.get(static_cast<unsigned int>(w_index))) {
1715 // even alternating cycle found mark the edge closing the cycle,
1716 // completing the scc
1717 e->use(bc);
1718 // if w belongs to an scc we detected earlier
1719 // merge components
1720 assert(roots.top()->index() < n_node);
1721 while (dfsnum[roots.top()->index()] > dfsnum[w_index]) {
1722 roots.pop();
1723 }
1724 }
1725 }
1726 }
1727
1728 if (v == roots.top()) {
1729 while (v != unfinished.top()) {
1730 // w belongs to the scc with root v
1731 Node* w = unfinished.top();
1732 w->inedge()->use(bc);
1733 in_unfinished.clear(static_cast<unsigned int>(w->index()));
1734 unfinished.pop();
1735 }
1736 assert(v == unfinished.top());
1737 in_unfinished.clear(static_cast<unsigned int>(v_index));
1738 roots.pop();
1739 unfinished.pop();
1740 }
1741 }
1742
1743 template<class Card> template<BC bc>
1744 forceinline void
1746 Region r;
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);
1750
1751 for (int i = n_node; i--; )
1752 dfsnum[i]=0;
1753
1754 int count = 0;
1755 NodeStack roots(r,n_node);
1756 NodeStack unfinished(r,n_node);
1757
1758 for (int i = n_var; i--; )
1759 dfs<bc>(vars[i], inscc, in_unfinished, dfsnum,
1760 roots, unfinished, count);
1761 }
1762
1763 template<class Card>
1764 forceinline void*
1765 VarValGraph<Card>::operator new(size_t t, Space& home) {
1766 return home.ralloc(t);
1767 }
1768
1769}}}
1770
1771// STATISTICS: int-prop
1772
1773
Class for edges in the variable-value-graph.
Definition dom-sup.hpp:264
void use(BC bc)
Update.
Definition dom-sup.hpp:851
void free(BC bc)
Mark the edge as unused.
Definition dom-sup.hpp:858
Edge * vprev(void) const
return the pointer to the previous edge incident on v
Definition dom-sup.hpp:901
Edge * vnext(void) const
return the pointer to the next edge incident on v
Definition dom-sup.hpp:885
void del_edge(void)
Mark the edge as deleted during synchronization.
Definition dom-sup.hpp:978
Edge ** prev_ref(void)
return the reference to the previous edge incident on x
Definition dom-sup.hpp:897
bool deleted(void) const
return whether the edge has been deleted from the graph
Definition dom-sup.hpp:989
void match(BC bc)
Match the edge.
Definition dom-sup.hpp:959
void unmatch(BC bc)
Unmatch the edge and the incident nodes.
Definition dom-sup.hpp:933
Edge ** vprev_ref(void)
return the reference to the previous edge incident on v
Definition dom-sup.hpp:905
Edge * prev(void) const
return the pointer to the previous edge incident on x
Definition dom-sup.hpp:893
void unlink(void)
Unlink the edge from the linked list of edges.
Definition dom-sup.hpp:808
void insert_edge(void)
Insert the edge again.
Definition dom-sup.hpp:983
Edge ** vnext_ref(void)
return the reference to the next edge incident on v
Definition dom-sup.hpp:889
Edge(void)
Default constructor.
Definition dom-sup.hpp:299
ValNode * getVal(void) const
return the pointer to the value node v of this edge
Definition dom-sup.hpp:919
Node * getMate(bool t) const
return pointer to x if t = true otherwise return v
Definition dom-sup.hpp:925
bool matched(BC bc) const
return whether the edge is matched
Definition dom-sup.hpp:970
void reset(BC bc)
Reset the edge (free the edge, and unmatch the edge)
Definition dom-sup.hpp:954
bool used(BC bc) const
Whether the edge is used.
Definition dom-sup.hpp:865
Edge * next(void) const
return the pointer to the next edge incident on x
Definition dom-sup.hpp:872
Edge ** next_ref(void)
return the reference to the next edge incident on x
Definition dom-sup.hpp:909
VarNode * getVar(void) const
return the pointer to the variable node x of this edge
Definition dom-sup.hpp:913
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...
Definition dom-sup.hpp:876
Base class for nodes in the variable-value-graph.
Definition dom-sup.hpp:52
Edge * e
Stores all incident edges on the node.
Definition dom-sup.hpp:55
Edge * lst
Last edge.
Definition dom-sup.hpp:59
bool type(void) const
Return the type of the node (false for a variable node)
Definition dom-sup.hpp:534
Edge * last(void) const
Return pointer to the last incident edge.
Definition dom-sup.hpp:522
bool removed(void) const
check whether a node has been removed from the graph
Definition dom-sup.hpp:546
Edge * fst
First edge.
Definition dom-sup.hpp:57
Node(void)
Default constructor.
Definition dom-sup.hpp:507
int noe
stores the number of incident edges on the node
Definition dom-sup.hpp:79
NodeFlag
Flags for nodes.
Definition dom-sup.hpp:65
@ NF_M_UBC
Whether matched for UBC.
Definition dom-sup.hpp:73
@ NF_VAL
Whether node is a value node.
Definition dom-sup.hpp:69
@ NF_NONE
No flags set.
Definition dom-sup.hpp:67
@ NF_M_LBC
Whether matched for LBC.
Definition dom-sup.hpp:71
Edge * inedge(void) const
Return pointer to the node's inedge.
Definition dom-sup.hpp:538
Edge * first(void) const
Return pointer to the first incident edge.
Definition dom-sup.hpp:518
unsigned char nf
Flags for node.
Definition dom-sup.hpp:76
Edge * ie
Single incoming edge used for storing a path in the algorithms.
Definition dom-sup.hpp:61
Edge ** adj(void)
Return reference to the incident edges.
Definition dom-sup.hpp:514
int index(void) const
Get index of either variable or value.
Definition dom-sup.hpp:554
int lb
Minimal capacity of the value node.
Definition dom-sup.hpp:179
int _kidx
Index to acces the value via cardinality array k.
Definition dom-sup.hpp:173
void unmatch(BC bc)
unmatch the node
Definition dom-sup.hpp:740
int kmin(void) const
return the minimal node capacity as stored in k
Definition dom-sup.hpp:701
int kbound(BC bc) const
return minimal or maximal capacity
Definition dom-sup.hpp:687
void match(BC bc)
match the node
Definition dom-sup.hpp:735
int incid_match(BC bc) const
returns the number of incident matching edges on a value node
Definition dom-sup.hpp:779
int _klb
Minimal required occurence of the value as stored in k.
Definition dom-sup.hpp:169
int _kcount
Stores the current number of occurences of the value.
Definition dom-sup.hpp:175
int ublow
Smallest maximal capacity of the value node.
Definition dom-sup.hpp:181
bool matched(BC bc) const
returns true if the node is matched in BC, false otherwise
Definition dom-sup.hpp:674
bool source(void) const
tests whether the node is a source
Definition dom-sup.hpp:795
int maxlow(void) const
get max cap for LBC
Definition dom-sup.hpp:642
int card_conflict(void) const
Check whether the value node is conflicting.
Definition dom-sup.hpp:662
int noc
Store numbre of conflicting matching edges.
Definition dom-sup.hpp:177
void card_conflict(int c)
Mark the value node as conflicting in case of variable cardinalities.
Definition dom-sup.hpp:651
void dec(BC bc)
decrease the node-capacity
Definition dom-sup.hpp:717
void reset(void)
node reset to original capacity values
Definition dom-sup.hpp:679
int val
Stores the value of the node.
Definition dom-sup.hpp:186
int kmax(void) const
return the maximal node capacity as stored in k
Definition dom-sup.hpp:696
void red_conflict(void)
Reduce the conflict counter.
Definition dom-sup.hpp:656
int kcount(void) const
returns the current number of occurences of the value
Definition dom-sup.hpp:758
bool sink(void) const
tests whether the node is a sink
Definition dom-sup.hpp:788
int _kub
Maximal required occurence of the value as stored in k.
Definition dom-sup.hpp:171
int ub
Maximal capacity of the value node.
Definition dom-sup.hpp:183
int cap(BC bc) const
return the the node-capacity
Definition dom-sup.hpp:667
int kindex(void) const
returns the index in cardinality array k
Definition dom-sup.hpp:773
ValNode(void)
Default constructor.
Definition dom-sup.hpp:625
void inc(void)
increases the value counter
Definition dom-sup.hpp:753
Edge * ubm
Stores the matching edge on this node in the UBC.
Definition dom-sup.hpp:134
void match(BC bc)
Set node to matched.
Definition dom-sup.hpp:585
VarNode(void)
Default constructor.
Definition dom-sup.hpp:570
bool matched(BC bc) const
tests whether the node is matched or not
Definition dom-sup.hpp:577
void set_match(BC bc, Edge *m)
Set the pointer of the matching edge to m.
Definition dom-sup.hpp:593
Edge * get_match(BC bc) const
Return the matching edge on the node.
Definition dom-sup.hpp:610
void unmatch(BC bc)
Unmatch the node.
Definition dom-sup.hpp:601
Edge * lbm
Stores the matching edge on this node in the LBC.
Definition dom-sup.hpp:136
ExecStatus maximum_matching(void)
Compute a maximum matching M on the graph.
Definition dom-sup.hpp:1511
ExecStatus min_require(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k)
Check whether minimum requirements shrink variable domains.
Definition dom-sup.hpp:1078
void strongly_connected_components(void)
Compute possible strongly connected components of the graph.
Definition dom-sup.hpp:1745
ExecStatus narrow(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k)
Remove edges that do not belong to any maximal matching.
Definition dom-sup.hpp:1417
void dfs(Node *, BitSet &, BitSet &, int[], NodeStack &, NodeStack &, int &)
Perform depth-first search on the graph.
Definition dom-sup.hpp:1681
void free_alternating_paths(void)
Compute possible free alternating paths in the graph.
Definition dom-sup.hpp:1575
bool augmenting_path(Node *)
Test whether the current maximal matching on the graph can be augmented by an alternating path starti...
Definition dom-sup.hpp:1144
ExecStatus sync(ViewArray< IntView > &x, ViewArray< Card > &k)
Synchronization of the graph.
Definition dom-sup.hpp:1237
VarValGraph(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k, int smin, int smax)
Constructor for the variable-value-graph.
Definition dom-sup.hpp:1004
Value iterator for integer views.
Definition view.hpp:94
int val(void) const
Return current value.
Handle to region.
Definition region.hpp:55
Computation spaces.
Definition core.hpp:1744
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition core.hpp:2841
bool get(unsigned int i) const
Access value at bit i.
void clear(unsigned int i)
Clear bit i.
void set(unsigned int i)
Set bit i.
Simple bitsets.
Definition bitset.hpp:45
Stack with fixed number of elements.
void push(const T &x)
Push element x on top of stack.
T pop(void)
Pop topmost element from stack and return it.
bool empty(void) const
Test whether stack is empty.
T & top(void) const
Return element on top of stack.
View arrays.
Definition array.hpp:253
Base * next(void) const
Return next test.
Definition test.hpp:58
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
Global cardinality propagators (Counting)
BC
Bounds constraint (BC) type.
Definition dom-sup.hpp:48
Finite domain integers.
Gecode toplevel namespace
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition count.cpp:40
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
void roots(Home home, const IntVarArgs &x, SetVar y, SetVar z)
Post constraint .
Definition aliases.hpp:163
T * dfs(T *s, const Search::Options &o=Search::Options::def)
Invoke depth-first search engine for subclass T of space s with options o.
Definition dfs.hpp:73
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
Definition set.hh:773
#define forceinline
Definition config.hpp:194
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56
#define GECODE_ASSUME(p)
Assert certain property.
Definition macros.hpp:114