Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
view-val-graph.hh
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 * 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
45namespace Gecode { namespace Int { namespace ViewValGraph {
46
53 template<class T>
55 private:
57 ptrdiff_t cpf;
58 public:
60 CombPtrFlag(T* p1, T* p2);
62 void init(T* p1, T* p2);
64 T* ptr(T* p) const;
66 int is_set(void) const;
68 void set(void);
70 void unset(void);
71 };
72
74 class BiLink {
75 private:
77 BiLink* _prev;
79 BiLink* _next;
80 public:
82 BiLink(void);
84 BiLink* prev(void) const;
86 BiLink* next(void) const;
88 void prev(BiLink* l);
90 void next(BiLink* l);
92 void add(BiLink* l);
94 void unlink(void);
96 void mark(void);
98 bool marked(void) const;
100 bool empty(void) const;
101 };
102
103
104 template<class View> class Edge;
105
115 template<class View>
116 class Node : public BiLink {
117 public:
121 unsigned int low, min, comp;
123 Node(void);
125 Edge<View>* edge_fst(void) const;
127 Edge<View>* edge_lst(void) const;
128
130 static void* operator new(size_t, Space&);
132 static void operator delete(void*, size_t);
134 static void operator delete(void*,Space&);
135 };
136
141 template<class View>
142 class ValNode : public Node<View> {
143 protected:
145 const int _val;
150 public:
152 ValNode(int v);
154 ValNode(int v, ValNode<View>* n);
156 int val(void) const;
158 void matching(Edge<View>* m);
160 Edge<View>* matching(void) const;
164 ValNode<View>* next_val(void) const;
166 void next_val(ValNode<View>* v);
167 };
168
173 template<class View>
174 class ViewNode : public Node<View> {
175 protected:
177 unsigned int _size;
182 public:
184 ViewNode(void);
186 ViewNode(View x);
188 Edge<View>* val_edges(void) const;
192 bool fake(void) const;
194 View view(void) const;
196 void update(void);
198 bool changed(void) const;
200 bool matched(void) const;
201 };
202
207 template<class View>
208 class Edge : public BiLink {
209 protected:
214 public:
220 Node<View>* dst(Node<View>* s) const;
221
226
228 bool used(Node<View>* v) const;
230 void use(void);
232 void free(void);
233
235 void revert(Node<View>* d);
236
238 Edge<View>* next_edge(void) const;
242 Edge<View>* next(void) const;
243
245 static void* operator new(size_t, Space&);
247 static void operator delete(void*, size_t);
249 static void operator delete(void*,Space&);
250 };
251
253 template<class View>
255 protected:
260 public:
262
263
266
268
269
270 bool operator ()(void) const;
272 void operator ++(void);
274
276
277
278 int val(void) const;
280 };
281
282}}}
283
289
290namespace Gecode { namespace Int { namespace ViewValGraph {
291
293 template<class View>
294 class Graph {
295 protected:
303 int n_val;
305 unsigned int count;
309 void init(Space& home, ViewNode<View>* x);
313 void scc(void);
314 public:
316 Graph(void);
318 operator bool(void) const;
320 void purge(void);
321 };
322
323}}}
324
326
327#endif
328
329// STATISTICS: int-prop
330
Class for combining two pointers with a flag.
int is_set(void) const
Check whether flag is set.
void init(T *p1, T *p2)
Initialize with pointer p1 and p2.
CombPtrFlag(T *p1, T *p2)
Initialize with pointer p1 and p2.
T * ptr(T *p) const
Return the other pointer when p is given.
Edges in view-value graph.
Edge(ValNode< View > *v, ViewNode< View > *x)
Construct new edge between x and v.
Definition edge.hpp:38
ValNode< View > * val(ViewNode< View > *x) const
Return value node when view node x is given.
Definition edge.hpp:69
CombPtrFlag< Node< View > > sd
Combine source and destination node and flag.
Edge< View > * next_edge(void) const
Return next edge in list of value edges.
Definition edge.hpp:91
ViewNode< View > * view(ValNode< View > *v) const
Return view node when value node v is given.
Definition edge.hpp:64
Edge< View > ** next_edge_ref(void)
Return reference to next edge in list of value edges.
Definition edge.hpp:96
Node< View > * dst(Node< View > *s) const
Return destination of edge when source s is given.
Definition edge.hpp:51
void free(void)
Unmark node as used.
Definition edge.hpp:85
Edge< View > * _next_edge
Next edge in chain of value edges.
void use(void)
Mark node as used.
Definition edge.hpp:80
Edge< View > * next(void) const
Return next edge in list of edges per node.
Definition edge.hpp:101
void revert(Node< View > *d)
Revert edge to node d for matching.
Definition edge.hpp:57
bool used(Node< View > *v) const
Whether edge is used (marked or between nodes from the same scc)
Definition edge.hpp:75
Support::StaticStack< ViewNode< View > *, Region > ViewNodeStack
Stack used during matching.
void purge(void)
Purge graph if necessary (reset information to avoid overflow)
Definition graph.hpp:130
Graph(void)
Construct graph as not yet initialized.
Definition graph.hpp:40
void init(Space &home, ViewNode< View > *x)
Initialize the edges for the view node x.
Definition graph.hpp:51
unsigned int count
Marking counter.
ViewNode< View > ** view
Array of view nodes.
bool match(ViewNodeStack &m, ViewNode< View > *x)
Find a matching for node x.
Definition graph.hpp:87
int n_view
Number of view nodes.
int n_val
Number of value nodes.
void scc(void)
Compute the strongly connected components.
Definition graph.hpp:142
ValNode< View > * val
Array of value nodes.
int val(void) const
Return current value.
IterPruneVal(ViewNode< View > *x)
Initialize with edges for view node x.
void operator++(void)
Move iterator to next value (if possible)
bool operator()(void) const
Test whether iterator is still at a value or done.
Edge< View > * e
Current value edge.
Base-class for nodes (both view and value nodes)
Edge< View > * edge_fst(void) const
Return first edge (organized by bi-links)
Definition node.hpp:48
Edge< View > * iter
Next edge for computing strongly connected components.
Node(void)
Initialize.
Definition node.hpp:43
Edge< View > * edge_lst(void) const
Return last edge (organized by bi-links)
Definition node.hpp:53
unsigned int low
Values for computing strongly connected components.
Value nodes in view-value graph.
const int _val
The value of the node.
ValNode(int v)
Initialize with value v.
Definition node.hpp:76
Edge< View > * matching(void) const
Return matching edge (NULL if unmatched)
Definition node.hpp:94
ValNode< View > * _next_val
The next value node.
Edge< View > * _matching
The matching edge.
ValNode< View > * next_val(void) const
Return next value node.
Definition node.hpp:104
int val(void) const
Return value of node.
Definition node.hpp:84
ValNode< View > ** next_val_ref(void)
Return pointer to next value node fields.
Definition node.hpp:99
View nodes in view-value graph.
bool matched(void) const
Whether the node is matched.
Definition node.hpp:160
View view(void) const
Return view.
Definition node.hpp:145
void update(void)
Update size of view after change.
Definition node.hpp:155
unsigned int _size
The size of the view after last change.
Edge< View > * val_edges(void) const
Return first edge of all value edges.
Definition node.hpp:130
Edge< View > ** val_edges_ref(void)
Return pointer to first edge fields of all value edges.
Definition node.hpp:135
bool fake(void) const
Test whether node has a fake view.
Definition node.hpp:140
bool changed(void) const
Return whether view has changed its size.
Definition node.hpp:150
Edge< View > * _val_edges
The first value edge.
ViewNode(void)
Initialize node for a non-view.
Definition node.hpp:122
Handle to region.
Definition region.hpp:55
Computation spaces.
Definition core.hpp:1744
Stack with fixed number of elements.
Support classes for propagators using a view-value graph.
Finite domain integers.
Gecode toplevel namespace
Post propagator for SetVar x
Definition set.hh:773