# SCIP

Solving Constraint Integer Programs

graph_delpseudo.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file graph_delpseudo.c
17  * @brief includes graph pseudo deletion methods for Steiner problems
18  * @author Daniel Rehfeldt
19  *
20  * Graph node or edge pseudo-deletion methods (aka replacement methods) for Steiner problems
21  *
22  */
23
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
25
26 /*lint -esym(766,stdlib.h) -esym(766,malloc.h) */
27 /*lint -esym(766,string.h) */
28
29 #include "graph.h"
30 #include "portab.h"
31
32
33 #define STP_DELPSEUDO_NOEDGE -1
34 #define STP_DELPSEUDO_SKIPEDGE -2
35
36
37
38 /** Internal data for pseudo-deletion.
39  * Is used for both pseudo-elimination of vertex and edge.
40  * In the latter case, the adjacency information is w.r.t. the head of the edge. */
41 typedef struct pseudo_deletion
42 {
43  SCIP_Real* ecost; /**< edge cost */
44  SCIP_Real* ecostrev; /**< reverse edge cost */
45  SCIP_Real* ecostreal; /**< reverse edge cost */
48  int* incedge; /**< incident edges */
50  int* neigbedge; /**< neighboring edges array */
51  SCIP_Real vertexprize; /**< prize for PC (either of head of edge, or of vertex itself) */
52  int degree; /**< degree of vertex to be deleted */
53  int ancestorsnode; /**< ancestor node for PC (either of head of edge, or of vertex itself) */
54  int edge; /**< edge for pseudo-deletion or UNKNOWN otherwise */
55 } DELPSEUDO;
56
57
58
59 /*
60  * Local methods
61  */
62
63 /** can edge in pseudo-elimination method be cut off? */
64 inline static
66  SCIP* scip, /**< SCIP data */
67  const SCIP_Real* cutoffs, /**< cutoff values for each incident edge */
68  const SCIP_Real* cutoffsrev, /**< revere cutoff values (or NULL if undirected) */
69  const SCIP_Real* ecost, /**< edge cost*/
70  const SCIP_Real* ecostrev, /**< reverse edge cost */
71  SCIP_Real prize, /**< prize if PcMw, 0.0 otherwise */
72  int edgeidx1, /**< index of first edge to be checked (wrt provided arrays) */
73  int edgeidx2, /**< index of second edge to be checked (wrt provided arrays) */
74  int cutoffidx /**< index for cutoff array */
75  )
76 {
77  SCIP_Real newcost;
78
79  assert(edgeidx1 != edgeidx2);
80
81  if( cutoffs == NULL )
82  return FALSE;
83
84  newcost = ecostrev[edgeidx1] + ecost[edgeidx2] - prize;
85
86  /* NOTE: don't replace by GT, to keep epsilon change valid! */
87  if( !SCIPisGT(scip, newcost, cutoffs[cutoffidx]) )
88  return FALSE;
89
90  if( cutoffsrev != NULL )
91  {
92  const SCIP_Real newcostrev = ecost[edgeidx1] + ecostrev[edgeidx2];
93
94  if( !SCIPisGT(scip, newcostrev, cutoffsrev[cutoffidx]) )
95  return FALSE;
96  }
97
98  return TRUE;
99 }
100
101 #ifndef NDEBUG
102 /** in edge deletion mode? */
103 static
105  const DELPSEUDO* delpseudo /**< data */
106 )
107 {
108  assert(delpseudo);
109  assert(delpseudo->edge == UNKNOWN || delpseudo->edge >= 0);
110
111  return (delpseudo->edge != UNKNOWN);
112 }
113 #endif
114
115
116 /** gets position of deletion edge in replacement arrays */
117 static inline
119  const DELPSEUDO* delpseudo /**< data */
120 )
121 {
122  const int edge_rev = flipedge(delpseudo->edge);
123  const int degree = delpseudo->degree;
124  const int* const incedges = delpseudo->incedge;
125  int pos = -1;
126
127  assert(edge_rev >= 0);
128  assert(delPseudoIsEdgeDeletionMode(delpseudo));
129
130  for( int i = 0; i < degree; i++ )
131  {
132  if( edge_rev == incedges[i] )
133  {
134  pos = i;
135  break;
136  }
137  }
138
139  assert(0 <= pos && pos < degree);
140
141  return pos;
142 }
143
144
145 /** initializes */
146 static
148  SCIP* scip, /**< SCIP data */
149  const SCIP_Real* edgecosts, /**< edge costs for cutoff */
150  const REDCOST* redcostdata, /**< reduced cost data for adaptation or NULL */
151  int vertex, /**< the vertex */
152  GRAPH* g, /**< graph */
153  DELPSEUDO* delpseudo /**< data */
154 )
155 {
156  SCIP_Real* RESTRICT ecost;
157  SCIP_Real* RESTRICT ecostrev;
158  SCIP_Real* RESTRICT ecostreal;
159  SCIP_Real* RESTRICT ecostadapt = NULL;
160  SCIP_Real* RESTRICT ecostadaptrev = NULL;
161  int* RESTRICT incedge;
163  int* RESTRICT neigbedge;
164  int edgecount = 0;
165  const int redcost_nlevels = redcostdata ? redcosts_getNlevels(redcostdata) : -1;
166
167  if( Is_term(g->term[vertex]) )
168  {
169  assert(graph_pc_isPcMw(g));
170  assert(!graph_pc_knotHasMaxPrize(g, vertex) );
171  assert(!delPseudoIsEdgeDeletionMode(delpseudo));
172
173  delpseudo->vertexprize = g->prize[vertex];
174  delpseudo->ancestorsnode = vertex;
175
176  /* NOTE: for degree 3 the deletion is always possible.
177  * Thus, we can already manipulate the graph here */
178  graph_pc_termToNonTerm(scip, g, vertex);
179
181
182  assert(delpseudo->vertexprize > 0.0);
183  assert(delpseudo->degree == 3);
184  }
185  else
186  {
187  delpseudo->vertexprize = 0.0;
188  delpseudo->ancestorsnode = -1;
190
191  if( g->pcancestors && g->pcancestors[vertex] )
192  {
193  assert(graph_pc_isPcMw(g));
194  assert(SCIPisZero(scip, g->prize[vertex]));
195
196  delpseudo->ancestorsnode = vertex;
197  }
198  }
199
200  if( redcostdata )
201  {
204  }
205
212
213  /* save the state of all incident edges */
214  for( int e = g->outbeg[vertex]; e != EAT_LAST; e = g->oeat[e] )
215  {
216  const int e_rev = flipedge(e);
217  assert(e >= 0);
218
219  if( redcostdata )
220  {
221  for( int i = 0; i < redcost_nlevels; i++ )
222  {
223  const SCIP_Real* const redcosts = redcosts_getEdgeCosts(redcostdata, i);
224  const int position = i * STP_DELPSEUDO_MAXGRAD + edgecount;
227  }
228  }
229
230  incedge[edgecount] = e;
231  ecostreal[edgecount] = g->cost[e];
232  ecost[edgecount] = edgecosts[e];
233  ecostrev[edgecount] = edgecosts[e_rev];
235
237  }
238
239  assert(edgecount == delpseudo->degree);
240
241  delpseudo->ecost = ecost;
242  delpseudo->ecostrev = ecostrev;
243  delpseudo->ecostreal = ecostreal;
246  delpseudo->incedge = incedge;
248  delpseudo->neigbedge = neigbedge;
249
250  return SCIP_OKAY;
251 }
252
253
254 /** initializes for check */
255 static
257  SCIP* scip, /**< SCIP data */
258  const GRAPH* g, /**< graph */
259  const SCIP_Real* edgecosts, /**< edge costs for cutoff */
260  int vertex, /**< the vertex */
261  DELPSEUDO* delpseudo /**< data */
262 )
263 {
264  SCIP_Real* RESTRICT ecost;
265  SCIP_Real* RESTRICT ecostrev;
266  SCIP_Real* RESTRICT ecostreal;
267  int* RESTRICT incedge;
269  int edgecount = 0;
270
271  if( Is_term(g->term[vertex]) )
272  {
273  assert(graph_pc_isPcMw(g));
274  assert(!graph_pc_knotHasMaxPrize(g, vertex) );
275  assert(!delPseudoIsEdgeDeletionMode(delpseudo));
276
277  delpseudo->vertexprize = g->prize[vertex];
278  delpseudo->ancestorsnode = vertex;
279
280  delpseudo->degree = 3;
281
282  assert(delpseudo->vertexprize > 0.0);
283  assert(delpseudo->degree == graph_pc_realDegree(g, vertex, FALSE));
284  }
285  else
286  {
287  delpseudo->vertexprize = 0.0;
288  delpseudo->ancestorsnode = -1;
290
291  if( g->pcancestors && g->pcancestors[vertex] )
292  {
293  assert(graph_pc_isPcMw(g));
294  assert(SCIPisZero(scip, g->prize[vertex]));
295
296  delpseudo->ancestorsnode = vertex;
297  }
298  }
299
305
306  /* save the state of all incident edges */
307  for( int e = g->outbeg[vertex]; e != EAT_LAST; e = g->oeat[e] )
308  {
309  const int e_rev = flipedge(e);
310  assert(e >= 0);
311
312  incedge[edgecount] = e;
313  ecostreal[edgecount] = g->cost[e];
314  ecost[edgecount] = edgecosts[e];
315  ecostrev[edgecount] = edgecosts[e_rev];
317
319  }
320
321  assert(edgecount == delpseudo->degree);
322
323  delpseudo->ecost = ecost;
324  delpseudo->ecostrev = ecostrev;
325  delpseudo->ecostreal = ecostreal;
326  delpseudo->incedge = incedge;
330  delpseudo->neigbedge = NULL;
331
332  return SCIP_OKAY;
333 }
334
335
336 /** pseudo-eliminates vertex */
337 static
339  SCIP* scip, /**< SCIP data */
340  int vertex, /**< the vertex */
341  GRAPH* g, /**< graph */
342  REDCOST* redcostdata, /**< reduced cost data for adaptation or NULL */
343  DELPSEUDO* delpseudo /**< data */
344 )
345 {
347  const SCIP_Real* ecostreal = delpseudo->ecostreal;
350  const int* incedge = delpseudo->incedge;
351  const int* neigbedge = delpseudo->neigbedge;
353  const int degree = delpseudo->degree;
354  const int nspareedges = degree; /* todo we might want to allow additional edges to be inserted */
355  int edgecount = 0;
356  int replacecount = 0;
357  int pseudoancestor = -1;
358
359  for( int i = 0; i < degree; i++ )
360  {
361  const int e = incedge[i];
362  SCIP_CALL( graph_singletonAncestors_init(scip, g, e, &(ancestors[i])) );
363  }
364
365  assert(EQ(delpseudo->vertexprize, 0.0) || graph_pc_isPc(g));
366
367  for( int i = 0; i < degree - 1; i++ )
368  {
369  for( int j = i + 1; j < degree; j++ )
370  {
371  const SCIP_Bool skipedge = (neigbedge[edgecount] == STP_DELPSEUDO_SKIPEDGE);
372
373  /* do we need to insert edge at all? */
374  if( !skipedge )
375  {
376  SCIP_Bool conflict;
377  int newijedge;
378  const SCIP_Real newijcost = ecostreal[i] + ecostreal[j] - delpseudo->vertexprize;
379  const int oldincedge = incedge[(replacecount == nspareedges) ? replacecount - 1 : replacecount];
380  const int oldijedge = neigbedge[edgecount];
381 #ifndef NDEBUG
382  const int oldinctail = g->tail[oldincedge];
384 #endif
385  assert(replacecount <= nspareedges);
386  assert(replacecount < nspareedges || neigbedge[edgecount] != STP_DELPSEUDO_NOEDGE);
387
389  delpseudo->ancestorsnode, &(ancestors[i]), &(ancestors[j]), &newijedge, &conflict) );
390
391  assert(!conflict);
392
393  /* has a new edge been inserted (or the existing one been updated)? */
394  if( newijedge >= 0 )
395  {
396
399
400  if( redcostdata)
401  {
402  const int redcost_nlevels = redcosts_getNlevels(redcostdata);
404
405  for( int level = 0; level < redcost_nlevels; level++ )
406  {
407  SCIP_Real* const redcosts = redcosts_getEdgeCosts(redcostdata, level);
408  const int offset = level * STP_DELPSEUDO_MAXGRAD;
409
412  }
413  // graph_edge_printInfo(g, newijedge);
415  }
416
417  if( pseudoancestor == -1 )
418  {
420  assert(pseudoancestor >= 0);
421  }
422
423  SCIP_CALL( graph_pseudoAncestors_addToEdge(scip, newijedge, pseudoancestor, g) );
424  }
425
426  /* does no original edge exist? */
427  if( oldijedge == STP_DELPSEUDO_NOEDGE )
428  {
429  replacecount++;
430  assert(newijedge >= 0);
432  }
433  else
434  {
435  assert(newijedge == oldijedge || newijedge == - 1);
436  assert(newijedge != oldincedge);
438  }
439  }
440
441  edgecount++;
442  assert(edgecount <= STP_DELPSEUDO_MAXNEDGES);
443  }
444  }
445
446  /* delete remaining edges */
447  graph_knot_del(scip, g, vertex, TRUE);
448
449  for( int i = 0; i < degree; i++ )
450  graph_singletonAncestors_freeMembers(scip, &(ancestors[i]));
451
452  return SCIP_OKAY;
453 }
454
455
456 /** gets replacement edges; helper function for pseudo-elimination */
457 static
459  SCIP* scip, /**< SCIP data */
460  const GRAPH* g, /**< graph */
461  const SCIP_Real* cutoffs, /**< cutoff values for each incident edge (or NULL) */
462  const SCIP_Real* cutoffsrev, /**< reverse edge cutoff values (or NULL if undirected or non-existent) */
463  DELPSEUDO* delpseudo, /**< data */
464  SCIP_Bool* success /**< enough replace edges available? */
465 )
466 {
467  int* hasharr;
468  int edgecount = 0;
469  int replacecount = 0;
470  const int degree = delpseudo->degree;
471  const int nspareedges = degree;
472  const int *incedge = delpseudo->incedge;
473  const SCIP_Real *ecost = delpseudo->ecost;
474  const SCIP_Real *ecostrev = delpseudo->ecostrev;
476  int* RESTRICT neigbedge = delpseudo->neigbedge;
477  const SCIP_Real vertexprize = delpseudo->vertexprize;
478
479  assert(scip && g && ecost && neigbedge);
480  assert(degree >= 0 && degree <= STP_DELPSEUDO_MAXGRAD);
481
482  *success = TRUE;
483
485
486  for( int i = 0; i < STP_DELPSEUDO_MAXNEDGES; i++ )
487  neigbedge[i] = STP_DELPSEUDO_NOEDGE;
488
489  for( int i = 0; i < degree - 1 && *success; i++ )
490  {
492  const int iedge = incedge[i];
493
495
496  for( int j = i + 1; j < degree; j++ )
497  {
498  SCIP_Bool skipedge = isCutoffEdge(scip, cutoffs, cutoffsrev, ecost, ecostrev, vertexprize, i, j, edgecount);
499
500  if( !skipedge )
501  {
502  const int jedge = incedge[j];
503  skipedge = graph_pseudoAncestors_edgeIsHashed(g->pseudoancestors, jedge, hasharr);
504  }
505
506  edgecount++;
507  assert(edgecount <= STP_DELPSEUDO_MAXNEDGES);
508
509  /* can edge be discarded? */
510  if( skipedge )
511  {
512  neigbedge[edgecount - 1] = STP_DELPSEUDO_SKIPEDGE;
513  }
514  else
515  {
516  int e;
517
518  /* check whether edge already exists */
519  for( e = g->outbeg[adjvertex]; e != EAT_LAST; e = g->oeat[e] )
520  {
522  {
523  assert(e >= 0);
524  neigbedge[edgecount - 1] = e;
525  break;
526  }
527  }
528
529  if( e != EAT_LAST )
530  continue;
531
532  /* not enough spare edges? */
533  if( ++replacecount > nspareedges )
534  {
535  *success = FALSE;
536  break;
537  }
538  }
539  } /* inner neighbor loop */
540
542  } /* outer neighbor loop */
543
544  SCIPfreeCleanBufferArray(scip, &hasharr);
545
546  return SCIP_OKAY;
547 }
548
549
550 /** checks whether replacement is possible */
551 static
553  SCIP* scip, /**< SCIP data */
554  const GRAPH* g, /**< graph */
555  const SCIP_Real* cutoffs, /**< cutoff values for each incident edge (or NULL) */
556  const SCIP_Real* cutoffsrev, /**< reverse edge cutoff values (or NULL if undirected or non-existent) */
557  DELPSEUDO* delpseudo, /**< data */
558  SCIP_Bool* success /**< enough replace edges available? */
559 )
560 {
561  int* hasharr;
562  int edgecount = 0;
563  int replacecount = 0;
564  const int degree = delpseudo->degree;
565  const int nspareedges = degree;
566  const int *incedge = delpseudo->incedge;
567  const SCIP_Real *ecost = delpseudo->ecost;
568  const SCIP_Real *ecostrev = delpseudo->ecostrev;
570
571  const SCIP_Real vertexprize = delpseudo->vertexprize;
572
573  assert(scip && g);
574  assert(incedge && ecost && ecostrev && adjvert);
575  assert(degree >= 0 && degree <= STP_DELPSEUDO_MAXGRAD);
576
577  *success = TRUE;
578
580
581  for( int i = 0; i < degree - 1 && *success; i++ )
582  {
584  const int iedge = incedge[i];
585
587
588  for( int j = i + 1; j < degree; j++ )
589  {
590  SCIP_Bool skipedge = isCutoffEdge(scip, cutoffs, cutoffsrev, ecost, ecostrev, vertexprize, i, j, edgecount);
591
592  if( !skipedge )
593  {
594  const int jedge = incedge[j];
595  skipedge = graph_pseudoAncestors_edgeIsHashed(g->pseudoancestors, jedge, hasharr);
596  }
597
598  edgecount++;
599  assert(edgecount <= STP_DELPSEUDO_MAXNEDGES);
600
601  /* can edge not be discarded? */
602  if( !skipedge )
603  {
604  int e;
605
606  /* check whether edge already exists */
607  for( e = g->outbeg[adjvertex]; e != EAT_LAST; e = g->oeat[e] )
608  {
610  {
611  assert(e >= 0);
612  break;
613  }
614  }
615
616  if( e != EAT_LAST )
617  continue;
618
619  /* not enough spare edges? */
620  if( ++replacecount > nspareedges )
621  {
622  *success = FALSE;
623  break;
624  }
625  }
626  } /* inner neighbor loop */
627
629  } /* outer neighbor loop */
630
631  SCIPfreeCleanBufferArray(scip, &hasharr);
632
633  return SCIP_OKAY;
634 }
635
636
637 /** initializes for edge elimination */
638 static
640  SCIP* scip, /**< SCIP data */
641  const SCIP_Real* edgecosts, /**< edge costs for cutoff */
642  const SCIP_Real* edgecosts_adapt, /**< edge costs that should be adapted */
643  GRAPH* g, /**< graph */
644  DELPSEUDO* delpseudo /**< data */
645 )
646 {
647  const int edge = delpseudo->edge;
649  assert(delPseudoIsEdgeDeletionMode(delpseudo));
650
651  /* would need to change for REDCOST */
652  assert(!edgecosts_adapt && "currently not supported!");
653
654  SCIP_CALL( delPseudoInit(scip, edgecosts, NULL, head, g, delpseudo) );
655
656  return SCIP_OKAY;
657 }
658
659
660 /** gets replacement edges for edge elimination; helper function for pseudo-elimination */
661 static
663  SCIP* scip, /**< SCIP data */
664  const GRAPH* g, /**< graph */
665  const SCIP_Real* cutoffs, /**< cutoff values for each incident edge (or NULL) */
666  const SCIP_Real* cutoffsrev, /**< reverse edge cutoff values (or NULL if undirected or non-existent) */
667  DELPSEUDO* delpseudo, /**< data */
668  SCIP_Bool* success /**< enough replace edges available? */
669 )
670 {
671  int* hasharr;
672  int replacecount = 0;
673  const int degree = delpseudo->degree;
674  const int *incedge = delpseudo->incedge;
675  const SCIP_Real *ecost = delpseudo->ecost;
676  const SCIP_Real *ecostrev = delpseudo->ecostrev;
678  int* RESTRICT neigbedge = delpseudo->neigbedge;
679  const SCIP_Real vertexprize = delpseudo->vertexprize;
680  const int edge_pos = delPseudoGetEdgePosition(delpseudo);
681  const int edge = delpseudo->edge;
682  const int tail = g->tail[edge];
683
684  assert(scip && g && ecost && neigbedge);
685  assert(degree >= 0 && degree <= STP_DELPSEUDO_MAXGRAD);
686  assert(delPseudoIsEdgeDeletionMode(delpseudo));
687  assert(EQ(g->cost[edge], ecostrev[edge_pos]));
688  assert(EQ(g->cost[flipedge(edge)], ecost[edge_pos]));
689
690  *success = TRUE;
691
694
695  for( int i = 0; i < degree; i++ )
696  neigbedge[i] = STP_DELPSEUDO_NOEDGE;
697
698  for( int i = 0; i < degree; i++ )
699  {
700  if( i != edge_pos )
701  {
703  const int iedge = incedge[i];
704  SCIP_Bool skipedge = isCutoffEdge(scip, cutoffs, cutoffsrev, ecost, ecostrev, vertexprize, i, edge_pos, i);
705
706  SCIPdebugMessage("in (degree=%d): %d->%d cutoff=%f \n", degree, tail, adjvertex, cutoffs[i]);
707
708  assert((iedge / 2) != (edge / 2));
709
710  if( !skipedge )
711  skipedge = graph_pseudoAncestors_edgeIsHashed(g->pseudoancestors, iedge, hasharr);
712
713  if( skipedge )
714  {
715  SCIPdebugMessage("skip edge %d->%d \n", tail, g->head[iedge]);
716  neigbedge[i] = STP_DELPSEUDO_SKIPEDGE;
717  }
718  else
719  {
720  int e;
721
722  /* check whether edge already exists */
723  for( e = g->outbeg[adjvertex]; e != EAT_LAST; e = g->oeat[e] )
724  {
725  if( g->head[e] == tail )
726  {
727  assert(e >= 0);
728  neigbedge[i] = e;
729  SCIPdebugMessage("edge exist: %d->%d \n", g->tail[e], g->head[e]);
730  break;
731  }
732  }
733
734  /* edge does not exist? */
735  if( e == EAT_LAST )
736  {
737  /* more than one edge to be reinserted? */
738  if( ++replacecount > 1 )
739  {
740  *success = FALSE;
741  break;
742  }
743  }
744  }
745  }
746  else
747  {
748  assert(EQ(cutoffs[i], -1.0));
749  }
750  } /* neighbor loop */
751
752
754  SCIPfreeCleanBufferArray(scip, &hasharr);
755
756  return SCIP_OKAY;
757 }
758
759
760 /** pseudo-eliminates edge */
761 static
763  SCIP* scip, /**< SCIP data */
764  GRAPH* g, /**< graph */
766  DELPSEUDO* delpseudo /**< data */
767 )
768 {
770  const SCIP_Real* ecostreal = delpseudo->ecostreal;
773  const int* incedge = delpseudo->incedge;
774  const int* neigbedge = delpseudo->neigbedge;
776  const int degree = delpseudo->degree;
777  const int edge_pos = delPseudoGetEdgePosition(delpseudo);
778  const int edge = delpseudo->edge;
779  const int tail = g->tail[edge];
780  int replacecount = 0;
781 #ifndef NDEBUG
783 #endif
784
785  for( int i = 0; i < degree; i++ )
786  {
787  const int e = incedge[i];
788  SCIP_CALL( graph_singletonAncestors_init(scip, g, e, &(ancestors[i])) );
789  }
790
791  assert(EQ(delpseudo->vertexprize, 0.0));
792
793  for( int i = 0; i < degree; i++ )
794  {
795  if( i != edge_pos )
796  {
797  const SCIP_Bool skipedge = (neigbedge[i] == STP_DELPSEUDO_SKIPEDGE);
798
799  if( !skipedge )
800  {
801  SCIP_Bool conflict;
802  int newijedge;
803  const SCIP_Real newijcost = ecostreal[i] + ecostreal[edge_pos] - delpseudo->vertexprize;
804  const int oldincedge = (replacecount == 0)? flipedge(edge) : -1;
805  const int oldAdjToTailEdge = neigbedge[i];
806
807  assert(replacecount <= 1);
808  assert(replacecount == 0 || oldAdjToTailEdge != STP_DELPSEUDO_NOEDGE);
810
811  SCIP_CALL( graph_edge_reinsert(scip, g, oldincedge, adjvert[i], tail, newijcost,
812  delpseudo->ancestorsnode, &(ancestors[i]), &(ancestors[edge_pos]), &newijedge, &conflict) );
813
814  assert(!conflict);
815
816  /* has a new edge been inserted (or the existing one been updated)? */
817  if( newijedge >= 0 )
818  {
820
822  {
826  }
827
828 #ifdef SCIP_DEBUG
829  SCIPdebugMessage("pseudo-edge-elimination reinserted edge: ");
830  graph_edge_printInfo(g, newijedge);
831 #endif
832
834  }
835
836  /* does no original edge exist? */
837  if( oldAdjToTailEdge == STP_DELPSEUDO_NOEDGE )
838  {
839  replacecount++;
840  assert(newijedge >= 0);
841  }
842  else
843  {
844  assert(newijedge == oldAdjToTailEdge || newijedge == -1);
845  assert(newijedge != oldincedge || newijedge == -1);
846  }
847  }
848  }
849  }
850
851  for( int i = 0; i < degree; i++ )
852  graph_singletonAncestors_freeMembers(scip, &(ancestors[i]));
853
854  if( replacecount == 0 )
855  {
857 #ifdef SCIP_DEBUG
858  SCIPdebugMessage("pseudo-edge-elimination delete edge: ");
859  graph_edge_printInfo(g, edge);
860 #endif
861  graph_edge_del(scip, g, edge, TRUE);
862  }
863  else
864  {
866  }
867
868  return SCIP_OKAY;
869 }
870
871
872 /** frees data */
873 static
875  SCIP* scip, /**< SCIP data */
876  DELPSEUDO* delpseudo /**< data */
877 )
878 {
885
887  {
891  }
892 }
893
894
895 /** frees data from check */
896 static
898  SCIP* scip, /**< SCIP data */
899  DELPSEUDO* delpseudo /**< data */
900 )
901 {
907
909 }
910
911
912 /** does the path replacement */
913 static inline
915  SCIP* scip, /**< SCIP data structure */
916  GRAPH* g, /**< the graph */
917  int edge1, /**< first edge */
918  int edge2 /**< second edge */
919  )
920 {
921  int pseudoancestor;
922
923  assert(edge1 / 2 != edge2 / 2);
924  assert(graph_edge_isInRange(g, edge1));
925  assert(graph_edge_isInRange(g, edge2));
926
928  SCIP_CALL( graph_pseudoAncestors_addToEdge(scip, edge1, pseudoancestor, g) );
929  SCIP_CALL( graph_pseudoAncestors_addToEdge(scip, edge2, pseudoancestor, g) );
930
931  return SCIP_OKAY;
932 }
933
934 /** does the path replacement */
935 static
937  SCIP* scip, /**< SCIP data structure */
938  GRAPH* g, /**< the graph */
939  int edge, /**< the edge to be replaced, mind the orientation! */
940  int edge_pathtail, /**< tail edge of path */
943  )
944 {
945  const int old_tail = g->tail[edge];
949  const SCIP_Real path_cost = g->cost[edge] + g->cost[edge_pathtail] + g->cost[edge_pathhead];
950  const int path_tail = g->tail[edge_pathtail];
952  const int newedge = graph_edge_redirect(scip, g, edge, path_tail, path_head, path_cost, FALSE, TRUE);
953
954  /* is there a new edge? */
955  if( newedge >= 0 )
956  {
957  SCIP_Bool conflict = FALSE;
958
959 #ifdef SCIP_DEBUG
960  printf("have path replace edge: \n");
961  graph_edge_printInfo(g, newedge);
962 #endif
963
966
967  if( !g->ancestors[newedge] || !g->ancestors[flipedge(newedge)] )
968  {
969  const int edge_even = Edge_even(newedge);
970  assert(graph_typeIsUndirected(g));
971  assert(edge_even == flipedge(newedge) || edge_even == edge);
972
973  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[edge_even]), graph_edge_getAncestors(g, edge_pathtail), NULL) );
974  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[edge_even]), graph_edge_getAncestors(g, edge_pathhead), NULL) );
975  }
976  else
977  {
978  assert(!graph_typeIsUndirected(g));
979  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[newedge]), g->ancestors[edge_pathtail], NULL) );
980  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[newedge]), g->ancestors[edge_pathhead], NULL) );
981  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[flipedge(newedge)]), g->ancestors[flipedge(edge_pathtail)], NULL) );
982  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[flipedge(newedge)]), g->ancestors[flipedge(edge_pathhead)], NULL) );
983  }
984
985  SCIP_CALL( graph_pseudoAncestors_appendCopyEdge(scip, newedge, edge_pathtail, FALSE, g, &conflict) );
986  assert(!conflict);
987
988  SCIP_CALL( graph_pseudoAncestors_appendCopyEdge(scip, newedge, edge_pathhead, FALSE, g, &conflict) );
989  assert(!conflict);
990
991  /* create new ancestor relations */
992  for( int e = g->outbeg[old_tail]; e != EAT_LAST; e = g->oeat[e] )
993  {
994  SCIP_CALL( delPseudoPathCreatePseudoAncestorTuple(scip, g, e, newedge) );
995  }
996
997  for( int e = g->outbeg[old_head]; e != EAT_LAST; e = g->oeat[e] )
998  {
999  SCIP_CALL( delPseudoPathCreatePseudoAncestorTuple(scip, g, e, newedge) );
1000  }
1001  }
1002
1003  return SCIP_OKAY;
1004 }
1005
1006
1007
1008 /*
1009  * Interface methods
1010  */
1011
1012
1013
1014 /** pseudo delete node, i.e. reconnect neighbors; maximum degree of STP_DELPSEUDO_MAXGRAD! */
1016  SCIP* scip, /**< SCIP data structure */
1017  GRAPH* g, /**< the graph */
1018  const SCIP_Real* cutoffcosts, /**< edge costs for cutoff */
1019  const SCIP_Real* cutoffs, /**< cutoff values for each incident edge (or NULL) */
1020  const SCIP_Real* cutoffsrev, /**< reverse edge cutoff values (or NULL if undirected or non-existent) */
1021  int vertex, /**< the vertex */
1022  REDCOST* redcostdata, /**< reduced cost data for adaptation or NULL */
1023  SCIP_Bool* success /**< has node been pseudo-eliminated? */
1024  )
1025 {
1026  DELPSEUDO delpseudo = { NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, -1.0, -1, -1, UNKNOWN};
1027
1028  assert(scip && success && g);
1029  assert(vertex >= 0 && vertex < g->knots);
1031  assert(!delPseudoIsEdgeDeletionMode(&delpseudo));
1032
1033 #ifndef NDEBUG
1034  {
1035  int sum = 0;
1036  for( int i = 1; i < STP_DELPSEUDO_MAXGRAD; i++ )
1037  sum += i;
1038  assert(sum == STP_DELPSEUDO_MAXNEDGES);
1039  }
1040 #endif
1041
1042  *success = TRUE;
1043
1044  if( g->grad[vertex] <= 1 )
1045  return SCIP_OKAY;
1046
1047  SCIP_CALL( delPseudoInit(scip, cutoffcosts, redcostdata, vertex, g, &delpseudo) );
1048  SCIP_CALL( delPseudoGetReplaceEdges(scip, g, cutoffs, cutoffsrev, &delpseudo, success) );
1049
1050  /* enough spare edges? */
1051  if( (*success) )
1052  {
1053  SCIP_CALL( delPseudoDeleteVertex(scip, vertex, g, redcostdata, &delpseudo) );
1054  }
1055
1056  delPseudoFreeData(scip, &delpseudo);
1057
1058  return SCIP_OKAY;
1059 }
1060
1061
1062 /** checks whether pseudo-deletion is possible; maximum degree of STP_DELPSEUDO_MAXGRAD! */
1064  SCIP* scip, /**< SCIP data structure */
1065  const GRAPH* g, /**< the graph */
1066  const SCIP_Real* cutoffcosts, /**< edge costs for cutoff */
1067  const SCIP_Real* cutoffs, /**< cutoff values for each incident edge (or NULL) */
1068  const SCIP_Real* cutoffsrev, /**< reverse edge cutoff values (or NULL if undirected or non-existent) */
1069  int vertex, /**< the vertex */
1070  SCIP_Bool* isPossible /**< can vertex pseudo-eliminated? */
1071  )
1072 {
1073  DELPSEUDO delpseudo = { NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, -1.0, -1, -1, UNKNOWN};
1074
1075  assert(scip && isPossible && g);
1076  assert(vertex >= 0 && vertex < g->knots);
1078  assert(!delPseudoIsEdgeDeletionMode(&delpseudo));
1079
1080  *isPossible = TRUE;
1081
1082  if( g->grad[vertex] <= 3 )
1083  return SCIP_OKAY;
1084
1085  SCIP_CALL( delPseudoInitForCheck(scip, g, cutoffcosts, vertex, &delpseudo) );
1086  SCIP_CALL( delPseudoCheckReplacement(scip, g, cutoffs, cutoffsrev, &delpseudo, isPossible) );
1087
1088  delPseudoFreeDataForCheck(scip, &delpseudo);
1089
1090  return SCIP_OKAY;
1091 }
1092
1093
1094
1095 /** Pseudo deletes edge, i.e. reconnects tail of edge with neighbors of head; maximum degree of STP_DELPSEUDO_MAXGRAD!
1096  * The orientation of the edge is important! */
1098  SCIP* scip, /**< SCIP data structure */
1099  GRAPH* g, /**< the graph */
1100  const SCIP_Real* cutoffcosts, /**< edge costs for cutoff */
1101  const SCIP_Real* cutoffs, /**< cutoff values for each incident edge (or NULL) */
1102  const SCIP_Real* cutoffsrev, /**< reverse edge cutoff values (or NULL if undirected or non-existent) */
1103  int edge, /**< the edge, mind the orientation! */
1105  SCIP_Bool* success /**< has node been pseudo-eliminated? */
1106  )
1107 {
1108  DELPSEUDO delpseudo = { NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, -1.0, -1, -1, edge };
1109
1110  assert(scip && success && g);
1111  assert(graph_edge_isInRange(g, edge));
1114  assert(delPseudoIsEdgeDeletionMode(&delpseudo));
1115
1116  *success = TRUE;
1117
1118  SCIP_CALL( delPseudoEdgeInit(scip, cutoffcosts, edgecosts_adapt, g, &delpseudo) );
1119  SCIP_CALL( delPseudoEdgeGetReplaceEdges(scip, g, cutoffs, cutoffsrev, &delpseudo, success) );
1120
1121  /* enough spare edges? */
1122  if( (*success) )
1123  {
1124  SCIP_CALL( delPseudoEdgeDeleteEdge(scip, g, edgecosts_adapt, &delpseudo) );
1125  }
1126
1127  delPseudoFreeData(scip, &delpseudo);
1128
1129  return SCIP_OKAY;
1130 }
1131
1132
1133 /** Path replacement of edge; path is given by three oriented edges:
1134  * edge_pathtail -> edge -> edge_pathhead.
1135  * Middle edges is replaced. */
1137  SCIP* scip, /**< SCIP data structure */
1138  GRAPH* g, /**< the graph */
1139  int edge, /**< the edge to be replaced, mind the orientation! */
1140  int edge_pathtail, /**< tail edge of path */
1143  )
1144 {
1145  assert(scip && g);
1146  assert(graph_edge_isInRange(g, edge));
1147  assert(graph_edge_isInRange(g, edge_pathtail));
1151
1153
1154  return SCIP_OKAY;
1155 }
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
SCIP_RETCODE graph_singletonAncestors_init(SCIP *, const GRAPH *, int, SINGLETONANS *)
void graph_pseudoAncestors_unhashEdge(const PSEUDOANS *, int, int *)
Definition: graphdefs.h:79
int graph_pc_realDegree(const GRAPH *, int, SCIP_Bool)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
Definition: graphdefs.h:224
void graph_edge_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_edge.c:368
static SCIP_RETCODE delPseudoEdgeDeleteEdge(SCIP *scip, GRAPH *g, SCIP_Real *edgecosts_adapt, DELPSEUDO *delpseudo)
#define Is_term(a)
Definition: graphdefs.h:102
static SCIP_RETCODE delPseudoPathCreatePseudoAncestorTuple(SCIP *scip, GRAPH *g, int edge1, int edge2)
int redcosts_getNlevels(const REDCOST *redcostdata)
Definition: redcosts.c:369
#define STP_DELPSEUDO_MAXNEDGES
Definition: graphdefs.h:80
#define STP_DELPSEUDO_NOEDGE
static void delPseudoFreeData(SCIP *scip, DELPSEUDO *delpseudo)
int graph_pseudoAncestorsGetHashArraySize(const PSEUDOANS *)
static SCIP_RETCODE delPseudoEdgeInit(SCIP *scip, const SCIP_Real *edgecosts, const SCIP_Real *edgecosts_adapt, GRAPH *g, DELPSEUDO *delpseudo)
#define FALSE
Definition: def.h:87
struct pseudo_deletion DELPSEUDO
SCIP_Real * ecostrev
SCIP_RETCODE graph_edge_delPseudoPath(SCIP *scip, GRAPH *g, int edge, int edge_pathtail, int edge_pathhead, SCIP_Real *edgecosts_adapt)
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
int graph_edge_redirect(SCIP *, GRAPH *, int, int, int, SCIP_Real, SCIP_Bool, SCIP_Bool)
Definition: graph_edge.c:103
static SCIP_RETCODE delPseudoCheckReplacement(SCIP *scip, const GRAPH *g, const SCIP_Real *cutoffs, const SCIP_Real *cutoffsrev, DELPSEUDO *delpseudo, SCIP_Bool *success)
static void delPseudoFreeDataForCheck(SCIP *scip, DELPSEUDO *delpseudo)
#define EAT_LAST
Definition: graphdefs.h:58
#define SCIPdebugMessage
Definition: pub_message.h:87
void graph_pseudoAncestors_hashEdge(const PSEUDOANS *, int, int *)
static SCIP_RETCODE delPseudoPath(SCIP *scip, GRAPH *g, int edge, int edge_pathtail, int edge_pathhead, SCIP_Real *edgecosts_adapt)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_Bool graph_pc_knotHasMaxPrize(const GRAPH *, int)
SCIP_RETCODE graph_edge_reinsert(SCIP *, GRAPH *, int, int, int, SCIP_Real, int, SINGLETONANS *, SINGLETONANS *, int *, SCIP_Bool *)
Definition: graph_edge.c:200
static SCIP_RETCODE delPseudoGetReplaceEdges(SCIP *scip, const GRAPH *g, const SCIP_Real *cutoffs, const SCIP_Real *cutoffsrev, DELPSEUDO *delpseudo, SCIP_Bool *success)
SCIP_Real * redcosts_getEdgeCosts(const REDCOST *redcostdata, int level)
Definition: redcosts.c:187
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:133
int *RESTRICT oeat
Definition: graphdefs.h:231
SCIP_RETCODE SCIPintListNodeAppendCopy(SCIP *scip, IDX **node1, IDX *node2, SCIP_Bool *conflict)
Definition: misc_stp.c:197
IDX ** ancestors
Definition: graphdefs.h:234
SCIP_RETCODE graph_knot_delPseudoCheckIfPossible(SCIP *scip, const GRAPH *g, const SCIP_Real *cutoffcosts, const SCIP_Real *cutoffs, const SCIP_Real *cutoffsrev, int vertex, SCIP_Bool *isPossible)
PSEUDOANS * pseudoancestors
Definition: graphdefs.h:236
SCIP_Real vertexprize
SCIP_Real * prize
Definition: graphdefs.h:210
SCIP_Real * ecostreal
Definition: graphdefs.h:201
void graph_pc_termToNonTerm(SCIP *, GRAPH *, int)
SCIP_RETCODE graph_pseudoAncestors_addToEdge(SCIP *, int, int, GRAPH *)
#define NULL
Definition: lpi_spx1.cpp:155
#define EQ(a, b)
Definition: portab.h:79
static SCIP_RETCODE delPseudoInitForCheck(SCIP *scip, const GRAPH *g, const SCIP_Real *edgecosts, int vertex, DELPSEUDO *delpseudo)
void graph_knot_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_node.c:111
#define SCIP_CALL(x)
Definition: def.h:384
IDX ** pcancestors
Definition: graphdefs.h:235
SCIP_RETCODE graph_knot_delPseudo(SCIP *scip, GRAPH *g, const SCIP_Real *cutoffcosts, const SCIP_Real *cutoffs, const SCIP_Real *cutoffsrev, int vertex, REDCOST *redcostdata, SCIP_Bool *success)
static SCIP_Bool delPseudoIsEdgeDeletionMode(const DELPSEUDO *delpseudo)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define SCIP_Bool
Definition: def.h:84
static int delPseudoGetEdgePosition(const DELPSEUDO *delpseudo)
static SCIP_RETCODE delPseudoInit(SCIP *scip, const SCIP_Real *edgecosts, const REDCOST *redcostdata, int vertex, GRAPH *g, DELPSEUDO *delpseudo)
int *RESTRICT tail
Definition: graphdefs.h:223
SCIP_RETCODE graph_pseudoAncestors_appendCopyEdge(SCIP *, int, int, SCIP_Bool, GRAPH *, SCIP_Bool *)
#define flipedge(edge)
Definition: graphdefs.h:84
void graph_singletonAncestors_freeMembers(SCIP *, SINGLETONANS *)
int *RESTRICT term
Definition: graphdefs.h:196
void graph_edge_printInfo(const GRAPH *, int)
Definition: graph_stats.c:133
SCIP_Bool graph_pc_isPc(const GRAPH *)
Portable definitions.
SCIP_Bool graph_typeIsUndirected(const GRAPH *)
Definition: graph_stats.c:69
static SCIP_Bool isCutoffEdge(SCIP *scip, const SCIP_Real *cutoffs, const SCIP_Real *cutoffsrev, const SCIP_Real *ecost, const SCIP_Real *ecostrev, SCIP_Real prize, int edgeidx1, int edgeidx2, int cutoffidx)
SCIP_RETCODE graph_edge_delPseudo(SCIP *scip, GRAPH *g, const SCIP_Real *cutoffcosts, const SCIP_Real *cutoffs, const SCIP_Real *cutoffsrev, int edge, SCIP_Real *edgecosts_adapt, SCIP_Bool *success)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real * ecost
SCIP_Real * cost
Definition: graphdefs.h:221
SCIP_Bool graph_edge_isInRange(const GRAPH *, int)
Definition: graph_stats.c:110
static SCIP_RETCODE delPseudoDeleteVertex(SCIP *scip, int vertex, GRAPH *g, REDCOST *redcostdata, DELPSEUDO *delpseudo)
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
#define SCIP_Real
Definition: def.h:177
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:137
int *RESTRICT outbeg
Definition: graphdefs.h:204