Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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
34namespace Gecode { namespace Int { namespace Sorted {
35
52
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
Item used to construct the OfflineMin sequence.
Definition sortsup.hpp:117
Offline-Min datastructure Used to compute the perfect matching between the unsorted views x and the s...
Definition sortsup.hpp:146
void unite(int a, int b, int c)
Unite two sets a and b and label the union with c.
Definition sortsup.hpp:210
void makeset(void)
Initialization of the datastructure.
Definition sortsup.hpp:227
View arrays.
Definition array.hpp:253
Sorted propagators
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
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
Finite domain integers.
Gecode toplevel namespace
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition sequence.cpp:47
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition set.hh:773
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:773
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
Definition set.hh:773