main page
modules
namespaces
classes
files
Gecode home
Generated on Mon Jul 27 2020 00:00:00 for Gecode by
doxygen
1.8.18
gecode
int
nvalues
graph.hpp
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Christian Schulte <schulte@gecode.org>
5
*
6
* Copyright:
7
* Christian Schulte, 2011
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
NValues {
35
36
forceinline
37
Graph::Graph
(
void
)
38
: n_matched(0) {}
39
40
forceinline
int
41
Graph::size
(
void
)
const
{
42
return
n_matched
;
43
}
44
45
forceinline
void
46
Graph::init
(
Space
& home,
const
ValSet
& vs,
const
ViewArray<IntView>
&
x
) {
47
using namespace
ViewValGraph;
48
n_view
=
x
.size() + vs.
size
();
49
view
= home.
alloc
<ViewNode<IntView>*>(
n_view
);
50
51
// Create nodes corresponding to the value set vs
52
{
53
int
i
=
x
.size();
54
ValSet::Ranges
vsr(vs);
55
ValNode<IntView>**
v
= &
val
;
56
for
(
Iter::Ranges::ToValues<ValSet::Ranges>
n
(vsr);
n
(); ++
n
) {
57
// Create view node
58
view
[
i
] =
new
(home) ViewNode<IntView>();
59
// Create and link value node
60
ValNode<IntView>* nv =
new
(home) ValNode<IntView>(
n
.val());
61
*
v
= nv;
v
= nv->next_val_ref();
62
// Create and link single edge
63
Edge<IntView>** e =
view
[
i
]->
val_edges_ref
();
64
*e =
new
(home) Edge<IntView>(nv,
view
[
i
],NULL);
65
// Match edge
66
(*e)->
revert
(
view
[
i
]); nv->matching(*e);
67
i
++;
68
}
69
*
v
= NULL;
70
n_val
= vs.
size
();
71
n_matched
= vs.
size
();
72
assert(
i
-
x
.size() == vs.
size
());
73
}
74
75
// Initialize real view nodes
76
for
(
int
i
=0;
i
<
x
.size();
i
++) {
77
view
[
i
] =
new
(home) ViewNode<IntView>(
x
[
i
]);
78
ViewValGraph::Graph<IntView>::init
(home,
view
[
i
]);
79
}
80
81
// Match the real view nodes, if possible
82
Region
r
;
83
ViewNodeStack
m(
r
,
n_view
);
84
for
(
int
i
=0;
i
<
x
.size();
i
++)
85
if
(
match
(m,
view
[
i
]))
86
n_matched
++;
87
}
88
89
forceinline
void
90
Graph::sync
(
void
) {
91
using namespace
ViewValGraph;
92
Region
r
;
93
94
// Whether to rematch
95
bool
rematch =
false
;
96
97
// Synchronize nodes
98
for
(
int
i
=0;
i
<
n_view
;
i
++) {
99
ViewNode<IntView>*
x
=
view
[
i
];
100
// Skip faked view nodes, they correspond to values in the value set
101
if
(!
x
->fake()) {
102
if
(
x
->changed()) {
103
ViewRanges<IntView>
rx(
x
->view());
104
Edge<IntView>* m =
x
->matched() ?
x
->edge_fst() : NULL;
105
Edge<IntView>**
p
=
x
->val_edges_ref();
106
Edge<IntView>* e = *
p
;
107
GECODE_ASSUME
(e != NULL);
108
do
{
109
while
(e->val(
x
)->val() < rx.
min
()) {
110
// Skip edge
111
e->unlink(); e->mark();
112
e = e->next_edge();
113
}
114
*
p
= e;
115
assert(rx.
min
() == e->val(
x
)->val());
116
// This edges must be kept
117
for
(
unsigned
int
j=rx.
width
(); j--; ) {
118
e->free();
119
p
= e->next_edge_ref();
120
e = e->next_edge();
121
}
122
++rx;
123
}
while
(rx());
124
*
p
= NULL;
125
while
(e != NULL) {
126
e->unlink(); e->mark();
127
e = e->next_edge();
128
}
129
if
((m != NULL) && m->marked()) {
130
// Matching has been deleted!
131
m->val(
x
)->matching(NULL);
132
rematch =
true
;
133
n_matched
--;
134
}
135
}
else
{
136
// Just free edges
137
for
(Edge<IntView>* e=
x
->val_edges(); e != NULL; e = e->next_edge())
138
e->free();
139
}
140
}
141
}
142
143
if
(rematch) {
144
ViewNodeStack
m(
r
,
n_view
);
145
for
(
int
i
=0;
i
<
n_view
;
i
++)
146
if
(!
view
[
i
]->matched() &&
match
(m,
view
[
i
]))
147
n_matched
++;
148
}
149
}
150
151
forceinline
bool
152
Graph::mark
(
void
) {
153
using namespace
ViewValGraph;
154
Region
r
;
155
156
int
n_view_visited = 0;
157
{
158
// Marks all edges as used that are on simple paths in the graph
159
// that start from a free value node by depth-first-search
160
Support::StaticStack<ValNode<IntView>
*,
Region
> visit(
r
,
n_val
);
161
162
// Insert all free value nodes
163
count
++;
164
{
165
ValNode<IntView>**
v
= &
val
;
166
while
(*
v
!= NULL)
167
// Is the node free?
168
if
(!(*v)->matching()) {
169
// Eliminate empty value nodes
170
if
((*v)->empty()) {
171
*
v
= (*v)->next_val();
172
n_val
--;
173
}
else
{
174
(*v)->min =
count
;
175
visit.
push
(*
v
);
176
v
= (*v)->next_val_ref();
177
}
178
}
else
{
179
v
= (*v)->next_val_ref();
180
}
181
}
182
183
// Invariant: only value nodes are on the stack!
184
while
(!visit.
empty
()) {
185
ValNode<IntView>*
n
= visit.
pop
();
186
for
(Edge<IntView>* e =
n
->edge_fst(); e !=
n
->edge_lst();
187
e = e->next()) {
188
// Is the view node is matched: the path must be alternating!
189
ViewNode<IntView>*
x
= e->view(
n
);
190
if
(
x
->matched()) {
191
// Mark the edge as used
192
e->use();
193
if
(
x
->min <
count
) {
194
n_view_visited++;
195
x
->min =
count
;
196
assert(
x
->edge_fst()->next() ==
x
->edge_lst());
197
ValNode<IntView>* m =
x
->edge_fst()->val(
x
);
198
x
->edge_fst()->use();
199
if
(m->min <
count
) {
200
m->min =
count
;
201
visit.
push
(m);
202
}
203
}
204
}
205
}
206
}
207
208
}
209
210
if
(n_view_visited <
n_view
) {
211
// Mark all edges as used starting from a free view node on
212
// an alternating path by depth-first search.
213
Support::StaticStack<ViewNode<IntView>
*,
Region
> visit(
r
,
n_view
);
214
215
// Insert all free view nodes
216
count
++;
217
for
(
int
i
=0;
i
<
n_view
;
i
++)
218
if
(!
view
[
i
]->matched()) {
219
view
[
i
]->
min
=
count
;
220
visit.
push
(
view
[
i
]);
221
}
222
223
// Invariant: only view nodes are on the stack!
224
while
(!visit.
empty
()) {
225
n_view_visited++;
226
ViewNode<IntView>*
x
= visit.
pop
();
227
for
(Edge<IntView>* e =
x
->val_edges(); e != NULL; e = e->next_edge())
228
// Consider only free edges
229
if
(e !=
x
->edge_fst()) {
230
ValNode<IntView>*
n
= e->val(
x
);
231
// Is there a matched edge from the value node to a view node?
232
if
(
n
->matching() != NULL) {
233
e->use();
234
n
->matching()->use();
235
ViewNode<IntView>*
y
=
n
->matching()->view(
n
);
236
if
(
y
->min <
count
) {
237
y
->min =
count
;
238
visit.
push
(
y
);
239
}
240
}
241
}
242
}
243
244
}
245
246
if
(n_view_visited <
n_view
) {
247
scc
();
248
return
true
;
249
}
else
{
250
return
false
;
251
}
252
}
253
254
forceinline
ExecStatus
255
Graph::prune
(
Space
& home) {
256
using namespace
ViewValGraph;
257
// Tell constraints and also eliminate nodes and edges
258
for
(
int
i
=
n_view
;
i
--; ) {
259
ViewNode<IntView>*
x
=
view
[
i
];
260
if
(!
x
->fake()) {
261
if
(
x
->matched() && !
x
->edge_fst()->used(
x
)) {
262
GECODE_ME_CHECK
(
x
->view().eq(home,
x
->edge_fst()->val(
x
)->val()));
263
x
->edge_fst()->val(
x
)->matching(NULL);
264
for
(Edge<IntView>* e =
x
->val_edges(); e != NULL; e=e->next_edge())
265
e->unlink();
266
view
[
i
] =
view
[--
n_view
];
267
}
else
{
268
IterPruneVal<IntView> pv(
x
);
269
GECODE_ME_CHECK
(
x
->view().minus_v(home,pv,
false
));
270
}
271
}
272
}
273
274
return
ES_OK
;
275
}
276
277
}}}
278
279
// STATISTICS: int-prop
280
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::Int::ValSet
Class for storing values of already assigned views.
Definition:
val-set.hh:44
Gecode::Int::ViewValGraph::Edge::revert
void revert(Node< View > *d)
Revert edge to node d for matching.
Definition:
edge.hpp:57
Gecode::Int::NValues::Graph::sync
void sync(void)
Synchronize graph with new view domains.
Definition:
graph.hpp:90
Gecode::Int::IntVarImpFwd::min
int min(void) const
Return smallest value of range.
Definition:
int.hpp:446
Gecode::Support::StaticStack
Stack with fixed number of elements.
Definition:
static-stack.hpp:42
Gecode::Space
Computation spaces.
Definition:
core.hpp:1742
Gecode::Int::ViewValGraph::Graph< IntView >::n_view
int n_view
Number of view nodes.
Definition:
view-val-graph.hh:301
Gecode::Int::NValues::Graph::n_matched
int n_matched
Number of matched edges.
Definition:
nvalues.hh:99
Gecode
Gecode toplevel namespace
Gecode::Int::ValSet::size
int size(void) const
Return size (number of values)
Definition:
val-set.hpp:81
Gecode::Int::ValSet::Ranges
Iterator over ranges.
Definition:
val-set.hh:78
Gecode::Int::ViewValGraph::Node::min
unsigned int min
Definition:
view-val-graph.hh:121
Gecode::Int::IntVarImpFwd::width
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition:
int.hpp:454
Gecode::Int::ViewValGraph::Graph< IntView >::n_val
int n_val
Number of value nodes.
Definition:
view-val-graph.hh:303
Gecode::Iter::Ranges::ToValues
Value iterator from range iterator.
Definition:
ranges-values.hpp:42
Gecode::Region
Handle to region.
Definition:
region.hpp:55
Gecode::r
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition:
set.hh:767
Gecode::Space::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition:
core.hpp:2837
Gecode::Support::StaticStack::empty
bool empty(void) const
Test whether stack is empty.
Definition:
static-stack.hpp:98
Gecode::Int::ViewValGraph::Graph< IntView >::count
unsigned int count
Marking counter.
Definition:
view-val-graph.hh:305
Gecode::Support::StaticStack::pop
T pop(void)
Pop topmost element from stack and return it.
Definition:
static-stack.hpp:116
Gecode::Int::NValues::Graph::mark
bool mark(void)
Definition:
graph.hpp:152
Gecode::Int::ViewValGraph::Graph< IntView >::scc
void scc(void)
Compute the strongly connected components.
Definition:
graph.hpp:142
Gecode::Int::ViewValGraph::ViewNode::val_edges_ref
Edge< View > ** val_edges_ref(void)
Return pointer to first edge fields of all value edges.
Definition:
node.hpp:135
Gecode::Int::ViewValGraph::Graph::init
void init(Space &home, ViewNode< View > *x)
Initialize the edges for the view node x.
Definition:
graph.hpp:51
Gecode::Int::ViewValGraph::Graph< IntView >::match
bool match(ViewNodeStack &m, ViewNode< IntView > *x)
Find a matching for node x.
Definition:
graph.hpp:87
Test::Int::Distinct::v
const int v[7]
Definition:
distinct.cpp:259
Gecode::Int::NValues::Graph::Graph
Graph(void)
Construct graph as not yet initialized.
Definition:
graph.hpp:37
Gecode::Int::NValues::Graph::size
int size(void) const
Return size of maximal matching (excluding assigned views)
Definition:
graph.hpp:41
Gecode::Support::StaticStack::push
void push(const T &x)
Push element x on top of stack.
Definition:
static-stack.hpp:137
Gecode::Int::ViewRanges< IntView >
Range iterator for integer variable views
Definition:
int.hpp:246
Gecode::Int::NValues::Graph::prune
ExecStatus prune(Space &home)
Prune all values corresponding to unused edges.
Definition:
graph.hpp:255
forceinline
#define forceinline
Definition:
config.hpp:185
GECODE_ME_CHECK
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition:
macros.hpp:52
Gecode::Int::ViewValGraph::Graph< IntView >::view
ViewNode< IntView > ** view
Array of view nodes.
Definition:
view-val-graph.hh:297
Gecode::ViewArray< IntView >
n
int n
Number of negative literals for node type.
Definition:
bool-expr.cpp:234
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition:
core.hpp:476
p
int p
Number of positive literals for node type.
Definition:
bool-expr.cpp:232
Gecode::Int::ViewValGraph::Graph< IntView >::val
ValNode< IntView > * val
Array of value nodes.
Definition:
view-val-graph.hh:299
Gecode::Int::NValues::Graph::init
void init(Space &home, const ValSet &vs, const ViewArray< IntView > &x)
Initialize graph including values in vs.
Definition:
graph.hpp:46
GECODE_ASSUME
#define GECODE_ASSUME(p)
Assert certain property.
Definition:
macros.hpp:114
Gecode::ExecStatus
ExecStatus
Definition:
core.hpp:472