this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 * Guido Tack <tack@gecode.org>
6 *
7 * Copyright:
8 * Christian Schulte, 2002
9 * Guido Tack, 2004
10 *
11 * This file is part of Gecode, the generic constraint
12 * development environment:
13 * http://www.gecode.org
14 *
15 * Permission is hereby granted, free of charge, to any person obtaining
16 * a copy of this software and associated documentation files (the
17 * "Software"), to deal in the Software without restriction, including
18 * without limitation the rights to use, copy, modify, merge, publish,
19 * distribute, sublicense, and/or sell copies of the Software, and to
20 * permit persons to whom the Software is furnished to do so, subject to
21 * the following conditions:
22 *
23 * The above copyright notice and this permission notice shall be
24 * included in all copies or substantial portions of the Software.
25 *
26 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 *
34 */
35
36#ifndef GECODE_INT_VIEW_VAL_GRAPH_HH
37#define GECODE_INT_VIEW_VAL_GRAPH_HH
38
39#include <gecode/int.hh>
40
41/**
42 * \namespace Gecode::Int::ViewValGraph
43 * \brief Support classes for propagators using a view-value graph
44 */
45namespace Gecode { namespace Int { namespace ViewValGraph {
46
47 /**
48 * \brief Class for combining two pointers with a flag
49 *
50 * When one pointer is given, the other can be retrieved.
51 *
52 */
53 template<class T>
54 class CombPtrFlag {
55 private:
56 /// Store pointer and flag
57 ptrdiff_t cpf;
58 public:
59 /// Initialize with pointer \a p1 and \a p2
60 CombPtrFlag(T* p1, T* p2);
61 /// Initialize with pointer \a p1 and \a p2
62 void init(T* p1, T* p2);
63 /// Return the other pointer when \a p is given
64 T* ptr(T* p) const;
65 /// Check whether flag is set
66 int is_set(void) const;
67 /// Set flag
68 void set(void);
69 /// Clear flag
70 void unset(void);
71 };
72
73 /// Bidirectional links for edges and anchors in nodes of view-value graph
74 class BiLink {
75 private:
76 /// Link to previous element
77 BiLink* _prev;
78 /// Link to next element
79 BiLink* _next;
80 public:
81 /// Initialize as empty (self referenced)
82 BiLink(void);
83 /// Return previous element
84 BiLink* prev(void) const;
85 /// Return next element
86 BiLink* next(void) const;
87 /// Set previous element to \a l
88 void prev(BiLink* l);
89 /// Set next element to \a l
90 void next(BiLink* l);
91 /// Add \a l after this element
92 void add(BiLink* l);
93 /// Unlink this element
94 void unlink(void);
95 /// Mark element (invalidates next element pointer)
96 void mark(void);
97 /// Whether element is marked
98 bool marked(void) const;
99 /// Whether element has no previous and next element
100 bool empty(void) const;
101 };
102
103
104 template<class View> class Edge;
105
106 /**
107 * \brief Base-class for nodes (both view and value nodes)
108 *
109 * Note: the obvious ill-design to have also nodes and edges
110 * parametric wrt View is because the right design (having template
111 * function members) gets miscompiled (and actually not even compiled
112 * with some C++ compilers). Duh!
113 *
114 */
115 template<class View>
116 class Node : public BiLink {
117 public:
118 /// Next edge for computing strongly connected components
119 Edge<View>* iter;
120 /// Values for computing strongly connected components
121 unsigned int low, min, comp;
122 /// Initialize
123 Node(void);
124 /// Return first edge (organized by bi-links)
125 Edge<View>* edge_fst(void) const;
126 /// Return last edge (organized by bi-links)
127 Edge<View>* edge_lst(void) const;
128
129 /// Allocate memory from space
130 static void* operator new(size_t, Space&);
131 /// Needed for exceptions
132 static void operator delete(void*, size_t);
133 /// Needed for exceptions
134 static void operator delete(void*,Space&);
135 };
136
137 /**
138 * \brief Value nodes in view-value graph
139 *
140 */
141 template<class View>
142 class ValNode : public Node<View> {
143 protected:
144 /// The value of the node
145 const int _val;
146 /// The matching edge
147 Edge<View>* _matching;
148 /// The next value node
149 ValNode<View>* _next_val;
150 public:
151 /// Initialize with value \a v
152 ValNode(int v);
153 /// Initialize with value \a v and successor \a n
154 ValNode(int v, ValNode<View>* n);
155 /// Return value of node
156 int val(void) const;
157 /// Set matching edge to \a m
158 void matching(Edge<View>* m);
159 /// Return matching edge (nullptr if unmatched)
160 Edge<View>* matching(void) const;
161 /// Return pointer to next value node fields
162 ValNode<View>** next_val_ref(void);
163 /// Return next value node
164 ValNode<View>* next_val(void) const;
165 /// Set next value node to \a v
166 void next_val(ValNode<View>* v);
167 };
168
169 /**
170 * \brief View nodes in view-value graph
171 *
172 */
173 template<class View>
174 class ViewNode : public Node<View> {
175 protected:
176 /// The size of the view after last change
177 unsigned int _size;
178 /// The node's view
179 View _view;
180 /// The first value edge
181 Edge<View>* _val_edges;
182 public:
183 /// Initialize node for a non-view
184 ViewNode(void);
185 /// Initialize new node for view \a x
186 ViewNode(View x);
187 /// Return first edge of all value edges
188 Edge<View>* val_edges(void) const;
189 /// Return pointer to first edge fields of all value edges
190 Edge<View>** val_edges_ref(void);
191 /// Test whether node has a fake view
192 bool fake(void) const;
193 /// Return view
194 View view(void) const;
195 /// Update size of view after change
196 void update(void);
197 /// Return whether view has changed its size
198 bool changed(void) const;
199 /// Whether the node is matched
200 bool matched(void) const;
201 };
202
203 /**
204 * \brief Edges in view-value graph
205 *
206 */
207 template<class View>
208 class Edge : public BiLink {
209 protected:
210 /// Next edge in chain of value edges
211 Edge<View>* _next_edge;
212 /// Combine source and destination node and flag
213 CombPtrFlag<Node<View> > sd;
214 public:
215 /// Construct new edge between \a x and \a v
216 Edge(ValNode<View>* v, ViewNode<View>* x);
217 /// Construct new edge between \a x and \a v with next edge \a n
218 Edge(ValNode<View>* v, ViewNode<View>* x, Edge<View>* n);
219 /// Return destination of edge when source \a s is given
220 Node<View>* dst(Node<View>* s) const;
221
222 /// Return view node when value node \a v is given
223 ViewNode<View>* view(ValNode<View>* v) const;
224 /// Return value node when view node \a x is given
225 ValNode<View>* val(ViewNode<View>* x) const;
226
227 /// Whether edge is used (marked or between nodes from the same scc)
228 bool used(Node<View>* v) const;
229 /// Mark node as used
230 void use(void);
231 /// Unmark node as used
232 void free(void);
233
234 /// Revert edge to node \a d for matching
235 void revert(Node<View>* d);
236
237 /// Return next edge in list of value edges
238 Edge<View>* next_edge(void) const;
239 /// Return reference to next edge in list of value edges
240 Edge<View>** next_edge_ref(void);
241 /// Return next edge in list of edges per node
242 Edge<View>* next(void) const;
243
244 /// Allocate memory from space
245 static void* operator new(size_t, Space&);
246 /// Needed for exceptions
247 static void operator delete(void*, size_t);
248 /// Needed for exceptions
249 static void operator delete(void*,Space&);
250 };
251
252 /// Iterates the values to be pruned from a view node
253 template<class View>
254 class IterPruneVal {
255 protected:
256 /// View node
257 ViewNode<View>* x;
258 /// Current value edge
259 Edge<View>* e;
260 public:
261 /// \name Constructors and initialization
262 //@{
263 /// Initialize with edges for view node \a x
264 IterPruneVal(ViewNode<View>* x);
265 //@}
266
267 /// \name Iteration control
268 //@{
269 /// Test whether iterator is still at a value or done
270 bool operator ()(void) const;
271 /// Move iterator to next value (if possible)
272 void operator ++(void);
273 //@}
274
275 /// \name Value access
276 //@{
277 /// Return current value
278 int val(void) const;
279 //@}
280 };
281
282}}}
283
284#include <gecode/int/view-val-graph/comb-ptr-flag.hpp>
285#include <gecode/int/view-val-graph/bi-link.hpp>
286#include <gecode/int/view-val-graph/edge.hpp>
287#include <gecode/int/view-val-graph/node.hpp>
288#include <gecode/int/view-val-graph/iter-prune-val.hpp>
289
290namespace Gecode { namespace Int { namespace ViewValGraph {
291
292 /// View-value graph base class
293 template<class View>
294 class Graph {
295 protected:
296 /// Array of view nodes
297 ViewNode<View>** view;
298 /// Array of value nodes
299 ValNode<View>* val;
300 /// Number of view nodes
301 int n_view;
302 /// Number of value nodes
303 int n_val;
304 /// Marking counter
305 unsigned int count;
306 /// Stack used during matching
307 typedef Support::StaticStack<ViewNode<View>*,Region> ViewNodeStack;
308 /// Initialize the edges for the view node \a x
309 void init(Space& home, ViewNode<View>* x);
310 /// Find a matching for node \a x
311 bool match(ViewNodeStack& m, ViewNode<View>* x);
312 /// Compute the strongly connected components
313 void scc(void);
314 public:
315 /// Construct graph as not yet initialized
316 Graph(void);
317 /// Test whether graph has been initialized
318 operator bool(void) const;
319 /// Purge graph if necessary (reset information to avoid overflow)
320 void purge(void);
321 };
322
323}}}
324
325#include <gecode/int/view-val-graph/graph.hpp>
326
327#endif
328
329// STATISTICS: int-prop
330