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