1 /****************************************************************************/
2 /* */
3 /* This file is part of CONCORDE */
4 /* */
5 /* (c) Copyright 1995--1999 by David Applegate, Robert Bixby, */
6 /* Vasek Chvatal, and William Cook */
7 /* */
8 /* Permission is granted for academic research use. For other uses, */
9 /* contact the authors for licensing options. */
10 /* */
11 /* Use at your own risk. We make no guarantees about the */
12 /* correctness or usefulness of this code. */
13 /* */
14 /****************************************************************************/
15
16 /****************************************************************************/
17 /* */
18 /* SHRINK ROUTINES */
19 /* */
20 /* Written by: Applegate, Bixby, Chvatal, and Cook (TSP Code) */
21 /* Date: July 19, 1996 */
22 /* October 21, 1996 (bico) */
23 /* */
24 /* EXPORTED FUNCTIONS: */
25 /* */
26 /* void CCcut_SRK_init_graph (CC_SRKgraph *G) */
27 /* INITIALIZES the fields of the CC_SRKgraph. */
28 /* */
29 /* int CCcut_SRK_buildgraph (CC_SRKgraph *G, int ncount, int ecount, */
30 /* int *elist, double *dlen) */
31 /* MISSING */
32 /* */
33 /* void CCcut_SRK_free_graph (CC_SRKgraph *G) */
34 /* FREES the CC_SRKgraph. */
35 /* */
36 /* void CCcut_SRK_init_expinfo (CC_SRKexpinfo *expand) */
37 /* MISSING */
38 /* */
39 /* void CCcut_SRK_free_expinfo (CC_SRKexpinfo *expand) */
40 /* MISSING */
41 /* */
42 /* void CCcut_SRK_init_callback (CC_SRKcallback *cb) */
43 /* MISSING */
44 /* */
45 /* int CCcut_SRK_grab_edges (CC_SRKgraph *G, int *oncount, int *oecount, */
46 /* int **olist, double **olen, CC_SRKexpinfo *expand) */
47 /* int **omembers) */
48 /* RETURNS the edges and member lists for the shrunk graph. */
49 /* -G is a pointer to a shrunk graph */
50 /* -oncount returns the number of nodes in the shrunk graph */
51 /* -oecount returns the number of edges in the shrunk graph */
52 /* -olist returns the edges in node node format */
53 /* -olen returns the edge lengths */
54 /* -expand will be filled in with a memindex and members array; */
55 /* memindex returns pointers into the members array, the */
56 /* members of node i will be stored in from memindex[i] to */
57 /* memindex[i+1] - 1, so memindex is ncount + 1 long; members */
58 /* returns the nodes lists corresponding to each node in the */
59 /* shrunk graph. (expand can be NULL) */
60 /* */
61 /* int CCcut_SRK_grab_nodes (CC_SRKgraph *G, CC_SRKexpinfo *expand) */
62 /* RETURNS the member lists for the shrunk graph (see above) */
63 /* */
64 /* int CCcut_SRK_trivial (int ncount, CC_SRKexpinfo *expand) */
65 /* MISSING */
66 /* */
67 /* int CCcut_SRK_expand (CC_SRKexpinfo *expand, int *arr, int size, */
68 /* int **pnewarr, int *pnewsize) */
69 /* MISSING */
70 /* */
71 /* void CCcut_SRK_identify_paths (CC_SRKgraph *G, int *newcount, */
72 /* int onecnt_okay) */
73 /* MISSING */
74 /* */
75 /* void CCcut_SRK_identify_paths_to_edges (CC_SRKgraph *G, int *newcount, */
76 /* int onecnt_okay) */
77 /* MISSING */
78 /* */
79 /* void CCcut_SRK_identify_ones (CC_SRKgraph *G, int *count, */
80 /* double epsilon) */
81 /* MISSING */
82 /* */
83 /* void CCcut_SRK_identify_one_triangles (CC_SRKgraph *G, int *count, */
84 /* CC_SRKnode *qstart, double epsilon, double cutoff, int unmarked) */
85 /* SHRINKS any one edge that sits in a tight triangle. */
86 /* -G is the current shrunk graph */
87 /* -count returns the number of shrunk triangles (can be NULL) */
88 /* -qstart can point to the start of a queue (linked by qnext) */
89 /* -epsilon is used to determine one edges (at least 1.0 - epsilon) */
90 /* -cutoff is used to determine tight triangles (weight cutoff) */
91 /* -unmarked should be nonzero if only unmarked nodes (determined */
92 /* by G->marker) should be involved in shrinks */
93 /* */
94 /* void CCcut_SRK_identify_tight_triangles (CC_SRKgraph *G, int *count, */
95 /* double cutoff, int unmarked) */
96 /* SHRINKS any tight triangle into a single node. */
97 /* -G is the current shrunk graph */
98 /* -count returns the number of shrunk triangles (can be NULL) */
99 /* -cutoff is used to decide if a triangle is tight (shrunk any T */
100 /* with x(T) >= cutoff) */
101 /* -unmarked should be nonzero if only unmarked nodes (determined */
102 /* by G->marker) should be involved in shrinks */
103 /* NOTES: All new shrunk nodes will be marked. */
104 /* */
105 /* void CCcut_SRK_identify_tight_squares (CC_SRKgraph *G, int *count, */
106 /* double cutoff, int unmarked) */
107 /* SHRINKS tight squares into a single nodes. */
108 /* -see above. */
109 /* */
110 /* void CCcut_SRK_identify_triangle_square (CC_SRKgraph *G, int *count, */
111 /* double epsilon, int unmarked) */
112 /* SHRINKS tight triangles within tight squares. */
113 /* -epsilon is used to determine the tight triangle and square. */
114 /* */
115 /* void CCcut_SRK_identify_one_square (CC_SRKgraph *G, int *count, */
116 /* double epsilon, double cutoff, int unmarked) */
117 /* SHRINKS two opposite 1-edge in a tight 4-square */
118 /* */
119 /* void CCcut_SRK_identify_nodes (CC_SRKgraph *G, CC_SRKnode *n, */
120 /* CC_SRKnode *m) */
121 /* MISSING */
122 /* */
123 /* int CCcut_SRK_identify_set (CC_SRKgraph *G, int scount, int *slist) */
124 /* SHRINKS the nodes int slist to a single node. NOTE this works */
125 /* by matching the indices in slist to the order in G's linked list of */
126 /* nodes. (So it will work immediately after a call to grab_edges */
127 /* if the set is based on the ends of the edges.) */
128 /* */
129 /* void CCcut_SRK_increment_marker (CC_SRKgraph *G) */
130 /* INCREASES the field used to mark nodes by 1. */
131 /* */
132 /* int CCcut_SRK_subtour_shrink (CC_SRKgraph *G, double *minval, */
133 /* double epsilon, CC_SRKcallback *cb, int **cut, int *cutcount) */
134 /* MISSING */
135 /* */
136 /* int CCcut_SRK_identify_pr_edges (CC_SRKgraph *G, double *minval, */
137 /* int *count, CC_SRKnode *qstart, double epsilon, */
138 /* CC_SRKcallback *cb, int **cut, int *cutcount) */
139 /* MISSING */
140 /* */
141 /* int CCcut_SRK_defluff (CC_SRKGRAPH *G) */
142 /* MISSING */
143 /* */
144 /* void CCcut_SRK_set_mark (CC_SRKgraph *G, int marker) */
145 /* SETS the mark field of all active nodes to marker. */
146 /* */
147 /* int CCcut_SRK_original_ncount (CC_SRKexpinfo *expand) */
148 /* RETURNS the number of nodes in the original (unshrunk) graph. */
149 /* */
150 /* NOTES: Cyles of 1's will be shrunk into single nodes. */
151 /* */
152 /****************************************************************************/
153
154 #include "machdefs.h"
155 #include "util.h"
156 #include "cut.h"
157
158 #define ADD_TO_PR_QUEUE(n) { \
159 if (!(n)->onqueue) { \
160 (n)->qnext = (CC_SRKnode *) NULL; \
161 if (qtail) \
162 qtail->qnext = (n); \
163 else \
164 qhead = (n); \
165 qtail = (n); \
166 (n)->onqueue = 1; \
167 } \
168 }
169
170 #undef PR_USE3 /* PR_USE3 and PR_USE4 cannot be defined in current code */
171 #undef PR_USE4
172 #undef DEBUG_SHRINK
173 #define SRK_ZERO_EPSILON (1e-10)
174
175
176 static void
177 #ifdef DEBUG_SHRINK
178 printgraph (CC_SRKgraph *G),
179 #endif
180 count_ones (CC_SRKgraph *G),
181 merge_adj (CC_SRKgraph *G, CC_SRKnode *n, CC_SRKnode *m),
182 initial_queue (CC_SRKgraph *G, CC_SRKnode **outqhead,
183 CC_SRKnode **outqtail, int unmarked);
184
185 static int
186 test_node (CC_SRKnode *n, double *minval, CC_SRKcallback *cb, int **cut,
187 int *cutcount),
188 expand_the_node (CC_SRKnode *n, int *cutcount, int **cut),
189 expand_and_pass (CC_SRKnode *n, int (*doit_fn) (double, int, int *,
190 void *), void *pass_param);
191
192
CCcut_SRK_subtour_shrink(CC_SRKgraph * G,double * minval,double epsilon,CC_SRKcallback * cb,int ** cut,int * cutcount)193 int CCcut_SRK_subtour_shrink (CC_SRKgraph *G, double *minval, double epsilon,
194 CC_SRKcallback *cb, int **cut, int *cutcount)
195 {
196 int rval = 0;
197 int k;
198 int cnt = 0;
199 CC_SRKnode *n;
200
201 for (n = G->head; n; n = n->next) {
202 cnt++;
203 }
204
205 /* In the tsp, paths of 1's can be shrunk via a call to the function */
206 /* CCcut_SRK_identify_paths. */
207
208 /* Could call a version of CCcut_SRK_identify_ones */
209
210 /* printf ("Identify PR edges ....\n"); fflush (stdout); */
211 rval = CCcut_SRK_identify_pr_edges (G, minval, &k, (CC_SRKnode *) NULL,
212 epsilon, cb, cut, cutcount);
213 if (rval) {
214 fprintf (stderr, "CCcut_SRK_identify_pr_edges failed\n"); goto CLEANUP;
215 }
216
217 cnt -= k;
218 /* printf ("Graph shrunk to %d nodes\n", cnt); fflush (stdout); */
219
220 CLEANUP:
221
222 return rval;
223 }
224
count_ones(CC_SRKgraph * G)225 static void count_ones (CC_SRKgraph *G)
226 {
227 int k;
228 CC_SRKnode *n;
229 CC_SRKedge *e;
230
231 for (n = G->head; n; n = n->next) {
232 for (k = 0, e = n->adj; e; e = e->next) {
233 if (e->weight == 1.0)
234 k++;
235 }
236 n->onecnt = k;
237 }
238 }
239
CCcut_SRK_identify_paths(CC_SRKgraph * G,int * newcount,int onecnt_okay)240 void CCcut_SRK_identify_paths (CC_SRKgraph *G, int *newcount, int onecnt_okay)
241 {
242 CC_SRKnode *n, *m, *last;
243 CC_SRKedge *e, *f;
244 int dropcnt = 0;
245 double dropweight = 0.0;
246 int k;
247
248 /* printf ("Identify paths ...\n"); fflush (stdout); */
249
250 if (!onecnt_okay)
251 count_ones (G);
252 for (n = G->head; n; n = n->next) {
253 if (n->onecnt == 1) {
254 e = n->adj;
255 while (e->weight != 1.0)
256 e = e->next;
257 last = n;
258 m = e->end;
259 while (m->onecnt != 1) {
260 m->parent = n;
261 m->members = n->members;
262 n->members = m;
263 e = m->adj;
264 while (e->weight != 1.0 || e->end == last)
265 e = e->next;
266 last = m;
267 m = e->end;
268 }
269 m->parent = n;
270 m->members = n->members;
271 n->members = m;
272 m->onecnt = 3;
273 }
274 }
275
276 for (n = G->head; n->parent != n; n = n->next);
277 G->head = n;
278 G->head->prev = (CC_SRKnode *) NULL;
279 for (n = G->head->next; n; n = n->next) {
280 if (n->parent != n) {
281 n->prev->next = n->next;
282 if (n->next)
283 n->next->prev = n->prev;
284 }
285 }
286 for (k = 0, n = G->head; n; n = n->next) {
287 k++;
288 if (n->members) {
289 for (e = n->members->adj; e; e = e->next) {
290 e->other->end = n;
291 }
292 for (m = n->members->members; m; m = m->members) {
293 for (e = m->adj; e; e = e->next) {
294 if (e->weight == 1.0) {
295 e->other->end = n;
296 } else {
297 /* drop fluff edge */
298 dropcnt++;
299 dropweight += e->weight;
300 f = e->other;
301 if (f->prev) {
302 f->prev->next = f->next;
303 } else {
304 e->end->adj = f->next;
305 }
306 if (f->next) {
307 f->next->prev = f->prev;
308 }
309 }
310 }
311 }
312 n->weight = n->weight + n->members->weight;
313 merge_adj (G, n, n->members);
314 }
315 }
316
317 if (dropcnt > 0) {
318 printf ("dropped %d edges of total weight %f\n", dropcnt, dropweight);
319 fflush (stdout);
320 }
321
322 *newcount = k;
323 }
324
CCcut_SRK_defluff(CC_SRKgraph * G)325 int CCcut_SRK_defluff (CC_SRKgraph *G)
326 {
327 CC_SRKnode *n;
328 CC_SRKedge *e, *enext;
329 int k;
330 int ndel = 0;
331 double delweight = 0.0;
332
333 for (n = G->head; n; n = n->next) {
334 for (k = 0, e = n->adj; e; e = e->next) {
335 if (e->weight >= 1.0 - SRK_ZERO_EPSILON) {
336 e->weight = 1.0;
337 k++;
338 }
339 }
340 n->onecnt = k;
341 }
342
343 for (n = G->head; n; n = n->next) {
344 for (e = n->adj, n->adj = (CC_SRKedge *) NULL; e; e = enext) {
345 enext = e->next;
346 if (e->weight == 1.0 ||
347 (n->onecnt < 2 && e->end->onecnt < 2
348 && e->weight > SRK_ZERO_EPSILON)) {
349 if (n->adj) n->adj->prev = e;
350 e->next = n->adj;
351 n->adj = e;
352 e->prev = (CC_SRKedge *) NULL;
353 } else {
354 delweight += e->weight;
355 ndel++;
356 }
357 }
358 }
359
360 if (ndel & 1) {
361 fprintf (stderr, "Whoa, deleted %d (odd) endpoints in CCcut_SRK_defluff\n",
362 ndel);
363 return -1;
364 }
365 /*
366 printf ("CCcut_SRK_defluff deleted %d endpoints (weight %.6f)\n", ndel,
367 delweight);
368 fflush (stdout);
369 */
370 return 0;
371 }
372
CCcut_SRK_identify_paths_to_edges(CC_SRKgraph * G,int * newcount,int onecnt_okay)373 void CCcut_SRK_identify_paths_to_edges (CC_SRKgraph *G, int *newcount,
374 int onecnt_okay)
375 {
376 CC_SRKnode *n, *p, *m, *last;
377 CC_SRKedge *e;
378 int k;
379
380 /* NOTE: We should add in code to drop fluff edges */
381
382 if (!onecnt_okay)
383 count_ones (G);
384 for (n = G->head; n; n = n->next) {
385 if (n->onecnt == 1) {
386 e = n->adj;
387 while (e->weight != 1.0)
388 e = e->next;
389 m = e->end;
390 if (m->onecnt != 1) {
391 e = m->adj;
392 while (e->weight != 1.0 || e->end == n)
393 e = e->next;
394 last = m;
395 p = e->end;
396 while (p->onecnt != 1) {
397 p->parent = m;
398 p->members = m->members;
399 m->members = p;
400 e = p->adj;
401 while (e->weight != 1.0 || e->end == last)
402 e = e->next;
403 last = p;
404 p = e->end;
405 }
406 p->parent = m;
407 p->members = m->members;
408 m->members = p;
409 p->onecnt = 3;
410 m->mark = G->marker; /* indicate node was in a contraction */
411 }
412 }
413 }
414
415
416 for (n = G->head; n->parent != n; n = n->next);
417 G->head = n;
418 G->head->prev = (CC_SRKnode *) NULL;
419 for (n = G->head->next; n; n = n->next) {
420 if (n->parent != n) {
421 n->prev->next = n->next;
422 if (n->next)
423 n->next->prev = n->prev;
424 }
425 }
426 for (k = 0, n = G->head; n; n = n->next) {
427 k++;
428 if (n->members) {
429 for (m = n->members; m; m = m->members) {
430 for (e = m->adj; e; e = e->next)
431 e->other->end = n;
432 }
433 merge_adj (G, n, n->members);
434 }
435 }
436 *newcount = k;
437 }
438
CCcut_SRK_identify_ones(CC_SRKgraph * G,int * count,double epsilon)439 void CCcut_SRK_identify_ones (CC_SRKgraph *G, int *count, double epsilon)
440 {
441 CC_SRKnode *n;
442 CC_SRKedge *e;
443 double tol = 1.0 - epsilon;
444
445 /* printf ("Identify ones ....\n"); fflush (stdout); */
446
447 *count = 0;
448
449 for (n = G->head; n; n = n->next) {
450 do {
451 for (e = n->adj; e; e = e->next) {
452 if (e->weight >= tol) {
453 CCcut_SRK_identify_nodes (G, n, e->end);
454 (*count)++;
455 break;
456 }
457 }
458 } while (e);
459 }
460 }
461
CCcut_SRK_crowder_padberg(CC_SRKgraph * G,double epsilon,CC_SRKcallback * cb)462 int CCcut_SRK_crowder_padberg (CC_SRKgraph *G, double epsilon,
463 CC_SRKcallback *cb)
464 {
465 int rval = 0;
466 CC_SRKnode *n;
467 CC_SRKedge *e, *h;
468 double tol, minval = 0.0;
469 CC_SRKnode *qhead, *qtail;
470
471 for (n = G->head; n->next; n = n->next) {
472 n->qnext = n->next;
473 n->onqueue = 1;
474 }
475 qhead = G->head;
476 qtail = n;
477 qtail->onqueue = 1;
478 qtail->qnext = (CC_SRKnode *) NULL;
479
480 while (qhead) {
481 n = qhead;
482 qhead = qhead->qnext;
483 if (!qhead)
484 qtail = (CC_SRKnode *) NULL;
485 if (n->parent != n)
486 continue;
487 n->onqueue = 0;
488 tol = 1.0 - epsilon;
489
490 for (e = n->adj; e && e->weight < tol; e = e->next);
491 if (e) {
492 CCcut_SRK_identify_nodes (G, n, e->end);
493 ADD_TO_PR_QUEUE(n);
494 for (h = n->adj; h; h = h->next) {
495 ADD_TO_PR_QUEUE(h->end);
496 }
497 rval = test_node (n, &minval, cb, (int **) NULL, (int *) NULL);
498 if (rval) { fprintf (stderr, "test_node failed\n"); goto CLEANUP; }
499 }
500 }
501
502 CLEANUP:
503
504 return rval;
505 }
506
CCcut_SRK_identify_pr_edges(CC_SRKgraph * G,double * minval,int * count,CC_SRKnode * qstart,double epsilon,CC_SRKcallback * cb,int ** cut,int * cutcount)507 int CCcut_SRK_identify_pr_edges (CC_SRKgraph *G, double *minval, int *count,
508 CC_SRKnode *qstart, double epsilon, CC_SRKcallback *cb, int **cut,
509 int *cutcount)
510 {
511 int rval = 0;
512 CC_SRKnode *n;
513 CC_SRKedge *e, *f, *h;
514 double tol, tol1, tol2;
515 CC_SRKnode *qhead, *qtail;
516
517 /* Trivial PR Test: If w(uv) >= c(u)/2, then we can shrink edge uv. */
518
519 /* First PR Test: If we have a triangle uv, uw, vw with */
520 /* w(uv) + w(vw) >= c(v)/2 and w(uw) + w(vw) >= c(w)/2, then we can */
521 /* shrink edge vw. */
522
523 /* Second PR Test: Compute a lower bound on any cut that separates */
524 /* the ends of an edge by summing the minimum values of the edges to */
525 /* common neighbors of the ends. If the bound is >= "2", then we can */
526 /* shrink the edge. */
527
528 /* Third PR Test: Edge uv with common neighbors xy. If */
529 /* w(ux) + w(uy) + w(uv) >= "1" and w(vx) + w(vy) + w(uv) >= "1" and */
530 /* at least one of w(uy) + w(uv) and w(vx) + w(uv) is >= "1" and */
531 /* at least one of w(ux) + w(uv) and w(vy) + w(uv) is >= "1" then we */
532 /* can shrink the edge uv. */
533
534 *count = 0;
535
536 if (cut && !cutcount) {
537 fprintf (stderr, "cut defined, but not cutcount\n");
538 rval = 1; goto CLEANUP;
539 }
540
541 if (qstart) {
542 qhead = qstart;
543 for (n = qstart; n->next; n = n->next)
544 n->onqueue = 1;
545 qtail = n;
546 qtail->onqueue = 1;
547 } else {
548 for (n = G->head; n->next; n = n->next) {
549 n->qnext = n->next;
550 n->onqueue = 1;
551 }
552 qhead = G->head;
553 qtail = n;
554 qtail->onqueue = 1;
555 qtail->qnext = (CC_SRKnode *) NULL;
556 }
557
558 while (qhead) {
559 n = qhead;
560 qhead = qhead->qnext;
561 if (!qhead)
562 qtail = (CC_SRKnode *) NULL;
563 if (n->parent != n)
564 continue;
565 n->onqueue = 0;
566 tol = n->weight/2.0 - epsilon;
567
568 for (e = n->adj; e && e->weight < tol; e = e->next);
569 if (e) {
570 rval = test_node (n, minval, cb, cut, cutcount);
571 if (rval) { fprintf (stderr, "test_node failed\n"); goto CLEANUP; }
572 rval = test_node (e->end, minval, cb, cut, cutcount);
573 if (rval) { fprintf (stderr, "test_node failed\n"); goto CLEANUP; }
574 CCcut_SRK_identify_nodes (G, n, e->end);
575 (*count)++;
576 ADD_TO_PR_QUEUE(n);
577 for (h = n->adj; h; h = h->next) {
578 ADD_TO_PR_QUEUE(h->end);
579 }
580 } else {
581 for (e = n->adj; e; e = e->next)
582 e->end->prweight = e->weight;
583 for (e = n->adj; e; e = e->next) {
584 tol1 = (n->weight/2.0) - e->weight - epsilon;
585 tol2 = (e->end->weight/2.0) - e->weight - epsilon;
586 for (f = e->end->adj; f; f = f->next) {
587 if (f->weight >= tol2 && f->end->prweight >= tol1) {
588 rval = test_node (n, minval, cb, cut, cutcount);
589 if (rval) {
590 fprintf (stderr, "test_node failed\n");
591 goto CLEANUP;
592 }
593 rval = test_node (e->end, minval, cb, cut, cutcount);
594 if (rval) {
595 fprintf (stderr, "test_node failed\n");
596 goto CLEANUP;
597 }
598 CCcut_SRK_identify_nodes (G, n, e->end);
599 (*count)++;
600 ADD_TO_PR_QUEUE(n);
601 for (h = n->adj; h; h = h->next) {
602 ADD_TO_PR_QUEUE(h->end);
603 }
604 goto GET_OUT;
605 }
606 }
607 }
608
609 #ifdef PR_USE3
610 -Must modify to use node current min cut value.
611 for (e = n->adj; e; e = e->next) {
612 tol = e->weight;
613 for (f = e->end->adj; f; f = f->next) {
614 if (f->end->prweight >= f->weight)
615 tol += f->weight;
616 else if (f->end->prweight > -CC_MINCUT_BIGDOUBLE)
617 tol += f->end->prweight;
618 }
619 if (tol >= 1.0 + onetol) {
620 printf ("X"); fflush (stdout);
621 CCcut_SRK_identify_nodes (G, n, e->end);
622 (*count)++;
623 ADD_TO_PR_QUEUE(n);
624 for (h = n->adj; h; h = h->next) {
625 ADD_TO_PR_QUEUE(h->end);
626 }
627 goto GET_OUT;
628 }
629 }
630 #endif
631
632 #ifdef PR_USE4
633 -Must modify to use node weights.
634 for (e = n->adj; e; e = e->next) {
635 tol = onetol - e->weight;
636 for (f = e->end->adj; f; f = f->next) {
637 if (f->end->prweight > -CC_MINCUT_BIGDOUBLE) {
638 for (h = f->next; h; h = h->next) {
639 if (h->end->prweight > -CC_MINCUT_BIGDOUBLE) {
640 if (f->weight + h->weight >= tol
641 && f->end->prweight + h->end->prweight >= tol
642 && (f->weight >= tol || h->end->prweight >= tol)
643 && (h->weight >= tol || f->end->prweight >= tol)) {
644 CCcut_SRK_identify_nodes (G, n, e->end);
645 (*count)++;
646 ADD_TO_PR_QUEUE(n);
647 for (h = n->adj; h; h = h->next) {
648 ADD_TO_PR_QUEUE(h->end);
649 }
650 goto GET_OUT;
651 }
652 }
653 }
654 }
655 }
656 }
657 #endif
658
659 GET_OUT:
660 for (e = n->adj; e; e = e->next)
661 e->end->prweight = -CC_MINCUT_BIGDOUBLE;
662 }
663 }
664
665 CLEANUP:
666
667 return rval;
668 }
669
test_node(CC_SRKnode * n,double * minval,CC_SRKcallback * cb,int ** cut,int * cutcount)670 static int test_node (CC_SRKnode *n, double *minval, CC_SRKcallback *cb,
671 int **cut, int *cutcount)
672 {
673 int rval = 0;
674
675 if (n->weight < *minval) {
676 *minval = n->weight;
677 /* printf ("New minimum: %f\n", *minval); */
678 if (cut) {
679 CC_IFFREE (*cut, int);
680 rval = expand_the_node (n, cutcount, cut);
681 if (rval) {
682 fprintf (stderr, "expand_the_node failed\n"); goto CLEANUP;
683 }
684 }
685 }
686 if (cb) {
687 if (n->weight <= cb->cutoff) {
688 rval = expand_and_pass (n, cb->doit_fn, cb->pass_param);
689 if (rval) {
690 fprintf (stderr,"expand_and_pass failed\n"); goto CLEANUP;
691 }
692 }
693 }
694
695 CLEANUP:
696
697 return rval;
698 }
699
expand_and_pass(CC_SRKnode * n,int (* doit_fn)(double,int,int *,void *),void * pass_param)700 static int expand_and_pass (CC_SRKnode *n, int (*doit_fn) (double, int, int *,
701 void *), void *pass_param)
702 {
703 int rval = 0;
704 int cutcount;
705 int *cut = (int *) NULL;
706
707 if (!doit_fn) goto CLEANUP;
708
709 rval = expand_the_node (n, &cutcount, &cut);
710 if (rval) {
711 fprintf (stderr, "expand_the_node failed\n"); fflush (stdout);
712 }
713
714 rval = doit_fn (n->weight, cutcount, cut, pass_param);
715 if (rval) {
716 fprintf (stderr, "doit_fn failed\n"); goto CLEANUP;
717 }
718
719 CLEANUP:
720
721 CC_IFFREE (cut, int);
722 return rval;
723 }
724
expand_the_node(CC_SRKnode * n,int * cutcount,int ** cut)725 static int expand_the_node (CC_SRKnode *n, int *cutcount, int **cut)
726 {
727 int rval = 0;
728 int cnt;
729 int *tcut = (int *) NULL;
730 CC_SRKnode *v;
731
732 *cutcount = 0;
733 *cut = (int *) NULL;
734
735 cnt = 1;
736 for (v = n->members; v; v = v->members) {
737 cnt++;
738 }
739 tcut = CC_SAFE_MALLOC (cnt, int);
740 if (!tcut) {
741 fprintf (stderr, "out of memory in expand_the_node\n");
742 rval = 1; goto CLEANUP;
743 }
744
745 tcut[0] = n->num;
746 cnt = 1;
747 for (v = n->members; v; v = v->members) {
748 tcut[cnt++] = v->num;
749 }
750
751 *cutcount = cnt;
752 *cut = tcut;
753
754 CLEANUP:
755
756 return rval;
757 }
758
CCcut_SRK_identify_one_triangles(CC_SRKgraph * G,int * count,CC_SRKnode * qstart,double epsilon,double cutoff,int unmarked)759 void CCcut_SRK_identify_one_triangles (CC_SRKgraph *G, int *count,
760 CC_SRKnode *qstart, double epsilon, double cutoff, int unmarked)
761 {
762 CC_SRKnode *n;
763 CC_SRKedge *e, *f, *h;
764 CC_SRKnode *qhead, *qtail;
765 double tol = 1.0 - epsilon;
766 double ctol = cutoff - 1.0 - epsilon;
767
768 /* Identify any edge of weight one that is contained in a triangle of */
769 /* weight >= cutoff */
770
771 if (count) *count = 0;
772 if (qstart) {
773 qhead = qstart;
774 for (n = qstart; n->next; n = n->next)
775 n->onqueue = 1;
776 qtail = n;
777 qtail->onqueue = 1;
778 } else {
779 for (n = G->head; n->next; n = n->next) {
780 n->qnext = n->next;
781 n->onqueue = 1;
782 }
783 qhead = G->head;
784 qtail = n;
785 qtail->onqueue = 1;
786 qtail->qnext = (CC_SRKnode *) NULL;
787 }
788
789 while (qhead) {
790 n = qhead;
791 qhead = qhead->qnext;
792 if (!qhead)
793 qtail = (CC_SRKnode *) NULL;
794 if (n->parent != n || (unmarked && n->mark == G->marker))
795 continue;
796 n->onqueue = 0;
797
798 for (e = n->adj; e && e->weight < tol; e = e->next);
799 if (e) {
800 for (f = n->adj; f; f = f->next)
801 f->end->prweight = f->weight;
802 for (f = e->end->adj; f; f = f->next) {
803 if (unmarked && f->end->mark == G->marker)
804 continue;
805 if (f->weight + f->end->prweight >= ctol ||
806 (f->weight >= ctol && f->end != n)) {
807 CCcut_SRK_identify_nodes (G, n, e->end);
808 if (count) (*count)++;
809 ADD_TO_PR_QUEUE(n);
810 for (h = n->adj; h; h = h->next) {
811 ADD_TO_PR_QUEUE(h->end);
812 }
813 n->mark = G->marker;
814 goto GET_OUT;
815 }
816 }
817 GET_OUT:
818 for (e = n->adj; e; e = e->next)
819 e->end->prweight = -CC_MINCUT_BIGDOUBLE;
820 }
821 }
822 }
823
CCcut_SRK_identify_tight_triangles(CC_SRKgraph * G,int * count,double cutoff,int unmarked)824 void CCcut_SRK_identify_tight_triangles (CC_SRKgraph *G, int *count,
825 double cutoff, int unmarked)
826 {
827 CC_SRKnode *qhead, *qtail, *n, *m, *o;
828 CC_SRKedge *e, *f, *h;
829 double ctol;
830
831 if (count) *count = 0;
832 initial_queue (G, &qhead, &qtail, unmarked);
833
834 while (qhead) {
835 n = qhead;
836 qhead = qhead->qnext;
837 if (!qhead)
838 qtail = (CC_SRKnode *) NULL;
839 if (n->parent != n || (unmarked && n->mark == G->marker))
840 continue;
841 n->onqueue = 0;
842
843 for (e = n->adj; e; e = e->next) {
844 e->end->prweight = e->weight;
845 }
846
847 for (e = n->adj; e; e = e->next) {
848 m = e->end;
849 if (unmarked && m->mark == G->marker)
850 continue;
851 ctol = cutoff - e->weight;
852 for (f = m->adj; f; f = f->next) {
853 o = f->end;
854 if (unmarked && o->mark == G->marker)
855 continue;
856 if (f->weight + o->prweight >= ctol ||
857 (f->weight >= ctol && o != n)) {
858 CCcut_SRK_identify_nodes (G, n, m);
859 CCcut_SRK_identify_nodes (G, n, o);
860 if (count) (*count)++;
861 if (!unmarked) {
862 ADD_TO_PR_QUEUE(n);
863 for (h = n->adj; h; h = h->next) {
864 ADD_TO_PR_QUEUE(h->end);
865 }
866 }
867 n->mark = G->marker;
868 goto GET_OUT;
869 }
870 }
871 }
872
873 GET_OUT:
874 for (e = n->adj; e; e = e->next) {
875 e->end->prweight = -CC_MINCUT_BIGDOUBLE;
876 }
877 }
878 }
879
880
CCcut_SRK_identify_tight_squares(CC_SRKgraph * G,int * count,double cutoff,int unmarked)881 void CCcut_SRK_identify_tight_squares (CC_SRKgraph *G, int *count,
882 double cutoff, int unmarked)
883 {
884 CC_SRKnode *qhead, *qtail, *n, *m, *o, *p;
885 CC_SRKedge *e, *f, *h, *d;
886 double ctol;
887
888 if (count) *count = 0;
889 initial_queue (G, &qhead, &qtail, unmarked);
890
891 for (n = G->head; n; n = n->next) {
892 n->prweight = 0.0;
893 }
894
895 while (qhead) {
896 n = qhead;
897 qhead = qhead->qnext;
898 if (!qhead)
899 qtail = (CC_SRKnode *) NULL;
900 if (n->parent != n || (unmarked && n->mark == G->marker))
901 continue;
902 n->onqueue = 0;
903
904 for (e = n->adj; e; e = e->next) {
905 e->end->prweight = e->weight;
906 }
907
908 for (e = n->adj; e; e = e->next) {
909 m = e->end;
910 if (unmarked && m->mark == G->marker)
911 continue;
912 ctol = cutoff - e->weight;
913 for (f = m->adj; f; f = f->next) {
914 f->end->prweight += f->weight;
915 }
916 for (f = m->adj; f; f = f->next) {
917 o = f->end;
918 if (o == n || (unmarked && o->mark == G->marker))
919 continue;
920 for (h = o->adj; h; h = h->next) {
921 p = h->end;
922 if (p == n || p == m || (unmarked && p->mark == G->marker))
923 continue;
924 if (p->prweight + o->prweight + h->weight >= ctol) {
925 if (count) (*count)++;
926 for (d = m->adj; d; d = d->next) {
927 d->end->prweight -= d->weight;
928 }
929 CCcut_SRK_identify_nodes (G, n, m);
930 CCcut_SRK_identify_nodes (G, n, o);
931 CCcut_SRK_identify_nodes (G, n, p);
932 if (!unmarked) {
933 ADD_TO_PR_QUEUE(n);
934 for (d = n->adj; d; d = d->next) {
935 ADD_TO_PR_QUEUE(d->end);
936 }
937 }
938 n->mark = G->marker;
939 goto GET_OUT;
940 }
941 }
942 }
943 for (f = m->adj; f; f = f->next) {
944 f->end->prweight -= f->weight;
945 }
946 }
947 GET_OUT:
948 for (e = n->adj; e; e = e->next) {
949 e->end->prweight = 0.0;
950 }
951
952 }
953
954 for (n = G->head; n; n = n->next) {
955 n->prweight = -CC_MINCUT_BIGDOUBLE;
956 }
957 }
958
CCcut_SRK_identify_triangle_square(CC_SRKgraph * G,int * count,double epsilon,int unmarked)959 void CCcut_SRK_identify_triangle_square (CC_SRKgraph *G, int *count,
960 double epsilon, int unmarked)
961 {
962 CC_SRKnode *qhead, *qtail, *n, *m, *o, *p;
963 CC_SRKedge *e, *f, *h;
964 int shrinkit = 0;
965
966 /* shrink tight triangles within tight squares */
967
968 if (count) *count = 0;
969 initial_queue (G, &qhead, &qtail, unmarked);
970
971 for (n = G->head; n; n = n->next) {
972 n->prweight = 0.0;
973 }
974
975 while (qhead) {
976 n = qhead;
977 qhead = qhead->qnext;
978 if (!qhead)
979 qtail = (CC_SRKnode *) NULL;
980 if (n->parent != n || (unmarked && n->mark == G->marker))
981 continue;
982 n->onqueue = 0;
983
984 for (e = n->adj; e; e = e->next) {
985 e->end->prweight = e->weight;
986 }
987
988 for (e = n->adj; e; e = e->next) {
989 m = e->end;
990 if (unmarked && m->mark == G->marker)
991 continue;
992 for (f = m->adj; f; f = f->next) {
993 f->end->prweight += f->weight;
994 }
995 for (f = m->adj; f; f = f->next) {
996 o = f->end;
997 if (o == n || (unmarked && o->mark == G->marker))
998 continue;
999 if (e->weight + o->prweight >= 2.0 - epsilon) {
1000 for (h = o->adj; h && !shrinkit; h = h->next) {
1001 p = h->end;
1002 if (p != n && p != m &&
1003 (p->prweight + h->weight >= 1.0 - epsilon)) {
1004 shrinkit = 1;
1005 }
1006 }
1007 if (!shrinkit) {
1008 for (h = m->adj; h && !shrinkit; h = h->next) {
1009 p = h->end;
1010 if (p != n && p != m &&
1011 (p->prweight >= 1 - epsilon)) {
1012 shrinkit = 1;
1013 }
1014 }
1015 }
1016 if (shrinkit) {
1017 shrinkit = 0;
1018 for (h = m->adj; h; h = h->next) {
1019 h->end->prweight -= h->weight;
1020 }
1021 CCcut_SRK_identify_nodes (G, n, m);
1022 CCcut_SRK_identify_nodes (G, n, o);
1023 if (!unmarked) {
1024 ADD_TO_PR_QUEUE(n);
1025 for (h = n->adj; h; h = h->next) {
1026 ADD_TO_PR_QUEUE(h->end);
1027 }
1028 }
1029 n->mark = G->marker;
1030 goto GET_OUT;
1031 }
1032 }
1033 }
1034 for (f = m->adj; f; f = f->next) {
1035 f->end->prweight -= f->weight;
1036 }
1037 }
1038 GET_OUT:
1039 for (e = n->adj; e; e = e->next) {
1040 e->end->prweight = 0.0;
1041 }
1042
1043 }
1044
1045 for (n = G->head; n; n = n->next) {
1046 n->prweight = -CC_MINCUT_BIGDOUBLE;
1047 }
1048 }
1049
CCcut_SRK_identify_one_square(CC_SRKgraph * G,int * count,double epsilon,double cutoff,int unmarked)1050 void CCcut_SRK_identify_one_square (CC_SRKgraph *G, int *count,
1051 double epsilon, double cutoff, int unmarked)
1052 {
1053 CC_SRKnode *qhead, *qtail, *n, *m, *o, *p;
1054 CC_SRKedge *e, *f, *h, *d;
1055
1056 /* shrink the opposing 1's in a square where the edges between the 1's */
1057 /* have weight at least cutoff */
1058
1059 if (count) *count = 0;
1060 initial_queue (G, &qhead, &qtail, unmarked);
1061
1062 for (n = G->head; n; n = n->next) {
1063 n->prweight = 0.0;
1064 }
1065
1066 while (qhead) {
1067 n = qhead;
1068 qhead = qhead->qnext;
1069 if (!qhead)
1070 qtail = (CC_SRKnode *) NULL;
1071 if (n->parent != n || (unmarked && n->mark == G->marker))
1072 continue;
1073 n->onqueue = 0;
1074
1075 for (e = n->adj; e && e->weight < 1.0 - epsilon; e = e->next);
1076 if (e) {
1077 m = e->end;
1078 if (!unmarked || m->mark != G->marker) {
1079 for (f = n->adj; f; f = f->next)
1080 f->end->prweight = f->weight;
1081 for (f = m->adj; f; f = f->next)
1082 f->end->prweight += f->weight;
1083 for (f = m->adj; f; f = f->next) {
1084 o = f->end;
1085 if (o == n || (unmarked && o->mark == G->marker))
1086 continue;
1087 for (h = o->adj; h && h->weight < 1.0 - epsilon;
1088 h = h->next);
1089 if (h) {
1090 p = h->end;
1091 if (p != n && p != m &&
1092 (!unmarked || p->mark != G->marker) &&
1093 (p->prweight + o->prweight >= cutoff)) {
1094 CCcut_SRK_identify_nodes (G, n, m);
1095 CCcut_SRK_identify_nodes (G, o, p);
1096 if (count) (*count)++;
1097 if (!unmarked) {
1098 ADD_TO_PR_QUEUE(n);
1099 for (d = n->adj; d; d = d->next) {
1100 ADD_TO_PR_QUEUE(d->end);
1101 }
1102 ADD_TO_PR_QUEUE(o);
1103 for (d = o->adj; d; d = d->next) {
1104 ADD_TO_PR_QUEUE(d->end);
1105 }
1106 }
1107 n->mark = G->marker;
1108 o->mark = G->marker;
1109 goto GET_OUT;
1110 }
1111 }
1112 }
1113 GET_OUT:
1114 for (e = n->adj; e; e = e->next)
1115 e->end->prweight = 0.0;
1116 for (e = m->adj; e; e = e->next)
1117 e->end->prweight = 0.0;
1118 }
1119 }
1120 }
1121
1122 for (n = G->head; n; n = n->next) {
1123 n->prweight = -CC_MINCUT_BIGDOUBLE;
1124 }
1125 }
1126
initial_queue(CC_SRKgraph * G,CC_SRKnode ** outqhead,CC_SRKnode ** outqtail,int unmarked)1127 static void initial_queue (CC_SRKgraph *G, CC_SRKnode **outqhead,
1128 CC_SRKnode **outqtail, int unmarked)
1129 {
1130 CC_SRKnode *n, *qhead, *qtail;
1131
1132 if (unmarked) {
1133 qhead = (CC_SRKnode *) NULL;
1134 qtail = (CC_SRKnode *) NULL;
1135 for (n = G->head; n; n = n->next) {
1136 n->onqueue = 0;
1137 if (n->mark != G->marker) {
1138 ADD_TO_PR_QUEUE (n);
1139 }
1140 }
1141 } else {
1142 for (n = G->head; n->next; n = n->next) {
1143 n->qnext = n->next;
1144 n->onqueue = 1;
1145 }
1146 qhead = G->head;
1147 qtail = n;
1148 qtail->onqueue = 1;
1149 qtail->qnext = (CC_SRKnode *) NULL;
1150 }
1151
1152 *outqhead = qhead;
1153 *outqtail = qtail;
1154 }
1155
CCcut_SRK_identify_set(CC_SRKgraph * G,int scount,int * slist)1156 int CCcut_SRK_identify_set (CC_SRKgraph *G, int scount, int *slist)
1157 {
1158 int rval = 0;
1159 CC_SRKnode **nlist = (CC_SRKnode **) NULL;
1160 CC_SRKnode *n;
1161 int i, k, cnt;
1162 int *perm = (int *) NULL;
1163
1164 nlist = CC_SAFE_MALLOC (scount, CC_SRKnode *);
1165 CCcheck_NULL (nlist, "out of memory for nlist");
1166
1167 perm = CC_SAFE_MALLOC (scount, int);
1168 CCcheck_NULL (perm, "out of memory for perm");
1169
1170 for (i = 0; i < scount; i++) perm[i] = i;
1171 CCutil_int_perm_quicksort (perm, slist, scount);
1172
1173 k = 0;
1174 for (n = G->head, cnt = 0; n && k < scount; n = n->next, cnt++) {
1175 if (cnt == slist[perm[k]]) {
1176 nlist[perm[k]] = n;
1177 k++;
1178 }
1179 }
1180
1181 if (k != scount) {
1182 fprintf (stderr, "Error - did not find all nodes in set\n");
1183 rval = 1; goto CLEANUP;
1184 }
1185
1186 for (i = 1; i < scount; i++) {
1187 CCcut_SRK_identify_nodes (G, nlist[0], nlist[i]);
1188 }
1189
1190 CLEANUP:
1191
1192 CC_IFFREE (nlist, CC_SRKnode *);
1193 CC_IFFREE (perm, int);
1194 return rval;
1195 }
1196
CCcut_SRK_identify_nodes(CC_SRKgraph * G,CC_SRKnode * n,CC_SRKnode * m)1197 void CCcut_SRK_identify_nodes (CC_SRKgraph *G, CC_SRKnode *n, CC_SRKnode *m)
1198 {
1199 CC_SRKedge *e;
1200
1201 m->parent = n;
1202 n->weight += m->weight;
1203
1204 if (!n->members) {
1205 n->members = m;
1206 } else if (!m->members) {
1207 m->members = n->members;
1208 n->members = m;
1209 } else {
1210 CC_SRKnode *t;
1211 for (t = n->members; t->members; t = t->members);
1212 t->members = m;
1213 }
1214
1215 for (e = m->adj; e; e = e->next) {
1216 e->other->end = n;
1217 }
1218
1219 merge_adj (G, n, m);
1220
1221 if (m->prev)
1222 m->prev->next = m->next;
1223 else
1224 G->head = m->next;
1225 if (m->next)
1226 m->next->prev = m->prev;
1227 }
1228
merge_adj(CC_SRKgraph * G,CC_SRKnode * n,CC_SRKnode * m)1229 static void merge_adj (CC_SRKgraph *G, CC_SRKnode *n, CC_SRKnode *m)
1230 {
1231 CC_SRKedge *e, *f, *last, *work;
1232 CC_SRKedge **hit = G->hit;
1233
1234 /* String together the two lists */
1235
1236 if (n->adj) {
1237 for (last = n->adj; last->next; last = last->next);
1238 last->next = m->adj;
1239 if (m->adj)
1240 m->adj->prev = last;
1241 work = n->adj;
1242 } else {
1243 work = m->adj;
1244 }
1245
1246 /* Remove any edges that become loops */
1247
1248 while (work && work->end == n) {
1249 n->weight -= work->weight;
1250 work = work->next;
1251 }
1252
1253 if (work) {
1254 work->prev = (CC_SRKedge *) NULL;
1255 for (e = work->next; e; e = e->next) {
1256 if (e->end == n) {
1257 n->weight -= e->weight;
1258 e->prev->next = e->next;
1259 if (e->next)
1260 e->next->prev = e->prev;
1261 }
1262 }
1263 } else {
1264 n->adj = (CC_SRKedge *) NULL;
1265 return;
1266 }
1267
1268 /* Remove the duplicate edges in the work list */
1269
1270 hit[work->end->num] = work;
1271 for (e = work->next; e; e = e->next) {
1272 if (hit[e->end->num]) {
1273 /* A duplicate edge */
1274
1275 hit[e->end->num]->weight += e->weight;
1276 hit[e->end->num]->other->weight = hit[e->end->num]->weight;
1277 e->prev->next = e->next;
1278 if (e->next)
1279 e->next->prev = e->prev;
1280
1281 /* Fix the adj of the other end of the duplicate */
1282
1283 f = e->other;
1284 if (f->prev) {
1285 f->prev->next = f->next;
1286 } else {
1287 e->end->adj = f->next;
1288 }
1289 if (f->next) {
1290 f->next->prev = f->prev;
1291 }
1292 } else {
1293 hit[e->end->num] = e;
1294 }
1295 }
1296
1297 for (e = work; e; e = e->next)
1298 hit[e->end->num] = (CC_SRKedge *) NULL;
1299 n->adj = work;
1300 }
1301
CCcut_SRK_buildgraph(CC_SRKgraph * G,int ncount,int ecount,int * elist,double * dlen)1302 int CCcut_SRK_buildgraph (CC_SRKgraph *G, int ncount, int ecount, int *elist,
1303 double *dlen)
1304 {
1305 int i;
1306 int *degree = (int *) NULL;
1307 int newecount = 0;
1308 CC_SRKnode *nodespace, *n, *n1, *n2;
1309 CC_SRKedge *e, *adj1, *adj2;
1310 CC_SRKedge **hit;
1311
1312 G->nodespace = CC_SAFE_MALLOC(ncount, CC_SRKnode);
1313 G->hit = CC_SAFE_MALLOC(ncount, CC_SRKedge *);
1314 if (!G->nodespace || !G->hit) {
1315 fprintf (stderr, "out of memory in CCcut_SRK_buildgraph\n");
1316 CC_IFFREE(G->nodespace, CC_SRKnode);
1317 CC_IFFREE(G->hit, CC_SRKedge *);
1318 return 1;
1319 }
1320 nodespace = G->nodespace;
1321 hit = G->hit;
1322 G->head = nodespace;
1323 G->original_ncount = ncount;
1324 G->original_ecount = ecount;
1325 G->marker = 0;
1326
1327 degree = CC_SAFE_MALLOC(ncount, int);
1328 if (!degree) {
1329 fprintf (stderr, "out of memory in CCcut_SRK_buildgraph\n");
1330 CC_IFFREE(G->nodespace, CC_SRKnode);
1331 CC_IFFREE(G->hit, CC_SRKedge *);
1332 return 1;
1333 }
1334
1335 for (i = 0, n = nodespace; i < ncount; i++, n++) {
1336 n->prev = n - 1;
1337 n->next = n + 1;
1338 n->num = i;
1339 n->members = (CC_SRKnode *) NULL;
1340 n->parent = n;
1341 n->prweight = -CC_MINCUT_BIGDOUBLE;
1342 n->weight = 0.0;
1343 hit[i] = (CC_SRKedge *) NULL;
1344 degree[i] = 0;
1345 n->onecnt = 0;
1346 n->mark = 0;
1347 }
1348 nodespace[0].prev = (CC_SRKnode *) NULL;
1349 nodespace[ncount - 1].next = (CC_SRKnode *) NULL;
1350
1351 for (i = 0; i < ecount; i++) {
1352 if (dlen[i] > SRK_ZERO_EPSILON) {
1353 newecount++;
1354 degree[elist[2*i]]++;
1355 degree[elist[2*i+1]]++;
1356 }
1357 }
1358 G->edgespace = CC_SAFE_MALLOC(2*newecount, CC_SRKedge);
1359 if (!G->edgespace) {
1360 fprintf (stderr, "out of memory in CCcut_SRK_buildgraph\n");
1361 CC_IFFREE(G->nodespace, CC_SRKnode);
1362 CC_IFFREE(G->hit, CC_SRKedge *);
1363 return 1;
1364 }
1365
1366 for (e = G->edgespace, i = 0; i < ncount; i++) {
1367 nodespace[i].adj = e;
1368 e += degree[i];
1369 }
1370 for (i = 0; i < ecount; i++) {
1371 if (dlen[i] > SRK_ZERO_EPSILON) {
1372 n1 = nodespace + elist[2 * i];
1373 n2 = nodespace + elist[2 * i + 1];
1374 adj1 = n1->adj;
1375 adj2 = n2->adj;
1376 adj1->end = n2;
1377 adj1->weight = dlen[i];
1378 adj1->next = adj1 + 1;
1379 adj1->prev = adj1 - 1;
1380 adj1->other = adj2;
1381 adj2->end = n1;
1382 adj2->weight = dlen[i];
1383 adj2->next = adj2 + 1;
1384 adj2->prev = adj2 - 1;
1385 adj2->other = adj1;
1386 n1->adj++;
1387 n2->adj++;
1388 if (dlen[i] == 1.0) {
1389 n1->onecnt++;
1390 n2->onecnt++;
1391 }
1392 }
1393 }
1394 for (e = G->edgespace, i = 0; i < ncount; i++) {
1395 if (degree[i]) {
1396 (nodespace[i].adj - 1)->next = (CC_SRKedge *) NULL;
1397 nodespace[i].adj = e;
1398 nodespace[i].adj->prev = (CC_SRKedge *) NULL;
1399 e += degree[i];
1400 } else {
1401 nodespace[i].adj = (CC_SRKedge *) NULL;
1402 }
1403 }
1404
1405 for (i = 0, n = nodespace; i < ncount; i++, n++) {
1406 for (e = n->adj; e; e = e->next) {
1407 n->weight += e->weight;
1408 }
1409 }
1410
1411 CC_IFFREE(degree, int);
1412 return 0;
1413 }
1414
CCcut_SRK_grab_edges(CC_SRKgraph * G,int * oncount,int * oecount,int ** olist,double ** olen,CC_SRKexpinfo * expand)1415 int CCcut_SRK_grab_edges (CC_SRKgraph *G, int *oncount, int *oecount,
1416 int **olist, double **olen, CC_SRKexpinfo *expand)
1417 {
1418 int rval = 0;
1419 int k, num;
1420 int ncount = 0, ecount = 0;
1421 CC_SRKnode *n;
1422 CC_SRKedge *e;
1423
1424 *oncount = 0;
1425 *oecount = 0;
1426 *olist = (int *) NULL;
1427 *olen = (double *) NULL;
1428 if (expand) {
1429 CCcut_SRK_init_expinfo (expand);
1430 }
1431
1432 for (n = G->head; n; n = n->next) {
1433 n->newnum = ncount;
1434 for (e = n->adj; e; e = e->next)
1435 ecount++;
1436 ncount++;
1437 }
1438
1439 if (ecount % 2) {
1440 fprintf (stderr, "Error in grab_edges\n");
1441 rval = 1; goto CLEANUP;
1442 } else {
1443 ecount /= 2;
1444 }
1445
1446 if (ecount == 0) {
1447 rval = 0; goto CLEANUP;
1448 }
1449
1450 *olist = CC_SAFE_MALLOC (ecount * 2, int);
1451 *olen = CC_SAFE_MALLOC (ecount, double);
1452 if (!(*olist) || !(*olen)) {
1453 fprintf (stderr, "out of memory in grab_edges\n");
1454 rval = 1; goto CLEANUP;
1455 }
1456
1457 k = 0;
1458 for (n = G->head; n; n = n->next) {
1459 num = n->newnum;
1460 for (e = n->adj; e; e = e->next) {
1461 if (num < e->end->newnum) {
1462 (*olist)[2 * k] = num;
1463 (*olist)[2 * k + 1] = e->end->newnum;
1464 (*olen)[k++] = e->weight;
1465 }
1466 }
1467 }
1468 if (k != ecount) {
1469 fprintf (stderr, "Error in grab_edges\n");
1470 rval = 1; goto CLEANUP;
1471 }
1472
1473 *oncount = ncount;
1474 *oecount = ecount;
1475
1476 if (expand) {
1477 rval = CCcut_SRK_grab_nodes (G, expand);
1478 if (rval) {
1479 fprintf (stderr, "CCcut_SRK_grab_nodes failed\n"); goto CLEANUP;
1480 }
1481 }
1482
1483 CLEANUP:
1484
1485 if (rval) {
1486 CC_IFFREE (*olist, int);
1487 CC_IFFREE (*olen, double);
1488 if (expand) {
1489 CCcut_SRK_free_expinfo (expand);
1490 }
1491 }
1492
1493 return rval;
1494 }
1495
CCcut_SRK_grab_nodes(CC_SRKgraph * G,CC_SRKexpinfo * expand)1496 int CCcut_SRK_grab_nodes (CC_SRKgraph *G, CC_SRKexpinfo *expand)
1497 {
1498 int rval = 0;
1499 int i;
1500 CC_SRKnode *n, *m;
1501 int total = 0;
1502 int ncount = 0;
1503
1504 if (!expand) {
1505 fprintf (stderr, "CCcut_SRK_grab_nodes called without an expand struct\n");
1506 rval = 1; goto CLEANUP;
1507 }
1508
1509 for (n = G->head; n; n = n->next) {
1510 ncount++;
1511 }
1512
1513 CCcut_SRK_init_expinfo (expand);
1514 expand->ncount = ncount;
1515 expand->members = CC_SAFE_MALLOC (G->original_ncount, int);
1516 expand->memindex = CC_SAFE_MALLOC (ncount + 1, int);
1517 if (!(expand->members) || !(expand->memindex)) {
1518 fprintf (stderr, "out of memory in grab_nodes\n");
1519 rval = 1; goto CLEANUP;
1520 }
1521 for (n = G->head, i = 0; n; n = n->next, i++) {
1522 expand->memindex[i] = total;
1523 expand->members[total++] = n->num;
1524 for (m = n->members; m; m = m->members)
1525 expand->members[total++] = m->num;
1526 }
1527 expand->memindex[i] = total;
1528
1529 CLEANUP:
1530
1531 if (rval) CCcut_SRK_free_expinfo (expand);
1532 return rval;
1533 }
1534
CCcut_SRK_init_graph(CC_SRKgraph * G)1535 void CCcut_SRK_init_graph (CC_SRKgraph *G)
1536 {
1537 if (G) {
1538 G->nodespace = (CC_SRKnode *) NULL;
1539 G->edgespace = (CC_SRKedge *) NULL;
1540 G->head = (CC_SRKnode *) NULL;
1541 G->hit = (CC_SRKedge **) NULL;
1542 G->original_ncount = 0;
1543 G->original_ecount = 0;
1544 G->marker = 0;
1545 }
1546 }
1547
CCcut_SRK_free_graph(CC_SRKgraph * G)1548 void CCcut_SRK_free_graph (CC_SRKgraph *G)
1549 {
1550 if (G) {
1551 CC_IFFREE(G->nodespace, CC_SRKnode);
1552 CC_IFFREE(G->edgespace, CC_SRKedge);
1553 CC_IFFREE(G->hit, CC_SRKedge *);
1554 }
1555 }
1556
CCcut_SRK_increment_marker(CC_SRKgraph * G)1557 void CCcut_SRK_increment_marker (CC_SRKgraph *G)
1558 {
1559 if (G) {
1560 G->marker++;
1561 }
1562 }
1563
CCcut_SRK_set_mark(CC_SRKgraph * G,int marker)1564 void CCcut_SRK_set_mark (CC_SRKgraph *G, int marker)
1565 {
1566 if (G) {
1567 CC_SRKnode *n;
1568
1569 G->marker = marker;
1570 for (n = G->head; n; n = n->next) {
1571 n->mark = marker;
1572 }
1573 }
1574 }
1575
CCcut_SRK_init_callback(CC_SRKcallback * cb)1576 void CCcut_SRK_init_callback (CC_SRKcallback *cb)
1577 {
1578 if (cb) {
1579 cb->cutoff = 0.0;
1580 cb->pass_param = (void *) NULL;
1581 cb->doit_fn = (int (*) (double, int, int *, void *)) NULL;
1582 }
1583 }
1584
CCcut_SRK_trivial(int ncount,CC_SRKexpinfo * expand)1585 int CCcut_SRK_trivial (int ncount, CC_SRKexpinfo *expand)
1586 {
1587 int i;
1588
1589 CCcut_SRK_init_expinfo (expand);
1590 expand->memindex = CC_SAFE_MALLOC (ncount+1, int);
1591 if (!expand->memindex) {
1592 fprintf (stderr, "Out of memory in CCcut_SRK_trivial\n");
1593 return -1;
1594 }
1595 expand->members = CC_SAFE_MALLOC (ncount, int);
1596 if (!expand->members) {
1597 fprintf (stderr, "Out of memory in CCcut_SRK_trivial\n");
1598 CC_FREE (expand->memindex, int);
1599 return -1;
1600 }
1601 for (i=0; i<ncount; i++) {
1602 expand->members[i] = i;
1603 expand->memindex[i] = i;
1604 }
1605 expand->memindex[ncount] = ncount;
1606 expand->ncount = ncount;
1607 return 0;
1608 }
1609
CCcut_SRK_init_expinfo(CC_SRKexpinfo * expand)1610 void CCcut_SRK_init_expinfo (CC_SRKexpinfo *expand)
1611 {
1612 expand->ncount = 0;
1613 expand->memindex = (int *) NULL;
1614 expand->members = (int *) NULL;
1615 }
1616
CCcut_SRK_free_expinfo(CC_SRKexpinfo * expand)1617 void CCcut_SRK_free_expinfo (CC_SRKexpinfo *expand)
1618 {
1619 expand->ncount = 0;
1620 CC_IFFREE (expand->memindex, int);
1621 CC_IFFREE (expand->members, int);
1622 }
1623
CCcut_SRK_expand(CC_SRKexpinfo * expand,int * arr,int size,int ** pnewarr,int * pnewsize)1624 int CCcut_SRK_expand (CC_SRKexpinfo *expand, int *arr, int size, int **pnewarr,
1625 int *pnewsize)
1626 {
1627 int newsize = 0;
1628 int *newarr = (int *) NULL;
1629 int i, j, jend;
1630
1631 *pnewsize = 0;
1632 *pnewarr = (int *) NULL;
1633 for (i=0; i<size; i++) {
1634 newsize += expand->memindex[arr[i]+1] - expand->memindex[arr[i]];
1635 }
1636 newarr = CC_SAFE_MALLOC (newsize, int);
1637 if (!newarr) {
1638 fprintf (stderr, "Out of memory in CCcut_SRK_expand\n");
1639 return -1;
1640 }
1641 newsize = 0;
1642 for (i=0; i<size; i++) {
1643 for (j=expand->memindex[arr[i]], jend = expand->memindex[arr[i]+1];
1644 j < jend; j++) {
1645 newarr[newsize++] = expand->members[j];
1646 }
1647 }
1648 *pnewarr = newarr;
1649 *pnewsize = newsize;
1650 return 0;
1651 }
1652
CCcut_SRK_original_ncount(CC_SRKexpinfo * expand)1653 int CCcut_SRK_original_ncount (CC_SRKexpinfo *expand)
1654 {
1655 return expand->memindex[expand->ncount];
1656 }
1657
1658 #ifdef DEBUG_SHRINK
printgraph(CC_SRKgraph * G)1659 static void printgraph (CC_SRKgraph *G)
1660 {
1661 CC_SRKnode *n;
1662 CC_SRKedge *e;
1663
1664 for (n = G->head; n; n = n->next) {
1665 printf ("Node %d: ", n->num);
1666 fflush (stdout);
1667 for (e = n->adj; e; e = e->next) {
1668 printf ("%d [%.2f] ", e->end->num, e->weight);
1669 fflush (stdout);
1670 if (e->other->end != n || e->other->weight != e->weight) {
1671 printf ("(Whoops) ");
1672 fflush (stdout);
1673 }
1674 }
1675 printf ("\n");
1676 }
1677 }
1678 #endif
1679