this repo has no description
dekker.one
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
40namespace Gecode { namespace Int { namespace GCC {
41
42 /**
43 * \brief Bounds constraint (BC) type
44 *
45 * If BC = UBC, then we argue about the Upper Bounds Constraint
46 * else we use the functions for the Lower Bounds Constraint
47 */
48 enum BC {UBC = 1, LBC = 0};
49
50 class Edge;
51 /// Base class for nodes in the variable-value-graph
52 class Node {
53 protected:
54 /// Stores all incident edges on the node
55 Edge* e;
56 /// First edge
57 Edge* fst;
58 /// Last edge
59 Edge* lst;
60 /// Single incoming edge used for storing a path in the algorithms
61 Edge* ie;
62 /// Index
63 int idx;
64 /// Flags for nodes
65 enum NodeFlag {
66 /// No flags set
67 NF_NONE = 0,
68 /// Whether node is a value node
69 NF_VAL = 1 << 0,
70 /// Whether matched for LBC
71 NF_M_LBC = 1 << 1,
72 /// Whether matched for UBC
73 NF_M_UBC = 1 << 2
74 };
75 /// Flags for node
76 unsigned char nf;
77 public:
78 /// stores the number of incident edges on the node
79 int noe;
80
81 /// \name Constructors and initialization
82 //@{
83 /// Default constructor
84 Node(void);
85 /// Constructor for index \a i that sets type to \a t
86 Node(NodeFlag nf, int i);
87 //@}
88
89 /// \name Access
90 //@{
91 /// Return the type of the node (false for a variable node)
92 bool type(void) const;
93 /// Return reference to the incident edges
94 Edge** adj(void);
95 /// Return pointer to the first incident edge
96 Edge* first(void) const;
97 /// Return pointer to the last incident edge
98 Edge* last(void) const;
99 /// Return pointer to the node's inedge
100 Edge* inedge(void) const;
101 /// Get index of either variable or value
102 int index(void) const;
103 /// check whether a node has been removed from the graph
104 bool removed(void) const;
105 //@}
106
107 /// \name Update
108 //@{
109 /// Set the first edge pointer to \a p
110 void first(Edge* p);
111 /// Set the last edge pointer to \a p
112 void last(Edge* p);
113 /// Set the inedge pointer to \a p
114 void inedge(Edge* p);
115 /// Set index of either variable or value
116 void index(int i);
117 //@}
118
119 /// \name Memory management
120 //@{
121 /// Allocate memory from space
122 static void* operator new(size_t s, Space& home);
123 /// Free memory (unused)
124 static void operator delete(void*, Space&) {};
125 /// Needed for exceptions
126 static void operator delete(void*) {};
127 //@}
128 };
129
130 /// %Variable node
131 class VarNode : public Node {
132 protected:
133 /// Stores the matching edge on this node in the UBC
134 Edge* ubm;
135 /// Stores the matching edge on this node in the LBC
136 Edge* lbm;
137 public:
138 /// \name Constructors and initialization
139 //@{
140 /// Default constructor
141 VarNode(void);
142 /// Creates a variable node with index \a i
143 VarNode(int i);
144 //@}
145
146 /// \name Access
147 //@{
148 /// Return the matching edge on the node
149 Edge* get_match(BC bc) const;
150 /// tests whether the node is matched or not
151 bool matched(BC bc) const;
152 //@}
153
154 /// \name Update
155 //@{
156 /// Set the pointer of the matching edge to m
157 void set_match(BC bc, Edge* m);
158 /// Set node to matched
159 void match(BC bc);
160 /// Unmatch the node
161 void unmatch(BC bc);
162 //@}
163 };
164
165 /// Value node
166 class ValNode : public Node {
167 protected:
168 /// Minimal required occurence of the value as stored in k
169 int _klb;
170 /// Maximal required occurence of the value as stored in k
171 int _kub;
172 /// Index to acces the value via cardinality array k
173 int _kidx;
174 /// Stores the current number of occurences of the value
175 int _kcount;
176 /// Store numbre of conflicting matching edges
177 int noc;
178 /// Minimal capacity of the value node
179 int lb;
180 /// Smallest maximal capacity of the value node
181 int ublow;
182 /// Maximal capacity of the value node
183 int ub;
184 public:
185 /// Stores the value of the node
186 int val;
187
188 /// \name Constructors and destructors
189 //@{
190 /// Default constructor
191 ValNode(void);
192 /**
193 * \brief Constructor for value node
194 *
195 * with minimal capacity \a min,
196 * maximal capacity \a max,
197 * the value \a value and the index \a k_access in \a k
198 */
199 ValNode(int min, int max, int value, int kidx, int kshift, int count);
200 //@}
201
202 /// \name Access
203 //@{
204 /// get max cap for LBC
205 int maxlow(void) const;
206 /// Mark the value node as conflicting in case of variable cardinalities
207 void card_conflict(int c);
208 /// Check whether the value node is conflicting
209 int card_conflict(void) const;
210 /// Reduce the conflict counter
211 void red_conflict(void);
212 /// increases the value counter
213 void inc(void);
214 /// returns the current number of occurences of the value
215 int kcount(void) const;
216 /// returns the number of incident matching edges on a value node
217 int incid_match(BC bc) const;
218 /// returns the index in cardinality array k
219 int kindex(void) const;
220 /// returns \a true if the node is matched in BC, \a false otherwise
221 bool matched(BC bc) const;
222 /// tests whether the node is a sink
223 bool sink(void) const;
224 /// tests whether the node is a source
225 bool source(void) const;
226 /// return the minimal node capacity as stored in \a k
227 int kmin(void) const;
228 /// return the maximal node capacity as stored in \a k
229 int kmax(void) const;
230 /// return minimal or maximal capacity
231 int kbound(BC bc) const;
232 //@}
233
234 /// \name Update
235 //@{
236 /// set the max cap for LBC
237 void maxlow(int i);
238 /// Set how often value occurs
239 void kcount(int);
240 /// changes the index in the cardinality array k
241 void kindex(int);
242 /// decrease the node-capacity
243 void dec(BC bc);
244 /// increase the node-capacity
245 void inc(BC bc);
246 /// return the the node-capacity
247 int cap(BC bc) const;
248 /// set the node-capacity to \a c
249 void cap(BC bc, int c);
250 /// match the node
251 void match(BC bc);
252 /// unmatch the node
253 void unmatch(BC bc);
254 /// node reset to original capacity values
255 void reset(void);
256 /// set the minimal k-capacity to min
257 void kmin(int min);
258 /// set the maximal k-capacity to max
259 void kmax(int max);
260 //@}
261 };
262
263 /// Class for edges \f$ e(x,v) \f$ in the variable-value-graph
264 class Edge {
265 private:
266 /// pointer to the variable node
267 VarNode* x;
268 /// pointer to the value node
269 ValNode* v;
270 /// pointer to the next edge incident on the same variable node
271 Edge* next_edge;
272 /// pointer to the previous edge incident on the same variable node
273 Edge* prev_edge;
274 /// pointer to the next edge on the same value node
275 Edge* next_vedge;
276 /// pointer to the previous edge on the same value node
277 Edge* prev_vedge;
278 /// Flags for edges
279 enum EdgeFlag {
280 /// No flags set
281 EF_NONE = 0,
282 /// Whether edge is used in LBC
283 EF_MRKLB = 1 << 0,
284 /// Whether edge is used in UBC
285 EF_MRKUB = 1 << 1,
286 /// Whether edge is matched in LBC
287 EF_LM = 1 << 2,
288 /// Whether edge is matched in UBC
289 EF_UM = 1 << 3,
290 /// Whether edge has been deleted
291 EF_DEL = 1 << 4
292 };
293 /// Flags for edges
294 unsigned char ef;
295 public:
296 /// \name Constructors
297 //@{
298 /// Default constructor
299 Edge(void) {}
300 /**
301 * \brief Construct edge \f$e(x,v)\f$ from variable node \a x
302 * and value node \a y
303 */
304 Edge(VarNode* x, ValNode* v);
305 //@}
306
307 /// \name Access
308 //@{
309 /// Whether the edge is used
310 bool used(BC bc) const;
311 /// return whether the edge is matched
312 bool matched(BC bc) const;
313 /// return whether the edge has been deleted from the graph
314 bool deleted(void) const;
315 /**
316 * \brief return a pointer to the next edge
317 * If \a t is false the function returns the next edge incident on \a x
318 * otherwise it returns the next edge incident on \a v
319 */
320 Edge* next(bool t) const;
321 /// return the pointer to the next edge incident on \a x
322 Edge* next(void) const;
323 /// return the pointer to the previous edge incident on \a x
324 Edge* prev(void) const;
325 /// return the pointer to the next edge incident on \a v
326 Edge* vnext(void) const;
327 /// return the pointer to the previous edge incident on \a v
328 Edge* vprev(void) const;
329 /// return the pointer to the variable node \a x of this edge
330 VarNode* getVar(void) const;
331 /// return the pointer to the value node \a v of this edge
332 ValNode* getVal(void) const;
333 /**
334 * \brief return pointer to \a x if \a t = true otherwise return \a v
335 *
336 */
337 Node* getMate(bool t) const;
338 //@}
339
340 /// Update
341 //@{
342 /// Mark the edge as used
343 void use(BC bc);
344 /// Mark the edge as unused
345 void free(BC bc);
346 /// Reset the edge (free the edge, and unmatch the edge)
347 void reset(BC bc);
348 /// Match the edge
349 void match(BC bc);
350 /// Unmatch the edge and the incident nodes
351 void unmatch(BC bc);
352 /// Unmatch the edge and ( \a x if t=false, \a v otherwise )
353 void unmatch(BC bc, bool t);
354 /// Unlink the edge from the linked list of edges
355 void unlink(void);
356 /// Mark the edge as deleted during synchronization
357 void del_edge(void);
358 /// Insert the edge again
359 void insert_edge(void);
360 /// return the reference to the next edge incident on \a x
361 Edge** next_ref(void);
362 /// return the reference to the previous edge incident on \a x
363 Edge** prev_ref(void);
364 /// return the reference to the next edge incident on \a v
365 Edge** vnext_ref(void);
366 /// return the reference to the previous edge incident on \a v
367 Edge** vprev_ref(void);
368 //@}
369
370 /// \name Memory management
371 //@{
372 /// Allocate memory from space
373 static void* operator new(size_t s, Space& home);
374 /// Free memory (unused)
375 static void operator delete(void*, Space&) {};
376 /// Needed for exceptions
377 static void operator delete(void*) {};
378 //@}
379 };
380
381
382 /**
383 * \brief Variable-value-graph used during propagation
384 *
385 */
386 template<class Card>
387 class VarValGraph {
388 private:
389 /// Temporary stack for nodes
390 typedef Support::StaticStack<Node*,Region> NodeStack;
391 /// Bitset
392 typedef Support::BitSet<Region> BitSet;
393 /// Variable partition representing the problem variables
394 VarNode** vars;
395 /**
396 * \brief Value partition
397 * For each value
398 * \f$ v_i\in V=\left(\bigcup_\{0, \dots, |x|-1\}\right) D_i \f$
399 * in the domains of the
400 * problem variables there is a node in the graph.
401 */
402 ValNode** vals;
403 /// Cardinality of the variable partition
404 int n_var;
405 /**
406 * \brief Cardinality of the value partition
407 *
408 * Computed as \f$ |V| = \left(\bigcup_\{0, \dots, |x|-1\}\right) D_i \f$
409 */
410 int n_val;
411 /// Total number of nodes in the graph
412 int n_node;
413 /**
414 * \brief The sum over the minimal capacities of all value nodes
415 *
416 * \f$sum_min = \sum_{v_i \in V} l_i= k[i].min() \f$
417 */
418 int sum_min;
419 /**
420 * \brief The sum over the maximal capacities of all value nodes
421 *
422 * \f$sum_max = \sum_{v_i \in V} l_i= k[i].max() \f$
423 */
424 int sum_max;
425 public:
426 /// \name Constructors and Destructors
427 //@{
428 /**
429 * \brief Constructor for the variable-value-graph
430 *
431 * The variable parition is initialized with the variables from \a x,
432 * the value partition is initialized with the values from \a k.
433 **/
434 VarValGraph(Space& home,
435 ViewArray<IntView>& x, ViewArray<Card>& k,
436 int smin, int smax);
437 //@}
438 /// \name Graph-interface
439 //@{
440 /// Check whether minimum requirements shrink variable domains
441 ExecStatus min_require(Space& home,
442 ViewArray<IntView>& x, ViewArray<Card>& k);
443
444 /**
445 * \brief Synchronization of the graph
446 *
447 * If the graph has already been constructed and some edges have
448 * been removed during propagation, this function removes those edges
449 * that do not longer belong to the graph associated with the current
450 * variable domains.
451 */
452 ExecStatus sync(ViewArray<IntView>& x, ViewArray<Card>& k);
453 /// Remove edges that do not belong to any maximal matching
454 template<BC>
455 ExecStatus narrow(Space& home,
456 ViewArray<IntView>& x, ViewArray<Card>& k);
457
458 /** \brief Compute a maximum matching M on the graph
459 *
460 * - If BC=UBC then \f$|M|= |X|\f$
461 * - If BC=LBC then \f$|M|= \sum_{i\in \{ 0, \dots, |X|-1\}}
462 * k[i].min()\f$
463 */
464 template<BC>
465 ExecStatus maximum_matching(void);
466
467 /// Compute possible free alternating paths in the graph
468 template<BC>
469 void free_alternating_paths(void);
470 /// Compute possible strongly connected components of the graph
471 template<BC>
472 void strongly_connected_components(void);
473 /**
474 * \brief Test whether the current maximal matching on the graph
475 * can be augmented by an alternating path starting and ending with
476 * a free node.
477 */
478 template<BC>
479 bool augmenting_path(Node*);
480
481 protected:
482 /**
483 * \brief Perform depth-first search on the graph
484 *
485 * Depth first search used to compute the
486 * strongly connected components of the graph.
487 */
488 template<BC>
489 void dfs(Node*, BitSet&, BitSet&, int[],
490 NodeStack&, NodeStack&, int&);
491
492 //@}
493 public:
494 /// Allocate memory for the graph
495 void* operator new(size_t t, Space& home);
496 /// Deallocation (void)
497 void operator delete(void*, Space&) {}
498 };
499
500
501
502 /*
503 * Nodes
504 *
505 */
506 forceinline
507 Node::Node(void) {}
508 forceinline
509 Node::Node(NodeFlag nf0, int i)
510 : e(nullptr), fst(nullptr), lst(nullptr), ie(nullptr), idx(i),
511 nf(static_cast<unsigned char>(nf0)), noe(0) {}
512
513 forceinline Edge**
514 Node::adj(void) {
515 return &e;
516 }
517 forceinline Edge*
518 Node::first(void) const {
519 return fst;
520 }
521 forceinline Edge*
522 Node::last(void) const {
523 return lst;
524 }
525 forceinline void
526 Node::first(Edge* p) {
527 fst = p;
528 }
529 forceinline void
530 Node::last(Edge* p) {
531 lst = p;
532 }
533 forceinline bool
534 Node::type(void) const {
535 return (nf & NF_VAL) != 0;
536 }
537 forceinline Edge*
538 Node::inedge(void) const {
539 return ie;
540 }
541 forceinline void
542 Node::inedge(Edge* p) {
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 */
569 forceinline
570 VarNode::VarNode(void) {}
571
572 forceinline
573 VarNode::VarNode(int x) :
574 Node(NF_NONE,x), ubm(nullptr), lbm(nullptr) {}
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
585 VarNode::match(BC bc) {
586 if (bc == UBC)
587 nf |= NF_M_UBC;
588 else
589 nf |= NF_M_LBC;
590 }
591
592 forceinline void
593 VarNode::set_match(BC bc, Edge* p) {
594 if (bc == UBC)
595 ubm = p;
596 else
597 lbm = p;
598 }
599
600 forceinline void
601 VarNode::unmatch(BC bc) {
602 if (bc == UBC) {
603 nf &= ~NF_M_UBC; ubm = nullptr;
604 } else {
605 nf &= ~NF_M_LBC; lbm = nullptr;
606 }
607 }
608
609 forceinline Edge*
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 */
624 forceinline
625 ValNode::ValNode(void) {}
626
627 forceinline
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
636 ValNode::maxlow(int i) {
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
651 ValNode::card_conflict(int c) {
652 noc = c;
653 }
654
655 forceinline void
656 ValNode::red_conflict(void) {
657 noc--;
658 assert(noc >= 0);
659 }
660
661 forceinline int
662 ValNode::card_conflict(void) const {
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
679 ValNode::reset(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
717 ValNode::dec(BC bc) {
718 if (bc == UBC) {
719 ub--;
720 } else {
721 lb--; ublow--;
722 }
723 }
724
725 forceinline void
726 ValNode::inc(BC bc) {
727 if (bc == UBC) {
728 ub++;
729 } else {
730 lb++; ublow++;
731 }
732 }
733
734 forceinline void
735 ValNode::match(BC bc) {
736 dec(bc);
737 }
738
739 forceinline void
740 ValNode::unmatch(BC bc) {
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
763 ValNode::kcount(int c) {
764 _kcount = c;
765 }
766
767 forceinline void
768 ValNode::kindex(int i) {
769 _kidx = i;
770 }
771
772 forceinline int
773 ValNode::kindex(void) const {
774 return _kidx;
775 }
776
777 /// Returs the number of incident matching edges on the node
778 forceinline int
779 ValNode::incid_match(BC bc) const {
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 != nullptr)
814 *p->next_ref() = n;
815 if (n != nullptr)
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 != nullptr)
832 *pv->vnext_ref() = nv;
833 if (nv != nullptr)
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
844 forceinline
845 Edge::Edge(VarNode* var, ValNode* val) :
846 x(var), v(val),
847 next_edge(nullptr), prev_edge(nullptr),
848 next_vedge(nullptr), prev_vedge(nullptr), 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
858 Edge::free(BC bc) {
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 }
871 forceinline Edge*
872 Edge::next(void) const {
873 return next_edge;
874 }
875 forceinline Edge*
876 Edge::next(bool t) const {
877 if (t) {
878 return next_vedge;
879 } else {
880 return next_edge;
881 }
882 }
883
884 forceinline Edge*
885 Edge::vnext(void) const {
886 return next_vedge;
887 }
888 forceinline Edge**
889 Edge::vnext_ref(void) {
890 return &next_vedge;
891 }
892 forceinline Edge*
893 Edge::prev(void) const {
894 return prev_edge;
895 }
896 forceinline Edge**
897 Edge::prev_ref(void) {
898 return &prev_edge;
899 }
900 forceinline Edge*
901 Edge::vprev(void) const {
902 return prev_vedge;
903 }
904 forceinline Edge**
905 Edge::vprev_ref(void) {
906 return &prev_vedge;
907 }
908 forceinline Edge**
909 Edge::next_ref(void) {
910 return &next_edge;
911 }
912 forceinline VarNode*
913 Edge::getVar(void) const {
914 assert(x != nullptr);
915 return x;
916 }
917
918 forceinline ValNode*
919 Edge::getVal(void) const {
920 assert(v != nullptr);
921 return v;
922 }
923
924 forceinline Node*
925 Edge::getMate(bool type) const {
926 if (type)
927 return x;
928 else
929 return v;
930 }
931
932 forceinline void
933 Edge::unmatch(BC bc) {
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
954 Edge::reset(BC bc) {
955 free(bc); unmatch(bc);
956 }
957
958 forceinline void
959 Edge::match(BC bc) {
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
978 Edge::del_edge(void) {
979 ef |= EF_DEL;
980 }
981
982 forceinline void
983 Edge::insert_edge(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>
1004 VarValGraph<Card>::VarValGraph(Space& home,
1005 ViewArray<IntView>& x, ViewArray<Card>& k,
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() == nullptr)
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() == nullptr) {
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 = nullptr;
1072 }
1073 }
1074
1075
1076 template<class Card>
1077 inline ExecStatus
1078 VarValGraph<Card>::min_require(Space& home,
1079 ViewArray<IntView>& x,
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 != nullptr; e = e->vnext()) {
1087 VarNode* vrn = e->getVar();
1088 for (Edge* f = vrn->first(); f != nullptr; 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
1144 VarValGraph<Card>::augmenting_path(Node* v) {
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(nullptr);
1162 start[i] = vals[i-n_var]->first();
1163 } else {
1164 vars[i]->inedge(nullptr);
1165 start[i] = vars[i]->first();
1166 }
1167
1168 v->inedge(nullptr);
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 = nullptr;
1174 if (vv->type() == sp) {
1175 e = start[vv->index()];
1176 while ((e != nullptr) && e->matched(bc))
1177 e = e->next(vv->type());
1178 } else {
1179 e = start[vv->index()];
1180 while ((e != nullptr) && !e->matched(bc))
1181 e = e->next(vv->type());
1182 start[vv->index()] = e;
1183 }
1184 if (e != nullptr) {
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() != nullptr) {
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
1237 VarValGraph<Card>::sync(ViewArray<IntView>& x, ViewArray<Card>& k) {
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 != nullptr) {
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 != nullptr) && (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 != nullptr) {
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 != nullptr; 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 != nullptr);
1341 do {
1342 // search the edge that has to be deleted
1343 while ((e != nullptr) && (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 != nullptr);
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 = nullptr;
1364 while (e != nullptr) {
1365 e->getVar()->noe--;
1366 e->getVal()->noe--;
1367 e->del_edge();
1368 e->unlink();
1369 e = e->next();
1370 }
1371
1372 if ((mub != nullptr) && mub->deleted()) {
1373 mub->unmatch(UBC);
1374 re.push(vars[i]);
1375 }
1376
1377 //lower bound matching can be zero
1378 if ((mlb != nullptr) && 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
1417 VarValGraph<Card>::narrow(Space& home,
1418 ViewArray<IntView>& x, ViewArray<Card>& k) {
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 != nullptr; 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 != nullptr; 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
1511 VarValGraph<Card>::maximum_matching(void) {
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 != nullptr ; 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) {
1525 Support::StaticStack<ValNode*,Region> free(r,n_val);
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) {
1548 Support::StaticStack<VarNode*,Region> free(r,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
1575 VarValGraph<Card>::free_alternating_paths(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 != nullptr; 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 != nullptr; 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 != nullptr) {
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
1681 VarValGraph<Card>::dfs(Node* v,
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 != nullptr; 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
1745 VarValGraph<Card>::strongly_connected_components(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