Generated on Tue Jan 26 2021 00:00:00 for Gecode by doxygen 1.9.1
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 
45 namespace Gecode { namespace Int { namespace ViewValGraph {
46 
53  template<class T>
54  class CombPtrFlag {
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;
162  ValNode<View>** next_val_ref(void);
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;
179  View _view;
182  public:
184  ViewNode(void);
186  ViewNode(View x);
188  Edge<View>* val_edges(void) const;
190  Edge<View>** val_edges_ref(void);
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;
240  Edge<View>** next_edge_ref(void);
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>
254  class IterPruneVal {
255  protected:
260  public:
262 
266 
268 
269  bool operator ()(void) const;
272  void operator ++(void);
274 
276 
277  int val(void) const;
280  };
281 
282 }}}
283 
289 
290 namespace Gecode { namespace Int { namespace ViewValGraph {
291 
293  template<class View>
294  class Graph {
295  protected:
301  int n_view;
303  int n_val;
305  unsigned int count;
309  void init(Space& home, ViewNode<View>* x);
311  bool match(ViewNodeStack& m, 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 
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
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
View-value graph base class.
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.
Iterates the values to be pruned from a view node.
ViewNode< View > * x
View node.
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:1742
Stack with fixed number of elements.
Gecode::IntSet d(v, 7)
const int v[7]
Definition: distinct.cpp:259