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