Scippy

SCIP

Solving Constraint Integer Programs

misc_stp.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 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 "probdata_stp.h"
35 #include "portab.h"
36 #include "misc_stp.h"
37 
38 
39 /** internal method for combining the siblings after the root has been deleted */
40 static
42  SCIP* scip, /**< SCIP data structure */
43  PHNODE** p, /**< the first sibling */
44  int size /**< the size of the heap */
45  )
46 {
47  PHNODE** treearray;
48  int i;
49  int j;
50  int nsiblings;
51  if( (*p)->sibling == NULL )
52  return SCIP_OKAY;
53 
54  SCIP_CALL( SCIPallocBufferArray(scip, &treearray, size) );
55 
56  /* store all siblings in an array */
57  for( nsiblings = 0; (*p) != NULL; nsiblings++ )
58  {
59  assert(size > nsiblings);
60  treearray[nsiblings] = (*p);
61  if( (*p)->prev != NULL )
62  (*p)->prev->sibling = NULL;
63  (*p) = (*p)->sibling;
64  }
65  assert(size > nsiblings);
66  treearray[nsiblings] = NULL;
67 
68  /* combine the subtrees (two at a time) */
69  for( i = 0; i < nsiblings - 1; i += 2 )
70  {
71  treearray[i] = SCIPpairheapMergeheaps(scip, treearray[i], treearray[i + 1]);
72  }
73  j = i - 2;
74 
75  /* if the number of trees is odd, get the last one */
76  if( j == nsiblings - 3 )
77  {
78  treearray[j] = SCIPpairheapMergeheaps(scip, treearray[j], treearray[j + 2]);
79  }
80 
81  for( ; j >= 2; j -= 2 )
82  {
83  treearray[j - 2] = SCIPpairheapMergeheaps(scip, treearray[j - 2], treearray[j]);
84  }
85 
86  (*p) = treearray[0];
87 
88  SCIPfreeBufferArray(scip, &treearray);
89 
90  return SCIP_OKAY;
91 }
92 
93 
94 /** add heap to heap */
95 static
97  SCIP* scip, /**< SCIP data structure */
98  PHNODE* root1, /**< pointer to root of first heap */
99  PHNODE* root2 /**< pointer to root of second heap */
100  )
101 {
102  assert(root2 != NULL);
103  assert(root1 != NULL);
104 
105  if( root1->key <= root2->key )
106  {
107  /* attach root2 as (the leftmost) child of root1 */
108  root2->prev = root1;
109  root1->sibling = root2->sibling;
110  /* @todo: should never happen */
111  if( root1->sibling != NULL )
112  {
113  root1->sibling->prev = root1;
114  }
115 
116  root2->sibling = root1->child;
117  if( root2->sibling != NULL )
118  root2->sibling->prev = root2;
119 
120  root1->child = root2;
121 
122  return root1;
123  }
124  else
125  {
126  /* attach root1 as (the leftmost) child of root2 */
127  root2->prev = root1->prev;
128  root1->prev = root2;
129  root1->sibling = root2->child;
130  if( root1->sibling != NULL )
131  root1->sibling->prev = root1;
132 
133  root2->child = root1;
134 
135  return root2;
136  }
137 }
138 
139 
140 /** returns maximum of given SCIP_Real values
141  * todo check whether this is really more efficient than a variadic function */
143  const SCIP_Real* realarr, /**< array of reals */
144  unsigned nreals /**< size of array of reals */
145  )
146 {
147  SCIP_Real max = realarr[0];
148 
149  assert(nreals >= 1);
150 
151  for( unsigned i = 1; i < nreals; i++ )
152  {
153  if( realarr[i] > max )
154  max = realarr[i];
155  }
156 
157  return max;
158 }
159 
160 /** compares distances of two GNODE structures */
162 {
163  SCIP_Real first = ((GNODE*)elem1)->dist;
164  SCIP_Real second = ((GNODE*)elem2)->dist;
165  if( LT(first,second) )
166  {
167  return -1;
168  }
169  else if( EQ(first, second) ) /* first == second */
170  {
171  return 0;
172  }
173  else
174  {
175  return 1;
176  }
177 }
178 
179 /** insert a new node */
181  SCIP* scip, /**< SCIP data structure */
182  IDX** node, /**< pointer to the last list node */
183  int nodeval /**< data of the new node */
184  )
185 {
186  IDX* curr;
187  curr = *node;
188 
189  SCIP_CALL( SCIPallocBlockMemory(scip, node) );
190  (*node)->index = nodeval;
191  (*node)->parent = (curr);
192 
193  return SCIP_OKAY;
194 }
195 
196 /** append copy of list pertaining to node2 to node1 */
198  SCIP* scip, /**< SCIP data structure */
199  IDX** node1, /**< pointer to the last node of list to be enlarged */
200  IDX* node2, /**< pointer to the last node of source list */
201  SCIP_Bool* conflict /**< pointer to store whether a conflict has been detected by the method */
202  )
203 {
204  IDX* new;
205  IDX* curr1;
206  IDX* curr2;
207  int curr2idx;
208  SCIP_Bool checkconflict;
209 
210  assert(scip != NULL);
211 
212  if( node2 == NULL )
213  return SCIP_OKAY;
214 
215  if( conflict != NULL )
216  {
217  *conflict = FALSE;
218  checkconflict = TRUE;
219  }
220  else
221  {
222  checkconflict = FALSE;
223  }
224 
225  new = NULL;
226  curr1 = *node1;
227  curr2 = node2;
228 
229  if( curr1 != NULL )
230  {
231  int* pointer;
232  int* hasharr;
233  int i;
234  int nelems = 0;
235  const SCIP_Bool ignoreconflicts = (SCIPprobdataGetType(scip) == STP_SPG);
236 
237  if( !ignoreconflicts )
238  {
239  /* todo fix this hack; don't check at all, but just add */
240  const int maxlength = SCIPprobdataGetNorgEdges(scip);
241 
242  assert(maxlength > 0);
243 
244  SCIP_CALL(SCIPallocCleanBufferArray(scip, &hasharr, maxlength));
245  SCIP_CALL(SCIPallocCleanBufferArray(scip, &pointer, maxlength));
246  while( curr1 != NULL )
247  {
248  i = curr1->index;
249  assert(i < maxlength && nelems < maxlength);
250  pointer[nelems++] = i;
251  hasharr[i] = 1;
252  curr1 = curr1->parent;
253  }
254  }
255 
256  curr1 = *node1;
257  while( curr2 != NULL )
258  {
259  curr2idx = curr2->index;
260 
261  if( ignoreconflicts || hasharr[curr2idx] == 0 )
262  {
263  SCIP_CALL( SCIPallocBlockMemory(scip, &new) );
264  new->index = curr2idx;
265  new->parent = curr1;
266  curr1 = new;
267  }
268  else if( checkconflict )
269  {
270  assert(conflict != NULL);
271  (*conflict) = TRUE;
272  }
273 
274  curr2 = curr2->parent;
275  }
276 
277  if( !ignoreconflicts )
278  {
279  for( i = 0; i < nelems; i++ )
280  {
281  hasharr[pointer[i]] = 0;
282  pointer[i] = 0;
283  }
284  SCIPfreeCleanBufferArray(scip, &pointer);
285  SCIPfreeCleanBufferArray(scip, &hasharr);
286  }
287  }
288  else
289  {
290  while( curr2 != NULL )
291  {
292  SCIP_CALL( SCIPallocBlockMemory(scip, &new) );
293  new->index = curr2->index;
294  new->parent = curr1;
295  curr1 = new;
296 
297  curr2 = curr2->parent;
298  }
299  }
300 
301  if( new != NULL )
302  *node1 = new;
303 
304  return SCIP_OKAY;
305 }
306 
307 
308 /** append list pertaining to node2 to (non-empty!) node1 */
310  IDX* node1, /**< pointer to the last node of non-empty list to be enlarged */
311  IDX* node2 /**< pointer to the last node of source list */
312  )
313 {
314  IDX* curr = node1;
315  assert(node1);
316 
317  while( curr->parent )
318  curr = curr->parent;
319 
320  curr->parent = node2;
321 }
322 
323 
324 /** free list */
326  SCIP* scip, /**< SCIP data structure */
327  IDX** node /**< pointer to the last list node */
328  )
329 {
330  IDX* curr;
331  curr = *node;
332 
333  while( curr != NULL )
334  {
335  *node = curr->parent;
336  SCIPfreeBlockMemory(scip, &curr);
337  curr = *node;
338  }
339  assert(*node == NULL);
340 }
341 
342 /*
343  * Linear Link Cut Tree
344  */
345 
346 /** inits a node, setting 'parent' and 'edge' to its default values */
348  LCNODE* v /**< pointer to node */
349  )
350 {
351  v->parent = -1;
352  v->edge = -1;
353 }
354 
355 
356 /** renders v a child of w; v has to be the root index of its tree */
358  LCNODE* tree, /**< the tree */
359  int v, /**< pointer to node representing the tree */
360  int w, /**< pointer to node of another tree */
361  int edge /**< link edge */
362  )
363 {
364  assert(tree[v].parent == -1);
365  assert(tree[v].edge == -1);
366  tree[v].parent = w;
367  tree[v].edge = edge;
368 }
369 
370 
371 /** cut tree at given node */
373  LCNODE* v /**< node to cut at */
374  )
375 {
376  v->edge = -1;
377  v->parent = -1;
378 }
379 
380 /** finds minimum weight chain between node 'start' and distinct root node **/
382  SCIP* scip, /**< SCIP data structure */
383  const LCNODE* tree, /**< tree */
384  const SCIP_Real* nodeweight, /**< node weight array */
385  const int* heads, /**< head of an arc */
386  const int* stdeg, /**< degree in Steiner tree */
387  const SCIP_Bool* nodeIsBlocked, /**< has node been blocked? */
388  int start, /**< the node to start at */
389  int* first, /**< first node of chain */
390  int* last /**< last node of chain */
391  )
392 {
393  int tmpfirst = -1;
394  SCIP_Real min = 0.0;
395  SCIP_Real tmpmin = 0.0;
396  SCIP_Bool stopped = TRUE;
397 
398  assert(scip && heads && nodeweight && nodeIsBlocked && stdeg && first && last);
399 
400  *first = -1;
401  *last = -1;
402 
403  /* while curr is not root */
404  for( int curr = start; tree[curr].parent != -1; curr = tree[curr].parent )
405  {
406  int head;
407  const SCIP_Bool headIsRoot = (tree[tree[curr].parent].parent == -1);
408 
409  assert(tree[curr].edge >= 0);
410 
411  head = heads[tree[curr].edge];
412 
413  if( stdeg[head] == 2 && nodeweight[head] < 0.0 && !headIsRoot && !nodeIsBlocked[head] )
414  {
415  if( stopped )
416  {
417  stopped = FALSE;
418  tmpmin = 0.0;
419  tmpfirst = curr;
420  }
421 
422  tmpmin += nodeweight[head];
423  }
424  else
425  {
426  /* better chain found? */
427  if( !stopped && SCIPisLT(scip, tmpmin, min) )
428  {
429  assert(tmpfirst != -1);
430  min = tmpmin;
431  *first = tmpfirst;
432  *last = curr;
433  }
434 
435  stopped = TRUE;
436  }
437  }
438 
439  return min;
440 }
441 
442 
443 /** Finds maximum weight chain between node 'start' and distinct root node and returns cost.
444  ** Note: 'last' is the tail of the last edge of the chain. So if 'last' and 'first' coincide, the chain is an edge. */
446  SCIP* scip, /**< SCIP data structure */
447  const LCNODE* tree, /**< tree */
448  const SCIP_Real* edgecosts, /**< edge cost array */
449  const SCIP_Real* prizes, /**< node weight array for PC/RPC */
450  const int* heads, /**< head of an arc */
451  const int* nonTermDeg, /**< degree in Steiner tree, or UNKNOWN if vertex is terminal */
452  const SCIP_Bool* nodeIsBlocked, /**< has node been blocked? */
453  int start, /**< the node to start at (NOT the root!) */
454  int* first, /**< first node of chain */
455  int* last /**< last node of chain */
456  )
457 {
458  int tmpfirst = -1;
459  SCIP_Real max;
460  SCIP_Real tmpmax;
461  SCIP_Bool reset_chain;
462  const SCIP_Bool withPrize = (prizes != NULL);
463 
464  assert(tree && edgecosts && heads && nonTermDeg && first && last && nodeIsBlocked);
465  assert(tree[start].parent != -1); /* start should not be the root */
466  assert(tree[start].edge >= 0);
467 
468  *first = -1;
469  *last = -1;
470 
471  max = -1.0;
472  tmpmax = 0.0;
473  reset_chain = TRUE;
474 
475  /* while curr is not root */
476  for( int curr = start; tree[curr].parent != -1; curr = tree[curr].parent )
477  {
478  int head;
479  const int edge = tree[curr].edge;
480  const SCIP_Bool headIsRoot = (tree[tree[curr].parent].parent == -1);
481 
482  assert(edge >= 0);
483 
484  /* is the current node the last one of a chain? */
485  if( reset_chain )
486  {
487  tmpfirst = curr;
488  tmpmax = 0.0;
489  }
490 
491  assert(SCIPisGE(scip, tmpmax, 0.0));
492 
493  tmpmax += edgecosts[edge];
494 
495  head = heads[edge];
496 
497  /* is head of degree 2, allowed, and not the root? */
498  if( nonTermDeg[head] == 2 && !nodeIsBlocked[head] && !headIsRoot )
499  {
500  reset_chain = FALSE;
501 
502  if( withPrize )
503  {
504  assert(SCIPisGE(scip, edgecosts[edge], prizes[head]));
505  tmpmax -= prizes[head];
506  }
507  }
508  else
509  {
510  /* better chain found? */
511  if( tmpmax > max )
512  {
513  assert(tmpfirst != -1 && curr != -1);
514 
515  max = tmpmax;
516  *first = tmpfirst;
517  *last = curr;
518  }
519 
520  reset_chain = TRUE;
521  }
522  }
523 
524  assert(max > -0.5);
525  assert(*last != -1 && *first != -1);
526 
527  return max;
528 }
529 
530 
531 /** finds the max edge value between node 'v' and the root of the tree
532  * Returns index of node that has this edge */
534  const LCNODE* tree, /**< tree */
535  const SCIP_Real* cost, /**< edge cost array */
536  int v /**< the node */
537  )
538 {
539  int p = v;
540  int q = v;
541  SCIP_Real max = -1.0;
542 
543  /* while p is not the root */
544  while( tree[p].parent != -1 )
545  {
546  assert(tree[p].edge >= 0);
547  if( GE(cost[tree[p].edge], max) )
548  {
549  max = cost[tree[p].edge];
550  q = p;
551  }
552  p = tree[p].parent;
553  }
554 
555  return q;
556 }
557 
558 /** makes vertex v the root of the link cut tree */
560  LCNODE* RESTRICT tree, /**< tree */
561  int root_new /**< the vertex to become the root */
562  )
563 {
564  int p = -1;
565  int q = root_new;
566  int edge = -1;
567 
568  while( q != -1 )
569  {
570  const int tmpedge = tree[q].edge;
571  const int r = tree[q].parent;
572 
573  if( edge != -1 )
574  tree[q].edge = flipedge(edge);
575  else
576  tree[q].edge = -1;
577 
578  edge = tmpedge;
579  tree[q].parent = p;
580  p = q;
581  q = r;
582  }
583 }
584 
585 
586 
587 /*
588  * Pairing Heap
589  */
590 
591 /** links nodes 'root1' and 'root2' together */
593  SCIP* scip, /**< SCIP data structure */
594  PHNODE *root1, /**< pointer to root of first heap */
595  PHNODE *root2 /**< pointer to root of second heap */
596  )
597 {
598  if( root2 == NULL )
599  return root1;
600  if( root1 == NULL )
601  return root2;
602 
603  if( root1->key <= root2->key )
604  {
605  /* attach root2 as (the leftmost) child of root1 */
606  root2->prev = root1;
607  root1->sibling = root2->sibling;
608  if( root1->sibling != NULL )
609  root1->sibling->prev = root1;
610 
611  root2->sibling = root1->child;
612  if( root2->sibling != NULL )
613  root2->sibling->prev = root2;
614 
615  root1->child = root2;
616 
617  return root1;
618  }
619  else
620  {
621  /* attach root1 as (the leftmost) child of root2 */
622  root2->prev = root1->prev;
623  root1->prev = root2;
624  root1->sibling = root2->child;
625  if( root1->sibling != NULL )
626  root1->sibling->prev = root1;
627 
628  root2->child = root1;
629 
630  return root2;
631  }
632 }
633 
634 
635 /** inserts a new node into the pairing heap */
637  SCIP* scip, /**< SCIP data structure */
638  PHNODE** root, /**< pointer to root of the heap */
639  PHNODE* pheapelems, /**< data array */
640  int element, /**< data of new node */
641  SCIP_Real key, /**< key of new node */
642  int* size /**< pointer to size of the heap */
643  )
644 {
645  assert(pheapelems[element].element == -1);
646 
647  if( (*root) == NULL )
648  {
649  (*size) = 1;
650  pheapelems[element].key = key;
651  pheapelems[element].element = element;
652  pheapelems[element].child = NULL;
653  pheapelems[element].sibling = NULL;
654  pheapelems[element].prev = NULL;
655  *root = &(pheapelems[element]);
656  }
657  else
658  {
659  (*size)++;
660  pheapelems[element].key = key;
661  pheapelems[element].element = element;
662  pheapelems[element].child = NULL;
663  pheapelems[element].sibling = NULL;
664  pheapelems[element].prev = NULL;
665  (*root) = pairheapAddtoHeap(scip, (*root), &pheapelems[element]);
666  }
667  return SCIP_OKAY;
668 }
669 
670 /** deletes the root of the paring heap, concomitantly storing its data and key in '*element' and '*key' respectively */
672  SCIP* scip, /**< SCIP data structure */
673  int* element, /**< data of the root */
674  SCIP_Real* key, /**< key of the root */
675  PHNODE** root, /**< pointer to root of the heap */
676  int* size /**< pointer to size of the heap */
677  )
678 {
679  assert(scip != NULL);
680  if( (*root) == NULL )
681  {
682  *element = -1;
683  return SCIP_OKAY;
684  }
685  else
686  {
687  PHNODE *newroot = NULL;
688 
689  assert(key != NULL);
690  assert(size != NULL);
691 
692  *element = (*root)->element;
693  *key = (*root)->key;
694  if( (*root)->child != NULL )
695  {
696  newroot = (*root)->child;
697  SCIP_CALL( pairheapCombineSiblings(scip, &newroot, (*size)--) );
698  }
699 
700  (*root)->element = -1;
701  (*root) = newroot;
702  }
703  return SCIP_OKAY;
704 }
705 
706 
707 /** links nodes 'root1' and 'root2' together, roots the resulting tree at root1 and sets root2 to NULL */
709  SCIP* scip, /**< SCIP data structure */
710  PHNODE** root1, /**< pointer to root of first heap */
711  PHNODE** root2, /**< pointer to root of second heap */
712  int* sizeroot1, /**< pointer to size of first heap */
713  int* sizeroot2 /**< pointer to size of second heap */
714  )
715 {
716  assert(scip != NULL);
717  assert(root1 != NULL);
718  assert(root2 != NULL);
719  assert(sizeroot1 != NULL);
720  assert(sizeroot2 != NULL);
721 
722  if( *root1 == NULL && *root2 == NULL )
723  {
724  assert(*sizeroot1 == 0);
725  assert(*sizeroot2 == 0);
726  return;
727  }
728 
729  (*root1) = SCIPpairheapMergeheaps(scip, *root1, *root2);
730  (*sizeroot1) += (*sizeroot2);
731  (*root2) = NULL;
732 }
733 
734 
735 /** frees the paring heap with root 'p' */
737  SCIP* scip, /**< SCIP data structure */
738  PHNODE** root /**< root of heap to be freed */
739  )
740 {
741  if( (*root) == NULL )
742  {
743  return;
744  }
745  if( (*root)->sibling != NULL )
746  {
747  SCIPpairheapFree(scip, &((*root)->sibling));
748  }
749  if( (*root)->child != NULL )
750  {
751  SCIPpairheapFree(scip, &((*root)->child));
752  }
753 
754  (*root)->element = -1;
755  (*root) = NULL;
756 }
757 
758 
759 
760 /** stores all elements of the pairing heap in an array */
762  SCIP* scip, /**< SCIP data structure */
763  const PHNODE* root, /**< root of the heap */
764  int size, /**< size of the array */
765  int** elements /**< pointer to array (will be allocated) */
766  )
767 {
768  int* RESTRICT arr;
769  const PHNODE** stack;
770  int n = 0;
771  int stacksize = 0;
772 
773  if( size == 0 )
774  {
775  *elements = NULL;
776  return SCIP_OKAY;
777  }
778 
779  assert(root);
780  assert(size > 0);
781 
782  SCIP_CALL( SCIPallocBufferArray(scip, elements, size) );
783  SCIP_CALL( SCIPallocBufferArray(scip, &stack, size) );
784 
785  arr = *elements;
786  stack[stacksize++] = root;
787 
788  while( stacksize > 0 )
789  {
790  const PHNODE* const p = stack[--stacksize];
791  arr[n++] = p->element;
792 
793  if( p->sibling )
794  {
795  assert(stacksize < size);
796  stack[stacksize++] = p->sibling;
797  }
798 
799  if( p->child )
800  {
801  assert(stacksize < size);
802  stack[stacksize++] = p->child;
803  }
804  }
805 
806  SCIPfreeBufferArray(scip, &stack);
807 
808  return SCIP_OKAY;
809 }
810 
811 
812 /*
813  *Union-Find data structure
814  */
815 
816 /** initializes the union-find structure 'uf' with 'length' many components (of size one) */
818  SCIP* scip, /**< SCIP data structure */
819  UF* uf, /**< union find data structure */
820  int length /**< number of elements */
821  )
822 {
823  assert(length > 0);
824 
825  uf->nComponents = length;
826  uf->nElements = length;
827 
828  SCIP_CALL( SCIPallocMemoryArray(scip, &(uf->parent), length) );
829  SCIP_CALL( SCIPallocMemoryArray(scip, &(uf->size), length) );
830 
831  for( int i = 0; i < length; i++ )
832  {
833  uf->parent[i] = i;
834  uf->size[i] = 1;
835  }
836 
837  return SCIP_OKAY;
838 }
839 
840 /** clears the union-find structure 'uf'*/
842  SCIP* scip, /**< SCIP data structure */
843  UF* uf /**< union find data structure */
844  )
845 {
846  const int length = uf->nElements;
847 
848  uf->nComponents = length;
849 
850  for( int i = 0; i < length; i++ )
851  {
852  uf->parent[i] = i;
853  uf->size[i] = 1;
854  }
855 
856  return;
857 }
858 
859 
860 /** is the union-find structure 'uf' clear? */
862  SCIP* scip, /**< SCIP data structure */
863  const UF* uf /**< union find data structure */
864  )
865 {
866  const int length = uf->nElements;
867 
868  if( uf->nComponents != length )
869  return FALSE;
870 
871  for( int i = 0; i < length; i++ )
872  {
873  if( uf->parent[i] != i )
874  return FALSE;
875 
876  if( uf->size[i] != 1 )
877  return FALSE;
878  }
879 
880  return TRUE;
881 }
882 
883 
884 /** finds and returns the component identifier */
886  UF* uf, /**< union find data structure */
887  int element /**< element to be found */
888  )
889 {
890  int newelement;
891  int root = element;
892  int* parent = uf->parent;
893 
894  assert(element >= 0 && element < uf->nElements);
895 
896  while( root != parent[root] )
897  {
898  root = parent[root];
899  }
900 
901  while( element != root )
902  {
903  newelement = parent[element];
904  parent[element] = root;
905  element = newelement;
906  }
907  return root;
908 }
909 
910 /** Merges the components containing p and q respectively.
911  * Identifier of 'p' will always be used if 'compress' is FALSE. */
913  UF* uf, /**< union find data structure */
914  int p, /**< first component */
915  int q, /**< second component */
916  SCIP_Bool compress /**< compress union find structure? */
917  )
918 {
919  int idp;
920  int idq;
921  int* size = uf->size;
922  int* parent = uf->parent;
923  idp = SCIPStpunionfindFind(uf, p);
924  idq = SCIPStpunionfindFind(uf, q);
925 
926  /* if p and q lie in the same component, there is nothing to be done */
927  if( idp == idq )
928  return;
929 
930  if( !compress )
931  {
932  parent[idq] = idp;
933  size[idp] += size[idq];
934  }
935  else
936  {
937  if( size[idp] < size[idq] )
938  {
939  parent[idp] = idq;
940  size[idq] += size[idp];
941  }
942  else
943  {
944  parent[idq] = idp;
945  size[idp] += size[idq];
946  }
947  }
948 
949  /* one less component */
950  uf->nComponents--;
951 
952 }
953 
954 /** frees the data fields of the union-find structure */
956  SCIP* scip, /**< SCIP data structure */
957  UF* uf /**< union find data structure */
958  )
959 {
960  uf->nElements = 0;
961  uf->nComponents = 0;
962 
963  SCIPfreeMemoryArray(scip, &uf->parent);
964  SCIPfreeMemoryArray(scip, &uf->size);
965 }
SCIP_Real SCIPlinkcuttreeFindMinChainMw(SCIP *scip, const LCNODE *tree, const SCIP_Real *nodeweight, const int *heads, const int *stdeg, const SCIP_Bool *nodeIsBlocked, int start, int *first, int *last)
Definition: misc_stp.c:381
SCIP_Real SCIPlinkcuttreeFindMaxChain(SCIP *scip, const LCNODE *tree, const SCIP_Real *edgecosts, const SCIP_Real *prizes, const int *heads, const int *nonTermDeg, const SCIP_Bool *nodeIsBlocked, int start, int *first, int *last)
Definition: misc_stp.c:445
SCIP_RETCODE SCIPStpunionfindInit(SCIP *scip, UF *uf, int length)
Definition: misc_stp.c:817
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
void SCIPStpunionfindClear(SCIP *scip, UF *uf)
Definition: misc_stp.c:841
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void SCIPpairheapMeldheaps(SCIP *scip, PHNODE **root1, PHNODE **root2, int *sizeroot1, int *sizeroot2)
Definition: misc_stp.c:708
struct PHeap_Node * sibling
Definition: misc_stp.h:99
#define FALSE
Definition: def.h:87
int SCIPlinkcuttreeFindMax(const LCNODE *tree, const SCIP_Real *cost, int v)
Definition: misc_stp.c:533
Problem data for stp problem.
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
struct PHeap_Node * child
Definition: misc_stp.h:98
SCIP_RETCODE SCIPpairheapDeletemin(SCIP *scip, int *element, SCIP_Real *key, PHNODE **root, int *size)
Definition: misc_stp.c:671
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
#define STP_SPG
Definition: graphdefs.h:42
void SCIPpairheapFree(SCIP *scip, PHNODE **root)
Definition: misc_stp.c:736
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_Real miscstp_maxReal(const SCIP_Real *realarr, unsigned nreals)
Definition: misc_stp.c:142
void SCIPlinkcuttreeEvert(LCNODE *RESTRICT tree, int root_new)
Definition: misc_stp.c:559
void SCIPintListNodeFree(SCIP *scip, IDX **node)
Definition: misc_stp.c:325
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:133
static SCIP_RETCODE pairheapCombineSiblings(SCIP *scip, PHNODE **p, int size)
Definition: misc_stp.c:41
SCIP_VAR * w
Definition: circlepacking.c:58
#define GE(a, b)
Definition: portab.h:85
void SCIPlinkcuttreeInitNode(LCNODE *v)
Definition: misc_stp.c:347
SCIP_DECL_SORTPTRCOMP(GNODECmpByDist)
Definition: misc_stp.c:161
miscellaneous methods used for solving Steiner problems
SCIP_RETCODE SCIPintListNodeAppendCopy(SCIP *scip, IDX **node1, IDX *node2, SCIP_Bool *conflict)
Definition: misc_stp.c:197
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPpairheapInsert(SCIP *scip, PHNODE **root, PHNODE *pheapelems, int element, SCIP_Real key, int *size)
Definition: misc_stp.c:636
#define NULL
Definition: lpi_spx1.cpp:155
#define EQ(a, b)
Definition: portab.h:79
#define SCIP_CALL(x)
Definition: def.h:384
void SCIPlinkcuttreeCutNode(LCNODE *v)
Definition: misc_stp.c:372
void SCIPStpunionfindUnion(UF *uf, int p, int q, SCIP_Bool compress)
Definition: misc_stp.c:912
int SCIPStpunionfindFind(UF *uf, int element)
Definition: misc_stp.c:885
Definition: graph_load.c:93
#define LT(a, b)
Definition: portab.h:81
int SCIPprobdataGetType(SCIP *scip)
int GNODECmpByDist(void *first_arg, void *second_arg)
SCIP_RETCODE SCIPintListNodeInsert(SCIP *scip, IDX **node, int nodeval)
Definition: misc_stp.c:180
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define SCIP_Bool
Definition: def.h:84
void SCIPintListNodeAppend(IDX *node1, IDX *node2)
Definition: misc_stp.c:309
#define flipedge(edge)
Definition: graphdefs.h:84
static PHNODE * pairheapAddtoHeap(SCIP *scip, PHNODE *root1, PHNODE *root2)
Definition: misc_stp.c:96
void SCIPlinkcuttreeLink(LCNODE *tree, int v, int w, int edge)
Definition: misc_stp.c:357
SCIP_Real key
Definition: misc_stp.h:101
Portable definitions.
PHNODE * SCIPpairheapMergeheaps(SCIP *scip, PHNODE *root1, PHNODE *root2)
Definition: misc_stp.c:592
SCIP_Real * r
Definition: circlepacking.c:50
struct PHeap_Node * prev
Definition: misc_stp.h:100
int element
Definition: misc_stp.h:102
int SCIPprobdataGetNorgEdges(SCIP *scip)
#define SCIP_Real
Definition: def.h:177
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:137
SCIP_RETCODE SCIPpairheapBuffarr(SCIP *scip, const PHNODE *root, int size, int **elements)
Definition: misc_stp.c:761
SCIP_Bool SCIPStpunionfindIsClear(SCIP *scip, const UF *uf)
Definition: misc_stp.c:861
SCIPallocBlockMemory(scip, subsol))
struct Int_List_Node * parent
Definition: misc_stp.h:91
void SCIPStpunionfindFreeMembers(SCIP *scip, UF *uf)
Definition: misc_stp.c:955