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-2020 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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 **/
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 **/
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 */
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 */
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 */
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
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 */
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 */
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 */
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' */
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
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 */
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) */
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'*/
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 */
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 */
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 */
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 }
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPStpunionfindInit(SCIP *scip, UF *uf, int length)
Definition: misc_stp.c:689
SCIP_Real SCIPlinkcuttreeFindMinChain(SCIP *scip, const SCIP_Real *nodeweight, const int *head, const int *stdeg, const NODE *start, NODE **first, NODE **last)
Definition: misc_stp.c:258
SCIP_Real misc_stp_maxReal(SCIP_Real *realarr, unsigned nreals)
Definition: misc_stp.c:41
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:69
struct ST_Node * parent
Definition: misc_stp.h:60
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:53
void SCIPpairheapMeldheaps(SCIP *scip, PHNODE **root1, PHNODE **root2, int *sizeroot1, int *sizeroot2)
Definition: misc_stp.c:599
struct PHeap_Node * sibling
Definition: misc_stp.h:85
#define FALSE
Definition: def.h:73
Problem data for stp problem.
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
struct PHeap_Node * child
Definition: misc_stp.h:84
PHNODE * SCIPpairheapAddtoheap(SCIP *scip, PHNODE *root1, PHNODE *root2)
Definition: misc_stp.c:429
SCIP_RETCODE SCIPpairheapDeletemin(SCIP *scip, int *element, SCIP_Real *key, PHNODE **root, int *size)
Definition: misc_stp.c:562
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
void SCIPpairheapFree(SCIP *scip, PHNODE **root)
Definition: misc_stp.c:627
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
NODE * SCIPlinkcuttreeFindMax(SCIP *scip, const SCIP_Real *cost, NODE *v)
Definition: misc_stp.c:327
void SCIPintListNodeFree(SCIP *scip, IDX **node)
Definition: misc_stp.c:205
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:129
static SCIP_RETCODE pairheapCombineSiblings(SCIP *scip, PHNODE **p, int size)
Definition: misc_stp.c:474
SCIP_VAR * w
Definition: circlepacking.c:58
SCIP_DECL_SORTPTRCOMP(GNODECmpByDist)
Definition: misc_stp.c:58
SCIP_RETCODE SCIPintListNodeAppendCopy(SCIP *scip, IDX **node1, IDX *node2, SCIP_Bool *conflict)
Definition: misc_stp.c:94
int edge
Definition: misc_stp.h:59
internal miscellaneous methods
#define NULL
Definition: lpi_spx1.cpp:155
void SCIPStpunionfindClear(SCIP *scip, UF *uf, int length)
Definition: misc_stp.c:708
#define EQ(a, b)
Definition: portab.h:62
#define SCIP_CALL(x)
Definition: def.h:364
void SCIPStpunionfindUnion(UF *uf, int p, int q, SCIP_Bool compress)
Definition: misc_stp.c:752
int SCIPStpunionfindFind(UF *uf, int element)
Definition: misc_stp.c:728
Definition: grphload.c:88
#define LT(a, b)
Definition: portab.h:64
void SCIPlinkcuttreeInit(NODE *v)
Definition: misc_stp.c:227
void SCIPlinkcuttreeEvert(NODE *v)
Definition: misc_stp.c:352
int SCIPprobdataGetType(SCIP *scip)
int GNODECmpByDist(void *first_arg, void *second_arg)
#define STP_SPG
Definition: grph.h:38
SCIP_RETCODE SCIPintListNodeInsert(SCIP *scip, IDX **node, int nodeval)
Definition: misc_stp.c:77
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
void SCIPlinkcuttreeLink(NODE *v, NODE *w, int edge)
Definition: misc_stp.c:236
#define SCIP_Bool
Definition: def.h:70
SCIP_Real key
Definition: misc_stp.h:83
Portable defintions.
PHNODE * SCIPpairheapMergeheaps(SCIP *scip, PHNODE *root1, PHNODE *root2)
Definition: misc_stp.c:386
SCIP_Real * r
Definition: circlepacking.c:50
SCIP_RETCODE SCIPpairheapInsert(SCIP *scip, PHNODE **root, int element, SCIP_Real key, int *size)
Definition: misc_stp.c:528
struct PHeap_Node * prev
Definition: misc_stp.h:86
int element
Definition: misc_stp.h:82
int SCIPprobdataGetNorgEdges(SCIP *scip)
void SCIPlinkcuttreeCut(NODE *v)
Definition: misc_stp.c:249
void SCIPStpunionfindFree(SCIP *scip, UF *uf)
Definition: misc_stp.c:795
#define SCIP_Real
Definition: def.h:163
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:133
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
shortest paths based primal heuristics for Steiner problems
#define flipedge(edge)
Definition: grph.h:150
SCIP_RETCODE SCIPpairheapBuffarr(SCIP *scip, PHNODE *root, int size, int **elements)
Definition: misc_stp.c:670
struct Int_List_Node * parent
Definition: misc_stp.h:76
static void pairheapRec(PHNODE *p, int **arr, int *n)
Definition: misc_stp.c:653