main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Mar 24 2020 14:04:04 for Gecode by
doxygen
1.8.17
gecode
int
sorted
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
55
glover
(
ViewArray<View>
&
x
,
ViewArray<View>
&
y
,
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
114
revglover
(
ViewArray<View>
&
x
,
ViewArray<View>
&
y
,
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
Gecode::x
Post propagator for SetVar x
Definition:
set.hh:767
Gecode::y
Post propagator for SetVar SetOpType SetVar y
Definition:
set.hh:767
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition:
arithmetic.cpp:49
Gecode::Int::Sorted::OfflineMin::makeset
void makeset(void)
Initialization of the datastructure.
Definition:
sortsup.hpp:227
Gecode::z
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition:
set.hh:767
Gecode
Gecode toplevel namespace
Gecode::Int::Sorted::OfflineMin::find_pc
int find_pc(int x)
Definition:
sortsup.hpp:196
Gecode::Int::Sorted::OfflineMin::unite
void unite(int a, int b, int c)
Unite two sets a and b and label the union with c.
Definition:
sortsup.hpp:210
Gecode::Int::Sorted::OfflineMinItem
Item used to construct the OfflineMin sequence.
Definition:
sortsup.hpp:117
Gecode::Int::Sorted::glover
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
Gecode::sequence
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel)
Post propagator for .
Definition:
sequence.cpp:47
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition:
arithmetic.cpp:67
Gecode::ViewArray
View arrays.
Definition:
array.hpp:253
Gecode::Int::Sorted::OfflineMin
Offline-Min datastructure Used to compute the perfect matching between the unsorted views x and the s...
Definition:
sortsup.hpp:146
Gecode::Int::Sorted::revglover
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
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::Int::Sorted::Sorted
Bounds consistent sortedness propagator.
Definition:
sorted.hh:59