Generated on Wed Jun 8 2016 10:43:15 for Gecode by doxygen 1.8.11
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  * Last modified:
12  * $Date: 2011-09-08 14:34:40 +0200 (Thu, 08 Sep 2011) $ by $Author: schulte $
13  * $Revision: 12395 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #ifndef __GECODE_INT_VIEW_VAL_GRAPH_HH__
41 #define __GECODE_INT_VIEW_VAL_GRAPH_HH__
42 
43 #include <gecode/int.hh>
44 
49 namespace Gecode { namespace Int { namespace ViewValGraph {
50 
57  template<class T>
58  class CombPtrFlag {
59  private:
61  ptrdiff_t cpf;
62  public:
64  CombPtrFlag(T* p1, T* p2);
66  void init(T* p1, T* p2);
68  T* ptr(T* p) const;
70  int is_set(void) const;
72  void set(void);
74  void unset(void);
75  };
76 
78  class BiLink {
79  private:
81  BiLink* _prev;
83  BiLink* _next;
84  public:
86  BiLink(void);
88  BiLink* prev(void) const;
90  BiLink* next(void) const;
92  void prev(BiLink* l);
94  void next(BiLink* l);
96  void add(BiLink* l);
98  void unlink(void);
100  void mark(void);
102  bool marked(void) const;
104  bool empty(void) const;
105  };
106 
107 
108  template<class View> class Edge;
109 
119  template<class View>
120  class Node : public BiLink {
121  public:
125  unsigned int low, min, comp;
127  Node(void);
129  Edge<View>* edge_fst(void) const;
131  Edge<View>* edge_lst(void) const;
132 
134  static void* operator new(size_t, Space&);
136  static void operator delete(void*, size_t);
138  static void operator delete(void*,Space&);
139  };
140 
145  template<class View>
146  class ValNode : public Node<View> {
147  protected:
149  const int _val;
154  public:
156  ValNode(int v);
158  ValNode(int v, ValNode<View>* n);
160  int val(void) const;
162  void matching(Edge<View>* m);
164  Edge<View>* matching(void) const;
166  ValNode<View>** next_val_ref(void);
168  ValNode<View>* next_val(void) const;
170  void next_val(ValNode<View>* v);
171  };
172 
177  template<class View>
178  class ViewNode : public Node<View> {
179  protected:
181  unsigned int _size;
183  View _view;
186  public:
188  ViewNode(void);
190  ViewNode(View x);
192  Edge<View>* val_edges(void) const;
194  Edge<View>** val_edges_ref(void);
196  bool fake(void) const;
198  View view(void) const;
200  void update(void);
202  bool changed(void) const;
204  bool matched(void) const;
205  };
206 
211  template<class View>
212  class Edge : public BiLink {
213  protected:
218  public:
224  Node<View>* dst(Node<View>* s) const;
225 
227  ViewNode<View>* view(ValNode<View>* v) const;
229  ValNode<View>* val(ViewNode<View>* x) const;
230 
232  bool used(Node<View>* v) const;
234  void use(void);
236  void free(void);
237 
239  void revert(Node<View>* d);
240 
242  Edge<View>* next_edge(void) const;
244  Edge<View>** next_edge_ref(void);
246  Edge<View>* next(void) const;
247 
249  static void* operator new(size_t, Space&);
251  static void operator delete(void*, size_t);
253  static void operator delete(void*,Space&);
254  };
255 
257  template<class View>
258  class IterPruneVal {
259  protected:
264  public:
266 
270 
272 
273  bool operator ()(void) const;
276  void operator ++(void);
278 
280 
281  int val(void) const;
284  };
285 
286 }}}
287 
293 
294 namespace Gecode { namespace Int { namespace ViewValGraph {
295 
297  template<class View>
298  class Graph {
299  protected:
305  int n_view;
307  int n_val;
309  unsigned int count;
313  void init(Space& home, ViewNode<View>* x);
315  bool match(ViewNodeStack& m, ViewNode<View>* x);
317  void scc(Space& home);
318  public:
320  Graph(void);
322  bool initialized(void) const;
324  void purge(void);
325  };
326 
327 }}}
328 
330 
331 #endif
332 
333 // STATISTICS: int-prop
334 
int is_set(void) const
Check whether flag is set.
bool marked(void *p)
Check whether p is marked.
ViewNode< View > ** view
Array of view nodes.
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
Handle to region.
Definition: region.hpp:61
void * mark(void *p)
Return marked pointer for p.
Edges in view-value graph.
Computation spaces.
Definition: core.hpp:1362
int n_view
Number of view nodes.
int n_val
Number of value nodes.
Gecode::IntSet d(v, 7)
const int _val
The value of the node.
Support::StaticStack< ViewNode< View > *, Region > ViewNodeStack
Stack used during matching.
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs p2(4, 4, 3, 3, 5)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
unsigned int _size
The size of the view after last change.
View nodes in view-value graph.
View _view
The node&#39;s view.
Edge< View > * _next_edge
Next edge in chain of value edges.
Edge< View > * _matching
The matching edge.
Class for combining two pointers with a flag.
View-value graph base class.
Iterates the values to be pruned from a view node.
Edge< View > * _val_edges
The first value edge.
const int v[7]
Definition: distinct.cpp:207
Edge< View > * e
Current value edge.
unsigned int count
Marking counter.
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
CombPtrFlag< Node< View > > sd
Combine source and destination node and flag.
Value nodes in view-value graph.
Stack with fixed number of elements.
ValNode< View > * val
Array of value nodes.
T * ptr(T *p) const
Return the other pointer when p is given.
Gecode toplevel namespace
void init(T *p1, T *p2)
Initialize with pointer p1 and p2.
Edge< View > * iter
Next edge for computing strongly connected components.
ViewNode< View > * x
View node.
Gecode::IntArgs p1(4, 2, 2, 2, 2)
ExecStatus purge(Space &home, Propagator &p, TaskArray< OptTask > &t)
Purge optional tasks that are excluded and possibly rewrite propagator.
Definition: purge.hpp:42
Base-class for nodes (both view and value nodes)
CombPtrFlag(T *p1, T *p2)
Initialize with pointer p1 and p2.
ValNode< View > * _next_val
The next value node.