Generated on Thu Mar 13 2014 04:39:31 for Gecode by doxygen 1.8.1.2
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: 2011-09-01 23:04:29 +1000 (Thu, 01 Sep 2011) $ by $Author: schulte $
17  * $Revision: 12384 $
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 
88  Node(void);
90  Node(NodeFlag nf, int i);
92 
94 
95 
96  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 
114  void first(Edge* p);
116  void last(Edge* p);
118  void inedge(Edge* p);
120  void index(int i);
122 
124 
125 
126  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 
145  VarNode(void);
147  VarNode(int i);
149 
151 
152 
153  Edge* get_match(BC bc) const;
155  bool matched(BC bc) const;
157 
159 
160 
161  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 
195  ValNode(void);
203  ValNode(int min, int max, int value, int kidx, int kshift, int count);
205 
207 
208 
209  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 
241  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 
303  Edge(void) {}
308  Edge(VarNode* x, ValNode* v);
310 
312 
313 
314  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 
347  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 
377  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 
443 
444 
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
1084  ViewArray<IntView>& x,
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  ValNode* rv = NULL;
1221  Edge* mub = vrn->get_match(UBC);
1222  if ((mub != NULL) && (v != mub->getVal()->val)) {
1223  mub->unmatch(UBC);
1224  re.push(vars[i]);
1225  }
1226 
1227  Edge* mlb = vrn->get_match(LBC);
1228  if (mlb != NULL) {
1229  ValNode* vln = mlb->getVal();
1230  if (v != vln->val) {
1231  mlb->unmatch(LBC);
1232  if (vln->incid_match(LBC) < vln->kmin())
1233  re.push(vln);
1234  }
1235  }
1236 
1237  for (Edge* e = vrn->first(); e != NULL; e = e->next()) {
1238  ValNode* vln = e->getVal();
1239  if (vln->val != v) {
1240  vrn->noe--;
1241  e->getVal()->noe--;
1242  e->del_edge();
1243  e->unlink();
1244  } else {
1245  rv = e->getVal();
1246  }
1247  }
1248  } else {
1249 
1250  // delete the edge
1251  ViewValues<IntView> xiter(x[i]);
1252  Edge* mub = vrn->get_match(UBC);
1253  Edge* mlb = vrn->get_match(LBC);
1254  Edge** p = vrn->adj();
1255  Edge* e = *p;
1256  do {
1257  // search the edge that has to be deleted
1258  while (e != NULL && (e->getVal()->val < xiter.val())) {
1259  // Skip edge
1260  e->getVal()->noe--;
1261  vrn->noe--;
1262  e->del_edge();
1263  e->unlink();
1264  e = e ->next();
1265  *p = e;
1266  }
1267 
1268  assert(xiter.val() == e->getVal()->val);
1269 
1270  // This edge must be kept
1271  e->free(UBC);
1272  e->free(LBC);
1273  ++xiter;
1274  p = e->next_ref();
1275  e = e->next();
1276  } while (xiter());
1277  *p = NULL;
1278  while (e) {
1279  e->getVar()->noe--;
1280  e->getVal()->noe--;
1281  e->del_edge();
1282  e->unlink();
1283  e = e->next();
1284  }
1285 
1286  if ((mub != NULL) && mub->deleted()) {
1287  mub->unmatch(UBC);
1288  re.push(vars[i]);
1289  }
1290 
1291  //lower bound matching can be zero
1292  if ((mlb != NULL) && mlb->deleted()) {
1293  ValNode* vln = mlb->getVal();
1294  mlb->unmatch(LBC);
1295  if (vln->incid_match(LBC) < vln->kmin())
1296  re.push(vln);
1297  }
1298  }
1299  }
1300  vars[i]->index(i);
1301  }
1302 
1303  for (int i = n_val; i--; ) {
1304  if ((k[i].min() > vals[i]->noe) && (k[i].counter() == 0))
1305  return ES_FAILED;
1306  vals[i]->index(n_var + i);
1307  }
1308 
1309  // start repair
1310  while (!re.empty()) {
1311  Node* n = re.pop();
1312  if (!n->removed()) {
1313  if (!n->type()) {
1314  VarNode* vrn = static_cast<VarNode*>(n);
1315  if (!vrn->matched(UBC) && !augmenting_path<UBC>(home,vrn))
1316  return ES_FAILED;
1317  } else {
1318  ValNode* vln = static_cast<ValNode*>(n);
1319  while (!vln->matched(LBC))
1320  if (!augmenting_path<LBC>(home,vln))
1321  return ES_FAILED;
1322  }
1323  }
1324  }
1325 
1326  return ES_OK;
1327  }
1328 
1329  template<class Card> template<BC bc>
1330  inline ExecStatus
1333  for (int i = n_var; i--; )
1334  if (vars[i]->noe == 1) {
1335  ValNode* v = vars[i]->first()->getVal();
1336  vars[i]->first()->free(bc);
1337  GECODE_ME_CHECK(x[i].eq(home, v->val));
1338  v->inc();
1339  }
1340 
1341  for (int i = n_val; i--; ) {
1342  ValNode* v = vals[i];
1343  if (Card::propagate && (k[i].counter() == 0))
1344  GECODE_ME_CHECK(k[i].lq(home, v->noe));
1345  if (v->noe > 0) {
1346  if (Card::propagate)
1347  GECODE_ME_CHECK(k[i].lq(home, v->noe));
1348 
1349  // If the maximum number of occurences of a value is reached
1350  // it cannot be consumed by another view
1351 
1352  if (v->kcount() == v->kmax()) {
1353  int vidx = v->kindex();
1354 
1355  k[i].counter(v->kcount());
1356 
1357  if (Card::propagate)
1358  GECODE_ME_CHECK(k[i].eq(home, k[i].counter()));
1359 
1360  bool delall = v->card_conflict() && (v->noe > v->kmax());
1361 
1362  for (Edge* e = v->last(); e != NULL; e = e->vprev()) {
1363  VarNode* vrn = e->getVar();
1364  if (vrn->noe == 1) {
1365  vrn->noe--;
1366  v->noe--;
1367  int vi= vrn->index();
1368 
1369  x.move_lst(vi);
1370  vars[vi] = vars[--n_var];
1371  vars[vi]->index(vi);
1372  n_node--;
1373  e->del_edge();
1374  e->unlink();
1375 
1376  } else if (delall) {
1377  GECODE_ME_CHECK(x[vrn->index()].nq(home, v->val));
1378  vrn->noe--;
1379  v->noe--;
1380  e->del_edge();
1381  e->unlink();
1382  }
1383  }
1384  v->cap(UBC,0);
1385  v->cap(LBC,0);
1386  v->maxlow(0);
1387  if (sum_min >= k[vidx].min())
1388  sum_min -= k[vidx].min();
1389  if (sum_max >= k[vidx].max())
1390  sum_max -= k[vidx].max();
1391 
1392  } else if (v->kcount() > 0) {
1393  v->kcount(0);
1394  }
1395  }
1396  }
1397  for (int i = n_var; i--; )
1398  vars[i]->index(i);
1399 
1400  for (int i = n_val; i--; ) {
1401  if (vals[i]->noe == 0) {
1402  vals[i]->cap(UBC,0);
1403  vals[i]->cap(LBC,0);
1404  vals[i]->maxlow(0);
1405  }
1406  vals[i]->index(n_var + i);
1407  }
1408 
1409  for (int i = n_var; i--; )
1410  if (vars[i]->noe > 1)
1411  for (Edge* e = vars[i]->first(); e != NULL; e = e->next())
1412  if (!e->matched(bc) && !e->used(bc)) {
1413  GECODE_ME_CHECK(x[i].nq(home, e->getVal()->val));
1414  } else {
1415  e->free(bc);
1416  }
1417 
1418  return ES_OK;
1419  }
1420 
1421  template<class Card> template<BC bc>
1422  forceinline bool
1424  Region r(home);
1425  NodeStack ns(r,n_node);
1426  BitSet visited(r,static_cast<unsigned int>(n_node));
1427  Edge** start = r.alloc<Edge*>(n_node);
1428 
1429  // keep track of the nodes that have already been visited
1430  Node* sn = v;
1431 
1432  // mark the start partition
1433  bool sp = sn->type();
1434 
1435  // nodes in sp only follow free edges
1436  // nodes in V - sp only follow matched edges
1437 
1438  for (int i = n_node; i--; )
1439  if (i >= n_var) {
1440  vals[i-n_var]->inedge(NULL);
1441  start[i] = vals[i-n_var]->first();
1442  } else {
1443  vars[i]->inedge(NULL);
1444  start[i] = vars[i]->first();
1445  }
1446 
1447  v->inedge(NULL);
1448  ns.push(v);
1449  visited.set(static_cast<unsigned int>(v->index()));
1450  while (!ns.empty()) {
1451  Node* v = ns.top();
1452  Edge* e = NULL;
1453  if (v->type() == sp) {
1454  e = start[v->index()];
1455  while ((e != NULL) && e->matched(bc))
1456  e = e->next(v->type());
1457  } else {
1458  e = start[v->index()];
1459  while ((e != NULL) && !e->matched(bc))
1460  e = e->next(v->type());
1461  start[v->index()] = e;
1462  }
1463  if (e != NULL) {
1464  start[v->index()] = e->next(v->type());
1465  Node* w = e->getMate(v->type());
1466  if (!visited.get(static_cast<unsigned int>(w->index()))) {
1467  // unexplored path
1468  bool m = w->type() ?
1469  static_cast<ValNode*>(w)->matched(bc) :
1470  static_cast<VarNode*>(w)->matched(bc);
1471  if (!m && w->type() != sp) {
1472  if (v->inedge() != NULL) {
1473  // augmenting path of length l > 1
1474  e->match(bc);
1475  break;
1476  } else {
1477  // augmenting path of length l = 1
1478  e->match(bc);
1479  ns.pop();
1480  return true;
1481  }
1482  } else {
1483  w->inedge(e);
1484  visited.set(static_cast<unsigned int>(w->index()));
1485  // find matching edge m incident with w
1486  ns.push(w);
1487  }
1488  }
1489  } else {
1490  // tried all outgoing edges without finding an augmenting path
1491  ns.pop();
1492  }
1493  }
1494 
1495  bool pathfound = !ns.empty();
1496 
1497  while (!ns.empty()) {
1498  Node* t = ns.pop();
1499  if (t != sn) {
1500  Edge* in = t->inedge();
1501  if (t->type() != sp) {
1502  in->match(bc);
1503  } else if (!sp) {
1504  in->unmatch(bc,!sp);
1505  } else {
1506  in->unmatch(bc);
1507  }
1508  }
1509  }
1510  return pathfound;
1511  }
1512 
1513  template<class Card> template<BC bc>
1514  inline ExecStatus
1516  int card_match = 0;
1517  // find an intial matching in O(n*d)
1518  // greedy algorithm
1519  for (int i = n_val; i--; )
1520  for (Edge* e = vals[i]->first(); e != NULL ; e = e->vnext())
1521  if (!e->getVar()->matched(bc) && !vals[i]->matched(bc)) {
1522  e->match(bc); card_match++;
1523  }
1524 
1525  Region r(home);
1526  switch (bc) {
1527  case LBC:
1528  if (card_match < sum_min) {
1530 
1531  // find failed nodes
1532  for (int i = n_val; i--; )
1533  if (!vals[i]->matched(LBC))
1534  free.push(vals[i]);
1535 
1536  while (!free.empty()) {
1537  ValNode* v = free.pop();
1538  while (!v->matched(LBC))
1539  if (augmenting_path<LBC>(home,v))
1540  card_match++;
1541  else
1542  break;
1543  }
1544 
1545  return (card_match >= sum_min) ? ES_OK : ES_FAILED;
1546  } else {
1547  return ES_OK;
1548  }
1549  break;
1550  case UBC:
1551  if (card_match < n_var) {
1553 
1554  // find failed nodes
1555  for (int i = n_var; i--; )
1556  if (!vars[i]->matched(UBC))
1557  free.push(vars[i]);
1558 
1559  while (!free.empty()) {
1560  VarNode* v = free.pop();
1561  if (!v->matched(UBC) && augmenting_path<UBC>(home,v))
1562  card_match++;
1563  }
1564 
1565  return (card_match >= n_var) ? ES_OK : ES_FAILED;
1566  } else {
1567  return ES_OK;
1568  }
1569  break;
1570  default: GECODE_NEVER;
1571  }
1572  GECODE_NEVER;
1573  return ES_FAILED;
1574  }
1575 
1576 
1577  template<class Card> template<BC bc>
1578  forceinline void
1580  Region r(home);
1581  NodeStack ns(r,n_node);
1582  BitSet visited(r,static_cast<unsigned int>(n_node));
1583 
1584  switch (bc) {
1585  case LBC:
1586  // after a maximum matching on the value nodes there still can be
1587  // free value nodes, hence we have to consider ALL nodes whether
1588  // they are the starting point of an even alternating path in G
1589  for (int i = n_var; i--; )
1590  if (!vars[i]->matched(LBC)) {
1591  ns.push(vars[i]);
1592  visited.set(static_cast<unsigned int>(vars[i]->index()));
1593  }
1594  for (int i = n_val; i--; )
1595  if (!vals[i]->matched(LBC)) {
1596  ns.push(vals[i]);
1597  visited.set(static_cast<unsigned int>(vals[i]->index()));
1598  }
1599  break;
1600  case UBC:
1601  // clearly, after a maximum matching on the x variables
1602  // corresponding to a set cover on x there are NO free var nodes
1603  for (int i = n_val; i--; )
1604  if (!vals[i]->matched(UBC)) {
1605  ns.push(vals[i]);
1606  visited.set(static_cast<unsigned int>(vals[i]->index()));
1607  }
1608  break;
1609  default: GECODE_NEVER;
1610  }
1611 
1612  while (!ns.empty()) {
1613  Node* node = ns.pop();
1614  if (node->type()) {
1615  // ValNode
1616  ValNode* vln = static_cast<ValNode*>(node);
1617 
1618  for (Edge* cur = vln->first(); cur != NULL; cur = cur->vnext()) {
1619  VarNode* mate = cur->getVar();
1620  switch (bc) {
1621  case LBC:
1622  if (cur->matched(LBC)) {
1623  // mark the edge
1624  cur->use(LBC);
1625  if (!visited.get(static_cast<unsigned int>(mate->index()))) {
1626  ns.push(mate);
1627  visited.set(static_cast<unsigned int>(mate->index()));
1628  }
1629  }
1630  break;
1631  case UBC:
1632  if (!cur->matched(UBC)) {
1633  // mark the edge
1634  cur->use(UBC);
1635  if (!visited.get(static_cast<unsigned int>(mate->index()))) {
1636  ns.push(mate);
1637  visited.set(static_cast<unsigned int>(mate->index()));
1638  }
1639  }
1640  break;
1641  default: GECODE_NEVER;
1642  }
1643  }
1644 
1645  } else {
1646  // VarNode
1647  VarNode* vrn = static_cast<VarNode*>(node);
1648 
1649  switch (bc) {
1650  case LBC:
1651  // after LBC-matching we can follow every unmatched edge
1652  for (Edge* cur = vrn->first(); cur != NULL; cur = cur->next()) {
1653  ValNode* mate = cur->getVal();
1654  if (!cur->matched(LBC)) {
1655  cur->use(LBC);
1656  if (!visited.get(static_cast<unsigned int>(mate->index()))) {
1657  ns.push(mate);
1658  visited.set(static_cast<unsigned int>(mate->index()));
1659  }
1660  }
1661  }
1662  break;
1663  case UBC:
1664  // after UBC-matching we can only follow a matched edge
1665  {
1666  Edge* cur = vrn->get_match(UBC);
1667  if (cur != NULL) {
1668  cur->use(UBC);
1669  ValNode* mate = cur->getVal();
1670  if (!visited.get(static_cast<unsigned int>(mate->index()))) {
1671  ns.push(mate);
1672  visited.set(static_cast<unsigned int>(mate->index()));
1673  }
1674  }
1675  }
1676  break;
1677  default: GECODE_NEVER;
1678  }
1679  }
1680  }
1681  }
1682 
1683  template<class Card> template<BC bc>
1684  void
1686  BitSet& inscc, BitSet& in_unfinished, int dfsnum[],
1687  NodeStack& roots, NodeStack& unfinished,
1688  int& count) {
1689  count++;
1690  int v_index = v->index();
1691  dfsnum[v_index] = count;
1692  inscc.set(static_cast<unsigned int>(v_index));
1693  in_unfinished.set(static_cast<unsigned int>(v_index));
1694 
1695  unfinished.push(v);
1696  roots.push(v);
1697  for (Edge* e = v->first(); e != NULL; e = e->next(v->type())) {
1698  bool m;
1699  switch (bc) {
1700  case LBC:
1701  m = v->type() ? e->matched(LBC) : !e->matched(LBC);
1702  break;
1703  case UBC:
1704  m = v->type() ? !e->matched(UBC) : e->matched(UBC);
1705  break;
1706  default: GECODE_NEVER;
1707  }
1708  if (m) {
1709  Node* w = e->getMate(v->type());
1710  int w_index = w->index();
1711 
1712  assert(w_index < n_node);
1713  if (!inscc.get(static_cast<unsigned int>(w_index))) {
1714  // w is an uncompleted scc
1715  w->inedge(e);
1716  dfs<bc>(w, inscc, in_unfinished, dfsnum,
1717  roots, unfinished, count);
1718  } else if (in_unfinished.get(static_cast<unsigned int>(w_index))) {
1719  // even alternating cycle found mark the edge closing the cycle,
1720  // completing the scc
1721  e->use(bc);
1722  // if w belongs to an scc we detected earlier
1723  // merge components
1724  assert(roots.top()->index() < n_node);
1725  while (dfsnum[roots.top()->index()] > dfsnum[w_index]) {
1726  roots.pop();
1727  }
1728  }
1729  }
1730  }
1731 
1732  if (v == roots.top()) {
1733  while (v != unfinished.top()) {
1734  // w belongs to the scc with root v
1735  Node* w = unfinished.top();
1736  w->inedge()->use(bc);
1737  in_unfinished.clear(static_cast<unsigned int>(w->index()));
1738  unfinished.pop();
1739  }
1740  assert(v == unfinished.top());
1741  in_unfinished.clear(static_cast<unsigned int>(v_index));
1742  roots.pop();
1743  unfinished.pop();
1744  }
1745  }
1746 
1747  template<class Card> template<BC bc>
1748  forceinline void
1750  Region r(home);
1751  BitSet inscc(r,static_cast<unsigned int>(n_node));
1752  BitSet in_unfinished(r,static_cast<unsigned int>(n_node));
1753  int* dfsnum = r.alloc<int>(n_node);
1754 
1755  for (int i = n_node; i--; )
1756  dfsnum[i]=0;
1757 
1758  int count = 0;
1759  NodeStack roots(r,n_node);
1760  NodeStack unfinished(r,n_node);
1761 
1762  for (int i = n_var; i--; )
1763  dfs<bc>(vars[i], inscc, in_unfinished, dfsnum,
1764  roots, unfinished, count);
1765  }
1766 
1767  template<class Card>
1768  forceinline void*
1769  VarValGraph<Card>::operator new(size_t t, Space& home) {
1770  return home.ralloc(t);
1771  }
1772 
1773 }}}
1774 
1775 // STATISTICS: int-prop
1776 
1777