Generated on Tue Jan 26 2021 00:00:00 for Gecode by doxygen 1.9.1
graph.hpp
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  *
6  * Copyright:
7  * Christian Schulte, 2003
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include <climits>
35 
36 namespace Gecode { namespace Int { namespace ViewValGraph {
37 
38  template<class View>
41  : view(NULL), val(NULL), n_view(0), n_val(0), count(1U) {}
42 
43  template<class View>
45  Graph<View>::operator bool(void) const {
46  return view != NULL;
47  }
48 
49  template<class View>
50  forceinline void
52  Edge<View>** edge_p = x->val_edges_ref();
53  ViewValues<View> xi(x->view());
54  ValNode<View>** v = &val;
55  while (xi() && (*v != NULL)) {
56  if ((*v)->val() == xi.val()) {
57  // Value node does already exist, create new edge
58  *edge_p = new (home) Edge<View>(*v,x);
59  edge_p = (*edge_p)->next_edge_ref();
60  v = (*v)->next_val_ref();
61  ++xi;
62  } else if ((*v)->val() < xi.val()) {
63  // Skip to next value node
64  v = (*v)->next_val_ref();
65  } else {
66  // Value node does not yet exist, create and link it
67  ValNode<View>* nv = new (home) ValNode<View>(xi.val(),*v);
68  *v = nv; v = nv->next_val_ref();
69  *edge_p = new (home) Edge<View>(nv,x);
70  edge_p = (*edge_p)->next_edge_ref();
71  ++xi; n_val++;
72  }
73  }
74  // Create missing value nodes
75  while (xi()) {
76  ValNode<View>* nv = new (home) ValNode<View>(xi.val(),*v);
77  *v = nv; v = nv->next_val_ref();
78  *edge_p = new (home) Edge<View>(nv,x);
79  edge_p = (*edge_p)->next_edge_ref();
80  ++xi; n_val++;
81  }
82  *edge_p = NULL;
83  }
84 
85  template<class View>
86  forceinline bool
88  count++;
89  start:
90  // Try to find matching edge cheaply: is there a free edge around?
91  {
92  Edge<View>* e = x->val_edges();
93  // This holds true as domains are never empty
94  assert(e != NULL);
95  do {
96  if (!e->val(x)->matching()) {
97  e->revert(x); e->val(x)->matching(e);
98  // Found a matching, revert all edges on stack
99  while (!m.empty()) {
100  x = m.pop(); e = x->iter;
101  e->val(x)->matching()->revert(e->val(x));
102  e->revert(x); e->val(x)->matching(e);
103  }
104  return true;
105  }
106  e = e->next_edge();
107  } while (e != NULL);
108  }
109  // No, find matching edge by augmenting path method
110  Edge<View>* e = x->val_edges();
111  do {
112  if (e->val(x)->matching()->view(e->val(x))->min < count) {
113  e->val(x)->matching()->view(e->val(x))->min = count;
114  m.push(x); x->iter = e;
115  x = e->val(x)->matching()->view(e->val(x));
116  goto start;
117  }
118  next:
119  e = e->next_edge();
120  } while (e != NULL);
121  if (!m.empty()) {
122  x = m.pop(); e = x->iter; goto next;
123  }
124  // All nodes and edges unsuccessfully tried
125  return false;
126  }
127 
128  template<class View>
129  forceinline void
131  if (count > (UINT_MAX >> 1)) {
132  count = 1;
133  for (int i=0; i<n_view; i++)
134  view[i]->min = 0;
135  for (ValNode<View>* v = val; v != NULL; v = v->next_val())
136  v->min = 0;
137  }
138  }
139 
140  template<class View>
141  forceinline void
143  Region r;
144 
145  Support::StaticStack<Node<View>*,Region> scc(r,n_val+n_view);
146  Support::StaticStack<Node<View>*,Region> visit(r,n_val+n_view);
147 
148  count++;
149  unsigned int cnt0 = count;
150  unsigned int cnt1 = count;
151 
152  for (int i=0; i<n_view; i++)
153  /*
154  * The following test is subtle: for scc, the test should be:
155  * view[i]->min < count
156  * However, if view[i] < count-1, then the node has already been
157  * reached on a path and all edges connected to the node have been
158  * marked anyway! So just ignore this node altogether for scc.
159  */
160  if (view[i]->min < count-1) {
161  Node<View>* w = view[i];
162  start:
163  w->low = w->min = cnt0++;
164  scc.push(w);
165  Edge<View>* e = w->edge_fst();
166  while (e != w->edge_lst()) {
167  if (e->dst(w)->min < count) {
168  visit.push(w); w->iter = e;
169  w=e->dst(w);
170  goto start;
171  }
172  next:
173  if (e->dst(w)->low < w->min)
174  w->min = e->dst(w)->low;
175  e = e->next();
176  }
177  if (w->min < w->low) {
178  w->low = w->min;
179  } else {
180  Node<View>* v;
181  do {
182  v = scc.pop();
183  v->comp = cnt1;
184  v->low = UINT_MAX;
185  } while (v != w);
186  cnt1++;
187  }
188  if (!visit.empty()) {
189  w=visit.pop(); e=w->iter; goto next;
190  }
191  }
192  count = cnt0+1;
193  }
194 
195 
196 }}}
197 
198 // STATISTICS: int-prop
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
Edges in view-value graph.
ValNode< View > * val(ViewNode< View > *x) const
Return value node when view node x is given.
Definition: edge.hpp:69
Edge< View > * next_edge(void) const
Return next edge in list of value edges.
Definition: edge.hpp:91
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
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
View-value graph base class.
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
bool match(ViewNodeStack &m, ViewNode< View > *x)
Find a matching for node x.
Definition: graph.hpp:87
void scc(void)
Compute the strongly connected components.
Definition: graph.hpp:142
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.
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.
ValNode< View > ** next_val_ref(void)
Return pointer to next value node fields.
Definition: node.hpp:99
View nodes in view-value graph.
Value iterator for integer views.
Definition: view.hpp:94
int val(void) const
Return current value.
Handle to region.
Definition: region.hpp:55
Computation spaces.
Definition: core.hpp:1742
Stack with fixed number of elements.
void push(const T &x)
Push element x on top of stack.
T pop(void)
Pop topmost element from stack and return it.
bool empty(void) const
Test whether stack is empty.
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
Definition: count.cpp:40
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
Gecode::IntArgs i({1, 2, 3, 4})
const int v[7]
Definition: distinct.cpp:259
#define forceinline
Definition: config.hpp:185