Generated on Tue Mar 24 2020 14:04:04 for Gecode by doxygen 1.8.17
matching.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5  *
6  * Copyright:
7  * Patrick Pekczynski, 2004
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 namespace Gecode { namespace Int { namespace Sorted {
35 
53  template<class View>
54  inline bool
56  int tau[], int phi[], OfflineMinItem sequence[], int vertices[]) {
57 
58  int xs = x.size();
59  OfflineMin seq(sequence, vertices, xs);
60  int s = 0;
61  seq.makeset();
62 
63  for (int z = 0; z < xs; z++) { // forall y nodes
64  int maxy = y[z].max();
65  // creating the sequence of inserts and extractions from the queue
66  for( ; s <xs && x[s].min() <= maxy; s++) {
67  seq[s].iset = z;
68  seq[z].rank++;
69  }
70  }
71 
72  // offline-min-procedure
73  for (int i = 0; i < xs; i++) {
74  // the upper bound of the x-node should be minimal
75  int perm = tau[i];
76  // find the iteration where \tau(i) became a maching candidate
77  int iter = seq[perm].iset;
78  if (iter<0)
79  return false;
80  int j = 0;
81  j = seq.find_pc(iter);
82  // check whether the sequence is valid
83  if (j >= xs)
84  return false;
85  // if there is no intersection between the matching candidate
86  // and the y node then there exists NO perfect matching
87  if (x[perm].max() < y[j].min())
88  return false;
89  phi[j] = perm;
90  seq[perm].iset = -5; //remove from candidate set
91  int sqjsucc = seq[j].succ;
92  if (sqjsucc < xs) {
93  seq.unite(j,sqjsucc,sqjsucc);
94  } else {
95  seq[seq[j].root].name = sqjsucc; // end of sequence achieved
96  }
97 
98  // adjust tree list
99  int pr = seq[j].pred;
100  if (pr != -1)
101  seq[pr].succ = sqjsucc;
102  if (sqjsucc != xs)
103  seq[sqjsucc].pred = pr;
104  }
105  return true;
106  }
107 
112  template<class View>
113  inline bool
115  int tau[], int phiprime[], OfflineMinItem sequence[],
116  int vertices[]) {
117 
118  int xs = x.size();
119  OfflineMin seq(sequence, vertices, xs);
120  int s = xs - 1;
121  seq.makeset();
122 
123  int miny = 0;
124  for (int z = xs; z--; ) { // forall y nodes
125  miny = y[z].min();
126  // creating the sequence of inserts and extractions from the queue
127  for ( ; s > -1 && x[tau[s]].max() >= miny; s--) {
128  seq[tau[s]].iset = z;
129  seq[z].rank++;
130  }
131  }
132 
133  // offline-min-procedure
134  for (int i = xs; i--; ) {
135  int perm = i;
136  int iter = seq[perm].iset;
137  if (iter < 0)
138  return false;
139  int j = 0;
140  j = seq.find_pc(iter);
141  if (j <= -1)
142  return false;
143  // if there is no intersection between the matching candidate
144  // and the y node then there exists NO perfect matching
145  if (x[perm].min() > y[j].max())
146  return false;
147  phiprime[j] = perm;
148  seq[perm].iset = -5;
149  int sqjsucc = seq[j].pred;
150  if (sqjsucc >= 0) {
151  seq.unite(j, sqjsucc, sqjsucc);
152  } else {
153  seq[seq[j].root].name = sqjsucc; // end of sequence achieved
154  }
155 
156  // adjust tree list
157  int pr = seq[j].succ;
158  if (pr != xs)
159  seq[pr].pred = sqjsucc;
160  if (sqjsucc != -1)
161  seq[sqjsucc].succ = pr;
162  }
163  return true;
164  }
165 
166 }}}
167 
168 // STATISTICS: int-prop
169 
Post propagator for SetVar x
Definition: set.hh:767
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
void makeset(void)
Initialization of the datastructure.
Definition: sortsup.hpp:227
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition: set.hh:767
Gecode toplevel namespace
int find_pc(int x)
Definition: sortsup.hpp:196
void unite(int a, int b, int c)
Unite two sets a and b and label the union with c.
Definition: sortsup.hpp:210
Item used to construct the OfflineMin sequence.
Definition: sortsup.hpp:117
bool glover(ViewArray< View > &x, ViewArray< View > &y, int tau[], int phi[], OfflineMinItem sequence[], int vertices[])
Glover's maximum matching in a bipartite graph.
Definition: matching.hpp:55
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel)
Post propagator for .
Definition: sequence.cpp:47
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
View arrays.
Definition: array.hpp:253
Offline-Min datastructure Used to compute the perfect matching between the unsorted views x and the s...
Definition: sortsup.hpp:146
bool revglover(ViewArray< View > &x, ViewArray< View > &y, int tau[], int phiprime[], OfflineMinItem sequence[], int vertices[])
Symmetric glover function for the upper domain bounds.
Definition: matching.hpp:114
Gecode::IntArgs i({1, 2, 3, 4})
Bounds consistent sortedness propagator.
Definition: sorted.hh:59