Scippy

SCIP

Solving Constraint Integer Programs

extreduce_dist.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 scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file extreduce_dist.c
17  * @brief (special) distance computation methods for Steiner tree extended reductions
18  * @author Daniel Rehfeldt
19  *
20  * This file implements methods for Steiner tree problem extended reduction techniques
21  * to compute and recompute (special) distances between vertices.
22  *
23  * A list of all interface methods can be found in extreduce.h.
24  *
25  */
26 
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
28 
29 
30 // #define SCIP_DEBUG
31 #include "extreduce.h"
32 #include "misc_stp.h"
33 #include "portab.h"
34 
35 
36 
37 #ifdef RED_UTIL_TIME
38 #include <time.h>
39 #endif
40 
41 #define EDGE_FORBIDDEN_NONE -2
42 
43 /** auxiliary data for (single) closenodes run*/
44 typedef struct close_nodes_run
45 {
46  int* prededge; /**< predecessors */
47  SCIP_Bool* edgemark; /**< debug only */
48  int startvertex; /**< start vertex */
49  SCIP_Bool is_buildphase; /**< in build up phase? */
50 } CNODESRUN;
51 
52 
53 /**@name Local methods
54  *
55  * @{
56  */
57 
58 /** returns entry of element within sorted array of size arraysize, or -1 if element could not be found
59  * NOTE: optimized binary search */
60 static inline
62  const int* array, /**< array */
63  unsigned int arraysize, /**< size */
64  int element /**< element to look for */
65  )
66 {
67  unsigned int lower = 0;
68  unsigned int shift = arraysize;
69 
70 #ifndef NDEBUG
71  assert(arraysize > 0);
72  for( unsigned int i = 1; i < arraysize; i++ )
73  assert(array[i - 1] < array[i] );
74 #endif
75 
76  while( shift > 1 )
77  {
78  const unsigned int middle = shift / 2;
79 
80  if( element >= array[lower + middle] )
81  lower += middle;
82 
83  shift -= middle;
84  }
85 
86  if( element == array[lower] )
87  return lower;
88 
89  return -1;
90 }
91 
92 
93 /** it the path between node and the close node forbidden?
94  * todo better have an additional closenodes_ancestor that saves the previous node! */
95 static inline
97  const GRAPH* g, /**< graph data structure */
98  const DISTDATA* distdata, /**< to be initialized */
99  int edge_forbidden, /**< forbidden edge */
100  const SCIP_Bool* edges_isForbidden, /**< blocked edges marked (half) */
101  int node, /**< the node */
102  int closenode, /**< the close node */
103  int closenode_pos /**< the close node position */
104 
105 )
106 {
107  const int* const indices = distdata->closenodes_indices;
108  const int* const prededges = distdata->closenodes_prededges;
109  const RANGE* const range = distdata->closenodes_range;
110  const int node_startpos = range[node].start;
111  const int size = range[node].end - node_startpos;
112  int pred = closenode;
113  int pred_pos = closenode_pos;
114  SCIP_Bool isForbidden = FALSE;
115 
116  assert(distdata->closenodes_indices[closenode_pos] == closenode);
117  assert(graph_edge_isInRange(g, prededges[pred_pos]));
118  assert(g->head[prededges[pred_pos]] == closenode);
119  assert(pred != node);
120  assert(size > 0);
121 
122 
123  // printf("check path %d->%d \n", node, closenode);
124 
125  while( pred != node )
126  {
127  int pred_edge;
128  int pred_edgeHalf;
129 
130  /* not in first iteration? */
131  if( pred != closenode )
132  pred_pos = node_startpos + findEntryFromSorted(&indices[node_startpos], size, pred);
133 
134  assert(pred_pos >= node_startpos);
135 
136  pred_edge = prededges[pred_pos];
137  assert(graph_edge_isInRange(g, pred_edge));
138 
139  // graph_edge_printInfo(g, pred_edge);
140 
141  pred_edgeHalf = pred_edge / 2;
142 
143  if( edges_isForbidden && edges_isForbidden[pred_edgeHalf] )
144  {
145  isForbidden = TRUE;
146  break;
147  }
148 
149  if( pred_edgeHalf == (edge_forbidden / 2) )
150  {
151  isForbidden = TRUE;
152  break;
153  }
154 
155  pred = g->tail[pred_edge];
156  }
157 
158  return isForbidden;
159 }
160 
161 
162 /** gets distance and path nodes */
163 static inline
165  const GRAPH* g, /**< graph data structure */
166  const DISTDATA* distdata, /**< distance data */
167  int node, /**< the node */
168  int closenode, /**< the close node whose position is to be found */
169  int* pathnodes, /**< inner nodes */
170  int* npathnodes /**< number of inner nodes */
171 )
172 {
173  const int* const indices = distdata->closenodes_indices;
174  const RANGE* const range = distdata->closenodes_range;
175  const int start = range[node].start;
176  const int end = range[node].end;
177  const int size = end - start;
178  int position;
179  SCIP_Real dist = -1.0;
180  assert(size > 0);
181 
182  *npathnodes = 0;
183 
184  position = findEntryFromSorted(&indices[start], size, closenode);
185 
186  if( position >= 0 )
187  {
188  const int* const prededges = distdata->closenodes_prededges;
189  int pred = closenode;
190  int pred_pos = start + position;
191 
192  assert(indices[pred_pos] == closenode);
193  assert(graph_edge_isInRange(g, prededges[pred_pos]));
194  assert(g->head[prededges[pred_pos]] == closenode);
195  assert(pred != node && closenode != node);
196 
197  dist = distdata->closenodes_distances[start + position];
198 
199  while( pred != node )
200  {
201  int pred_edge;
202 
203  /* not in first iteration? */
204  if( pred != closenode )
205  {
206  pred_pos = start + findEntryFromSorted(&indices[start], size, pred);
207  pathnodes[(*npathnodes)++] = pred;
208  }
209 
210  assert(pred_pos >= start);
211 
212  pred_edge = prededges[pred_pos];
213  assert(graph_edge_isInRange(g, pred_edge));
214 
215  pred = g->tail[pred_edge];
216  }
217  }
218 
219  return dist;
220 }
221 
222 
223 /** returns distance of closenode from node, or -1.0 if this distance is not stored in close nodes list of node */
224 static inline
226  const DISTDATA* distdata, /**< to be initialized */
227  int node, /**< the node */
228  int closenode /**< the close node whose position is to be found */
229 )
230 {
231  const int* const indices = distdata->closenodes_indices;
232  const RANGE* const range = distdata->closenodes_range;
233  const int start = range[node].start;
234  const int end = range[node].end;
235  const int size = end - start;
236  int position;
237  SCIP_Real dist = -1.0;
238 
239  assert(size >= 0);
240 
241  if( size == 0 )
242  {
243  assert(distdata->hasPathReplacement);
244  return dist;
245  }
246 
247  position = findEntryFromSorted(&indices[start], size, closenode);
248 
249  if( position >= 0 )
250  {
251  assert(indices[start + position] == closenode);
252  dist = distdata->closenodes_distances[start + position];
253  }
254 
255  return dist;
256 }
257 
258 
259 /** as above, but with forbidden edge */
260 static inline
262  const GRAPH* g, /**< graph data structure */
263  const DISTDATA* distdata, /**< to be initialized */
264  int edge_forbidden, /**< forbidden edge */
265  const SCIP_Bool* edges_isForbidden, /**< blocked edges marked or NULL */
266  int node, /**< the node */
267  int closenode /**< the close node whose position is to be found */
268 )
269 {
270  const int* const indices = distdata->closenodes_indices;
271  const RANGE* const range = distdata->closenodes_range;
272  const int start = range[node].start;
273  const int end = range[node].end;
274  const int size = end - start;
275  int position;
276  SCIP_Real dist = -1.0;
277 
278  assert(size >= 0);
279 
280  if( size == 0 )
281  {
282  assert(distdata->hasPathReplacement);
283  return dist;
284  }
285 
286  position = findEntryFromSorted(&indices[start], size, closenode);
287 
288  if( position >= 0 )
289  {
290  assert(indices[start + position] == closenode);
291 
292  if( !closeNodesPathIsForbidden(g, distdata, edge_forbidden, edges_isForbidden, node, closenode, start + position) )
293  {
294  dist = distdata->closenodes_distances[start + position];
295  }
296  }
297 
298  return dist;
299 }
300 
301 
302 /** as above, but with forbidden last edge */
303 static inline
305  const GRAPH* g, /**< graph data structure */
306  const DISTDATA* distdata, /**< to be initialized */
307  int node, /**< the node */
308  int closenode, /**< the close node whose position is to be found */
309  int lastedge_node2close /**< last edge */
310 )
311 {
312  const int* const prededges = distdata->closenodes_prededges;
313  const int* const indices = distdata->closenodes_indices;
314  const RANGE* const range = distdata->closenodes_range;
315  const int start = range[node].start;
316  const int end = range[node].end;
317  const int size = end - start;
318  int position_rel;
319  SCIP_Real dist = -1.0;
320 
321  if( size == 0 )
322  {
323  assert(distdata->hasPathReplacement);
324  return dist;
325  }
326 
327  assert(size > 0);
328  assert(graph_edge_isInRange(g, lastedge_node2close));
329  assert(g->head[lastedge_node2close] == closenode);
330 
331  position_rel = findEntryFromSorted(&indices[start], size, closenode);
332 
333  if( position_rel >= 0 )
334  {
335  const int position_abs = start + position_rel;
336  const int prededge = prededges[position_abs];
337 
338  assert(indices[position_abs] == closenode);
339  assert(graph_edge_isInRange(g, prededge));
340 
341  if( prededge != lastedge_node2close )
342  {
343  assert((prededge / 2) != (lastedge_node2close / 2));
344 
345  dist = distdata->closenodes_distances[position_abs];
346  }
347  }
348 
349  return dist;
350 }
351 
352 
353 /** as above, but with forbidden edge/edges and known equality value */
354 static inline
356  const GRAPH* g, /**< graph data structure */
357  const DISTDATA* distdata, /**< to be initialized */
358  SCIP_Real dist_eq, /**< critical distance or -1.0 if not known */
359  int edge_forbidden, /**< forbidden edge */
360  const SCIP_Bool* edges_isForbidden, /**< blocked edges marked */
361  int node, /**< the node */
362  int closenode /**< the close node whose position is to be found */
363 )
364 {
365  const int* const indices = distdata->closenodes_indices;
366  const RANGE* const range = distdata->closenodes_range;
367  const int start = range[node].start;
368  const int end = range[node].end;
369  const int size = end - start;
370  int position;
371  SCIP_Real dist = -1.0;
372 
373  if( size == 0 )
374  {
375  assert(distdata->hasPathReplacement);
376  return dist;
377  }
378 
379  assert(size > 0);
380 
381  position = findEntryFromSorted(&indices[start], size, closenode);
382 
383  if( position >= 0 )
384  {
385  assert(indices[start + position] == closenode);
386  dist = distdata->closenodes_distances[start + position];
387 
388  if( GT(dist, dist_eq) )
389  {
390  dist = -1.0;
391  }
392  else if( EQ(dist, dist_eq) )
393  {
394  if( closeNodesPathIsForbidden(g, distdata, edge_forbidden, edges_isForbidden, node,
395  closenode, start + position) )
396  {
397  dist = -1.0;
398  }
399  }
400  }
401 
402  return dist;
403 }
404 
405 
406 /** compute paths root list */
407 static inline
409  SCIP* scip, /**< SCIP */
410  const GRAPH* g, /**< graph data structure */
411  int halfedge, /**< halfedge to insert at */
412  int root, /**< root to insert */
413  DISTDATA* distdata /**< distance data */
414 )
415 {
416  int* const pathroot_blocksizes = distdata->pathroot_blocksizes;
417  int* const pathroot_blocksizesmax = distdata->pathroot_blocksizesmax;
418 
419  assert(scip && g && distdata && pathroot_blocksizes && pathroot_blocksizesmax);
420  assert(halfedge >= 0 && halfedge < g->edges / 2);
421  assert(root >= 0 && root < g->knots);
422  assert(pathroot_blocksizes[halfedge] <= pathroot_blocksizesmax[halfedge]);
423 
424  /* need to reallocate? */
425  if( pathroot_blocksizes[halfedge] == pathroot_blocksizesmax[halfedge] )
426  {
427  const int oldsize = pathroot_blocksizesmax[halfedge];
428  int newsize;
429 
430  assert(oldsize >= 0);
431 
432  if( oldsize == 0 )
433  {
434  assert(distdata->pathroot_blocks[halfedge] == NULL);
435  newsize = 2;
436  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(distdata->pathroot_blocks[halfedge]), newsize) );
437  }
438  else
439  {
440  assert(distdata->pathroot_blocks[halfedge] != NULL);
441  newsize = 2 * pathroot_blocksizesmax[halfedge];
442  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(distdata->pathroot_blocks[halfedge]), oldsize, newsize) );
443  }
444 
445  pathroot_blocksizesmax[halfedge] = newsize;
446  }
447 
448  assert(pathroot_blocksizes[halfedge] < pathroot_blocksizesmax[halfedge] );
449 
450  /* now add the root */
451  distdata->pathroot_blocks[halfedge][pathroot_blocksizes[halfedge]].pathroot_id = root;
452  distdata->pathroot_blocks[halfedge][pathroot_blocksizes[halfedge]++].pathroot_nrecomps = distdata->pathroot_nrecomps[root];
453 
454  return SCIP_OKAY;
455 }
456 
457 
458 /** compute paths root list */
459 static
461  SCIP* scip, /**< SCIP */
462  const GRAPH* g, /**< graph data structure */
463  DISTDATA* distdata /**< to be initialized */
464  )
465 {
466  int* pathroot_blocksizes;
467  int* pathroot_blocksizesmax;
468  int* pathroot_blockcount;
469  PRSTATE** pathroot_blocks;
470  const int* const closenodes_prededges = distdata->closenodes_prededges;
471  const int nnodes = g->knots;
472  const int halfnedges = g->edges / 2;
473  const RANGE* const range_closenodes = distdata->closenodes_range;
474 
475  assert(scip && g && closenodes_prededges && distdata);
476 
477  SCIP_CALL( SCIPallocMemoryArray(scip, &(distdata->pathroot_nrecomps), nnodes) );
478  SCIP_CALL( SCIPallocMemoryArray(scip, &(distdata->pathroot_isdirty), nnodes) );
479 
480  for( int i = 0; i < nnodes; i++ )
481  distdata->pathroot_isdirty[i] = FALSE;
482 
483  for( int i = 0; i < nnodes; i++ )
484  distdata->pathroot_nrecomps[i] = 0;
485 
486  SCIP_CALL( SCIPallocMemoryArray(scip, &(pathroot_blocks), halfnedges) );
487  SCIP_CALL( SCIPallocMemoryArray(scip, &(pathroot_blocksizes), halfnedges) );
488  SCIP_CALL( SCIPallocMemoryArray(scip, &(pathroot_blocksizesmax), halfnedges) );
489 
490  SCIP_CALL( SCIPallocBufferArray(scip, &(pathroot_blockcount), halfnedges) );
491 
492  for( int k = 0; k < halfnedges; k++ )
493  pathroot_blocksizes[k] = 0;
494 
495  /* compute the edge range sizes */
496  for( int j = 0; j < range_closenodes[nnodes - 1].end; j++ )
497  {
498  const int edge = closenodes_prededges[j] / 2;
499  assert(edge >= 0 && edge < halfnedges);
500  assert(g->oeat[2 * edge] != EAT_FREE);
501 
502  pathroot_blocksizes[edge]++;
503  }
504 
505  for( int e = 0; e < halfnedges; e++ )
506  {
507  const int size = pathroot_blocksizes[e];
508 
509  /* is edge used? */
510  if( size > 0 )
511  {
512  assert(g->oeat[2 * e] != EAT_FREE);
513 
514  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pathroot_blocks[e]), size) );
515  }
516  else
517  {
518  pathroot_blocks[e] = NULL;
519  }
520  }
521 
522  /* fill the path roots in */
523 
524  for( int k = 0; k < halfnedges; k++ )
525  pathroot_blockcount[k] = 0;
526 
527  for( int k = 0; k < nnodes; k++ )
528  {
529  if( g->grad[k] == 0 )
530  continue;
531 
532  for( int j = range_closenodes[k].start; j < range_closenodes[k].end; j++ )
533  {
534  const int edge = closenodes_prededges[j] / 2;
535  const int blockcount = pathroot_blockcount[edge];
536 
537  assert(edge >= 0 && edge < halfnedges);
538  assert(g->oeat[2 * edge] != EAT_FREE);
539  assert(blockcount < pathroot_blocksizes[edge]);
540 
541  pathroot_blocks[edge][blockcount].pathroot_id = k;
542  pathroot_blocks[edge][blockcount].pathroot_nrecomps = 0;
543 
544  pathroot_blockcount[edge]++;
545  }
546  }
547 
548 #ifndef NDEBUG
549  for( int e = 0; e < halfnedges; e++ )
550  assert(pathroot_blockcount[e] == pathroot_blocksizes[e]);
551 #endif
552 
553  for( int k = 0; k < halfnedges; k++ )
554  pathroot_blocksizesmax[k] = pathroot_blocksizes[k];
555 
556  distdata->pathroot_blocks = pathroot_blocks;
557  distdata->pathroot_blocksizes = pathroot_blocksizes;
558  distdata->pathroot_blocksizesmax = pathroot_blocksizesmax;
559 
560  SCIPfreeBufferArray(scip, &pathroot_blockcount);
561 
562  return SCIP_OKAY;
563 }
564 
565 
566 /** initializes run from 'startvertex' */
567 static inline
569  SCIP* scip, /**< SCIP */
570  const GRAPH* g, /**< graph data structure */
571  DISTDATA* distdata, /**< distance data */
572  CNODESRUN* cnodesrun /**< auxiliary data */
573 )
574 {
575  DIJK* const dijkdata = distdata->dijkdata;
576  SCIP_Real* const dist = dijkdata->node_distance;
577  DHEAP* const dheap = dijkdata->dheap;
578  const int nnodes = g->knots;
579  const int startvertex = cnodesrun->startvertex;
580 
581  assert(dheap->size == 0 && distdata->closenodes_maxnumber > 0);
582  assert(graph_knot_isInRange(g, startvertex));
583  assert(distdata->closenodes_range[startvertex].start == distdata->closenodes_range[startvertex].end);
584 
585  SCIP_CALL( SCIPallocBufferArray(scip, &(cnodesrun->prededge), nnodes) );
586 
587 #ifndef NDEBUG
588  SCIP_CALL( SCIPallocMemoryArray(scip, &(cnodesrun->edgemark), g->edges / 2) );
589 
590  for( int e = 0; e < g->edges / 2; e++ )
591  (cnodesrun->edgemark)[e] = FALSE;
592 
593  for( int k = 0; k < nnodes; k++ )
594  {
595  (cnodesrun->prededge)[k] = -1;
596  assert(dist[k] == FARAWAY && dheap->position[k] == UNKNOWN);
597  }
598 #endif
599 
600  dist[startvertex] = 0.0;
601  dijkdata->visitlist[0] = startvertex;
602  graph_heap_correct(startvertex, 0.0, dheap);
603 
604  dijkdata->nvisits = 1;
605 
606  assert(dheap->size == 1);
607 
608  return SCIP_OKAY;
609 }
610 
611 
612 /** computes sorted shortest path list to constant number of neighbors */
613 static inline
615  SCIP* scip, /**< SCIP */
616  const GRAPH* g, /**< graph data structure */
617  CNODESRUN* cnodesrun, /**< auxiliary data */
618  DISTDATA* distdata /**< to be initialized */
619  )
620 {
621  const SDPROFIT* sdprofit = NULL;
622  DIJK* const dijkdata = distdata->dijkdata;
623  int* const visitlist = dijkdata->visitlist;
624  SCIP_Real* const dist = dijkdata->node_distance;
625  DHEAP* const dheap = dijkdata->dheap;
626  STP_Bool* const visited = dijkdata->node_visited;
627  int* const prededge = cnodesrun->prededge;
628  int* const state = dheap->position;
629  DCSR* const dcsr = g->dcsr_storage;
630  const RANGE* const RESTRICT range_csr = dcsr->range;
631  const int* const RESTRICT head_csr = dcsr->head;
632  const int* const edgeid = dcsr->edgeid;
633  const SCIP_Real* const RESTRICT cost_csr = dcsr->cost;
634  const SCIP_Real* const pc_costshifts = dijkdata->node_bias;
635  RANGE* const range_closenodes = distdata->closenodes_range;
636  int* const closenodes_indices = distdata->closenodes_indices;
637  int* const closenodes_prededges = distdata->closenodes_prededges;
638  SCIP_Real* const closenodes_distances = distdata->closenodes_distances;
639  int nvisits = dijkdata->nvisits;
640  int nclosenodes = 0;
641  const int startvertex = cnodesrun->startvertex;
642  const int closenodes_limit = distdata->closenodes_maxnumber;
643  const SCIP_Bool isPc = graph_pc_isPc(g);
644  const SCIP_Bool withProfit = (distdata->sdistdata != NULL && distdata->sdistdata->sdprofit != NULL);
645  const SCIP_Bool is_buildphase = cnodesrun->is_buildphase;
646 
647  assert(dcsr && dist && visitlist && visited && dheap && prededge && cnodesrun->edgemark);
648  assert(range_closenodes && closenodes_indices && closenodes_prededges);
649  assert(dheap->size == 1);
650  assert(!isPc || pc_costshifts);
651 
652  if( withProfit )
653  sdprofit = distdata->sdistdata->sdprofit;
654 
655  /* main loop */
656  while( dheap->size > 0 )
657  {
658  /* get nearest labeled node */
659  const int k = graph_heap_deleteMinReturnNode(dheap);
660  const int k_start = range_csr[k].start;
661  const int k_end = range_csr[k].end;
662  const SCIP_Real k_dist = dist[k];
663  int k_pred = -1;
664 
665  if( k != startvertex )
666  {
667  const int closenodes_pos = range_closenodes[startvertex].end;
668 
669 #ifndef NDEBUG
670  assert(graph_edge_isInRange(g, prededge[k]));
671  assert(cnodesrun->edgemark[prededge[k] / 2] == FALSE); /* make sure that the edge is not marked twice */
672  assert(closenodes_pos < distdata->closenodes_totalsize && state[k] == CONNECT);
673 
674  cnodesrun->edgemark[prededge[k] / 2] = TRUE;
675 #endif
676 
677  closenodes_indices[closenodes_pos] = k;
678  closenodes_distances[closenodes_pos] = isPc ? (k_dist + pc_costshifts[k]) : (k_dist);
679 
680  if( is_buildphase )
681  {
682  closenodes_prededges[closenodes_pos] = prededge[k];
683  }
684  else
685  {
686  closenodes_prededges[closenodes_pos] = prededge[k];
687  SCIP_CALL( distDataPathRootsInsertRoot(scip, g, prededge[k] / 2, startvertex, distdata) );
688  }
689 
690  range_closenodes[startvertex].end++;
691 
692  if( ++nclosenodes >= closenodes_limit )
693  break;
694 
695  if( withProfit )
696  k_pred = g->tail[prededge[k]];
697  }
698 
699  /* correct adjacent nodes */
700  for( int e = k_start; e < k_end; e++ )
701  {
702  const int m = head_csr[e];
703  assert(g->mark[m]);
704 
705  if( state[m] != CONNECT )
706  {
707  SCIP_Real distnew = isPc ?
708  k_dist + cost_csr[e] - pc_costshifts[m]
709  : k_dist + cost_csr[e];
710 
711  assert(GE(distnew, 0.0));
712 
713  if( withProfit && m != k_pred )
714  {
715  SCIP_Real profitBias = reduce_sdprofitGetProfit(sdprofit, k, m, k_pred);
716  profitBias = MIN(profitBias, cost_csr[e]);
717  profitBias = MIN(profitBias, k_dist);
718  distnew -= profitBias;
719  }
720 
721  if( LT(distnew, dist[m]) )
722  {
723  if( !visited[m] )
724  {
725  visitlist[nvisits++] = m;
726  visited[m] = TRUE;
727  }
728 
729  dist[m] = distnew;
730  prededge[m] = edgeid[e];
731  graph_heap_correct(m, distnew, dheap);
732  }
733  }
734  }
735  }
736 
737  dijkdata->nvisits = nvisits;
738 
739  return SCIP_OKAY;
740 }
741 
742 
743 /** sort close nodes list of node */
744 static inline
746  const GRAPH* g, /**< graph data structure */
747  int node, /**< the node to sort for */
748  DISTDATA* distdata /**< to be initialized */
749 )
750 {
751  const RANGE* const range_closenodes = distdata->closenodes_range;
752  int* const closenodes_indices = distdata->closenodes_indices;
753  SCIP_Real* const closenodes_distances = distdata->closenodes_distances;
754  const int start = range_closenodes[node].start;
755  const int length = range_closenodes[node].end - start;
756 
757  assert(g && distdata);
758  assert(node >= 0 && node < g->knots);
759  assert(g->grad[node] > 0);
760  assert(length >= 0);
761  assert(distdata->closenodes_prededges);
762 
763  SCIPsortIntIntReal(&closenodes_indices[start], &(distdata->closenodes_prededges[start]), &closenodes_distances[start], length);
764 
765 #ifndef NDEBUG
766  for( int i = 1; i < length; i++ )
767  assert(closenodes_indices[start] < closenodes_indices[start + i]);
768 #endif
769 }
770 
771 
772 /** exits */
773 static inline
775  SCIP* scip, /**< SCIP */
776  CNODESRUN* cnodesrun /**< auxiliary data */
777 )
778 {
779  SCIPfreeMemoryArrayNull(scip, &(cnodesrun ->edgemark));
780  SCIPfreeBufferArray(scip, &(cnodesrun ->prededge));
781 }
782 
783 
784 #ifdef RED_UTIL_TIME
785 
786 typedef struct pathroot_info
787 {
788  int pathroot_id;
789 } PRINFO;
790 
791 //#define USE_STRUCT
792 /** compute paths root list */
793 static
794 SCIP_RETCODE distDataPathRootsInitializeBench(
795  SCIP* scip, /**< SCIP */
796  const GRAPH* g, /**< graph data structure */
797  int* closenodes_edges, /**< edges used to reach close nodes */
798  DISTDATA* distdata /**< to be initialized */
799  )
800 {
801  int* pathroot_blocksizes;
802 #ifdef USE_STRUCT
803  PRINFO** pathroot_blocks;
804 #else
805  int** pathroot_blocks;
806 
807 #endif
808  const int halfnedges = 1000000;
809 
810 
811  clock_t start, end;
812  double cpu_time_used;
813 
814  start = clock();
815 
816 
817  SCIP_CALL( SCIPallocMemoryArray(scip, &(pathroot_blocks), halfnedges) );
818  SCIP_CALL( SCIPallocMemoryArray(scip, &(pathroot_blocksizes), halfnedges) );
819 
820 
821  for( int e = 0; e < halfnedges; e++ )
822  {
823  const int size = 1 + halfnedges % 32;
824 
825  /* is edge used? */
826  if( size > 0 )
827  {
828  assert(g->oeat[2 * e] != EAT_FREE);
829 
830  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pathroot_blocks[e]), size) );
831 #ifdef USE_STRUCT
832  pathroot_blocks[e][0].pathroot_id = size;
833 #else
834  pathroot_blocks[e][0] = size;
835 #endif
836  }
837  else
838  {
839  pathroot_blocks[e] = NULL;
840  }
841  }
842 
843 
844  for( int e = halfnedges - 1; e >= 0 ; e-- )
845  {
846 #ifdef USE_STRUCT
847  const int size = pathroot_blocks[e][0].pathroot_id;
848 #else
849  const int size = pathroot_blocks[e][0];
850 #endif
851 
852  /* is edge used? */
853  if( size > 0 )
854  {
855  assert(pathroot_blocks[e] != NULL);
856 
857  SCIPfreeBlockMemoryArray(scip, &(pathroot_blocks[e]), size);
858  }
859  else
860  {
861  assert(pathroot_blocks[e] == NULL);
862  }
863  }
864 
865  SCIPfreeMemoryArray(scip, &pathroot_blocksizes);
866  SCIPfreeMemoryArray(scip, &pathroot_blocks);
867 
868  end = clock();
869  cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
870 
871  printf("time %f \n", cpu_time_used);
872 
873  exit(1);
874 
875  return SCIP_OKAY;
876 }
877 #endif
878 
879 /** frees paths root list */
880 static
882  SCIP* scip, /**< SCIP */
883  const GRAPH* g, /**< graph data structure */
884  DISTDATA* distdata /**< to be initialized */
885  )
886 {
887  int* pathroot_blocksizesmax;
888  PRSTATE** pathroot_blocks;
889  const int halfnedges = g->edges / 2;
890 
891  assert(scip && g && distdata);
892 
893  pathroot_blocksizesmax = distdata->pathroot_blocksizesmax;
894  pathroot_blocks = distdata->pathroot_blocks;
895 
896  for( int e = halfnedges - 1; e >= 0 ; e-- )
897  {
898  const int maxsize = pathroot_blocksizesmax[e];
899 
900  /* is edge used? */
901  if( maxsize > 0 )
902  {
903  assert(pathroot_blocks[e] != NULL);
904 
905  SCIPfreeBlockMemoryArray(scip, &(pathroot_blocks[e]), maxsize);
906  }
907  else
908  {
909  assert(pathroot_blocks[e] == NULL);
910  }
911  }
912 
914  SCIPfreeMemoryArray(scip, &distdata->pathroot_blocksizes);
915  SCIPfreeMemoryArray(scip, &distdata->pathroot_blocks);
916  SCIPfreeMemoryArray(scip, &distdata->pathroot_isdirty);
917  SCIPfreeMemoryArray(scip, &distdata->pathroot_nrecomps);
918 }
919 
920 
921 /** computes sorted shortest path list to constant number of neighbors */
922 static
924  SCIP* scip, /**< SCIP */
925  const GRAPH* g, /**< graph data structure */
926  CNODESRUN* cnodesrun, /**< auxiliary data */
927  DISTDATA* distdata /**< to be initialized */
928  )
929 {
930  assert(scip && g && distdata && cnodesrun);
931 
932  SCIP_CALL( closeNodesRunInit(scip, g, distdata, cnodesrun) );
933 
934  SCIP_CALL( closeNodesRunCompute(scip, g, cnodesrun, distdata) );
935 
936  closeNodesRunExit(scip, cnodesrun);
937 
938  /* sort close nodes according to their index */
939  closeNodesRunSort(g, cnodesrun->startvertex, distdata);
940 
941  return SCIP_OKAY;
942 }
943 
944 
945 /** sets sizes */
946 static
948  const GRAPH* g, /**< graph data structure */
949  int maxnclosenodes, /**< maximum number of close nodes to each node */
950  DISTDATA* distdata /**< to be initialized */
951 )
952 {
953  int nnodes_undeleted;
954  int closenodes_totalsize;
955 
956  graph_get_nVET(g, &nnodes_undeleted, NULL, NULL);
957  assert(nnodes_undeleted >= 1 && maxnclosenodes >= 1);
958 
959  closenodes_totalsize = nnodes_undeleted * maxnclosenodes;
960 
961  assert(closenodes_totalsize >= 1);
962 
963  distdata->closenodes_totalsize = closenodes_totalsize;
964  distdata->closenodes_maxnumber = maxnclosenodes;
965 }
966 
967 
968 /** allocates memory for some distance data members */
969 static
971  SCIP* scip, /**< SCIP */
972  const GRAPH* g, /**< graph data structure */
973  DISTDATA* distdata /**< to be initialized */
974 )
975 {
976  const int nnodes = g->knots;
977  const int closenodes_totalsize = distdata->closenodes_totalsize;
978 
979  assert(scip && g && distdata);
980  assert(distdata->closenodes_totalsize > 0);
981 
982  SCIP_CALL( SCIPallocMemoryArray(scip, &(distdata->closenodes_range), nnodes) );
983  SCIP_CALL( SCIPallocMemoryArray(scip, &(distdata->closenodes_indices), closenodes_totalsize) );
984  SCIP_CALL( SCIPallocMemoryArray(scip, &(distdata->closenodes_distances), closenodes_totalsize) );
985  SCIP_CALL( SCIPallocMemoryArray(scip, &(distdata->closenodes_prededges), closenodes_totalsize) );
986 
987  return SCIP_OKAY;
988 }
989 
990 
991 /** re-compute close nodes for default distance from vertex1 */
992 static inline
994  SCIP* scip, /**< SCIP */
995  const GRAPH* g, /**< graph data structure */
996  int vertex1, /**< first vertex */
997  DISTDATA* distdata /**< distance data */
998 )
999 {
1000  CNODESRUN closenodes = { .edgemark = NULL, .prededge = NULL,
1001  .startvertex = vertex1, .is_buildphase = FALSE };
1002 
1003  assert(distdata->pathroot_isdirty[vertex1]);
1004  assert(!distdata->sdistdata || !distdata->sdistdata->sdprofit);
1005 
1006  distdata->pathroot_nrecomps[vertex1]++;
1007  SCIP_CALL_ABORT( distDataComputeCloseNodes(scip, g, &closenodes, distdata) );
1008 
1009  graph_dijkLimited_reset(g, distdata->dijkdata);
1010 
1011  SCIPdebugMessage("vertex %d is dirty, recompute \n", vertex1);
1012 
1013  distdata->pathroot_isdirty[vertex1] = FALSE;
1014 }
1015 
1016 
1017 /** returns (normal) shortest path distance between vertex1 and vertex2
1018  * and provides inner shortest path vertices. Returns -1.0 if no shortest path was found */
1019 static inline
1021  SCIP* scip, /**< SCIP */
1022  const GRAPH* g, /**< graph data structure */
1023  int vertex1, /**< first vertex */
1024  int vertex2, /**< second vertex */
1025  int* pathnodes, /**< inner nodes */
1026  int* npathnodes, /**< number of inner nodes */
1027  DISTDATA* distdata /**< distance data */
1028 )
1029 {
1030  SCIP_Real dist;
1031 
1032  /* neighbors list not valid anymore? */
1033  if( distdata->pathroot_isdirty[vertex1] )
1034  {
1035  distDataRecomputeNormalDist(scip, g, vertex1, distdata);
1036  }
1037 
1038  dist = getCloseNodePath(g, distdata, vertex1, vertex2, pathnodes, npathnodes);
1039 
1040  return dist;
1041 }
1042 
1043 
1044 /** Gets shortest v1->v2 (standard) distance.
1045  * Returns -1.0 if the distance is not known. */
1046 static inline
1048  SCIP* scip, /**< SCIP */
1049  const GRAPH* g, /**< graph data structure */
1050  int vertex1, /**< first vertex */
1051  int vertex2, /**< second vertex */
1052  DISTDATA* distdata /**< distance data */
1053 )
1054 {
1055  SCIP_Real dist;
1056 
1057  assert(distdata);
1058  assert(vertex1 >= 0 && vertex2 >= 0);
1059 
1060  /* neighbors list not valid anymore? */
1061  if( distdata->pathroot_isdirty[vertex1] )
1062  {
1063  /* recompute */
1064  distDataRecomputeNormalDist(scip, g, vertex1, distdata);
1065  }
1066 
1067  /* look in neighbors list of vertex1 */
1068  dist = getCloseNodeDistance(distdata, vertex1, vertex2);
1069 
1070  return dist;
1071 }
1072 
1073 
1074 /** as above, but with forbidden edge */
1075 static inline
1077  SCIP* scip, /**< SCIP */
1078  const GRAPH* g, /**< graph data structure */
1079  int edge_forbidden, /**< forbidden edge */
1080  const SCIP_Bool* edges_isForbidden, /**< blocked edges marked or NULL */
1081  int vertex1, /**< first vertex */
1082  int vertex2, /**< second vertex */
1083  DISTDATA* distdata /**< distance data */
1084 )
1085 {
1086  SCIP_Real dist;
1087 
1088  assert(distdata);
1089  assert(vertex1 >= 0 && vertex2 >= 0);
1090  assert(edge_forbidden == EDGE_FORBIDDEN_NONE || graph_edge_isInRange(g, edge_forbidden));
1091 
1092  /* neighbors list not valid anymore? */
1093  if( distdata->pathroot_isdirty[vertex1] )
1094  {
1095  distDataRecomputeNormalDist(scip, g, vertex1, distdata);
1096  }
1097 
1098  dist = getCloseNodeDistanceForbidden(g, distdata, edge_forbidden, edges_isForbidden, vertex1, vertex2);
1099 
1100  return dist;
1101 }
1102 
1103 
1104 /** as above, but with forbidden last edge */
1105 static inline
1107  SCIP* scip, /**< SCIP */
1108  const GRAPH* g, /**< graph data structure */
1109  int vertex1, /**< first vertex */
1110  int vertex2, /**< second vertex */
1111  int lastedge12, /**< forbidden last edge for v1->v2 path */
1112  DISTDATA* distdata /**< distance data */
1113 )
1114 {
1115  SCIP_Real dist;
1116 
1117  assert(distdata);
1118  assert(vertex1 >= 0 && vertex2 >= 0);
1119  assert(graph_edge_isInRange(g, lastedge12));
1120 
1121  /* neighbors list not valid anymore? */
1122  if( distdata->pathroot_isdirty[vertex1] )
1123  {
1124  distDataRecomputeNormalDist(scip, g, vertex1, distdata);
1125  }
1126 
1127  dist = getCloseNodeDistanceForbiddenLast(g, distdata, vertex1, vertex2, lastedge12);
1128 
1129  return dist;
1130 }
1131 
1132 /** as above, but with forbidden edges and known equality value */
1133 static inline
1135  SCIP* scip, /**< SCIP */
1136  const GRAPH* g, /**< graph data structure */
1137  SCIP_Real dist_eq, /**< critical distance */
1138  int edge_forbidden, /**< forbidden edge */
1139  const SCIP_Bool* edges_isForbidden, /**< blocked edges marked, or NULL */
1140  int vertex1, /**< first vertex */
1141  int vertex2, /**< second vertex */
1142  DISTDATA* distdata /**< distance data */
1143 )
1144 {
1145  SCIP_Real dist;
1146 
1147  assert(distdata);
1148  assert(vertex1 >= 0 && vertex2 >= 0);
1149  assert(graph_edge_isInRange(g, edge_forbidden));
1150 
1151  /* neighbors list not valid anymore? */
1152  if( distdata->pathroot_isdirty[vertex1] )
1153  {
1154  /* recompute */
1155  distDataRecomputeNormalDist(scip, g, vertex1, distdata);
1156  }
1157 
1158  /* look in neighbors list of vertex1 */
1159  dist = getCloseNodeDistanceForbiddenEq(g, distdata, dist_eq, edge_forbidden, edges_isForbidden, vertex1, vertex2);
1160 
1161  return dist;
1162 }
1163 
1164 
1165 /** returns v1->v2 special distance */
1166 static inline
1168  const GRAPH* g, /**< graph data structure */
1169  int vertex1, /**< first vertex */
1170  int vertex2, /**< second vertex */
1171  DISTDATA* distdata /**< distance data */
1172 )
1173 {
1174  SCIP_Real dist;
1175 
1176  assert(distdata);
1177  assert(vertex1 >= 0 && vertex2 >= 0);
1178  assert(distdata->sdistdata);
1179 
1180  dist = reduce_sdGetSd(g, vertex1, vertex2, FARAWAY, 0.0, distdata->sdistdata);
1181 
1182  return dist;
1183 }
1184 
1185 
1186 /** returns v1->v2 special distance, but only for SDs with intermediate terms */
1187 static inline
1189  const GRAPH* g, /**< graph data structure */
1190  int vertex1, /**< first vertex */
1191  int vertex2, /**< second vertex */
1192  DISTDATA* distdata /**< distance data */
1193 )
1194 {
1195  SCIP_Real dist;
1196 
1197  assert(distdata);
1198  assert(vertex1 >= 0 && vertex2 >= 0);
1199  assert(distdata->sdistdata);
1200 
1201  dist = reduce_sdGetSdIntermedTerms(g, vertex1, vertex2, FARAWAY, 0.0, distdata->sdistdata);
1202 
1203  return dist;
1204 }
1205 
1206 
1207 
1208 /**@} */
1209 
1210 /**@name Interface methods
1211  *
1212  * @{
1213  */
1214 
1215 
1216 
1217 /** initializes distance data */
1219  SCIP* scip, /**< SCIP */
1220  GRAPH* g, /**< graph data structure */
1221  int maxnclosenodes, /**< maximum number of close nodes to each node */
1222  SCIP_Bool computeSD, /**< also compute special distances? */
1223  SCIP_Bool useBias, /**< use bias? */
1224  DISTDATA** distdata /**< to be initialized */
1225 )
1226 {
1227  CNODESRUN closenodes = { NULL, NULL, -1, FALSE };
1228  const int nnodes = g->knots;
1229  RANGE* range_closenodes;
1230  DHEAP* dheap;
1231  DISTDATA* dist;
1232 
1233  assert(distdata && g && scip && g->dcsr_storage);
1234  assert(graph_valid_dcsr(g, FALSE));
1235  assert(!graph_pc_isPcMw(g) || !g->extended);
1236 
1237  SCIP_CALL( SCIPallocMemory(scip, distdata) );
1238  dist = *distdata;
1239  dist->hasPathReplacement = FALSE;
1240 
1241  distDataInitSizes(g, maxnclosenodes, dist);
1242  SCIP_CALL( distDataAllocateNodesArrays(scip, g, dist) );
1243 
1244  SCIP_CALL( graph_dijkLimited_init(scip, g, &(dist->dijkdata)) );
1245 
1246  if( graph_pc_isPc(g) )
1247  {
1249  }
1250 
1251  if( computeSD )
1252  {
1253  if( useBias )
1254  {
1255  SCIP_CALL( reduce_sdInitBiasedBottleneck(scip, g, &(dist->sdistdata)) );
1256  }
1257  else
1258  {
1259  SCIP_CALL( reduce_sdInit(scip, g, &(dist->sdistdata)) );
1260  }
1261  }
1262  else
1263  {
1264  assert(!useBias);
1265  dist->sdistdata = NULL;
1266  }
1267 
1268  range_closenodes = dist->closenodes_range;
1269 
1270  /* compute close nodes to each not yet deleted node */
1271  for( int k = 0; k < nnodes; k++ )
1272  {
1273  range_closenodes[k].start = (k == 0) ? 0 : range_closenodes[k - 1].end;
1274  range_closenodes[k].end = range_closenodes[k].start;
1275 
1276  if( !g->mark[k] )
1277  {
1278  assert(g->grad[k] == 0 || graph_pc_isPcMw(g));
1279  // assert(g->dcsr_storage->range[k].end == g->dcsr_storage->range[k].start);
1280 
1281  continue;
1282  }
1283 
1284  if( g->grad[k] == 0 )
1285  {
1286  assert(graph_pc_isPcMw(g));
1287  assert(graph_pc_knotIsNonLeafTerm(g, k));
1288 
1289  continue;
1290  }
1291 
1292  assert(g->grad[k] > 0);
1293 
1294  closenodes.startvertex = k;
1295  closenodes.is_buildphase = TRUE;
1296  SCIP_CALL( distDataComputeCloseNodes(scip, g, &closenodes, dist) );
1297 
1299  }
1300 
1301  /* store for each edge the roots of all paths it is used for */
1302  SCIP_CALL( distDataPathRootsInitialize(scip, g, dist) );
1303 
1304  SCIP_CALL( graph_heap_create(scip, nnodes, NULL, NULL, &dheap) );
1305  dist->dheap = dheap;
1306 
1307  assert(dist->closenodes_prededges);
1308  assert(useBias || extreduce_distCloseNodesAreValid(scip, g, dist));
1309 
1310  return SCIP_OKAY;
1311 }
1312 
1313 
1314 /** updates data for edge deletion */
1316  SCIP* scip, /**< SCIP */
1317  const GRAPH* g, /**< graph data structure */
1318  int edge, /**< edge to be deleted */
1319  DISTDATA* distdata /**< distance data */
1320 )
1321 {
1322  const int halfedge = edge / 2;
1323  PRSTATE* const pathrootblock = distdata->pathroot_blocks[halfedge];
1324  SCIP_Bool* const node_isdirty = distdata->pathroot_isdirty;
1325  RANGE* const range_closenodes = distdata->closenodes_range;
1326  const int* const node_nrecomps = distdata->pathroot_nrecomps;
1327  const int npathroots = distdata->pathroot_blocksizes[halfedge];
1328 
1329  assert(scip && distdata && distdata->pathroot_blocks);
1330  assert(edge >= 0);
1331  // assert(g->oeat[edge] == EAT_FREE && g->ieat[edge] == EAT_FREE);
1332 
1333  for( int k = 0; k < npathroots; k++ )
1334  {
1335  const int node = pathrootblock[k].pathroot_id;
1336  const int nrecomps = pathrootblock[k].pathroot_nrecomps;
1337 
1338  if( nrecomps == node_nrecomps[node] && !node_isdirty[node] )
1339  {
1340  node_isdirty[node] = TRUE;
1341 
1342 #ifndef NDEBUG
1343  for( int j = range_closenodes[node].start; j < range_closenodes[node].end; j++ )
1344  {
1345  distdata->closenodes_indices[j] = -1;
1346  distdata->closenodes_distances[j] = -FARAWAY;
1347  }
1348 #endif
1349  range_closenodes[node].end = range_closenodes[node].start;
1350  }
1351  }
1352 
1353  if( distdata->pathroot_blocksizesmax[halfedge] > 0 )
1354  {
1355  assert(distdata->pathroot_blocksizes[halfedge] <= distdata->pathroot_blocksizesmax[halfedge]);
1356 
1357  SCIPfreeBlockMemoryArray(scip, &(distdata->pathroot_blocks[halfedge]), distdata->pathroot_blocksizesmax[halfedge]);
1358  }
1359  else
1360  {
1361  assert(distdata->pathroot_blocks[halfedge] == NULL);
1362  }
1363 
1364  distdata->pathroot_blocksizes[halfedge] = 0;
1365  distdata->pathroot_blocksizesmax[halfedge] = 0;
1366 }
1367 
1368 
1369 /** recomputes shortest paths for dirty nodes */
1371  SCIP* scip, /**< SCIP */
1372  const GRAPH* g, /**< graph data structure */
1373  DISTDATA* distdata /**< distance data */
1374 )
1375 {
1376  SCIP_Bool* pathroot_isdirty;
1377  const int* isMarked;
1378  const int nnodes = graph_get_nNodes(g);
1379 
1380  assert(scip && distdata);
1381  assert(graph_isMarked(g));
1382 
1383  pathroot_isdirty = distdata->pathroot_isdirty;
1384  isMarked = g->mark;
1385 
1386  for( int i = 0; i < nnodes; i++ )
1387  {
1388  if( pathroot_isdirty[i] && isMarked[i] )
1389  {
1390  assert(g->grad[i] > 0);
1391  distDataRecomputeNormalDist(scip, g, i, distdata);
1392  pathroot_isdirty[i] = FALSE;
1393  }
1394  }
1395 }
1396 
1397 
1398 /** returns (normal) shortest path distance between vertex1 and vertex2
1399  * and provides inner shortest path vertices. Returns -1.0 if no shortest path was found */
1401  SCIP* scip, /**< SCIP */
1402  const GRAPH* g, /**< graph data structure */
1403  int vertex1, /**< first vertex */
1404  int vertex2, /**< second vertex */
1405  int* pathnodes, /**< inner nodes */
1406  int* npathnodes, /**< number of inner nodes */
1407  DISTDATA* distdata /**< distance data */
1408 )
1409 {
1410  SCIP_Real dist;
1411 
1412  assert(scip && g && distdata && pathnodes && npathnodes);
1413  assert(graph_knot_isInRange(g, vertex1) && graph_knot_isInRange(g, vertex2));
1414 
1415  dist = distDataGetSp(scip, g, vertex1, vertex2, pathnodes, npathnodes, distdata);
1416 
1417  assert(EQ(dist, -1.0) || dist >= 0.0);
1418 
1419  return dist;
1420 }
1421 
1422 
1423 /** Gets bottleneck (or special) distance between v1 and v2.
1424  * Will check shortest known v1->v2 path, but NOT shortest known v2->v1 path.
1425  * Returns -1.0 if no distance is known. (might only happen for RPC or PC) */
1427  SCIP* scip, /**< SCIP */
1428  const GRAPH* g, /**< graph data structure */
1429  int vertex1, /**< first vertex */
1430  int vertex2, /**< second vertex */
1431  DISTDATA* distdata /**< distance data */
1432 )
1433 {
1434  SCIP_Real dist;
1435 
1436  assert(distdata);
1437 
1438  dist = distDataGetNormalDist(scip, g, vertex1, vertex2, distdata);
1439 
1440  assert(EQ(dist, -1.0) || dist >= 0.0);
1441 
1442  if( distdata->sdistdata )
1443  {
1444  const SCIP_Real dist_sd = distDataGetSpecialDist(g, vertex1, vertex2, distdata);
1445 
1446  if( EQ(dist, -1.0) || dist_sd < dist )
1447  {
1448  // printf("%f->%f \n", dist, dist_sd);
1449 
1450  dist = dist_sd;
1451  }
1452 
1453  assert(GE(dist, 0.0));
1454  }
1455 
1456  return dist;
1457 }
1458 
1459 
1460 /** Gets bottleneck (or special) distance between v1 and v2.
1461  * Will check shortest known v1->v2 path, and also shortest known v2->v1 path if no v1-v2 path is known.
1462  * Returns -1.0 if no distance is known. (might only happen for RPC or PC) */
1464  SCIP* scip, /**< SCIP */
1465  const GRAPH* g, /**< graph data structure */
1466  int vertex1, /**< first vertex */
1467  int vertex2, /**< second vertex */
1468  DISTDATA* distdata /**< distance data */
1469 )
1470 {
1471  SCIP_Real dist = distDataGetNormalDist(scip, g, vertex1, vertex2, distdata);
1472 
1473  /* no distance found? */
1474  if( dist < -0.5 )
1475  {
1476  assert(EQ(dist, -1.0));
1477  dist = distDataGetNormalDist(scip, g, vertex2, vertex1, distdata);
1478  }
1479  else
1480  {
1481  const SCIP_Real distrev = distDataGetNormalDist(scip, g, vertex2, vertex1, distdata);
1482 
1483  if( distrev > -0.5 && distrev < dist )
1484  dist = distrev;
1485 
1486  assert(GE(dist, 0.0));
1487  }
1488 
1489  if( distdata->sdistdata )
1490  {
1491  const SCIP_Real dist_sd = distDataGetSpecialDist(g, vertex1, vertex2, distdata);
1492 
1493  if( EQ(dist, -1.0) || dist_sd < dist )
1494  dist = dist_sd;
1495 
1496  assert(GE(dist, 0.0));
1497  }
1498 
1499  assert(EQ(dist, -1.0) || dist >= 0.0);
1500 
1501  return dist;
1502 }
1503 
1504 
1505 /** As 'extreduce_distDataGetSdDouble', but with critial value for early abort */
1507  SCIP* scip, /**< SCIP */
1508  const GRAPH* g, /**< graph data structure */
1509  SCIP_Real dist_eq, /**< critical distance */
1510  int vertex1, /**< first vertex */
1511  int vertex2, /**< second vertex */
1512  DISTDATA* distdata /**< distance data */
1513 )
1514 {
1515  SCIP_Real dist = distDataGetNormalDist(scip, g, vertex1, vertex2, distdata);
1516 
1517  /* no distance found? */
1518  if( dist < -0.5 )
1519  {
1520  assert(EQ(dist, -1.0));
1521  dist = distDataGetNormalDist(scip, g, vertex2, vertex1, distdata);
1522 
1523  if( dist > -0.5 && LT(dist, dist_eq) )
1524  return dist;
1525  }
1526  else
1527  {
1528  const SCIP_Real distrev = distDataGetNormalDist(scip, g, vertex2, vertex1, distdata);
1529 
1530  if( distrev > -0.5 && distrev < dist )
1531  dist = distrev;
1532 
1533  if( dist > -0.5 && LT(dist, dist_eq) )
1534  return dist;
1535 
1536  assert(GE(dist, 0.0));
1537  }
1538 
1539  if( distdata->sdistdata )
1540  {
1541  const SCIP_Real dist_sd = distDataGetSpecialDist(g, vertex1, vertex2, distdata);
1542 
1543  if( EQ(dist, -1.0) || dist_sd < dist )
1544  dist = dist_sd;
1545 
1546  assert(GE(dist, 0.0));
1547  }
1548 
1549  assert(EQ(dist, -1.0) || dist >= 0.0);
1550 
1551  return dist;
1552 }
1553 
1554 
1555 
1556 /** Same as extreduce_distDataGetSdDouble, but only takes paths that do not include any edges marked as blocked. */
1558  SCIP* scip, /**< SCIP */
1559  const GRAPH* g, /**< graph data structure */
1560  int vertex1, /**< first vertex */
1561  int vertex2, /**< second vertex */
1562  EXTDATA* extdata /**< extension data */
1563 )
1564 {
1565  DISTDATA* distdata = extdata->distdata;
1566  SCIP_Real dist = -1.0;
1567 
1568  assert(scip && g && distdata);
1569 
1570  /* NOTE: does not work for pseudo-elimination, because paths might get destroyed */
1571  if( extInitialCompIsEdge(extdata) || extInitialCompIsGenStar(extdata) )
1572  {
1573  const SCIP_Bool* const edges_isForbidden = extdata->sdeq_edgesIsForbidden;
1574  dist = distDataGetNormalDistForbidden(scip, g, EDGE_FORBIDDEN_NONE, edges_isForbidden, vertex1, vertex2, distdata);
1575 
1576  /* no distance found? */
1577  if( dist < -0.5 )
1578  {
1579  assert(EQ(dist, -1.0));
1580  dist = distDataGetNormalDistForbidden(scip, g, EDGE_FORBIDDEN_NONE, edges_isForbidden, vertex1, vertex2, distdata);
1581  }
1582  else
1583  {
1584  const SCIP_Real distrev = distDataGetNormalDistForbidden(scip, g, EDGE_FORBIDDEN_NONE, edges_isForbidden, vertex1, vertex2, distdata);
1585 
1586  if( distrev > -0.5 && distrev < dist )
1587  dist = distrev;
1588 
1589  assert(GE(dist, 0.0));
1590  }
1591  }
1592 
1593  if( distdata->sdistdata )
1594  {
1595  if( !Is_term(g->term[vertex1]) || !Is_term(g->term[vertex2]) )
1596  {
1597  dist = distDataGetSpecialDistIntermedTerms(g, vertex1, vertex2, distdata);
1598  }
1599  }
1600 
1601  assert(EQ(dist, -1.0) || dist >= 0.0);
1602 
1603  return dist;
1604 }
1605 
1606 /** Same as extreduce_distDataGetSdDouble, but only takes paths that do not include
1607  * given edge or any edges marked as blocked.
1608  * User needs to provide (known) equality value */
1610  SCIP* scip, /**< SCIP */
1611  const GRAPH* g, /**< graph data structure */
1612  SCIP_Real dist_eq, /**< critical distance */
1613  int edge_forbidden, /**< forbidden edge */
1614  int vertex1, /**< first vertex */
1615  int vertex2, /**< second vertex */
1616  EXTDATA* extdata /**< extension data */
1617 )
1618 {
1619  DISTDATA* distdata = extdata->distdata;
1620  SCIP_Real dist = -1.0;
1621 
1622  assert(scip && g && distdata);
1623  assert(graph_edge_isInRange(g, edge_forbidden));
1624 
1625  /* NOTE: does not work for pseudo-elimination, because paths might get destroyed */
1626  if( extInitialCompIsEdge(extdata) || extInitialCompIsGenStar(extdata) )
1627  {
1628  const SCIP_Bool* const edges_isForbidden = extdata->sdeq_edgesIsForbidden;
1629  dist = distDataGetNormalDistForbiddenEq(scip, g, dist_eq, edge_forbidden, edges_isForbidden, vertex1, vertex2, distdata);
1630 
1631  if( EQ(dist_eq, dist) )
1632  return dist;
1633 
1634  /* no distance found? */
1635  if( dist < -0.5 )
1636  {
1637  assert(EQ(dist, -1.0));
1638  dist = distDataGetNormalDistForbiddenEq(scip, g, dist_eq, edge_forbidden, edges_isForbidden, vertex2, vertex1, distdata);
1639  }
1640  else
1641  {
1642  const SCIP_Real distrev = distDataGetNormalDistForbiddenEq(scip, g, dist_eq, edge_forbidden, edges_isForbidden, vertex2, vertex1, distdata);
1643 
1644  if( distrev > -0.5 && distrev < dist )
1645  dist = distrev;
1646 
1647  assert(GE(dist, 0.0));
1648  }
1649 
1650  if( EQ(dist_eq, dist) )
1651  return dist;
1652  }
1653 
1654  if( distdata->sdistdata )
1655  {
1656  if( !Is_term(g->term[vertex1]) || !Is_term(g->term[vertex2]) )
1657  {
1658  dist = distDataGetSpecialDistIntermedTerms(g, vertex1, vertex2, distdata);
1659  }
1660  }
1661 
1662  assert(EQ(dist, -1.0) || dist >= 0.0);
1663 
1664  return dist;
1665 }
1666 
1667 
1668 /** Same as extreduce_distDataGetSdDouble, but only takes paths that do not contain given edge */
1670  SCIP* scip, /**< SCIP */
1671  const GRAPH* g, /**< graph data structure */
1672  int edge_forbidden, /**< edge */
1673  int vertex1, /**< first vertex */
1674  int vertex2, /**< second vertex */
1675  DISTDATA* distdata /**< distance data */
1676 )
1677 {
1678  SCIP_Real dist = -1.0;
1679 
1680  assert(scip && g && distdata);
1681  assert(graph_edge_isInRange(g, edge_forbidden));
1682 
1683  /* NOTE: does not work for pseudo-elimination, because paths might get destroyed */
1684  {
1685  dist = distDataGetNormalDistForbidden(scip, g, edge_forbidden, NULL, vertex1, vertex2, distdata);
1686 
1687  /* no distance found? */
1688  if( dist < -0.5 )
1689  {
1690  assert(EQ(dist, -1.0));
1691 
1692  dist = distDataGetNormalDistForbidden(scip, g, edge_forbidden, NULL, vertex2, vertex1, distdata);
1693  }
1694  else
1695  {
1696  const SCIP_Real distrev = distDataGetNormalDistForbidden(scip, g, edge_forbidden, NULL, vertex2, vertex1, distdata);
1697 
1698  if( distrev > -0.5 && distrev < dist )
1699  dist = distrev;
1700 
1701  assert(GE(dist, 0.0));
1702  }
1703  }
1704 
1705  if( distdata->sdistdata )
1706  {
1707  if( !Is_term(g->term[vertex1]) || !Is_term(g->term[vertex2]) )
1708  {
1709  const SCIP_Real dist_sd = distDataGetSpecialDistIntermedTerms(g, vertex1, vertex2, distdata);
1710 
1711  assert(GE(dist_sd, 0.0));
1712 
1713  if( LT(dist_sd, dist) || dist < -0.5 )
1714  dist = dist_sd;
1715  }
1716  }
1717 
1718  assert(EQ(dist, -1.0) || dist >= 0.0);
1719 
1720  return dist;
1721 }
1722 
1723 
1724 
1725 /** Same as extreduce_distDataGetSdDouble, but only takes paths that do not contain given last edges.
1726  * NOTE: Behaves peculiarly for terminal-paths! */
1728  SCIP* scip, /**< SCIP */
1729  const GRAPH* g, /**< graph data structure */
1730  int vertex1, /**< first vertex */
1731  int vertex2, /**< second vertex */
1732  int lastedge12, /**< forbidden last edge on v1->v2 path; needs to be in-edge of v2 */
1733  int lastedge21, /**< forbidden last edge on v2->v1 path; needs to be in-edge of v1 */
1734  DISTDATA* distdata /**< distance data */
1735 )
1736 {
1737  SCIP_Real dist;
1738 
1739  assert(scip && g && distdata);
1740  assert(graph_edge_isInRange(g, lastedge12));
1741  assert(graph_edge_isInRange(g, lastedge21));
1742 
1743  dist = distDataGetNormalDistForbiddenLast(scip, g, vertex1, vertex2, lastedge12, distdata);
1744 
1745  /* no distance found? */
1746  if( dist < -0.5 )
1747  {
1748  assert(EQ(dist, -1.0));
1749 
1750  dist = distDataGetNormalDistForbiddenLast(scip, g, vertex2, vertex1, lastedge21, distdata);
1751  }
1752  else
1753  {
1754  const SCIP_Real distrev = distDataGetNormalDistForbiddenLast(scip, g, vertex2, vertex1, lastedge21, distdata);
1755 
1756  if( distrev > -0.5 && distrev < dist )
1757  dist = distrev;
1758 
1759  assert(GE(dist, 0.0));
1760  }
1761 
1762  if( distdata->sdistdata )
1763  {
1764 #if 1
1765  if( !Is_term(g->term[vertex1]) && !Is_term(g->term[vertex2]) )
1766  {
1767  const SCIP_Real dist_sd = distDataGetSpecialDistIntermedTerms(g, vertex1, vertex2, distdata);
1768 
1769  assert(GE(dist_sd, 0.0));
1770 
1771  if( LT(dist_sd, dist) || dist < -0.5 )
1772  dist = dist_sd;
1773  }
1774 #endif
1775  }
1776 
1777  assert(EQ(dist, -1.0) || dist >= 0.0);
1778 
1779  return dist;
1780 }
1781 
1782 
1783 /** frees distance data */
1785  SCIP* scip, /**< SCIP */
1786  const GRAPH* graph, /**< graph data structure */
1787  DISTDATA** distdata /**< to be freed */
1788 )
1789 {
1790  DISTDATA* dist;
1791 
1792  assert(scip && graph && distdata);
1793 
1794  dist = *distdata;
1795 
1796  graph_heap_free(scip, TRUE, TRUE, &(dist->dheap));
1797  SCIPfreeMemoryArray(scip, &(dist->closenodes_range));
1798  SCIPfreeMemoryArray(scip, &(dist->closenodes_indices));
1799  SCIPfreeMemoryArray(scip, &(dist->closenodes_distances));
1801 
1802  if( dist->sdistdata )
1803  reduce_sdFree(scip, &(dist->sdistdata));
1804 
1805  distDataPathRootsFree(scip, graph, dist);
1806  graph_dijkLimited_free(scip, &(dist->dijkdata));
1807 
1808  SCIPfreeMemory(scip, distdata);
1809 }
1810 
1811 /**@} */
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
SCIP_RETCODE reduce_sdInit(SCIP *, GRAPH *, SD **)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:90
int * visitlist
Definition: graphdefs.h:314
int closenodes_maxnumber
Definition: extreducedefs.h:95
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
SCIP_Real extreduce_distDataGetSdDoubleForbidden(SCIP *scip, const GRAPH *g, int vertex1, int vertex2, EXTDATA *extdata)
static SCIP_Bool extInitialCompIsGenStar(const EXTDATA *extdata)
int *RESTRICT head
Definition: graphdefs.h:224
static SCIP_Real getCloseNodeDistanceForbidden(const GRAPH *g, const DISTDATA *distdata, int edge_forbidden, const SCIP_Bool *edges_isForbidden, int node, int closenode)
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip_mem.h:72
static void closeNodesRunSort(const GRAPH *g, int node, DISTDATA *distdata)
#define Is_term(a)
Definition: graphdefs.h:102
int start
Definition: graphdefs.h:152
static SCIP_Real getCloseNodePath(const GRAPH *g, const DISTDATA *distdata, int node, int closenode, int *pathnodes, int *npathnodes)
SCIP_Real extreduce_distDataGetSdDouble(SCIP *scip, const GRAPH *g, int vertex1, int vertex2, DISTDATA *distdata)
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
SCIP_Real extreduce_distDataGetSdDoubleEq(SCIP *scip, const GRAPH *g, SCIP_Real dist_eq, int vertex1, int vertex2, DISTDATA *distdata)
static SCIP_Real distDataGetNormalDistForbidden(SCIP *scip, const GRAPH *g, int edge_forbidden, const SCIP_Bool *edges_isForbidden, int vertex1, int vertex2, DISTDATA *distdata)
#define EDGE_FORBIDDEN_NONE
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
struct close_nodes_run CNODESRUN
SCIP_Real extreduce_distDataGetSdDoubleForbiddenLast(SCIP *scip, const GRAPH *g, int vertex1, int vertex2, int lastedge12, int lastedge21, DISTDATA *distdata)
#define EAT_FREE
Definition: graphdefs.h:57
#define FALSE
Definition: def.h:87
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
int * pathroot_nrecomps
Definition: extreducedefs.h:92
static void distDataPathRootsFree(SCIP *scip, const GRAPH *g, DISTDATA *distdata)
static SCIP_Bool extInitialCompIsEdge(const EXTDATA *extdata)
SCIP_Real * cost
Definition: graphdefs.h:164
SCIP_Real * node_bias
Definition: graphdefs.h:319
void extreduce_distDataDeleteEdge(SCIP *scip, const GRAPH *g, int edge, DISTDATA *distdata)
void SCIPsortIntIntReal(int *intarray1, int *intarray2, SCIP_Real *realarray, int len)
#define SCIPdebugMessage
Definition: pub_message.h:87
static void distDataInitSizes(const GRAPH *g, int maxnclosenodes, DISTDATA *distdata)
#define FARAWAY
Definition: graphdefs.h:89
int * closenodes_prededges
Definition: extreducedefs.h:86
SCIP_Real extreduce_distDataGetSd(SCIP *scip, const GRAPH *g, int vertex1, int vertex2, DISTDATA *distdata)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
RANGE * closenodes_range
Definition: extreducedefs.h:84
int * closenodes_indices
Definition: extreducedefs.h:85
SCIP_Real * node_distance
Definition: graphdefs.h:316
static SCIP_RETCODE closeNodesRunCompute(SCIP *scip, const GRAPH *g, CNODESRUN *cnodesrun, DISTDATA *distdata)
int * pathroot_blocksizes
Definition: extreducedefs.h:88
int *RESTRICT mark
Definition: graphdefs.h:198
int * position
Definition: graphdefs.h:305
void graph_dijkLimited_reset(const GRAPH *, DIJK *)
Definition: graph_util.c:2105
int *RESTRICT oeat
Definition: graphdefs.h:231
This file implements extended reduction techniques for several Steiner problems.
#define GE(a, b)
Definition: portab.h:85
PRSTATE ** pathroot_blocks
Definition: extreducedefs.h:90
miscellaneous methods used for solving Steiner problems
void extreduce_distDataRecomputeDirtyPaths(SCIP *scip, const GRAPH *g, DISTDATA *distdata)
SCIP_Bool extended
Definition: graphdefs.h:267
static SCIP_Real distDataGetNormalDist(SCIP *scip, const GRAPH *g, int vertex1, int vertex2, DISTDATA *distdata)
SCIP_Real reduce_sdGetSd(const GRAPH *, int, int, SCIP_Real, SCIP_Real, SD *)
Definition: reduce_sd.c:2433
void graph_get_nVET(const GRAPH *, int *, int *, int *)
Definition: graph_stats.c:571
DHEAP * dheap
Definition: graphdefs.h:315
SCIP_Real extreduce_distDataGetSdDoubleForbiddenSingle(SCIP *scip, const GRAPH *g, int edge_forbidden, int vertex1, int vertex2, DISTDATA *distdata)
static SCIP_Real distDataGetSp(SCIP *scip, const GRAPH *g, int vertex1, int vertex2, int *pathnodes, int *npathnodes, DISTDATA *distdata)
SCIP_Real reduce_sdGetSdIntermedTerms(const GRAPH *, int, int, SCIP_Real, SCIP_Real, SD *)
Definition: reduce_sd.c:2449
SCIP_Bool * edgemark
int *RESTRICT grad
Definition: graphdefs.h:201
void extreduce_distDataFree(SCIP *scip, const GRAPH *graph, DISTDATA **distdata)
static SCIP_RETCODE closeNodesRunInit(SCIP *scip, const GRAPH *g, DISTDATA *distdata, CNODESRUN *cnodesrun)
SCIP_Real * closenodes_distances
Definition: extreducedefs.h:87
#define NULL
Definition: lpi_spx1.cpp:155
#define EQ(a, b)
Definition: portab.h:79
int knots
Definition: graphdefs.h:190
static SCIP_RETCODE distDataComputeCloseNodes(SCIP *scip, const GRAPH *g, CNODESRUN *cnodesrun, DISTDATA *distdata)
#define SCIP_CALL(x)
Definition: def.h:384
void reduce_sdFree(SCIP *, SD **)
SCIP_Bool hasPathReplacement
Definition: extreducedefs.h:96
static SCIP_RETCODE distDataAllocateNodesArrays(SCIP *scip, const GRAPH *g, DISTDATA *distdata)
#define LT(a, b)
Definition: portab.h:81
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
SCIP_RETCODE graph_dijkLimited_init(SCIP *, const GRAPH *, DIJK **)
Definition: graph_util.c:1989
static SCIP_Real distDataGetSpecialDist(const GRAPH *g, int vertex1, int vertex2, DISTDATA *distdata)
SCIP_Bool graph_valid_dcsr(const GRAPH *, SCIP_Bool verbose)
Definition: graph_util.c:1919
#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
void graph_dijkLimited_free(SCIP *, DIJK **)
Definition: graph_util.c:2143
static void closeNodesRunExit(SCIP *scip, CNODESRUN *cnodesrun)
#define SCIP_Bool
Definition: def.h:84
SCIP_Bool *const sdeq_edgesIsForbidden
SCIP_Bool graph_isMarked(const GRAPH *)
Definition: graph_base.c:1165
SCIP_RETCODE extreduce_distDataInit(SCIP *scip, GRAPH *g, int maxnclosenodes, SCIP_Bool computeSD, SCIP_Bool useBias, DISTDATA **distdata)
int *RESTRICT tail
Definition: graphdefs.h:223
SCIP_Bool extreduce_distCloseNodesAreValid(SCIP *, const GRAPH *, const DISTDATA *)
static int findEntryFromSorted(const int *array, unsigned int arraysize, int element)
SCIP_RETCODE reduce_sdInitBiasedBottleneck(SCIP *, GRAPH *, SD **)
int *RESTRICT term
Definition: graphdefs.h:196
int closenodes_totalsize
Definition: extreducedefs.h:94
static void distDataRecomputeNormalDist(SCIP *scip, const GRAPH *g, int vertex1, DISTDATA *distdata)
SCIP_Bool graph_pc_knotIsNonLeafTerm(const GRAPH *, int)
static SCIP_Real getCloseNodeDistance(const DISTDATA *distdata, int node, int closenode)
SCIP_RETCODE graph_dijkLimited_initPcShifts(SCIP *, const GRAPH *, DIJK *)
Definition: graph_util.c:2031
SCIP_Bool graph_pc_isPc(const GRAPH *)
#define CONNECT
Definition: graphdefs.h:87
Portable definitions.
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
static SCIP_Bool closeNodesPathIsForbidden(const GRAPH *g, const DISTDATA *distdata, int edge_forbidden, const SCIP_Bool *edges_isForbidden, int node, int closenode, int closenode_pos)
SCIP_Real extreduce_distDataGetSdDoubleForbiddenEq(SCIP *scip, const GRAPH *g, SCIP_Real dist_eq, int edge_forbidden, int vertex1, int vertex2, EXTDATA *extdata)
DISTDATA *const distdata
static SCIP_Real distDataGetSpecialDistIntermedTerms(const GRAPH *g, int vertex1, int vertex2, DISTDATA *distdata)
SCIP_Bool graph_edge_isInRange(const GRAPH *, int)
Definition: graph_stats.c:110
static SCIP_Real getCloseNodeDistanceForbiddenLast(const GRAPH *g, const DISTDATA *distdata, int node, int closenode, int lastedge_node2close)
static SCIP_Real getCloseNodeDistanceForbiddenEq(const GRAPH *g, const DISTDATA *distdata, SCIP_Real dist_eq, int edge_forbidden, const SCIP_Bool *edges_isForbidden, int node, int closenode)
SCIP_Bool is_buildphase
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 edges
Definition: graphdefs.h:219
STP_Bool * node_visited
Definition: graphdefs.h:317
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
SCIP_Bool graph_knot_isInRange(const GRAPH *, int)
Definition: graph_node.c:52
#define UNKNOWN
Definition: sepa_mcf.c:4095
#define nnodes
Definition: gastrans.c:65
DCSR * dcsr_storage
Definition: graphdefs.h:271
static SCIP_RETCODE distDataPathRootsInitialize(SCIP *scip, const GRAPH *g, DISTDATA *distdata)
#define SCIP_CALL_ABORT(x)
Definition: def.h:363
int * pathroot_blocksizesmax
Definition: extreducedefs.h:89
SCIP_Bool * pathroot_isdirty
Definition: extreducedefs.h:91
SCIP_Real extreduce_distDataGetSp(SCIP *scip, const GRAPH *g, int vertex1, int vertex2, int *pathnodes, int *npathnodes, DISTDATA *distdata)
static SCIP_RETCODE distDataPathRootsInsertRoot(SCIP *scip, const GRAPH *g, int halfedge, int root, DISTDATA *distdata)
void graph_heap_correct(int, SCIP_Real, DHEAP *)
Definition: graph_util.c:1166
static SCIP_Real distDataGetNormalDistForbiddenEq(SCIP *scip, const GRAPH *g, SCIP_Real dist_eq, int edge_forbidden, const SCIP_Bool *edges_isForbidden, int vertex1, int vertex2, DISTDATA *distdata)
static SCIP_Real distDataGetNormalDistForbiddenLast(SCIP *scip, const GRAPH *g, int vertex1, int vertex2, int lastedge12, DISTDATA *distdata)