« back to all changes in this revision
Viewing changes to int/gcc/graphsup.icc
- browse files at revision 1
- compare with another revision
- download diff
- download tarball
- view history from revision 1
- Committer: Bazaar Package Importer
- Author(s): Kari Pahula
- Date: 2005-12-24 07:51:25 UTC
- Revision ID: james.westby@ubuntu.com-20051224075125-klkiqofvbfvusfvt
Tags: upstream-1.0.0.dfsg.1
Import upstream version 1.0.0.dfsg.1
- files added:
- contribs
- contribs/graph
- contribs/graph/branch
- contribs/graph/examples
- contribs/graph/misc
- contribs/graph/misc/doxygen
- contribs/graph/path
- contribs/graph/view
- examples
- int
- int/arithmetic
- int/bool
- int/branch
- int/count
- int/cumulatives
- int/distinct
- int/dom
- int/element
- int/gcc
- int/linear
- int/regular
- int/rel
- int/sortedness
- int/var
- int/view
- iter
- kernel
- minimodel
- misc
- misc/debian
- misc/doxygen
- parallel
- search
- set
- set/branch
- set/branching
- set/convex
- set/distinct
- set/int
- set/rel
- set/rel-op
- set/select
- set/sequence
- set/var
- set/view
- support
- test
- test/int
- test/set
- test/stress
added
removed
int/gcc/graphsup.icc
1
/*
2
* Main authors:
3
* Patrick Pekczynski <pekczynski@ps.uni-sb.de>
4
*
5
* Copyright:
6
* Patrick Pekczynski, 2005
7
*
8
* Last modified:
9
* $Date: 2005-12-06 07:46:40 +0100 (Tue, 06 Dec 2005) $ by $Author: pekczynski $
10
* $Revision: 2696 $
11
*
12
* This file is part of Gecode, the generic constraint
13
* development environment:
14
* http://www.gecode.org
15
*
16
* See the file "LICENSE" for information on usage and
17
* redistribution of this file, and for a
18
* DISCLAIMER OF ALL WARRANTIES.
19
*
20
*/
21
22
namespace Gecode { namespace Int { namespace GCC {
23
24
/// Debugging: Print a View
25
template <class View>
26
void pview(View& v){
27
if (v.min() == v.max()) {
28
std::cout << v.min() <<" ";
29
} else {
30
if (v.range()){
31
std::cout << "["<<v.min() <<".."<<v.max()<<"] ";
32
} else {
33
std::cout << "{";
34
ViewValues<View> iter(v);
35
while(iter()){
36
std::cout << iter.val() <<",";
37
++iter;
38
}
39
std::cout << "} ";
40
}
41
}
42
}
43
44
/**
45
* \brief Bounds constraint (BC) type
46
*
47
* If BC = UBC, then we argue about the Upper Bounds Constraint
48
* else we use the functions for the Lower Bounds Constraint
49
*/
50
enum BC {UBC = 1, LBC = 0};
51
52
class Edge;
53
/// Base class for nodes in the variable-value-graph
54
class VVGNode{
55
private:
56
/// stores all incident edges on the node
57
Edge* e;
58
/// returns the first edge
59
Edge* fst;
60
/// returns the last edge
61
Edge* lst;
62
/// single incoming edge used for storing a path in the algorithms
63
Edge* ie;
64
/// Mark as matching edge in LBC
65
bool lm;
66
/// Mark as matching edge in UBC
67
bool um;
68
/// Explicit node type
69
bool type;
70
public:
71
/// \name Constructors and initialization
72
//@{
73
/// Default constructor
74
VVGNode(void);
75
//@}
76
/// Destructor
77
virtual ~VVGNode(void){};
78
/// Create a new node
79
void* operator new(size_t, void*);
80
81
/// \name Access
82
//@{
83
/// return reference to the incident edges
84
Edge** adj(void);
85
/// return pointer to the first incident edge
86
Edge* first(void);
87
/// return pointer to the last incident edge
88
Edge* last(void);
89
/// return pointer to the node's inedge
90
Edge* inedge(void);
91
/// return the type of the node
92
bool get_type(void);
93
/// access the matching flag of the node
94
template <BC>
95
bool get_match_flag(void);
96
/// get the information on the node (either var-index or value)
97
virtual int get_info(void) = 0;
98
/// test whether the node is matched
99
virtual bool is_matched(BC) = 0;
100
101
/// check whether a node has been removed from the graph
102
virtual bool removed(void) = 0;
103
//@}
104
105
/// \name Update
106
//@{
107
/// set the first edge pointer to \a p
108
void first(Edge* p);
109
/// set the last edge pointer to \a p
110
void last(Edge* p);
111
/// set the inedge pointer to \a p
112
void inedge(Edge* p);
113
/// set the node type to \a t
114
void set_type(bool t);
115
/// set the matching flag to \a f
116
template <BC>
117
void set_match_flag(bool f);
118
/// set the node information to \a i
119
virtual void set_info(int i) = 0;
120
//@}
121
};
122
123
/// %Variable Node
124
class VarNode : public VVGNode{
125
private:
126
/// stores the matching edge on this node in the UBC
127
Edge* ubm;
128
/// stores the matching edge on this node in the LBC
129
Edge* lbm;
130
131
public:
132
/// stores the variable index of the node
133
unsigned int var;
134
/// stores the number of incident edges on the node
135
unsigned int noe;
136
137
/// stores the variable index of the node
138
unsigned int xindex;
139
140
/// \name Constructors and initialization
141
//@{
142
/// Creates a variable node with index i
143
VarNode(int i, int oidx);
144
//@}
145
146
/// \name Access
147
//@{
148
/// return the matching edge on the node
149
template <BC>
150
Edge* get_match(void);
151
/// return the variable index of the node
152
int get_info(void);
153
/// returns whether the node is still matchable
154
bool is_matched(BC);
155
/// tests whether the node is matched or not
156
template <BC>
157
bool matched(void);
158
159
/// check for removal from graph
160
bool removed(void);
161
//@}
162
163
/// \name Update
164
//@{
165
/// set the node info to \a i
166
void set_info(int i);
167
/// set the pointer of the matching edge to m
168
template <BC>
169
void set_match(Edge* m);
170
/// match the node
171
template <BC>
172
void match(void);
173
/// unmatch the node
174
template <BC>
175
void unmatch(void);
176
//@}
177
};
178
179
/// Value node
180
class ValNode : public VVGNode{
181
private:
182
/// minimal required occurence of the value as stored in k
183
int _klb;
184
/// maximal required occurence of the value as stored in k
185
int _kub;
186
/// index to acces the value via cardinality array k
187
int _kidx;
188
/// stores the current number of occurences of the value
189
int _kcount;
190
191
192
/// mark as conflicting
193
bool conflict;
194
195
/**
196
* \brief Minimal capacity of the value node
197
*
198
* Stores who often the value node can be matched in a LBC-matching
199
*/
200
int lb;
201
int ublow;
202
/**
203
* \brief Maximal capacity of the value node
204
*
205
* Stores who often the value node can be matched in a UBC-matching
206
*/
207
208
int ub;
209
210
public:
211
/// stores the value of the node
212
int val;
213
/// stores the index of the node
214
int idx;
215
/// stores the number of incident edges on the node
216
int noe;
217
218
/// \name Constructors and destructors
219
//@{
220
/**
221
* \brief Constructor for value node
222
*
223
* with minimal capacity \a min,
224
* maximal capacity \a max,
225
* the value \a value and the index \a k_access in \a k
226
*/
227
ValNode(int min, int max, int value, int kidx, int kshift, int count);
228
//@}
229
230
/// \name Access
231
//@{
232
233
/// set the max cap for LBC
234
void set_maxlow(int i);
235
/// get max cap for LBC
236
int get_maxlow(void);
237
238
239
/// Mark the value node as conflicting in case of variable cardinalities
240
void card_conflict(bool c);
241
/// Check whether the value node is conflicting
242
bool card_conflict(void);
243
244
/// check for removal from graph
245
bool removed(void);
246
247
/// increases the value counter
248
void inc(void);
249
/// returns the current number of occurences of the value
250
int kcount(void);
251
/// returns the number of incident matching edges on a value node
252
template <BC>
253
int incid_match(void);
254
/// returns the index in cardinality array k
255
int kindex(void);
256
/// return the node information
257
int get_info(void);
258
/// returns \a true if the node is matched in BC, \a false otherwise
259
template <BC>
260
bool matched(void);
261
/// tests whether the node is a sink
262
bool sink(void);
263
/// tests whether the node is a source
264
bool source(void);
265
/// return the minimal node capacity as stored in \a k
266
int kmin(void);
267
/// return the maximal node capacity as stored in \a k
268
int kmax(void);
269
/// return minimal or maximal capacity
270
template <BC>
271
int kbound(void);
272
273
/// returns whether the node is still matchable
274
bool is_matched(BC);
275
//@}
276
277
/// \name Update
278
//@{
279
void kcount(int);
280
/// changes the index in the cardinality array k
281
void kindex(int);
282
/// decrease the node-capacity
283
template <BC>
284
void dec(void);
285
/// increase the node-capacity
286
template <BC>
287
void inc(void);
288
/// return the the node-capacity
289
template <BC>
290
int cap(void);
291
/// set the node-capacity to \a c
292
template <BC>
293
void set_cap(int c);
294
/// match the node
295
template <BC>
296
void match(void);
297
/// unmatch the node
298
template <BC>
299
void unmatch(void);
300
/// node reset to original capacity values
301
void reset(void);
302
/// set the node infomration to \a i
303
void set_info(int i);
304
/// set the minimal k-capacity to min
305
void set_kmin(int min);
306
/// set the maximal k-capacity to max
307
void set_kmax(int max);
308
//@}
309
};
310
311
/// Class for edges \f$ e(x,v) \f$ in the variable-value-graph
312
class Edge{
313
private:
314
/// pointer to the variable node
315
VarNode* x;
316
/// pointer to the value node
317
ValNode* v;
318
/// pointer to the next edge incident on the same variable node
319
Edge* next_edge;
320
/// pointer to the previous edge incident on the same variable node
321
Edge* prev_edge;
322
/// pointer to the next edge on the same value node
323
Edge* next_vedge;
324
/// pointer to the previous edge on the same value node
325
Edge* prev_vedge;
326
/**
327
* \brief stores whether the edge is used in LBC
328
* Flag storing whether the edge is used in any maximum LBC matching
329
* in the variable-value-graph
330
*/
331
bool mrklb;
332
/**
333
* \brief stores whether the edge is used in UBC
334
* Flag storing whether the edge is used in any maximum UBC matching
335
* in the variable-value-graph
336
*/
337
bool mrkub;
338
/// stores whether the edge is matched in LBC matching
339
bool um;
340
/// stores whether the edge is matched in UBC matching
341
bool lm;
342
/// stores whether the edge has been deleted during syncronization
343
bool deleted; // del
344
345
public:
346
/// \name Constructors
347
//@{
348
/**
349
* \brief Construct edge \f$e(x,v)\f$ from variable node \a x
350
* and value node \a y
351
*/
352
Edge(VarNode* x, ValNode* v);
353
/// Create a new edge in memory
354
void* operator new(size_t, void*);
355
//@}
356
357
/// \name Access
358
//@{
359
/**
360
* \brief return whether the edge is used
361
*
362
* An edge can be used in a matching on the graph,
363
* a path on the graph or a cycle in the graph.
364
*
365
*/
366
template <BC>
367
bool used(void);
368
/// return whether the edge is matched
369
template <BC>
370
bool matched(void);
371
/// return whether the edge has been deleted from the graph
372
bool is_deleted(void);
373
/**
374
* \brief return a pointer to the next edge
375
* If \a t is false the function returns the next edge incident on \a x
376
* otherwise it returns the next edge incident on \a v
377
*/
378
Edge* next(bool t) const;
379
/// return the pointer to the next edge incident on \a x
380
Edge* next(void) const;
381
/// return the pointer to the previous edge incident on \a x
382
Edge* prev(void) const;
383
/// return the pointer to the next edge incident on \a v
384
Edge* vnext(void) const;
385
/// return the pointer to the previous edge incident on \a v
386
Edge* vprev(void) const;
387
/// return the pointer to the variable node \a x of this edge
388
VarNode* getVar(void);
389
/// return the pointer to the value node \a v of this edge
390
ValNode* getVal(void);
391
/**
392
* \brief return pointer to \a x if \a t = true otherwise return \a v
393
*
394
*/
395
VVGNode* getMate(bool t);
396
//@}
397
398
/// Update
399
//@{
400
/// Mark the edge as used
401
template <BC>
402
void use(void);
403
/// Mark the edge as unused
404
template <BC>
405
void free(void);
406
/**
407
* \brief Reset the edge ( free the edge, and unmatch
408
* the edge including its end-nodes
409
*
410
*/
411
template <BC>
412
void reset(void);
413
/// Match the edge
414
template <BC>
415
void match(void);
416
/// Unmatch the edge and the incident nodes
417
template <BC>
418
void unmatch(void);
419
/// Unmatch the edge and ( \a x if t=false, \a v otherwise )
420
template <BC>
421
void unmatch(bool t);
422
/// Unlink the edge from the linked list of edges
423
void unlink(void);
424
/// Mark the edge as deleted during synchronization
425
void del_edge(void);
426
/// Insert the edge again
427
void insert_edge(void);
428
/// return the reference to the next edge incident on \a x
429
Edge** next_ref(void);
430
/// return the reference to the previous edge incident on \a x
431
Edge** prev_ref(void);
432
/// return the reference to the next edge incident on \a v
433
Edge** vnext_ref(void);
434
/// return the reference to the previous edge incident on \a v
435
Edge** vprev_ref(void);
436
//@}
437
};
438
439
/**
440
* \brief Variable-value-graph used during propagation
441
*
442
*/
443
template <class View, class Card, bool isView>
444
class VarValGraph{
445
private:
446
/// failure flag
447
bool fail;
448
/// Allocated memory for nodes and edges
449
char* mem;
450
/// Problem variables
451
ViewArray<View>& x;
452
/// Copy keeping track of removed variables
453
ViewArray<View>& y;
454
/// Occurences
455
Card& k;
456
/// Variable partition representing the problem variables
457
VarNode** vars;
458
/**
459
* \brief Value partition
460
* For each value
461
* \f$ v_i\in V=\left(\bigcup_\{0, \dots, |x|-1\}\right) D_i \f$
462
* in the domains of the
463
* problem variables there is a node in the graph.
464
*/
465
ValNode** vals; // value partition De
466
/// the edges connecting the variable and the value partition
467
Edge* edges; // edges e
468
/// cardinality of the variable partition
469
int n_var;
470
/**
471
* \brief cardinality of the value partition
472
*
473
* Computed as \f$ |V| = \left(\bigcup_\{0, \dots, |x|-1\}\right) D_i \f$
474
*/
475
int n_val;
476
/// the number of edges in the graph
477
int n_edge;
478
/// total number of nodes in the graph
479
int node_size;
480
/**
481
* \brief The sum over the minimal capacities of all value nodes
482
*
483
* \f$sum_min = \sum_{v_i \in V} l_i= k[i].min() \f$
484
*/
485
int sum_min;
486
/**
487
* \brief The sum over the maximal capacities of all value nodes
488
*
489
* \f$sum_max = \sum_{v_i \in V} l_i= k[i].max() \f$
490
*/
491
int sum_max;
492
public:
493
/// \name Constructors and Destructors
494
//@{
495
VarValGraph(ViewArray<View>&, ViewArray<View>&, Card& , int , int , int );
496
/// Destructor
497
~VarValGraph(void);
498
//@}
499
/// \name Graph-interface
500
//@{
501
/**
502
* \brief Check whether propagation failed
503
* This is actually needed to cope with failures
504
* occuring in functions returing only a boolean value
505
* and not an ExecStatus.
506
*/
507
bool failed(void);
508
/**
509
* \brief Set the failure flag of the graph
510
*/
511
void failed(bool b);
512
513
/**
514
* \brief Check whether minimum requirements shrink variable domains
515
*
516
*/
517
bool min_require(Space* home);
518
519
/**
520
* \brief Synchronization of the graph
521
*
522
* If the graph has already been constructed and some edges have
523
* been removed during propagation \fn sync removes those edges
524
* that do not longer belong to the graph associated with the current
525
* variable domains.
526
*/
527
bool sync(void);
528
/// Print graph information for debugging
529
void print_graph(void);
530
/// Print matching information for debugging
531
template <BC>
532
void print_matching(void);
533
/// Gather matching information
534
void print_match(void);
535
536
/// Print edge information
537
void print_edges(void);
538
539
/// Allocate memory for the graph
540
void* operator new(size_t t);
541
/// Free the memory for the graph
542
void operator delete(void* p);
543
544
/**
545
* \brief Narrow the variable domains
546
* Remove all those edges from the graph that do not belong
547
* to any possible maximum matching on the graph
548
*
549
*/
550
551
template <BC>
552
bool narrow(Space*);
553
/** \brief Compute a maximum matching M on the graph
554
*
555
* If BC=UBC then \f$|M|= |X|\f$
556
* If BC=LBC then \f$|M|= \sum_{i\in \{ 0, \dots, |X|-1\}}
557
* k[i].min()\f$
558
*/
559
template <BC>
560
bool maximum_matching(void);
561
562
/// Compute possible free alternating paths in the graph
563
template <BC>
564
void free_alternating_paths(void);
565
/// Compute possible strongly connected components of the graph
566
template <BC>
567
void strongly_connected_components(void);
568
/**
569
* \brief Test whether the current maximal matching on the graph
570
* can be augmented by an alternating path starting and ending with
571
* a free node.
572
*/
573
template <BC>
574
bool augmenting_path(VVGNode*);
575
576
protected:
577
/**
578
* \brief DFS on the graph
579
*
580
* Depth first search used to compute the
581
* strongly connected components of the graph.
582
*/
583
template <BC>
584
void dfs(VVGNode*,
585
bool[], bool[], int[],
586
Support::StaticStack<VVGNode*>&,
587
Support::StaticStack<VVGNode*>&,
588
int&);
589
590
//@}
591
};
592
593
forceinline
594
VVGNode::VVGNode(void){} //no-op
595
596
forceinline void*
597
VVGNode::operator new(size_t n, void* p){
598
return p;
599
}
600
601
forceinline Edge**
602
VVGNode::adj(void){
603
return &e;
604
}
605
606
forceinline Edge*
607
VVGNode::first(void){
608
return fst;
609
}
610
611
forceinline Edge*
612
VVGNode::last(void){
613
return lst;
614
}
615
616
forceinline void
617
VVGNode::first(Edge* p){
618
fst = p;
619
}
620
621
forceinline void
622
VVGNode::last(Edge* p){
623
lst = p;
624
}
625
626
forceinline bool
627
VVGNode::get_type(void){
628
return type;
629
}
630
631
forceinline void
632
VVGNode::set_type(bool b){
633
type = b;
634
}
635
636
forceinline Edge*
637
VVGNode::inedge(void){
638
return ie;
639
}
640
641
forceinline void
642
VVGNode::inedge(Edge* p){
643
ie = p;
644
}
645
646
template <BC direction>
647
forceinline void
648
VVGNode::set_match_flag(bool b){
649
if (direction == UBC) {
650
um = b;
651
} else {
652
lm = b;
653
}
654
}
655
656
template <BC direction>
657
forceinline bool
658
VVGNode::get_match_flag(void){
659
if (direction == UBC) {
660
return um;
661
} else {
662
return lm;
663
}
664
}
665
666
667
/// Variable Node
668
669
forceinline bool
670
VarNode::removed(void) {
671
return noe == 0;
672
}
673
674
675
676
forceinline
677
VarNode::VarNode(int x, int orig_idx) :
678
ubm(NULL), lbm(NULL), var(x), noe(0), xindex(orig_idx){
679
first(NULL);
680
last(NULL);
681
inedge(NULL);
682
unmatch<LBC>();
683
unmatch<UBC>();
684
set_type(false);
685
}
686
687
forceinline bool
688
VarNode::is_matched(BC d) {
689
if (d == UBC) {
690
return matched<UBC>();
691
} else {
692
return matched<LBC>();
693
}
694
}
695
696
template <BC direction>
697
forceinline bool
698
VarNode::matched(void){
699
return get_match_flag<direction>();
700
}
701
702
template <BC direction>
703
forceinline void
704
VarNode::match(void){
705
set_match_flag<direction>(true);
706
}
707
708
template <BC direction>
709
forceinline void
710
VarNode::unmatch(void){
711
set_match_flag<direction>(false);
712
set_match<direction>(NULL);
713
}
714
715
template <BC direction>
716
forceinline void
717
VarNode::set_match(Edge* p){
718
if (direction == UBC) {
719
ubm = p;
720
} else {
721
lbm = p;
722
}
723
}
724
725
template <BC direction>
726
forceinline Edge*
727
VarNode::get_match(void){
728
if (direction == UBC) {
729
return ubm;
730
} else {
731
return lbm;
732
}
733
}
734
735
forceinline void
736
VarNode::set_info(int i){
737
var = i;
738
}
739
740
forceinline int
741
VarNode::get_info(void){
742
return var;
743
}
744
745
/// Value Node
746
747
forceinline void
748
ValNode::set_maxlow(int i){
749
ublow = i;
750
}
751
752
forceinline int
753
ValNode::get_maxlow(void) {
754
if (_klb == _kub) {
755
assert(ublow == lb);
756
}
757
758
return ublow;
759
}
760
761
762
forceinline void
763
ValNode::card_conflict(bool c){
764
conflict = c;
765
}
766
767
forceinline bool
768
ValNode::card_conflict(void){
769
return conflict;
770
}
771
772
forceinline bool
773
ValNode::removed(void) {
774
return noe == 0;
775
}
776
777
forceinline bool
778
ValNode::is_matched(BC d) {
779
if (d == UBC) {
780
return matched<UBC>();
781
} else {
782
return ublow == 0;
783
}
784
}
785
786
forceinline void
787
ValNode::reset(void){
788
lb = _klb;
789
ublow = _kub;
790
ub = _kub;
791
noe = 0;
792
}
793
794
template <BC direction>
795
forceinline int
796
ValNode::kbound(void){
797
if (direction == UBC) {
798
return _kub;
799
} else {
800
return _klb;
801
}
802
}
803
804
forceinline int
805
ValNode::kmax(void){
806
return _kub;
807
}
808
809
forceinline int
810
ValNode::kmin(void){
811
return _klb;
812
}
813
814
forceinline void
815
ValNode::set_kmin(int klb){
816
_klb = klb;
817
}
818
819
forceinline void
820
ValNode::set_kmax(int kub){
821
_kub = kub;
822
}
823
824
template <BC direction>
825
forceinline int
826
ValNode::cap(void){
827
if (direction == UBC) {
828
return ub;
829
} else {
830
return lb;
831
}
832
}
833
834
template <BC direction>
835
forceinline void
836
ValNode::dec(void){
837
if (direction == UBC) {
838
ub--;
839
} else {
840
lb--;
841
ublow--;
842
}
843
}
844
845
template <BC direction>
846
forceinline void
847
ValNode::inc(void){
848
if (direction == UBC) {
849
ub++;
850
} else {
851
lb++;
852
ublow++;
853
}
854
}
855
856
template <BC direction>
857
forceinline void
858
ValNode::match(void){
859
dec<direction>();
860
}
861
862
template <BC direction>
863
forceinline void
864
ValNode::unmatch(void){
865
inc<direction>();
866
}
867
868
template <BC direction>
869
forceinline bool
870
ValNode::matched(void){
871
return ( cap<direction>() == 0);
872
}
873
874
forceinline
875
ValNode::ValNode(int min, int max, int value,
876
int kidx, int kshift, int count) :
877
_klb(min), _kub(max), _kidx(kidx), _kcount(count),
878
conflict(false),
879
lb(min), ublow(max), ub(max),
880
val(value), idx(kshift), noe(0) {
881
first(NULL);
882
last(NULL);
883
inedge(NULL);
884
Edge** vadjacent = adj();
885
*vadjacent = NULL;
886
set_type(true);
887
}
888
889
template<BC direction>
890
forceinline void
891
ValNode::set_cap(int c){
892
if (direction == UBC) {
893
ub = c;
894
} else {
895
lb = c;
896
ublow = c;
897
}
898
}
899
900
forceinline void
901
ValNode::set_info(int i){
902
idx = i;
903
}
904
905
forceinline int
906
ValNode::get_info(void){
907
return idx;
908
}
909
910
forceinline void
911
ValNode::inc(void) {
912
_kcount++;
913
}
914
915
forceinline int
916
ValNode::kcount(void) {
917
return _kcount;
918
}
919
920
forceinline void
921
ValNode::kcount(int c) {
922
_kcount = c;
923
}
924
925
forceinline void
926
ValNode::kindex(int i){
927
_kidx = i;
928
}
929
930
forceinline int
931
ValNode::kindex(void){
932
return _kidx;
933
}
934
935
/// Returs the number of incident matching edges on the node
936
template <BC direction>
937
forceinline int
938
ValNode::incid_match(void){
939
if (direction == LBC) {
940
return _kub - ublow + _kcount;
941
} else {
942
return _kub - ub + _kcount;
943
}
944
}
945
946
947
forceinline bool
948
ValNode::sink(void){
949
// there are only incoming edges
950
// in case of the UBC-matching
951
bool is_sink = false;
952
is_sink = (_kub - ub == noe);
953
return is_sink;
954
}
955
956
forceinline bool
957
ValNode::source(void){
958
// there are only incoming edges
959
// in case of the UBC-matching
960
bool is_sink = false;
961
is_sink = (_klb - lb == noe);
962
return is_sink;
963
}
964
965
/// Edge
966
967
forceinline std::ostream&
968
operator<<(std::ostream& os, Edge* e){
969
if (e== NULL) {
970
os << "(N)";
971
} else {
972
os << "e("<<e->getVar()->var<<","<<e->getVal()->val<<")";
973
}
974
return os;
975
}
976
977
978
forceinline void
979
Edge::unlink(void){
980
// unlink from variable side
981
Edge* p = prev_edge;
982
Edge* n = next_edge;
983
984
if (p != NULL) {
985
Edge** pnext = p->next_ref();
986
*pnext = n;
987
}
988
989
if (n != NULL) {
990
Edge** nprev = n->prev_ref();
991
*nprev = p;
992
}
993
994
if (this == x->first()) {
995
Edge** ref = x->adj();
996
*ref = n;
997
x->first(n);
998
}
999
1000
if (this == x->last()) {
1001
x->last(p);
1002
}
1003
1004
// unlink from value side
1005
Edge* pv = prev_vedge;
1006
Edge* nv = next_vedge;
1007
1008
if (pv != NULL) {
1009
Edge** pvnext = pv->vnext_ref();
1010
*pvnext = nv;
1011
}
1012
1013
if (nv != NULL) {
1014
Edge** nvprev = nv->vprev_ref();
1015
*nvprev = pv;
1016
}
1017
1018
if (this == v->first()) {
1019
Edge** ref = v->adj();
1020
*ref = nv;
1021
v->first(nv);
1022
}
1023
1024
if (this == v->last()) {
1025
v->last(pv);
1026
}
1027
}
1028
1029
forceinline
1030
Edge::Edge(VarNode* var, ValNode* val) :
1031
x(var), v(val),
1032
next_edge(NULL), prev_edge(NULL),
1033
next_vedge(NULL), prev_vedge(NULL),
1034
mrklb(false), mrkub(false),
1035
um(false), lm(false), deleted(false) {};
1036
1037
forceinline void*
1038
Edge::operator new(size_t, void* p){ //why is there no argument?
1039
return p;
1040
}
1041
1042
template <BC direction>
1043
forceinline void
1044
Edge::use(void){
1045
if (direction == UBC) {
1046
mrkub = true;
1047
} else {
1048
mrklb = true;
1049
}
1050
}
1051
1052
template <BC direction>
1053
forceinline void
1054
Edge::free(void){
1055
/// the failure is here, capacity is not increased for value nodes
1056
if (direction == UBC) {
1057
mrkub = false;
1058
} else {
1059
mrklb = false;
1060
}
1061
}
1062
1063
template <BC direction>
1064
forceinline void
1065
Edge::reset(void){
1066
this->free<direction>();
1067
this->unmatch<direction>();
1068
}
1069
1070
template <BC direction>
1071
forceinline bool
1072
Edge::used(void){
1073
if (direction == UBC){
1074
return mrkub;
1075
} else {
1076
return mrklb;
1077
}
1078
}
1079
1080
forceinline Edge*
1081
Edge::next(void) const{
1082
return next_edge;
1083
}
1084
1085
forceinline Edge*
1086
Edge::next(bool t) const{
1087
if (t) {
1088
return next_vedge;
1089
} else {
1090
return next_edge;
1091
}
1092
}
1093
1094
forceinline Edge*
1095
Edge::vnext(void) const{
1096
return next_vedge;
1097
}
1098
1099
forceinline Edge**
1100
Edge::vnext_ref(void) {
1101
return &next_vedge;
1102
}
1103
1104
forceinline Edge*
1105
Edge::prev(void) const{
1106
return prev_edge;
1107
}
1108
1109
forceinline Edge**
1110
Edge::prev_ref(void) {
1111
return &prev_edge;
1112
}
1113
1114
forceinline Edge*
1115
Edge::vprev(void) const{
1116
return prev_vedge;
1117
}
1118
1119
forceinline Edge**
1120
Edge::vprev_ref(void) {
1121
return &prev_vedge;
1122
}
1123
1124
forceinline Edge**
1125
Edge::next_ref(void){
1126
return &next_edge;
1127
}
1128
forceinline VarNode*
1129
Edge::getVar(void){
1130
return x;
1131
}
1132
1133
forceinline ValNode*
1134
Edge::getVal(void){
1135
return v;
1136
}
1137
1138
forceinline VVGNode*
1139
Edge::getMate(bool type){
1140
if (type) {
1141
return x;
1142
} else {
1143
return v;
1144
}
1145
}
1146
1147
template <BC direction>
1148
forceinline void
1149
Edge::unmatch(void){
1150
if (direction == UBC) {
1151
um = false;
1152
} else {
1153
lm = false;
1154
}
1155
x->unmatch<direction>();
1156
v->unmatch<direction>();
1157
}
1158
1159
template <BC direction>
1160
forceinline void
1161
Edge::unmatch(bool node){
1162
if (direction == UBC) {
1163
um = false;
1164
} else {
1165
lm = false;
1166
}
1167
if (node) {
1168
v->template unmatch<direction>();
1169
} else {
1170
x->template unmatch<direction>();
1171
}
1172
}
1173
1174
template <BC direction>
1175
forceinline void
1176
Edge::match(void){
1177
if (direction == UBC) {
1178
um = true;
1179
x->template match<direction>();
1180
x->template set_match<direction>(this);
1181
v->template match<direction>();
1182
} else {
1183
lm = true;
1184
x->template match<direction>();
1185
x->template set_match<direction>(this);
1186
v->template match<direction>();
1187
}
1188
}
1189
1190
template <BC direction>
1191
forceinline bool
1192
Edge::matched(void){
1193
if (direction == UBC) {
1194
return um;
1195
} else {
1196
return lm;
1197
}
1198
}
1199
1200
forceinline void
1201
Edge::del_edge(void){
1202
deleted = true;
1203
}
1204
1205
forceinline void
1206
Edge::insert_edge(void){
1207
deleted = false;
1208
}
1209
1210
1211
forceinline bool
1212
Edge::is_deleted(void){
1213
return deleted;
1214
}
1215
1216
/**
1217
* \brief Constructor for the variable-value-graph
1218
*
1219
* The variable parition is initialized with the variables from \a x,
1220
* the value partition is initialized with the values from \a v,
1221
* where \f$ \forall v_i\in V: val_idx[i] is the
1222
* index of v_i in k \f$. \a nov denotes the cardinality of the
1223
* value partition in the graph, \a noe the number of edges in the
1224
* graph, \a min_occ the sum over the minimal occurences
1225
* of all values and \a max_occ the sum over the maximal occurences
1226
* of all values.
1227
**/
1228
1229
template <class View, class Card, bool isView>
1230
VarValGraph<View, Card, isView>::VarValGraph(ViewArray<View>& xref,
1231
ViewArray<View>& yref,
1232
Card& kref,
1233
int noe,
1234
int smin, int smax)
1235
: fail(false),
1236
x(xref),
1237
y(yref),
1238
k(kref),
1239
n_var(x.size()),
1240
n_val(k.size()),
1241
n_edge(noe),
1242
node_size(n_var + n_val),
1243
sum_min(smin),
1244
sum_max(smax) {
1245
1246
//memory allocation
1247
size_t edge_size = sizeof(Edge) * n_edge;
1248
size_t var_size = sizeof(VarNode) * n_var;
1249
size_t var_ptr_size = sizeof(VarNode*) * n_var;
1250
size_t val_size = sizeof(ValNode) * n_val;
1251
size_t val_ptr_size = sizeof(ValNode*) * n_val;
1252
size_t size = edge_size + var_size + var_ptr_size +
1253
val_size + val_ptr_size;
1254
1255
mem = reinterpret_cast<char*>
1256
(Memory::malloc(size));
1257
edges = reinterpret_cast<Edge*>
1258
(mem);
1259
VarNode* vars_ptr = reinterpret_cast<VarNode*>
1260
(mem + edge_size);
1261
ValNode* vals_ptr = reinterpret_cast<ValNode*>
1262
(mem + edge_size + var_size);
1263
vars = reinterpret_cast<VarNode**>
1264
(mem + edge_size + var_size + val_size);
1265
vals = reinterpret_cast<ValNode**>
1266
(mem + edge_size + var_size + val_size + var_ptr_size);
1267
1268
for (int i = n_val; i--; ){
1269
int kmi = k[i].min();
1270
int kma = k[i].max();
1271
int kc = k[i].counter();
1272
if (kc != kma) {
1273
if (kmi >= kc) {
1274
kmi -=kc;
1275
assert(kmi >=0);
1276
} else {
1277
kmi = 0;
1278
}
1279
kma -= kc;
1280
assert (kma > 0);
1281
vals[i] = new (vals_ptr + i)
1282
ValNode(kmi, kma, k[i].card(), i, i + n_var, kc);
1283
} else {
1284
vals[i] = new (vals_ptr + i)
1285
ValNode(0, 0, k[i].card(), i, i + n_var, kc);
1286
}
1287
}
1288
1289
for (int i = n_var; i--; ){
1290
1291
vars[i] = new (vars_ptr + i) VarNode(i, x[i].oldindex());
1292
VarNode* vrn = vars[i];
1293
// get the space for the edges of the varnode
1294
Edge** xadjacent = vrn->adj();
1295
1296
ViewValues<View> xiter(x[i]);
1297
int j = 0;
1298
for (; xiter(); ++xiter){
1299
int v = xiter.val();
1300
// get the correct index for the value
1301
while(vals[j]->val < v){
1302
j++;
1303
}
1304
ValNode* vln = vals[j];
1305
*xadjacent = new (edges) Edge(vars_ptr + i, vals_ptr + j);
1306
vrn->noe++;
1307
if (vrn->first() == NULL) {
1308
vrn->first(*xadjacent);
1309
}
1310
Edge* oldprev = vrn->last();
1311
vrn->last(*xadjacent);
1312
Edge** newprev = vrn->last()->prev_ref();
1313
*newprev = oldprev;
1314
1315
if (vln->first() == NULL) {
1316
vln->first(*xadjacent);
1317
vln->last(*xadjacent);
1318
vln->noe++;
1319
} else {
1320
Edge* old = vln->first();
1321
vln->first(*xadjacent);
1322
Edge** newnext = vln->first()->vnext_ref();
1323
*newnext = old;
1324
Edge** setprev = old->vprev_ref();
1325
*setprev = vln->first();
1326
vln->noe++;
1327
}
1328
edges++;
1329
xadjacent = (*xadjacent)->next_ref();
1330
}
1331
*xadjacent = NULL;
1332
}
1333
}
1334
1335
template <class View, class Card, bool isView>
1336
forceinline bool
1337
VarValGraph<View, Card, isView>::failed(void){
1338
return fail;
1339
}
1340
1341
template <class View, class Card, bool isView>
1342
forceinline void
1343
VarValGraph<View, Card, isView>::failed(bool b){
1344
fail = b;
1345
}
1346
1347
template <class View, class Card, bool isView>
1348
forceinline bool
1349
VarValGraph<View, Card, isView>::min_require(Space* home){
1350
1351
bool modified = false;
1352
for (int i = n_val; i--; ) {
1353
ValNode* vln = vals[i];
1354
if (vln->noe > 0) {
1355
if (k[i].min() == vln->noe) {
1356
// all variable nodes reachable from vln should be equal to vln->val
1357
for (Edge* e = vln->first(); e != NULL; e = e->vnext()) {
1358
VarNode* vrn = e->getVar();
1359
int vi = vrn->get_info();
1360
for (Edge* f = vrn->first(); f != NULL; f = f->next()) {
1361
if (f != e) {
1362
ValNode* w = f->getVal();
1363
w->noe--;
1364
vrn->noe--;
1365
f->del_edge();
1366
f->unlink();
1367
}
1368
}
1369
1370
modified |= x[vi].modified();
1371
x[vi].eq(home, vln->val);
1372
1373
vars[vi] = vars[--n_var];
1374
vars[vi]->set_info(vi);
1375
1376
int n = x.size();
1377
x[vi] = x[--n];
1378
x[vi].index(vi);
1379
x.size(n);
1380
1381
node_size--;
1382
vln->noe--;
1383
}
1384
1385
k[i].eq(home, k[i].min());
1386
k[i].counter(k[i].min());
1387
vln->template set_cap<UBC>(0);
1388
vln->template set_cap<LBC>(0);
1389
vln->set_maxlow(0);
1390
sum_min -= k[i].min();
1391
sum_max -= k[i].max();
1392
1393
}
1394
}
1395
}
1396
1397
for (int i = n_val; i--; ) {
1398
vals[i]->set_info(n_var + i);
1399
}
1400
1401
return modified;
1402
}
1403
1404
template <class View, class Card, bool isView>
1405
forceinline bool
1406
VarValGraph<View, Card, isView>::sync(void){
1407
1408
GECODE_AUTOARRAY(VVGNode*, re, node_size);
1409
GECODE_AUTOARRAY(BC, re_direct, node_size);
1410
GECODE_AUTOARRAY(Edge*, cre, node_size);
1411
int n_re = 0;
1412
1413
if (isView) {
1414
for (int i = n_val; i--; ) {
1415
1416
ValNode* v = vals[i];
1417
int inc_ubc = v->template incid_match<UBC>();
1418
int inc_lbc = v->template incid_match<LBC>();
1419
1420
// the cardinality bounds have been modified
1421
if (k[i].max() < v->kmax() || k[i].min() > v->kmin()) {
1422
if (!k[i].max() == k[i].counter()) {
1423
// update the bounds
1424
v->set_kmax(k[i].max());
1425
v->set_kmin(k[i].min());
1426
1427
//everything is fine
1428
if (inc_ubc <= k[i].max()) {
1429
v->template set_cap<UBC>(k[i].max() - (inc_ubc));
1430
v->set_maxlow(k[i].max() - (inc_lbc));
1431
if (v->kmin() == v->kmax()) {
1432
v->set_cap<LBC>(k[i].max() - (inc_lbc));
1433
}
1434
} else {
1435
// set cap to max and resolve conflicts on view side
1436
// set to full capacity for later rescheduling
1437
v->template set_cap<UBC>(k[i].max());
1438
v->set_maxlow(k[i].max() - (inc_lbc));
1439
if (v->kmin() == v->kmax()) {
1440
v->set_cap<LBC>(k[i].max() - (inc_lbc));
1441
}
1442
v->card_conflict(true);
1443
}
1444
}
1445
}
1446
1447
if (inc_lbc < k[i].min()) {
1448
v->template set_cap<LBC>(k[i].min() - inc_lbc);
1449
cre[n_re] = NULL;
1450
re[n_re] = v;
1451
re_direct[n_re] = LBC;
1452
n_re++;
1453
}
1454
}
1455
1456
for (int i = n_var; i--; ) {
1457
Edge* mub = vars[i]->template get_match<UBC>();
1458
if (mub != NULL) {
1459
ValNode* vu = mub->getVal();
1460
if (! (vars[i]->noe == 1) ) {
1461
if (vu->card_conflict()) {
1462
mub->template unmatch<UBC>(vars[i]->get_type());
1463
cre[n_re] = mub;
1464
re[n_re] = vars[i];
1465
re_direct[n_re] = UBC;
1466
n_re++;
1467
}
1468
}
1469
}
1470
}
1471
1472
for (int i = n_val; i--; ) {
1473
if (vals[i]->card_conflict()) {
1474
vals[i]->card_conflict(false);
1475
}
1476
}
1477
}
1478
1479
// because of value propagation it is possible that
1480
// x.size < n_var => hence graphnodes have to be eliminated
1481
// variable size
1482
int xs = x.size();
1483
// graph size (variable partition)
1484
int gs = n_var;
1485
if (gs > xs) {
1486
GECODE_AUTOARRAY(bool, idx_used, gs);
1487
// init idx_use
1488
for (int i = gs; i--; ) {
1489
idx_used[i] = false;
1490
}
1491
// mark remaining indices in x
1492
for (int i = xs; i--; ) {
1493
idx_used[x[i].index()] = true;
1494
}
1495
1496
int j = 0;
1497
for (int i = 0; i < gs && j < x.size(); i++) {
1498
if (i != x[j].index()) {
1499
std::swap(vars[i], vars[x[j].index()]);
1500
}
1501
j++;
1502
}
1503
1504
for (int i = gs; i--; ) {
1505
if (!idx_used[vars[i]->get_info()]) {
1506
// the node to remove
1507
VarNode* rm = vars[i];
1508
// the value node it is assigned to
1509
ValNode* rv = NULL;
1510
Edge* mub = rm->template get_match<UBC>();
1511
Edge* mlb = rm->template get_match<LBC>();
1512
1513
assert(y[rm->xindex].assigned());
1514
int v = y[rm->xindex].val();
1515
for (Edge* e = rm->first(); e != NULL; e = e->next()) {
1516
ValNode* w = e->getVal();
1517
if (e->getVal()->val == v) {
1518
rv = e->getVal();
1519
}
1520
rm->noe--;
1521
w->noe--;
1522
e->del_edge();
1523
e->unlink();
1524
}
1525
1526
// repair upper bound matching
1527
if (mub != NULL) {
1528
if (mub->getVal()->val != v) {
1529
mub->template unmatch<UBC>();
1530
if (!rv->is_matched(UBC)) {
1531
rv->template dec<UBC>();
1532
} else {
1533
// find a blocking variable node
1534
for (Edge* f = rv->first(); f != NULL; f = f->vnext()) {
1535
if (mub != f && f->template matched<UBC>()) {
1536
f->template unmatch<UBC>(rm->get_type());
1537
cre[n_re] = f;
1538
re[n_re] = f->getVar();
1539
re_direct[n_re] = UBC;
1540
n_re++;
1541
break;
1542
}
1543
}
1544
}
1545
}
1546
}
1547
if (mlb != NULL) {
1548
// repair lower bound matching
1549
if (mlb->getVal()->val != v) {
1550
mlb->template unmatch<LBC>();
1551
ValNode* w = mlb->getVal();
1552
if (!w->template matched<LBC>()) {
1553
cre[n_re] = NULL;
1554
re[n_re] = w;
1555
re_direct[n_re] = LBC;
1556
n_re++;
1557
}
1558
if (!rv->is_matched(LBC)) {
1559
rv->template dec<LBC>();
1560
} else {
1561
// find a blocking variable node
1562
for (Edge* f = rv->first(); f != NULL; f = f->vnext()) {
1563
if (mlb != f && f->template matched<LBC>()) {
1564
f->template unmatch<LBC>(rm->get_type());
1565
break;
1566
}
1567
}
1568
}
1569
}
1570
}
1571
node_size--;
1572
vars[i] = vars[--n_var];
1573
}
1574
}
1575
}
1576
1577
// adjust value information
1578
for (int i = n_val; i--; ) {
1579
vals[i]->set_info(n_var + i);
1580
}
1581
1582
// go on with synchronization
1583
assert(x.size() == n_var);
1584
for (int i = n_var; i--; ) {
1585
VarNode* vrn = vars[i];
1586
if(x[i].size() != vrn->noe){
1587
// if the variable is already assigned
1588
if (x[i].assigned()) {
1589
int v = x[i].val();
1590
ValNode* rv = NULL;
1591
int rv_idx = 0;
1592
Edge* mub = vrn->template get_match<UBC>();
1593
if (mub != NULL) {
1594
if (v != mub->getVal()->val) {
1595
mub->template unmatch<UBC>();
1596
cre[n_re] = NULL;
1597
re[n_re] = vrn;
1598
re_direct[n_re] = UBC;
1599
n_re++;
1600
}
1601
}
1602
1603
Edge* mlb = vrn->template get_match<LBC>();
1604
if (mlb != NULL) {
1605
ValNode* vln = mlb->getVal();
1606
if (v != vln->val) {
1607
mlb->template unmatch<LBC>();
1608
int nom = vln->template incid_match<LBC>();
1609
// less values than required
1610
bool cond = nom < vln->kmin();
1611
if (cond) {
1612
cre[n_re] = NULL;
1613
re[n_re] = vln;
1614
re_direct[n_re] = LBC;
1615
n_re++;
1616
}
1617
}
1618
}
1619
1620
for (Edge* e = vrn->first(); e != NULL; e = e->next()){
1621
ValNode* vln = e->getVal();
1622
if (vln->val != v) {
1623
vrn->noe--;
1624
e->getVal()->noe--;
1625
e->del_edge();
1626
e->unlink();
1627
} else {
1628
rv = e->getVal();
1629
rv_idx = rv->kindex();
1630
}
1631
}
1632
} else {
1633
1634
// delete the edge
1635
ViewValues<View> xiter(x[i]);
1636
Edge* mub = vrn->template get_match<UBC>();
1637
Edge* mlb = vrn->template get_match<LBC>();
1638
Edge** p = vrn->adj();
1639
Edge* e = *p;
1640
do {
1641
// search the edge that has to be deleted
1642
while (e != NULL && e->getVal()->val < xiter.val()) {
1643
// Skip edge
1644
e->getVal()->noe--;
1645
vrn->noe--;
1646
e->del_edge();
1647
e->unlink();
1648
e = e ->next();
1649
*p = e;
1650
}
1651
assert(xiter.val() == e->getVal()->val);
1652
1653
// This edge must be kept
1654
e->template free<UBC>();
1655
e->template free<LBC>();
1656
++xiter;
1657
p = e->next_ref();
1658
e = e->next();
1659
} while (xiter());
1660
*p = NULL;
1661
while (e) {
1662
e->getVar()->noe--;
1663
e->getVal()->noe--;
1664
e->del_edge();
1665
e->unlink();
1666
e = e->next();
1667
}
1668
1669
if (mub != NULL){
1670
if (mub->is_deleted()) {
1671
mub->template unmatch<UBC>();
1672
cre[n_re] = NULL;
1673
re[n_re] = mub->getVar();
1674
re_direct[n_re] = UBC;
1675
n_re++;
1676
1677
}
1678
}
1679
1680
//lower bound matching can be zero
1681
if (mlb != NULL) {
1682
if (mlb->is_deleted()) {
1683
ValNode* vln = mlb->getVal();
1684
mlb->template unmatch<LBC>();
1685
int nom = vln->template incid_match<LBC>();
1686
bool cond = nom < vln->kmin();
1687
if (cond) {
1688
cre[n_re] = NULL;
1689
re[n_re] = vln;
1690
re_direct[n_re] = LBC;
1691
n_re++;
1692
}
1693
}
1694
}
1695
}
1696
}
1697
}
1698
1699
for (int i = n_var; i--; ) {
1700
vars[i]->set_info(i);
1701
x[i].index(i);
1702
}
1703
1704
for (int i = n_val; i--; ) {
1705
vals[i]->set_info(n_var + i);
1706
}
1707
1708
// std::cout << "before end\n";
1709
1710
if (n_re == 0) {
1711
// no repair needed
1712
// std::cout << "no repair\n";
1713
return true;
1714
} else {
1715
// start repair
1716
1717
// resolve conflicts
1718
for (int i = n_re; i--; ) {
1719
if ( (cre[i] != NULL && cre[i]->is_deleted()) ||
1720
(re[i]->removed()) ) {
1721
// the conflict exists no more
1722
cre[i] = cre[--n_re];
1723
re[i] = re[n_re];
1724
re_direct[i] = re_direct[n_re];
1725
}
1726
}
1727
1728
bool repaired = true;
1729
while (n_re > 0) {
1730
n_re--;
1731
if (!re[n_re]->is_matched(re_direct[n_re])) {
1732
if (re_direct[n_re] == UBC) {
1733
repaired &= augmenting_path<UBC>(re[n_re]);
1734
} else {
1735
repaired &= augmenting_path<LBC>(re[n_re]);
1736
}
1737
}
1738
}
1739
1740
1741
return repaired;
1742
}
1743
}
1744
1745
template <class View, class Card, bool isView> template <BC direction>
1746
forceinline bool
1747
VarValGraph<View, Card, isView>::narrow(Space* home){
1748
1749
bool shared = false;
1750
for (int i = n_var; i--; ) {
1751
VarNode* vrn = vars[i];
1752
if (vrn->noe == 1) {
1753
Edge* e = vrn->first();
1754
shared |= x[i].modified();
1755
ValNode* v = e->getVal();
1756
e->template free<direction>();
1757
x[i].eq(home, v->val);
1758
v->inc();
1759
}
1760
}
1761
1762
for (int i = n_val; i--; ) {
1763
ValNode* v = vals[i];
1764
if (v->noe > 0) {
1765
1766
if (isView) {
1767
ModEvent klq = k[i].lq(home, v->noe);
1768
if (me_failed(klq)) {
1769
failed(true);
1770
return false;
1771
}
1772
}
1773
1774
1775
// If the maximum number of occurences of a value is reached
1776
// it cannot be consumed by another view
1777
1778
if (v->kcount() == v->kmax()) {
1779
k[i].counter(v->kcount());
1780
// std::cout << "eq on : " << v->val<<"\n";
1781
if (isView) {
1782
ModEvent me = k[i].eq(home, k[i].counter());
1783
if (me_failed(me)) {
1784
failed(true);
1785
return false;
1786
}
1787
}
1788
1789
bool delall = false;
1790
if (v->card_conflict() &&
1791
v->kmax() == v->kcount() &&
1792
v->noe > v->kmax()) {
1793
delall = true;
1794
// std::cout << "delall : " << v->val<<"\n";
1795
}
1796
1797
for (Edge* e = v->last(); e != NULL; e = e->vprev()) {
1798
VarNode* vrn = e->getVar();
1799
if (vrn->noe == 1) {
1800
vrn->noe--;
1801
v->noe--;
1802
int vi= vrn->get_info();
1803
1804
int n = x.size();
1805
x[vi] = x[--n];
1806
x[vi].index(vi);
1807
x.size(n);
1808
1809
vars[vi] = vars[--n_var];
1810
vars[vi]->set_info(vi);
1811
node_size--;
1812
e->del_edge();
1813
e->unlink();
1814
} else {
1815
if (delall) {
1816
x[vrn->get_info()].nq(home, v->val);
1817
vrn->noe--;
1818
v->noe--;
1819
e->del_edge();
1820
e->unlink();
1821
}
1822
}
1823
}
1824
1825
} else {
1826
int cur = v->kcount();
1827
if (cur > 0) {
1828
v->kcount(0);
1829
}
1830
}
1831
}
1832
}
1833
1834
for (int i = n_var; i--; ) {
1835
vars[i]->set_info(i);
1836
x[i].index(i);
1837
}
1838
1839
for (int i = n_val; i--; ) {
1840
vals[i]->set_info(n_var + i);
1841
}
1842
1843
for (int i = n_var; i--; ) {
1844
if (vars[i]->noe > 1){
1845
for (Edge* e = vars[i]->first(); e != NULL; e = e->next()){
1846
bool keepedge = false;
1847
keepedge = (e->template matched<direction>() ||
1848
e->template used<direction>());
1849
if (!keepedge) {
1850
ValNode* v = e->getVal();
1851
shared |= x[i].modified();
1852
x[i].nq(home, v->val);
1853
} else {
1854
e->template free<direction>();
1855
}
1856
}
1857
}
1858
}
1859
1860
1861
// min_require(home);
1862
return shared;
1863
}
1864
1865
template <class View, class Card, bool isView> template <BC direction>
1866
forceinline bool
1867
VarValGraph<View, Card, isView>::maximum_matching(void){
1868
int required_size = 0;
1869
int card_match = 0;
1870
1871
if (direction == UBC) {
1872
required_size = n_var;
1873
} else {
1874
required_size = sum_min;
1875
}
1876
1877
// find an intial matching in O(n*d)
1878
// greedy algorithm
1879
1880
for (int i = n_val; i--; ){
1881
ValNode* vln = vals[i];
1882
for (Edge* e = vln->first(); e != NULL ; e = e->vnext()) {
1883
VarNode* vrn = e->getVar();
1884
if (!vrn->template matched<direction>() &&
1885
!vln->template matched<direction>()) {
1886
e->template match<direction>();
1887
card_match++;
1888
}
1889
}
1890
}
1891
1892
if (card_match < required_size) {
1893
if (direction == LBC) {
1894
// collect free value nodes
1895
GECODE_AUTOARRAY(ValNode*, free, n_val);
1896
int f = 0;
1897
// find failed nodes
1898
for (int i = n_val; i--; ) {
1899
ValNode* vln = vals[i];
1900
if (!vln->template matched<direction>()) {
1901
free[f++] = vln;
1902
}
1903
}
1904
1905
for (int i = 0; i < f; i++) {
1906
while(!free[i]->template matched<direction>()) {
1907
if (augmenting_path<direction>(free[i])) {
1908
card_match++;
1909
} else {
1910
break;
1911
}
1912
}
1913
}
1914
} else {
1915
GECODE_AUTOARRAY(VarNode*, free, n_var);
1916
int f = 0;
1917
// find failed nodes
1918
for (int i = n_var; i--; ) {
1919
VarNode* vrn = vars[i];
1920
if (!vrn->template matched<direction>()) {
1921
free[f++] = vrn;
1922
}
1923
}
1924
1925
for (int i = 0; i < f; i++) {
1926
if (!free[i]->template matched<direction>()) {
1927
if (augmenting_path<direction>(free[i])) {
1928
card_match++;
1929
}
1930
}
1931
}
1932
}
1933
}
1934
return (card_match >= required_size);
1935
}
1936
1937
template <class View, class Card, bool isView> template<BC direction>
1938
forceinline bool
1939
VarValGraph<View, Card, isView>::augmenting_path(VVGNode* v){
1940
1941
Support::StaticStack<VVGNode*> ns(node_size);
1942
GECODE_AUTOARRAY(bool, visited, node_size);
1943
GECODE_AUTOARRAY(Edge*, start, node_size);
1944
1945
// augmenting path starting in a free var node
1946
assert(!v->is_matched(direction));
1947
1948
// keep track of the nodes that have already been visited
1949
VVGNode* sn = v;
1950
1951
// mark the start partition
1952
bool sp = sn->get_type();
1953
1954
// nodes in sp only follow free edges
1955
// nodes in V - sp only follow matched edges
1956
1957
for (int i = node_size; i--; ){
1958
visited[i] = false;
1959
}
1960
1961
for (int i = node_size; i--; ){
1962
if (i >= n_var) {
1963
vals[i - n_var]->inedge(NULL);
1964
start[i] = vals[i - n_var]->first();
1965
} else {
1966
vars[i]->inedge(NULL);
1967
start[i] = vars[i]->first();
1968
}
1969
}
1970
1971
v->inedge(NULL);
1972
ns.push(v);
1973
visited[v->get_info()] = true;
1974
while (!ns.empty()) {
1975
VVGNode* v = ns.top();
1976
Edge* e = NULL;
1977
if (v->get_type() == sp) {
1978
// follow next free edge
1979
e = start[v->get_info()];
1980
while (e != NULL && e->template matched<direction>()) {
1981
e = e->next(v->get_type());
1982
}
1983
} else {
1984
e = start[v->get_info()];
1985
while (e != NULL && !e->template matched<direction>()) {
1986
e = e->next(v->get_type());
1987
}
1988
start[v->get_info()] = e;
1989
}
1990
if (e != NULL) {
1991
start[v->get_info()] = e->next(v->get_type());
1992
VVGNode* w = e->getMate(v->get_type());
1993
if (!visited[w->get_info()]) {
1994
// unexplored path
1995
if (!w->is_matched(direction) && w->get_type() != sp) {
1996
if (v->inedge() != NULL) {
1997
// augmenting path of length l > 1
1998
e->template match<direction>();
1999
break;
2000
} else {
2001
// augmenting path of length l = 1
2002
e->template match<direction>();
2003
ns.pop();
2004
return true;
2005
}
2006
} else {
2007
w->inedge(e);
2008
visited[w->get_info()] = true;
2009
// find matching edge m incident with w
2010
ns.push(w);
2011
}
2012
}
2013
} else {
2014
// tried all outgoing edges without finding an augmenting path
2015
ns.pop();
2016
}
2017
}
2018
2019
bool pathfound = false;
2020
if (!ns.empty()) {
2021
pathfound = true;
2022
}
2023
2024
while (!ns.empty()) {
2025
VVGNode* t = ns.top();
2026
if (t != sn) {
2027
Edge* in = t->inedge();
2028
if (t->get_type() != sp) {
2029
assert(in != NULL);
2030
in->template match<direction>();
2031
} else {
2032
// avoid defects
2033
if (!sp) {
2034
in->template unmatch<direction>(!sp);
2035
} else {
2036
in->template unmatch<direction>();
2037
}
2038
}
2039
ns.pop();
2040
} else {
2041
ns.pop();
2042
}
2043
}
2044
return pathfound;
2045
}
2046
2047
template <class View, class Card, bool isView> template<BC direction>
2048
forceinline void
2049
VarValGraph<View, Card, isView>::free_alternating_paths(void){
2050
2051
Support::StaticStack<VVGNode*> ns(node_size);
2052
GECODE_AUTOARRAY(bool, visited, node_size);
2053
// keep track of the nodes that have already been visited
2054
for (int i = node_size; i--; ){
2055
visited[i] = false;
2056
}
2057
2058
if (direction == LBC) {
2059
// after a maximum matching on the value nodes there still can be
2060
// free value nodes, hence we have to consider ALL nodes whether
2061
// they are the starting point of an even alternating path in G
2062
for (int i = n_var; i--; ){
2063
if(!vars[i]->is_matched(LBC)){
2064
// unmatched var-node
2065
ns.push(vars[i]);
2066
visited[vars[i]->get_info()] = true;
2067
}
2068
}
2069
} else {
2070
// clearly, after a maximum matching on the x variables
2071
// corresponding to a set cover on x there are NO free var nodes
2072
// std::cout << "alt_path for ubm: \n";
2073
// after max_match_ub there can only be free val-nodes
2074
for (int i = n_val; i--; ){
2075
if(!vals[i]->is_matched(UBC)){
2076
// still capacities left
2077
ns.push(vals[i]);
2078
visited[vals[i]->get_info()] = true;
2079
}
2080
}
2081
}
2082
2083
while(!ns.empty()){
2084
VVGNode* node = ns.top();
2085
ns.pop();
2086
if (node->get_type()) {
2087
// ValNode
2088
ValNode* vln = reinterpret_cast<ValNode*> (node);
2089
for (Edge* cur = vln->first(); cur != NULL; cur = cur->vnext()){
2090
VarNode* mate = cur->getVar();
2091
bool follow = false;
2092
switch (direction) {
2093
// edges in M_l are directed from values to variables
2094
case LBC: {
2095
follow = cur->template matched<direction>();
2096
break;
2097
}
2098
case UBC: {
2099
follow = !cur->template matched<direction>();
2100
break;
2101
}
2102
}
2103
if (follow) {
2104
// mark the edge
2105
cur->template use<direction>();
2106
if (!visited[mate->get_info()]) {
2107
ns.push(mate);
2108
visited[mate->get_info()] = true;
2109
}
2110
}
2111
}
2112
} else {
2113
// VarNode
2114
VarNode* vrn = reinterpret_cast<VarNode*> (node);
2115
switch (direction) {
2116
// after LBC-matching we can follow every unmatched edge
2117
case LBC: {
2118
for (Edge* cur = vrn->first(); cur != NULL; cur = cur->next()){
2119
ValNode* mate = cur->getVal();
2120
if (!cur->template matched<LBC>()) {
2121
cur->template use<LBC>();
2122
if (!visited[mate->get_info()]) {
2123
ns.push(mate);
2124
visited[mate->get_info()] = true;
2125
}
2126
}
2127
}
2128
break;
2129
}
2130
// after ub-matching we can only follow a matched edge
2131
case UBC: {
2132
Edge* cur = vrn->template get_match<UBC>();
2133
if (cur != NULL) {
2134
cur->template use<UBC>();
2135
ValNode* mate = cur->getVal();
2136
if (!visited[mate->get_info()]) {
2137
ns.push(mate);
2138
visited[mate->get_info()] = true;
2139
}
2140
}
2141
break;
2142
}
2143
}
2144
}
2145
}
2146
}
2147
2148
template <class View, class Card, bool isView> template <BC direction>
2149
forceinline void
2150
VarValGraph<View, Card, isView>::dfs(VVGNode* v,
2151
bool inscc[],
2152
bool in_unfinished[],
2153
int dfsnum[],
2154
Support::StaticStack<VVGNode*>& roots,
2155
Support::StaticStack<VVGNode*>& unfinished,
2156
int& count){
2157
count++;
2158
int v_index = v->get_info();
2159
dfsnum[v_index] = count;
2160
inscc[v_index] = true;
2161
in_unfinished[v_index] = true;
2162
2163
unfinished.push(v);
2164
roots.push(v);
2165
for (Edge* e = v->first(); e != NULL; e = e->next(v->get_type())) {
2166
bool condition = false;
2167
// LBC-matching
2168
if (direction == LBC) {
2169
// ValNode
2170
if (v->get_type()) {
2171
condition = e->template matched<LBC>();
2172
} else {
2173
condition = !e->template matched<LBC>();
2174
}
2175
// UBC - matching
2176
} else {
2177
if (v->get_type()) {
2178
// in an upper bound matching a valnode only can follow unmatched edges
2179
condition = !e->template matched<UBC>();
2180
} else {
2181
condition = e->template matched<UBC>();
2182
}
2183
}
2184
if (condition) {
2185
VVGNode* w = e->getMate(v->get_type());
2186
int w_index = w->get_info();
2187
2188
assert(w_index < node_size);
2189
if (!inscc[w_index]) {
2190
// w is an uncompleted scc
2191
w->inedge(e);
2192
dfs<direction>(w, inscc, in_unfinished, dfsnum,
2193
roots, unfinished, count);
2194
} else {
2195
if (in_unfinished[w_index]) {
2196
// even alternating cycle found mark the edge closing the cycle,
2197
// completing the scc
2198
e->template use<direction>();
2199
// if w belongs to an scc we detected earlier
2200
// merge components
2201
assert(roots.top()->get_info() < node_size);
2202
while (dfsnum[roots.top()->get_info()] > dfsnum[w_index]) {
2203
roots.pop();
2204
}
2205
}
2206
}
2207
}
2208
}
2209
2210
if (v == roots.top()) {
2211
while (v != unfinished.top()) {
2212
// w belongs to the scc with root v
2213
VVGNode* w = unfinished.top();
2214
Edge* ie = w->inedge();
2215
ie->template use<direction>();
2216
in_unfinished[w->get_info()] = false;
2217
unfinished.pop();
2218
}
2219
assert(v == unfinished.top());
2220
in_unfinished[v_index] = false;
2221
roots.pop();
2222
unfinished.pop();
2223
}
2224
}
2225
2226
template <class View, class Card, bool isView> template <BC direction>
2227
forceinline void
2228
VarValGraph<View, Card, isView>::strongly_connected_components(void){
2229
2230
GECODE_AUTOARRAY(bool, inscc, node_size);
2231
GECODE_AUTOARRAY(bool, in_unfinished, node_size);
2232
GECODE_AUTOARRAY(int, dfsnum, node_size);
2233
2234
for (int i = node_size; i--; ) {
2235
inscc[i] = false;
2236
in_unfinished[i] = false;
2237
dfsnum[i] = 0;
2238
}
2239
2240
int count = 0;
2241
Support::StaticStack<VVGNode*> roots(node_size);
2242
Support::StaticStack<VVGNode*> unfinished(node_size);
2243
2244
for (int i = n_var; i--; ) {
2245
dfs<direction>(vars[i], inscc, in_unfinished, dfsnum,
2246
roots, unfinished, count);
2247
}
2248
}
2249
2250
2251
template <class View, class Card, bool isView>
2252
forceinline void
2253
VarValGraph<View, Card, isView>::print_match(void) {
2254
print_matching<UBC>();
2255
print_matching<LBC>();
2256
}
2257
2258
2259
template <class View, class Card, bool isView>
2260
forceinline void
2261
VarValGraph<View, Card, isView>::print_edges(void) {
2262
for (int i = 0; i < n_var; i++) {
2263
std::cout << vars[i]->var<<": ";
2264
for (Edge* e = vars[i]->first(); e != NULL; e = e->next()) {
2265
std::cout << e->getVal()->val<<"("
2266
<< e->template matched<LBC>() << ","
2267
<< e->template matched<UBC>() << ","
2268
<< e->template used<LBC>() << ","
2269
<< e->template used<UBC>() <<") ";
2270
}
2271
std::cout <<"\n";
2272
}
2273
std::cout <<"\n";
2274
}
2275
2276
// for debugging purposes
2277
template <class View, class Card, bool isView> template <BC direction>
2278
forceinline void
2279
VarValGraph<View, Card, isView>::print_matching(void) {
2280
if (direction == UBC) {
2281
std::cout << "UBM - check:\n";
2282
} else {
2283
std::cout << "LBM - check:\n";
2284
}
2285
2286
for (int i = 0; i < n_var; i++ ){
2287
std::cout << vars[i]->var <<" ";
2288
if (vars[i]->template matched<direction>()) {
2289
if (vars[i]->template get_match<direction>() == NULL) {
2290
std::cout << "N ";
2291
} else {
2292
std::cout << vars[i]->template get_match<direction>() << " ";
2293
std::cout << vars[i]->template get_match<direction>()->getVal()->val << " ";
2294
}
2295
} else {
2296
// is not matched
2297
std::cout << "% ";
2298
}
2299
std::cout <<"\n";
2300
}
2301
std::cout <<"\n";
2302
2303
for (int i = 0; i < n_val; i++ ){
2304
(vals[i]->template matched<direction>())? std::cout << "X " : std::cout << "- ";
2305
std::cout << vals[i]->template cap<direction>() << " ";
2306
std::cout << vals[i]->val << " ";
2307
std::cout <<"\n";
2308
}
2309
std::cout <<"\n";
2310
}
2311
2312
template <class View, class Card, bool isView>
2313
forceinline void
2314
VarValGraph<View, Card, isView>::print_graph(void) {
2315
std::cout << "Graph-size = "<<node_size<<" ";
2316
std::cout << "sum_min ="<<sum_min << " & "
2317
<< "sum_max ="<<sum_max << "\n";
2318
std::cout << "X-Partition: \n";
2319
for (int i = 0; i < n_var; i++) {
2320
VarNode* vrn = vars[i];
2321
std::cout << "X("<<vars[i]->get_info()<<") ";
2322
std::cout << "["<<vrn->xindex <<"]";
2323
std::cout << "|"<<vrn->noe <<"|";
2324
std::cout << "{";
2325
for (Edge* e = vrn->first(); e != NULL; e = e->next()){
2326
std::cout << e->getVal()->val<<",";
2327
}
2328
std::cout <<"}\t";
2329
std::cout << "F"<<vrn->first() << ", L" << vrn->last() << " ";
2330
std::cout <<"\n";
2331
}
2332
std::cout <<"\n";
2333
2334
std::cout << "V-Partition: \n";
2335
for (int i = 0; i < n_val; i++) {
2336
ValNode* vln = vals[i];
2337
std::cout << vln->val <<" ";
2338
std::cout << "V(" << i << ") ";
2339
std::cout << "k(" << vln->kmin() << "," <<vln->kmax() << ") ";
2340
std::cout << "c(" << vln->template cap<LBC>() << ","
2341
<< vln->template cap<UBC>() << ") ";
2342
std::cout << "ublow: "<<vln->get_maxlow() <<" ";
2343
std::cout << "|"<<vln->noe <<"|";
2344
std::cout << "{";
2345
if (vln->noe == 0 || vln->first() == NULL) {
2346
std::cout << "EMPTY";
2347
} else {
2348
for(Edge* c = vln->first(); c != NULL; c = c->vnext()){
2349
std::cout << c->getVar()->var << ",";
2350
}
2351
}
2352
std::cout <<"}\t";
2353
std::cout <<"\t";
2354
if (vln->noe == 0 || vln->first() == NULL) {
2355
std::cout <<"no-ptr";
2356
} else {
2357
std::cout << "F"<<vln->first() << ", L" <<vln->last() << " ";
2358
}
2359
std::cout <<"\n";
2360
}
2361
std::cout <<"\n";
2362
}
2363
2364
2365
template <class View, class Card, bool isView>
2366
forceinline
2367
VarValGraph<View, Card, isView>::~VarValGraph(void){
2368
Memory::free(mem);
2369
}
2370
2371
template <class View, class Card, bool isView>
2372
forceinline void*
2373
VarValGraph<View, Card, isView>::operator new(size_t t){
2374
return Memory::malloc(t);
2375
}
2376
2377
template <class View, class Card, bool isView>
2378
forceinline void
2379
VarValGraph<View, Card, isView>::operator delete(void* p){
2380
Memory::free(p);
2381
}
2382
2383
}}}
2384
2385
// STATISTICS: int-prop
Loggerhead is a web-based interface for Breezy
Version: 2.0.1