TdZdd  1.1
A top-down/breadth-first decision diagram manipulation framework
LinearConstraints.hpp
1 /*
2  * Top-Down ZDD Construction Library for Frontier-Based Search
3  * by Hiroaki Iwashita <iwashita@erato.ist.hokudai.ac.jp>
4  * Copyright (c) 2012 Japan Science and Technology Agency
5  * $Id: DegreeConstraint.hpp 421 2013-02-25 05:33:17Z iwashita $
6  */
7 
8 #pragma once
9 
10 #include <cassert>
11 #include <map>
12 #include <vector>
13 
14 #include "../DdSpec.hpp"
15 
16 namespace tdzdd {
17 
18 template<typename T>
19 class LinearConstraints: public PodArrayDdSpec<LinearConstraints<T>,T,2> {
20  struct CheckItem {
21  int index;
22  T weight;
23  T addMin;
24  T addMax;
25  T lowerBound;
26  T upperBound;
27  bool finalChoice;
28 
29  CheckItem(int i,
30  T const& w,
31  T const& min,
32  T const& max,
33  T const& lb,
34  T const& ub,
35  bool fc) :
36  index(i),
37  weight(w),
38  addMin(min),
39  addMax(max),
40  lowerBound(lb),
41  upperBound(ub),
42  finalChoice(fc) {
43  }
44  };
45 
46  typedef std::vector<CheckItem> Checklist;
47 
48  int const n;
49  std::vector<Checklist> checklists;
50  int arraySize;
51  int constraintId;
52  bool isFalse;
53 
54 public:
55  LinearConstraints(int n) :
56  n(n),
57  checklists(n + 1),
58  arraySize(0),
59  constraintId(0),
60  isFalse(false) {
61  assert(n >= 1);
62  }
63 
64  void addConstraint(std::map<int,T> const& expr, T const& lb, T const& ub) {
65  if (isFalse) return;
66  T min = 0;
67  T max = 0;
68  for (typename std::map<int,T>::const_iterator t = expr.begin();
69  t != expr.end(); ++t) {
70  T const& w = t->second;
71  if (w > 0) max += w;
72  else if (w < 0) min += w;
73  }
74  if (lb <= min && max <= ub) return;
75  if (ub < lb || max < lb || ub < min) {
76  isFalse = true;
77  return;
78  }
79  if (expr.empty()) return;
80 
81  min = 0;
82  max = 0;
83  bool fc = true;
84  for (typename std::map<int,T>::const_iterator t = expr.begin();
85  t != expr.end(); ++t) {
86  Checklist& list = checklists[t->first];
87  T const& w = t->second;
88  list.push_back(CheckItem(constraintId, w, min, max, lb, ub, fc));
89  if (w > 0) max += w;
90  else if (w < 0) min += w;
91  fc = false;
92  }
93  ++constraintId;
94  }
95 
96  void update() {
97  std::vector<int> indexMap(constraintId);
98  for (int id = 0; id < constraintId; ++id) {
99  indexMap[id] = -1;
100  }
101  std::vector<int> freeIndex;
102 
103  for (int i = n; i >= 1; --i) {
104  Checklist& list = checklists[i];
105 
106  for (typename Checklist::iterator t = list.begin(); t != list.end();
107  ++t) {
108  int id = t->index;
109 
110  if (indexMap[id] < 0) {
111  if (freeIndex.empty()) {
112  indexMap[id] = arraySize++;
113  }
114  else {
115  indexMap[id] = freeIndex.back();
116  freeIndex.pop_back();
117  }
118  }
119 
120  t->index = indexMap[id];
121  }
122 
123  for (typename Checklist::iterator t = list.begin(); t != list.end();
124  ++t) {
125  if (t->finalChoice) {
126  freeIndex.push_back(t->index);
127  }
128  }
129  }
130 
131  this->setArraySize(arraySize);
132  }
133 
134  int getRoot(T* value) const {
135  if (isFalse) return 0;
136 
137  for (int k = 0; k < arraySize; ++k) {
138  value[k] = 0;
139  }
140 
141  return n;
142  }
143 
144  int getChild(T* value, int level, bool take) const {
145  Checklist const& list = checklists[level];
146 
147  for (typename Checklist::const_iterator t = list.begin();
148  t != list.end(); ++t) {
149  T& v = value[t->index];
150  if (take) v += t->weight;
151  if (v + t->addMax < t->lowerBound || t->upperBound < v + t->addMin)
152  return 0;
153  if (t->lowerBound <= v + t->addMin
154  && v + t->addMax <= t->upperBound) // state compression
155  v = t->lowerBound - t->addMin;
156  if (t->finalChoice) v = 0;
157  }
158 
159  return (--level >= 1) ? level : -1;
160  }
161 };
162 
163 } // namespace tdzdd