Graphviz  2.35.20130930.0449
quad_prog_vpsc.c
Go to the documentation of this file.
1 /* $Id$ $Revision$ */
2 /* vim:set shiftwidth=4 ts=8: */
3 
20 /**********************************************************
21  *
22  * Solve a quadratic function f(X) = X' e->A X + b X
23  * subject to a set of separation constraints e->cs
24  *
25  * Tim Dwyer, 2006
26  **********************************************************/
27 
28 #include "digcola.h"
29 #ifdef IPSEPCOLA
30 #include <math.h>
31 #include <stdlib.h>
32 #include <time.h>
33 #include <stdio.h>
34 #include <float.h>
35 #include <assert.h>
36 #include "matrix_ops.h"
37 #include "kkutils.h"
38 #include <csolve_VPSC.h>
39 #include "quad_prog_vpsc.h"
40 #include "quad_prog_solver.h"
41 
42 /* #define CONMAJ_LOGGING 1 */
43 #define quad_prog_tol 1e-4
44 
45 /*
46  * Use gradient-projection to solve Variable Placement with Separation Constraints problem.
47  */
48 int
49 constrained_majorization_vpsc(CMajEnvVPSC * e, float *b, float *place,
50  int max_iterations)
51 {
52  int i, j, counter;
53  float *g, *old_place, *d;
54  /* for laplacian computation need number of real vars and those
55  * dummy vars included in lap
56  */
57  int n = e->nv + e->nldv;
58  boolean converged = FALSE;
59 #ifdef CONMAJ_LOGGING
60  static int call_no = 0;
61 #endif /* CONMAJ_LOGGING */
62 
63  if (max_iterations == 0)
64  return 0;
65  g = e->fArray1;
66  old_place = e->fArray2;
67  d = e->fArray3;
68  /* fprintf(stderr,"Entered: constrained_majorization_vpsc, #constraints=%d\n",e->m); */
69  if (e->m > 0) {
70  for (i = 0; i < n; i++) {
71  setVariableDesiredPos(e->vs[i], place[i]);
72  }
73  /* fprintf(stderr," calling satisfyVPSC...\n"); */
74  satisfyVPSC(e->vpsc);
75  for (i = 0; i < n; i++) {
76  place[i] = getVariablePos(e->vs[i]);
77  /* fprintf(stderr,"vs[%d]=%f\n",i,place[i]); */
78  }
79  /* fprintf(stderr," done.\n"); */
80  }
81 #ifdef CONMAJ_LOGGING
82  float prev_stress = 0;
83  for (i = 0; i < n; i++) {
84  prev_stress += 2 * b[i] * place[i];
85  for (j = 0; j < n; j++) {
86  prev_stress -= e->A[i][j] * place[j] * place[i];
87  }
88  }
89  FILE *logfile = fopen("constrained_majorization_log", "a");
90 
91  /* fprintf(logfile,"grad proj %d: stress=%f\n",call_no,prev_stress); */
92 #endif
93 
94  for (counter = 0; counter < max_iterations && !converged; counter++) {
95  float test = 0;
96  float alpha, beta;
97  float numerator = 0, denominator = 0, r;
98  /* fprintf(stderr,"."); */
99  converged = TRUE;
100  /* find steepest descent direction */
101  for (i = 0; i < n; i++) {
102  old_place[i] = place[i];
103  g[i] = 2 * b[i];
104  for (j = 0; j < n; j++) {
105  g[i] -= 2 * e->A[i][j] * place[j];
106  }
107  }
108  for (i = 0; i < n; i++) {
109  numerator += g[i] * g[i];
110  r = 0;
111  for (j = 0; j < n; j++) {
112  r += 2 * e->A[i][j] * g[j];
113  }
114  denominator -= r * g[i];
115  }
116  if (denominator != 0)
117  alpha = numerator / denominator;
118  else
119  alpha = 1.0;
120  for (i = 0; i < n; i++) {
121  place[i] -= alpha * g[i];
122  }
123  if (e->m > 0) {
124  /* project to constraint boundary */
125  for (i = 0; i < n; i++) {
126  setVariableDesiredPos(e->vs[i], place[i]);
127  }
128  satisfyVPSC(e->vpsc);
129  for (i = 0; i < n; i++) {
130  place[i] = getVariablePos(e->vs[i]);
131  }
132  }
133  /* set place to the intersection of old_place-g and boundary and
134  * compute d, the vector from intersection pnt to projection pnt
135  */
136  for (i = 0; i < n; i++) {
137  d[i] = place[i] - old_place[i];
138  }
139  /* now compute beta */
140  numerator = 0, denominator = 0;
141  for (i = 0; i < n; i++) {
142  numerator += g[i] * d[i];
143  r = 0;
144  for (j = 0; j < n; j++) {
145  r += 2 * e->A[i][j] * d[j];
146  }
147  denominator += r * d[i];
148  }
149  if (denominator != 0.0)
150  beta = numerator / denominator;
151  else
152  beta = 1.0;
153 
154  for (i = 0; i < n; i++) {
155  /* beta > 1.0 takes us back outside the feasible region
156  * beta < 0 clearly not useful and may happen due to numerical imp.
157  */
158  if (beta > 0 && beta < 1.0) {
159  place[i] = old_place[i] + beta * d[i];
160  }
161  test += fabs(place[i] - old_place[i]);
162  }
163 #ifdef CONMAJ_LOGGING
164  float stress = 0;
165  for (i = 0; i < n; i++) {
166  stress += 2 * b[i] * place[i];
167  for (j = 0; j < n; j++) {
168  stress -= e->A[i][j] * place[j] * place[i];
169  }
170  }
171  fprintf(logfile, "%d: stress=%f, test=%f, %s\n", call_no, stress,
172  test, (stress >= prev_stress) ? "No Improvement" : "");
173  prev_stress = stress;
174 #endif
175  if (test > quad_prog_tol) {
176  converged = FALSE;
177  }
178  }
179 #ifdef CONMAJ_LOGGING
180  call_no++;
181  fclose(logfile);
182 #endif
183  return counter;
184 }
185 
186 /*
187  * Set up environment and global constraints (dir-edge constraints, containment constraints
188  * etc).
189  *
190  * diredges: 0=no dir edge constraints
191  * 1=one separation constraint for each edge (in acyclic subgraph)
192  * 2=DiG-CoLa level constraints
193  */
194 CMajEnvVPSC *initCMajVPSC(int n, float *packedMat, vtx_data * graph,
195  ipsep_options * opt, int diredges)
196 {
197  int i, j;
198  /* nv is the number of real nodes */
199  int nConCs;
200  /* fprintf(stderr,"Entered initCMajVPSC\n"); */
201  CMajEnvVPSC *e = GNEW(CMajEnvVPSC);
202  e->A = NULL;
203  e->packedMat = packedMat;
204  /* if we have clusters then we'll need two constraints for each var in
205  * a cluster */
206  e->nldv = 2 * opt->clusters->nclusters;
207  e->nv = n - e->nldv;
208  e->ndv = 0;
209 
210  e->gcs = NULL;
211  e->vs = N_GNEW(n, Variable *);
212  for (i = 0; i < n; i++) {
213  e->vs[i] = newVariable(i, 1.0, 1.0);
214  }
215  e->gm = 0;
216  if (diredges == 1) {
217  if (Verbose)
218  fprintf(stderr, " generate edge constraints...\n");
219  for (i = 0; i < e->nv; i++) {
220  for (j = 1; j < graph[i].nedges; j++) {
221  /* fprintf(stderr,"edist=%f\n",graph[i].edists[j]); */
222  if (graph[i].edists[j] > 0.01) {
223  e->gm++;
224  }
225  }
226  }
227  e->gcs = newConstraints(e->gm);
228  e->gm = 0;
229  for (i = 0; i < e->nv; i++) {
230  for (j = 1; j < graph[i].nedges; j++) {
231  int u = i, v = graph[i].edges[j];
232  if (graph[i].edists[j] > 0) {
233  e->gcs[e->gm++] =
234  newConstraint(e->vs[u], e->vs[v], opt->edge_gap);
235  }
236  }
237  }
238  } else if (diredges == 2) {
239  int *ordering = NULL, *ls = NULL, cvar;
240  double halfgap;
241  DigColaLevel *levels;
242  Variable **vs = e->vs;
243  /* e->ndv is the number of dummy variables required, one for each boundary */
244  if (compute_hierarchy(graph, e->nv, 1e-2, 1e-1, NULL, &ordering, &ls,
245  &e->ndv)) return NULL;
246  levels = assign_digcola_levels(ordering, e->nv, ls, e->ndv);
247  if (Verbose)
248  fprintf(stderr, "Found %d DiG-CoLa boundaries\n", e->ndv);
249  e->gm =
250  get_num_digcola_constraints(levels, e->ndv + 1) + e->ndv - 1;
251  e->gcs = newConstraints(e->gm);
252  e->gm = 0;
253  e->vs = N_GNEW(n + e->ndv, Variable *);
254  for (i = 0; i < n; i++) {
255  e->vs[i] = vs[i];
256  }
257  free(vs);
258  /* create dummy vars */
259  for (i = 0; i < e->ndv; i++) {
260  /* dummy vars should have 0 weight */
261  cvar = n + i;
262  e->vs[cvar] = newVariable(cvar, 1.0, 0.000001);
263  }
264  halfgap = opt->edge_gap;
265  for (i = 0; i < e->ndv; i++) {
266  cvar = n + i;
267  /* outgoing constraints for each var in level below boundary */
268  for (j = 0; j < levels[i].num_nodes; j++) {
269  e->gcs[e->gm++] =
270  newConstraint(e->vs[levels[i].nodes[j]], e->vs[cvar],
271  halfgap);
272  }
273  /* incoming constraints for each var in level above boundary */
274  for (j = 0; j < levels[i + 1].num_nodes; j++) {
275  e->gcs[e->gm++] =
276  newConstraint(e->vs[cvar],
277  e->vs[levels[i + 1].nodes[j]], halfgap);
278  }
279  }
280  /* constraints between adjacent boundary dummy vars */
281  for (i = 0; i < e->ndv - 1; i++) {
282  e->gcs[e->gm++] =
283  newConstraint(e->vs[n + i], e->vs[n + i + 1], 0);
284  }
285  }
286  /* fprintf(stderr," generate edge constraints... done: n=%d,m=%d\n",e->n,e->gm); */
287  if (opt->clusters->nclusters > 0) {
288  /* fprintf(stderr," generate cluster containment constraints...\n"); */
289  Constraint **ecs = e->gcs;
290  nConCs = 2 * opt->clusters->nvars;
291  e->gcs = newConstraints(e->gm + nConCs);
292  for (i = 0; i < e->gm; i++) {
293  e->gcs[i] = ecs[i];
294  }
295  if (ecs != NULL)
296  deleteConstraints(0, ecs);
297  for (i = 0; i < opt->clusters->nclusters; i++) {
298  for (j = 0; j < opt->clusters->clustersizes[i]; j++) {
299  Variable *v = e->vs[opt->clusters->clusters[i][j]];
300  Variable *cl = e->vs[e->nv + 2 * i];
301  Variable *cr = e->vs[e->nv + 2 * i + 1];
302  e->gcs[e->gm++] = newConstraint(cl, v, 0);
303  e->gcs[e->gm++] = newConstraint(v, cr, 0);
304  }
305  }
306  /* fprintf(stderr," containment constraints... done: \n"); */
307  }
308 
309  e->m = 0;
310  e->cs = NULL;
311  if (e->gm > 0) {
312  e->vpsc = newIncVPSC(n + e->ndv, e->vs, e->gm, e->gcs);
313  e->m = e->gm;
314  e->cs = e->gcs;
315  }
316  if (packedMat != NULL) {
317  e->A = unpackMatrix(packedMat, n);
318  }
319 #ifdef MOSEK
320  e->mosekEnv = NULL;
321  if (opt->mosek) {
322  e->mosekEnv =
323  mosek_init_sep(e->packedMat, n, e->ndv, e->gcs, e->gm);
324  }
325 #endif
326 
327  e->fArray1 = N_GNEW(n, float);
328  e->fArray2 = N_GNEW(n, float);
329  e->fArray3 = N_GNEW(n, float);
330  if (Verbose)
331  fprintf(stderr,
332  " initCMajVPSC done: %d global constraints generated.\n",
333  e->m);
334  return e;
335 }
336 
337 void deleteCMajEnvVPSC(CMajEnvVPSC * e)
338 {
339  int i;
340  if (e->A != NULL) {
341  free(e->A[0]);
342  free(e->A);
343  }
344  if (e->m > 0) {
345  deleteVPSC(e->vpsc);
346  if (e->cs != e->gcs && e->gcs != NULL)
347  deleteConstraints(0, e->gcs);
348  deleteConstraints(e->m, e->cs);
349  for (i = 0; i < e->nv + e->nldv + e->ndv; i++) {
350  deleteVariable(e->vs[i]);
351  }
352  free(e->vs);
353  }
354  free(e->fArray1);
355  free(e->fArray2);
356  free(e->fArray3);
357 #ifdef MOSEK
358  if (e->mosekEnv) {
359  mosek_delete(e->mosekEnv);
360  }
361 #endif /* MOSEK */
362  free(e);
363 }
364 
365 /* generate non-overlap constraints inside each cluster, including dummy
366  * nodes at bounds of cluster
367  * generate constraints again for top level nodes and clusters treating
368  * clusters as rectangles of dim (l,r,b,t)
369  * for each cluster map in-constraints to l out-constraints to r
370  *
371  * For now, we'll keep the global containment constraints already
372  * generated for each cluster, and simply generate non-overlap constraints
373  * for all nodes and then an additional set of non-overlap constraints for
374  * clusters that we'll map back to the dummy vars as above.
375  */
376 void generateNonoverlapConstraints(CMajEnvVPSC * e,
377  float nsizeScale,
378  float **coords,
379  int k,
380  boolean transitiveClosure,
381  ipsep_options * opt)
382 {
383  Constraint **csol, **csolptr;
384  int i, j, mol = 0;
385  int n = e->nv + e->nldv;
386 #ifdef WIN32
387  boxf* bb = N_GNEW (n, boxf);
388 #else
389  boxf bb[n];
390 #endif
391  boolean genclusters = opt->clusters->nclusters > 0;
392  if (genclusters) {
393  /* n is the number of real variables, not dummy cluster vars */
394  n -= 2 * opt->clusters->nclusters;
395  }
396  if (k == 0) {
397  /* grow a bit in the x dimension, so that if overlap is resolved
398  * horizontally then it won't be considered overlapping vertically
399  */
400  nsizeScale *= 1.0001;
401  }
402  for (i = 0; i < n; i++) {
403  bb[i].LL.x =
404  coords[0][i] - nsizeScale * opt->nsize[i].x / 2.0 -
405  opt->gap.x / 2.0;
406  bb[i].UR.x =
407  coords[0][i] + nsizeScale * opt->nsize[i].x / 2.0 +
408  opt->gap.x / 2.0;
409  bb[i].LL.y =
410  coords[1][i] - nsizeScale * opt->nsize[i].y / 2.0 -
411  opt->gap.y / 2.0;
412  bb[i].UR.y =
413  coords[1][i] + nsizeScale * opt->nsize[i].y / 2.0 +
414  opt->gap.y / 2.0;
415  }
416  if (genclusters) {
417 #ifdef WIN32
418  Constraint ***cscl = N_GNEW(opt->clusters->nclusters + 1, Constraint**);
419  int* cm = N_GNEW(opt->clusters->nclusters + 1, int);
420 #else
421  Constraint **cscl[opt->clusters->nclusters + 1];
422  int cm[opt->clusters->nclusters + 1];
423 #endif
424  for (i = 0; i < opt->clusters->nclusters; i++) {
425  int cn = opt->clusters->clustersizes[i];
426 #ifdef WIN32
427  Variable** cvs = N_GNEW(cn + 2, Variable*);
428  boxf* cbb = N_GNEW(cn + 2, boxf);
429 #else
430  Variable *cvs[cn + 2];
431  boxf cbb[cn + 2];
432 #endif
433  /* compute cluster bounding bb */
434  boxf container;
435  container.LL.x = container.LL.y = DBL_MAX;
436  container.UR.x = container.UR.y = -DBL_MAX;
437  for (j = 0; j < cn; j++) {
438  int iv = opt->clusters->clusters[i][j];
439  cvs[j] = e->vs[iv];
440  B2BF(bb[iv], cbb[j]);
441  EXPANDBB(container, bb[iv]);
442  }
443  B2BF(container, opt->clusters->bb[i]);
444  cvs[cn] = e->vs[n + 2 * i];
445  cvs[cn + 1] = e->vs[n + 2 * i + 1];
446  B2BF(container, cbb[cn]);
447  B2BF(container, cbb[cn + 1]);
448  if (k == 0) {
449  cbb[cn].UR.x = container.LL.x + 0.0001;
450  cbb[cn + 1].LL.x = container.UR.x - 0.0001;
451  cm[i] =
452  genXConstraints(cn + 2, cbb, cvs, &cscl[i],
453  transitiveClosure);
454  } else {
455  cbb[cn].UR.y = container.LL.y + 0.0001;
456  cbb[cn + 1].LL.y = container.UR.y - 0.0001;
457  cm[i] = genYConstraints(cn + 2, cbb, cvs, &cscl[i]);
458  }
459  mol += cm[i];
460 #ifdef WIN32
461  free (cvs);
462  free (cbb);
463 #endif
464  }
465  /* generate top level constraints */
466  {
467  int cn = opt->clusters->ntoplevel + opt->clusters->nclusters;
468 #ifdef WIN32
469  Variable** cvs = N_GNEW(cn,Variable*);
470  boxf* cbb = N_GNEW(cn, boxf);
471 #else
472  Variable *cvs[cn];
473  boxf cbb[cn];
474 #endif
475  for (i = 0; i < opt->clusters->ntoplevel; i++) {
476  int iv = opt->clusters->toplevel[i];
477  cvs[i] = e->vs[iv];
478  B2BF(bb[iv], cbb[i]);
479  }
480  /* make dummy variables for clusters */
481  for (i = opt->clusters->ntoplevel; i < cn; i++) {
482  cvs[i] = newVariable(123 + i, 1, 1);
483  j = i - opt->clusters->ntoplevel;
484  B2BF(opt->clusters->bb[j], cbb[i]);
485  }
486  i = opt->clusters->nclusters;
487  if (k == 0) {
488  cm[i] =
489  genXConstraints(cn, cbb, cvs, &cscl[i],
490  transitiveClosure);
491  } else {
492  cm[i] = genYConstraints(cn, cbb, cvs, &cscl[i]);
493  }
494  /* remap constraints from tmp dummy vars to cluster l and r vars */
495  for (i = opt->clusters->ntoplevel; i < cn; i++) {
496  double dgap;
497  j = i - opt->clusters->ntoplevel;
498  /* dgap is the change in required constraint gap.
499  * since we are going from a source rectangle the size
500  * of the cluster bounding box to a zero width (in x dim,
501  * zero height in y dim) rectangle, the change will be
502  * half the bb width.
503  */
504  if (k == 0) {
505  dgap = -(cbb[i].UR.x - cbb[i].LL.x) / 2.0;
506  } else {
507  dgap = -(cbb[i].UR.y - cbb[i].LL.y) / 2.0;
508  }
509  remapInConstraints(cvs[i], e->vs[n + 2 * j], dgap);
510  remapOutConstraints(cvs[i], e->vs[n + 2 * j + 1], dgap);
511  /* there may be problems with cycles between
512  * cluster non-overlap and diredge constraints,
513  * to resolve:
514  *
515  * for each constraint c:v->cvs[i]:
516  * if exists diredge constraint u->v where u in c:
517  * remap v->cl to cr->v (gap = height(v)/2)
518  *
519  * in = getInConstraints(cvs[i])
520  * for(c : in) {
521  * assert(c.right==cvs[i]);
522  * vin = getOutConstraints(v=c.left)
523  * for(d : vin) {
524  * if(d.left.cluster==i):
525  * tmp = d.left
526  * d.left = d.right
527  * d.right = tmp
528  * d.gap = height(d.right)/2
529  * }
530  * }
531  *
532  */
533  deleteVariable(cvs[i]);
534  }
535  mol += cm[opt->clusters->nclusters];
536 #ifdef WIN32
537  free (cvs);
538  free (cbb);
539 #endif
540  }
541  csolptr = csol = newConstraints(mol);
542  for (i = 0; i < opt->clusters->nclusters + 1; i++) {
543  /* copy constraints into csol */
544  for (j = 0; j < cm[i]; j++) {
545  *csolptr++ = cscl[i][j];
546  }
547  deleteConstraints(0, cscl[i]);
548  }
549 #ifdef WIN32
550  free (cscl);
551  free (cm);
552 #endif
553  } else {
554  if (k == 0) {
555  mol = genXConstraints(n, bb, e->vs, &csol, transitiveClosure);
556  } else {
557  mol = genYConstraints(n, bb, e->vs, &csol);
558  }
559  }
560  /* remove constraints from previous iteration */
561  if (e->m > 0) {
562  /* can't reuse instance of VPSC when constraints change! */
563  deleteVPSC(e->vpsc);
564  for (i = e->gm == 0 ? 0 : e->gm; i < e->m; i++) {
565  /* delete previous overlap constraints */
566  deleteConstraint(e->cs[i]);
567  }
568  /* just delete the array, not the elements */
569  if (e->cs != e->gcs)
570  deleteConstraints(0, e->cs);
571  }
572  /* if we have no global constraints then the overlap constraints
573  * are all we have to worry about.
574  * Otherwise, we have to copy the global and overlap constraints
575  * into the one array
576  */
577  if (e->gm == 0) {
578  e->m = mol;
579  e->cs = csol;
580  } else {
581  e->m = mol + e->gm;
582  e->cs = newConstraints(e->m);
583  for (i = 0; i < e->m; i++) {
584  if (i < e->gm) {
585  e->cs[i] = e->gcs[i];
586  } else {
587  e->cs[i] = csol[i - e->gm];
588  }
589  }
590  /* just delete the array, not the elements */
591  deleteConstraints(0, csol);
592  }
593  if (Verbose)
594  fprintf(stderr, " generated %d constraints\n", e->m);
595  e->vpsc = newIncVPSC(e->nv + e->nldv + e->ndv, e->vs, e->m, e->cs);
596 #ifdef MOSEK
597  if (opt->mosek) {
598  if (e->mosekEnv != NULL) {
599  mosek_delete(e->mosekEnv);
600  }
601  e->mosekEnv =
602  mosek_init_sep(e->packedMat, e->nv + e->nldv, e->ndv, e->cs,
603  e->m);
604  }
605 #endif
606 #ifdef WIN32
607  free (bb);
608 #endif
609 }
610 
611 /*
612  * Statically remove overlaps, that is remove all overlaps by moving each node as
613  * little as possible.
614  */
615 void removeoverlaps(int n, float **coords, ipsep_options * opt)
616 {
617  int i;
618  CMajEnvVPSC *e = initCMajVPSC(n, NULL, NULL, opt, 0);
619  generateNonoverlapConstraints(e, 1.0, coords, 0, TRUE, opt);
620  solveVPSC(e->vpsc);
621  for (i = 0; i < n; i++) {
622  coords[0][i] = getVariablePos(e->vs[i]);
623  }
624  generateNonoverlapConstraints(e, 1.0, coords, 1, FALSE, opt);
625  solveVPSC(e->vpsc);
626  for (i = 0; i < n; i++) {
627  coords[1][i] = getVariablePos(e->vs[i]);
628  }
629  deleteCMajEnvVPSC(e);
630 }
631 
632 /*
633  unpack the "ordering" array into an array of DigColaLevel
634 */
635 DigColaLevel *assign_digcola_levels(int *ordering, int n, int *level_inds,
636  int num_divisions)
637 {
638  int i, j;
639  DigColaLevel *l = N_GNEW(num_divisions + 1, DigColaLevel);
640  /* first level */
641  l[0].num_nodes = level_inds[0];
642  l[0].nodes = N_GNEW(l[0].num_nodes, int);
643  for (i = 0; i < l[0].num_nodes; i++) {
644  l[0].nodes[i] = ordering[i];
645  }
646  /* second through second last level */
647  for (i = 1; i < num_divisions; i++) {
648  l[i].num_nodes = level_inds[i] - level_inds[i - 1];
649  l[i].nodes = N_GNEW(l[i].num_nodes, int);
650  for (j = 0; j < l[i].num_nodes; j++) {
651  l[i].nodes[j] = ordering[level_inds[i - 1] + j];
652  }
653  }
654  /* last level */
655  if (num_divisions > 0) {
656  l[num_divisions].num_nodes = n - level_inds[num_divisions - 1];
657  l[num_divisions].nodes = N_GNEW(l[num_divisions].num_nodes, int);
658  for (i = 0; i < l[num_divisions].num_nodes; i++) {
659  l[num_divisions].nodes[i] =
660  ordering[level_inds[num_divisions - 1] + i];
661  }
662  }
663  return l;
664 }
665 void delete_digcola_levels(DigColaLevel * l, int num_levels)
666 {
667  int i;
668  for (i = 0; i < num_levels; i++) {
669  free(l[i].nodes);
670  }
671  free(l);
672 }
673 void print_digcola_levels(FILE * logfile, DigColaLevel * levels,
674  int num_levels)
675 {
676  int i, j;
677  fprintf(logfile, "levels:\n");
678  for (i = 0; i < num_levels; i++) {
679  fprintf(logfile, " l[%d]:", i);
680  for (j = 0; j < levels[i].num_nodes; j++) {
681  fprintf(logfile, "%d ", levels[i].nodes[j]);
682  }
683  fprintf(logfile, "\n");
684  }
685 }
686 
687 /*********************
688 get number of separation constraints based on the number of nodes in each level
689 ie, num_sep_constraints = sum_i^{num_levels-1} (|L[i]|+|L[i+1]|)
690 **********************/
691 int get_num_digcola_constraints(DigColaLevel * levels, int num_levels)
692 {
693  int i, nc = 0;
694  for (i = 1; i < num_levels; i++) {
695  nc += levels[i].num_nodes + levels[i - 1].num_nodes;
696  }
697  nc += levels[0].num_nodes + levels[num_levels - 1].num_nodes;
698  return nc;
699 }
700 
701 #endif /* IPSEPCOLA */