main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Jan 28 2020 00:00:00 for Gecode by
doxygen
1.8.17
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
* Last modified:
10
* $Date: 2016-06-18 14:20:49 +0200 (Sat, 18 Jun 2016) $ by $Author: schulte $
11
* $Revision: 15118 $
12
*
13
* This file is part of Gecode, the generic constraint
14
* development environment:
15
* http://www.gecode.org
16
*
17
* Permission is hereby granted, free of charge, to any person obtaining
18
* a copy of this software and associated documentation files (the
19
* "Software"), to deal in the Software without restriction, including
20
* without limitation the rights to use, copy, modify, merge, publish,
21
* distribute, sublicense, and/or sell copies of the Software, and to
22
* permit persons to whom the Software is furnished to do so, subject to
23
* the following conditions:
24
*
25
* The above copyright notice and this permission notice shall be
26
* included in all copies or substantial portions of the Software.
27
*
28
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35
*
36
*/
37
38
namespace
Gecode
{
namespace
Int {
namespace
NValues {
39
40
forceinline
41
Graph::Graph
(
void
)
42
: n_matched(0) {}
43
44
forceinline
int
45
Graph::size
(
void
)
const
{
46
return
n_matched
;
47
}
48
49
forceinline
void
50
Graph::init
(
Space
& home,
const
ValSet
& vs,
const
ViewArray<IntView>
&
x
) {
51
using namespace
ViewValGraph;
52
n_view
=
x
.size() + vs.
size
();
53
view
= home.
alloc
<ViewNode<IntView>*>(
n_view
);
54
55
// Create nodes corresponding to the value set vs
56
{
57
int
i
=
x
.size();
58
ValSet::Ranges
vsr(vs);
59
ValNode<IntView>**
v
= &
val
;
60
for
(
Iter::Ranges::ToValues<ValSet::Ranges>
n
(vsr);
n
(); ++
n
) {
61
// Create view node
62
view
[
i
] =
new
(home) ViewNode<IntView>();
63
// Create and link value node
64
ValNode<IntView>* nv =
new
(home) ValNode<IntView>(
n
.val());
65
*
v
= nv;
v
= nv->next_val_ref();
66
// Create and link single edge
67
Edge<IntView>** e =
view
[
i
]->
val_edges_ref
();
68
*e =
new
(home) Edge<IntView>(nv,
view
[
i
],NULL);
69
// Match edge
70
(*e)->
revert
(
view
[
i
]); nv->matching(*e);
71
i
++;
72
}
73
*
v
= NULL;
74
n_val
= vs.
size
();
75
n_matched
= vs.
size
();
76
assert(
i
-
x
.size() == vs.
size
());
77
}
78
79
// Initialize real view nodes
80
for
(
int
i
=
x
.size();
i
--; ) {
81
view
[
i
] =
new
(home) ViewNode<IntView>(
x
[
i
]);
82
ViewValGraph::Graph<IntView>::init
(home,
view
[
i
]);
83
}
84
85
// Match the real view nodes, if possible
86
Region
r
(home);
87
ViewNodeStack
m(
r
,
n_view
);
88
for
(
int
i
=
x
.size();
i
--; )
89
if
(
match
(m,
view
[
i
]))
90
n_matched
++;
91
}
92
93
forceinline
void
94
Graph::sync
(
Space
& home) {
95
using namespace
ViewValGraph;
96
Region
r
(home);
97
98
// Whether to rematch
99
bool
rematch =
false
;
100
101
// Synchronize nodes
102
for
(
int
i
=
n_view
;
i
--; ) {
103
ViewNode<IntView>*
x
=
view
[
i
];
104
// Skip faked view nodes, they correspond to values in the value set
105
if
(!
x
->fake()) {
106
if
(
x
->changed()) {
107
ViewRanges<IntView>
rx(
x
->view());
108
Edge<IntView>* m =
x
->matched() ?
x
->edge_fst() : NULL;
109
Edge<IntView>**
p
=
x
->val_edges_ref();
110
Edge<IntView>* e = *
p
;
111
do
{
112
while
(e->val(
x
)->val() < rx.
min
()) {
113
// Skip edge
114
e->unlink(); e->mark();
115
e = e->next_edge();
116
}
117
*
p
= e;
118
assert(rx.
min
() == e->val(
x
)->val());
119
// This edges must be kept
120
for
(
unsigned
int
j=rx.
width
(); j--; ) {
121
e->free();
122
p
= e->next_edge_ref();
123
e = e->next_edge();
124
}
125
++rx;
126
}
while
(rx());
127
*
p
= NULL;
128
while
(e != NULL) {
129
e->unlink(); e->mark();
130
e = e->next_edge();
131
}
132
if
((m != NULL) && m->marked()) {
133
// Matching has been deleted!
134
m->val(
x
)->matching(NULL);
135
rematch =
true
;
136
n_matched
--;
137
}
138
}
else
{
139
// Just free edges
140
for
(Edge<IntView>* e=
x
->val_edges(); e != NULL; e = e->next_edge())
141
e->free();
142
}
143
}
144
}
145
146
if
(rematch) {
147
ViewNodeStack
m(
r
,
n_view
);
148
for
(
int
i
=
n_view
;
i
--; )
149
if
(!
view
[
i
]->matched() &&
match
(m,
view
[
i
]))
150
n_matched
++;
151
}
152
}
153
154
forceinline
bool
155
Graph::mark
(
Space
& home) {
156
using namespace
ViewValGraph;
157
Region
r
(home);
158
159
int
n_view_visited = 0;
160
{
161
// Marks all edges as used that are on simple paths in the graph
162
// that start from a free value node by depth-first-search
163
Support::StaticStack<ValNode<IntView>
*,
Region
> visit(
r
,
n_val
);
164
165
// Insert all free value nodes
166
count
++;
167
{
168
ValNode<IntView>**
v
= &
val
;
169
while
(*
v
!= NULL)
170
// Is the node free?
171
if
(!(*v)->matching()) {
172
// Eliminate empty value nodes
173
if
((*v)->empty()) {
174
*
v
= (*v)->next_val();
175
n_val
--;
176
}
else
{
177
(*v)->min =
count
;
178
visit.
push
(*
v
);
179
v
= (*v)->next_val_ref();
180
}
181
}
else
{
182
v
= (*v)->next_val_ref();
183
}
184
}
185
186
// Invariant: only value nodes are on the stack!
187
while
(!visit.
empty
()) {
188
ValNode<IntView>*
n
= visit.
pop
();
189
for
(Edge<IntView>* e =
n
->edge_fst(); e !=
n
->edge_lst();
190
e = e->next()) {
191
// Is the view node is matched: the path must be alternating!
192
ViewNode<IntView>*
x
= e->view(
n
);
193
if
(
x
->matched()) {
194
// Mark the edge as used
195
e->use();
196
if
(
x
->min <
count
) {
197
n_view_visited++;
198
x
->min =
count
;
199
assert(
x
->edge_fst()->next() ==
x
->edge_lst());
200
ValNode<IntView>* m =
x
->edge_fst()->val(
x
);
201
x
->edge_fst()->use();
202
if
(m->min <
count
) {
203
m->min =
count
;
204
visit.
push
(m);
205
}
206
}
207
}
208
}
209
}
210
211
}
212
213
if
(n_view_visited <
n_view
) {
214
// Mark all edges as used starting from a free view node on
215
// an alternating path by depth-first search.
216
Support::StaticStack<ViewNode<IntView>
*,
Region
> visit(
r
,
n_view
);
217
218
// Insert all free view nodes
219
count
++;
220
for
(
int
i
=
n_view
;
i
--; )
221
if
(!
view
[
i
]->matched()) {
222
view
[
i
]->
min
=
count
;
223
visit.
push
(
view
[
i
]);
224
}
225
226
// Invariant: only view nodes are on the stack!
227
while
(!visit.
empty
()) {
228
n_view_visited++;
229
ViewNode<IntView>*
x
= visit.
pop
();
230
for
(Edge<IntView>* e =
x
->val_edges(); e != NULL; e = e->next_edge())
231
// Consider only free edges
232
if
(e !=
x
->edge_fst()) {
233
ValNode<IntView>*
n
= e->val(
x
);
234
// Is there a matched edge from the value node to a view node?
235
if
(
n
->matching() != NULL) {
236
e->use();
237
n
->matching()->use();
238
ViewNode<IntView>*
y
=
n
->matching()->view(
n
);
239
if
(
y
->min <
count
) {
240
y
->min =
count
;
241
visit.
push
(
y
);
242
}
243
}
244
}
245
}
246
247
}
248
249
if
(n_view_visited <
n_view
) {
250
scc
(home);
251
return
true
;
252
}
else
{
253
return
false
;
254
}
255
}
256
257
forceinline
ExecStatus
258
Graph::prune
(
Space
& home) {
259
using namespace
ViewValGraph;
260
// Tell constraints and also eliminate nodes and edges
261
for
(
int
i
=
n_view
;
i
--; ) {
262
ViewNode<IntView>*
x
=
view
[
i
];
263
if
(!
x
->fake()) {
264
if
(
x
->matched() && !
x
->edge_fst()->used(
x
)) {
265
GECODE_ME_CHECK
(
x
->view().eq(home,
x
->edge_fst()->val(
x
)->val()));
266
x
->edge_fst()->val(
x
)->matching(NULL);
267
for
(Edge<IntView>* e =
x
->val_edges(); e != NULL; e=e->next_edge())
268
e->unlink();
269
view
[
i
] =
view
[--
n_view
];
270
}
else
{
271
IterPruneVal<IntView> pv(
x
);
272
GECODE_ME_CHECK
(
x
->view().minus_v(home,pv,
false
));
273
}
274
}
275
}
276
277
return
ES_OK
;
278
}
279
280
}}}
281
282
// STATISTICS: int-prop
283
Gecode::x
Post propagator for SetVar x
Definition:
set.hh:784
Gecode::y
Post propagator for SetVar SetOpType SetVar y
Definition:
set.hh:784
forceinline
#define forceinline
Definition:
config.hpp:173
Gecode::Int::NValues::Graph::sync
void sync(Space &home)
Synchronize graph with new view domains.
Definition:
graph.hpp:94
Gecode::Int::ValSet
Class for storing values of already assigned views.
Definition:
val-set.hh:48
Gecode::Int::ViewValGraph::Edge::revert
void revert(Node< View > *d)
Revert edge to node d for matching.
Definition:
edge.hpp:61
Test::Int::Basic::i
Gecode::IntArgs i(4, 1, 2, 3, 4)
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:46
Gecode::Space
Computation spaces.
Definition:
core.hpp:1748
Gecode::Int::ViewValGraph::Graph< IntView >::n_view
int n_view
Number of view nodes.
Definition:
view-val-graph.hh:305
Gecode::Int::NValues::Graph::n_matched
int n_matched
Number of matched edges.
Definition:
nvalues.hh:103
Gecode
Gecode toplevel namespace
Gecode::Int::ValSet::size
int size(void) const
Return size (number of values)
Definition:
val-set.hpp:85
Gecode::Int::ValSet::Ranges
Iterator over ranges.
Definition:
val-set.hh:82
Gecode::Int::ViewValGraph::Node::min
unsigned int min
Definition:
view-val-graph.hh:125
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:307
Gecode::Iter::Ranges::ToValues
Value iterator from range iterator.
Definition:
ranges-values.hpp:46
Gecode::Region
Handle to region.
Definition:
region.hpp:61
Gecode::r
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition:
set.hh:784
Gecode::Space::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition:
core.hpp:2868
Gecode::Support::StaticStack::empty
bool empty(void) const
Test whether stack is empty.
Definition:
static-stack.hpp:102
Gecode::Int::ViewValGraph::Graph< IntView >::count
unsigned int count
Marking counter.
Definition:
view-val-graph.hh:309
Gecode::Support::StaticStack::pop
T pop(void)
Pop topmost element from stack and return it.
Definition:
static-stack.hpp:120
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:139
Gecode::Int::ViewValGraph::Graph::init
void init(Space &home, ViewNode< View > *x)
Initialize the edges for the view node x.
Definition:
graph.hpp:55
Gecode::Int::ViewValGraph::Graph< IntView >::match
bool match(ViewNodeStack &m, ViewNode< IntView > *x)
Find a matching for node x.
Definition:
graph.hpp:91
Test::Int::Distinct::v
const int v[7]
Definition:
distinct.cpp:263
Gecode::Int::NValues::Graph::Graph
Graph(void)
Construct graph as not yet initialized.
Definition:
graph.hpp:41
Gecode::Int::NValues::Graph::mark
bool mark(Space &home)
Definition:
graph.hpp:155
Gecode::Int::NValues::Graph::size
int size(void) const
Return size of maximal matching (excluding assigned views)
Definition:
graph.hpp:45
Gecode::Support::StaticStack::push
void push(const T &x)
Push element x on top of stack.
Definition:
static-stack.hpp:141
Gecode::Int::ViewRanges< IntView >
Range iterator for integer variable views
Definition:
int.hpp:236
Gecode::Int::NValues::Graph::prune
ExecStatus prune(Space &home)
Prune all values corresponding to unused edges.
Definition:
graph.hpp:258
GECODE_ME_CHECK
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition:
macros.hpp:56
Gecode::Int::ViewValGraph::Graph< IntView >::view
ViewNode< IntView > ** view
Array of view nodes.
Definition:
view-val-graph.hh:301
Gecode::ViewArray< IntView >
n
int n
Number of negative literals for node type.
Definition:
bool-expr.cpp:238
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition:
core.hpp:544
Gecode::Int::ViewValGraph::Graph< IntView >::scc
void scc(Space &home)
Compute the strongly connected components.
Definition:
graph.hpp:146
p
int p
Number of positive literals for node type.
Definition:
bool-expr.cpp:236
Gecode::Int::ViewValGraph::Graph< IntView >::val
ValNode< IntView > * val
Array of value nodes.
Definition:
view-val-graph.hh:303
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:50
Gecode::ExecStatus
ExecStatus
Definition:
core.hpp:540