# SCIP

Solving Constraint Integer Programs

grphbase.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 grphbase.c
17  * @brief includes several methods for Steiner problem graphs
18  * @author Thorsten Koch
19  * @author Daniel Rehfeldt
20  *
21  * This file contains several basic methods to process Steiner problem graphs.
22  * A graph can not be reduced in terms of edge or node size, but edges can be marked as
23  * EAT_FREE (to not be used anymore) and nodes may have degree one.
24  * The method 'graph_pack()' can be used to build a new graph that discards these nodes and edges.
25  *
26  */
27
28 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
29
30 /*lint -esym(766,stdlib.h) -esym(766,malloc.h) */
31 /*lint -esym(766,string.h) */
32
33 #include "scip/misc.h"
34 #include <stdio.h>
35 #include <stdlib.h>
36 #include <string.h>
37 #include <assert.h>
38 #include "portab.h"
39 #include "misc_stp.h"
40 #include "scip/misc.h"
41 #include "grph.h"
42 #include "heur_tm.h"
43
45 #define STP_DELPSEUDO_MAXNEDGES 10
46
47 /*
48  * local functions
49  */
50
51 /** can edge in pseudo-elimination method be cut off? */
52 inline static
54  SCIP* scip, /**< SCIP data */
55  const SCIP_Real* cutoffs, /**< cutoff values for each incident edge */
56  const SCIP_Real* cutoffsrev, /**< revere cutoff values (or NULL if undirected) */
57  const SCIP_Real* ecost, /**< edge cost*/
58  const SCIP_Real* ecostrev, /**< reverse edge cost */
59  int edgeidx1, /**< index of first edge to be checked (wrt provided arrays) */
60  int edgeidx2, /**< index of second edge to be checked (wrt provided arrays) */
61  int cutoffidx /**< index for cutoff array */
62  )
63 {
64  SCIP_Real newcost;
65
66  assert(edgeidx1 != edgeidx2);
67
68  if( cutoffs == NULL )
69  return FALSE;
70
71  newcost = ecostrev[edgeidx1] + ecost[edgeidx2];
72
73  if( !SCIPisGT(scip, newcost, cutoffs[cutoffidx]) )
74  return FALSE;
75
76  if( cutoffsrev != NULL )
77  {
78  const SCIP_Real newcostrev = ecost[edgeidx1] + ecostrev[edgeidx2];
79
80  if( !SCIPisGT(scip, newcostrev, cutoffsrev[cutoffidx]) )
81  return FALSE;
82  }
83
84  return TRUE;
85 }
86
87
88 inline static
90  GRAPH* g, /**< the graph */
91  int e /**< the edge to be removed */
92  )
93 {
94  int i;
96  int tail;
97
98  assert(g != NULL);
99  assert(e >= 0);
100  assert(e < g->edges);
101
103  tail = g->tail[e];
104
105  if( g->inpbeg[head] == e )
107  else
108  {
109  if( g->rootedgeprevs != NULL && head == g->source )
110  {
111  i = g->rootedgeprevs[e];
112  assert(g->ieat[i] == e);
113  if( g->ieat[e] >= 0 )
114  g->rootedgeprevs[g->ieat[e]] = i;
115  }
116  else
117  for( i = g->inpbeg[head]; g->ieat[i] != e; i = g->ieat[i] )
118  assert(i >= 0);
119
120  g->ieat[i] = g->ieat[e];
121  }
122  if( g->outbeg[tail] == e )
123  g->outbeg[tail] = g->oeat[e];
124  else
125  {
126  if( g->rootedgeprevs != NULL && tail == g->source )
127  {
128  i = g->rootedgeprevs[e];
129  assert(g->oeat[i] == e);
130  if( g->oeat[e] >= 0 )
131  g->rootedgeprevs[g->oeat[e]] = i;
132  }
133  else
134  for( i = g->outbeg[tail]; g->oeat[i] != e; i = g->oeat[i] )
135  assert(i >= 0);
136
137  g->oeat[i] = g->oeat[e];
138  }
139 }
140
141 /** used by graph_grid_create */
142 static
144  int grid_dim,
145  int shiftcoord,
146  int* ncoords,
147  int* currcoord
148  )
149 {
150  int number = 0;
151  int tmp;
152  int i;
153  int j;
154  for( i = 0; i < grid_dim; i++ )
155  {
156  tmp = 1;
157  for( j = i + 1; j < grid_dim; j++ )
158  {
159  tmp = tmp * ncoords[j];
160  }
161  if( shiftcoord == i )
162  number += (currcoord[i] + 1) * tmp;
163  else
164  number += currcoord[i] * tmp;
165  }
166  number++;
167  return number;
168 }
169
170 /** used by graph_obstgrid_create */
171 static
173  int coord,
174  int grid_dim,
175  int nobstacles,
176  int* ncoords,
177  int* currcoord,
178  int* edgecosts,
179  int* gridedgecount,
180  int** coords,
181  int** gridedges,
182  int** obst_coords,
183  char* inobstacle
184  )
185 {
186  char inobst;
187  int i;
188  int j;
189  int z;
190  int x;
191  int y;
192  int node;
193  i = 0;
194  while( i < ncoords[coord] )
195  {
196  currcoord[coord] = i;
197  if( coord < grid_dim - 1 )
198  compEdgesObst(coord + 1, grid_dim, nobstacles, ncoords, currcoord, edgecosts, gridedgecount, coords, gridedges, obst_coords, inobstacle);
199  else
200  {
201  x = coords[0][currcoord[0]];
202  y = coords[1][currcoord[1]];
203  inobst = FALSE;
204  node = getNodeNumber(grid_dim, -1, ncoords, currcoord);
205  for( z = 0; z < nobstacles; z++ )
206  {
207  assert(obst_coords[0][z] < obst_coords[2][z]);
208  assert(obst_coords[1][z] < obst_coords[3][z]);
209  if( x > obst_coords[0][z] && x < obst_coords[2][z] &&
210  y > obst_coords[1][z] && y < obst_coords[3][z] )
211  {
212  inobst = TRUE;
213  inobstacle[node-1] = TRUE;
214  break;
215  }
216  }
217  for( j = 0; j < grid_dim; j++ )
218  {
219  if( currcoord[j] + 1 < ncoords[j] )
220  {
221  if( inobst == FALSE )
222  {
223  gridedges[0][*gridedgecount] = node;
224  gridedges[1][*gridedgecount] = getNodeNumber(grid_dim, j, ncoords, currcoord);
225  edgecosts[*gridedgecount] = coords[j][currcoord[j] + 1] - coords[j][currcoord[j]];
226  (*gridedgecount)++;
227  }
228  }
229  }
230  }
231  i++;
232  }
233 }
234
235 /** used by graph_grid_create */
236 static
238  int coord,
239  int grid_dim,
240  int* ncoords,
241  int* currcoord,
242  int* edgecosts,
243  int* gridedgecount,
244  int** coords,
245  int** gridedges
246  )
247 {
248  int j;
249  int i = 0;
250  while( i < ncoords[coord] )
251  {
252  currcoord[coord] = i;
253  if( coord < grid_dim - 1 )
254  compEdges(coord + 1, grid_dim, ncoords, currcoord, edgecosts, gridedgecount, coords, gridedges);
255  else
256  {
257  for( j = 0; j < grid_dim; j++ )
258  {
259  if( currcoord[j] + 1 < ncoords[j] )
260  {
261  gridedges[0][*gridedgecount] = getNodeNumber(grid_dim, -1, ncoords, currcoord);
262  gridedges[1][*gridedgecount] = getNodeNumber(grid_dim, j, ncoords, currcoord);
263  edgecosts[*gridedgecount] = coords[j][currcoord[j] + 1] - coords[j][currcoord[j]];
264  (*gridedgecount)++;
265  }
266  }
267  }
268  i++;
269  }
270 }
271
272 /*
273  * global functions
274  */
275
276
277 #if 0
278 /** transforms an MWCSP to an SAP */
279 SCIP_RETCODE graph_MwcsToSap(
280  SCIP* scip, /**< SCIP data structure */
281  GRAPH* graph, /**< the graph */
282  SCIP_Real* maxweights /**< array containing the weight of each node */
283  )
284 {
285  int e;
286  int i;
287  int nnodes;
288  int nterms = 0;
289
290  assert(maxweights != NULL);
291  assert(scip != NULL);
292  assert(graph != NULL);
293  assert(graph->cost != NULL);
294  assert(graph->terms == 0);
295
296  nnodes = graph->knots;
297
298  /* count number of terminals, modify incoming edges for non-terminals */
299  for( i = 0; i < nnodes; i++ )
300  {
301  if( SCIPisLT(scip, maxweights[i], 0.0) )
302  {
303  for( e = graph->inpbeg[i]; e != EAT_LAST; e = graph->ieat[e] )
304  {
305  graph->cost[e] -= maxweights[i];
306  }
307  }
308  else
309  {
310  graph_knot_chg(graph, i, 0);
311  nterms++;
312  }
313  }
314  nterms = 0;
315  for( i = 0; i < nnodes; i++ )
316  {
317  graph->prize[i] = maxweights[i];
318  if( Is_term(graph->term[i]) )
319  {
320  assert(SCIPisGE(scip, maxweights[i], 0.0));
321  nterms++;
322  }
323  else
324  {
325  assert(SCIPisLT(scip, maxweights[i], 0.0));
326  }
327  }
328  assert(nterms == graph->terms);
329  graph->stp_type = STP_MWCSP;
330
331  SCIP_CALL( graph_PcToSap(scip, graph) );
332  assert(graph->stp_type == STP_MWCSP);
333  return SCIP_OKAY;
334 }
335
336
337 /** alters the graph for prize collecting problems */
338 SCIP_RETCODE graph_PcToSap(
339  SCIP* scip, /**< SCIP data structure */
340  GRAPH* graph /**< the graph */
341  )
342 {
343  SCIP_Real* prize;
344  int k;
345  int root;
346  int node;
347  int nnodes;
348  int nterms;
349  int pseudoroot;
350
351  assert(graph != NULL);
352  assert(graph->prize != NULL);
353  assert(graph->knots == graph->ksize);
354  assert(graph->edges == graph->esize);
355
356  prize = graph->prize;
357  nnodes = graph->knots;
358  nterms = graph->terms;
359  graph->norgmodelknots = nnodes;
360  graph->norgmodeledges = graph->edges;
361
362  /* for each terminal, except for the root, one node and three edges (i.e. six arcs) are to be added */
363  SCIP_CALL( graph_resize(scip, graph, (graph->ksize + graph->terms + 2), (graph->esize + graph->terms * 8) , -1) );
364
365  /* create a new nodes */
366  for( k = 0; k < nterms; ++k )
368
369  /* new pseudo-root */
370  pseudoroot = graph->knots;
372
373  /* new root */
374  root = graph->knots;
376
377  nterms = 0;
378  for( k = 0; k < nnodes; ++k )
379  {
380  /* is the kth node a terminal other than the root? */
381  if( Is_term(graph->term[k]) )
382  {
383  /* the copied node */
384  node = nnodes + nterms;
385  nterms++;
386
387  /* switch the terminal property, mark k */
388  graph_knot_chg(graph, k, -2);
389  graph_knot_chg(graph, node, 0);
390  assert(SCIPisGE(scip, prize[k], 0.0));
391
392  /* add one edge going from the root to the 'copied' terminal and one going from the former terminal to its copy */
393  graph_edge_add(scip, graph, root, k, BLOCKED, FARAWAY);
394  graph_edge_add(scip, graph, pseudoroot, node, prize[k], FARAWAY);
395  graph_edge_add(scip, graph, k, node, 0.0, FARAWAY);
396  graph_edge_add(scip, graph, k, pseudoroot, 0.0, FARAWAY);
397  }
398  else if( graph->stp_type != STP_MWCSP )
399  {
400  prize[k] = 0;
401  }
402  }
403  graph->source = root;
404  graph->extended = TRUE;
405  assert((nterms + 1) == graph->terms);
406  if( graph->stp_type != STP_MWCSP )
407  graph->stp_type = STP_PCSPG;
408
409  return SCIP_OKAY;
410 }
411
412
413
414
415 #endif
416
417
418 /** creates a graph out of a given grid */
420  SCIP* scip, /**< SCIP data structure */
421  GRAPH** gridgraph, /**< the (obstacle) grid graph to be constructed */
422  int** coords, /**< coordinates of all points */
423  int** obst_coords, /**< coordinates of obstacles */
424  int nterms, /**< number of terminals */
425  int grid_dim, /**< dimension of the problem */
426  int nobstacles, /**< number of obstacles*/
427  int scale_order /**< scale factor */
428  )
429 {
430  GRAPH* g;
431  GRAPH* gp;
432  double cost;
433  int i;
434  int j;
435  int k;
436  int tmp;
437  int shift;
438  int nnodes;
439  int nedges;
440  double scale_factor;
441  int gridedgecount;
442  int* ncoords;
443  int* currcoord;
444  int* edgecosts;
445  int** termcoords;
446  int** gridedges;
447  char* inobstacle;
448  assert(coords != NULL);
449  assert(grid_dim > 1);
450  assert(nterms > 0);
451  assert(grid_dim == 2);
452  scale_factor = pow(10.0, (double) scale_order);
453
454  /* initialize the terminal-coordinates array */
455  SCIP_CALL( SCIPallocBufferArray(scip, &termcoords, grid_dim) );
456
457  for( i = 0; i < grid_dim; i++ )
458  {
459  SCIP_CALL( SCIPallocBufferArray(scip, &(termcoords[i]), nterms) ); /*lint !e866*/
460  for( j = 0; j < nterms; j++ )
461  termcoords[i][j] = coords[i][j];
462  }
463
464  SCIP_CALL( SCIPallocBufferArray(scip, &ncoords, grid_dim) );
465  SCIP_CALL( SCIPallocBufferArray(scip, &currcoord, grid_dim) );
466
467  /* sort the coordinates and delete multiples */
468  for( i = 0; i < grid_dim; i++ )
469  {
470  ncoords[i] = 1;
471  SCIPsortInt(coords[i], nterms);
472  shift = 0;
473  for( j = 0; j < nterms - 1; j++ )
474  {
475  if( coords[i][j] == coords[i][j + 1] )
476  {
477  shift++;
478  }
479  else
480  {
481  coords[i][j + 1 - shift] = coords[i][j + 1];
482  ncoords[i]++;
483  }
484  }
485  }
486
487  nnodes = 1;
488
489  for( i = 0; i < grid_dim; i++ )
490  nnodes = nnodes * ncoords[i];
491
492  tmp = 0;
493
494  for( i = 0; i < grid_dim; i++ )
495  tmp = tmp + nnodes / ncoords[i];
496
497  nedges = grid_dim * nnodes - tmp;
498  SCIP_CALL( SCIPallocBufferArray(scip, &gridedges, 2) );
499  SCIP_CALL( SCIPallocBufferArray(scip, &edgecosts, nedges) );
500  SCIP_CALL( SCIPallocBufferArray(scip, &(gridedges[0]), nedges) );
501  SCIP_CALL( SCIPallocBufferArray(scip, &(gridedges[1]), nedges) );
502  SCIP_CALL( SCIPallocBufferArray(scip, &(inobstacle), nnodes) );
503  gridedgecount = 0;
504  for( i = 0; i < nnodes; i++ )
505  inobstacle[i] = FALSE;
506  compEdgesObst(0, grid_dim, nobstacles, ncoords, currcoord, edgecosts, &gridedgecount, coords, gridedges, obst_coords, inobstacle);
507  nedges = gridedgecount;
508  /* initialize empty g with allocated slots for nodes and edges */
509  SCIP_CALL( graph_init(scip, gridgraph, nnodes, 2 * nedges, 1) );
510
511  g = *gridgraph;
512  SCIP_CALL( SCIPallocMemoryArray(scip, &(g->grid_ncoords), grid_dim) );
513  for( i = 0; i < grid_dim; i++ )
514  g->grid_ncoords[i] = ncoords[i];
515
516  g->grid_dim = grid_dim;
517  g->grid_coordinates = coords;
518
520  for( i = 0; i < nnodes; i++ )
522
524  for( i = 0; i < nedges; i++ )
525  {
526  /* (re) scale edge costs */
527  if( inobstacle[gridedges[1][i] - 1] == FALSE )
528  {
529  cost = ((double) edgecosts[i]) / scale_factor;
530  graph_edge_add(scip, g, gridedges[0][i] - 1, gridedges[1][i] - 1, cost, cost);
531  }
532  }
533
535  for( i = 0; i < nterms; i++ )
536  {
537  for( j = 0; j < grid_dim; j++ )
538  {
539  for( k = 0; k <= ncoords[j]; k++ )
540  {
541  assert(k != ncoords[j]);
542  if( coords[j][k] == termcoords[j][i] )
543  {
544  currcoord[j] = k;
545  break;
546  }
547  }
548  }
549  /* the position of the (future) terminal */
550  k = getNodeNumber(grid_dim, -1, ncoords, currcoord) - 1;
551
552  if( i == 0 )
553  g->source = k;
554
555  /* make a terminal out of the node */
556  graph_knot_chg(g, k, 0);
557  }
558
559  SCIP_CALL( graph_pack(scip, g, &gp, TRUE) );
560  g = gp;
561  g->stp_type = STP_OARSMT;
562
563  SCIPfreeBufferArray(scip, &inobstacle);
564  SCIPfreeBufferArray(scip, &(gridedges[1]));
565  SCIPfreeBufferArray(scip, &(gridedges[0]));
566  SCIPfreeBufferArray(scip, &edgecosts);
567  SCIPfreeBufferArray(scip, &gridedges);
568  SCIPfreeBufferArray(scip, &currcoord);
569  SCIPfreeBufferArray(scip, &ncoords);
570
571  for( i = grid_dim - 1; i >= 0 ; --i )
572  SCIPfreeBufferArray(scip, &(termcoords[i]));
573
574  SCIPfreeBufferArray(scip, &termcoords);
575
576  return SCIP_OKAY;
577 }
578
579
580
581 /** creates a graph out of a given grid */
583  SCIP* scip, /**< SCIP data structure */
584  GRAPH** gridgraph, /**< the grid graph to be constructed */
585  int** coords, /**< coordinates */
586  int nterms, /**< number of terminals*/
587  int grid_dim, /**< problem dimension */
588  int scale_order /**< scale order */
589  )
590 {
591  GRAPH* g;
592  double cost;
593  int i;
594  int j;
595  int k;
596  int tmp;
597  int shift;
598  int nnodes;
599  int nedges;
600  double scale_factor;
601  int gridedgecount;
602  int* ncoords;
603  int* currcoord;
604  int* edgecosts;
605  int** termcoords;
606  int** gridedges;
607  assert(coords != NULL);
608  assert(grid_dim > 1);
609  assert(nterms > 0);
610
611  scale_factor = pow(10.0, (double) scale_order);
612
613  /* initialize the terminal-coordinates array */
614  SCIP_CALL( SCIPallocBufferArray(scip, &termcoords, grid_dim) );
615  for( i = 0; i < grid_dim; i++ )
616  {
617  SCIP_CALL( SCIPallocBufferArray(scip, &(termcoords[i]), nterms) ); /*lint !e866*/
618  for( j = 0; j < nterms; j++ )
619  termcoords[i][j] = coords[i][j];
620  }
621  SCIP_CALL( SCIPallocBufferArray(scip, &ncoords, grid_dim) );
622  SCIP_CALL( SCIPallocBufferArray(scip, &currcoord, grid_dim) );
623
624  /* sort the coordinates and delete multiples */
625  for( i = 0; i < grid_dim; i++ )
626  {
627  ncoords[i] = 1;
628  SCIPsortInt(coords[i], nterms);
629  shift = 0;
630  for( j = 0; j < nterms - 1; j++ )
631  {
632  if( coords[i][j] == coords[i][j + 1] )
633  {
634  shift++;
635  }
636  else
637  {
638  coords[i][j + 1 - shift] = coords[i][j + 1];
639  ncoords[i]++;
640  }
641  }
642  }
643
644  nnodes = 1;
645  for( i = 0; i < grid_dim; i++ )
646  nnodes = nnodes * ncoords[i];
647
648  tmp = 0;
649  for( i = 0; i < grid_dim; i++ )
650  {
651  tmp = tmp + nnodes / ncoords[i];
652  }
653
654  nedges = grid_dim * nnodes - tmp;
655
656  SCIP_CALL( SCIPallocBufferArray(scip, &gridedges, 2) );
657  SCIP_CALL( SCIPallocBufferArray(scip, &edgecosts, nedges) );
658  SCIP_CALL( SCIPallocBufferArray(scip, &(gridedges[0]), nedges) );
659  SCIP_CALL( SCIPallocBufferArray(scip, &(gridedges[1]), nedges) );
660
661  gridedgecount = 0;
662
663  compEdges(0, grid_dim, ncoords, currcoord, edgecosts, &gridedgecount, coords, gridedges);
664
665  /* initialize empty graph with allocated slots for nodes and edges */
666  SCIP_CALL( graph_init(scip, gridgraph, nnodes, 2 * nedges, 1) );
667
668  g = *gridgraph;
669
670  SCIP_CALL( SCIPallocMemoryArray(scip, &(g->grid_ncoords), grid_dim) );
671  for( i = 0; i < grid_dim; i++ )
672  g->grid_ncoords[i] = ncoords[i];
673
674  g->grid_dim = grid_dim;
675  g->grid_coordinates = coords;
676
678  for( i = 0; i < nnodes; i++ )
680
682  for( i = 0; i < nedges; i++ )
683  {
684  /* (re) scale edge costs */
685  cost = (double) edgecosts[i] / scale_factor;
686  graph_edge_add(scip, g, gridedges[0][i] - 1, gridedges[1][i] - 1, cost, cost);
687  }
688
690  for( i = 0; i < nterms; i++ )
691  {
692  for( j = 0; j < grid_dim; j++ )
693  {
694  for( k = 0; k <= ncoords[j]; k++ )
695  {
696  assert(k != ncoords[j]);
697  if( coords[j][k] == termcoords[j][i] )
698  {
699  currcoord[j] = k;
700  break;
701  }
702  }
703  }
704  /* the position of the (future) terminal */
705  k = getNodeNumber(grid_dim, -1, ncoords, currcoord) - 1;
706
707  /* make a terminal out of the node */
708  graph_knot_chg(g, k, 0);
709  }
710
711  g->stp_type = STP_RSMT;
712
713  SCIPfreeBufferArray(scip, &(gridedges[1]));
714  SCIPfreeBufferArray(scip, &(gridedges[0]));
715  SCIPfreeBufferArray(scip, &edgecosts);
716  SCIPfreeBufferArray(scip, &gridedges);
717  SCIPfreeBufferArray(scip, &currcoord);
718  SCIPfreeBufferArray(scip, &ncoords);
719
720  for( i = grid_dim - 1; i >= 0 ; i-- )
721  SCIPfreeBufferArray(scip, &(termcoords[i]));
722
723  SCIPfreeBufferArray(scip, &termcoords);
724
725  return SCIP_OKAY;
726 }
727
728
729 /** computes coordinates of node 'node' */
731  SCIP* scip, /**< SCIP data structure */
732  int** coords, /**< coordinates */
733  int** nodecoords, /**< coordinates of the node (to be computed) */
734  int* ncoords, /**< array with number of coordinate */
735  int node, /**< the node */
736  int grid_dim /**< problem dimension */
737  )
738 {
739  int i;
740  int j;
741  int tmp;
742  int coord;
743  assert(grid_dim > 1);
744  assert(node >= 0);
745  assert(coords != NULL);
746  assert(ncoords != NULL);
747  if( *nodecoords == NULL )
748  SCIP_CALL( SCIPallocMemoryArray(scip, nodecoords, grid_dim) );
749
750  for( i = 0; i < grid_dim; i++ )
751  {
752  tmp = 1;
753  for( j = i; j < grid_dim; j++ )
754  tmp = tmp * ncoords[j];
755
756  coord = node % tmp;
757  tmp = tmp / ncoords[i];
758  coord = coord / tmp;
759  (*nodecoords)[i] = coords[i][coord];
760  }
761  return SCIP_OKAY;
762 }
763
764
765 /** allocates (first and second) and initializes (only second) arrays for PC and MW problems */
767  SCIP* scip, /**< SCIP data structure */
768  GRAPH* g, /**< the graph */
769  int sizeprize, /**< size of prize array to allocate (or -1) */
770  int sizeterm2edge /**< size of term2edge array to allocate and initialize to -1 (or -1) */
771  )
772 {
773  assert(scip != NULL);
774  assert(g != NULL);
775
776  if( sizeprize > 0 )
777  {
778  assert(NULL == g->prize);
779  SCIP_CALL( SCIPallocMemoryArray(scip, &(g->prize), sizeprize) );
780  }
781
782  if( sizeterm2edge > 0 )
783  {
784  assert(NULL == g->term2edge);
785  SCIP_CALL( SCIPallocMemoryArray(scip, &(g->term2edge), sizeterm2edge) );
786  for( int i = 0; i < sizeterm2edge; i++ )
787  g->term2edge[i] = -1;
788  }
789
790  return SCIP_OKAY;
791 }
792
793 /** changes graph of PC and MW problems needed for presolving routines */
795  SCIP* scip, /**< SCIP data structure */
796  GRAPH* g /**< the graph */
797  )
798 {
799  int prev;
800  const int root = g->source;
801  const int nedges = g->edges;
802
803  if( g->stp_type == STP_RPCSPG )
804  return SCIP_OKAY;
805
806  assert(scip != NULL && g != NULL);
807  assert(g->rootedgeprevs == NULL);
808  assert(nedges > 0 && g->grad[root] > 0);
809
810  SCIP_CALL( SCIPallocMemoryArray(scip, &(g->rootedgeprevs), nedges) );
811
812  for( int e = 0; e < nedges; e++ )
813  g->rootedgeprevs[e] = -1;
814
815  prev = g->outbeg[root];
816  assert(prev != EAT_LAST);
817
818  for( int e = g->oeat[prev]; e != EAT_LAST; e = g->oeat[e] )
819  {
820  g->rootedgeprevs[e] = prev;
821  prev = e;
822  }
823
824  prev = g->inpbeg[root];
825  assert(prev != EAT_LAST);
826
827  for( int e = g->ieat[prev]; e != EAT_LAST; e = g->ieat[e] )
828  {
829  g->rootedgeprevs[e] = prev;
830  prev = e;
831  }
832
833  return SCIP_OKAY;
834 }
835
836 /** changes graph of PC and MW problems needed after exiting presolving routines */
838  SCIP* scip, /**< SCIP data structure */
839  GRAPH* g /**< the graph */
840  )
841 {
842  assert(scip != NULL && g != NULL);
843
844  if( g->stp_type == STP_RPCSPG )
845  return;
846
847  assert(g->rootedgeprevs != NULL);
848
849  SCIPfreeMemoryArray(scip, &(g->rootedgeprevs));
850 }
851
852 /** checks consistency of term2edge array ONLY for non-extended graphs! */
854  const GRAPH* g /**< the graph */
855 )
856 {
857  assert(g != NULL);
858  assert(g->term2edge);
859  assert(!g->extended);
860
861  if( g->term2edge[g->source] != -1 )
862  return FALSE;
863
864  for( int i = 0; i < g->knots; i++ )
865  {
866  if( Is_gterm(g->term[i]) && i != g->source && g->term2edge[i] < 0 )
867  {
868  SCIPdebugMessage("term2edge consistency fail1 %d \n", i);
869  return FALSE;
870  }
871
872  if( !Is_gterm(g->term[i]) && g->term2edge[i] != -1 )
873  {
874  SCIPdebugMessage("term2edge consistency fail2 %d \n", i);
875  return FALSE;
876  }
877
878  if( Is_pterm(g->term[i]) && i != g->source )
879  {
880  int k = -1;
881  int e;
882
883  for( e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
884  {
886  if( Is_term(g->term[k]) && k != g->source )
887  break;
888  }
889  assert(e != EAT_LAST);
890  assert(k >= 0);
891
892  if( g->term2edge[i] != e )
893  {
894  SCIPdebugMessage("term2edge consistency fail3 %d \n", i);
895  return FALSE;
896  }
897
898  if( g->term2edge[k] != flipedge(e) )
899  {
900  SCIPdebugMessage("term2edge consistency fail4 %d \n", i);
901  return FALSE;
902  }
903  }
904  }
905  return TRUE;
906 }
907
908 /** change property of node to non-terminal */
910  GRAPH* g, /**< the graph */
911  int node /**< node to be changed */
912  )
913 {
914  assert(g != NULL);
915  assert(node >= 0);
916  assert(node < g->knots);
917  assert(g->stp_type == STP_PCSPG || g->stp_type == STP_RPCSPG || g->stp_type == STP_MWCSP || g->stp_type == STP_RMWCSP);
918  assert(g->term2edge);
919
920  if( Is_term(g->term[node]) )
921  g->terms--;
922
923  g->term[node] = -1;
924  g->term2edge[node] = -1;
925 }
926
927 /** updates term2edge array for new graph */
929  GRAPH* newgraph, /**< the new graph */
930  const GRAPH* oldgraph, /**< the old graph */
931  int newtail, /**< tail in new graph */
933  int oldtail, /**< tail in old graph */
935 )
936 {
937  assert(newgraph != NULL);
938  assert(oldgraph != NULL);
939  assert(newgraph->term2edge != NULL);
940  assert(oldgraph->term2edge != NULL);
941  assert(newtail >= 0);
943  assert(oldtail >= 0);
945  assert(oldgraph->extended);
946  assert(newgraph->extended);
947
948  assert(newgraph->term2edge != NULL);
949  if( oldgraph->term2edge[oldtail] >= 0 && oldgraph->term2edge[oldhead] >= 0 && oldgraph->term[oldtail] != oldgraph->term[oldhead] )
950  {
953  assert(oldgraph->source != oldtail && oldgraph->source != oldhead);
954  assert(flipedge(newgraph->edges) == newgraph->edges + 1);
955
956  newgraph->term2edge[newtail] = newgraph->edges;
957  newgraph->term2edge[newhead] = newgraph->edges + 1;
958  }
959
960  assert(-1 == newgraph->term2edge[newgraph->source]);
961 }
962
963 /** mark terminals and switch terminal property to original terminals */
965  GRAPH* graph /**< the graph */
966  )
967 {
968  int root;
969  int nnodes;
970
971  assert(graph != NULL);
972  assert(graph->extended);
973
974  root = graph->source;
975  nnodes = graph->knots;
976
977  for( int k = 0; k < nnodes; k++ )
978  {
979  graph->mark[k] = (graph->grad[k] > 0);
980
981  if( Is_pterm(graph->term[k]) )
982  {
983  graph_knot_chg(graph, k, 0);
984  }
985  else if( Is_term(graph->term[k]) )
986  {
987  graph->mark[k] = FALSE;
988  if( k != root )
989  graph_knot_chg(graph, k, -2);
990  }
991  }
992
993  if( graph->stp_type == STP_RPCSPG || graph->stp_type == STP_RMWCSP )
994  graph->mark[root] = TRUE;
995
996  graph->extended = FALSE;
997
998  return;
999 }
1000
1001 /** unmark terminals and switch terminal property to transformed terminals */
1003  GRAPH* graph /**< the graph */
1004  )
1005 {
1006  const int root = graph->source;
1007  const int nnodes = graph->knots;;
1008
1009  assert(graph != NULL);
1010  assert(!(graph->extended));
1011
1012  for( int k = 0; k < nnodes; k++ )
1013  {
1014  graph->mark[k] = (graph->grad[k] > 0);
1015
1016  if( Is_pterm(graph->term[k]) )
1017  graph_knot_chg(graph, k, 0);
1018  else if( Is_term(graph->term[k]) && k != root )
1019  graph_knot_chg(graph, k, -2);
1020  }
1021
1022  graph->extended = TRUE;
1023
1024  return;
1025 }
1026
1027 /** graph_pc_2org if extended */
1029  GRAPH* graph /**< the graph */
1030  )
1031 {
1032  assert(graph != NULL);
1033
1034  if( !graph->extended )
1035  return;
1036
1037  graph_pc_2org(graph);
1038 }
1039
1040 /** graph_pc_2trans if not extended */
1042  GRAPH* graph /**< the graph */
1043  )
1044 {
1045  assert(graph != NULL);
1046
1047  if( graph->extended )
1048  return;
1049
1050  graph_pc_2trans(graph);
1051 }
1052
1053 /* returns sum of positive vertex weights */
1055  SCIP* scip, /**< SCIP data structure */
1056  const GRAPH* graph /**< the graph */
1057  )
1058 {
1059  SCIP_Real prizesum = 0.0;
1060
1061  assert(scip != NULL);
1062  assert(graph != NULL);
1063  assert(graph->prize != NULL);
1064  assert(!graph->extended);
1065
1066  for( int i = 0; i < graph->knots; i++ )
1067  if( Is_term(graph->term[i]) && i != graph->source && graph->prize[i] < BLOCKED )
1068  prizesum += graph->prize[i];
1069
1070  return prizesum;
1071 }
1072
1073
1074 /** alters the graph for prize collecting problems */
1076  SCIP* scip, /**< SCIP data structure */
1077  GRAPH* graph, /**< the graph */
1078  GRAPH** newgraph, /**< the new graph */
1079  SCIP_Real* offset /**< offset */
1080  )
1081 {
1082  SCIP_Real* prize;
1083  SCIP_Real max;
1084  SCIP_Real prizesum;
1085  int k;
1086  int e;
1087  int enext;
1088  int root;
1090  int nnodes;
1091  int nterms;
1092  int stp_type;
1093  int pseudoroot;
1094
1095  assert(scip != NULL);
1096  assert(graph != NULL);
1097  assert(graph->prize != NULL);
1098  assert(graph->knots == graph->ksize);
1099  assert(graph->edges == graph->esize);
1100
1101  prize = graph->prize;
1102  nnodes = graph->knots;
1103  nterms = graph->terms;
1104  prizesum = 0.0;
1105
1106  stp_type = graph->stp_type;
1107  graph->stp_type = STP_SAP;
1108
1109  /* for each terminal, except for the root, three edges (i.e. six arcs) are to be added */
1110  SCIP_CALL( graph_copy(scip, graph, newgraph) );
1111
1112  graph->stp_type = stp_type;
1113
1114  SCIP_CALL( graph_resize(scip, (*newgraph), ((*newgraph)->ksize + 1), ((*newgraph)->esize + 2 * (nterms - 1)) , -1) );
1115
1116  (*newgraph)->source = graph->source;
1117  root = (*newgraph)->source;
1118
1119  /* new pseudo-root */
1120  pseudoroot = (*newgraph)->knots;
1122
1123  max = 0.0;
1124  for( k = 0; k < nnodes; k++ )
1125  if( Is_pterm(graph->term[k]) )
1126  {
1127  prizesum += prize[k];
1128
1129  if( prize[k] > max )
1130  max = prize[k];
1131  }
1132
1133  prizesum -= max;
1134  *offset -= prizesum;
1135
1136  SCIP_CALL( graph_pc_presolInit(scip, *newgraph) );
1137
1138  e = (*newgraph)->outbeg[root];
1139
1140  while( e != EAT_LAST )
1141  {
1142  enext = (*newgraph)->oeat[e];
1145  {
1146  (void) graph_edge_redirect(scip, (*newgraph), e, pseudoroot, head, graph->cost[e], TRUE);
1147  (*newgraph)->cost[flipedge(e)] = FARAWAY;
1149  assert((*newgraph)->tail[e] == pseudoroot);
1150  }
1151  else
1152  {
1153  (*newgraph)->cost[e] = prizesum;
1154  }
1155
1156  e = enext;
1157  }
1158
1159  graph_pc_presolExit(scip, *newgraph);
1160
1161  for( k = 0; k < nnodes; k++ )
1162  {
1163  /* is the kth node a terminal other than the root? */
1164  if( Is_pterm((*newgraph)->term[k]) )
1165  {
1166  graph_edge_add(scip, (*newgraph), k, pseudoroot, 0.0, FARAWAY);
1167  }
1168  }
1169
1170  return SCIP_OKAY;
1171 }
1172
1173 /** adapts SAP deriving from PCST or MWCS problem with new big M */
1175  SCIP* scip, /**< SCIP data structure */
1176  SCIP_Real bigM, /**< new big M value */
1177  GRAPH* graph, /**< the SAP graph */
1178  SCIP_Real* offset /**< the offset */
1179  )
1180 {
1181  SCIP_Real oldbigM;
1182  const int root = graph->source;
1183
1184  assert(bigM > 0.0);
1185  assert(scip != NULL && graph != NULL && offset != NULL);
1186  assert(graph->outbeg[root] >= 0);
1187
1188  oldbigM = graph->cost[graph->outbeg[root]];
1189  assert(oldbigM > 0.0);
1190
1191  *offset += (oldbigM - bigM);
1192
1193  printf("new vs old %f, %f \n", bigM, oldbigM);
1194
1195  for( int e = graph->outbeg[root]; e != EAT_LAST; e = graph->oeat[e] )
1196  {
1197  assert(graph->cost[e] == oldbigM);
1198  graph->cost[e] = bigM;
1199  }
1200 }
1201
1202
1203 /** alters the graph for prize collecting problems and shifts weights to reduce number of terminal */
1205  SCIP* scip, /**< SCIP data structure */
1206  GRAPH* graph, /**< the graph */
1207  GRAPH** newgraph, /**< the new graph */
1208  SCIP_Real* offset /**< offset */
1209  )
1210 {
1211  GRAPH* newg;
1212  SCIP_Real maxp;
1213  SCIP_Real* const prize = graph->prize;
1214  SCIP_Real prizesum;
1215  int e;
1216  int root;
1217  const int nnodes = graph->knots;
1218  const int stp_type = graph->stp_type;
1219  int maxvert;
1220  int pseudoroot;
1221
1222  assert(scip != NULL);
1223  assert(graph != NULL);
1224  assert(graph->prize != NULL);
1225  assert(graph->knots == graph->ksize);
1226  assert(graph->edges == graph->esize);
1227  assert(stp_type == STP_MWCSP || stp_type == STP_PCSPG);
1228  assert(graph->extended);
1229  graph->stp_type = STP_SAP;
1230
1231  /* for each terminal, except for the root, three edges (i.e. six arcs) are to be added */
1232  SCIP_CALL( graph_copy(scip, graph, newgraph) );
1233
1234  graph->stp_type = stp_type;
1235  newg = *newgraph;
1236
1237  /* get max prize and max vertex */
1238  maxvert = -1;
1239  maxp = -1.0;
1240  for( int k = 0; k < nnodes; k++ )
1241  if( Is_pterm(graph->term[k]) && SCIPisGT(scip, graph->prize[k], maxp) )
1242  {
1244  maxp = graph->prize[k];
1245  maxvert = k;
1246  }
1247
1248  assert(maxvert >= 0);
1249
1250  /* shift the costs */
1251  for( int k = 0; k < nnodes; k++ )
1252  {
1253  newg->mark[k] = (newg->grad[k] > 0);
1254  if( Is_pterm(graph->term[k]) && k != maxvert )
1255  {
1256  SCIP_Real p;
1257
1258  assert(newg->mark[k]);
1259
1260  p = prize[k];
1261  for( e = graph->inpbeg[k]; e != EAT_LAST; e = graph->ieat[e] )
1262  if( SCIPisLT(scip, graph->cost[e], p) && !Is_term(graph->term[graph->tail[e]]) )
1263  break;
1264
1265  /* if there is no incoming arc of lower cost than prize[k], make k a common node */
1266  if( e == EAT_LAST )
1267  {
1268  int e2 = -1;
1269  int term = -1;
1270
1271  newg->term[k] = -1;
1272
1273  for( e = graph->inpbeg[k]; e != EAT_LAST; e = graph->ieat[e] )
1274  {
1275  const int tail = graph->tail[e];
1276
1277  if( Is_term(graph->term[tail]) )
1278  {
1279  if( tail == graph->source )
1280  e2 = e;
1281  else
1282  {
1283  assert(term == -1);
1284  term = tail;
1285  }
1286  }
1287  else
1288  {
1289  newg->cost[e] -= p;
1290  assert(SCIPisGE(scip, newg->cost[e], 0.0));
1291  }
1292  }
1293  prize[k] = 0.0;
1294
1295  (*offset) += p;
1296  assert(e2 != -1);
1297  assert(term != -1);
1298
1299  while( newg->inpbeg[term] != EAT_LAST )
1300  graph_edge_del(scip, newg, newg->inpbeg[term], FALSE);
1301
1302  newg->mark[term] = FALSE;
1303  graph_knot_chg(newg, k, -1);
1304  graph_knot_chg(newg, term, -1);
1305  graph_edge_del(scip, newg, e2, FALSE);
1306  }
1307  }
1308  }
1309
1310  SCIP_CALL( graph_resize(scip, newg, (newg->ksize + 1), (newg->esize + 2 * (newg->terms - 1)) , -1) );
1311
1312  assert(newg->source == graph->source);
1313  root = newg->source;
1314
1315  /* new pseudo-root */
1316  pseudoroot = newg->knots;
1318
1319  prizesum = 0.0;
1320  for( int k = 0; k < nnodes; k++ )
1321  if( Is_pterm(graph->term[k]) )
1322  prizesum += prize[k];
1323
1324  prizesum += 1;
1325
1326  *offset -= prizesum;
1327
1328  /* move edges to terminal from root to pseudo-root */
1329  e = newg->outbeg[root];
1330  while( e != EAT_LAST )
1331  {
1333  const int enext = newg->oeat[e];
1334
1336  {
1337  (void) graph_edge_redirect(scip, newg, e, pseudoroot, head, graph->cost[e], TRUE);
1338  newg->cost[flipedge(e)] = FARAWAY;
1340  assert(newg->tail[e] == pseudoroot);
1341  }
1342  else
1343  {
1344  newg->cost[e] = prizesum;
1345  }
1346
1347  e = enext;
1348  }
1349
1350  /* add edges from pterminals to pseudo-root */
1351  for( int k = 0; k < nnodes; k++ )
1352  {
1353  /* is the kth node a terminal other than the root? */
1354  if( Is_pterm(newg->term[k]) )
1355  {
1356  assert(newg->mark[k]);
1357  graph_edge_add(scip, newg, k, pseudoroot, 0.0, FARAWAY);
1358  }
1359  }
1360
1361  return SCIP_OKAY;
1362 }
1363
1364 /** alters the graph for prize-collecting problems with given root */
1366  SCIP* scip, /**< SCIP data structure */
1367  GRAPH* graph, /**< the graph */
1368  GRAPH** newgraph, /**< the new graph */
1369  int* rootcands, /**< array containing all vertices that could be used as root */
1370  int nrootcands, /**< number of all vertices could be used as root */
1371  int root /**< the root of the new SAP */
1372  )
1373 {
1374  GRAPH* p;
1375  int k;
1376  int e;
1377  int e2;
1379  int aterm;
1380  int proot;
1381  int nnodes;
1382  int stp_type;
1383
1384  assert(graph != NULL);
1385  assert(graph->prize != NULL);
1386  assert(graph->knots == graph->ksize);
1387  assert(graph->edges == graph->esize);
1388
1389  graph_pc_2transcheck(graph);
1390
1391  aterm = -1;
1392  proot = graph->source;
1393  stp_type = graph->stp_type;
1394  graph->stp_type = STP_SAP;
1395
1396  /* copy graph */
1397  SCIP_CALL( graph_copy(scip, graph, newgraph) );
1398
1399  p = *newgraph;
1400
1401  graph->stp_type = stp_type;
1402
1403  assert(Is_pterm(graph->term[root]));
1404
1405  for( e = p->outbeg[root]; e != EAT_LAST; e = p->oeat[e] )
1406  {
1409  {
1412  graph_edge_del(scip, p, e, FALSE);
1413  break;
1414  }
1415  }
1416
1417  assert(aterm != -1);
1418  SCIP_CALL( graph_pc_presolInit(scip, p) );
1419
1420  for( e = graph->outbeg[proot]; e != EAT_LAST; e = graph->oeat[e] )
1421  {
1423
1425  assert(graph->tail[e] == p->tail[e]);
1426
1428  {
1430
1431  (void) graph_edge_redirect(scip, p, e, root, head, graph->cost[e], TRUE);
1432  p->cost[flipedge(e)] = FARAWAY;
1433
1434  for( e2 = p->outbeg[head]; e2 != EAT_LAST; e2 = p->oeat[e2] )
1435  if( p->head[e2] != root )
1437  }
1438  else
1439  {
1440  graph_edge_del(scip, p, e, FALSE);
1441  }
1442  }
1443
1444  graph_pc_presolExit(scip, p);
1445
1447
1448  nnodes = p->knots;
1449  p->source = root;
1450  graph_knot_chg(p, root, 0);
1451
1452  for( k = 0; k < nnodes; k++ )
1453  p->mark[k] = (p->grad[k] > 0);
1454
1456
1457  SCIP_CALL( graph_pc_init(scip, p, nnodes, nnodes) );
1458
1459  assert(graph->term2edge != NULL);
1460
1461  for( k = 0; k < nnodes; k++)
1462  {
1463  p->term2edge[k] = graph->term2edge[k];
1464  if( k < graph->norgmodelknots )
1465  p->prize[k] = graph->prize[k];
1466  else
1467  p->prize[k] = 0.0;
1468  }
1469  p->term2edge[root] = -1;
1470  p->term2edge[aterm] = -1;
1471
1472  if( nrootcands > 0 )
1473  {
1474  SCIP_CALL( graph_pc_presolInit(scip, p) );
1475  for( k = 0; k < nrootcands; k++ )
1476  {
1477  aterm = rootcands[k];
1478  if( aterm == root )
1479  continue;
1480
1481  for( e = p->outbeg[aterm]; e != EAT_LAST; e = p->oeat[e] )
1482  {
1484
1486  {
1489
1490  while( p->outbeg[head] != EAT_LAST )
1492
1494  break;
1495  }
1496  }
1497
1499  p->term2edge[aterm] = -1;
1500
1501  assert(e != EAT_LAST);
1502  graph_knot_chg(p, aterm, 0);
1503  }
1504  graph_pc_presolExit(scip, p);
1505  }
1506
1507  graph_knot_chg(p, proot, -1);
1508  p->prize[root] = 0.0;
1509
1510  return SCIP_OKAY;
1511 }
1512
1513
1514
1515 /** alters the graph for prize collecting problems */
1517  SCIP* scip, /**< SCIP data structure */
1518  GRAPH* graph /**< the graph */
1519  )
1520 {
1521  SCIP_Real* prize;
1522  int root;
1523  const int nnodes = graph->knots;
1524  int nterms;
1525
1526  assert(graph != NULL);
1527  assert(graph->edges == graph->esize);
1528
1529  nterms = graph->terms;
1530  prize = graph->prize;
1531  assert(prize != NULL);
1532  assert(nnodes == graph->ksize);
1533  graph->norgmodeledges = graph->edges;
1534  graph->norgmodelknots = nnodes;
1535
1536  /* for each terminal, except for the root, one node and three edges (i.e. six arcs) are to be added */
1537  SCIP_CALL( graph_resize(scip, graph, (graph->ksize + graph->terms + 1), (graph->esize + graph->terms * 6) , -1) );
1538
1539  /* add new nodes */
1540  for( int k = 0; k < nterms; ++k )
1542
1543  /* new root */
1544  root = graph->knots;
1546
1547  /* allocate and initialize term2edge array */
1548  graph_pc_init(scip, graph, -1, graph->knots);
1549  assert(NULL != graph->term2edge);
1550
1551  nterms = 0;
1552  for( int k = 0; k < nnodes; ++k )
1553  {
1554  /* is the kth node a terminal other than the root? */
1555  if( Is_term(graph->term[k]) )
1556  {
1557  /* the copied node */
1558  const int node = nnodes + nterms;
1559  nterms++;
1560
1561  /* switch the terminal property, mark k */
1562  graph_knot_chg(graph, k, -2);
1563  graph_knot_chg(graph, node, 0);
1564  assert(SCIPisGE(scip, prize[k], 0.0));
1565
1566  /* add one edge going from the root to the 'copied' terminal and one going from the former terminal to its copy */
1567  graph_edge_add(scip, graph, root, k, 0.0, FARAWAY);
1568  graph_edge_add(scip, graph, root, node, prize[k], FARAWAY);
1569
1570  graph->term2edge[k] = graph->edges;
1571  graph->term2edge[node] = graph->edges + 1;
1572  assert(graph->edges + 1 == flipedge(graph->edges));
1573
1574  graph_edge_add(scip, graph, k, node, 0.0, FARAWAY);
1575
1578  }
1579  else if( graph->stp_type != STP_MWCSP )
1580  {
1581  prize[k] = 0;
1582  }
1583  }
1584  graph->source = root;
1585  graph->extended = TRUE;
1586  assert((nterms + 1) == graph->terms);
1587  if( graph->stp_type != STP_MWCSP )
1588  graph->stp_type = STP_PCSPG;
1589
1590  SCIPdebugMessage("Transformed to PC \n");
1591
1592  return SCIP_OKAY;
1593 }
1594
1595
1596 /** alters the graph for rooted prize collecting problems */
1598  SCIP* scip, /**< SCIP data structure */
1599  GRAPH* graph /**< the graph */
1600  )
1601 {
1602  SCIP_Real* prize;
1603  int root;
1604  int node;
1605  int nnodes;
1606  int nterms;
1607
1608  assert(graph != NULL);
1609  assert(graph->edges == graph->esize);
1610
1611  root = graph->source;
1612  nnodes = graph->knots;
1613  nterms = graph->terms;
1614  prize = graph->prize;
1615  graph->norgmodeledges = graph->edges;
1616  graph->norgmodelknots = nnodes;
1617
1618  assert(prize != NULL);
1619  assert(nnodes == graph->ksize);
1620  assert(root >= 0);
1621
1622  /* for each terminal, except for the root, one node and three edges (i.e. six arcs) are to be added */
1623  SCIP_CALL( graph_resize(scip, graph, (graph->ksize + graph->terms), (graph->esize + graph->terms * 4) , -1) );
1624
1625  /* create a new nodes */
1626  for( int k = 0; k < nterms - 1; ++k )
1628
1629  /* allocate and initialize term2edge array */
1630  graph_pc_init(scip, graph, -1, graph->knots);
1631  assert(graph->term2edge != NULL);
1632
1633  nterms = 0;
1634
1635  for( int k = 0; k < nnodes; ++k )
1636  {
1637  /* is the kth node a terminal other than the root? */
1638  if( Is_term(graph->term[k]) && k != root )
1639  {
1640  /* the copied node */
1641  node = nnodes + nterms;
1642  nterms++;
1643  /* switch the terminal property, mark k as former terminal */
1644  graph_knot_chg(graph, k, -2);
1645  graph_knot_chg(graph, node, 0);
1646  assert(SCIPisGE(scip, prize[k], 0.0));
1647
1648  /* add one edge going from the root to the 'copied' terminal and one going from the former terminal to its copy */
1649  graph_edge_add(scip, graph, root, node, prize[k], FARAWAY);
1650
1651  graph->term2edge[k] = graph->edges;
1652  graph->term2edge[node] = graph->edges + 1;
1653  assert(graph->edges + 1 == flipedge(graph->edges));
1654
1655  graph_edge_add(scip, graph, k, node, 0.0, FARAWAY);
1656
1659  }
1660  else
1661  {
1662  prize[k] = 0.0;
1663  }
1664  }
1665  /* one for the root */
1666  nterms++;
1667
1668  graph->extended = TRUE;
1669  assert(nterms == graph->terms);
1670  graph->stp_type = STP_RPCSPG;
1671
1672  SCIPdebugMessage("Transformed to RPC \n");
1673
1674  return SCIP_OKAY;
1675 }
1676
1677 /** alters the graph for MWCS problems */
1679  SCIP* scip, /**< SCIP data structure */
1680  GRAPH* graph, /**< the graph */
1681  SCIP_Real* maxweights /**< array containing the weight of each node */
1682  )
1683 {
1684  int nnodes;
1685  int nterms = 0;
1686
1687  assert(maxweights != NULL);
1688  assert(scip != NULL);
1689  assert(graph != NULL);
1690  assert(graph->cost != NULL);
1691  assert(graph->terms == 0);
1692
1693  nnodes = graph->knots;
1694
1695  /* count number of terminals, modify incoming edges for non-terminals */
1696  for( int i = 0; i < nnodes; i++ )
1697  {
1698  if( SCIPisLT(scip, maxweights[i], 0.0) )
1699  {
1700  for( int e = graph->inpbeg[i]; e != EAT_LAST; e = graph->ieat[e] )
1701  graph->cost[e] -= maxweights[i];
1702  }
1703  else if( SCIPisGT(scip, maxweights[i], 0.0) )
1704  {
1705  graph_knot_chg(graph, i, 0);
1706  nterms++;
1707  }
1708  }
1709  nterms = 0;
1710  for( int i = 0; i < nnodes; i++ )
1711  {
1712  graph->prize[i] = maxweights[i];
1713  if( Is_term(graph->term[i]) )
1714  {
1715  assert(SCIPisGE(scip, maxweights[i], 0.0));
1716  nterms++;
1717  }
1718  else
1719  {
1720  assert(SCIPisLE(scip, maxweights[i], 0.0));
1721  }
1722  }
1723  assert(nterms == graph->terms);
1724  graph->stp_type = STP_MWCSP;
1725
1726  SCIP_CALL( graph_pc_2pc(scip, graph) );
1727  assert(graph->stp_type == STP_MWCSP);
1728
1729  SCIPdebugMessage("Transformed to MW \n");
1730
1731  return SCIP_OKAY;
1732 }
1733
1734
1735
1736 /** alters the graph for RMWCS problems */
1738  SCIP* scip, /**< SCIP data structure */
1739  GRAPH* graph /**< the graph */
1740  )
1741 {
1742  SCIP_Real* maxweights;
1743  int i;
1744  int root;
1745  int nnodes;
1746  int npterms;
1747  int nrterms;
1749
1750  assert(scip != NULL);
1751  assert(graph != NULL);
1752  assert(graph->cost != NULL);
1753
1754  root = -1;
1756  npterms = 0;
1757  nrterms = 0;
1758  nnodes = graph->knots;
1759  maxweights = graph->prize;
1760
1761  assert(maxweights != NULL);
1762
1763  /* count number of terminals, modify incoming edges for non-terminals */
1764  for( i = 0; i < nnodes; i++ )
1765  {
1766  if( SCIPisLT(scip, maxweights[i], 0.0) )
1767  {
1768  for( int e = graph->inpbeg[i]; e != EAT_LAST; e = graph->ieat[e] )
1769  graph->cost[e] -= maxweights[i];
1770  }
1771  else if( SCIPisGE(scip, maxweights[i], FARAWAY) )
1772  {
1773  assert(Is_term(graph->term[i]));
1775  {
1776  root = i;
1778  }
1779
1780  nrterms++;
1781  }
1782  else if( SCIPisGT(scip, maxweights[i], 0.0) )
1783  {
1784  graph_knot_chg(graph, i, 0);
1785  npterms++;
1786  }
1787  }
1788
1789  assert(root >= 0);
1790  assert(graph->terms == (npterms + nrterms));
1791
1792  graph->norgmodeledges = graph->edges;
1793  graph->norgmodelknots = nnodes;
1794  graph->source = root;
1795
1796  /* for each terminal, except for the root, one node and three edges (i.e. six arcs) are to be added */
1797  SCIP_CALL( graph_resize(scip, graph, (graph->ksize + npterms), (graph->esize + npterms * 4) , -1) );
1798
1799  /* create a new nodes */
1800  for( int k = 0; k < npterms; k++ )
1802
1803  /* allocate and initialize term2edge array */
1804  graph_pc_init(scip, graph, -1, graph->knots);
1805  assert(graph->term2edge != NULL);
1806
1807  i = 0;
1808  for( int k = 0; k < nnodes; ++k )
1809  {
1810  /* is the kth node a terminal other than the root? */
1811  if( Is_term(graph->term[k]) && SCIPisLT(scip, maxweights[k], FARAWAY) )
1812  {
1813  /* the copied node */
1814  const int node = nnodes + i;
1815  i++;
1816
1817  /* switch the terminal property, mark k */
1818  graph_knot_chg(graph, k, -2);
1819  graph_knot_chg(graph, node, 0);
1820  assert(SCIPisGE(scip, maxweights[k], 0.0));
1821
1822  /* add one edge going from the root to the 'copied' terminal and one going from the former terminal to its copy */
1823  graph_edge_add(scip, graph, root, node, maxweights[k], FARAWAY);
1824
1825  graph->term2edge[k] = graph->edges;
1826  graph->term2edge[node] = graph->edges + 1;
1827  assert(graph->edges + 1 == flipedge(graph->edges));
1828
1829  graph_edge_add(scip, graph, k, node, 0.0, FARAWAY);
1830
1833  }
1834  }
1835
1836  assert(i == npterms);
1837  graph->extended = TRUE;
1838  graph->stp_type = STP_RMWCSP;
1839
1840  SCIPdebugMessage("Transformed to RMW \n");
1841
1842  return SCIP_OKAY;
1843 }
1844
1845 /** transforms MWCSP to RMWCSP if possible */
1847  SCIP* scip, /**< SCIP data structure */
1848  GRAPH* graph, /**< the graph */
1849  SCIP_Real prizesum /**< sum of positive prizes */
1850  )
1851 {
1852  int e;
1853  int p;
1854  int newroot;
1856  const int root = graph->source;
1857
1858  assert(scip != NULL);
1859  assert(graph != NULL);
1860  assert(graph->term2edge != NULL);
1861  assert(graph->extended);
1862
1863  newroot = -1;
1865
1866  e = graph->outbeg[root];
1867  while( e != EAT_LAST )
1868  {
1869  const int enext = graph->oeat[e];
1870  if( SCIPisGE(scip, graph->cost[e], prizesum) )
1871  {
1872  int e2;
1873  const int k = graph->head[e];
1874
1875  assert(Is_term(graph->term[k]));
1877
1878  for( e2 = graph->outbeg[k]; e2 != EAT_LAST; e2 = graph->oeat[e2] )
1879  if( graph->head[e2] != root )
1880  break;
1881
1883  assert(e2 == graph->term2edge[k]);
1884
1885  assert(Is_pterm(graph->term[p]));
1886  assert(SCIPisGE(scip, graph->prize[p], prizesum));
1887
1888  /* delete terminal */
1889  graph_knot_chg(graph, k, -1);
1890  while( graph->outbeg[k] != EAT_LAST )
1891  graph_edge_del(scip, graph, graph->outbeg[k], TRUE);
1892
1893  graph->term2edge[k] = -1;
1894  graph->term2edge[p] = -1;
1895
1896  graph_knot_chg(graph, p, 0);
1897
1899  {
1900  newroot = p;
1902  }
1903  }
1904  e = enext;
1905  }
1906
1907  /* is there a new root? */
1908  if( newroot >= 0 )
1909  {
1910  graph->source = newroot;
1911
1912  e = graph->outbeg[root];
1913  while( e != EAT_LAST )
1914  {
1915  const int enext = graph->oeat[e];
1916  const int k = graph->head[e];
1917  if( Is_term(graph->term[k]) && !SCIPisZero(scip, graph->cost[e]) )
1918  {
1919  (void) graph_edge_redirect(scip, graph, e, newroot, k, graph->cost[e], TRUE);
1920  graph->cost[flipedge(e)] = FARAWAY;
1921  }
1922  e = enext;
1923  }
1924
1925  /* delete old root */
1926  graph_knot_chg(graph, root, -1);
1927  while( graph->outbeg[root] != EAT_LAST )
1928  graph_edge_del(scip, graph, graph->outbeg[root], TRUE);
1929
1930  graph->stp_type = STP_RMWCSP;
1931
1932  }
1933
1934  SCIPdebugMessage("Transformed MW to RMW \n");
1935
1936  return SCIP_OKAY;
1937 }
1938
1939
1940 /** delete a terminal for a (rooted) prize-collecting problem */
1942  SCIP* scip, /**< SCIP data structure */
1943  GRAPH* g, /**< graph data structure */
1944  int i /**< index of the terminal */
1945  )
1946 {
1947  int e;
1948  int t;
1950
1951  assert(g != NULL);
1952  assert(scip != NULL);
1953  assert(Is_term(g->term[i]));
1954
1955  t = UNKNOWN;
1956
1957  /* delete terminal */
1958
1959  assert(g->term2edge[i] != -1);
1960  graph_pc_knot2nonTerm(g, i);
1961  g->mark[i] = FALSE;
1962
1963  while( (e = g->outbeg[i]) != EAT_LAST )
1964  {
1965  const int i1 = g->head[e];
1966
1967  if( Is_pterm(g->term[i1]) && g->source != i1 )
1969  graph_edge_del(scip, g, e, TRUE);
1970  }
1971
1973  assert(t != UNKNOWN);
1974  assert(g->term2edge != NULL);
1975
1976  /* delete artificial terminal */
1977
1978  graph_pc_knot2nonTerm(g, t);
1979
1980  while( g->outbeg[t] != EAT_LAST )
1981  graph_edge_del(scip, g, g->outbeg[t], TRUE);
1982
1984 }
1985
1986
1987 /** subtract a given sum from the prize of a terminal */
1989  SCIP* scip, /**< SCIP data structure */
1990  GRAPH* g, /**< the graph */
1991  SCIP_Real cost, /**< cost to be subtracted */
1992  int i /**< the terminal */
1993  )
1994 {
1995  int e;
1996  int j;
1997
1998  assert(scip != NULL);
1999  assert(g != NULL);
2000
2001  if( g->stp_type == STP_RPCSPG && i == g->source )
2002  return;
2003
2004  g->prize[i] -= cost;
2005  for( e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
2007  break;
2008
2009  assert(e != EAT_LAST);
2010
2012
2013  assert(j != g->source);
2014  assert(!g->mark[j]);
2015
2016  for( e = g->inpbeg[j]; e != EAT_LAST; e = g->ieat[e] )
2017  if( g->source == g->tail[e] )
2018  break;
2019
2020  assert(e != EAT_LAST);
2021  assert(!g->mark[g->tail[e]] || g->stp_type == STP_RPCSPG);
2022
2023  g->cost[e] -= cost;
2024
2025  assert(g->stp_type == STP_MWCSP || g->stp_type == STP_RMWCSP || SCIPisGE(scip, g->prize[i], 0.0));
2026  assert(SCIPisEQ(scip, g->prize[i], g->cost[e]));
2027  assert(SCIPisGE(scip, g->prize[i], 0.0) || g->stp_type == STP_MWCSP);
2028 }
2029
2030 /** change prize of a terminal */
2032  SCIP* scip, /**< SCIP data structure */
2033  GRAPH* g, /**< the graph */
2034  SCIP_Real newprize, /**< prize to be subtracted */
2035  int i /**< the terminal */
2036  )
2037 {
2038  int e;
2039  int j;
2040
2041  assert(scip != NULL);
2042  assert(g != NULL);
2043  assert(newprize > 0.0);
2044
2045  if( g->stp_type == STP_RPCSPG && i == g->source )
2046  return;
2047
2048  g->prize[i] = newprize;
2049  for( e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
2051  break;
2052
2053  assert(e != EAT_LAST);
2054
2056
2057  assert(j != g->source);
2058  assert(!g->mark[j]);
2059
2060  for( e = g->inpbeg[j]; e != EAT_LAST; e = g->ieat[e] )
2061  if( g->source == g->tail[e] )
2062  break;
2063
2064  assert(e != EAT_LAST);
2065  assert(!g->mark[g->tail[e]] || g->stp_type == STP_RPCSPG);
2066
2067  g->cost[e] = newprize;
2068
2069  assert(g->stp_type == STP_MWCSP || g->stp_type == STP_RMWCSP || SCIPisGE(scip, g->prize[i], 0.0));
2070  assert(SCIPisEQ(scip, g->prize[i], g->cost[e]));
2071  assert(SCIPisGE(scip, g->prize[i], 0.0) || g->stp_type == STP_MWCSP);
2072 }
2073
2074 /** contract ancestors of an edge of (rooted) prize-collecting Steiner tree problem or maximum-weight connected subgraph problem */
2076  SCIP* scip, /**< SCIP data structure */
2077  GRAPH* g, /**< the graph */
2078  int t, /**< tail node to be contracted (surviving node) */
2079  int s, /**< head node to be contracted */
2080  int ets /**< edge from t to s or -1 */
2081  )
2082 {
2083  assert(g != NULL);
2084  assert(scip != NULL);
2085
2086  if( ets < 0 )
2087  {
2088  for( ets = g->outbeg[t]; ets != EAT_LAST; ets = g->oeat[ets] )
2089  if( g->head[ets] == s )
2090  break;
2091  assert(ets >= 0);
2092  }
2093
2094  SCIP_CALL(SCIPintListNodeAppendCopy(scip, &(g->pcancestors[s]), g->ancestors[ets], NULL));
2095  SCIP_CALL(SCIPintListNodeAppendCopy(scip, &(g->pcancestors[t]), g->ancestors[ets], NULL));
2096
2097  return SCIP_OKAY;
2098 }
2099
2100 /** contract an edge of (rooted) prize-collecting Steiner tree problem or maximum-weight connected subgraph problem */
2102  SCIP* scip, /**< SCIP data structure */
2103  GRAPH* g, /**< the graph */
2104  int* solnode, /**< solution nodes or NULL */
2105  int t, /**< tail node to be contracted (surviving node) */
2106  int s, /**< head node to be contracted */
2107  int i /**< terminal to add offset to */
2108  )
2109 {
2110  int ets;
2111
2112  assert(g != NULL);
2113  assert(scip != NULL);
2114  assert(Is_term(g->term[i]));
2115
2116  /* get edge from t to s */
2117  for( ets = g->outbeg[t]; ets != EAT_LAST; ets = g->oeat[ets] )
2118  if( g->head[ets] == s )
2119  break;
2120
2121  assert(ets != EAT_LAST);
2122
2123  SCIP_CALL( graph_pc_contractEdgeAncestors(scip, g, t, s, ets) );
2124
2125  /* are both endpoints of the edge to be contracted terminals? */
2126  if( Is_term(g->term[t]) && Is_term(g->term[s]) )
2127  {
2128  int e;
2129  int j;
2130
2131  /* get edge from s to its artificial terminal */
2132  for( e = g->outbeg[s]; e != EAT_LAST; e = g->oeat[e] )
2134  break;
2135
2136  assert(e != EAT_LAST);
2137  assert(g->pcancestors != NULL);
2138
2139  /* artificial terminal to s */
2141
2142  assert(j != g->source);
2143  assert(!g->mark[j]);
2144  assert(g->term2edge != NULL);
2145
2146  /* delete edge and unmark artificial terminal */
2147  graph_knot_chg(g, j, -1);
2148  graph_edge_del(scip, g, e, TRUE);
2149  g->term2edge[j] = -1;
2150
2151  /* delete remaining incident edge of artificial terminal */
2152  e = g->inpbeg[j];
2153
2154  assert(e != EAT_LAST);
2155  assert(g->source == g->tail[e] || g->source == j);
2156  assert(SCIPisEQ(scip, g->prize[s], g->cost[e]));
2157
2158  graph_pc_subtractPrize(scip, g, g->cost[ets] - g->prize[s], i);
2159  graph_edge_del(scip, g, e, TRUE);
2160
2161  assert(g->inpbeg[j] == EAT_LAST);
2162
2163  /* contract s into t */
2164  SCIP_CALL( graph_knot_contract(scip, g, solnode, t, s) );
2165  g->term2edge[s] = -1;
2166
2168
2169  SCIPdebugMessage("PC contract: %d, %d \n", t, s);
2170  }
2171  else
2172  {
2173  if( g->stp_type != STP_MWCSP && g->stp_type != STP_RMWCSP )
2174  graph_pc_subtractPrize(scip, g, g->cost[ets], i);
2175  else
2176  graph_pc_subtractPrize(scip, g, -(g->prize[s]), i);
2177  SCIP_CALL( graph_knot_contract(scip, g, solnode, t, s) );
2178  }
2179  return SCIP_OKAY;
2180 }
2181
2182
2183 /** is this graph a prize-collecting or maximum-weight variant? */
2185  const GRAPH* g /**< the graph */
2186 )
2187 {
2188  const int type = g->stp_type;
2189  assert(g != NULL);
2190
2191  return (type == STP_PCSPG || type == STP_RPCSPG || type == STP_MWCSP || type == STP_RMWCSP);
2192 }
2193
2194
2195 /** add a vertex */
2197  GRAPH* p, /**< the graph */
2198  int term /**< terminal property */
2199  )
2200 {
2201  assert(p != NULL);
2202  assert(p->ksize > p->knots);
2203  assert(term < p->layers);
2204
2205  p->term [p->knots] = term;
2206  p->mark [p->knots] = TRUE;
2208  p->inpbeg[p->knots] = EAT_LAST;
2209  p->outbeg[p->knots] = EAT_LAST;
2210
2211  if( Is_term(term) )
2212  p->terms++;
2213
2214  p->knots++;
2215 }
2216
2217 /** change terminal property of a vertex */
2219  GRAPH* p, /**< the graph */
2220  int node, /**< node to be changed */
2221  int term /**< terminal property */
2222  )
2223 {
2224  assert(p != NULL);
2225  assert(node >= 0);
2226  assert(node < p->knots);
2227  assert(term < p->layers);
2228
2229  if( term != p->term[node] )
2230  {
2231  if( Is_term(p->term[node]) )
2232  p->terms--;
2233
2234  p->term[node] = term;
2235
2236  if( Is_term(p->term[node]) )
2237  p->terms++;
2238  }
2239 }
2240
2241 /** delete node */
2243  SCIP* scip, /**< SCIP data structure */
2244  GRAPH* g, /**< the graph */
2245  int k, /**< the node */
2246  SCIP_Bool freeancestors /**< free edge ancestors? */
2247  )
2248 {
2249  assert(g != NULL);
2250  assert(k >= 0);
2251  assert(k < g->knots);
2252
2253  while( g->outbeg[k] != EAT_LAST )
2254  graph_edge_del(scip, g, g->outbeg[k], freeancestors);
2255 }
2256
2257 /** pseudo delete node, i.e. reconnect neighbors; maximum degree of 4! */
2259  SCIP* scip, /**< SCIP data structure */
2260  GRAPH* g, /**< the graph */
2261  const SCIP_Real* edgecosts, /**< edge costs for cutoff */
2262  const SCIP_Real* cutoffs, /**< cutoff values for each incident edge */
2263  const SCIP_Real* cutoffsrev, /**< revere cutoff values (or NULL if undirected) */
2264  int vertex, /**< the vertex */
2265  SCIP_Bool* success /**< has node been pseudo-eliminated? */
2266  )
2267 {
2275  int neigbedge[STP_DELPSEUDO_MAXNEDGES];
2276  int edgecount;
2277  int nspareedges;
2278  int replacecount;
2279  const int degree = g->grad[vertex];
2280
2281  assert(scip != NULL);
2282  assert(success != NULL);
2283  assert(g != NULL);
2284  assert(vertex >= 0);
2285  assert(vertex < g->knots);
2287
2288 #ifndef NDEBUG
2289  {
2290  int sum = 0;
2291  for( int i = 1; i < STP_DELPSEUDO_MAXGRAD; i++ )
2292  sum += i;
2293  assert(sum == STP_DELPSEUDO_MAXNEDGES);
2294  }
2295 #endif
2296
2297  *success = TRUE;
2298
2299  if( degree <= 1 )
2300  return SCIP_OKAY;
2301
2302  nspareedges = degree; /* todo */
2303
2304  edgecount = 0;
2305
2306  for( int i = 0; i < STP_DELPSEUDO_MAXNEDGES; i++ )
2307  neigbedge[i] = -1;
2308
2309  /* save old edges */
2310  for( int e = g->outbeg[vertex]; e != EAT_LAST; e = g->oeat[e] )
2311  {
2312  assert(e >= 0);
2313
2314  incedge[edgecount] = e;
2315  ecostreal[edgecount] = g->cost[e];
2316  ecost[edgecount] = edgecosts[e];
2317  ecostrev[edgecount] = edgecosts[flipedge(e)];
2318
2320
2322  }
2323
2324  assert(edgecount == degree);
2325  edgecount = 0;
2326  replacecount = 0;
2327
2328  /* check whether there are enough spare edges */
2329  for( int i = 0; i < degree - 1; i++ )
2330  {
2332  for( int j = i + 1; j < degree; j++ )
2333  {
2334  int e;
2335  const SCIP_Bool cutoff = cutoffEdge(scip, cutoffs, cutoffsrev, ecost, ecostrev, i, j, edgecount);
2336
2337  assert(edgecount < STP_DELPSEUDO_MAXNEDGES);
2338
2339  edgecount++;
2340
2341  /* can edge be discarded? */
2342  if( cutoff )
2343  continue;
2344
2345  /* check whether edge already exists */
2346  for( e = g->outbeg[adjvertex]; e != EAT_LAST; e = g->oeat[e] )
2348  {
2349  assert(e >= 0);
2350  neigbedge[edgecount - 1] = e;
2351  break;
2352  }
2353
2354  if( e != EAT_LAST )
2355  continue;
2356
2357  if( ++replacecount > nspareedges )
2358  {
2359  *success = FALSE;
2360  return SCIP_OKAY;
2361  }
2362  }
2363  }
2364
2365  for( int i = 0; i < degree; i++ )
2366  {
2367  const int e = incedge[i];
2368  ancestors[i] = NULL;
2369  revancestors[i] = NULL;
2370
2371  SCIP_CALL(SCIPintListNodeAppendCopy(scip, &(ancestors[i]), g->ancestors[e], NULL));
2372  SCIP_CALL(SCIPintListNodeAppendCopy(scip, &(revancestors[i]), g->ancestors[flipedge(e)], NULL));
2373  }
2374
2375  /* replace edges */
2376  edgecount = 0;
2377  replacecount = 0;
2378  for( int i = 0; i < degree - 1; i++ )
2379  {
2380  for( int j = i + 1; j < degree; j++ )
2381  {
2382  const SCIP_Bool cutoff = cutoffEdge(scip, cutoffs, cutoffsrev, ecost, ecostrev, i, j, edgecount);
2383
2384  assert(edgecount < STP_DELPSEUDO_MAXNEDGES);
2385
2386  edgecount++;
2387
2388  /* do we need to insert edge at all? */
2389  if( !cutoff )
2390  {
2391  const SCIP_Real newcost = ecostreal[i] + ecostreal[j];
2392  const int oldedge = incedge[(replacecount == nspareedges) ? replacecount - 1 : replacecount];
2393 #ifndef NDEBUG
2394  const int oldtail = g->tail[oldedge];
2396 #endif
2397  assert(replacecount <= nspareedges);
2398  assert(replacecount < nspareedges || neigbedge[edgecount - 1] >= 0);
2399
2400  SCIP_CALL( graph_edge_reinsert(scip, g, oldedge, adjvert[i], adjvert[j], newcost, ancestors[i], ancestors[j], revancestors[i], revancestors[j], FALSE));
2401
2402  /* does no edge exist? */
2403  if( neigbedge[edgecount - 1] < 0 )
2404  replacecount++;
2405 #ifndef NDEBUG
2406  else
2407  {
2408  assert(oldtail == g->tail[oldedge]);
2410  }
2411 #endif
2412  }
2413  }
2414  }
2415
2416  /* delete remaining edges */
2417  graph_knot_del(scip, g, vertex, TRUE);
2418
2419  for( int i = 0; i < degree; i++ )
2420  {
2421  SCIPintListNodeFree(scip, &(ancestors[i]));
2422  SCIPintListNodeFree(scip, &(revancestors[i]));
2423  }
2424
2425  return SCIP_OKAY;
2426 }
2427
2428 /** contract an edge, given by its endpoints */
2430  SCIP* scip, /**< SCIP data structure */
2431  GRAPH* p, /**< graph data structure */
2432  int* solnode, /**< node array to mark whether an node is part of a given solution (CONNECT),
2433  or NULL */
2434  int t, /**< tail node to be contracted */
2435  int s /**< head node to be contracted */
2436  )
2437 {
2438  SCIP_Real* incost = NULL;
2439  SCIP_Real* outcost = NULL;
2440  IDX** ancestors = NULL;
2441  IDX** revancestors = NULL;
2442  int* mark = NULL;
2443  int* edge = NULL;
2444  int* knot = NULL;
2445  int slc = 0;
2446  int i;
2447  int et;
2448  int anti;
2449  int es;
2451  int tail;
2453
2454  assert(p != NULL);
2455  assert(t >= 0);
2456  assert(t < p->knots);
2457  assert(s >= 0);
2458  assert(s < p->knots);
2459  assert(s != t);
2460  assert(scip != NULL);
2463  assert(p->layers == 1);
2464
2465  /* save solution */
2466  if( solnode != NULL )
2467  if( solnode[s] == CONNECT )
2468  solnode[t] = CONNECT;
2469
2470  /* change terminal property */
2471  if( Is_term(p->term[s]) )
2472  {
2473  graph_knot_chg(p, t, p->term[s]);
2474  graph_knot_chg(p, s, -1);
2475  }
2476
2477  /* retain root */
2478  if( p->source == s )
2479  p->source = t;
2480
2482  if( sgrad >= 2 )
2483  {
2484  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &incost, sgrad - 1) );
2485  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &outcost, sgrad - 1) );
2486  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &mark, sgrad - 1) );
2487  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &edge, sgrad - 1) );
2488  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &knot, sgrad - 1) );
2489  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &ancestors, sgrad - 1) );
2490  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &revancestors, sgrad - 1) );
2491  }
2492
2493  /* store edges to be moved/removed */
2494  for( es = p->outbeg[s]; es != EAT_LAST; es = p->oeat[es] )
2495  {
2496  assert(p->tail[es] == s);
2497
2498  if( p->head[es] != t )
2499  {
2500  assert(ancestors != NULL);
2501  assert(revancestors != NULL);
2502  assert(mark != NULL);
2503  assert(incost != NULL);
2504  assert(outcost != NULL);
2505  assert(edge != NULL);
2506  assert(knot != NULL);
2507
2508  ancestors[slc] = NULL;
2509  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(ancestors[slc]), p->ancestors[es], NULL) );
2510  revancestors[slc] = NULL;
2511  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(revancestors[slc]), p->ancestors[Edge_anti(es)], NULL) );
2512
2513  mark[slc] = FALSE;
2514  edge[slc] = es;
2516  outcost[slc] = p->cost[es];
2517  incost[slc] = p->cost[Edge_anti(es)];
2518  slc++;
2519
2521  }
2522  }
2523
2524  assert(slc == sgrad - 1);
2525
2526  /* traverse edges */
2527  for( i = 0; i < slc; i++ )
2528  {
2529  const int ihead = knot[i];
2530  assert(knot != NULL && outcost != NULL && incost != NULL && mark != NULL);
2531
2532  /* search for an edge out of t with same head as current edge */
2533
2535  {
2536  for( et = p->outbeg[t]; et >= 0; et = p->oeat[et] )
2538  break;
2539  }
2540  else
2541  {
2542  for( et = p->inpbeg[ihead]; et >= 0; et = p->ieat[et] )
2543  if( p->tail[et] == t )
2544  break;
2545  }
2546
2547  /* does such an edge not exist? */
2548  if( et == EAT_LAST )
2549  {
2550  mark[i] = TRUE;
2551  }
2552  else
2553  {
2554  assert(et != EAT_LAST);
2555
2556  /* This is for nodes with edges to s and t.
2557  * Need to adjust the out and in costs of the edge
2558  */
2559  if( p->cost[et] > outcost[i] )
2560  {
2561  SCIPintListNodeFree(scip, &((p->ancestors)[et]));
2562  assert(ancestors != NULL);
2563  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &((p->ancestors)[et]), ancestors[i], NULL) );
2564
2565  p->cost[et] = outcost[i];
2566  }
2567  if( p->cost[Edge_anti(et)] > incost[i] )
2568  {
2569  anti = Edge_anti(et);
2570  SCIPintListNodeFree(scip, &(p->ancestors[anti]));
2571  assert(revancestors != NULL);
2572  assert(incost != NULL);
2573  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &((p->ancestors)[anti]), revancestors[i], NULL) );
2574  p->cost[anti] = incost[i];
2575  }
2576  }
2577  }
2578
2579  /* insert edges */
2580  for( i = 0; i < slc; i++ )
2581  {
2582  assert(mark != NULL);
2583  if( mark[i] )
2584  {
2585  es = p->outbeg[s];
2586
2587  assert(es != EAT_LAST);
2588  assert(ancestors != NULL);
2589  assert(revancestors != NULL);
2590  assert(ancestors[i] != NULL);
2591  assert(revancestors[i] != NULL);
2592  assert(knot != NULL);
2593  assert(outcost != NULL);
2594  assert(incost != NULL);
2595  SCIPintListNodeFree(scip, &(p->ancestors[es]));
2596  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(p->ancestors[es]), ancestors[i], NULL) );
2597
2598  graph_edge_del(scip, p, es, FALSE);
2599
2601  tail = t;
2602
2605
2606  p->cost[es] = outcost[i];
2607  p->tail[es] = tail;
2610  p->oeat[es] = p->outbeg[tail];
2612  p->outbeg[tail] = es;
2613
2614  es = Edge_anti(es);
2615  SCIPintListNodeFree(scip, &(p->ancestors[es]));
2616
2617  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(p->ancestors[es]), revancestors[i], NULL) );
2618
2619  p->cost[es] = incost[i];
2622  p->ieat[es] = p->inpbeg[tail];
2624  p->inpbeg[tail] = es;
2626  }
2627  }
2628
2629  /* delete remaining edges */
2630  while( p->outbeg[s] != EAT_LAST )
2631  {
2632  es = p->outbeg[s];
2633  SCIPintListNodeFree(scip, &(p->ancestors[es]));
2634  SCIPintListNodeFree(scip, &(p->ancestors[Edge_anti(es)]));
2635  graph_edge_del(scip, p, es, FALSE);
2636  }
2637
2638  if( sgrad >= 2 )
2639  {
2640  assert(ancestors != NULL);
2641  assert(revancestors != NULL);
2642  for( i = 0; i < slc; i++ )
2643  {
2644  SCIPintListNodeFree(scip, &(ancestors[i]));
2645  SCIPintListNodeFree(scip, &(revancestors[i]));
2646  }
2647  SCIPfreeBlockMemoryArray(scip, &revancestors, sgrad - 1);
2648  SCIPfreeBlockMemoryArray(scip, &ancestors, sgrad - 1);
2649  SCIPfreeBlockMemoryArray(scip, &knot, sgrad - 1);
2650  SCIPfreeBlockMemoryArray(scip, &edge, sgrad - 1);
2651  SCIPfreeBlockMemoryArray(scip, &mark, sgrad - 1);
2652  SCIPfreeBlockMemoryArray(scip, &outcost, sgrad - 1);
2653  SCIPfreeBlockMemoryArray(scip, &incost, sgrad - 1);
2654  }
2656  assert(p->outbeg[s] == EAT_LAST);
2657  assert(p->inpbeg[s] == EAT_LAST);
2658  return SCIP_OKAY;
2659 }
2660
2661 /** contract endpoint of lower degree into endpoint of higher degree */
2663  SCIP* scip, /**< SCIP data structure */
2664  GRAPH* g, /**< graph data structure */
2665  int* solnode, /**< node array to mark whether an node is part of a given solution (CONNECT),
2666  or NULL */
2667  int t, /**< tail node to be contracted */
2668  int s /**< head node to be contracted */
2669  )
2670 {
2671  assert(g != NULL);
2672
2674  SCIP_CALL( graph_knot_contract(scip, g, solnode, t, s) );
2675  else
2676  SCIP_CALL( graph_knot_contract(scip, g, solnode, s, t) );
2677
2678  return SCIP_OKAY;
2679 }
2680
2682  SCIP* scip, /**< SCIP data structure */
2683  GRAPH* g, /**< the graph */
2684  int eki, /**< the edge */
2685  int k, /**< new tail */
2686  int j, /**< new head */
2687  SCIP_Real cost, /**< new cost */
2688  SCIP_Bool forcedelete /**< delete edge eki if it is not used? */
2689  )
2690 {
2691  int e;
2692
2693  if( forcedelete )
2694  graph_edge_del(NULL, g, eki, FALSE);
2695
2696  for( e = g->outbeg[k]; e != EAT_LAST; e = g->oeat[e] )
2697  {
2698  assert(g->tail[e] == k);
2699
2700  if( g->head[e] == j )
2701  break;
2702  }
2703
2704  /* does edge already exist? */
2705  if( e != EAT_LAST )
2706  {
2707  /* correct cost */
2708  if( SCIPisGT(scip, g->cost[e], cost) )
2709  {
2710  g->cost[e] = cost;
2711  g->cost[Edge_anti(e)] = cost;
2712  }
2713  else
2714  {
2715  e = -1;
2716  }
2717  }
2718  else
2719  {
2720  if( !forcedelete )
2721  graph_edge_del(NULL, g, eki, FALSE);
2722
2723  assert(g->oeat[eki] == EAT_FREE);
2724
2725  e = eki;
2726
2729
2730  g->cost[e] = cost;
2732  g->tail[e] = k;
2733  g->ieat[e] = g->inpbeg[j];
2734  g->oeat[e] = g->outbeg[k];
2735  g->inpbeg[j] = e;
2736  g->outbeg[k] = e;
2737
2738  e = Edge_anti(eki);
2739
2740  g->cost[e] = cost;
2742  g->tail[e] = j;
2743  g->ieat[e] = g->inpbeg[k];
2744  g->oeat[e] = g->outbeg[j];
2745  g->inpbeg[k] = e;
2746  g->outbeg[j] = e;
2747  return eki;
2748  }
2749  return e;
2750 }
2751
2752 /** reinsert an edge to replace two other edges */
2754  SCIP* scip, /**< SCIP data structure */
2755  GRAPH* g, /**< the graph */
2756  int e1, /**< edge to reinsert */
2757  int k1, /**< tail */
2758  int k2, /**< head */
2759  SCIP_Real cost, /**< edge cost */
2760  IDX* ancestors0, /**< ancestors of first edge */
2761  IDX* ancestors1, /**< ancestors of second edge */
2762  IDX* revancestors0, /**< reverse ancestors of first edge */
2763  IDX* revancestors1, /**< reverse ancestors of first edge */
2764  SCIP_Bool forcedelete /**< delete edge e1 if it is not used? */
2765  )
2766 {
2767  /* redirect; store new edge in n1 */
2768  const int n1 = graph_edge_redirect(scip, g, e1, k1, k2, cost, forcedelete);
2769
2770  if( n1 >= 0 )
2771  {
2772  SCIPintListNodeFree(scip, &(g->ancestors[n1]));
2773  SCIPintListNodeFree(scip, &(g->ancestors[Edge_anti(n1)]));
2774
2775  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[n1]), revancestors0, NULL) );
2776  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[n1]), ancestors1, NULL) );
2777
2778  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[Edge_anti(n1)]), ancestors0, NULL) );
2779  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[Edge_anti(n1)]), revancestors1, NULL) );
2780  }
2781  return SCIP_OKAY;
2782 }
2783
2784
2785 /** add a new edge to the graph */
2787  SCIP* scip, /**< SCIP data structure */
2788  GRAPH* g, /**< the graph */
2789  int tail, /**< tail of the new edge */
2791  SCIP_Real cost1, /**< tail to head cost */
2792  SCIP_Real cost2 /**< head to tail cost */
2793  )
2794 {
2795  int e;
2796
2797  assert(g != NULL);
2798  assert(SCIPisGE(scip, cost1, 0.0) || SCIPisEQ(scip, cost1, (double) UNKNOWN));
2799  assert(SCIPisGE(scip, cost2, 0.0) || SCIPisEQ(scip, cost2, (double) UNKNOWN));
2800  assert(tail >= 0);
2801  assert(tail < g->knots);
2804
2805  assert(g->esize >= g->edges + 2);
2806
2807  e = g->edges;
2808
2811
2812  if( cost1 != UNKNOWN )
2813  g->cost[e] = cost1;
2814  g->tail[e] = tail;
2817  g->oeat[e] = g->outbeg[tail];
2819  g->outbeg[tail] = e;
2820
2821  e++;
2822
2823  if( cost2 != UNKNOWN )
2824  g->cost[e] = cost2;
2827  g->ieat[e] = g->inpbeg[tail];
2829  g->inpbeg[tail] = e;
2831
2832  g->edges += 2;
2833 }
2834
2835
2836 /** delete an edge */
2838  SCIP* scip, /**< SCIP data structure */
2839  GRAPH* g, /**< the graph */
2840  int e, /**< the edge */
2841  SCIP_Bool freeancestors /**< free edge ancestors? */
2842  )
2843 {
2844  assert(g != NULL);
2845  assert(e >= 0);
2846  assert(e < g->edges);
2847
2848  if( freeancestors )
2849  {
2850  assert(scip != NULL);
2851  SCIPintListNodeFree(scip, &((g->ancestors)[e]));
2852  SCIPintListNodeFree(scip, &((g->ancestors)[Edge_anti(e)]));
2853  }
2854
2855  /* delete first arc */
2856  e -= e % 2;
2857  assert(g->head[e] == g->tail[e + 1]);
2858  assert(g->tail[e] == g->head[e + 1]);
2859
2862
2863  removeEdge(g, e);
2864
2865  assert(g->ieat[e] != EAT_FREE);
2866  assert(g->ieat[e] != EAT_HIDE);
2867  assert(g->oeat[e] != EAT_FREE);
2868  assert(g->oeat[e] != EAT_HIDE);
2869
2870  g->ieat[e] = EAT_FREE;
2871  g->oeat[e] = EAT_FREE;
2872
2873  /* delete second arc */
2874  e++;
2875  removeEdge(g, e);
2876
2877  assert(g->ieat[e] != EAT_FREE);
2878  assert(g->ieat[e] != EAT_HIDE);
2879  assert(g->oeat[e] != EAT_FREE);
2880  assert(g->oeat[e] != EAT_HIDE);
2881
2882  g->ieat[e] = EAT_FREE;
2883  g->oeat[e] = EAT_FREE;
2884 }
2885
2886 /** hide edge */
2888  GRAPH* g, /**< the graph */
2889  int e /**< the edge */
2890  )
2891 {
2892  assert(g != NULL);
2893  assert(e >= 0);
2894  assert(e < g->edges);
2895
2896  /* Immer mit der ersten von beiden Anfangen
2897  */
2898  e -= e % 2;
2899
2900  assert(g->head[e] == g->tail[e + 1]);
2901  assert(g->tail[e] == g->head[e + 1]);
2902
2905
2906  removeEdge(g, e);
2907
2908  assert(g->ieat[e] != EAT_FREE);
2909  assert(g->ieat[e] != EAT_HIDE);
2910  assert(g->oeat[e] != EAT_FREE);
2911  assert(g->oeat[e] != EAT_HIDE);
2912
2913  g->ieat[e] = EAT_HIDE;
2914  g->oeat[e] = EAT_HIDE;
2915
2916  e++;
2917
2918  removeEdge(g, e);
2919
2920  assert(g->ieat[e] != EAT_FREE);
2921  assert(g->ieat[e] != EAT_HIDE);
2922  assert(g->oeat[e] != EAT_FREE);
2923  assert(g->oeat[e] != EAT_HIDE);
2924
2925  g->ieat[e] = EAT_HIDE;
2926  g->oeat[e] = EAT_HIDE;
2927 }
2928
2929
2930 /** print edge info */
2932  SCIP* scip, /**< SCIP data structure */
2933  const GRAPH* g, /**< the graph */
2934  int e /**< the edge */
2935  )
2936 {
2937  const int t = g->tail[e];
2938  const int h = g->head[e];
2939  printf("e: %d %d->%d (%d->%d) \n", e, t, h, g->term[t], g->term[h]);
2940 }
2941
2942 /** changes solution according to given root */
2944  SCIP* scip, /**< SCIP data structure */
2945  GRAPH* g, /**< the graph */
2946  int* result, /**< solution array (CONNECT/UNKNOWN) */
2947  int newroot /**< the new root */
2948  )
2949 {
2950  int* queue;
2951  int* const gmark = g->mark;
2952  int size;
2953  const int nnodes = g->knots;
2954
2955  assert(scip != NULL);
2956  assert(g != NULL);
2957  assert(result != NULL);
2958  assert(Is_term(g->term[newroot]));
2959
2960  if( g->grad[newroot] == 0 )
2961  return SCIP_OKAY;
2962
2963  for( int k = 0; k < nnodes; k++ )
2964  gmark[k] = FALSE;
2965
2966  SCIP_CALL( SCIPallocBufferArray(scip, &queue, nnodes) );
2967
2968  gmark[newroot] = TRUE;
2969  size = 0;
2970  queue[size++] = newroot;
2971
2972  /* BFS loop */
2973  while( size )
2974  {
2975  const int node = queue[--size];
2976
2977  /* traverse outgoing arcs */
2978  for( int a = g->outbeg[node]; a != EAT_LAST; a = g->oeat[a] )
2979  {
2981
2982  if( !gmark[head] && (result[a] == CONNECT || result[flipedge(a)] == CONNECT ) )
2983  {
2984  if( result[flipedge(a)] == CONNECT )
2985  {
2986  result[a] = CONNECT;
2987  result[flipedge(a)] = UNKNOWN;
2988  }
2991  }
2992  }
2993  }
2994
2995  SCIPfreeBufferArray(scip, &queue);
2996
2997  /* adjust solution if infeasible */
2998  for( int k = 0; k < nnodes; k++ )
2999  {
3000  if( !gmark[k] )
3001  {
3002  for( int a = g->outbeg[k]; a != EAT_LAST; a = g->oeat[a] )
3003  {
3004  result[a] = UNKNOWN;
3005  result[flipedge(a)] = UNKNOWN;
3006  }
3007
3008  /* not yet connected terminal? */
3009  if( Is_term(g->term[k]) )
3010  {
3011  int a;
3012  assert(g->stp_type != STP_SPG);
3013
3014  for( a = g->inpbeg[k]; a != EAT_LAST; a = g->ieat[a] )
3015  {
3016  const int node = g->tail[a];
3017  if( gmark[node] && node != newroot )
3018  {
3019  result[a] = CONNECT;
3020  break;
3021  }
3022  }
3023  if( a == EAT_LAST )
3024  {
3025  for( a = g->inpbeg[k]; a != EAT_LAST; a = g->ieat[a] )
3026  {
3027  const int node = g->tail[a];
3028  if( node == newroot )
3029  {
3030  result[a] = CONNECT;
3031  break;
3032  }
3033  }
3034  }
3035  else
3036  gmark[k] = TRUE;
3037  }
3038  }
3039  }
3040
3041  return SCIP_OKAY;
3042 }
3043
3044
3045 /** checks whether edge(s) of given primal solution have been deleted */
3047  SCIP* scip, /**< SCIP data structure */
3048  const GRAPH* graph, /**< graph data structure */
3049  const int* result /**< solution array, indicating whether an edge is in the solution */
3050  )
3051 {
3052  const int nedges = graph->edges;
3053
3054  assert(scip != NULL);
3055  assert(graph != NULL);
3056  assert(result != NULL);
3057
3058  for( int i = 0; i < nedges; i++ )
3059  if( result[i] == CONNECT && graph->oeat[i] == EAT_FREE )
3060  return FALSE;
3061
3062  return TRUE;
3063 }
3064
3065 /** verifies whether a given primal solution is feasible */
3067  SCIP* scip, /**< SCIP data structure */
3068  const GRAPH* graph, /**< graph data structure */
3069  const int* result /**< solution array, indicating whether an edge is in the solution */
3070  )
3071 {
3072  int* queue;
3073  STP_Bool* reached;
3074  int root;
3075  int size;
3076  int nnodes;
3077  int termcount;
3078  SCIP_Bool usepterms;
3079
3080  assert(scip != NULL);
3081  assert(graph != NULL);
3082  assert(result != NULL);
3083
3084  reached = NULL;
3085  nnodes = graph->knots;
3086  root = graph->source;
3087  assert(root >= 0);
3088
3089  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &reached, nnodes) );
3090  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &queue, nnodes) );
3091
3092  if( (graph->stp_type == STP_MWCSP || graph->stp_type == STP_PCSPG) && !graph->extended )
3093  usepterms = TRUE;
3094  else
3095  usepterms = FALSE;
3096
3097  assert(reached != NULL);
3098
3099  for( int i = 0; i < nnodes; i++ )
3100  reached[i] = FALSE;
3101
3102  /* BFS until all terminals are reached */
3103
3104  termcount = 1;
3105  size = 0;
3106  reached[root] = TRUE;
3107  queue[size++] = root;
3108
3109  while( size )
3110  {
3111  const int node = queue[--size];
3112
3113  for( int e = graph->outbeg[node]; e != EAT_LAST; e = graph->oeat[e] )
3114  {
3115  if( result[e] == CONNECT )
3116  {
3117  const int i = graph->head[e];
3118
3119  /* cycle? */
3120  if( reached[i] )
3121  {
3122  SCIPfreeBufferArray(scip, &queue);
3123  SCIPfreeBufferArray(scip, &reached);
3124  return FALSE;
3125  }
3126
3127  if( usepterms)
3128  {
3129  if( Is_pterm(graph->term[i]) )
3130  termcount++;
3131  }
3132  else
3133  {
3134  if( Is_term(graph->term[i]) )
3135  termcount++;
3136  }
3137
3138  reached[i] = TRUE;
3139  queue[size++] = i;
3140  }
3141  }
3142  }
3143
3144 #if 0
3145  if(termcount != graph->terms)
3146  {
3147  printf("termcount %d graph->terms %d \n", termcount, graph->terms);
3148  printf("root %d \n", root);
3149
3150  for( int i = 0; i < nnodes && 0; i++ )
3151  {
3152  if( Is_term(graph->term[i]) && !reached[i] )
3153  {
3155  for( int e = graph->inpbeg[i]; e != EAT_LAST; e = graph->ieat[e] )
3156  {
3157  printf("tail %d %d \n", graph->tail[e], graph->term[graph->tail[e]]);
3158  }
3159  }
3160  }
3161  }
3162 #endif
3163  SCIPfreeBufferArray(scip, &queue);
3164  SCIPfreeBufferArray(scip, &reached);
3165
3166  return (termcount == graph->terms);
3167 }
3168
3169 /** mark endpoints of edges in given list */
3171  const GRAPH* g, /**< graph data structure */
3172  STP_Bool* solnode, /**< solution nodes array (TRUE/FALSE) */
3173  IDX* listnode /**< edge list */
3174  )
3175 {
3176  int i;
3177  IDX* curr;
3178
3179  assert(g != NULL);
3180  assert(solnode != NULL);
3181
3182  curr = listnode;
3183
3184  while( curr != NULL )
3185  {
3186  i = curr->index;
3187
3189  solnode[g->tail[i]] = TRUE;
3190
3191  curr = curr->parent;
3192  }
3193 }
3194
3195 /** compute solution value for given edge-solution array (CONNECT/UNKNOWN) and offset */
3197  const SCIP_Real* edgecost,
3198  const int* soledge,
3199  SCIP_Real offset,
3200  int nedges
3201  )
3202 {
3203  SCIP_Real obj = offset;
3204  int e;
3205
3206  for( e = 0; e < nedges; e++ )
3207  if( soledge[e] == CONNECT )
3208  obj += edgecost[e];
3209
3210  return obj;
3211 }
3212
3213 /** get original solution */
3215  SCIP* scip, /**< SCIP data structure */
3216  const GRAPH* transgraph, /**< the transformed graph */
3217  const GRAPH* orggraph, /**< the original graph */
3218  const int* transsoledge, /**< solution for transformed problem */
3219  int* orgsoledge /**< new retransformed solution */
3220 )
3221 {
3222  STP_Bool* orgnodearr;
3223  STP_Bool* transnodearr = NULL;
3224
3225  IDX** const ancestors = transgraph->ancestors;
3226
3227  const int transnedges = transgraph->edges;
3228  const int transnnodes = transgraph->knots;
3229  const int orgnnodes = orggraph->knots;
3230  const SCIP_Bool pcmw = graph_pc_isPcMw(transgraph);
3231
3232  assert(transgraph != NULL && orggraph != NULL && transsoledge != NULL && orgsoledge != NULL);
3233  assert(transgraph->ancestors != NULL);
3234  assert(transgraph->stp_type == orggraph->stp_type);
3235
3236  SCIP_CALL( SCIPallocBufferArray(scip, &orgnodearr, orgnnodes) );
3237
3238  if( pcmw )
3239  {
3240  SCIP_CALL( SCIPallocBufferArray(scip, &transnodearr, transnnodes) );
3241
3242  for( int k = 0; k < transnnodes; k++ )
3243  transnodearr[k] = FALSE;
3244
3245  for( int e = 0; e < transnedges; e++ )
3246  if( transsoledge[e] == CONNECT )
3247  {
3248  transnodearr[transgraph->tail[e]] = TRUE;
3250  }
3251  }
3252
3253  for( int k = 0; k < orgnnodes; k++ )
3254  orgnodearr[k] = FALSE;
3255
3256  for( int e = 0; e < transnedges; e++ )
3257  if( transsoledge[e] == CONNECT )
3258  graph_sol_setNodeList(orggraph, orgnodearr, ancestors[e]);
3259
3260  /* retransform edges fixed during graph reduction */
3261  graph_sol_setNodeList(orggraph, orgnodearr, transgraph->fixedges);
3262
3263  if( pcmw )
3264  {
3265  SCIP_CALL( graph_sol_markPcancestors(scip, transgraph->pcancestors, orggraph->tail, orggraph->head, orgnnodes,
3266  orgnodearr, NULL, NULL, NULL, NULL ) );
3267  }
3268
3269  for( int e = 0; e < orggraph->edges; e++ )
3270  orgsoledge[e] = UNKNOWN;
3271
3272  /* prune solution (in original graph) */
3273  if( pcmw )
3274  SCIP_CALL( SCIPStpHeurTMPrunePc(scip, orggraph, orggraph->cost, orgsoledge, orgnodearr) );
3275  else
3276  SCIP_CALL( SCIPStpHeurTMPrune(scip, orggraph, orggraph->cost, 0, orgsoledge, orgnodearr) );
3277
3278  SCIPfreeBufferArray(scip, &orgnodearr);
3279  SCIPfreeBufferArrayNull(scip, &transnodearr);
3280
3281  assert(graph_sol_valid(scip, orggraph, orgsoledge));
3282
3283  return SCIP_OKAY;
3284 }
3285
3286
3287 /** mark original solution */
3289  SCIP* scip, /**< SCIP data structure */
3290  IDX** pcancestors, /**< the ancestors */
3291  const int* tails, /**< tails array */
3293  int orgnnodes, /**< original number of nodes */
3294  STP_Bool* solnodemark, /**< solution nodes mark array */
3295  STP_Bool* soledgemark, /**< solution edges mark array or NULL */
3296  int* solnodequeue, /**< solution nodes queue or NULL */
3297  int* nsolnodes, /**< number of solution nodes or NULL */
3298  int* nsoledges /**< number of solution edges or NULL */
3299 )
3300 {
3301  int* queue;
3302  int nnodes;
3303  int nedges = (nsoledges != NULL)? *nsoledges : 0;
3304  int qstart;
3305  int qend;
3306
3307  assert(scip != NULL && tails != NULL && heads != NULL && pcancestors != NULL && solnodemark != NULL);
3308
3309  if( solnodequeue != NULL )
3310  queue = solnodequeue;
3311  else
3312  SCIP_CALL( SCIPallocBufferArray(scip, &queue, orgnnodes) );
3313
3314  if( nsolnodes == NULL )
3315  {
3316  assert(solnodequeue == NULL);
3317  nnodes = 0;
3318  for( int k = 0; k < orgnnodes; k++ )
3319  if( solnodemark[k] )
3320  queue[nnodes++] = k;
3321  }
3322  else
3323  {
3324  nnodes = *nsolnodes;
3325  assert(solnodequeue != NULL);
3326  }
3327
3328  qstart = 0;
3329  qend = nnodes;
3330
3331  while( qend != qstart )
3332  {
3333  int k = qstart;
3334
3335  assert(qstart < qend);
3336  qstart = qend;
3337
3338  for( ; k < qend; k++ )
3339  {
3340  const int ancestornode = queue[k];
3341
3342  assert(solnodemark[ancestornode]);
3343
3344  for( IDX* curr = pcancestors[ancestornode]; curr != NULL; curr = curr->parent )
3345  {
3346  const int ancestoredge = curr->index;
3347  assert(tails[ancestoredge] < orgnnodes && heads[ancestoredge] < orgnnodes);
3348
3349  if( soledgemark != NULL && !soledgemark[ancestoredge] )
3350  {
3351  soledgemark[ancestoredge] = TRUE;
3352  nedges++;
3353  }
3354  if( !solnodemark[tails[ancestoredge]] )
3355  {
3356  solnodemark[tails[ancestoredge]] = TRUE;
3357  queue[nnodes++] = tails[ancestoredge];
3358  }
3360  {
3363  }
3364  }
3365  }
3366  qend = nnodes;
3367  }
3368
3369  if( nsolnodes != NULL )
3370  *nsolnodes = nnodes;
3371
3372  if( nsoledges != NULL )
3373  *nsoledges = nedges;
3374
3375  if( solnodequeue == NULL )
3376  SCIPfreeBufferArray(scip, &queue);
3377
3378  return SCIP_OKAY;
3379 }
3380
3381 /** get (real) number of nodes , edges, terminals */
3383  const GRAPH* graph, /**< the graph */
3384  int* nnodes, /**< number of nodes */
3385  int* nedges, /**< number of edges */
3386  int* nterms /**< number of terminals */
3387  )
3388 {
3389  int v = 0;
3390  int e = 0;
3391  int t = 0;
3392  int vorg;
3393
3394  assert(graph != NULL);
3395
3396  vorg = graph->knots;
3397
3398  for( int k = 0; k < vorg; k++ )
3399  {
3400  if( graph->grad[k] > 0 )
3401  {
3402  v++;
3404  if( Is_term(graph->term[k]) )
3405  t++;
3406  }
3407  }
3408
3409  *nnodes = v;
3410  *nedges = e;
3411  *nterms = t;
3412
3413  return;
3414 }
3415
3416 /* get compressed sparse row arrays representing current graph */
3418  const GRAPH* g, /**< the graph */
3419  int* RESTRICT edgearr, /**< original edge array [0,...,nedges - 1] */
3420  int* RESTRICT tailarr, /**< tail of csr edge [0,...,nedges - 1] */
3421  int* RESTRICT start, /**< start array [0,...,nnodes] */
3422  int* nnewedges /**< pointer to store number of new edges */
3423  )
3424 {
3425  int i = 0;
3426  const int nnodes = g->knots;
3427
3428  assert(g != NULL);
3429  assert(tailarr != NULL);
3430  assert(edgearr != NULL);
3431  assert(start != NULL);
3432
3433  for( int k = 0; k < nnodes; k++ )
3434  {
3435  start[k] = i;
3436  for( int e = g->inpbeg[k]; e != EAT_LAST; e = g->ieat[e] )
3437  {
3438  edgearr[i] = e;
3439  tailarr[i++] = g->tail[e] + 1;
3440  }
3441  }
3442
3443  *nnewedges = i;
3444  start[nnodes] = i;
3445 }
3446
3447 /* gets edge conflicts */
3449  SCIP* scip, /**< SCIP data structure */
3450  const GRAPH* g /**< the graph */
3451  )
3452 {
3453  int* childcount;
3454  int nconflicts;
3455  const int nedges = g->edges;
3456  const int nedgesorg = g->orgedges;
3457
3458  assert(scip != NULL && g != NULL);
3459  assert(g->ancestors != NULL);
3460  assert(nedgesorg % 2 == 0);
3461
3462  printf("orgedes %d \n", nedgesorg);
3463
3464  SCIP_CALL( SCIPallocBufferArray(scip, &childcount, nedgesorg / 2) );
3465
3466  for( int e = 0; e < nedgesorg / 2; e++ )
3467  childcount[e] = 0;
3468
3469  for( int e = 0; e < nedges; e += 2 )
3470  for( IDX* curr = g->ancestors[e]; curr != NULL; curr = curr->parent )
3471  {
3472  assert(curr->index >= 0 && curr->index / 2 < nedgesorg / 2);
3473  childcount[curr->index / 2]++;
3474  }
3475
3476  nconflicts = 0;
3477
3478  for( int e = 0; e < nedgesorg / 2; e++ )
3479  if( childcount[e] > 1 )
3480  nconflicts++;
3481
3482  printf("nconflicts %d \n", nconflicts);
3483
3484  SCIPfreeBufferArray(scip, &childcount);
3485
3486  return SCIP_OKAY;
3487 }
3488
3489
3490 /** initialize graph */
3492  SCIP* scip, /**< SCIP data structure */
3493  GRAPH** g, /**< new graph */
3494  int ksize, /**< slots for nodes */
3495  int esize, /**< slots for edges */
3496  int layers /**< number of layers (only needed for packing, otherwise 1) */
3497  )
3498 {
3499  GRAPH* p;
3500
3501  assert(ksize > 0);
3502  assert(ksize < INT_MAX);
3503  assert(esize >= 0);
3504  assert(esize < INT_MAX);
3505  assert(layers > 0);
3506  assert(layers < SHRT_MAX);
3507
3508  SCIP_CALL( SCIPallocMemory(scip, g) );
3509  p = *g;
3510  assert(p != NULL);
3511
3512  /* ancestor data for retransformation after reductions */
3513  p->fixedges = NULL;
3514  p->ancestors = NULL;
3515  p->pcancestors = NULL;
3516  p->orgtail = NULL;
3518  p->rootedgeprevs = NULL;
3519  p->norgmodelknots = 0;
3520  p->norgmodeledges = 0;
3521  p->ksize = ksize;
3522  p->orgknots = 0;
3523  p->orgedges = 0;
3524  p->knots = 0;
3525  p->terms = 0;
3526  p->orgsource = UNKNOWN;
3527  p->stp_type = UNKNOWN;
3528  p->layers = layers;
3529  p->hoplimit = UNKNOWN;
3530  p->extended = FALSE;
3531  p->source = -1;
3532
3533  SCIP_CALL( SCIPallocMemoryArray(scip, &(p->term), ksize) );
3534  SCIP_CALL( SCIPallocMemoryArray(scip, &(p->mark), ksize) );
3535  SCIP_CALL( SCIPallocMemoryArray(scip, &(p->grad), ksize) );
3536  SCIP_CALL( SCIPallocMemoryArray(scip, &(p->inpbeg), ksize) );
3537  SCIP_CALL( SCIPallocMemoryArray(scip, &(p->outbeg), ksize) );
3538  SCIP_CALL( SCIPallocMemoryArray(scip, &(p->cost), esize) );
3539  SCIP_CALL( SCIPallocMemoryArray(scip, &(p->tail), esize) );
3540  SCIP_CALL( SCIPallocMemoryArray(scip, &(p->head), esize) );
3541  SCIP_CALL( SCIPallocMemoryArray(scip, &(p->ieat), esize) );
3542  SCIP_CALL( SCIPallocMemoryArray(scip, &(p->oeat), esize) );
3543
3544  p->esize = esize;
3545  p->edges = 0;
3546  p->prize = NULL;
3547  p->maxdeg = NULL;
3548  p->grid_coordinates = NULL;
3549  p->grid_ncoords = NULL;
3550  p->mincut_dist = NULL;
3552  p->mincut_numb = NULL;
3553  p->mincut_prev = NULL;
3554  p->mincut_next = NULL;
3555  p->mincut_temp = NULL;
3556  p->mincut_e = NULL;
3557  p->mincut_x = NULL;
3558  p->mincut_r = NULL;
3559  p->path_heap = NULL;
3560  p->path_state = NULL;
3561  p->term2edge = NULL;
3562
3563  SCIPdebugMessage("Initialized new graph \n");
3564
3565  return SCIP_OKAY;
3566 }
3567
3568 /** initialize data structures required to keep track of reductions */
3570  SCIP* scip, /**< SCIP data structure */
3571  GRAPH* graph /**< graph */
3572  )
3573 {
3574  IDX** ancestors; /* ancestor lists array (over all edges) */
3575  IDX** pcancestors; /* ancestor lists array (over all nodes) */
3576  int* tail; /* tail of all edges */
3578  int* orgtail; /* (original) tail of all original edges */
3580  int nedges;
3581  SCIP_Bool pcmw;
3582
3583  assert(scip != NULL);
3584  assert(graph != NULL);
3585
3586  pcmw = graph_pc_isPcMw(graph);
3587
3588  nedges = graph->edges;
3589
3590  SCIP_CALL( SCIPallocMemoryArray(scip, &(graph->orgtail), nedges) );
3591  SCIP_CALL( SCIPallocMemoryArray(scip, &(graph->orghead), nedges) );
3592
3593  tail = graph->tail;
3595  orgtail = graph->orgtail;
3597
3598  for( int e = 0; e < nedges; e++ )
3599  {
3600  orgtail[e] = tail[e];
3602  }
3603
3604  if( pcmw )
3605  {
3606  const int nnodes = graph->knots;
3607
3608  SCIP_CALL( SCIPallocMemoryArray(scip, &(graph->pcancestors), nnodes) );
3609
3610  pcancestors = graph->pcancestors;
3611
3612  for( int k = 0; k < nnodes; k++ )
3613  pcancestors[k] = NULL;
3614  }
3615
3616  SCIP_CALL( SCIPallocMemoryArray(scip, &(graph->ancestors), nedges) );
3617
3618  ancestors = graph->ancestors;
3619
3620  for( int e = 0; e < nedges; e++ )
3621  {
3622  SCIP_CALL( SCIPallocBlockMemory(scip, &(ancestors[e])) ); /*lint !e866*/
3623  (ancestors)[e]->index = e;
3624  (ancestors)[e]->parent = NULL;
3625  }
3626
3627  return SCIP_OKAY;
3628 }
3629
3630 /** enlarge given graph */
3632  SCIP* scip, /**< SCIP data structure */
3633  GRAPH* g, /**< graph to be resized */
3634  int ksize, /**< new node slots */
3635  int esize, /**< new edge slots */
3636  int layers /**< layers (set to -1 by default) */
3637  )
3638 {
3639  assert(scip != NULL);
3640  assert(g != NULL);
3641  assert((ksize < 0) || (ksize >= g->knots));
3642  assert((esize < 0) || (esize >= g->edges));
3643  assert((layers < 0) || (layers >= g->layers));
3644
3645  if( (layers > 0) && (layers != g->layers) )
3646  g->layers = layers;
3647
3648  if( (ksize > 0) && (ksize != g->ksize) )
3649  {
3650  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->term), ksize) );
3651  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->mark), ksize) );
3652  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->grad), ksize) );
3653  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->inpbeg), ksize) );
3654  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->outbeg), ksize) );
3655
3656  g->ksize = ksize;
3657  }
3658  if( (esize > 0) && (esize != g->esize) )
3659  {
3660  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->cost), esize) );
3661  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->tail), esize) );
3662  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->head), esize) );
3663  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->ieat), esize) );
3664  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->oeat), esize) );
3665
3666  g->esize = esize;
3667  }
3668
3669  return SCIP_OKAY;
3670 }
3671
3672
3673 /** free the graph */
3675  SCIP* scip, /**< SCIP data structure */
3676  GRAPH** graph, /**< graph to be freed */
3677  SCIP_Bool final /**< delete ancestor data structures? */
3678  )
3679 {
3680  GRAPH* p;
3681
3682  assert(scip != NULL);
3683  assert(graph != NULL);
3684
3685  p = *graph;
3686  assert(p != NULL);
3687
3688  graph_free_history(scip, p);
3689
3690  if( final )
3691  graph_free_historyDeep(scip, p);
3692
3693  if( p->prize != NULL )
3694  {
3695  assert(p->term2edge != NULL);
3696  SCIPfreeMemoryArray(scip, &(p->term2edge));
3697  SCIPfreeMemoryArray(scip, &(p->prize));
3698  }
3699
3700  if( p->stp_type == STP_DCSTP )
3701  {
3702  SCIPfreeMemoryArray(scip, &(p->maxdeg));
3703  }
3704  else if( p->stp_type == STP_RSMT )
3705  {
3706  if( p->grid_coordinates != NULL )
3707  {
3708  assert(p->grid_coordinates != NULL);
3709  for( int i = p->grid_dim - 1; i >= 0; i-- )
3710  SCIPfreeMemoryArray(scip, &(p->grid_coordinates[i]));
3711
3713  }
3714
3715  if( p->grid_ncoords != NULL )
3716  SCIPfreeMemoryArray(scip, &(p->grid_ncoords));
3717  }
3718
3719  SCIPfreeMemoryArray(scip, &(p->oeat));
3720  SCIPfreeMemoryArray(scip, &(p->ieat));
3722  SCIPfreeMemoryArray(scip, &(p->tail));
3723  SCIPfreeMemoryArray(scip, &(p->cost));
3724  SCIPfreeMemoryArray(scip, &(p->outbeg));
3725  SCIPfreeMemoryArray(scip, &(p->inpbeg));
3727  SCIPfreeMemoryArray(scip, &(p->mark));
3728  SCIPfreeMemoryArray(scip, &(p->term));
3730
3731  SCIPfreeMemory(scip, graph);
3732 }
3733
3734
3735 /** free the history */
3737  SCIP* scip, /**< SCIP data */
3738  GRAPH* p /**< graph data */
3739  )
3740 {
3741  if( p->ancestors != NULL )
3742  {
3743  const int nedges = p->edges;
3744
3745  for( int e = nedges - 1; e >= 0; e-- )
3746  {
3747  IDX* curr = p->ancestors[e];
3748  while( curr != NULL )
3749  {
3750  p->ancestors[e] = curr->parent;
3751  SCIPfreeBlockMemory(scip, &(curr));
3752  curr = p->ancestors[e];
3753  }
3754  }
3755  SCIPfreeMemoryArray(scip, &(p->ancestors));
3756  }
3757 }
3758
3759 /** free the deep history */
3761  SCIP* scip, /**< SCIP data */
3762  GRAPH* p /**< graph data */
3763  )
3764 {
3765  IDX* curr;
3766
3767  assert(scip != NULL);
3768  assert(p != NULL);
3769  assert(p->path_heap == NULL);
3770  assert(p->path_state == NULL);
3771
3772  if( p->pcancestors != NULL )
3773  {
3774  for( int e = p->norgmodelknots - 1; e >= 0; e-- )
3775  {
3776  curr = p->pcancestors[e];
3777  while( curr != NULL )
3778  {
3779  p->pcancestors[e] = curr->parent;
3780  SCIPfreeBlockMemory(scip, &(curr));
3781  curr = p->pcancestors[e];
3782  }
3783  }
3784  SCIPfreeMemoryArray(scip, &(p->pcancestors));
3785  }
3786
3787  if( p->orgtail != NULL )
3788  {
3790
3792  SCIPfreeMemoryArray(scip, &(p->orgtail));
3793  }
3794  curr = p->fixedges;
3795  while( curr != NULL )
3796  {
3797  p->fixedges = curr->parent;
3798  SCIPfreeBlockMemory(scip, &(curr));
3799
3800  curr = p->fixedges;
3801  }
3802 }
3803
3804 /** copy the data of the graph */
3806  SCIP* scip, /**< SCIP data structure */
3807  const GRAPH* orgraph, /**< original graph */
3808  GRAPH* copygraph /**< graph to be copied to */
3809  )
3810 {
3811  GRAPH* g = copygraph;
3812  const GRAPH* p = orgraph;
3813  const int ksize = p->ksize;
3814  const int esize = p->esize;
3815
3816  assert(scip != NULL);
3817  assert(orgraph != NULL);
3818  assert(copygraph != NULL);
3819  assert(ksize == g->ksize && ksize > 0);
3820  assert(esize == g->esize && esize >= 0);
3821
3824  g->knots = p->knots;
3825  g->terms = p->terms;
3826  g->edges = p->edges;
3827  g->source = p->source;
3828  g->orgsource = p->orgsource;
3829  g->orgedges = p->orgedges;
3830  g->orgknots = p->orgknots;
3831  g->grid_dim = p->grid_dim;
3832  g->stp_type = p->stp_type;
3833  g->hoplimit = p->hoplimit;
3834  g->extended = p->extended;
3835  g->term2edge = NULL;
3836  g->prize = NULL;
3837
3838  BMScopyMemoryArray(g->term, p->term, ksize);
3839  BMScopyMemoryArray(g->mark, p->mark, ksize);
3841  BMScopyMemoryArray(g->inpbeg, p->inpbeg, ksize);
3842  BMScopyMemoryArray(g->outbeg, p->outbeg, ksize);
3843  BMScopyMemoryArray(g->cost, p->cost, esize);
3844  BMScopyMemoryArray(g->tail, p->tail, esize);
3846  BMScopyMemoryArray(g->ieat, p->ieat, esize);
3847  BMScopyMemoryArray(g->oeat, p->oeat, esize);
3848
3849  if( g->stp_type == STP_PCSPG || g->stp_type == STP_RPCSPG || g->stp_type == STP_MWCSP || g->stp_type == STP_RMWCSP )
3850  {
3851  SCIP_CALL(SCIPallocMemoryArray(scip, &(g->prize), g->knots));
3852  SCIP_CALL(SCIPallocMemoryArray(scip, &(g->term2edge), g->knots));
3853
3854  for( int k = 0; k < g->knots; k++ )
3855  if( Is_term(p->term[k]) )
3856  g->prize[k] = 0.0;
3857  else
3858  g->prize[k] = p->prize[k];
3859
3860  assert(p->term2edge != NULL);
3861
3863  }
3864  else if( g->stp_type == STP_DCSTP )
3865  {
3866  assert(p->maxdeg != NULL);
3867
3868  SCIP_CALL(SCIPallocMemoryArray(scip, &(g->maxdeg), g->knots));
3869
3870  for( int k = 0; k < g->knots; k++ )
3871  g->maxdeg[k] = p->maxdeg[k];
3872  }
3873  else if( p->stp_type == STP_RSMT )
3874  {
3875  assert(p->grid_ncoords != NULL);
3876  assert(p->grid_coordinates != NULL);
3877
3879
3881  for( int k = 0; k < p->grid_dim; k++ )
3882  {
3883  SCIP_CALL(SCIPallocMemoryArray(scip, &(g->grid_coordinates[k]), p->terms)); /*lint !e866*/
3884  BMScopyMemoryArray(g->grid_coordinates[k], p->grid_coordinates[k], p->terms); /*lint !e866*/
3885  }
3887
3889  }
3890  assert(graph_valid(g));
3891
3892  return SCIP_OKAY;
3893 }
3894
3895 /** copy the graph */
3897  SCIP* scip, /**< SCIP data structure */
3898  const GRAPH* orgraph, /**< original graph */
3899  GRAPH** copygraph /**< graph to be created */
3900  )
3901 {
3902  const GRAPH* p = orgraph;
3903  assert(p != NULL);
3904
3905  SCIP_CALL( graph_init(scip, copygraph, p->ksize, p->esize, p->layers) );
3906
3907  SCIP_CALL( graph_copy_data(scip, orgraph, *copygraph) );
3908
3909  return SCIP_OKAY;
3910 }
3911
3913  const GRAPH* p /**< the graph */
3914  )
3915 {
3916  int i;
3917
3918  assert(p != NULL);
3919
3920  for(i = 0; i < p->knots; i++)
3922  (void)printf("Knot %d, term=%d, grad=%d, inpbeg=%d, outbeg=%d\n",
3923  i, p->term[i], p->grad[i], p->inpbeg[i], p->outbeg[i]);
3924
3925  (void)fputc('\n', stdout);
3926
3927  for(i = 0; i < p->edges; i++)
3928  if (p->ieat[i] != EAT_FREE)
3929  (void)printf("Edge %d, cost=%g, tail=%d, head=%d, ieat=%d, oeat=%d\n",
3930  i, p->cost[i], p->tail[i], p->head[i], p->ieat[i], p->oeat[i]);
3931
3932  (void)fputc('\n', stdout);
3933 }
3934
3935
3936 /** reinsert all hidden edges */
3938  GRAPH* g /**< the graph */
3939  )
3940 {/*lint --e{850}*/
3942  int tail;
3943  int e;
3944
3945  assert(g != NULL);
3946
3947  for( e = 0; e < g->edges; e++ )
3948  {
3949  if( g->ieat[e] == EAT_HIDE )
3950  {
3951  assert(e % 2 == 0);
3952  assert(g->oeat[e] == EAT_HIDE);
3953
3955  tail = g->tail[e];
3956
3959
3961  g->oeat[e] = g->outbeg[tail];
3963  g->outbeg[tail] = e;
3964
3965  e++;
3966
3967  assert(g->ieat[e] == EAT_HIDE);
3968  assert(g->oeat[e] == EAT_HIDE);
3971
3973  tail = g->tail[e];
3975  g->oeat[e] = g->outbeg[tail];
3977  g->outbeg[tail] = e;
3978  }
3979  }
3980 }
3981
3982
3983 /** pack the graph, i.e. build a new graph that discards deleted edges and nodes */
3985  SCIP* scip, /**< SCIP data structure */
3986  GRAPH* graph, /**< the graph */
3987  GRAPH** newgraph, /**< the new graph */
3988  SCIP_Bool verbose /**< verbose? */
3989  )
3990 {
3991  GRAPH* g;
3992  GRAPH* q;
3993  int* new;
3994  int e;
3995  int oldnnodes;
3996  int oldnedges;
3997  int nnodes;
3998  int nedges;
3999  SCIP_Bool rmw;
4000  SCIP_Bool pcmw;
4001
4002  assert(scip != NULL);
4003  assert(graph != NULL);
4004  assert(graph_valid(graph));
4005
4006  g = graph;
4007  nnodes = 0;
4008  nedges = 0;
4009  oldnnodes = g->knots;
4010  oldnedges = g->edges;
4011  SCIP_CALL( SCIPallocBufferArray(scip, &new, oldnnodes) );
4012
4013  if( verbose )
4014  printf("Reduced graph: ");
4015
4016  /* count nodes */
4017  for( int i = 0; i < oldnnodes; i++ )
4018  {
4019  /* are there incident edges to current node? */
4020  if( g->grad[i] > 0 )
4021  new[i] = nnodes++;
4022  else
4023  new[i] = -1;
4024  }
4025
4026  /* graph vanished? */
4027  if( nnodes == 0 )
4028  {
4029  SCIPfreeBufferArray(scip, &new);
4030  new = NULL;
4031  if( verbose )
4032  printf(" graph vanished!\n");
4033
4034  nnodes = 1;
4035  }
4036
4037  /* count edges */
4038  for( int i = 0; i < oldnedges; i++ )
4039  {
4040  if( g->oeat[i] != EAT_FREE )
4041  {
4042  assert(g->ieat[i] != EAT_FREE);
4043  nedges++;
4044  }
4045  }
4046
4047  assert(nnodes > 1 || nedges == 0);
4048  SCIP_CALL( graph_init(scip, newgraph, nnodes, nedges, g->layers) );
4049  q = *newgraph;
4052  q->orgsource = g->orgsource;
4053  q->orgtail = g->orgtail;
4055  q->orgknots = g->knots;
4056  q->orgedges = g->edges;
4057  q->stp_type = g->stp_type;
4058  q->maxdeg = g->maxdeg;
4059  q->grid_dim = g->grid_dim;
4060  q->grid_ncoords = g->grid_ncoords;
4062  q->fixedges = g->fixedges;
4063  q->hoplimit = g->hoplimit;
4064  q->extended = g->extended;
4065  q->pcancestors = g->pcancestors;
4066
4067  if( new == NULL )
4068  {
4069  q->ancestors = NULL;
4070  graph_free(scip, &g, FALSE);
4071
4072  if( q->stp_type == STP_RSMT )
4073  {
4074  q->grid_ncoords = NULL;
4075  q->grid_coordinates = NULL;
4076  }
4077
4079  q->source = 0;
4080  return SCIP_OKAY;
4081  }
4082
4083  SCIP_CALL( SCIPallocMemoryArray(scip, &(q->ancestors), nedges) );
4084
4085  rmw = g->stp_type == STP_RMWCSP;
4086  pcmw = (g->stp_type == STP_MWCSP || g->stp_type == STP_RPCSPG || g->stp_type == STP_PCSPG || g->stp_type == STP_RMWCSP);
4087  if( pcmw )
4088  SCIP_CALL( graph_pc_init(scip, q, nnodes, nnodes) );
4089
4090  /* add nodes (of positive degree) */
4091  if( rmw )
4092  {
4093  int i;
4094  for( i = 0; i < oldnnodes; i++ )
4095  g->mark[i] = (g->grad[i] > 0);
4096
4097  for( e = g->outbeg[g->source]; e != EAT_LAST; e = g->oeat[e] )
4098  {
4099  if( SCIPisGT(scip, g->cost[e], 0.0) && Is_term(g->term[g->head[e]]) )
4100  {
4102  g->mark[i] = FALSE;
4104  }
4105  }
4106  }
4107
4108  for( int i = 0; i < oldnnodes; i++ )
4109  {
4110  assert(g->term[i] < g->layers);
4111  if( g->grad[i] > 0 )
4112  {
4113  if( pcmw )
4114  {
4115  if( !Is_term(g->term[i]) || (rmw && g->mark[i]) )
4116  q->prize[q->knots] = g->prize[i];
4117  else
4118  q->prize[q->knots] = 0.0;
4119  }
4121  }
4122  }
4123
4125  assert(q->term[new[g->source]] == 0);
4126
4127  q->source = new[g->source];
4128
4129  if( g->stp_type == STP_RPCSPG || g->stp_type == STP_RMWCSP )
4130  q->prize[q->source] = FARAWAY;
4131
4133  for( int i = 0; i < oldnedges; i += 2 )
4134  {
4135  if( g->ieat[i] == EAT_FREE )
4136  {
4137  assert(g->oeat[i] == EAT_FREE);
4138  assert(g->ieat[i + 1] == EAT_FREE);
4139  assert(g->oeat[i + 1] == EAT_FREE);
4140  SCIPintListNodeFree(scip, &(g->ancestors[i]));
4141  SCIPintListNodeFree(scip, &(g->ancestors[i + 1]));
4142  continue;
4143  }
4144
4145  assert(g->oeat[i] != EAT_FREE);
4146  assert(g->ieat[i + 1] != EAT_FREE);
4147  assert(g->oeat[i + 1] != EAT_FREE);
4148  assert(new[g->tail[i]] >= 0);
4150
4151  e = q->edges;
4152
4153  q->ancestors[e] = NULL;
4154  q->ancestors[e + 1] = NULL;
4155  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(q->ancestors[e]), g->ancestors[i], NULL) );
4156  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(q->ancestors[e + 1]), g->ancestors[i + 1], NULL) );
4157
4158  assert(new[g->tail[i]] < nnodes && new[g->head[i]] < nnodes);
4159
4160  if( pcmw )
4162
4164  }
4165
4166  SCIPfreeBufferArray(scip, &new);
4167
4168  if( g->path_heap != NULL )
4169  graph_path_exit(scip, g);
4170
4171  g->stp_type = UNKNOWN;
4172  graph_free(scip, &g, FALSE);
4173
4174  assert(graph_valid(q));
4175
4176  if( verbose )
4177  printf("Nodes: %d Edges: %d Terminals: %d\n", q->knots, q->edges, q->terms);
4178
4179  return SCIP_OKAY;
4180 }
4181
4182
4183 /** traverse the graph and mark all reached nodes (g->mark[i] has to be FALSE for all i) */
4185  const GRAPH* g, /**< the new graph */
4186  int i /**< node to start from */
4187  )
4188 {
4189  int* gmark;
4190
4191  assert(g != NULL);
4192  assert(i >= 0);
4193  assert(i < g->knots);
4194
4195  gmark = g->mark;
4196
4197  if( !gmark[i] )
4198  {
4199  SCIP_QUEUE* queue;
4200  int a;
4202  int node;
4203  int* pnode;
4204
4205  gmark[i] = TRUE;
4206
4207  if( g->grad[i] == 0 )
4208  return;
4209
4210  SCIP_CALL_ABORT( SCIPqueueCreate(&queue, g->knots, 1.1) );
4211  SCIP_CALL_ABORT( SCIPqueueInsert(queue, &i));
4212
4213  /* BFS loop */
4214  while( !SCIPqueueIsEmpty(queue) )
4215  {
4216  pnode = (SCIPqueueRemove(queue));
4217  node = *pnode;
4218
4219  /* traverse outgoing arcs */
4220  for( a = g->outbeg[node]; a != EAT_LAST; a = g->oeat[a] )
4221  {
4223
4225  {
4228  }
4229  }
4230  }
4231  SCIPqueueFree(&queue);
4232  }
4233 }
4234
4235
4236 /** traverse the graph and mark all reached nodes (g->mark[i] has to be FALSE for all i) .... uses an array and should be faster
4237  * than graph_trail, but needs a scip */
4239  SCIP* scip, /**< scip struct */
4240  const GRAPH* g, /**< the new graph */
4241  int i /**< node to start from */
4242  )
4243 {
4244  int* const gmark = g->mark;
4245
4246  assert(scip != NULL);
4247  assert(g != NULL);
4248  assert(i >= 0);
4249  assert(i < g->knots);
4250
4251  if( !gmark[i] )
4252  {
4253  int* stackarr;
4254  int a;
4256  int node;
4257  int nnodes;
4258  int stacksize;
4259
4260  gmark[i] = TRUE;
4261
4262  if( g->grad[i] == 0 )
4263  return SCIP_OKAY;
4264
4265  nnodes = g->knots;
4266  stacksize = 0;
4267
4268  SCIP_CALL( SCIPallocBufferArray(scip, &stackarr, nnodes) );
4269
4270  stackarr[stacksize++] = i;
4271
4272  /* DFS loop */
4273  while( stacksize != 0 )
4274  {
4275  node = stackarr[--stacksize];
4276
4277  /* traverse outgoing arcs */
4278  for( a = g->outbeg[node]; a != EAT_LAST; a = g->oeat[a] )
4279  {
4281
4283  {
4286  }
4287  }
4288  }
4289  SCIPfreeBufferArray(scip, &stackarr);
4290  }
4291  return SCIP_OKAY;
4292 }
4293
4294 /** checks whether all terminals are reachable from root */
4296  SCIP* scip, /**< scip struct */
4297  const GRAPH* g, /**< the new graph */
4298  SCIP_Bool* reachable /**< are they reachable? */
4299  )
4300 {
4301  const int nnodes = g->knots;
4302
4303  assert(g != NULL);
4304  assert(reachable != NULL);
4305
4306  for( int k = 0; k < nnodes; k++ )
4307  g->mark[k] = FALSE;
4308
4309  *reachable = TRUE;
4310
4311  graph_trail_arr(scip, g, g->source);
4312
4313  for( int k = 0; k < nnodes; k++ )
4314  if( Is_term(g->term[k]) && !g->mark[k] )
4315  {
4316  *reachable = FALSE;
4317  break;
4318  }
4319
4320  return SCIP_OKAY;
4321 }
4322
4323 /** is the given graph valid? */
4325  const GRAPH* g /**< the new graph */
4326  )
4327 {
4328  const char* fehler1 = "*** Graph invalid: Head invalid, Knot %d, Edge %d, Tail=%d, Head=%d\n";
4329  const char* fehler2 = "*** Graph invalid: Tail invalid, Knot %d, Edge %d, Tail=%d, Head=%d\n";
4330  const char* fehler3 = "*** Graph invalid: Source invalid, Layer %d, Source %d, Terminal %d\n";
4331  const char* fehler4 = "*** Graph invalid: FREE invalid, Edge %d/%d\n";
4332  const char* fehler5 = "*** Graph invalid: Anti invalid, Edge %d/%d, Tail=%d/%d, Head=%d/%d\n";
4333  const char* fehler6 = "*** Graph invalid: Knot %d with Grad 0 has Edges\n";
4334  const char* fehler7 = "*** Graph invalid: Knot %d not connected\n";
4335  const char* fehler9 = "*** Graph invalid: Wrong Terminal count, count is %d, should be %d\n";
4336
4337  int k;
4338  int e;
4339  int nterms;
4340  int nnodes;
4341  int nedges;
4342
4343  assert(g != NULL);
4344
4345  nterms = g->terms;
4346  nedges = g->edges;
4347  nnodes = g->knots;
4348
4349  for( k = 0; k < nnodes; k++ )
4350  {
4351  if( Is_term(g->term[k]) )
4352  {
4353  nterms--;
4354  }
4355  for( e = g->inpbeg[k]; e != EAT_LAST; e = g->ieat[e] )
4356  if( g->head[e] != k )
4357  break;
4358
4359  if( e != EAT_LAST )
4360  return((void)fprintf(stderr, fehler1, k, e, g->tail[e], g->head[e]), FALSE);
4361
4362  for( e = g->outbeg[k]; e != EAT_LAST; e = g->oeat[e] )
4363  if( g->tail[e] != k )
4364  break;
4365
4366  if( e != EAT_LAST )
4367  return((void)fprintf(stderr, fehler2, k, e, g->tail[e], g->head[e]), FALSE);
4368  }
4369  if( nterms != 0 )
4370  return((void)fprintf(stderr, fehler9, g->terms, g->terms - nterms), FALSE);
4371
4372  if( (g->source < 0 )
4373  || (g->source >= g->knots)
4374  || (g->term[g->source] != 0))
4375  return((void)fprintf(stderr, fehler3,
4376  0, g->source, g->term[g->source]), FALSE);
4377
4378  for( e = 0; e < nedges; e += 2 )
4379  {
4380  if( (g->ieat[e] == EAT_FREE) && (g->oeat[e] == EAT_FREE)
4381  && (g->ieat[e + 1] == EAT_FREE) && (g->oeat[e + 1] == EAT_FREE) )
4382  continue;
4383
4384  if( (g->ieat[e] == EAT_FREE) || (g->oeat[e] == EAT_FREE)
4385  || (g->ieat[e + 1] == EAT_FREE) || (g->oeat[e + 1] == EAT_FREE) )
4386  return((void)fprintf(stderr, fehler4, e, e + 1), FALSE);
4387
4388  if( (g->head[e] != g->tail[e + 1]) || (g->tail[e] != g->head[e + 1]) )
4389  return((void)fprintf(stderr, fehler5,
4390  e, e + 1, g->head[e], g->tail[e + 1],
4391  g->tail[e], g->head[e + 1]), FALSE);
4392  }
4393
4394  for( k = 0; k < nnodes; k++ )
4395  g->mark[k] = FALSE;
4396
4397  graph_trail(g, g->source);
4398
4399  for( k = 0; k < nnodes; k++ )
4400  {
4402  && ((g->inpbeg[k] != EAT_LAST) || (g->outbeg[k] != EAT_LAST)) )
4403  return((void)fprintf(stderr, fehler6, k), FALSE);
4404
4405  if( !g->mark[k] && ((g->grad[k] > 0) || (Is_term(g->term[k])))
4406  && g->stp_type != STP_PCSPG && g->stp_type != STP_MWCSP && g->stp_type != STP_RMWCSP )
4407  return((void)fprintf(stderr, fehler7, k), FALSE);
4408  }
4409
4410  if( (g->stp_type == STP_PCSPG || g->stp_type == STP_MWCSP || g->stp_type == STP_RPCSPG || g->stp_type == STP_RMWCSP) )
4411  {
4412  int npterms = 0;
4413  const int root = g->source;
4414  const SCIP_Bool extended = g->extended;
4415  const SCIP_Bool rooted = (g->stp_type == STP_RPCSPG || g->stp_type == STP_RMWCSP);
4416  nterms = 0;
4417
4418  assert(g->prize != NULL);
4419  assert(g->term2edge != NULL);
4420
4421  for( k = 0; k < nnodes; k++ )
4422  {
4423  if( k == root || (rooted && g->term2edge[k] < 0) )
4424  continue;
4425
4426  if( (extended ? Is_term(g->term[k]) : Is_pterm(g->term[k])) )
4427  {
4428  int e2;
4429  int pterm;
4430  const int term = k;
4431  nterms++;
4432
4433  if( g->grad[k] != 2 )
4434  {
4435  SCIPdebugMessage("terminal degree != 2 for %d \n", k);
4436  return FALSE;
4437  }
4438
4439  for( e = g->inpbeg[term]; e != EAT_LAST; e = g->ieat[e] )
4440  if( g->tail[e] == root )
4441  break;
4442
4443  if( e == EAT_LAST )
4444  {
4445  SCIPdebugMessage("no edge to root for term %d \n", term);
4446  return FALSE;
4447  }
4448
4449  for( e2 = g->outbeg[term]; e2 != EAT_LAST; e2 = g->oeat[e2] )
4450  {
4452  if( (extended ? Is_pterm(g->term[pterm]) : Is_term(g->term[pterm])) && pterm != root )
4453  break;
4454  }
4455
4456  if( e2 == EAT_LAST)
4457  {
4458  SCIPdebugMessage("no terminal for dummy %d \n", g->head[e2]);
4459  return FALSE;
4460  }
4461
4462  assert(pterm != root);
4463
4464  if( e2 != g->term2edge[term] )
4465  {
4466  SCIPdebugMessage("term2edge for node %d faulty \n", term);
4467  return FALSE;
4468  }
4469
4470  if( g->cost[e] != g->prize[pterm] )
4471  {
4472  SCIPdebugMessage("prize mismatch for node %d: \n", k);
4473  return FALSE;
4474  }
4475  }
4476  else if( (extended ? Is_pterm(g->term[k]) : Is_term(g->term[k])) )
4477  {
4478  npterms++;
4479  }
4480  }
4481  if( nterms != npterms || nterms != g->terms - 1 )
4482  {
4483  if( !rooted )
4484  {
4485  SCIPdebugMessage("wrong terminal count \n");
4486  return FALSE;
4487  }
4488  }
4489
4490  for( k = 0; k < nnodes; k++ )
4491  {
4492  g->mark[k] = (g->grad[k] > 0);
4493
4494  if( !extended && (Is_pterm(g->term[k]) || k == root) )
4495  g->mark[k] = FALSE;
4496  }
4497  if( !extended && (g->stp_type == STP_RPCSPG || g->stp_type == STP_RMWCSP) )
4498  g->mark[root] = TRUE;
4499
4500  }
4501  else
4502  {
4503  for( k = 0; k < nnodes; k++ )
4504  g->mark[k] = (g->grad[k] > 0);
4505  }
4506
4507  return TRUE;
4508 }
SCIP_RETCODE graph_sol_getOrg(SCIP *scip, const GRAPH *transgraph, const GRAPH *orggraph, const int *transsoledge, int *orgsoledge)
Definition: grphbase.c:3214
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
static volatile int nterms
Definition: interrupt.c:37
int *RESTRICT mincut_e
Definition: grph.h:113
#define NULL
Definition: def.h:253
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:80
void graph_sol_setNodeList(const GRAPH *g, STP_Bool *solnode, IDX *listnode)
Definition: grphbase.c:3170
SCIP_Bool graph_pc_isPcMw(const GRAPH *g)
Definition: grphbase.c:2184
Definition: grph.h:96
int *RESTRICT mincut_x
Definition: grph.h:114
SCIP_RETCODE graph_init(SCIP *scip, GRAPH **g, int ksize, int esize, int layers)
Definition: grphbase.c:3491
int *RESTRICT orgtail
Definition: grph.h:97
Definition: grph.h:57
int source
Definition: grph.h:67
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip_mem.h:70
SCIP_RETCODE graph_grid_create(SCIP *scip, GRAPH **gridgraph, int **coords, int nterms, int grid_dim, int scale_order)
Definition: grphbase.c:582
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:69
SCIP_RETCODE graph_copy(SCIP *scip, const GRAPH *orgraph, GRAPH **copygraph)
Definition: grphbase.c:3896
SCIP_RETCODE SCIPqueueInsert(SCIP_QUEUE *queue, void *elem)
Definition: misc.c:1018
int terms
Definition: grph.h:64
SCIP_RETCODE graph_pc_init(SCIP *scip, GRAPH *g, int sizeprize, int sizeterm2edge)
Definition: grphbase.c:766
SCIPInterval pow(const SCIPInterval &x, const SCIPInterval &y)
void graph_pc_updateTerm2edge(GRAPH *newgraph, const GRAPH *oldgraph, int newtail, int newhead, int oldtail, int oldhead)
Definition: grphbase.c:928
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:53
SCIP_Bool graph_sol_valid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: grphbase.c:3066
void graph_pc_adaptSap(SCIP *scip, SCIP_Real bigM, GRAPH *graph, SCIP_Real *offset)
Definition: grphbase.c:1174
void graph_pc_chgPrize(SCIP *scip, GRAPH *g, SCIP_Real newprize, int i)
Definition: grphbase.c:2031
SCIP_RETCODE graph_knot_contract(SCIP *scip, GRAPH *p, int *solnode, int t, int s)
Definition: grphbase.c:2429
int norgmodeledges
Definition: grph.h:88
int *RESTRICT maxdeg
Definition: grph.h:78
#define EAT_LAST
Definition: grph.h:31
#define Edge_anti(a)
Definition: grph.h:171
void graph_pc_presolExit(SCIP *scip, GRAPH *g)
Definition: grphbase.c:837
#define RESTRICT
Definition: def.h:265
SCIP_Bool graph_valid(const GRAPH *g)
Definition: grphbase.c:4324
SCIP_RETCODE graph_pc_getSapShift(SCIP *scip, GRAPH *graph, GRAPH **newgraph, SCIP_Real *offset)
Definition: grphbase.c:1204
int *RESTRICT mincut_temp
Definition: grph.h:112
#define BLOCKED
Definition: grph.h:157
void graph_uncover(GRAPH *g)
Definition: grphbase.c:3937
void * SCIPqueueRemove(SCIP_QUEUE *queue)
Definition: misc.c:1069
#define FALSE
Definition: def.h:73
SCIP_RETCODE graph_knot_delPseudo(SCIP *scip, GRAPH *g, const SCIP_Real *edgecosts, const SCIP_Real *cutoffs, const SCIP_Real *cutoffsrev, int vertex, SCIP_Bool *success)
Definition: grphbase.c:2258
static int getNodeNumber(int grid_dim, int shiftcoord, int *ncoords, int *currcoord)
Definition: grphbase.c:143
SCIP_RETCODE graph_trail_arr(SCIP *scip, const GRAPH *g, int i)
Definition: grphbase.c:4238
int *RESTRICT inpbeg
Definition: grph.h:74
void graph_free_history(SCIP *scip, GRAPH *p)
Definition: grphbase.c:3736
int *RESTRICT path_state
Definition: grph.h:119
#define STP_RMWCSP
Definition: grph.h:50
SCIP_RETCODE graph_pc_2rmw(SCIP *scip, GRAPH *graph)
Definition: grphbase.c:1737
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE graph_copy_data(SCIP *scip, const GRAPH *orgraph, GRAPH *copygraph)
Definition: grphbase.c:3805
void graph_path_exit(SCIP *, GRAPH *)
Definition: grphpath.c:466
SCIP_Real graph_sol_getObj(const SCIP_Real *edgecost, const int *soledge, SCIP_Real offset, int nedges)
Definition: grphbase.c:3196
SCIP_RETCODE graph_pc_2pc(SCIP *scip, GRAPH *graph)
Definition: grphbase.c:1516
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
#define STP_PCSPG
Definition: grph.h:40
#define SCIPdebugMessage
Definition: pub_message.h:77
void graph_pc_2org(GRAPH *graph)
Definition: grphbase.c:964
#define STP_DELPSEUDO_MAXNEDGES
Definition: grphbase.c:45
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
Definition: grph.h:98
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
SCIP_VAR ** x
Definition: circlepacking.c:54
SCIP_EXPORT void SCIPsortInt(int *intarray, int len)
SCIP_Real graph_pc_getPosPrizeSum(SCIP *scip, const GRAPH *graph)
Definition: grphbase.c:1054
SCIP_RETCODE graph_sol_reroot(SCIP *scip, GRAPH *g, int *result, int newroot)
Definition: grphbase.c:2943
SCIP_RETCODE graph_pack(SCIP *scip, GRAPH *graph, GRAPH **newgraph, SCIP_Bool verbose)
Definition: grphbase.c:3984
int *RESTRICT mark
Definition: grph.h:70
IDX * fixedges
Definition: grph.h:85
SCIP_RETCODE graph_edge_reinsert(SCIP *scip, GRAPH *g, int e1, int k1, int k2, SCIP_Real cost, IDX *ancestors0, IDX *ancestors1, IDX *revancestors0, IDX *revancestors1, SCIP_Bool forcedelete)
Definition: grphbase.c:2753
void graph_pc_subtractPrize(SCIP *scip, GRAPH *g, SCIP_Real cost, int i)
Definition: grphbase.c:1988
SCIP_RETCODE graph_pc_mw2rmw(SCIP *scip, GRAPH *graph, SCIP_Real prizesum)
Definition: grphbase.c:1846
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void SCIPintListNodeFree(SCIP *scip, IDX **node)
Definition: misc_stp.c:205
void graph_show(const GRAPH *p)
Definition: grphbase.c:3912
Definition: grphbase.c:2196
static SCIP_Bool cutoffEdge(SCIP *scip, const SCIP_Real *cutoffs, const SCIP_Real *cutoffsrev, const SCIP_Real *ecost, const SCIP_Real *ecostrev, int edgeidx1, int edgeidx2, int cutoffidx)
Definition: grphbase.c:53
SCIP_Bool SCIPqueueIsEmpty(SCIP_QUEUE *queue)
Definition: misc.c:1173
int *RESTRICT oeat
Definition: grph.h:103
#define CONNECT
Definition: grph.h:154
void graph_edge_printInfo(SCIP *scip, const GRAPH *g, int e)
Definition: grphbase.c:2931
int *RESTRICT mincut_dist
Definition: grph.h:106
miscellaneous methods used for solving Steiner problems
SCIP_RETCODE SCIPintListNodeAppendCopy(SCIP *scip, IDX **node1, IDX *node2, SCIP_Bool *conflict)
Definition: misc_stp.c:94
SCIP_Bool extended
Definition: grph.h:128
#define STP_SAP
Definition: grph.h:39
int stp_type
Definition: grph.h:127
IDX ** ancestors
Definition: grph.h:86
int orgedges
Definition: grph.h:93
#define Is_pterm(a)
Definition: grph.h:169
unsigned char STP_Bool
Definition: grph.h:52
void graph_pc_2transcheck(GRAPH *graph)
Definition: grphbase.c:1041
#define STP_DCSTP
Definition: grph.h:43
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:124
SCIP_Real * prize
Definition: grph.h:82
static void compEdges(int coord, int grid_dim, int *ncoords, int *currcoord, int *edgecosts, int *gridedgecount, int **coords, int **gridedges)
Definition: grphbase.c:237
SCIP_RETCODE graph_obstgrid_create(SCIP *scip, GRAPH **gridgraph, int **coords, int **obst_coords, int nterms, int grid_dim, int nobstacles, int scale_order)
Definition: grphbase.c:419
#define SCIPreallocMemoryArray(scip, ptr, newnum)
Definition: scip_mem.h:59
Definition: grph.h:73
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
int graph_pc_deleteTerm(SCIP *scip, GRAPH *g, int i)
Definition: grphbase.c:1941
SCIP_Bool graph_pc_term2edgeConsistent(const GRAPH *g)
Definition: grphbase.c:853
internal miscellaneous methods
void graph_free(SCIP *scip, GRAPH **graph, SCIP_Bool final)
Definition: grphbase.c:3674
void graph_edge_del(SCIP *scip, GRAPH *g, int e, SCIP_Bool freeancestors)
Definition: grphbase.c:2837
int knots
Definition: grph.h:62
#define SCIP_CALL(x)
Definition: def.h:365
SCIP_RETCODE graph_get_edgeConflicts(SCIP *scip, const GRAPH *g)
Definition: grphbase.c:3448
int * term2edge
Definition: grph.h:80
IDX ** pcancestors
Definition: grph.h:87
SCIP_VAR * h
Definition: circlepacking.c:59
void graph_pc_knot2nonTerm(GRAPH *g, int node)
Definition: grphbase.c:909
SCIP_RETCODE graph_resize(SCIP *scip, GRAPH *g, int ksize, int esize, int layers)
Definition: grphbase.c:3631
#define EAT_HIDE
Definition: grph.h:32
SCIP_RETCODE SCIPqueueCreate(SCIP_QUEUE **queue, int initsize, SCIP_Real sizefac)
Definition: misc.c:932
SCIP_RETCODE graph_pc_presolInit(SCIP *scip, GRAPH *g)
Definition: grphbase.c:794
int orgknots
Definition: grph.h:63
#define Is_gterm(a)
Definition: grph.h:170
#define FARAWAY
Definition: grph.h:156
Definition: grph.h:107
#define STP_SPG
Definition: grph.h:38
void graph_trail(const GRAPH *g, int i)
Definition: grphbase.c:4184
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
void graph_get_csr(const GRAPH *g, int *RESTRICT edgearr, int *RESTRICT tailarr, int *RESTRICT start, int *nnewedges)
Definition: grphbase.c:3417
#define SCIP_Bool
Definition: def.h:70
int *RESTRICT ieat
Definition: grph.h:102
int *RESTRICT path_heap
Definition: grph.h:118
#define STP_MWCSP
Definition: grph.h:47
int *RESTRICT tail
Definition: grph.h:95
SCIP_Bool graph_sol_unreduced(SCIP *scip, const GRAPH *graph, const int *result)
Definition: grphbase.c:3046
void graph_pc_2trans(GRAPH *graph)
Definition: grphbase.c:1002
SCIP_RETCODE graph_pc_2rpc(SCIP *scip, GRAPH *graph)
Definition: grphbase.c:1597
int *RESTRICT term
Definition: grph.h:68
void graph_get_NVET(const GRAPH *graph, int *nnodes, int *nedges, int *nterms)
Definition: grphbase.c:3382
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:124
static void compEdgesObst(int coord, int grid_dim, int nobstacles, int *ncoords, int *currcoord, int *edgecosts, int *gridedgecount, int **coords, int **gridedges, int **obst_coords, char *inobstacle)
Definition: grphbase.c:172
static long * number
int *RESTRICT mincut_prev
Definition: grph.h:110
int grid_dim
Definition: grph.h:122
includes various files containing graph methods used for Steiner tree problems
SCIP_RETCODE graph_init_history(SCIP *scip, GRAPH *graph)
Definition: grphbase.c:3569
int ** grid_coordinates
Definition: grph.h:124
void graph_edge_hide(GRAPH *g, int e)
Definition: grphbase.c:2887
Portable defintions.
SCIP_RETCODE graph_pc_contractEdge(SCIP *scip, GRAPH *g, int *solnode, int t, int s, int i)
Definition: grphbase.c:2101
int *RESTRICT mincut_numb
Definition: grph.h:109
int layers
Definition: grph.h:65
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:67
#define Is_term(a)
Definition: grph.h:168
#define EAT_FREE
Definition: grph.h:30
SCIP_Real * cost
Definition: grph.h:94
Definition: grphbase.c:44
void graph_free_historyDeep(SCIP *scip, GRAPH *p)
Definition: grphbase.c:3760
int *RESTRICT rootedgeprevs
Definition: grph.h:99
SCIP_VAR * a
Definition: circlepacking.c:57
SCIP_RETCODE graph_pc_2mw(SCIP *scip, GRAPH *graph, SCIP_Real *maxweights)
Definition: grphbase.c:1678
#define SCIP_Real
Definition: def.h:164
SCIP_RETCODE graph_sol_markPcancestors(SCIP *scip, IDX **pcancestors, const int *tails, const int *heads, int orgnnodes, STP_Bool *solnodemark, STP_Bool *soledgemark, int *solnodequeue, int *nsolnodes, int *nsoledges)
Definition: grphbase.c:3288
int esize
Definition: grph.h:91
SCIP_VAR ** y
Definition: circlepacking.c:55
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int *RESTRICT outbeg
Definition: grph.h:76
SCIP_RETCODE SCIPStpHeurTMPrunePc(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int *result, STP_Bool *connected)
Definition: heur_tm.c:167
shortest paths based primal heuristics for Steiner problems
SCIP_RETCODE graph_knot_contractLowdeg2High(SCIP *scip, GRAPH *g, int *solnode, int t, int s)
Definition: grphbase.c:2662
int edges
Definition: grph.h:92
int * grid_ncoords
Definition: grph.h:123
#define flipedge(edge)
Definition: grph.h:150
void graph_knot_chg(GRAPH *p, int node, int term)
Definition: grphbase.c:2218
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
int ksize
Definition: grph.h:61
#define UNKNOWN
Definition: sepa_mcf.c:4081
int *RESTRICT mincut_r
Definition: grph.h:115
#define STP_RSMT
Definition: grph.h:45
#define nnodes
Definition: gastrans.c:65
SCIP_RETCODE graph_pc_getSap(SCIP *scip, GRAPH *graph, GRAPH **newgraph, SCIP_Real *offset)
Definition: grphbase.c:1075
int graph_edge_redirect(SCIP *scip, GRAPH *g, int eki, int k, int j, SCIP_Real cost, SCIP_Bool forcedelete)
Definition: grphbase.c:2681
#define STP_OARSMT
Definition: grph.h:46
SCIP_RETCODE graph_pc_contractEdgeAncestors(SCIP *scip, GRAPH *g, int t, int s, int ets)
Definition: grphbase.c:2075
void SCIPqueueFree(SCIP_QUEUE **queue)
Definition: misc.c:956
static void removeEdge(GRAPH *g, int e)
Definition: grphbase.c:89
struct Int_List_Node * parent
Definition: misc_stp.h:76
#define SCIP_CALL_ABORT(x)
Definition: def.h:344
int hoplimit
Definition: grph.h:89
SCIP_RETCODE SCIPStpHeurTMPrune(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int layer, int *result, STP_Bool *connected)
Definition: heur_tm.c:555
#define STP_RPCSPG
Definition: grph.h:41
void graph_knot_del(SCIP *scip, GRAPH *g, int k, SCIP_Bool freeancestors)
Definition: grphbase.c:2242
void graph_edge_add(SCIP *scip, GRAPH *g, int tail, int head, SCIP_Real cost1, SCIP_Real cost2)
Definition: grphbase.c:2786
int *RESTRICT mincut_next
Definition: grph.h:111
SCIP_RETCODE graph_pc_getRsap(SCIP *scip, GRAPH *graph, GRAPH **newgraph, int *rootcands, int nrootcands, int root)
Definition: grphbase.c:1365
int norgmodelknots
Definition: grph.h:60
void graph_pc_2orgcheck(GRAPH *graph)
Definition: grphbase.c:1028
int orgsource
Definition: grph.h:66
SCIP_RETCODE graph_grid_coordinates(SCIP *scip, int **coords, int **nodecoords, int *ncoords, int node, int grid_dim)
Definition: grphbase.c:730
SCIP_RETCODE graph_termsReachable(SCIP *scip, const GRAPH *g, SCIP_Bool *reachable)
Definition: grphbase.c:4295