2 #include "linespace.hh"
6 #include "unionfind.hh"
7 #include "idealspacing.hh"
10 const Real COLFUDGE=1e-3;
11 template class P<Real>; // ugh.
14 Spacing_problem::contains(PCol const *w)
16 for (int i=0; i< cols.size(); i++)
17 if (cols[i].pcol_l_ == w)
23 Spacing_problem::col_id(PCol const *w)const
25 for (int i=0; i< cols.size(); i++)
26 if (cols[i].pcol_l_ == w)
33 Spacing_problem::OK() const
36 for (int i = 1; i < cols.size(); i++)
37 assert(cols[i].rank_i_ > cols[i-1].rank_i_);
38 for (int i = 1; i < loose_col_arr_.size(); i++)
39 assert(loose_col_arr_[i].rank_i_ > loose_col_arr_[i-1].rank_i_);
44 Make sure no unconnected columns happen.
47 Spacing_problem::handle_loose_cols()
49 Union_find connected(cols.size());
51 for (int i=0; i < ideals.size(); i++) {
52 assert(ideals[i]->hooke > 0);
53 int l = col_id(ideals[i]->left);
54 int r = col_id(ideals[i]->right);
55 connected.connect(l,r);
57 for (int i = 0; i < cols.size(); i++)
60 for (int i=1; i < fixed.size(); i++)
61 connected.connect(fixed[i-1], fixed[i]);
63 for (int i = cols.size(); i--; ) {
64 if (! connected.equiv(fixed[0], i)) {
65 warning("unconnected column: " + String(i));
73 /** Guess a stupid position for loose columns. Put loose columns at
74 regular distances from enclosing calced columns */
76 Spacing_problem::position_loose_cols(Vector &sol_vec)const
78 if (!loose_col_arr_.size())
80 assert(sol_vec.dim());
81 Array<bool> fix_b_arr;
82 fix_b_arr.set_size(cols.size() + loose_col_arr_.size());
83 Real utter_right_f=-INFTY;
84 Real utter_left_f =INFTY;
85 for (int i=0; i < loose_col_arr_.size(); i++) {
86 fix_b_arr[loose_col_arr_[i].rank_i_] = false;
88 for (int i=0; i < cols.size(); i++) {
89 int r= cols[i].rank_i_;
91 utter_right_f = utter_right_f >? sol_vec(i);
92 utter_left_f = utter_left_f <? sol_vec(i);
94 Vector v(fix_b_arr.size());
97 for (int i=0; i < v.dim(); i++) {
99 assert(cols[j].rank_i_ == i);
103 (j>0) ?sol_vec(j-1) : utter_left_f;
105 (j < sol_vec.dim()) ? sol_vec(j) : utter_right_f;
106 int left_rank = (j>0) ? cols[j-1].rank_i_ : 0;
107 int right_rank = (j<sol_vec.dim()) ? cols[j].rank_i_ : sol_vec.dim();
109 int d_r = right_rank - left_rank;
110 Colinfo loose=loose_col_arr_[k++];
111 int r = loose.rank_i_ ;
112 assert(r > left_rank && r < right_rank);
114 v(i) = (r - left_rank)*left_pos_f/ d_r +
115 (right_rank - r) *right_pos_f /d_r;
122 Spacing_problem::check_constraints(Vector v) const
125 assert(dim == cols.size());
127 for (int i=0; i < dim; i++) {
129 if (cols[i].fixed()&&
130 abs(cols[i].fixed_position() - v(i)) > COLFUDGE)
136 Real mindist=cols[i-1].minright()
140 Real dif =v(i) - v(i-1)- mindist;
141 bool b = (dif > - COLFUDGE);
152 Spacing_problem::prepare()
158 Spacing_problem::check_feasible() const
160 Vector sol(try_initial_solution());
161 return check_constraints(sol);
164 /// generate a solution which obeys the min distances and fixed positions
166 Spacing_problem::try_initial_solution() const
170 for (int i=0; i < dim; i++) {
171 if (cols[i].fixed()) {
172 initsol(i)=cols[i].fixed_position();
175 Real r =initsol(i-1) + cols[i-1].minright();
176 if (initsol(i) < r ) {
177 warning("overriding fixed position");
183 Real mindist=cols[i-1].minright()
186 warning("Excentric column");
187 initsol(i)=initsol(i-1)+mindist;
197 Spacing_problem::find_initial_solution() const
199 Vector v(try_initial_solution());
200 assert(check_constraints(v));
204 // generate the matrices
206 Spacing_problem::make_matrices(Matrix &quad, Vector &lin, Real &c) const
211 for (int j=0; j < ideals.size(); j++){
212 Idealspacing const*i=ideals[j];
213 int l = col_id(i->left);
214 int r = col_id(i->right);
216 quad(r,r) += i->hooke;
217 quad(r,l) -= i->hooke;
218 quad(l,r) -= i->hooke;
219 quad(l,l) += i->hooke;
221 lin(r) -= i->space*i->hooke;
222 lin(l) += i->space*i->hooke;
228 // put the constraints into the LP problem
230 Spacing_problem::make_constraints(Mixed_qp& lp) const
233 for (int j=0; j < dim; j++) {
236 lp.add_fixed_var(j,c.fixed_position());
243 lp.add_inequality_cons(c1, cols[j-1].minright() +
250 Spacing_problem::solve() const
252 assert(check_feasible());
255 Mixed_qp lp(cols.size());
256 make_matrices(lp.quad,lp.lin, lp.const_term);
257 make_constraints(lp);
258 Vector start=find_initial_solution();
259 Vector sol(lp.solve(start));
260 if (!check_constraints(sol)) {
261 WARN << "solution doesn't satisfy constraints.\n" ;
263 Real energy_f =lp.eval(sol);
264 position_loose_cols(sol);
266 Array<Real> posns(sol);
268 posns.push(energy_f);
273 add one column to the problem.
276 Spacing_problem::add_column(PCol *col, bool fixed, Real fixpos)
278 Colinfo c(col,(fixed)? &fixpos : 0);
280 c.rank_i_ = cols.top().rank_i_+1;
287 Spacing_problem::error_pcol_l_arr()const
290 for (int i=0; i< cols.size(); i++)
292 retval.push(cols[i].pcol_l_);
293 for (int i=0; i < loose_col_arr_.size(); i++) {
294 retval.push(loose_col_arr_[i].pcol_l_);
300 Spacing_problem::loosen_column(int i)
302 Colinfo c=cols.get(i);
303 for (int i=0; i < ideals.size(); ) {
304 Idealspacing const *i_l =ideals[i];
305 if (i_l->left == c.pcol_l_ || i_l->right == c.pcol_l_)
313 for (; i < loose_col_arr_.size(); i++) {
314 if (loose_col_arr_[i].rank_i_ > c.rank_i_)
317 loose_col_arr_.insert(c,i);
321 Spacing_problem::add_ideal(Idealspacing const *i)
323 PCol const *l =i->left;
324 PCol const *r= i->right;
326 if (!contains(l) || !contains(r)) {
333 Spacing_problem::print_ideal(Idealspacing const *id)const
336 int l = col_id(id->left);
337 int r = col_id(id->right);
339 mtor << "between " << l <<","<<r<<":" ;
345 Spacing_problem::print() const
348 for (int i=0; i < cols.size(); i++) {
349 mtor << "col " << i<<' ';
352 for (int i=0; i < ideals.size(); i++) {
353 print_ideal(ideals[i]);
359 /* **************** */
362 Colinfo::print() const
367 mtor << "fixed at " << fixed_position()<<", ";
369 mtor << "[" << minleft() << ", " << minright() << "]";
374 Colinfo::Colinfo(PCol *col_l, Real const *fixed_C)
377 fixpos_p_.set_l(fixed_C);
380 width = pcol_l_->width();