Generated on Sat Feb 7 2015 02:01:26 for Gecode by doxygen 1.8.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  * 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 
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.
Edge< View > * next_edge(void) const
Return next edge in list of value edges.
Definition: edge.hpp:95
bool initialized(void) const
Test whether graph has been initialized.
Definition: graph.hpp:49
Edge< View > * edge_fst(void) const
Return first edge (organized by bi-links)
Definition: node.hpp:52
ViewNode< View > ** view
Array of view nodes.
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
ValNode< View > * val(ViewNode< View > *x) const
Return value node when view node x is given.
Definition: edge.hpp:73
Edge< View > * val_edges(void) const
Return first edge of all value edges.
Definition: node.hpp:134
Edge< View > ** next_edge_ref(void)
Return reference to next edge in list of value edges.
Definition: edge.hpp:100
void update(void)
Update size of view after change.
Definition: node.hpp:159
IterPruneVal(ViewNode< View > *x)
Initialize with edges for view node x.
Edge< View > * next(void) const
Return next edge in list of edges per node.
Definition: edge.hpp:105
ViewNode< View > * view(ValNode< View > *v) const
Return view node when value node v is given.
Definition: edge.hpp:68
Handle to region.
Definition: region.hpp:61
Edges in view-value graph.
ValNode< View > * next_val(void) const
Return next value node.
Definition: node.hpp:108
Computation spaces.
Definition: core.hpp:1362
ValNode< View > ** next_val_ref(void)
Return pointer to next value node fields.
Definition: node.hpp:103
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.
int val(void) const
Return value of node.
Definition: node.hpp:88
View view(void) const
Return view.
Definition: node.hpp:149
Support::StaticStack< ViewNode< View > *, Region > ViewNodeStack
Stack used during matching.
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
ViewNode(void)
Initialize node for a non-view.
Definition: node.hpp:126
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.
unsigned int low
Values for computing strongly connected components.
void revert(Node< View > *d)
Revert edge to node d for matching.
Definition: edge.hpp:61
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.
void purge(void)
Purge graph if necessary (reset information to avoid overflow)
Definition: graph.hpp:134
Edge< View > * edge_lst(void) const
Return last edge (organized by bi-links)
Definition: node.hpp:57
Graph(void)
Construct graph as not yet initialized.
Definition: graph.hpp:44
void init(Space &home, ViewNode< View > *x)
Initialize the edges for the view node x.
Definition: graph.hpp:55
bool fake(void) const
Test whether node has a fake view.
Definition: node.hpp:144
View-value graph base class.
bool used(Node< View > *v) const
Whether edge is used (marked or between nodes from the same scc)
Definition: edge.hpp:79
ValNode(int v)
Initialize with value v.
Definition: node.hpp:80
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.
Edge< View > * matching(void) const
Return matching edge (NULL if unmatched)
Definition: node.hpp:98
unsigned int count
Marking counter.
void use(void)
Mark node as used.
Definition: edge.hpp:84
void operator++(void)
Move iterator to next value (if possible)
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
CombPtrFlag< Node< View > > sd
Combine source and destination node and flag.
Edge< View > ** val_edges_ref(void)
Return pointer to first edge fields of all value edges.
Definition: node.hpp:139
Value nodes in view-value graph.
bool changed(void) const
Return whether view has changed its size.
Definition: node.hpp:154
Stack with fixed number of elements.
ValNode< View > * val
Array of value nodes.
void free(void)
Unmark node as used.
Definition: edge.hpp:89
int val(void) const
Return current value.
bool operator()(void) const
Test whether iterator is still at a value or done.
T * ptr(T *p) const
Return the other pointer when p is given.
Gecode toplevel namespace
void scc(Space &home)
Compute the strongly connected components.
Definition: graph.hpp:146
Node< View > * dst(Node< View > *s) const
Return destination of edge when source s is given.
Definition: edge.hpp:55
void init(T *p1, T *p2)
Initialize with pointer p1 and p2.
bool match(ViewNodeStack &m, ViewNode< View > *x)
Find a matching for node x.
Definition: graph.hpp:91
Edge< View > * iter
Next edge for computing strongly connected components.
ViewNode< View > * x
View node.
Gecode::IntArgs p1(4, 2, 2, 2, 2)
Edge(ValNode< View > *v, ViewNode< View > *x)
Construct new edge between x and v.
Definition: edge.hpp:42
Node(void)
Initialize.
Definition: node.hpp:47
Base-class for nodes (both view and value nodes)
CombPtrFlag(T *p1, T *p2)
Initialize with pointer p1 and p2.
bool matched(void) const
Whether the node is matched.
Definition: node.hpp:164
ValNode< View > * _next_val
The next value node.