Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
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$ by $Author$
17  * $Revision$
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 
444  ExecStatus min_require(Space& home,
447 
458  template<BC>
459  ExecStatus narrow(Space& home,
461 
468  template<BC>
469  ExecStatus maximum_matching(void);
470 
472  template<BC>
473  void free_alternating_paths(void);
475  template<BC>
476  void strongly_connected_components(void);
482  template<BC>
483  bool augmenting_path(Node*);
484 
485  protected:
492  template<BC>
493  void dfs(Node*, BitSet&, BitSet&, int[],
494  NodeStack&, NodeStack&, int&);
495 
497  public:
499  void* operator new(size_t t, Space& home);
501  void operator delete(void*, Space&) {}
502  };
503 
504 
505 
506  /*
507  * Nodes
508  *
509  */
511  Node::Node(void) {}
514  : e(NULL), fst(NULL), lst(NULL), ie(NULL), idx(i),
515  nf(static_cast<unsigned char>(nf0)), noe(0) {}
516 
517  forceinline Edge**
518  Node::adj(void) {
519  return &e;
520  }
522  Node::first(void) const {
523  return fst;
524  }
526  Node::last(void) const {
527  return lst;
528  }
529  forceinline void
531  fst = p;
532  }
533  forceinline void
535  lst = p;
536  }
537  forceinline bool
538  Node::type(void) const {
539  return (nf & NF_VAL) != 0;
540  }
542  Node::inedge(void) const {
543  return ie;
544  }
545  forceinline void
547  ie = p;
548  }
549  forceinline bool
550  Node::removed(void) const {
551  return noe == 0;
552  }
553  forceinline void
554  Node::index(int i) {
555  idx = i;
556  }
557  forceinline int
558  Node::index(void) const {
559  return idx;
560  }
561 
562  forceinline void*
563  Node::operator new(size_t s, Space& home) {
564  return home.ralloc(s);
565  }
566 
567 
568 
569  /*
570  * Variable nodes
571  *
572  */
575 
578  Node(NF_NONE,x), ubm(NULL), lbm(NULL) {}
579 
580  forceinline bool
581  VarNode::matched(BC bc) const {
582  if (bc == UBC)
583  return (nf & NF_M_UBC) != 0;
584  else
585  return (nf & NF_M_LBC) != 0;
586  }
587 
588  forceinline void
590  if (bc == UBC)
591  nf |= NF_M_UBC;
592  else
593  nf |= NF_M_LBC;
594  }
595 
596  forceinline void
598  if (bc == UBC)
599  ubm = p;
600  else
601  lbm = p;
602  }
603 
604  forceinline void
606  if (bc == UBC) {
607  nf &= ~NF_M_UBC; ubm = NULL;
608  } else {
609  nf &= ~NF_M_LBC; lbm = NULL;
610  }
611  }
612 
614  VarNode::get_match(BC bc) const {
615  if (bc == UBC)
616  return ubm;
617  else
618  return lbm;
619  }
620 
621 
622 
623 
624  /*
625  * Value nodes
626  *
627  */
630 
632  ValNode::ValNode(int min, int max, int value,
633  int kidx, int kshift, int count) :
634  Node(NF_VAL,kshift), _klb(min), _kub(max), _kidx(kidx), _kcount(count),
635  noc(0),
636  lb(min), ublow(max), ub(max),
637  val(value) {}
638 
639  forceinline void
641  assert(i >= lb);
642  ublow = i;
643  }
644 
645  forceinline int
646  ValNode::maxlow(void) const {
647  if (_klb == _kub) {
648  assert(ublow == lb);
649  }
650  return ublow;
651  }
652 
653 
654  forceinline void
656  noc = c;
657  }
658 
659  forceinline void
661  noc--;
662  assert(noc >= 0);
663  }
664 
665  forceinline int
667  return noc;
668  }
669 
670  forceinline int
671  ValNode::cap(BC bc) const {
672  if (bc == UBC)
673  return ub;
674  else
675  return lb;
676  }
677  forceinline bool
678  ValNode::matched(BC bc) const {
679  return cap(bc) == 0;
680  }
681 
682  forceinline void
684  lb = _klb;
685  ublow = _kub;
686  ub = _kub;
687  noe = 0;
688  }
689 
690  forceinline int
691  ValNode::kbound(BC bc) const {
692  if (bc == UBC) {
693  return _kub;
694  } else {
695  return _klb;
696  }
697  }
698 
699  forceinline int
700  ValNode::kmax(void) const {
701  return _kub;
702  }
703 
704  forceinline int
705  ValNode::kmin(void) const {
706  return _klb;
707  }
708 
709  forceinline void
710  ValNode::kmin(int klb) {
711  _klb = klb;
712  }
713 
714  forceinline void
715  ValNode::kmax(int kub) {
716  _kub = kub;
717  }
718 
719 
720  forceinline void
722  if (bc == UBC) {
723  ub--;
724  } else {
725  lb--; ublow--;
726  }
727  }
728 
729  forceinline void
731  if (bc == UBC) {
732  ub++;
733  } else {
734  lb++; ublow++;
735  }
736  }
737 
738  forceinline void
740  dec(bc);
741  }
742 
743  forceinline void
745  inc(bc);
746  }
747 
748  forceinline void
749  ValNode::cap(BC bc, int c) {
750  if (bc == UBC)
751  ub = c;
752  else
753  lb = c;
754  }
755 
756  forceinline void
757  ValNode::inc(void) {
758  _kcount++;
759  }
760 
761  forceinline int
762  ValNode::kcount(void) const {
763  return _kcount;
764  }
765 
766  forceinline void
768  _kcount = c;
769  }
770 
771  forceinline void
773  _kidx = i;
774  }
775 
776  forceinline int
777  ValNode::kindex(void) const {
778  return _kidx;
779  }
780 
782  forceinline int
784  if (bc == LBC)
785  return _kub - ublow + _kcount;
786  else
787  return _kub - ub + _kcount;
788  }
789 
790 
791  forceinline bool
792  ValNode::sink(void) const {
793  // there are only incoming edges
794  // in case of the UBC-matching
795  return _kub - ub == noe;
796  }
797 
798  forceinline bool
799  ValNode::source(void) const {
800  // there are only incoming edges
801  // in case of the UBC-matching
802  return _klb - lb == noe;
803  }
804 
805 
806 
807  /*
808  * Edges
809  *
810  */
811  forceinline void
812  Edge::unlink(void) {
813  // unlink from variable side
814  Edge* p = prev_edge;
815  Edge* n = next_edge;
816 
817  if (p != NULL)
818  *p->next_ref() = n;
819  if (n != NULL)
820  *n->prev_ref() = p;
821 
822  if (this == x->first()) {
823  Edge** ref = x->adj();
824  *ref = n;
825  x->first(n);
826  }
827 
828  if (this == x->last())
829  x->last(p);
830 
831  // unlink from value side
832  Edge* pv = prev_vedge;
833  Edge* nv = next_vedge;
834 
835  if (pv != NULL)
836  *pv->vnext_ref() = nv;
837  if (nv != NULL)
838  *nv->vprev_ref() = pv;
839  if (this == v->first()) {
840  Edge** ref = v->adj();
841  *ref = nv;
842  v->first(nv);
843  }
844  if (this == v->last())
845  v->last(pv);
846  }
847 
850  x(var), v(val),
851  next_edge(NULL), prev_edge(NULL),
852  next_vedge(NULL), prev_vedge(NULL), ef(EF_NONE) {}
853 
854  forceinline void
855  Edge::use(BC bc) {
856  if (bc == UBC)
857  ef |= EF_MRKUB;
858  else
859  ef |= EF_MRKLB;
860  }
861  forceinline void
863  if (bc == UBC)
864  ef &= ~EF_MRKUB;
865  else
866  ef &= ~EF_MRKLB;
867  }
868  forceinline bool
869  Edge::used(BC bc) const {
870  if (bc == UBC)
871  return (ef & EF_MRKUB) != 0;
872  else
873  return (ef & EF_MRKLB) != 0;
874  }
876  Edge::next(void) const {
877  return next_edge;
878  }
880  Edge::next(bool t) const {
881  if (t) {
882  return next_vedge;
883  } else {
884  return next_edge;
885  }
886  }
887 
889  Edge::vnext(void) const {
890  return next_vedge;
891  }
892  forceinline Edge**
894  return &next_vedge;
895  }
897  Edge::prev(void) const {
898  return prev_edge;
899  }
900  forceinline Edge**
902  return &prev_edge;
903  }
905  Edge::vprev(void) const {
906  return prev_vedge;
907  }
908  forceinline Edge**
910  return &prev_vedge;
911  }
912  forceinline Edge**
914  return &next_edge;
915  }
917  Edge::getVar(void) const {
918  assert(x != NULL);
919  return x;
920  }
921 
923  Edge::getVal(void) const {
924  assert(v != NULL);
925  return v;
926  }
927 
929  Edge::getMate(bool type) const {
930  if (type)
931  return x;
932  else
933  return v;
934  }
935 
936  forceinline void
938  if (bc == UBC)
939  ef &= ~EF_UM;
940  else
941  ef &= ~EF_LM;
942  x->unmatch(bc); v->unmatch(bc);
943  }
944 
945  forceinline void
946  Edge::unmatch(BC bc, bool node) {
947  if (bc == UBC)
948  ef &= ~EF_UM;
949  else
950  ef &= ~EF_LM;
951  if (node)
952  v->unmatch(bc);
953  else
954  x->unmatch(bc);
955  }
956 
957  forceinline void
959  free(bc); unmatch(bc);
960  }
961 
962  forceinline void
964  if (bc == UBC)
965  ef |= EF_UM;
966  else
967  ef |= EF_LM;
968  x->match(bc);
969  x->set_match(bc,this);
970  v->match(bc);
971  }
972 
973  forceinline bool
974  Edge::matched(BC bc) const {
975  if (bc == UBC)
976  return (ef & EF_UM) != 0;
977  else
978  return (ef & EF_LM) != 0;
979  }
980 
981  forceinline void
983  ef |= EF_DEL;
984  }
985 
986  forceinline void
988  ef &= ~EF_DEL;
989  }
990 
991 
992  forceinline bool
993  Edge::deleted(void) const {
994  return (ef & EF_DEL) != 0;
995  }
996 
997  forceinline void*
998  Edge::operator new(size_t s, Space& home) {
999  return home.ralloc(s);
1000  }
1001 
1002 
1003  /*
1004  * Variable value graph
1005  *
1006  */
1007  template<class Card>
1010  int smin, int smax)
1011  : n_var(x.size()),
1012  n_val(k.size()),
1013  n_node(n_var + n_val),
1014  sum_min(smin),
1015  sum_max(smax) {
1016 
1017  unsigned int noe = 0;
1018  for (int i=x.size(); i--; )
1019  noe += x[i].size();
1020 
1021  vars = home.alloc<VarNode*>(n_var);
1022  vals = home.alloc<ValNode*>(n_val);
1023 
1024  for (int i = n_val; i--; ) {
1025  int kmi = k[i].min();
1026  int kma = k[i].max();
1027  int kc = k[i].counter();
1028  if (kc != kma) {
1029  if (kmi >= kc) {
1030  kmi -=kc;
1031  assert(kmi >=0);
1032  } else {
1033  kmi = 0;
1034  }
1035  kma -= kc;
1036  assert (kma > 0);
1037  vals[i] = new (home)
1038  ValNode(kmi, kma, k[i].card(), i, i + n_var, kc);
1039  } else {
1040  vals[i] = new (home)
1041  ValNode(0, 0, k[i].card(), i, i + n_var, kc);
1042  }
1043  }
1044 
1045  for (int i = n_var; i--; ) {
1046  vars[i] = new (home) VarNode(i);
1047  // get the space for the edges of the varnode
1048  Edge** xadjacent = vars[i]->adj();
1049 
1050  int j = 0;
1051  for (ViewValues<IntView> xi(x[i]); xi(); ++xi) {
1052  // get the correct index for the value
1053  while(vals[j]->val < xi.val())
1054  j++;
1055  *xadjacent = new (home) Edge(vars[i],vals[j]);
1056  vars[i]->noe++;
1057  if (vars[i]->first() == NULL)
1058  vars[i]->first(*xadjacent);
1059  Edge* oldprev = vars[i]->last();
1060  vars[i]->last(*xadjacent);
1061  *vars[i]->last()->prev_ref() = oldprev;
1062 
1063  if (vals[j]->first() == NULL) {
1064  vals[j]->first(*xadjacent);
1065  vals[j]->last(*xadjacent);
1066  } else {
1067  Edge* old = vals[j]->first();
1068  vals[j]->first(*xadjacent);
1069  *vals[j]->first()->vnext_ref() = old;
1070  *old->vprev_ref() = vals[j]->first();
1071  }
1072  vals[j]->noe++;
1073  xadjacent = (*xadjacent)->next_ref();
1074  }
1075  *xadjacent = NULL;
1076  }
1077  }
1078 
1079 
1080  template<class Card>
1081  inline ExecStatus
1084  ViewArray<Card>& k) {
1085  for (int i = n_val; i--; ) {
1086  ValNode* vln = vals[i];
1087  if (vln->noe > 0) {
1088  if (k[i].min() == vln->noe) {
1089  // all variable nodes reachable from vln should be equal to vln->val
1090  for (Edge* e = vln->first(); e != NULL; e = e->vnext()) {
1091  VarNode* vrn = e->getVar();
1092  for (Edge* f = vrn->first(); f != NULL; f = f->next())
1093  if (f != e) {
1094  ValNode* w = f->getVal();
1095  w->noe--;
1096  vrn->noe--;
1097  f->del_edge();
1098  f->unlink();
1099  }
1100  assert(vrn->noe == 1);
1101 
1102  int vi = vrn->index();
1103  GECODE_ME_CHECK(x[vi].eq(home, vln->val));
1104 
1105  vars[vi] = vars[--n_var];
1106  vars[vi]->index(vi);
1107  x.move_lst(vi);
1108  n_node--;
1109  vln->noe--;
1110  }
1111 
1112 
1113  int vidx = vln->kindex();
1114  if (Card::propagate)
1115  GECODE_ME_CHECK(k[vidx].eq(home, k[vidx].min()));
1116 
1117  k[vidx].counter(k[vidx].min());
1118 
1119  vln->cap(UBC,0);
1120  vln->cap(LBC,0);
1121  vln->maxlow(0);
1122 
1123  if (sum_min >= k[vidx].min())
1124  sum_min -= k[vidx].min();
1125  if (sum_max >= k[vidx].max())
1126  sum_max -= k[vidx].max();
1127  }
1128  } else {
1129  vals[i]->cap(UBC,0);
1130  vals[i]->cap(LBC,0);
1131  vals[i]->maxlow(0);
1132  vals[i]->kmax(0);
1133  vals[i]->kmin(0);
1134  }
1135 
1136  if (Card::propagate && (k[i].counter() == 0))
1137  GECODE_ME_CHECK(k[i].lq(home, vals[i]->noe));
1138  }
1139 
1140  for (int i = n_val; i--; )
1141  vals[i]->index(n_var + i);
1142 
1143  return ES_OK;
1144  }
1145 
1146  template<class Card> template<BC bc>
1147  forceinline bool
1149  Region r;
1150  NodeStack ns(r,n_node);
1151  BitSet visited(r,static_cast<unsigned int>(n_node));
1152  Edge** start = r.alloc<Edge*>(n_node);
1153 
1154  // keep track of the nodes that have already been visited
1155  Node* sn = v;
1156 
1157  // mark the start partition
1158  bool sp = sn->type();
1159 
1160  // nodes in sp only follow free edges
1161  // nodes in V - sp only follow matched edges
1162 
1163  for (int i = n_node; i--; )
1164  if (i >= n_var) {
1165  vals[i-n_var]->inedge(NULL);
1166  start[i] = vals[i-n_var]->first();
1167  } else {
1168  vars[i]->inedge(NULL);
1169  start[i] = vars[i]->first();
1170  }
1171 
1172  v->inedge(NULL);
1173  ns.push(v);
1174  visited.set(static_cast<unsigned int>(v->index()));
1175  while (!ns.empty()) {
1176  Node* vv = ns.top();
1177  Edge* e = NULL;
1178  if (vv->type() == sp) {
1179  e = start[vv->index()];
1180  while ((e != NULL) && e->matched(bc))
1181  e = e->next(vv->type());
1182  } else {
1183  e = start[vv->index()];
1184  while ((e != NULL) && !e->matched(bc))
1185  e = e->next(vv->type());
1186  start[vv->index()] = e;
1187  }
1188  if (e != NULL) {
1189  start[vv->index()] = e->next(vv->type());
1190  Node* w = e->getMate(vv->type());
1191  if (!visited.get(static_cast<unsigned int>(w->index()))) {
1192  // unexplored path
1193  bool m = w->type() ?
1194  static_cast<ValNode*>(w)->matched(bc) :
1195  static_cast<VarNode*>(w)->matched(bc);
1196  if (!m && w->type() != sp) {
1197  if (vv->inedge() != NULL) {
1198  // augmenting path of length l > 1
1199  e->match(bc);
1200  break;
1201  } else {
1202  // augmenting path of length l = 1
1203  e->match(bc);
1204  ns.pop();
1205  return true;
1206  }
1207  } else {
1208  w->inedge(e);
1209  visited.set(static_cast<unsigned int>(w->index()));
1210  // find matching edge m incident with w
1211  ns.push(w);
1212  }
1213  }
1214  } else {
1215  // tried all outgoing edges without finding an augmenting path
1216  ns.pop();
1217  }
1218  }
1219 
1220  bool pathfound = !ns.empty();
1221 
1222  while (!ns.empty()) {
1223  Node* t = ns.pop();
1224  if (t != sn) {
1225  Edge* in = t->inedge();
1226  if (t->type() != sp) {
1227  in->match(bc);
1228  } else if (!sp) {
1229  in->unmatch(bc,!sp);
1230  } else {
1231  in->unmatch(bc);
1232  }
1233  }
1234  }
1235  return pathfound;
1236  }
1237 
1238 
1239  template<class Card>
1240  inline ExecStatus
1242  Region r;
1243  // A node can be pushed twice (once when checking cardinality and later again)
1244  NodeStack re(r,2*n_node);
1245 
1246  // synchronize cardinality variables
1247  if (Card::propagate) {
1248  for (int i = n_val; i--; ) {
1249  ValNode* v = vals[i];
1250  int inc_ubc = v->incid_match(UBC);
1251  int inc_lbc = v->incid_match(LBC);
1252  if (v->noe == 0) {
1253  inc_ubc = 0;
1254  inc_lbc = 0;
1255  }
1256  int rm = v->kmax() - k[i].max();
1257  // the cardinality bounds have been modified
1258  if ((k[i].max() < v->kmax()) || (k[i].min() > v->kmin())) {
1259  if ((k[i].max() != k[i].counter()) || (k[i].max() == 0)) {
1260  // update the bounds
1261  v->kmax(k[i].max());
1262  v->kmin(k[i].min());
1263 
1264  //everything is fine
1265  if (inc_ubc <= k[i].max()) {
1266  // adjust capacities
1267  v->cap(UBC, k[i].max() - inc_ubc);
1268  v->maxlow(k[i].max() - inc_lbc);
1269  if (v->kmin() == v->kmax())
1270  v->cap(LBC, k[i].max() - inc_lbc);
1271  } else {
1272  // set cap to max and resolve conflicts on view side
1273  // set to full capacity for later rescheduling
1274  if (v->cap(UBC))
1275  v->cap(UBC,k[i].max());
1276  v->maxlow(k[i].max() - (inc_lbc));
1277  if (v->kmin() == v->kmax())
1278  v->cap(LBC,k[i].max() - (inc_lbc));
1279  v->card_conflict(rm);
1280  }
1281  }
1282  }
1283  if (inc_lbc < k[i].min() && v->noe > 0) {
1284  v->cap(LBC, k[i].min() - inc_lbc);
1285  re.push(v);
1286  }
1287  }
1288 
1289  for (int i = n_var; i--; ) {
1290  Edge* mub = vars[i]->get_match(UBC);
1291  if (mub != NULL) {
1292  ValNode* vu = mub->getVal();
1293  if ((vars[i]->noe != 1) && vu->card_conflict()) {
1294  vu->red_conflict();
1295  mub->unmatch(UBC,vars[i]->type());
1296  re.push(vars[i]);
1297  }
1298  }
1299  }
1300  }
1301 
1302  // go on with synchronization
1303  assert(x.size() == n_var);
1304  for (int i = n_var; i--; ) {
1305 
1306  VarNode* vrn = vars[i];
1307  if (static_cast<int>(x[i].size()) != vrn->noe) {
1308  // if the variable is already assigned
1309  if (x[i].assigned()) {
1310  int v = x[i].val();
1311  Edge* mub = vrn->get_match(UBC);
1312  if ((mub != NULL) && (v != mub->getVal()->val)) {
1313  mub->unmatch(UBC);
1314  re.push(vars[i]);
1315  }
1316 
1317  Edge* mlb = vrn->get_match(LBC);
1318  if (mlb != NULL) {
1319  ValNode* vln = mlb->getVal();
1320  if (v != vln->val) {
1321  mlb->unmatch(LBC);
1322  if (vln->incid_match(LBC) < vln->kmin())
1323  re.push(vln);
1324  }
1325  }
1326 
1327  for (Edge* e = vrn->first(); e != NULL; e = e->next()) {
1328  ValNode* vln = e->getVal();
1329  if (vln->val != v) {
1330  vrn->noe--;
1331  e->getVal()->noe--;
1332  e->del_edge();
1333  e->unlink();
1334  }
1335  }
1336  } else {
1337 
1338  // delete the edge
1339  ViewValues<IntView> xiter(x[i]);
1340  Edge* mub = vrn->get_match(UBC);
1341  Edge* mlb = vrn->get_match(LBC);
1342  Edge** p = vrn->adj();
1343  Edge* e = *p;
1344  do {
1345  // search the edge that has to be deleted
1346  while (e != NULL && (e->getVal()->val < xiter.val())) {
1347  // Skip edge
1348  e->getVal()->noe--;
1349  vrn->noe--;
1350  e->del_edge();
1351  e->unlink();
1352  e = e ->next();
1353  *p = e;
1354  }
1355 
1356  assert(xiter.val() == e->getVal()->val);
1357 
1358  // This edge must be kept
1359  e->free(UBC);
1360  e->free(LBC);
1361  ++xiter;
1362  p = e->next_ref();
1363  e = e->next();
1364  } while (xiter());
1365  *p = NULL;
1366  while (e) {
1367  e->getVar()->noe--;
1368  e->getVal()->noe--;
1369  e->del_edge();
1370  e->unlink();
1371  e = e->next();
1372  }
1373 
1374  if ((mub != NULL) && mub->deleted()) {
1375  mub->unmatch(UBC);
1376  re.push(vars[i]);
1377  }
1378 
1379  //lower bound matching can be zero
1380  if ((mlb != NULL) && mlb->deleted()) {
1381  ValNode* vln = mlb->getVal();
1382  mlb->unmatch(LBC);
1383  if (vln->incid_match(LBC) < vln->kmin())
1384  re.push(vln);
1385  }
1386  }
1387  }
1388  vars[i]->index(i);
1389  }
1390 
1391  for (int i = n_val; i--; ) {
1392  if ((k[i].min() > vals[i]->noe) && (k[i].counter() == 0))
1393  return ES_FAILED;
1394  vals[i]->index(n_var + i);
1395  }
1396 
1397  // start repair
1398  while (!re.empty()) {
1399  Node* n = re.pop();
1400  if (!n->removed()) {
1401  if (!n->type()) {
1402  VarNode* vrn = static_cast<VarNode*>(n);
1403  if (!vrn->matched(UBC) && !augmenting_path<UBC>(vrn))
1404  return ES_FAILED;
1405  } else {
1406  ValNode* vln = static_cast<ValNode*>(n);
1407  while (!vln->matched(LBC))
1408  if (!augmenting_path<LBC>(vln))
1409  return ES_FAILED;
1410  }
1411  }
1412  }
1413 
1414  return ES_OK;
1415  }
1416 
1417  template<class Card> template<BC bc>
1418  inline ExecStatus
1421  for (int i = n_var; i--; )
1422  if (vars[i]->noe == 1) {
1423  ValNode* v = vars[i]->first()->getVal();
1424  vars[i]->first()->free(bc);
1425  GECODE_ME_CHECK(x[i].eq(home, v->val));
1426  v->inc();
1427  }
1428 
1429  for (int i = n_val; i--; ) {
1430  ValNode* v = vals[i];
1431  if (Card::propagate && (k[i].counter() == 0))
1432  GECODE_ME_CHECK(k[i].lq(home, v->noe));
1433  if (v->noe > 0) {
1434  if (Card::propagate)
1435  GECODE_ME_CHECK(k[i].lq(home, v->noe));
1436 
1437  // If the maximum number of occurences of a value is reached
1438  // it cannot be consumed by another view
1439 
1440  if (v->kcount() == v->kmax()) {
1441  int vidx = v->kindex();
1442 
1443  k[i].counter(v->kcount());
1444 
1445  if (Card::propagate)
1446  GECODE_ME_CHECK(k[i].eq(home, k[i].counter()));
1447 
1448  bool delall = v->card_conflict() && (v->noe > v->kmax());
1449 
1450  for (Edge* e = v->last(); e != NULL; e = e->vprev()) {
1451  VarNode* vrn = e->getVar();
1452  if (vrn->noe == 1) {
1453  vrn->noe--;
1454  v->noe--;
1455  int vi= vrn->index();
1456 
1457  x.move_lst(vi);
1458  vars[vi] = vars[--n_var];
1459  vars[vi]->index(vi);
1460  n_node--;
1461  e->del_edge();
1462  e->unlink();
1463 
1464  } else if (delall) {
1465  GECODE_ME_CHECK(x[vrn->index()].nq(home, v->val));
1466  vrn->noe--;
1467  v->noe--;
1468  e->del_edge();
1469  e->unlink();
1470  }
1471  }
1472  v->cap(UBC,0);
1473  v->cap(LBC,0);
1474  v->maxlow(0);
1475  if (sum_min >= k[vidx].min())
1476  sum_min -= k[vidx].min();
1477  if (sum_max >= k[vidx].max())
1478  sum_max -= k[vidx].max();
1479 
1480  } else if (v->kcount() > 0) {
1481  v->kcount(0);
1482  }
1483  }
1484  }
1485  for (int i = n_var; i--; )
1486  vars[i]->index(i);
1487 
1488  for (int i = n_val; i--; ) {
1489  if (vals[i]->noe == 0) {
1490  vals[i]->cap(UBC,0);
1491  vals[i]->cap(LBC,0);
1492  vals[i]->maxlow(0);
1493  }
1494  vals[i]->index(n_var + i);
1495  }
1496 
1497  for (int i = n_var; i--; ) {
1498  if (vars[i]->noe > 1) {
1499  for (Edge* e = vars[i]->first(); e != NULL; e = e->next()) {
1500  if (!e->matched(bc) && !e->used(bc)) {
1501  GECODE_ME_CHECK(x[i].nq(home, e->getVal()->val));
1502  } else {
1503  e->free(bc);
1504  }
1505  }
1506  }
1507  }
1508  return ES_OK;
1509  }
1510 
1511  template<class Card> template<BC bc>
1512  inline ExecStatus
1514  int card_match = 0;
1515  // find an intial matching in O(n*d)
1516  // greedy algorithm
1517  for (int i = n_val; i--; )
1518  for (Edge* e = vals[i]->first(); e != NULL ; e = e->vnext())
1519  if (!e->getVar()->matched(bc) && !vals[i]->matched(bc)) {
1520  e->match(bc); card_match++;
1521  }
1522 
1523  Region r;
1524  switch (bc) {
1525  case LBC:
1526  if (card_match < sum_min) {
1528 
1529  // find failed nodes
1530  for (int i = n_val; i--; )
1531  if (!vals[i]->matched(LBC))
1532  free.push(vals[i]);
1533 
1534  while (!free.empty()) {
1535  ValNode* v = free.pop();
1536  while (!v->matched(LBC))
1537  if (augmenting_path<LBC>(v))
1538  card_match++;
1539  else
1540  break;
1541  }
1542 
1543  return (card_match >= sum_min) ? ES_OK : ES_FAILED;
1544  } else {
1545  return ES_OK;
1546  }
1547  break;
1548  case UBC:
1549  if (card_match < n_var) {
1551 
1552  // find failed nodes
1553  for (int i = n_var; i--; )
1554  if (!vars[i]->matched(UBC))
1555  free.push(vars[i]);
1556 
1557  while (!free.empty()) {
1558  VarNode* v = free.pop();
1559  if (!v->matched(UBC) && augmenting_path<UBC>(v))
1560  card_match++;
1561  }
1562 
1563  return (card_match >= n_var) ? ES_OK : ES_FAILED;
1564  } else {
1565  return ES_OK;
1566  }
1567  break;
1568  default: GECODE_NEVER;
1569  }
1570  GECODE_NEVER;
1571  return ES_FAILED;
1572  }
1573 
1574 
1575  template<class Card> template<BC bc>
1576  forceinline void
1578  Region r;
1579  NodeStack ns(r,n_node);
1580  BitSet visited(r,static_cast<unsigned int>(n_node));
1581 
1582  switch (bc) {
1583  case LBC:
1584  // after a maximum matching on the value nodes there still can be
1585  // free value nodes, hence we have to consider ALL nodes whether
1586  // they are the starting point of an even alternating path in G
1587  for (int i = n_var; i--; )
1588  if (!vars[i]->matched(LBC)) {
1589  ns.push(vars[i]);
1590  visited.set(static_cast<unsigned int>(vars[i]->index()));
1591  }
1592  for (int i = n_val; i--; )
1593  if (!vals[i]->matched(LBC)) {
1594  ns.push(vals[i]);
1595  visited.set(static_cast<unsigned int>(vals[i]->index()));
1596  }
1597  break;
1598  case UBC:
1599  // clearly, after a maximum matching on the x variables
1600  // corresponding to a set cover on x there are NO free var nodes
1601  for (int i = n_val; i--; )
1602  if (!vals[i]->matched(UBC)) {
1603  ns.push(vals[i]);
1604  visited.set(static_cast<unsigned int>(vals[i]->index()));
1605  }
1606  break;
1607  default: GECODE_NEVER;
1608  }
1609 
1610  while (!ns.empty()) {
1611  Node* node = ns.pop();
1612  if (node->type()) {
1613  // ValNode
1614  ValNode* vln = static_cast<ValNode*>(node);
1615 
1616  for (Edge* cur = vln->first(); cur != NULL; cur = cur->vnext()) {
1617  VarNode* mate = cur->getVar();
1618  switch (bc) {
1619  case LBC:
1620  if (cur->matched(LBC)) {
1621  // mark the edge
1622  cur->use(LBC);
1623  if (!visited.get(static_cast<unsigned int>(mate->index()))) {
1624  ns.push(mate);
1625  visited.set(static_cast<unsigned int>(mate->index()));
1626  }
1627  }
1628  break;
1629  case UBC:
1630  if (!cur->matched(UBC)) {
1631  // mark the edge
1632  cur->use(UBC);
1633  if (!visited.get(static_cast<unsigned int>(mate->index()))) {
1634  ns.push(mate);
1635  visited.set(static_cast<unsigned int>(mate->index()));
1636  }
1637  }
1638  break;
1639  default: GECODE_NEVER;
1640  }
1641  }
1642 
1643  } else {
1644  // VarNode
1645  VarNode* vrn = static_cast<VarNode*>(node);
1646 
1647  switch (bc) {
1648  case LBC:
1649  // after LBC-matching we can follow every unmatched edge
1650  for (Edge* cur = vrn->first(); cur != NULL; cur = cur->next()) {
1651  ValNode* mate = cur->getVal();
1652  if (!cur->matched(LBC)) {
1653  cur->use(LBC);
1654  if (!visited.get(static_cast<unsigned int>(mate->index()))) {
1655  ns.push(mate);
1656  visited.set(static_cast<unsigned int>(mate->index()));
1657  }
1658  }
1659  }
1660  break;
1661  case UBC:
1662  // after UBC-matching we can only follow a matched edge
1663  {
1664  Edge* cur = vrn->get_match(UBC);
1665  if (cur != NULL) {
1666  cur->use(UBC);
1667  ValNode* mate = cur->getVal();
1668  if (!visited.get(static_cast<unsigned int>(mate->index()))) {
1669  ns.push(mate);
1670  visited.set(static_cast<unsigned int>(mate->index()));
1671  }
1672  }
1673  }
1674  break;
1675  default: GECODE_NEVER;
1676  }
1677  }
1678  }
1679  }
1680 
1681  template<class Card> template<BC bc>
1682  void
1684  BitSet& inscc, BitSet& in_unfinished, int dfsnum[],
1685  NodeStack& roots, NodeStack& unfinished,
1686  int& count) {
1687  count++;
1688  int v_index = v->index();
1689  dfsnum[v_index] = count;
1690  inscc.set(static_cast<unsigned int>(v_index));
1691  in_unfinished.set(static_cast<unsigned int>(v_index));
1692 
1693  unfinished.push(v);
1694  roots.push(v);
1695  for (Edge* e = v->first(); e != NULL; e = e->next(v->type())) {
1696  bool m;
1697  switch (bc) {
1698  case LBC:
1699  m = v->type() ? e->matched(LBC) : !e->matched(LBC);
1700  break;
1701  case UBC:
1702  m = v->type() ? !e->matched(UBC) : e->matched(UBC);
1703  break;
1704  default: GECODE_NEVER;
1705  }
1706  if (m) {
1707  Node* w = e->getMate(v->type());
1708  int w_index = w->index();
1709 
1710  assert(w_index < n_node);
1711  if (!inscc.get(static_cast<unsigned int>(w_index))) {
1712  // w is an uncompleted scc
1713  w->inedge(e);
1714  dfs<bc>(w, inscc, in_unfinished, dfsnum,
1715  roots, unfinished, count);
1716  } else if (in_unfinished.get(static_cast<unsigned int>(w_index))) {
1717  // even alternating cycle found mark the edge closing the cycle,
1718  // completing the scc
1719  e->use(bc);
1720  // if w belongs to an scc we detected earlier
1721  // merge components
1722  assert(roots.top()->index() < n_node);
1723  while (dfsnum[roots.top()->index()] > dfsnum[w_index]) {
1724  roots.pop();
1725  }
1726  }
1727  }
1728  }
1729 
1730  if (v == roots.top()) {
1731  while (v != unfinished.top()) {
1732  // w belongs to the scc with root v
1733  Node* w = unfinished.top();
1734  w->inedge()->use(bc);
1735  in_unfinished.clear(static_cast<unsigned int>(w->index()));
1736  unfinished.pop();
1737  }
1738  assert(v == unfinished.top());
1739  in_unfinished.clear(static_cast<unsigned int>(v_index));
1740  roots.pop();
1741  unfinished.pop();
1742  }
1743  }
1744 
1745  template<class Card> template<BC bc>
1746  forceinline void
1748  Region r;
1749  BitSet inscc(r,static_cast<unsigned int>(n_node));
1750  BitSet in_unfinished(r,static_cast<unsigned int>(n_node));
1751  int* dfsnum = r.alloc<int>(n_node);
1752 
1753  for (int i = n_node; i--; )
1754  dfsnum[i]=0;
1755 
1756  int count = 0;
1757  NodeStack roots(r,n_node);
1758  NodeStack unfinished(r,n_node);
1759 
1760  for (int i = n_var; i--; )
1761  dfs<bc>(vars[i], inscc, in_unfinished, dfsnum,
1762  roots, unfinished, count);
1763  }
1764 
1765  template<class Card>
1766  forceinline void*
1767  VarValGraph<Card>::operator new(size_t t, Space& home) {
1768  return home.ralloc(t);
1769  }
1770 
1771 }}}
1772 
1773 // STATISTICS: int-prop
1774 
1775 
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.
ValNode(void)
Default constructor.
Definition: dom-sup.hpp:629
void unlink(void)
Unlink the edge from the linked list of edges.
Definition: dom-sup.hpp:812
NodeFlag
Flags for nodes.
Definition: dom-sup.hpp:69
NodeType t
Type of node.
Definition: bool-expr.cpp:234
Edge ** vnext_ref(void)
return the reference to the next edge incident on v
Definition: dom-sup.hpp:893
Node(void)
Default constructor.
Definition: dom-sup.hpp:511
Edge * vnext(void) const
return the pointer to the next edge incident on v
Definition: dom-sup.hpp:889
bool type(void) const
Return the type of the node (false for a variable node)
Definition: dom-sup.hpp:538
bool removed(void) const
check whether a node has been removed from the graph
Definition: dom-sup.hpp:550
bool sink(void) const
tests whether the node is a sink
Definition: dom-sup.hpp:792
int index(void) const
Get index of either variable or value.
Definition: dom-sup.hpp:558
void reset(BC bc)
Reset the edge (free the edge, and unmatch the edge)
Definition: dom-sup.hpp:958
int ub
Maximal capacity of the value node.
Definition: dom-sup.hpp:187
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
Definition: count.cpp:44
VarValGraph(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k, int smin, int smax)
Constructor for the variable-value-graph.
Definition: dom-sup.hpp:1008
VarNode(void)
Default constructor.
Definition: dom-sup.hpp:574
void clear(unsigned int i)
Clear bit i.
void strongly_connected_components(void)
Compute possible strongly connected components of the graph.
Definition: dom-sup.hpp:1747
Edge ** prev_ref(void)
return the reference to the previous edge incident on x
Definition: dom-sup.hpp:901
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:384
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:53
int lb
Minimal capacity of the value node.
Definition: dom-sup.hpp:183
bool empty(void) const
Test whether stack is empty.
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:2040
bool used(BC bc) const
Whether the edge is used.
Definition: dom-sup.hpp:869
Handle to region.
Definition: region.hpp:57
int _kcount
Stores the current number of occurences of the value.
Definition: dom-sup.hpp:179
Edge * first(void) const
Return pointer to the first incident edge.
Definition: dom-sup.hpp:522
int noc
Store numbre of conflicting matching edges.
Definition: dom-sup.hpp:181
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:880
int kcount(void) const
returns the current number of occurences of the value
Definition: dom-sup.hpp:762
Edge ** vprev_ref(void)
return the reference to the previous edge incident on v
Definition: dom-sup.hpp:909
#define forceinline
Definition: config.hpp:182
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:105
int kbound(BC bc) const
return minimal or maximal capacity
Definition: dom-sup.hpp:691
Computation spaces.
Definition: core.hpp:1668
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
int val(void) const
Return current value.
void unmatch(BC bc)
Unmatch the node.
Definition: dom-sup.hpp:605
unsigned char nf
Flags for node.
Definition: dom-sup.hpp:80
ValNode * getVal(void) const
return the pointer to the value node v of this edge
Definition: dom-sup.hpp:923
int ublow
Smallest maximal capacity of the value node.
Definition: dom-sup.hpp:185
T & top(void) const
Return element on top of stack.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2757
Gecode::FloatVal c(-8, 8)
void inc(void)
increases the value counter
Definition: dom-sup.hpp:757
ExecStatus sync(ViewArray< IntView > &x, ViewArray< Card > &k)
Synchronization of the graph.
Definition: dom-sup.hpp:1241
Edge * lst
Last edge.
Definition: dom-sup.hpp:63
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
int incid_match(BC bc) const
returns the number of incident matching edges on a value node
Definition: dom-sup.hpp:783
int kmax(void) const
return the maximal node capacity as stored in k
Definition: dom-sup.hpp:700
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:963
Execution has resulted in failure.
Definition: core.hpp:466
Node * getMate(bool t) const
return pointer to x if t = true otherwise return v
Definition: dom-sup.hpp:929
void match(BC bc)
Set node to matched.
Definition: dom-sup.hpp:589
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:937
int kindex(void) const
returns the index in cardinality array k
Definition: dom-sup.hpp:777
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:1148
Whether node is a value node.
Definition: dom-sup.hpp:73
void use(BC bc)
Update.
Definition: dom-sup.hpp:855
Base class for nodes in the variable-value-graph.
Definition: dom-sup.hpp:56
int card_conflict(void) const
Check whether the value node is conflicting.
Definition: dom-sup.hpp:666
VarNode * getVar(void) const
return the pointer to the variable node x of this edge
Definition: dom-sup.hpp:917
ExecStatus min_require(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k)
Check whether minimum requirements shrink variable domains.
Definition: dom-sup.hpp:1082
bool deleted(void) const
return whether the edge has been deleted from the graph
Definition: dom-sup.hpp:993
void set(unsigned int i)
Set bit i.
void insert_edge(void)
Insert the edge again.
Definition: dom-sup.hpp:987
void free(BC bc)
Mark the edge as unused.
Definition: dom-sup.hpp:862
void unmatch(BC bc)
unmatch the node
Definition: dom-sup.hpp:744
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:56
bool matched(BC bc) const
returns true if the node is matched in BC, false otherwise
Definition: dom-sup.hpp:678
T * dfs(T *s, const Search::Options &o)
Invoke depth-first search engine for subclass T of space s with options o.
Definition: dfs.hpp:77
void move_lst(int i)
Move view from position size()-1 to position i (truncate array by one)
Definition: array.hpp:1283
Class for edges in the variable-value-graph.
Definition: dom-sup.hpp:268
int kmin(void) const
return the minimal node capacity as stored in k
Definition: dom-sup.hpp:705
Edge ** next_ref(void)
return the reference to the next edge incident on x
Definition: dom-sup.hpp:913
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:769
const int v[7]
Definition: distinct.cpp:263
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:71
Edge ** adj(void)
Return reference to the incident edges.
Definition: dom-sup.hpp:518
Edge * inedge(void) const
Return pointer to the node&#39;s inedge.
Definition: dom-sup.hpp:542
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
ExecStatus narrow(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k)
Remove edges that do not belong to any maximal matching.
Definition: dom-sup.hpp:1419
void reset(void)
node reset to original capacity values
Definition: dom-sup.hpp:683
void red_conflict(void)
Reduce the conflict counter.
Definition: dom-sup.hpp:660
int maxlow(void) const
get max cap for LBC
Definition: dom-sup.hpp:646
Whether matched for UBC.
Definition: dom-sup.hpp:77
void del_edge(void)
Mark the edge as deleted during synchronization.
Definition: dom-sup.hpp:982
void dec(BC bc)
decrease the node-capacity
Definition: dom-sup.hpp:721
ExecStatus
Definition: core.hpp:464
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
Stack with fixed number of elements.
T pop(void)
Pop topmost element from stack and return it.
Post propagator for SetVar x
Definition: set.hh:769
Execution is okay.
Definition: core.hpp:468
bool source(void) const
tests whether the node is a source
Definition: dom-sup.hpp:799
Variable-value-graph used during propagation.
Definition: dom-sup.hpp:391
void free_alternating_paths(void)
Compute possible free alternating paths in the graph.
Definition: dom-sup.hpp:1577
Edge * prev(void) const
return the pointer to the previous edge incident on x
Definition: dom-sup.hpp:897
void match(BC bc)
match the node
Definition: dom-sup.hpp:739
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:1683
int cap(BC bc) const
return the the node-capacity
Definition: dom-sup.hpp:671
Edge * next(void) const
return the pointer to the next edge incident on x
Definition: dom-sup.hpp:876
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:655
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1203
Edge * ubm
Stores the matching edge on this node in the UBC.
Definition: dom-sup.hpp:138
bool matched(BC bc) const
return whether the edge is matched
Definition: dom-sup.hpp:974
#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:597
Edge * vprev(void) const
return the pointer to the previous edge incident on v
Definition: dom-sup.hpp:905
Edge * last(void) const
Return pointer to the last incident edge.
Definition: dom-sup.hpp:526
bool matched(BC bc) const
tests whether the node is matched or not
Definition: dom-sup.hpp:581
int val
Stores the value of the node.
Definition: dom-sup.hpp:190
Edge * get_match(BC bc) const
Return the matching edge on the node.
Definition: dom-sup.hpp:614
ExecStatus maximum_matching(void)
Compute a maximum matching M on the graph.
Definition: dom-sup.hpp:1513