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
view-val-graph
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, 2003
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
#include <climits>
35
36
namespace
Gecode
{
namespace
Int {
namespace
ViewValGraph {
37
38
template
<
class
View>
39
forceinline
40
Graph<View>::Graph
(
void
)
41
: view(NULL), val(NULL), n_view(0), n_val(0),
count
(1U) {}
42
43
template
<
class
View>
44
forceinline
45
Graph<View>::operator
bool(
void
)
const
{
46
return
view != NULL;
47
}
48
49
template
<
class
View>
50
forceinline
void
51
Graph<View>::init
(
Space
& home,
ViewNode<View>
*
x
) {
52
Edge<View>
** edge_p =
x
->val_edges_ref();
53
ViewValues<View>
xi(
x
->view());
54
ValNode<View>
**
v
= &val;
55
while
(xi() && (*
v
!= NULL)) {
56
if
((*v)->val() == xi.
val
()) {
57
// Value node does already exist, create new edge
58
*edge_p =
new
(home)
Edge<View>
(*
v
,
x
);
59
edge_p = (*edge_p)->
next_edge_ref
();
60
v
= (*v)->next_val_ref();
61
++xi;
62
}
else
if
((*v)->val() < xi.
val
()) {
63
// Skip to next value node
64
v
= (*v)->next_val_ref();
65
}
else
{
66
// Value node does not yet exist, create and link it
67
ValNode<View>
* nv =
new
(home)
ValNode<View>
(xi.
val
(),*
v
);
68
*
v
= nv;
v
= nv->
next_val_ref
();
69
*edge_p =
new
(home)
Edge<View>
(nv,
x
);
70
edge_p = (*edge_p)->
next_edge_ref
();
71
++xi; n_val++;
72
}
73
}
74
// Create missing value nodes
75
while
(xi()) {
76
ValNode<View>
* nv =
new
(home)
ValNode<View>
(xi.
val
(),*
v
);
77
*
v
= nv;
v
= nv->
next_val_ref
();
78
*edge_p =
new
(home)
Edge<View>
(nv,
x
);
79
edge_p = (*edge_p)->
next_edge_ref
();
80
++xi; n_val++;
81
}
82
*edge_p = NULL;
83
}
84
85
template
<
class
View>
86
forceinline
bool
87
Graph<View>::match
(
ViewNodeStack
& m,
ViewNode<View>
*
x
) {
88
count
++;
89
start:
90
// Try to find matching edge cheaply: is there a free edge around?
91
{
92
Edge<View>
* e =
x
->val_edges();
93
// This holds true as domains are never empty
94
assert(e != NULL);
95
do
{
96
if
(!e->
val
(
x
)->matching()) {
97
e->
revert
(
x
); e->
val
(
x
)->matching(e);
98
// Found a matching, revert all edges on stack
99
while
(!m.
empty
()) {
100
x
= m.
pop
(); e =
x
->iter;
101
e->
val
(
x
)->matching()->revert(e->
val
(
x
));
102
e->
revert
(
x
); e->
val
(
x
)->matching(e);
103
}
104
return
true
;
105
}
106
e = e->
next_edge
();
107
}
while
(e != NULL);
108
}
109
// No, find matching edge by augmenting path method
110
Edge<View>
* e =
x
->val_edges();
111
do
{
112
if
(e->
val
(
x
)->matching()->view(e->
val
(
x
))->min <
count
) {
113
e->
val
(
x
)->matching()->view(e->
val
(
x
))->min =
count
;
114
m.
push
(
x
);
x
->iter = e;
115
x
= e->
val
(
x
)->matching()->view(e->
val
(
x
));
116
goto
start;
117
}
118
next:
119
e = e->
next_edge
();
120
}
while
(e != NULL);
121
if
(!m.
empty
()) {
122
x
= m.
pop
(); e =
x
->iter;
goto
next;
123
}
124
// All nodes and edges unsuccessfully tried
125
return
false
;
126
}
127
128
template
<
class
View>
129
forceinline
void
130
Graph<View>::purge
(
void
) {
131
if
(
count
> (UINT_MAX >> 1)) {
132
count
= 1;
133
for
(
int
i
=0;
i
<n_view;
i
++)
134
view[
i
]->
min
= 0;
135
for
(
ValNode<View>
*
v
= val;
v
!= NULL;
v
=
v
->next_val())
136
v
->min = 0;
137
}
138
}
139
140
template
<
class
View>
141
forceinline
void
142
Graph<View>::scc
(
void
) {
143
Region
r
;
144
145
Support::StaticStack<Node<View>
*,
Region
> scc(
r
,n_val+n_view);
146
Support::StaticStack<Node<View>
*,
Region
> visit(
r
,n_val+n_view);
147
148
count
++;
149
unsigned
int
cnt0 =
count
;
150
unsigned
int
cnt1 =
count
;
151
152
for
(
int
i
=0;
i
<n_view;
i
++)
153
/*
154
* The following test is subtle: for scc, the test should be:
155
* view[i]->min < count
156
* However, if view[i] < count-1, then the node has already been
157
* reached on a path and all edges connected to the node have been
158
* marked anyway! So just ignore this node altogether for scc.
159
*/
160
if
(view[
i
]->
min
<
count
-1) {
161
Node<View>
* w = view[
i
];
162
start:
163
w->
low
= w->
min
= cnt0++;
164
scc.
push
(w);
165
Edge<View>
* e = w->
edge_fst
();
166
while
(e != w->
edge_lst
()) {
167
if
(e->
dst
(w)->min <
count
) {
168
visit.
push
(w); w->
iter
= e;
169
w=e->
dst
(w);
170
goto
start;
171
}
172
next:
173
if
(e->
dst
(w)->low < w->
min
)
174
w->
min
= e->
dst
(w)->low;
175
e = e->
next
();
176
}
177
if
(w->
min
< w->
low
) {
178
w->
low
= w->
min
;
179
}
else
{
180
Node<View>
*
v
;
181
do
{
182
v
= scc.
pop
();
183
v
->comp = cnt1;
184
v
->low = UINT_MAX;
185
}
while
(
v
!= w);
186
cnt1++;
187
}
188
if
(!visit.
empty
()) {
189
w=visit.
pop
(); e=w->
iter
;
goto
next;
190
}
191
}
192
count
= cnt0+1;
193
}
194
195
196
}}}
197
198
// STATISTICS: int-prop
Gecode::Int::ViewValGraph::Graph
View-value graph base class.
Definition:
view-val-graph.hh:294
Gecode::Int::ViewValGraph::Edge::val
ValNode< View > * val(ViewNode< View > *x) const
Return value node when view node x is given.
Definition:
edge.hpp:69
Gecode::Int::ViewValGraph::Node
Base-class for nodes (both view and value nodes)
Definition:
view-val-graph.hh:116
Gecode::Int::ViewValGraph::ViewNode
View nodes in view-value graph.
Definition:
view-val-graph.hh:174
Gecode::FloatVal::min
FloatVal min(const FloatVal &x, const FloatVal &y)
Return minimum of x and y.
Definition:
val.hpp:398
Gecode::Int::ViewValGraph::Node::low
unsigned int low
Values for computing strongly connected components.
Definition:
view-val-graph.hh:121
Gecode::Int::ViewValGraph::Edge::revert
void revert(Node< View > *d)
Revert edge to node d for matching.
Definition:
edge.hpp:57
Gecode::Support::StaticStack
Stack with fixed number of elements.
Definition:
static-stack.hpp:42
Gecode::Int::ViewValues
Value iterator for integer views.
Definition:
view.hpp:94
Gecode::Space
Computation spaces.
Definition:
core.hpp:1742
Gecode::Iter::Ranges::ToValues< ViewRanges< View > >::val
int val(void) const
Return current value.
Definition:
ranges-values.hpp:129
Gecode::Int::ViewValGraph::Edge::next_edge
Edge< View > * next_edge(void) const
Return next edge in list of value edges.
Definition:
edge.hpp:91
Gecode::Int::ViewValGraph::Node::edge_fst
Edge< View > * edge_fst(void) const
Return first edge (organized by bi-links)
Definition:
node.hpp:48
Gecode
Gecode toplevel namespace
x
Node * x
Pointer to corresponding Boolean expression node.
Definition:
bool-expr.cpp:249
Gecode::Int::ViewValGraph::Node::edge_lst
Edge< View > * edge_lst(void) const
Return last edge (organized by bi-links)
Definition:
node.hpp:53
Gecode::Int::ViewValGraph::Node::min
unsigned int min
Definition:
view-val-graph.hh:121
Gecode::Int::ViewValGraph::Graph::Graph
Graph(void)
Construct graph as not yet initialized.
Definition:
graph.hpp:40
Gecode::Region
Handle to region.
Definition:
region.hpp:55
Gecode::Support::StaticStack::empty
bool empty(void) const
Test whether stack is empty.
Definition:
static-stack.hpp:98
Gecode::Support::StaticStack::pop
T pop(void)
Pop topmost element from stack and return it.
Definition:
static-stack.hpp:116
Gecode::Int::ViewValGraph::Edge::dst
Node< View > * dst(Node< View > *s) const
Return destination of edge when source s is given.
Definition:
edge.hpp:51
Gecode::Int::ViewValGraph::Node::iter
Edge< View > * iter
Next edge for computing strongly connected components.
Definition:
view-val-graph.hh:119
Gecode::Int::ViewValGraph::Edge
Edges in view-value graph.
Definition:
view-val-graph.hh:104
Gecode::Int::ViewValGraph::Edge::next_edge_ref
Edge< View > ** next_edge_ref(void)
Return reference to next edge in list of value edges.
Definition:
edge.hpp:96
Test::Int::Distinct::v
const int v[7]
Definition:
distinct.cpp:259
Gecode::count
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
Definition:
count.cpp:40
Gecode::Int::ViewValGraph::ValNode
Value nodes in view-value graph.
Definition:
view-val-graph.hh:142
Gecode::Support::StaticStack::push
void push(const T &x)
Push element x on top of stack.
Definition:
static-stack.hpp:137
r
NNF * r
Right subtree.
Definition:
bool-expr.cpp:242
Gecode::Int::purge
ExecStatus purge(Space &home, Propagator &p, TaskArray< OptTask > &t)
Purge optional tasks that are excluded and possibly rewrite propagator.
Definition:
purge.hpp:38
forceinline
#define forceinline
Definition:
config.hpp:185
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::Int::ViewValGraph::ValNode::next_val_ref
ValNode< View > ** next_val_ref(void)
Return pointer to next value node fields.
Definition:
node.hpp:99
Gecode::Int::ViewValGraph::Edge::next
Edge< View > * next(void) const
Return next edge in list of edges per node.
Definition:
edge.hpp:101