1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file misc_stp.c
17 * @brief Miscellaneous methods used for solving Steiner problems
18 * @author Daniel Rehfeldt
19 *
20 * This file includes miscellaneous methods used for solving Steiner problems. For more details see \ref STP_MISC page.
21 *
22 * @page STP_MISC Miscellaneous methods used for Steiner tree problems
23 *
24 * This file implements an integer data linked list, a linear link-cut tree, a union-find data structure
25 * and a pairing heap.
26 *
27 * A list of all interface methods can be found in misc_stp.h.
28 */
29
30 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31
32 #include <assert.h>
33 #include <string.h>
34 #include "heur_tm.h"
35 #include "probdata_stp.h"
36 #include "portab.h"
37 #include "scip/misc.h"
38
39
40 /** returns maximum of given SCIP_Real values */
misc_stp_maxReal(SCIP_Real * realarr,unsigned nreals)41 SCIP_Real misc_stp_maxReal(
42 SCIP_Real* realarr, /**< array of reals */
43 unsigned nreals /**< size of array of reals */
44 )
45 {
46 SCIP_Real max = realarr[0];
47
48 assert(nreals >= 1);
49
50 for( unsigned i = 1; i < nreals; i++ )
51 if( realarr[i] > max )
52 max = realarr[i];
53
54 return max;
55 }
56
57 /** compares distances of two GNODE structures */
SCIP_DECL_SORTPTRCOMP(GNODECmpByDist)58 SCIP_DECL_SORTPTRCOMP(GNODECmpByDist)
59 {
60 SCIP_Real first = ((GNODE*)elem1)->dist;
61 SCIP_Real second = ((GNODE*)elem2)->dist;
62 if( LT(first,second) )
63 {
64 return -1;
65 }
66 else if( EQ(first, second) ) /* first == second */
67 {
68 return 0;
69 }
70 else
71 {
72 return 1;
73 }
74 }
75
76 /** insert a new node */
SCIPintListNodeInsert(SCIP * scip,IDX ** node,int nodeval)77 SCIP_RETCODE SCIPintListNodeInsert(
78 SCIP* scip, /**< SCIP data structure */
79 IDX** node, /**< pointer to the last list node */
80 int nodeval /**< data of the new node */
81 )
82 {
83 IDX* curr;
84 curr = *node;
85
86 SCIP_CALL( SCIPallocBlockMemory(scip, node) );
87 (*node)->index = nodeval;
88 (*node)->parent = (curr);
89
90 return SCIP_OKAY;
91 }
92
93 /** append copy of list pertaining to node2 to node1 */
SCIPintListNodeAppendCopy(SCIP * scip,IDX ** node1,IDX * node2,SCIP_Bool * conflict)94 SCIP_RETCODE SCIPintListNodeAppendCopy(
95 SCIP* scip, /**< SCIP data structure */
96 IDX** node1, /**< pointer to the last node of list to be enlarged */
97 IDX* node2, /**< pointer to the last node of source list */
98 SCIP_Bool* conflict /**< pointer to store whether a conflict has been detected by the method */
99 )
100 {
101 IDX* new;
102 IDX* curr1;
103 IDX* curr2;
104 int curr2idx;
105 SCIP_Bool checkconflict;
106
107 assert(scip != NULL);
108
109 if( node2 == NULL )
110 return SCIP_OKAY;
111
112 if( conflict != NULL )
113 {
114 *conflict = FALSE;
115 checkconflict = TRUE;
116 }
117 else
118 {
119 checkconflict = FALSE;
120 }
121
122 new = NULL;
123 curr1 = *node1;
124 curr2 = node2;
125
126 if( curr1 != NULL )
127 {
128 int* pointer;
129 int* hasharr;
130 int i;
131 int nelems = 0;
132 const SCIP_Bool ignoreconflicts = (SCIPprobdataGetType(scip) == STP_SPG);
133
134 if( !ignoreconflicts )
135 {
136 /* todo fix this hack; don't check at all, but just add */
137 const int maxlength = SCIPprobdataGetNorgEdges(scip);
138
139 assert(maxlength > 0);
140
141 SCIP_CALL(SCIPallocCleanBufferArray(scip, &hasharr, maxlength));
142 SCIP_CALL(SCIPallocCleanBufferArray(scip, &pointer, maxlength));
143 while( curr1 != NULL )
144 {
145 i = curr1->index;
146 assert(i < maxlength && nelems < maxlength);
147 pointer[nelems++] = i;
148 hasharr[i] = 1;
149 curr1 = curr1->parent;
150 }
151 }
152
153 curr1 = *node1;
154 while( curr2 != NULL )
155 {
156 curr2idx = curr2->index;
157
158 if( ignoreconflicts || hasharr[curr2idx] == 0 )
159 {
160 SCIP_CALL( SCIPallocBlockMemory(scip, &new) );
161 new->index = curr2idx;
162 new->parent = curr1;
163 curr1 = new;
164 }
165 else if( checkconflict )
166 {
167 assert(conflict != NULL);
168 (*conflict) = TRUE;
169 }
170
171 curr2 = curr2->parent;
172 }
173
174 if( !ignoreconflicts )
175 {
176 for( i = 0; i < nelems; i++ )
177 {
178 hasharr[pointer[i]] = 0;
179 pointer[i] = 0;
180 }
181 SCIPfreeCleanBufferArray(scip, &pointer);
182 SCIPfreeCleanBufferArray(scip, &hasharr);
183 }
184 }
185 else
186 {
187 while( curr2 != NULL )
188 {
189 SCIP_CALL( SCIPallocBlockMemory(scip, &new) );
190 new->index = curr2->index;
191 new->parent = curr1;
192 curr1 = new;
193
194 curr2 = curr2->parent;
195 }
196 }
197
198 if( new != NULL )
199 *node1 = new;
200
201 return SCIP_OKAY;
202 }
203
204 /** free list */
SCIPintListNodeFree(SCIP * scip,IDX ** node)205 void SCIPintListNodeFree(
206 SCIP* scip, /**< SCIP data structure */
207 IDX** node /**< pointer to the last list node */
208 )
209 {
210 IDX* curr;
211 curr = *node;
212
213 while( curr != NULL )
214 {
215 *node = curr->parent;
216 SCIPfreeBlockMemory(scip, &curr);
217 curr = *node;
218 }
219 assert(*node == NULL);
220 }
221
222 /*
223 * Linear Link Cut Tree
224 */
225
226 /** inits a node, setting 'parent' and 'edge' to its default values */
SCIPlinkcuttreeInit(NODE * v)227 void SCIPlinkcuttreeInit(
228 NODE* v /**< pointer to node representing the tree */
229 )
230 {
231 v->parent = NULL;
232 v->edge = -1;
233 }
234
235 /** renders v a child of w; v has to be the root of its tree */
SCIPlinkcuttreeLink(NODE * v,NODE * w,int edge)236 void SCIPlinkcuttreeLink(
237 NODE* v, /**< pointer to node representing the tree */
238 NODE* w, /**< pointer to the child */
239 int edge /**< link edge */
240 )
241 {
242 assert(v->parent == NULL);
243 assert(v->edge == -1);
244 v->parent = w;
245 v->edge = edge;
246 }
247
248 /** cut tree at given node */
SCIPlinkcuttreeCut(NODE * v)249 void SCIPlinkcuttreeCut(
250 NODE* v /**< node to cut at */
251 )
252 {
253 v->edge = -1;
254 v->parent = NULL;
255 }
256
257 /** finds minimum weight chain between node 'start' and distinct root node **/
SCIPlinkcuttreeFindMinChain(SCIP * scip,const SCIP_Real * nodeweight,const int * head,const int * stdeg,const NODE * start,NODE ** first,NODE ** last)258 SCIP_Real SCIPlinkcuttreeFindMinChain(
259 SCIP* scip, /**< SCIP data structure */
260 const SCIP_Real* nodeweight, /**< node weight array */
261 const int* head, /**< head of an arc */
262 const int* stdeg, /**< degree in Steiner tree */
263 const NODE* start, /**< the node to start at */
264 NODE** first, /**< first node of chain */
265 NODE** last /**< last node of chain */
266 )
267 {
268 NODE* curr;
269 NODE* tmpfirst;
270 SCIP_Real min;
271 SCIP_Real tmpmin;
272 SCIP_Bool stopped;
273 int node;
274
275 assert(scip != NULL);
276 assert(head != NULL);
277 assert(nodeweight != NULL);
278 assert(stdeg != NULL);
279 assert(start != NULL);
280 assert(first != NULL);
281 assert(last != NULL);
282
283 *last = NULL;
284 *first = NULL;
285
286 min = 0.0;
287 tmpmin = 0.0;
288 stopped = TRUE;
289
290 /* while p is not root */
291 for( curr = (NODE*) start; curr->parent != NULL; curr = curr->parent )
292 {
293 assert(curr->edge >= 0);
294
295 node = head[curr->edge];
296
297 if( stdeg[node] == 2 && !SCIPisPositive(scip, nodeweight[node]) && curr->parent->parent != NULL )
298 {
299 if( stopped )
300 {
301 stopped = FALSE;
302 tmpmin = 0.0;
303 tmpfirst = curr;
304 }
305 tmpmin += nodeweight[node];
306 }
307 else
308 {
309 /* better chain found? */
310 if( !stopped && SCIPisLT(scip, tmpmin, min) )
311 {
312 assert(tmpfirst != NULL);
313 min = tmpmin;
314 *first = tmpfirst;
315 *last = curr;
316 }
317 stopped = TRUE;
318 }
319 }
320
321 return min;
322 }
323
324
325
326 /** finds the max edge value between node 'v' and the root of the tree **/
SCIPlinkcuttreeFindMax(SCIP * scip,const SCIP_Real * cost,NODE * v)327 NODE* SCIPlinkcuttreeFindMax(
328 SCIP* scip, /**< SCIP data structure */
329 const SCIP_Real* cost, /**< edge cost array */
330 NODE* v /**< the node */
331 )
332 {
333 NODE* p = v;
334 NODE* q = v;
335 SCIP_Real max = -1;
336
337 /* while p is not the root */
338 while( p->parent != NULL )
339 {
340 assert(p->edge >= 0);
341 if( SCIPisGE(scip, cost[p->edge], max) )
342 {
343 max = cost[p->edge];
344 q = p;
345 }
346 p = p->parent;
347 }
348 return q;
349 }
350
351 /** makes vertex v the root of the link cut tree */
SCIPlinkcuttreeEvert(NODE * v)352 void SCIPlinkcuttreeEvert(
353 NODE* v /**< the vertex to become the root */
354 )
355 {
356 NODE* p = NULL;
357 NODE* q = v;
358 NODE* r;
359 int val = -1;
360 int tmpval;
361
362 assert(v != NULL);
363
364 while( q != NULL )
365 {
366 r = q->parent;
367 tmpval = q->edge;
368 if( val != -1 )
369 q->edge = flipedge(val);
370 else
371 q->edge = -1;
372 val = tmpval;
373 q->parent = p;
374 p = q;
375 q = r;
376 }
377 }
378
379
380
381 /*
382 * Pairing Heap
383 */
384
385 /** links nodes 'root1' and 'root2' together */
SCIPpairheapMergeheaps(SCIP * scip,PHNODE * root1,PHNODE * root2)386 PHNODE* SCIPpairheapMergeheaps(
387 SCIP* scip, /**< SCIP data structure */
388 PHNODE *root1, /**< pointer to root of first heap */
389 PHNODE *root2 /**< pointer to root of second heap */
390 )
391 {
392 if( root2 == NULL )
393 return root1;
394 if( root1 == NULL )
395 return root2;
396
397 if( root1->key <= root2->key )
398 {
399 /* attach root2 as (the leftmost) child of root1 */
400 root2->prev = root1;
401 root1->sibling = root2->sibling;
402 if( root1->sibling != NULL )
403 root1->sibling->prev = root1;
404
405 root2->sibling = root1->child;
406 if( root2->sibling != NULL )
407 root2->sibling->prev = root2;
408
409 root1->child = root2;
410
411 return root1;
412 }
413 else
414 {
415 /* attach root1 as (the leftmost) child of root2 */
416 root2->prev = root1->prev;
417 root1->prev = root2;
418 root1->sibling = root2->child;
419 if( root1->sibling != NULL )
420 root1->sibling->prev = root1;
421
422 root2->child = root1;
423
424 return root2;
425 }
426 }
427
428 /** add heap to heap */
SCIPpairheapAddtoheap(SCIP * scip,PHNODE * root1,PHNODE * root2)429 PHNODE* SCIPpairheapAddtoheap(
430 SCIP* scip, /**< SCIP data structure */
431 PHNODE* root1, /**< pointer to root of first heap */
432 PHNODE* root2 /**< pointer to root of second heap */
433 )
434 {
435 assert(root2 != NULL);
436 assert(root1 != NULL);
437
438 if( root1->key <= root2->key )
439 {
440 /* attach root2 as (the leftmost) child of root1 */
441 root2->prev = root1;
442 root1->sibling = root2->sibling;
443 /* @todo: should never happen */
444 if( root1->sibling != NULL )
445 {
446 root1->sibling->prev = root1;
447 }
448
449 root2->sibling = root1->child;
450 if( root2->sibling != NULL )
451 root2->sibling->prev = root2;
452
453 root1->child = root2;
454
455 return root1;
456 }
457 else
458 {
459 /* attach root1 as (the leftmost) child of root2 */
460 root2->prev = root1->prev;
461 root1->prev = root2;
462 root1->sibling = root2->child;
463 if( root1->sibling != NULL )
464 root1->sibling->prev = root1;
465
466 root2->child = root1;
467
468 return root2;
469 }
470 }
471
472 /** internal method for combining the siblings after the root has been deleted */
473 static
pairheapCombineSiblings(SCIP * scip,PHNODE ** p,int size)474 SCIP_RETCODE pairheapCombineSiblings(
475 SCIP* scip, /**< SCIP data structure */
476 PHNODE** p, /**< the first sibling */
477 int size /**< the size of the heap */
478 )
479 {
480 PHNODE** treearray;
481 int i;
482 int j;
483 int nsiblings;
484 if( (*p)->sibling == NULL )
485 return SCIP_OKAY;
486
487 SCIP_CALL( SCIPallocBufferArray(scip, &treearray, size) );
488
489 /* store all siblings in an array */
490 for( nsiblings = 0; (*p) != NULL; nsiblings++ )
491 {
492 assert(size > nsiblings);
493 treearray[nsiblings] = (*p);
494 if( (*p)->prev != NULL )
495 (*p)->prev->sibling = NULL;
496 (*p) = (*p)->sibling;
497 }
498 assert(size > nsiblings);
499 treearray[nsiblings] = NULL;
500
501 /* combine the subtrees (two at a time) */
502 for( i = 0; i < nsiblings - 1; i += 2 )
503 {
504 treearray[i] = SCIPpairheapMergeheaps(scip, treearray[i], treearray[i + 1]);
505 }
506 j = i - 2;
507
508 /* if the number of trees is odd, get the last one */
509 if( j == nsiblings - 3 )
510 {
511 treearray[j] = SCIPpairheapMergeheaps(scip, treearray[j], treearray[j + 2]);
512 }
513
514 for( ; j >= 2; j -= 2 )
515 {
516 treearray[j - 2] = SCIPpairheapMergeheaps(scip, treearray[j - 2], treearray[j]);
517 }
518
519 (*p) = treearray[0];
520
521 SCIPfreeBufferArray(scip, &treearray);
522
523 return SCIP_OKAY;
524 }
525
526
527 /** inserts a new node into the pairing heap */
SCIPpairheapInsert(SCIP * scip,PHNODE ** root,int element,SCIP_Real key,int * size)528 SCIP_RETCODE SCIPpairheapInsert(
529 SCIP* scip, /**< SCIP data structure */
530 PHNODE** root, /**< pointer to root of the heap */
531 int element, /**< data of new node */
532 SCIP_Real key, /**< key of new node */
533 int* size /**< pointer to size of the heap */
534 )
535 {
536 if( (*root) == NULL )
537 {
538 (*size) = 1;
539 SCIP_CALL( SCIPallocBlockMemory(scip, root) );
540 (*root)->key = key;
541 (*root)->element = element;
542 (*root)->child = NULL;
543 (*root)->sibling = NULL;
544 (*root)->prev = NULL;
545 }
546 else
547 {
548 PHNODE* node;
549 (*size)++;
550 SCIP_CALL( SCIPallocBlockMemory(scip, &node) );
551 node->key = key;
552 node->element = element;
553 node->child = NULL;
554 node->sibling = NULL;
555 node->prev = NULL;
556 (*root) = SCIPpairheapAddtoheap(scip, (*root), node);
557 }
558 return SCIP_OKAY;
559 }
560
561 /** deletes the root of the paring heap, concomitantly storing its data and key in '*element' and '*key' respectively */
SCIPpairheapDeletemin(SCIP * scip,int * element,SCIP_Real * key,PHNODE ** root,int * size)562 SCIP_RETCODE SCIPpairheapDeletemin(
563 SCIP* scip, /**< SCIP data structure */
564 int* element, /**< data of the root */
565 SCIP_Real* key, /**< key of the root */
566 PHNODE** root, /**< pointer to root of the heap */
567 int* size /**< pointer to size of the heap */
568 )
569 {
570 assert(scip != NULL);
571 if( (*root) == NULL )
572 {
573 *element = -1;
574 return SCIP_OKAY;
575 }
576 else
577 {
578 PHNODE *newroot = NULL;
579
580 assert(key != NULL);
581 assert(size != NULL);
582
583 *element = (*root)->element;
584 *key = (*root)->key;
585 if( (*root)->child != NULL )
586 {
587 newroot = (*root)->child;
588 SCIP_CALL( pairheapCombineSiblings(scip, &newroot, (*size)--) );
589 }
590
591 SCIPfreeBlockMemory(scip, root);
592 (*root) = newroot;
593 }
594 return SCIP_OKAY;
595 }
596
597
598 /** links nodes 'root1' and 'root2' together, roots the resulting tree at root1 and sets root2 to NULL */
SCIPpairheapMeldheaps(SCIP * scip,PHNODE ** root1,PHNODE ** root2,int * sizeroot1,int * sizeroot2)599 void SCIPpairheapMeldheaps(
600 SCIP* scip, /**< SCIP data structure */
601 PHNODE** root1, /**< pointer to root of first heap */
602 PHNODE** root2, /**< pointer to root of second heap */
603 int* sizeroot1, /**< pointer to size of first heap */
604 int* sizeroot2 /**< pointer to size of second heap */
605 )
606 {
607 assert(scip != NULL);
608 assert(root1 != NULL);
609 assert(root2 != NULL);
610 assert(sizeroot1 != NULL);
611 assert(sizeroot2 != NULL);
612
613 if( *root1 == NULL && *root2 == NULL )
614 {
615 assert(*sizeroot1 == 0);
616 assert(*sizeroot2 == 0);
617 return;
618 }
619
620 (*root1) = SCIPpairheapMergeheaps(scip, *root1, *root2);
621 (*sizeroot1) += (*sizeroot2);
622 (*root2) = NULL;
623 }
624
625
626 /** frees the paring heap with root 'p' */
SCIPpairheapFree(SCIP * scip,PHNODE ** root)627 void SCIPpairheapFree(
628 SCIP* scip, /**< SCIP data structure */
629 PHNODE** root /**< root of heap to be freed */
630 )
631 {
632 if( (*root) == NULL )
633 {
634 return;
635 }
636 if( (*root)->sibling != NULL )
637 {
638 SCIPpairheapFree(scip, &((*root)->sibling));
639 }
640 if( (*root)->child != NULL )
641 {
642 SCIPpairheapFree(scip, &((*root)->child));
643 }
644
645 SCIPfreeBlockMemory(scip, root);
646 (*root) = NULL;
647
648 }
649
650
651 /** internal method used by 'pairheap_buffarr' */
652 static
pairheapRec(PHNODE * p,int ** arr,int * n)653 void pairheapRec(
654 PHNODE* p,
655 int** arr,
656 int* n
657 )
658 {
659 if( p == NULL )
660 {
661 return;
662 }
663 (*arr)[(*n)++] = p->element;
664 pairheapRec(p->sibling, arr, n);
665 pairheapRec(p->child, arr, n);
666 }
667
668
669 /** stores all elements of the pairing heap in an array */
SCIPpairheapBuffarr(SCIP * scip,PHNODE * root,int size,int ** elements)670 SCIP_RETCODE SCIPpairheapBuffarr(
671 SCIP* scip, /**< SCIP data structure */
672 PHNODE* root, /**< root of the heap */
673 int size, /**< size of the array */
674 int** elements /**< pointer to array */
675 )
676 {
677 int n = 0;
678 SCIP_CALL( SCIPallocBufferArray(scip, elements, size) );
679 pairheapRec(root, elements, &n);
680 return SCIP_OKAY;
681 }
682
683
684 /*
685 *Union-Find data structure
686 */
687
688 /** initializes the union-find structure 'uf' with 'length' many components (of size one) */
SCIPStpunionfindInit(SCIP * scip,UF * uf,int length)689 SCIP_RETCODE SCIPStpunionfindInit(
690 SCIP* scip, /**< SCIP data structure */
691 UF* uf, /**< union find data structure */
692 int length /**< number of components */
693 )
694 {
695 int i;
696 uf->count = length;
697 SCIP_CALL( SCIPallocMemoryArray(scip, &(uf->parent), length) );
698 SCIP_CALL( SCIPallocMemoryArray(scip, &(uf->size), length) );
699 for( i = 0; i < length; i++ ) {
700 uf->parent[i] = i;
701 uf->size[i] = 1;
702 }
703
704 return SCIP_OKAY;
705 }
706
707 /** clears the union-find structure 'uf'*/
SCIPStpunionfindClear(SCIP * scip,UF * uf,int length)708 void SCIPStpunionfindClear(
709 SCIP* scip, /**< SCIP data structure */
710 UF* uf, /**< union find data structure */
711 int length /**< number of components */
712 )
713 {
714 int i;
715 uf->count = length;
716
717 for( i = 0; i < length; i++ )
718 {
719 uf->parent[i] = i;
720 uf->size[i] = 1;
721 }
722
723 return;
724 }
725
726
727 /** finds and returns the component identifier */
SCIPStpunionfindFind(UF * uf,int element)728 int SCIPStpunionfindFind(
729 UF* uf, /**< union find data structure */
730 int element /**< element to be found */
731 )
732 {
733 int newelement;
734 int root = element;
735 int* parent = uf->parent;
736
737 while( root != parent[root] )
738 {
739 root = parent[root];
740 }
741
742 while( element != root )
743 {
744 newelement = parent[element];
745 parent[element] = root;
746 element = newelement;
747 }
748 return root;
749 }
750
751 /** merges the components containing p and q respectively */
SCIPStpunionfindUnion(UF * uf,int p,int q,SCIP_Bool compress)752 void SCIPStpunionfindUnion(
753 UF* uf, /**< union find data structure */
754 int p, /**< first component */
755 int q, /**< second component*/
756 SCIP_Bool compress /**< compress union find structure? */
757 )
758 {
759 int idp;
760 int idq;
761 int* size = uf->size;
762 int* parent = uf->parent;
763 idp = SCIPStpunionfindFind(uf, p);
764 idq = SCIPStpunionfindFind(uf, q);
765
766 /* if p and q lie in the same component, there is nothing to be done */
767 if( idp == idq )
768 return;
769
770 if( !compress )
771 {
772 parent[idq] = idp;
773 size[idp] += size[idq];
774 }
775 else
776 {
777 if( size[idp] < size[idq] )
778 {
779 parent[idp] = idq;
780 size[idq] += size[idp];
781 }
782 else
783 {
784 parent[idq] = idp;
785 size[idp] += size[idq];
786 }
787 }
788
789 /* one less component */
790 uf->count--;
791
792 }
793
794 /** frees the data fields of the union-find structure */
SCIPStpunionfindFree(SCIP * scip,UF * uf)795 void SCIPStpunionfindFree(
796 SCIP* scip, /**< SCIP data structure */
797 UF* uf /**< union find data structure */
798 )
799 {
800 SCIPfreeMemoryArray(scip, &uf->parent);
801 SCIPfreeMemoryArray(scip, &uf->size);
802 }
803