TdZdd  1.1
A top-down/breadth-first decision diagram manipulation framework
FrontierBasedSearch.hpp
1 /*
2  * TdZdd: a Top-down/Breadth-first Decision Diagram Manipulation Framework
3  * by Hiroaki Iwashita <iwashita@erato.ist.hokudai.ac.jp>
4  * Copyright (c) 2014 ERATO MINATO Project
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining a
7  * copy of this software and associated documentation files (the "Software"),
8  * to deal in the Software without restriction, including without limitation
9  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
10  * and/or sell copies of the Software, and to permit persons to whom the
11  * Software is furnished to do so, subject to the following conditions:
12  *
13  * The above copyright notice and this permission notice shall be included in
14  * all copies or substantial portions of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22  * DEALINGS IN THE SOFTWARE.
23  */
24 
25 #pragma once
26 
27 #include <cassert>
28 #include <cstring>
29 #include <stdint.h>
30 #include <iostream>
31 #include <stdexcept>
32 #include <vector>
33 
34 #include "../DdSpec.hpp"
35 #include "../util/Graph.hpp"
36 
37 namespace tdzdd {
38 
39 struct FrontierBasedSearchCount {
40  int16_t uec;
41 
42  FrontierBasedSearchCount()
43  : uec(0) {
44  }
45 
46  FrontierBasedSearchCount(int16_t uncoloredEdgeComponents)
47  : uec(uncoloredEdgeComponents) {
48  }
49 
50  size_t hash() const {
51  return uec;
52  }
53 
54  bool operator==(FrontierBasedSearchCount const& o) const {
55  return uec == o.uec;
56  }
57 
58  friend std::ostream& operator<<(std::ostream& os,
59  FrontierBasedSearchCount const& o) {
60  return os << o.uec;
61  }
62 };
63 
64 class FrontierBasedSearchMate {
65 public:
66  typedef int16_t Offset;
67  static Offset const UNCOLORED = 32766;
68  static Offset const UNCOLORED_EDGE_COMPONENT = 32767;
69 
70 private:
71  Offset hoc;
72  Offset nxt;
73 
74  /*
75  * ┌────────────────────────┌─────────────────────┐
76  * │ ┌────┐────────┐ │ ┌────┐────────┐ │
77  * ┌┼───┴┐ ┌┼────┐ ┌┼────┐┌┼───┴┐ ┌┼────┐ ┌┼───┴┐
78  * │color│ │head │ │head ││color│ │head │ │head │
79  * ├─────┤ ├─────┤ ├─────┤├─────┤ ├─────┤ ├─────┤
80  * │next─┼──┤next─┼──┤next ││next─┼──┤next─┼──┤next │
81  * └─────┘ └─────┘ └─────┘└─────┘ └─────┘ └─────┘
82  * head head coloredTail
83  */
84 
85 public:
86  FrontierBasedSearchMate(Offset hoc = 0)
87  : hoc(hoc), nxt(0) {
88  }
89 
90  bool operator==(FrontierBasedSearchMate const& o) const {
91  return this == &o;
92  }
93 
94  bool operator!=(FrontierBasedSearchMate const& o) const {
95  return this != &o;
96  }
97 
98  void clear() {
99  hoc = 0;
100  nxt = 0;
101  }
102 
103  bool isHead() const {
104  return hoc >= 0;
105  }
106 
107  bool isTail() const {
108  return nxt == 0;
109  }
110 
111  bool isIsolated() const {
112  return isHead() && isTail();
113  }
114 
115  FrontierBasedSearchMate& head() {
116  return isHead() ? *this : *(this + hoc);
117  }
118 
119  FrontierBasedSearchMate const& head() const {
120  return isHead() ? *this : *(this + hoc);
121  }
122 
123  FrontierBasedSearchMate& next() {
124  return *(this + nxt);
125  }
126 
127  FrontierBasedSearchMate const& next() const {
128  return *(this + nxt);
129  }
130 
131  bool isColored() const {
132  return head().hoc < UNCOLORED;
133  }
134 
135  bool isUncoloredEdgeComponent() const {
136  return head().hoc == UNCOLORED_EDGE_COMPONENT;
137  }
138 
139  bool isColoredTail() const {
140  return hoc == 0 || (hoc < 0 && hoc + (this + hoc)->hoc == 0);
141  }
142 
143  bool hasSameColorAs(FrontierBasedSearchMate const& o) const {
144  FrontierBasedSearchMate const* p = &head();
145  FrontierBasedSearchMate const* q = &o.head();
146  return p + p->hoc == q + q->hoc;
147  }
148 
149  FrontierBasedSearchMate const* findColorPredecessor(
150  FrontierBasedSearchMate const& o) const {
151  assert(o.isColoredTail());
152  FrontierBasedSearchMate const* p = &o;
153 
154  while (--p >= this) {
155  FrontierBasedSearchMate const* p1 = &p->head();
156  if (p1 + p1->hoc == &o) return p;
157  }
158 
159  return 0;
160  }
161 
162  void mergeLists(FrontierBasedSearchMate& o1, FrontierBasedSearchMate& o2) {
163  FrontierBasedSearchMate* p1 = &o1.head();
164  FrontierBasedSearchMate* p2 = &o2.head();
165  if (p1 == p2) return;
166  if (p1 > p2) std::swap(p1, p2);
167 
168  bool painting; // merging colored and uncolored
169 
170  if (p2->hoc < UNCOLORED) {
171  painting = (p1->hoc >= UNCOLORED);
172 
173  if (painting || p1 + p1->hoc < p2 + p2->hoc) {
174  p1->hoc = p2->hoc + (p2 - p1); // updated if uncolored element becomes tail
175  }
176  }
177  else {
178  painting = (p1->hoc < UNCOLORED);
179 
180  if (p1->hoc == UNCOLORED) {
181  p1->hoc = UNCOLORED_EDGE_COMPONENT;
182  }
183  }
184 
185  for (FrontierBasedSearchMate* q = p2;; q += q->nxt) {
186  q->hoc = p1 - q;
187  if (q->nxt == 0) break;
188  }
189 
190  FrontierBasedSearchMate* p = p1;
191  FrontierBasedSearchMate* q = p2;
192 
193  while (true) {
194  assert(p != q);
195  FrontierBasedSearchMate* pp = p + p->nxt;
196  assert(p <= pp && pp != q);
197 
198  while (p < pp && pp < q) {
199  p = pp;
200  pp += pp->nxt;
201  assert(p <= pp && pp != q);
202  }
203 
204  assert(p == pp || q < pp);
205  p->nxt = q - p;
206  if (p == pp) break;
207  p = q, q = pp;
208  }
209 
210  if (painting) {
211  while (q->nxt) {
212  q += q->nxt;
213  }
214 
215  FrontierBasedSearchMate* pp = p1 + p1->hoc;
216 
217  if (pp < q) { // q must be an uncolored tail.
218  for (p = this; p <= pp; ++p) {
219  if (p + p->hoc == pp) p->hoc = q - p;
220  }
221  }
222  }
223  }
224 
225  void replaceHeadWith(FrontierBasedSearchMate& newHead) const {
226  FrontierBasedSearchMate const* p = &head();
227  FrontierBasedSearchMate* q = &newHead;
228 
229  q->hoc = (p->hoc < UNCOLORED) ? p->hoc + (p - q) : p->hoc;
230 
231  while (q->nxt > 0) {
232  q += q->nxt;
233  q->hoc = &newHead - q;
234  }
235  }
236 
237  void removeFromList(FrontierBasedSearchMate const& o) {
238  if (o.isColoredTail()) {
239  assert(o.nxt == 0);
240  FrontierBasedSearchMate const* pp = findColorPredecessor(o);
241  if (pp == 0) return;
242 
243  for (FrontierBasedSearchMate* p = this; p <= pp; ++p) {
244  if (p + p->hoc == &o) p->hoc = pp - p;
245  if (p + p->nxt == &o) p->nxt = 0;
246  }
247  }
248  else if (o.nxt == 0) {
249  for (FrontierBasedSearchMate* p = this; p <= &o; ++p) {
250  if (p + p->nxt == &o) p->nxt = 0;
251  }
252  }
253  else {
254  for (FrontierBasedSearchMate* p = this; p <= &o; ++p) {
255  if (p + p->nxt == &o) p->nxt += o.nxt;
256  }
257  }
258  }
259 
260  friend std::ostream& operator<<(std::ostream& os,
261  FrontierBasedSearchMate const& o) {
262  return os << "<" << o.hoc << "," << o.nxt << ">";
263  }
264 };
265 
266 class FrontierBasedSearch: public tdzdd::HybridDdSpec<FrontierBasedSearch,
267  FrontierBasedSearchCount,FrontierBasedSearchMate,2> {
268  typedef FrontierBasedSearchCount Count;
269  typedef FrontierBasedSearchMate Mate;
270 
271  Graph const& graph;
272  int const m;
273  int const n;
274  int const mateSize;
275  std::vector<Mate> initialMate;
276  int numUEC;
277  bool const noLoop;
278  bool const lookahead;
279 
280  int takable(Count& c, Mate const* mate, Graph::EdgeInfo const& e) const {
281  Mate const& w1 = mate[e.v1 - e.v0];
282  Mate const& w2 = mate[e.v2 - e.v0];
283 
284  // don't connect again
285  if (noLoop && w1.head() == w2.head()) return false;
286 
287  // don't connect different colors
288  if (w1.isColored() && w2.isColored() && !w1.hasSameColorAs(w2)) return false;
289 
290  if (e.v1final && e.v2final) {
291  if (w1.isIsolated() && w2.isIsolated()) { // new component leaves immediately
292  if (w2.isColored()) {
293  // don't leave the color unconnected
294  if (!w2.isColoredTail()) return false;
295  if (mate[1].findColorPredecessor(w2)) return false;
296  }
297  else {
298  if (w1.isColored()) {
299  // don't leave the color unconnected
300  if (!w1.isColoredTail()) return false;
301  }
302  else {
303  if (c.uec == 0) return false;
304  if (c.uec > 0) --c.uec;
305  }
306  }
307  }
308  else if (w1.isHead() && w2 == w1.next() && w2.isTail()) { // existing component leaves
309  if (w1.isColored()) {
310  // don't leave the color unconnected
311  if (!w2.isColoredTail()) return false;
312  if (w2.findColorPredecessor(mate[1])) return false;
313  }
314  else {
315  assert(w1.isUncoloredEdgeComponent());
316  if (c.uec == 0) return false;
317  if (c.uec > 0) --c.uec;
318  }
319  }
320  }
321 
322  if (e.finalEdge && c.uec > 0) return false; //TODO 枝刈り可能
323  return true;
324  }
325 
326  bool doTake(Count& count, Mate* mate, Graph::EdgeInfo const& e) const {
327  Count c = count;
328 
329  if (!takable(c, mate, e)) return false;
330 
331  count = c;
332  mate[0].mergeLists(mate[e.v1 - e.v0], mate[e.v2 - e.v0]);
333  return true;
334  }
335 
336  bool doNotTake(Count& count, Mate* mate, Graph::EdgeInfo const& e) const {
337  Count c = count;
338  Mate const& w1 = mate[e.v1 - e.v0];
339  Mate const& w2 = mate[e.v2 - e.v0];
340 
341  if (e.v1final && w1.isIsolated()) {
342  if (w1.isColored()) {
343  // don't leave the color unconnected
344  if (!w1.isColoredTail()) return false;
345  }
346  else if (c.uec >= 0 && w1.isUncoloredEdgeComponent()) {
347  if (c.uec == 0) return false;
348  --c.uec;
349  }
350  }
351 
352  if (e.v2final && w2.isIsolated()) {
353  if (w2.isColored()) {
354  // don't leave the color unconnected
355  if (!w2.isColoredTail()) return false;
356  if (mate[1].findColorPredecessor(w2)) return false;
357  }
358  else if (c.uec >= 0 && w2.isUncoloredEdgeComponent()) {
359  if (c.uec == 0) return false;
360  --c.uec;
361  }
362  }
363 
364  if (e.v1final && e.v2final && w1.isHead() && w2 == w1.next()
365  && w2.isTail()) { // existing component leaves) {
366  if (w1.isColored()) {
367  // don't leave the color unconnected
368  if (!w2.isColoredTail()) return false;
369  if (w2.findColorPredecessor(mate[1])) return false;
370  }
371  else {
372  assert(w1.isUncoloredEdgeComponent());
373  if (c.uec == 0) return false;
374  if (c.uec > 0) --c.uec;
375  }
376  }
377 
378  if (e.finalEdge && c.uec > 0) return false; //TODO 枝刈り可能
379  count = c;
380  return true;
381  }
382 
383  void update(Mate* mate, Graph::EdgeInfo const& e,
384  Graph::EdgeInfo const& ee) const {
385  int const d = ee.v0 - e.v0;
386  assert(d >= 0);
387  Mate* p1 = &mate[e.v1 - e.v0];
388  Mate* p2 = &mate[e.v2 - e.v0];
389  Mate* pd = p1 + d;
390 
391  for (Mate* q = p1; q < pd; ++q) {
392  Mate* qq = &q->next();
393  if (qq >= pd) {
394  q->replaceHeadWith(*qq);
395  }
396  }
397 
398  if (e.v2final) {
399  mate[0].removeFromList(*p2);
400  p2->clear();
401  }
402 
403  if (e.v1final) {
404  mate[0].removeFromList(*p1);
405  p1->clear();
406  }
407 
408  if (d > 0) {
409  std::memmove(p1, pd, (mateSize - d) * sizeof(*mate));
410  for (int i = mateSize - d; i < mateSize; ++i) {
411  p1[i] = initialMate[ee.v0 + i];
412  }
413  }
414  }
415 
416 public:
417  FrontierBasedSearch(Graph const& graph, int numUEC = -1,
418  bool noLoop = false, bool lookahead = true)
419  : graph(graph), m(graph.vertexSize()), n(graph.edgeSize()),
420  mateSize(graph.maxFrontierSize()), initialMate(1 + m + mateSize),
421  numUEC(numUEC), noLoop(noLoop), lookahead(lookahead) {
422  this->setArraySize(mateSize);
423 
424  std::vector<int> rootOfColor(graph.numColor() + 1);
425  for (int v = 1; v <= m; ++v) {
426  rootOfColor[graph.colorNumber(v)] = v;
427  }
428  for (int v = 1; v <= m; ++v) {
429  int k = graph.colorNumber(v);
430  int hoc = (k > 0) ? rootOfColor[k] - v : Mate::UNCOLORED;
431  initialMate[v] = Mate(hoc);
432  }
433  }
434 
435  int getRoot(Count& count, Mate* mate) const {
436  int const v0 = graph.edgeInfo(0).v0;
437 
438  count = Count(numUEC);
439 
440  for (int i = 0; i < mateSize; ++i) {
441  mate[i] = initialMate[v0 + i];
442  }
443 
444  return n;
445  }
446 
447  int getChild(Count& count, Mate* mate, int level, int take) const {
448  assert(1 <= level && level <= n);
449  int i = n - level;
450  Graph::EdgeInfo const* e = &graph.edgeInfo(i);
451 
452  if (take) {
453  if (!doTake(count, mate, *e)) return 0;
454  }
455  else {
456  if (!doNotTake(count, mate, *e)) return 0;
457  }
458 
459  if (++i == n) return -1;
460 
461  Graph::EdgeInfo const* ee = &graph.edgeInfo(i);
462  update(mate, *e, *ee);
463 
464  while (lookahead) {
465  e = ee;
466 
467  Count c = count;
468  if (takable(c, mate, *e)) break;
469  if (!doNotTake(count, mate, *e)) return 0;
470 
471  if (++i == n) return -1;
472 
473  ee = &graph.edgeInfo(i);
474  update(mate, *e, *ee);
475  }
476 
477  assert(i < n);
478  return n - i;
479  }
480 
481  size_t hashCode(Count const& count) const {
482  return count.hash();
483  }
484 };
485 
486 } // namespace tdzdd
Abstract class of DD specifications using both scalar and POD array states.
Definition: DdSpec.hpp:526