Generated on Thu Jan 20 2022 00:00:00 for Gecode by doxygen 1.9.1
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 
40 namespace Gecode { namespace Int { namespace GCC {
41 
48  enum BC {UBC = 1, LBC = 0};
49 
50  class Edge;
52  class Node {
53  protected:
55  Edge* e;
61  Edge* ie;
63  int idx;
65  enum NodeFlag {
67  NF_NONE = 0,
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  Node(void);
86  Node(NodeFlag nf, int i);
88 
90 
91  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  void first(Edge* p);
112  void last(Edge* p);
114  void inedge(Edge* p);
116  void index(int i);
118 
120 
121  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  VarNode(void);
143  VarNode(int i);
145 
147 
148  Edge* get_match(BC bc) const;
151  bool matched(BC bc) const;
153 
155 
156  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;
175  int _kcount;
177  int noc;
179  int lb;
181  int ublow;
183  int ub;
184  public:
186  int val;
187 
189 
190  ValNode(void);
199  ValNode(int min, int max, int value, int kidx, int kshift, int count);
201 
203 
204  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  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  Edge(void) {}
304  Edge(VarNode* x, ValNode* v);
306 
308 
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;
330  VarNode* getVar(void) const;
332  ValNode* getVal(void) const;
337  Node* getMate(bool t) const;
339 
341 
342  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  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>
387  class VarValGraph {
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 
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 
513  forceinline Edge**
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
577  VarNode::matched(BC bc) const {
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 
610  VarNode::get_match(BC bc) const {
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
674  ValNode::matched(BC bc) const {
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
753  ValNode::inc(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
808  Edge::unlink(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 
845  Edge::Edge(VarNode* var, ValNode* val) :
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
851  Edge::use(BC bc) {
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  }
888  forceinline Edge**
890  return &next_vedge;
891  }
893  Edge::prev(void) const {
894  return prev_edge;
895  }
896  forceinline Edge**
898  return &prev_edge;
899  }
901  Edge::vprev(void) const {
902  return prev_vedge;
903  }
904  forceinline Edge**
906  return &prev_vedge;
907  }
908  forceinline Edge**
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  }
1568  GECODE_NEVER;
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 
void roots(Home home, const IntVarArgs &x, SetVar y, SetVar z)
Post constraint .
Definition: aliases.hpp:163
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
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
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.
View arrays.
Definition: array.hpp:253
Base * next(void) const
Return next test.
Definition: test.hpp:58
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 count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
Definition: count.cpp:40
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
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::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