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