Generated on Thu Jul 21 2022 00:00:00 for Gecode by doxygen 1.9.4
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 };
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:
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
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*
1766 return home.ralloc(t);
1767 }
1768
1769}}}
1770
1771// STATISTICS: int-prop
1772
1773
NodeType t
Type of node.
Definition: bool-expr.cpp:230
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
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
Variable-value-graph used during propagation.
Definition: dom-sup.hpp:387
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
int val(void) const
Return current value.
Handle to region.
Definition: region.hpp:55
Computation spaces.
Definition: core.hpp:1742
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2837
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.
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.
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
BC
Bounds constraint (BC) type.
Definition: dom-sup.hpp:48
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
unsigned int size(I &i)
Size of all ranges of range iterator i.
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:101
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:767
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
void roots(Home home, const IntVarArgs &x, SetVar y, SetVar z)
Post constraint .
Definition: aliases.hpp:163
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 .
Definition: arithmetic.cpp:49
Post propagator for SetVar x
Definition: set.hh:767
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})
const int v[7]
Definition: distinct.cpp:259
#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