SCIP

Solving Constraint Integer Programs

graph_vnoi.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 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file graph_vnoi.c
17  * @brief Voronoi graph algorithms for Steiner problems
18  * @author Daniel Rehfeldt
19  *
20  * This file encompasses various Voronoi diagram algorithms.
21  *
22  */
23
24 #include <stdlib.h>
25 #include <stdio.h>
26 #include <stddef.h>
27 #include <assert.h>
28 #include "portab.h"
29 #include "graph.h"
30 #include "reduce.h"
31
32
33 /* todo deprecated replace */
34 inline static
35 void correct(
36  int* RESTRICT heap,
37  int* RESTRICT state,
38  int* RESTRICT count, /* pointer to store the number of elements on the heap */
39  PATH* RESTRICT path,
40  int l,
41  int k,
42  int e,
43  SCIP_Real cost)
44 {
45  int t;
46  int c;
47  int j;
48
49  path[l].dist = path[k].dist + cost;
50  path[l].edge = e;
51
52  /* new node? */
53  if( state[l] == UNKNOWN )
54  {
55  heap[++(*count)] = l;
56  state[l] = (*count);
57  }
58
59  /* Heap shift up */
60  j = state[l];
61  c = j / 2;
62  while( (j > 1) && path[heap[c]].dist > path[heap[j]].dist )
63  {
64  t = heap[c];
65  heap[c] = heap[j];
66  heap[j] = t;
67  state[heap[j]] = j;
68  state[heap[c]] = c;
69  j = c;
70  c = j / 2;
71  }
72 }
73
74 /* todo deprecated, replace */
75 inline static
76 int nearest(
77  int* RESTRICT heap,
78  int* RESTRICT state,
79  int* RESTRICT count, /* pointer to store the number of elements on the heap */
80  const PATH* path)
81 {
82  int k;
83  int t;
84  int c;
85  int j;
86  k = heap[1];
87  j = 1;
88  c = 2;
89  heap[1] = heap[(*count)--];
90  state[heap[1]] = 1;
91
92  if ((*count) > 2)
93  if (LT(path[heap[3]].dist, path[heap[2]].dist))
94  c++;
95
96  while((c <= (*count)) && GT(path[heap[j]].dist, path[heap[c]].dist))
97  {
98  t = heap[c];
99  heap[c] = heap[j];
100  heap[j] = t;
101  state[heap[j]] = j;
102  state[heap[c]] = c;
103  j = c;
104  c += c;
105
106  if ((c + 1) <= (*count))
107  if (LT(path[heap[c + 1]].dist, path[heap[c]].dist))
108  c++;
109  }
110  return(k);
111 }
112
113
114 /** initializes */
115 static
116 void vnoiInit(
117  const GRAPH* g, /**< graph data structure */
118  DHEAP* dheap, /**< heap */
119  VNOI* vnoi /**< vnoi data structure */
120 )
121 {
122  const int nnodes = graph_get_nNodes(g);
123  SCIP_Real* RESTRICT nodes_dist = vnoi->nodes_dist;
124  int* RESTRICT nodes_pred = vnoi->nodes_predEdge;
125  int* RESTRICT nodes_base = vnoi->nodes_base;
126
127  assert(graph_heap_isClean(dheap));
128
129  for( int i = 0; i < nnodes; i++ )
130  {
131  assert(UNKNOWN == dheap->position[i]);
132
133  if( Is_term(g->term[i]) )
134  {
135  nodes_base[i] = i;
136  nodes_dist[i] = 0.0;
137
138  graph_heap_correct(i, 0.0, dheap);
139  }
140  else
141  {
142  nodes_base[i] = UNKNOWN;
143  nodes_dist[i] = FARAWAY;
144  }
145
146  nodes_pred[i] = UNKNOWN;
147  }
148 }
149
150
151 /** builds a Voronoi region w.r.t. shortest paths for all terminals */
152 static
154  SCIP* scip, /**< SCIP data structure */
155  const GRAPH* g, /**< graph data structure */
156  DHEAP* dheap, /**< heap */
157  VNOI* vnoi /**< Voronoi data structure */
158  )
159 {
160  SCIP_Real* RESTRICT nodes_dist = vnoi->nodes_dist;
161  int* RESTRICT nodes_pred = vnoi->nodes_predEdge;
162  int* RESTRICT nodes_base = vnoi->nodes_base;
163  int* const state = dheap->position;
164  const SCIP_Real* const gCost = g->cost;
165  const int* const gOeat = g->oeat;
167
168  assert(dheap->size > 0);
169  assert(graph_get_nNodes(g) > 1);
170
171  /* until the heap is empty */
172  while( dheap->size > 0 )
173  {
174  const int k = graph_heap_deleteMinReturnNode(dheap);
175  assert(CONNECT == state[k]);
176
177  for( int e = g->outbeg[k]; e >= 0; e = gOeat[e] )
178  {
179  const int m = gHead[e];
180
181  if( state[m] != CONNECT )
182  {
183  const SCIP_Real newdist = nodes_dist[k] + gCost[e];
184
185  /* check whether the path (to m) including k is shorter than the so far best known */
186  if( GT(nodes_dist[m], newdist) )
187  {
188  graph_heap_correct(m, newdist, dheap);
189  nodes_pred[m] = e;
190  nodes_dist[m] = newdist;
191  nodes_base[m] = nodes_base[k];
192  }
193  }
194  }
195  }
196 }
197
198
199 /** build a Voronoi region w.r.t. implied shortest paths for all terminals */
200 static
202  const GRAPH* g, /**< graph data structure */
203  const SDPROFIT* sdprofit, /**< SD profit */
204  DHEAP* dheap, /**< heap */
205  VNOI* vnoi /**< Voronoi data structure */
206 )
207 {
208  SCIP_Real* RESTRICT nodes_dist = vnoi->nodes_dist;
209  int* RESTRICT nodes_pred = vnoi->nodes_predEdge;
210  int* RESTRICT nodes_base = vnoi->nodes_base;
211  int* const state = dheap->position;
212  const SCIP_Real* const gCost = g->cost;
213  const int* const gOeat = g->oeat;
215
216  assert(dheap->size > 0);
217  assert(graph_get_nNodes(g) > 1);
218
219  /* until the heap is empty */
220  while( dheap->size > 0 )
221  {
222  const int k = graph_heap_deleteMinReturnNode(dheap);
223  const int k_predNode = (nodes_pred[k] >= 0) ? g->tail[nodes_pred[k]] : -1;
224  const SCIP_Real k_dist = nodes_dist[k];
225
226  assert(CONNECT == state[k]);
227
228  for( int e = g->outbeg[k]; e >= 0; e = gOeat[e] )
229  {
230  const int m = gHead[e];
231
232  if( state[m] != CONNECT )
233  {
234  const SCIP_Real profit = reduce_sdprofitGetProfit(sdprofit, k, k_predNode, m);
235  const SCIP_Real bias = MIN(gCost[e], profit);
236  const SCIP_Real newdist = k_dist + gCost[e] - MIN(k_dist, bias);
237
238  /* check whether the path (to m) including k is shorter than the so far best known */
239  if( GT(nodes_dist[m], newdist) )
240  {
241  graph_heap_correct(m, newdist, dheap);
242  nodes_pred[m] = e;
243  nodes_dist[m] = newdist;
244  nodes_base[m] = nodes_base[k];
245  }
246  }
247  }
248  }
249 }
250
251
252 /** extend a Voronoi region until all neighbouring terminals are spanned */
254  SCIP* scip, /**< SCIP data structure */
255  const GRAPH* g, /**< graph data structure */
256  const SCIP_Real* cost, /**< edgecosts */
257  PATH* path, /**< shortest paths data structure */
258  SCIP_Real** distarr, /**< array to store distance from each node to its base */
259  int** basearr, /**< array to store the bases */
260  int** edgearr, /**< array to store the ancestor edge */
261  STP_Bool* termsmark, /**< array to mark terminal */
262  int* reachednodes, /**< array to mark reached nodes */
263  int* nreachednodes, /**< pointer to number of reached nodes */
264  int* nodenterms, /**< array to store number of terimals to each node */
265  int nneighbterms, /**< number of neighbouring terminals */
266  int base, /**< voronoi base */
267  int countex /**< count of heap elements */
268  )
269 {
270  int k;
271  int m;
272  int i;
273  int* heap;
274  int* state;
275  int count = countex;
276
277  assert(g != NULL);
278  assert(g->path_heap != NULL);
279  assert(g->path_state != NULL);
280  assert(path != NULL);
281  assert(cost != NULL);
282
283  if( g->knots == 0 || nneighbterms <= 0 )
284  return SCIP_OKAY;
285
286  heap = g->path_heap;
287  state = g->path_state;
288
289  if( g->knots > 1 )
290  {
291  while( count > 0 && nneighbterms > 0 )
292  {
293  k = nearest(heap, state, &count, path);
294  state[k] = CONNECT;
295  reachednodes[(*nreachednodes)++] = k;
296  distarr[k][nodenterms[k]] = path[k].dist;
297  edgearr[k][nodenterms[k]] = path[k].edge;
298  basearr[k][nodenterms[k]] = base;
299
300  nodenterms[k]++;
301
302  if( termsmark[k] == TRUE )
303  {
304  termsmark[k] = FALSE;
305  if( --nneighbterms == 0 )
306  {
307  while( count > 0 )
308  reachednodes[(*nreachednodes)++] = heap[count--];
309
310  return SCIP_OKAY;
311  }
312  }
313  else if( !Is_term(g->term[k]) )
314  {
315  /* iterate over all outgoing edges of vertex k */
316  for( i = g->outbeg[k]; i != EAT_LAST; i = g->oeat[i] )
317  {
319
320  /* check whether the path (to m) including (k, m) is shorter than the so far best known */
321  if( (state[m]) && (g->mark[m]) && (GT(path[m].dist, (path[k].dist + cost[i]))) )
322  correct(heap, state, &count, path, m, k, i, cost[i]);
323  }
324  }
325  }
326  assert(nneighbterms == 0);
327  }
328  return SCIP_OKAY;
329 }
330
331
332 /** build a Voronoi region, w.r.t. shortest paths, for a given set of bases */
334  const GRAPH* g, /**< graph data structure */
335  const SCIP_Real* cost, /**< edge costs */
336  const SCIP_Real* costrev, /**< reversed edge costs (or NULL if symmetric) */
337  const STP_Bool* basemark, /**< array to indicate whether a vertex is a Voronoi base */
338  int* vbase, /**< voronoi base to each vertex */
339  PATH* path /**< path data struture (leading to respective Voronoi base) */
340  )
341 {
342  int* RESTRICT heap;
343  int* RESTRICT state;
344  int root;
345  int count = 0;
346  int nbases = 0;
347
348  assert(g && cost && basemark && vbase && path);
349  assert(g->path_heap != NULL);
350  assert(g->path_state != NULL);
351
352  if( g->knots == 0 )
353  return;
354
355  root = g->source;
356  heap = g->path_heap;
357  state = g->path_state;
358
359  /* initialize */
360  for( int i = 0; i < g->knots; i++ )
361  {
362  /* set the base of vertex i */
363  if( basemark[i] )
364  {
365  nbases++;
366  if( g->knots > 1 )
367  heap[++count] = i;
368  vbase[i] = i;
369  path[i].dist = 0.0;
370  path[i].edge = UNKNOWN;
371  state[i] = count;
372  }
373  else
374  {
375  vbase[i] = UNKNOWN;
376  path[i].dist = FARAWAY;
377  path[i].edge = UNKNOWN;
378  state[i] = UNKNOWN;
379  }
380  }
381  assert(nbases > 0);
382
383  if( g->knots > 1 )
384  {
385  /* with reversed costs? */
386  if( costrev )
387  {
388  /* until the heap is empty */
389  while( count > 0 )
390  {
391  /* get the next (i.e. a nearest) vertex of the heap */
392  const int k = nearest(heap, state, &count, path);
393
394  /* mark vertex k as scanned */
395  state[k] = CONNECT;
396
397  for( int i = g->outbeg[k]; i >= 0; i = g->oeat[i] )
398  {
399  const int m = g->head[i];
400
401  /* check whether the path (to m) including k is shorter than the so far best known */
402  if( (state[m]) && GT(path[m].dist, path[k].dist + ((vbase[k] == root)? cost[i] : costrev[i])) )
403  {
404  assert(!basemark[m]);
405  correct(heap, state, &count, path, m, k, i, ((vbase[k] == root)? cost[i] : costrev[i]));
406  vbase[m] = vbase[k];
407  }
408  }
409  }
410  }
411  else
412  {
413  while( count > 0 )
414  {
415  const int k = nearest(heap, state, &count, path);
416  state[k] = CONNECT;
417
418  for( int i = g->outbeg[k]; i >= 0; i = g->oeat[i] )
419  {
420  const int m = g->head[i];
421  if( (state[m]) && GT(path[m].dist, path[k].dist + cost[i]) )
422  {
423  assert(!basemark[m]);
424  correct(heap, state, &count, path, m, k, i, cost[i]);
425  vbase[m] = vbase[k];
426  }
427  }
428  }
429  }
430  }
431 }
432
433
434
435
436 /** build a voronoi region, w.r.t. shortest paths, for all terminal
437  * NOTE: uses bias for PC! */
439  const GRAPH* g, /**< graph data structure */
440  const SCIP_Bool* nodes_isTerm, /**< for each node: is terminal? */
441  int* RESTRICT vbase, /**< array containing Voronoi base to each node */
442  PATH* RESTRICT path /**< array containing Voronoi paths data */
443  )
444 {
445  int* RESTRICT heap;
446  int* RESTRICT state;
447  int heapsize;
448  const int nnodes = graph_get_nNodes(g);
449
450  assert(nodes_isTerm && vbase && path);
451
452  heap = g->path_heap;
453  state = g->path_state;
454  assert(heap && state);
455
456  heapsize = 0;
457
458  /* initialize */
459  for( int i = 0; i < nnodes; i++ )
460  {
461  /* set the base of vertex i */
462  if( nodes_isTerm[i] && g->mark[i] )
463  {
464  if( nnodes > 1 )
465  heap[++heapsize] = i;
466  vbase[i] = i;
467  state[i] = heapsize;
468  path[i].dist = 0.0;
469  }
470  else
471  {
472  vbase[i] = UNKNOWN;
473  state[i] = UNKNOWN;
474  path[i].dist = FARAWAY;
475  }
476  path[i].edge = UNKNOWN;
477  }
478
479  if( nnodes > 1 )
480  {
481  const SCIP_Bool isPc = graph_pc_isPc(g);
482
483  /* until the heap is empty */
484  while( heapsize > 0 )
485  {
486  /* get the next (i.e. a nearest) vertex of the heap */
487  const int k = nearest(heap, state, &heapsize, path);
488
489  /* mark vertex k as scanned */
490  state[k] = CONNECT;
491
492  /* iterate over all outgoing edges of vertex k */
493  for( int e = g->outbeg[k]; e != EAT_LAST; e = g->oeat[e] )
494  {
495  SCIP_Real costbiased;
496  const int m = g->head[e];
497
498  costbiased = g->cost[e];
499
500  if( isPc && !nodes_isTerm[k] )
501  costbiased -= g->prize[k];
502
503  assert(GE(costbiased, 0.0) && LE(costbiased, g->cost[e]));
504
505  if( state[m] && g->mark[m] && GT(path[m].dist, path[k].dist + costbiased) )
506  {
507  correct(heap, state, &heapsize, path, m, k, e, costbiased);
508  vbase[m] = vbase[k];
509  }
510  }
511  }
512  }
513 }
514
515
516 /** build a Voronoi region, w.r.t. shortest paths, for all positive vertices */
518  SCIP* scip, /**< SCIP data structure */
519  const GRAPH* g, /**< graph data structure */
520  const SCIP_Real* costrev, /**< reversed edge costs */
521  PATH* path, /**< path data structure (leading to respective Voronoi base) */
522  int* vbase, /**< Voronoi base to each vertex */
523  int* heap, /**< array representing a heap */
524  int* state /**< array to mark the state of each node during calculation */
525  )
526 {
527  int k;
528  int m;
529  int i;
530  int count = 0;
531  int nbases = 0;
532  int nnodes;
533
534  assert(g != NULL);
535  assert(path != NULL);
536  assert(costrev != NULL);
537  assert(heap != NULL);
538  assert(state != NULL);
539
540  nnodes = g->knots;
541
542  /* initialize */
543  for( i = 0; i < nnodes; i++ )
544  {
545  /* set the base of vertex i */
546  if( Is_term(g->term[i]) && g->mark[i] )
547  {
548  nbases++;
549  if( nnodes > 1 )
550  heap[++count] = i;
551  vbase[i] = i;
552  path[i].dist = -g->prize[i];
553  path[i].edge = UNKNOWN;
554  state[i] = count;
555  }
556  else
557  {
558  vbase[i] = UNKNOWN;
559  path[i].dist = FARAWAY;
560  path[i].edge = UNKNOWN;
561  state[i] = UNKNOWN;
562  }
563  }
564  if( nbases == 0 )
565  return;
566  if( nnodes > 1 )
567  {
568  /* until the heap is empty */
569  while( count > 0 )
570  {
571  /* get the next (i.e. a nearest) vertex of the heap */
572  k = nearest(heap, state, &count, path);
573
574  /* mark vertex k as scanned */
575  state[k] = CONNECT;
576
577  /* iterate over all outgoing edges of vertex k */
578  for( i = g->outbeg[k]; i != EAT_LAST; i = g->oeat[i] )
579  {
581
582  /* check whether the path (to m) including k is shorter than the so far best known */
583  if( (state[m]) && SCIPisGT(scip, path[m].dist, path[k].dist + costrev[i]) && g->mark[m] && !Is_term(g->term[m]) )
584  {
585  assert(vbase[m] != m);
586  correct(heap, state, &count, path, m, k, i, costrev[i]);
587  vbase[m] = vbase[k];
588  }
589  }
590  }
591  }
592  return;
593 }
594
595
596 /** build a voronoi region, w.r.t. shortest paths, for all terminal and the distance */
598  SCIP* scip, /**< SCIP data structure */
599  const GRAPH* g, /**< graph data structure */
600  const SCIP_Bool* nodes_isTerm, /**< for each node: is terminal? */
601  const SCIP_Real* cost, /**< edge costs */
602  SCIP_Real* distance, /**< array storing path from a terminal over shortest
603  incident edge to nearest terminal */
604  int* edges_isMinedgePred, /**< shortest edge predecessor array */
605  int* vbase, /**< array containing Voronoi base to each node */
606  int* minarc, /**< array to mark whether an edge is one a path corresponding to 'distance' */
607  int* distnode, /**< array to store terminal corresponding to distance stored in distance array */
608  PATH* path /**< array containing Voronoi paths data */
609  )
610 {
611  int* RESTRICT heap;
612  int* RESTRICT state;
613  int count;
614  int nbases;
615  const int nnodes = graph_get_nNodes(g);
616
617  assert(path != NULL);
618  assert(cost != NULL);
619  assert(distance != NULL);
620  assert(nodes_isTerm);
621
622  heap = g->path_heap;
623  state = g->path_state;
624  assert(heap);
625  assert(state);
626
627  count = 0;
628  nbases = 0;
629
630  if( distnode != NULL )
631  {
632  for( int i = 0; i < nnodes; i++ )
633  distnode[i] = UNKNOWN;
634  }
635
636  /* initialize */
637  for( int i = 0; i < nnodes; i++ )
638  {
639  distance[i] = FARAWAY;
640
641  /* set the base of vertex i */
642  if( nodes_isTerm[i] && g->mark[i] )
643  {
644  nbases++;
645  if( nnodes > 1 )
646  heap[++count] = i;
647  vbase[i] = i;
648  state[i] = count;
649  path[i].dist = 0.0;
650  }
651  else
652  {
653  vbase[i] = UNKNOWN;
654  state[i] = UNKNOWN;
655  path[i].dist = FARAWAY;
656  }
657  path[i].edge = UNKNOWN;
658  }
659
660  /* initialize predecessor array */
661
662  for( int e = 0; e < g->edges; e++ )
663  edges_isMinedgePred[e] = FALSE;
664
665  for( int k = 0; k < nbases; k++ )
666  {
667  if( minarc[k] == UNKNOWN )
668  {
669  assert(graph_pc_isPc(g));
670  continue;
671  }
672  assert(graph_edge_isInRange(g, minarc[k]));
673  edges_isMinedgePred[minarc[k]] = TRUE;
674  }
675
676  /* if graph contains more than one vertices, start main loop */
677  if( nnodes > 1 )
678  {
679  const SCIP_Bool isPc = graph_pc_isPc(g);
680  /* until the heap is empty */
681  while( count > 0 )
682  {
683  /* get the next (i.e. a nearest) vertex of the heap */
684  const int k = nearest(heap, state, &count, path);
685  const int prededge = path[k].edge;
686
687  /* mark vertex k as scanned */
688  state[k] = CONNECT;
689
690  if( prededge != UNKNOWN )
691  {
692  const int pred = g->tail[prededge];
693
694  assert(vbase[k] != UNKNOWN);
695  assert(vbase[pred] != UNKNOWN);
696  assert(vbase[pred] == vbase[k]);
698
699  if( !nodes_isTerm[pred] && g->mark[pred] )
700  {
701  assert(path[pred].edge != UNKNOWN);
702  edges_isMinedgePred[prededge] = edges_isMinedgePred[path[pred].edge];
703  }
704  }
705
706  /* iterate over all outgoing edges of vertex k */
707  for( int e = g->outbeg[k]; e != EAT_LAST; e = g->oeat[e] )
708  {
709  SCIP_Real costbiased;
710  const int m = g->head[e];
711
712  costbiased = cost[e];
713
714  if( isPc && !nodes_isTerm[k] )
715  costbiased -= g->prize[k];
716
717  assert(GE(costbiased, 0.0) && LE(costbiased, cost[e]));
718
719  if( state[m] == CONNECT && vbase[m] != vbase[k] )
720  {
721  assert(g->mark[m]);
722
723  if( edges_isMinedgePred[e] || (prededge != UNKNOWN && edges_isMinedgePred[prededge] ) )
724  {
725  SCIP_Real distnew = path[k].dist + costbiased + path[m].dist;
726  if( isPc && !nodes_isTerm[m] )
727  distnew -= g->prize[m];
728
729  if( SCIPisLT(scip, distnew, distance[vbase[k]]) )
730  {
731  if( distnode != NULL )
732  distnode[vbase[k]] = vbase[m];
733
734  distance[vbase[k]] = distnew;
735  }
736  }
737  if( edges_isMinedgePred[Edge_anti(e)] || (path[m].edge != UNKNOWN && edges_isMinedgePred[path[m].edge] ) )
738  {
739  SCIP_Real distnew = path[m].dist + costbiased + path[k].dist;
740  if( isPc && !nodes_isTerm[m] )
741  distnew -= g->prize[m];
742
743  if( SCIPisLT(scip, distnew, distance[vbase[m]]) )
744  {
745  if( distnode != NULL )
746  distnode[vbase[m]] = vbase[k];
747
748  distance[vbase[m]] = distnew;
749  }
750  }
751  }
752
753  /* Check whether the path (to m) including k is shorter than the so far best known.
754  In case of equality, also update if k is sucessor of minedge. */
755  if( state[m] && g->mark[m] &&
756  (SCIPisGT(scip, path[m].dist, path[k].dist + costbiased) ||
757  (prededge != UNKNOWN && edges_isMinedgePred[prededge] && SCIPisEQ(scip, path[m].dist, path[k].dist + costbiased))) )
758  {
759  /* NOTE guard against cycling */
760  if( isPc && EQ(path[m].dist, path[k].dist + costbiased) && EQ(costbiased, 0.0) )
761  continue;
762
763  correct(heap, state, &count, path, m, k, e, costbiased);
764  vbase[m] = vbase[k];
765  }
766  }
767  }
768  }
769
770  return SCIP_OKAY;
771 }
772
773 /** build voronoi regions, w.r.t. shortest paths, for all terminals and compute the radii */
775  SCIP* scip, /**< SCIP data structure */
776  const GRAPH* graph, /**< graph data structure */
777  GRAPH* adjgraph, /**< graph data structure */
778  PATH* path, /**< array containing Voronoi paths data */
779  SCIP_Real* rad, /**< array storing shortest way from a terminal out of its Voronoi region */
780  SCIP_Real* cost, /**< edge costs */
781  SCIP_Real* costrev, /**< reversed edge costs */
782  int* vbase, /**< array containing Voronoi base of each node */
783  int* heap, /**< array representing a heap */
784  int* state /**< array to mark state of each node during calculation */
785  )
786 {
787  int* nodesid;
788  int count = 0;
789  int nterms = 0;
790  const int root = graph->source;
791  const int nnodes = graph->knots;
792  const STP_Bool mw = (graph->stp_type == STP_MWCSP);
793  const STP_Bool pc = ((graph->stp_type == STP_PCSPG) || (graph->stp_type == STP_RPCSPG));
794
795  assert(graph != NULL);
796  assert(heap != NULL);
797  assert(state != NULL);
798  assert(path != NULL);
799  assert(cost != NULL);
800  assert(costrev != NULL);
802  assert(vbase != NULL);
803  assert(!graph->extended);
804
805  if( graph->terms == 0 )
806  return SCIP_OKAY;
807
808  SCIP_CALL( SCIPallocBufferArray(scip, &nodesid, nnodes) );
809
810  /* initialize */
811  for( int i = 0; i < nnodes; i++ )
812  {
814
815  /* set the base of vertex i */
816  if( Is_term(graph->term[i]) && graph->mark[i] )
817  {
818  if( nnodes > 1 )
819  heap[++count] = i;
820
821  if( !mw && adjgraph != NULL )
822  {
825  }
826
827  nodesid[i] = nterms++;
828  vbase[i] = i;
829
830  if( mw )
831  assert(SCIPisGE(scip, graph->prize[i], 0.0));
832  if( mw )
833  path[i].dist = -graph->prize[i];
834  else
835  path[i].dist = 0.0;
836
837  path[i].edge = UNKNOWN;
838  state[i] = count;
839  }
840  else
841  {
842  vbase[i] = UNKNOWN;
843  nodesid[i] = UNKNOWN;
844  path[i].dist = FARAWAY;
845  path[i].edge = UNKNOWN;
846  state[i] = UNKNOWN;
847  }
848  }
849
850  if( nnodes > 1 )
851  {
852  SCIP_Real ecost;
853
854  /* until the heap is empty */
855  while( count > 0 )
856  {
857  /* get the next (i.e. a nearest) vertex of the heap */
858  const int k = nearest(heap, state, &count, path);
859
860  /* mark vertex k as scanned */
861  state[k] = CONNECT;
862
863  /* iterate over all outgoing edges of vertex k */
864  for( int i = graph->outbeg[k]; i != EAT_LAST; i = graph->oeat[i] )
865  {
866  const int m = graph->head[i];
867  const int vbm = vbase[m];
868  const int vbk = vbase[k];
869
870  if( state[m] == CONNECT && vbm != vbk && graph->mark[m] )
871  {
872  assert(graph->mark[vbm]);
873  assert(graph->mark[vbk]);
874  if( mw )
875  {
876  if( SCIPisGT(scip, rad[vbk], path[k].dist) )
878  if( SCIPisGT(scip, rad[vbm], path[m].dist) )
880  }
881  else
882  {
883
884  if( SCIPisGT(scip, rad[vbk], path[k].dist + ((vbk == root) ? cost[i] : costrev[i])) )
885  rad[vbk] = path[k].dist + ((vbk == root) ? cost[i] : costrev[i]);
886
887  if( SCIPisGT(scip, rad[vbm], path[m].dist + ((vbm == root) ? costrev[i] : cost[i])) )
888  rad[vbm] = path[m].dist + ((vbm == root) ? costrev[i] : cost[i]);
889
890  if( adjgraph != NULL )
891  {
892  int ne;
893
894  if( graph->stp_type == STP_DHCSTP )
895  {
896  SCIP_Real c1;
897  SCIP_Real c2;
898
899  if( m == root )
900  c1 = path[m].dist + costrev[i];
901  else
902  c1 = path[m].dist + cost[i];
903  if( k == root )
904  c2 = path[k].dist + cost[i];
905  else
906  c2 = path[k].dist + costrev[i];
907
908  if( SCIPisGT(scip, c1, c2) )
909  ecost = c2;
910  else
911  ecost = c1;
912  }
913  else
914  {
915  if( SCIPisGT(scip, path[m].dist, path[k].dist) )
916  ecost = path[k].dist + cost[i];
917  else
918  ecost = path[m].dist + cost[i];
919  }
920
921  if( pc )
922  {
923  if( SCIPisGT(scip, ecost, graph->prize[vbm]) && root != vbm && !graph_pc_knotIsFixedTerm(graph, vbm) )
924  ecost = graph->prize[vbm];
925
926  if( SCIPisGT(scip, ecost, graph->prize[vbk]) && root != vbk && !graph_pc_knotIsFixedTerm(graph, vbk) )
927  ecost = graph->prize[vbk];
928  }
929
930  /* find edge in adjgraph */
931  for( ne = adjgraph->outbeg[nodesid[vbk]]; ne != EAT_LAST; ne = adjgraph->oeat[ne] )
933  break;
934
935  /* edge exists? */
936  if( ne != EAT_LAST )
937  {
938  assert(ne >= 0);
941  if( SCIPisGT(scip, adjgraph->cost[ne], ecost) )
942  {
945  }
946  }
947  else
948  {
950  }
951  }
952  }
953  }
954
955  /* check whether the path (to m) including k is shorter than the so far best known */
956  if( state[m] && graph->mark[m] && !Is_term(graph->term[m]) && SCIPisGT(scip, path[m].dist, path[k].dist + ((vbk == root)? cost[i] : costrev[i])) )
957  {
958  correct(heap, state, &count, path, m, k, i, ((vbk == root)? cost[i] : costrev[i]));
959  vbase[m] = vbk;
960  }
961  }
962  }
963  }
964  SCIPfreeBufferArray(scip, &nodesid);
965
966  return SCIP_OKAY;
967 }
968
969 /** Build partition of graph for MWCSP into regions around the positive vertices.
970  * Store the weight of a minimum weight center-boundary path for each region
971  * in the radius array (has to be reverted to obtain the final r() value).
972  */
974  SCIP* scip, /**< SCIP data structure */
975  const GRAPH* g, /**< graph data structure */
976  PATH* path, /**< array containing graph decomposition data */
977  const SCIP_Real* cost, /**< edge costs */
978  SCIP_Real* radius, /**< array storing shortest way from a positive vertex out of its region */
979  int* vbase, /**< array containing base of each node */
980  int* heap, /**< array representing a heap */
981  int* state /**< array to mark state of each node during calculation */
982  )
983 {
984  SCIP_Real* nodeweight;
985  int i;
986  int k;
987  int m;
988  int count;
989  int nbases;
990  int nnodes;
991  int nterms;
992
993  assert(g != NULL);
994  assert(heap != NULL);
995  assert(state != NULL);
996  assert(path != NULL);
997  assert(cost != NULL);
999  assert(vbase != NULL);
1000
1001  count = 0;
1002  nbases = 0;
1003  nnodes = g->knots;
1004  nterms = g->terms - 1;
1005  nodeweight = g->prize;
1006
1007  assert(nodeweight != NULL);
1008
1009  if( nnodes == 0 || nterms <= 0 )
1010  return;
1011
1012  assert(!g->mark[g->source]);
1013
1014  /* initialize data */
1015  for( i = 0; i < nnodes; i++ )
1016  {
1018
1019  /* set the base of vertex i */
1020  if( Is_term(g->term[i]) && g->mark[i] )
1021  {
1022  nbases++;
1023  if( nnodes > 1 )
1024  heap[++count] = i;
1025  vbase[i] = i;
1026  path[i].dist = 0.0;
1027  path[i].edge = UNKNOWN;
1028  state[i] = count;
1029  }
1030  else
1031  {
1032  vbase[i] = UNKNOWN;
1033  path[i].dist = FARAWAY;
1034  path[i].edge = UNKNOWN;
1035  state[i] = UNKNOWN;
1036  }
1037  }
1038
1039  if( nbases == 0 )
1040  return;
1041
1042  if( nnodes > 1 )
1043  {
1044  int basem;
1045  int basek;
1046
1047  /* until the heap is empty */
1048  while( count > 0 )
1049  {
1050  /* get the next (i.e. a nearest) vertex of the heap */
1051  k = nearest(heap, state, &count, path);
1052
1053  /* mark vertex k as scanned */
1054  state[k] = CONNECT;
1055  basek = vbase[k];
1056
1057  assert(g->mark[basek]);
1058
1059  /* iterate over all outgoing edges of vertex k */
1060  for( i = g->outbeg[k]; i != EAT_LAST; i = g->oeat[i] )
1061  {
1063
1064  if( !(g->mark[m]) )
1065  continue;
1066
1067  basem = vbase[m];
1068
1069  /* are both m and k finally in different regions? */
1070  if( basem != basek && (state[m] == CONNECT || vbase[m] == m ||
1071  SCIPisGE(scip, path[k].dist, nodeweight[basek])) )
1072  {
1073  if( SCIPisGT(scip, radius[basek], path[k].dist) )
1075  if( (state[m] == CONNECT || vbase[m] == m) && SCIPisGT(scip, radius[basem], path[m].dist) )
1076  {
1077  assert(g->mark[basem]);
1079  }
1080  }
1081
1082  /* is the distance of vertex k smaller than the weight of its base node and smaller than the temp. radius? */
1083  if( SCIPisLT(scip, path[k].dist, nodeweight[basek]) && SCIPisLT(scip, path[k].dist, radius[basek]) )
1084  {
1085  /* check whether the path (to m) including k is shorter than the so far best known */
1086  if( (state[m]) && SCIPisGT(scip, path[m].dist, path[k].dist + cost[i]) )
1087  {
1088  assert(vbase[m] != m);
1089  correct(heap, state, &count, path, m, k, i, cost[i]);
1090  vbase[m] = basek;
1091  }
1092  }
1093  }
1094  }
1095  }
1096  return;
1097 }
1098
1099 /** repair a Voronoi diagram for a given set of base nodes */
1101  SCIP* scip, /**< SCIP data structure */
1102  const GRAPH* g, /**< graph data structure */
1103  const SCIP_Real* cost, /**< edge costs (possibly biased) */
1104  const SCIP_Real* cost_org, /**< original edge costs (only needed for PC) */
1105  int* nheapelems, /**< pointer to number of heap elements */
1106  int* vbase, /**< array containing Voronoi base of each node */
1107  PATH* path, /**< Voronoi paths data struture */
1108  int* newedge, /**< the new edge */
1109  int crucnode, /**< the current crucial node */
1110  UF* uf /**< union find data structure */
1111  )
1112 {
1113  const int nnodes = graph_get_nNodes(g);
1114  int boundaryedge = UNKNOWN;
1115  SCIP_Real boundarydist = FARAWAY;
1116
1117  assert(cost && scip && nheapelems && newedge && vbase && uf);
1118
1119  *newedge = UNKNOWN;
1120
1121  if( nnodes > 1 )
1122  {
1123  int* const heap = g->path_heap;
1124  int* const state = g->path_state;
1125  const SCIP_Bool isPcMw = graph_pc_isPcMw(g);
1126  const SCIP_Bool isPc = graph_pc_isPc(g);
1127
1128  assert(heap && state);
1129
1130  /* until the heap is empty */
1131  while( *nheapelems > 0 )
1132  {
1133  /* get the next (i.e. a nearest) vertex from the heap */
1134  const int k = nearest(heap, state, nheapelems, path);
1135
1136  /* mark vertex k as scanned */
1137  state[k] = CONNECT;
1138
1139  assert(vbase[k] >= 0);
1140  assert(g->mark[k] && g->mark[vbase[k]]);
1141
1142  /* iterate over all outgoing edges of vertex k */
1143  for( int e = g->outbeg[k]; e != EAT_LAST; e = g->oeat[e] )
1144  {
1145  const int m = g->head[e];
1146
1147  /* check whether the path (to m) including k is shorter than the so far best known */
1148  if( (state[m]) && (SCIPisGT(scip, path[m].dist, path[k].dist + cost[e])) )
1149  {
1150  assert(g->mark[m]);
1151  correct(heap, state, nheapelems, path, m, k, e, cost[e]);
1152  vbase[m] = vbase[k];
1153  }
1154  /* check whether there is a better new boundary edge adjacent to vertex k */
1155  else if( state[m] == CONNECT && g->mark[m] )
1156  {
1157  const int node1 = SCIPStpunionfindFind(uf, vbase[m]);
1158  const int node2 = SCIPStpunionfindFind(uf, vbase[k]);
1159
1160  if( (node1 == crucnode) == (node2 == crucnode) )
1161  continue;
1162
1163  if( !g->mark[node1] || !g->mark[node2] || !g->mark[vbase[m]] )
1164  continue;
1165
1166  /* now to the actual checks */
1167
1168  if( boundaryedge == UNKNOWN )
1169  {
1170  boundaryedge = e;
1171  }
1172  else
1173  {
1174  SCIP_Real dist_new = path[k].dist + path[m].dist;
1175
1176  if( isPcMw )
1177  {
1178  if( isPc )
1179  {
1180  assert(cost_org);
1181  dist_new += cost_org[e];
1182  }
1183  }
1184  else
1185  {
1186  assert(!cost_org);
1187  dist_new += cost[e];
1188  }
1189
1190  if( dist_new < boundarydist )
1191  {
1192  boundarydist = dist_new;
1193  boundaryedge = e;
1194  }
1195  }
1196  } /* check for boundary edge */
1197  }
1198  }
1199  }
1200
1201  *newedge = boundaryedge;
1202 }
1203
1204
1205 /** repair the Voronoi diagram for a given set nodes */
1207  SCIP* scip, /**< SCIP data structure */
1208  const GRAPH* g, /**< graph data structure */
1209  const SCIP_Real* cost, /**< edge costs */
1210  const STP_Bool* nodesmark, /**< array to mark temporarily discarded nodes */
1211  int* RESTRICT count, /**< pointer to number of heap elements */
1212  int* RESTRICT vbase, /**< array containing Voronoi base of each node */
1213  int* RESTRICT boundedges, /**< boundary edges */
1214  int* RESTRICT nboundedges, /**< number of boundary edges */
1215  UF* RESTRICT uf, /**< union find data structure */
1216  PATH* RESTRICT path /**< Voronoi paths data structure */
1217  )
1218 {
1219  assert(scip && g && cost && nodesmark && count && vbase && boundedges && nboundedges && uf && path);
1220  assert(g->path_heap && g->path_state);
1221
1222  if( g->knots > 1 )
1223  {
1224  int node1;
1225  int node2;
1226  int* const heap = g->path_heap;
1227  int* const state = g->path_state;
1228
1229  /* until the heap is empty */
1230  while( (*count) > 0 )
1231  {
1232  /* get the next (i.e. a nearest) vertex from the heap */
1233  const int k = nearest(heap, state, count, path);
1234
1235  /* mark vertex k as scanned */
1236  state[k] = CONNECT;
1237
1238  /* iterate all outgoing edges of vertex k */
1239  for( int i = g->outbeg[k]; i != EAT_LAST; i = g->oeat[i] )
1240  {
1241  const int m = g->head[i];
1242
1243  if( !(g->mark[m]) )
1244  continue;
1245
1246  /* check whether the path (to m) including k is shorter than the so far best known */
1247  if( state[m] && (SCIPisGT(scip, path[m].dist, path[k].dist + cost[i])) )
1248  {
1249  correct(heap, state, count, path, m, k, i, cost[i]);
1250  vbase[m] = vbase[k];
1251  }
1252  /* check whether there is a new boundary edge adjacent to vertex k */
1253  else if( (state[m] == CONNECT) && ((node1 = SCIPStpunionfindFind(uf, vbase[m])) != (node2 = SCIPStpunionfindFind(uf, vbase[k])))
1254  && g->mark[node1] && g->mark[node2] && (nodesmark[node1] || nodesmark[node2]) )
1255  {
1256  boundedges[(*nboundedges)++] = i;
1257  }
1258  }
1259  }
1260  }
1261 }
1262
1263
1264 /** initializes VNOI structure */
1266  SCIP* scip, /**< SCIP */
1267  const GRAPH* graph, /**< graph data structure to work on */
1268
1269  SCIP_Bool useBufferArrays, /**< should buffer arrays be used? */
1270  VNOI** vnoi /**< the VNOI */
1271 )
1272 {
1273  VNOI* vnoi_d;
1274  const int nnodes = graph_get_nNodes(graph);
1275
1276  assert(scip);
1277
1278  SCIP_CALL( SCIPallocMemory(scip, vnoi) );
1279
1280  vnoi_d = *vnoi;
1281  vnoi_d->nnodes = nnodes;
1282  vnoi_d->usingBufferArrays = useBufferArrays;
1283
1284  if( useBufferArrays )
1285  {
1286  SCIP_CALL( SCIPallocBufferArray(scip, &(vnoi_d->nodes_dist), nnodes) );
1287  SCIP_CALL( SCIPallocBufferArray(scip, &(vnoi_d->nodes_predEdge), nnodes) );
1288  SCIP_CALL( SCIPallocBufferArray(scip, &(vnoi_d->nodes_base), nnodes) );
1289  }
1290  else
1291  {
1292  SCIP_CALL( SCIPallocMemoryArray(scip, &(vnoi_d->nodes_dist), nnodes) );
1293  SCIP_CALL( SCIPallocMemoryArray(scip, &(vnoi_d->nodes_predEdge), nnodes) );
1294  SCIP_CALL( SCIPallocMemoryArray(scip, &(vnoi_d->nodes_base), nnodes) );
1295  }
1296
1297  return SCIP_OKAY;
1298 }
1299
1300
1301 /** computes Voronoi region on given graph */
1303  SCIP* scip, /**< SCIP */
1304  const GRAPH* graph, /**< graph data structure to work on */
1305  VNOI* vnoi /**< the VNOI */
1306 )
1307 {
1308  DHEAP* dheap;
1309  const int nnodes = graph_get_nNodes(graph);
1310  assert(vnoi->nnodes == graph->knots);
1311
1312  SCIP_CALL( graph_heap_create(scip, nnodes, NULL, NULL, &(dheap) ));
1313  vnoiInit(graph, dheap, vnoi);
1314  vnoiCompute(scip, graph, dheap, vnoi);
1315
1316  graph_heap_free(scip, TRUE, TRUE, &dheap);
1317
1318  return SCIP_OKAY;
1319 }
1320
1321
1322 /** computes implied Voronoi region on given graph */
1324  SCIP* scip, /**< SCIP */
1325  const GRAPH* graph, /**< graph data structure to work on */
1326  const SDPROFIT* sdprofit, /**< SD profit */
1327  VNOI* vnoi /**< the VNOI */
1328 )
1329 {
1330  DHEAP* dheap;
1331
1332  const int nnodes = graph_get_nNodes(graph);
1333
1334  assert(vnoi->nnodes == graph->knots);
1335
1336  SCIP_CALL( graph_heap_create(scip, nnodes, NULL, NULL, &(dheap) ));
1337
1338  vnoiInit(graph, dheap, vnoi);
1339  vnoiComputeImplied(graph, sdprofit, dheap, vnoi);
1340
1341  graph_heap_free(scip, TRUE, TRUE, &dheap);
1342
1343  return SCIP_OKAY;
1344 }
1345
1346
1347 /** frees VNOI structure */
1349  SCIP* scip, /**< SCIP */
1350  VNOI** vnoi /**< the VNOI */
1351 )
1352 {
1353  VNOI* vnoi_d;
1354  assert(scip && vnoi);
1355
1356  vnoi_d = *vnoi;
1357  assert(vnoi_d);
1358
1359  if( vnoi_d->usingBufferArrays )
1360  {
1361  SCIPfreeBufferArray(scip, &(vnoi_d->nodes_base));
1362  SCIPfreeBufferArray(scip, &(vnoi_d->nodes_predEdge));
1363  SCIPfreeBufferArray(scip, &(vnoi_d->nodes_dist));
1364  }
1365  else
1366  {
1367  SCIPfreeMemoryArray(scip, &(vnoi_d->nodes_base));
1368  SCIPfreeMemoryArray(scip, &(vnoi_d->nodes_predEdge));
1369  SCIPfreeMemoryArray(scip, &(vnoi_d->nodes_dist));
1370  }
1371
1372  SCIPfreeMemory(scip, vnoi);
1373 }
static volatile int nterms
Definition: interrupt.c:38
Definition: graphdefs.h:224
int source
Definition: graphdefs.h:195
#define Is_term(a)
Definition: graphdefs.h:102
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
signed int edge
Definition: graphdefs.h:287
void graph_voronoi(const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, const STP_Bool *basemark, int *vbase, PATH *path)
Definition: graph_vnoi.c:333
int terms
Definition: graphdefs.h:192
void graph_voronoiTerms(const GRAPH *g, const SCIP_Bool *nodes_isTerm, int *RESTRICT vbase, PATH *RESTRICT path)
Definition: graph_vnoi.c:438
int * nodes_predEdge
Definition: graphdefs.h:329
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static void vnoiInit(const GRAPH *g, DHEAP *dheap, VNOI *vnoi)
Definition: graph_vnoi.c:116
static void vnoiCompute(SCIP *scip, const GRAPH *g, DHEAP *dheap, VNOI *vnoi)
Definition: graph_vnoi.c:153
#define FALSE
Definition: def.h:87
int *RESTRICT path_state
Definition: graphdefs.h:256
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
SCIP_RETCODE graph_vnoiComputeImplied(SCIP *scip, const GRAPH *graph, const SDPROFIT *sdprofit, VNOI *vnoi)
Definition: graph_vnoi.c:1323
#define EAT_LAST
Definition: graphdefs.h:58
SCIP_Bool graph_heap_isClean(const DHEAP *)
Definition: graph_util.c:962
#define FARAWAY
Definition: graphdefs.h:89
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
static void correct(int *RESTRICT heap, int *RESTRICT state, int *RESTRICT count, PATH *RESTRICT path, int l, int k, int e, SCIP_Real cost)
Definition: graph_vnoi.c:35
void graph_voronoiRepair(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *cost_org, int *nheapelems, int *vbase, PATH *path, int *newedge, int crucnode, UF *uf)
Definition: graph_vnoi.c:1100
int *RESTRICT mark
Definition: graphdefs.h:198
void graph_voronoiWithRadiusMw(SCIP *scip, const GRAPH *g, PATH *path, const SCIP_Real *cost, SCIP_Real *radius, int *vbase, int *heap, int *state)
Definition: graph_vnoi.c:973
int * position
Definition: graphdefs.h:305
int *RESTRICT oeat
Definition: graphdefs.h:231
#define LE(a, b)
Definition: portab.h:83
#define GE(a, b)
Definition: portab.h:85
SCIP_Bool extended
Definition: graphdefs.h:267
int stp_type
Definition: graphdefs.h:264
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE graph_voronoiExtend(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, PATH *path, SCIP_Real **distarr, int **basearr, int **edgearr, STP_Bool *termsmark, int *reachednodes, int *nreachednodes, int *nodenterms, int nneighbterms, int base, int countex)
Definition: graph_vnoi.c:253
SCIP_Real * prize
Definition: graphdefs.h:210
SCIP_Bool usingBufferArrays
Definition: graphdefs.h:332
void graph_edge_add(SCIP *, GRAPH *, int, int, double, double)
SCIP_Real dist
Definition: graphdefs.h:286
Definition: graph_node.c:64
#define NULL
Definition: lpi_spx1.cpp:155
#define STP_DHCSTP
Definition: graphdefs.h:52
void graph_voronoiMw(SCIP *scip, const GRAPH *g, const SCIP_Real *costrev, PATH *path, int *vbase, int *heap, int *state)
Definition: graph_vnoi.c:517
int * nodes_base
Definition: graphdefs.h:330
#define Edge_anti(a)
Definition: graphdefs.h:106
#define EQ(a, b)
Definition: portab.h:79
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
int SCIPStpunionfindFind(UF *uf, int element)
Definition: misc_stp.c:885
void graph_vnoiFree(SCIP *scip, VNOI **vnoi)
Definition: graph_vnoi.c:1348
#define STP_PCSPG
Definition: graphdefs.h:44
#define LT(a, b)
Definition: portab.h:81
SCIP_RETCODE graph_vnoiCompute(SCIP *scip, const GRAPH *graph, VNOI *vnoi)
Definition: graph_vnoi.c:1302
unsigned char STP_Bool
Definition: portab.h:34
static SCIP_Real reduce_sdprofitGetProfit(const SDPROFIT *sdprofit, int node, int nonsource1, int nonsource2)
Definition: reducedefs.h:178
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
void graph_heap_free(SCIP *, SCIP_Bool, SCIP_Bool, DHEAP **)
Definition: graph_util.c:1034
#define GT(a, b)
Definition: portab.h:84
#define SCIP_Bool
Definition: def.h:84
int *RESTRICT path_heap
Definition: graphdefs.h:255
int *RESTRICT tail
Definition: graphdefs.h:223
void graph_voronoiRepairMult(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, const STP_Bool *nodesmark, int *RESTRICT count, int *RESTRICT vbase, int *RESTRICT boundedges, int *RESTRICT nboundedges, UF *RESTRICT uf, PATH *RESTRICT path)
Definition: graph_vnoi.c:1206
int *RESTRICT term
Definition: graphdefs.h:196
SCIP_Bool graph_pc_isPc(const GRAPH *)
#define CONNECT
Definition: graphdefs.h:87
Portable definitions.
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
SCIP_RETCODE graph_vnoiInit(SCIP *scip, const GRAPH *graph, SCIP_Bool useBufferArrays, VNOI **vnoi)
Definition: graph_vnoi.c:1265
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *, int)
SCIP_Real * cost
Definition: graphdefs.h:221
SCIP_Bool graph_edge_isInRange(const GRAPH *, int)
Definition: graph_stats.c:110
SCIP_RETCODE graph_heap_create(SCIP *, int, int *, DENTRY *, DHEAP **)
Definition: graph_util.c:992
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
#define SCIP_Real
Definition: def.h:177
int graph_heap_deleteMinReturnNode(DHEAP *)
Definition: graph_util.c:1076
int *RESTRICT outbeg
Definition: graphdefs.h:204
int edges
Definition: graphdefs.h:219
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
SCIP_RETCODE graph_voronoiWithRadius(SCIP *scip, const GRAPH *graph, GRAPH *adjgraph, PATH *path, SCIP_Real *rad, SCIP_Real *cost, SCIP_Real *costrev, int *vbase, int *heap, int *state)
Definition: graph_vnoi.c:774
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
static void vnoiComputeImplied(const GRAPH *g, const SDPROFIT *sdprofit, DHEAP *dheap, VNOI *vnoi)
Definition: graph_vnoi.c:201
#define UNKNOWN
Definition: sepa_mcf.c:4095
SCIP_Real * nodes_dist
Definition: graphdefs.h:328
#define nnodes
Definition: gastrans.c:65
static int nearest(int *RESTRICT heap, int *RESTRICT state, int *RESTRICT count, const PATH *path)
Definition: graph_vnoi.c:76
includes various reduction methods for Steiner tree problems
#define STP_RPCSPG
Definition: graphdefs.h:45
#define STP_MWCSP
Definition: graphdefs.h:51
void graph_heap_correct(int, SCIP_Real, DHEAP *)
Definition: graph_util.c:1166
SCIP_RETCODE graph_voronoiWithDist(SCIP *scip, const GRAPH *g, const SCIP_Bool *nodes_isTerm, const SCIP_Real *cost, SCIP_Real *distance, int *edges_isMinedgePred, int *vbase, int *minarc, int *distnode, PATH *path)
Definition: graph_vnoi.c:597