1 /* $Id$ $Revision$ */
2 /* vim:set shiftwidth=4 ts=8: */
3
4 /**
5 *
6 * Authors:
7 * Tim Dwyer <tgdwyer@gmail.com>
8 *
9 * Copyright (C) 2005 Authors
10 *
11 * This version is released under the CPL (Common Public License) with
12 * the Graphviz distribution.
13 * A version is also available under the LGPL as part of the Adaptagrams
14 * project: http://sourceforge.net/projects/adaptagrams.
15 * If you make improvements or bug fixes to this code it would be much
16 * appreciated if you could also contribute those changes back to the
17 * Adaptagrams repository.
18 */
19
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
constrained_majorization_vpsc(CMajEnvVPSC * e,float * b,float * place,int max_iterations)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 */
initCMajVPSC(int n,float * packedMat,vtx_data * graph,ipsep_options * opt,int diredges)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
deleteCMajEnvVPSC(CMajEnvVPSC * e)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 */
generateNonoverlapConstraints(CMajEnvVPSC * e,float nsizeScale,float ** coords,int k,boolean transitiveClosure,ipsep_options * opt)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 */
removeoverlaps(int n,float ** coords,ipsep_options * opt)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 */
assign_digcola_levels(int * ordering,int n,int * level_inds,int num_divisions)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 }
delete_digcola_levels(DigColaLevel * l,int num_levels)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 }
print_digcola_levels(FILE * logfile,DigColaLevel * levels,int num_levels)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 **********************/
get_num_digcola_constraints(DigColaLevel * levels,int num_levels)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 */
702