Scippy

SCIP

Solving Constraint Integer Programs

solstp.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file solstp.c
17  * @brief includes methods working on solutions (i.e. trees) to Steiner tree problems
18  * @author Daniel Rehfeldt
19  *
20  * Methods for manipulating solutions (i.e. trees) to Steiner tree problems, such as pruning.
21  * Also includes methods for obtaining information about solutions.
22  *
23  * A list of all interface methods can be found in solstp.h
24  *
25  */
26 
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
28 
29 /*lint -esym(766,stdlib.h) -esym(766,malloc.h) */
30 /*lint -esym(766,string.h) */
31 //#define SCIP_DEBUG
32 
33 #include "probdata_stp.h"
34 #include "portab.h"
35 #include "solstp.h"
36 #include "mst.h"
37 #include "shortestpath.h"
38 
39 
40 
41 /** changes solution according to given root */
42 static
44  SCIP* scip, /**< SCIP data structure */
45  const GRAPH* g, /**< the graph */
46  int* result, /**< solution array (CONNECT/UNKNOWN) */
47  int newroot, /**< the new root */
48  SCIP_Bool* isInfeasible /**< infeasible? */
49  )
50 {
51  int* queue;
52  int* gmark;
53  int size;
54  const int nnodes = graph_get_nNodes(g);
55  const SCIP_Bool isPcMw = graph_pc_isPcMw(g);
56 
57  assert(newroot >= 0 && newroot < nnodes);
58  assert(Is_term(g->term[newroot]));
59 
60  *isInfeasible = FALSE;
61 
62  if( g->grad[newroot] == 0 )
63  {
64  if( g->terms > 1 )
65  {
66  *isInfeasible = TRUE;
67  }
68  return SCIP_OKAY;
69  }
70 
71  SCIP_CALL( SCIPallocBufferArray(scip, &gmark, nnodes) );
72  SCIP_CALL( SCIPallocBufferArray(scip, &queue, nnodes) );
73 
74  for( int k = 0; k < nnodes; k++ )
75  gmark[k] = FALSE;
76 
77  gmark[newroot] = TRUE;
78  size = 0;
79  queue[size++] = newroot;
80 
81  /* BFS loop */
82  while( size )
83  {
84  const int node = queue[--size];
85 
86  /* traverse outgoing arcs */
87  for( int a = g->outbeg[node]; a != EAT_LAST; a = g->oeat[a] )
88  {
89  const int head = g->head[a];
90 
91  if( !gmark[head] && (result[a] == CONNECT || result[flipedge(a)] == CONNECT ) )
92  {
93  if( result[flipedge(a)] == CONNECT )
94  {
95  result[a] = CONNECT;
96  result[flipedge(a)] = UNKNOWN;
97  }
98  gmark[head] = TRUE;
99  queue[size++] = head;
100  }
101  }
102  }
103 
104  /* adjust solution */
105  for( int k = 0; k < nnodes; k++ )
106  {
107  assert(*isInfeasible == FALSE);
108 
109  if( !gmark[k] )
110  {
111  if( isPcMw )
112  {
113  for( int a = g->outbeg[k]; a != EAT_LAST; a = g->oeat[a] )
114  {
115  result[a] = UNKNOWN;
116  result[flipedge(a)] = UNKNOWN;
117  }
118  }
119 
120  /* not yet connected terminal? */
121  if( Is_term(g->term[k]) )
122  {
123  int a;
124 
125  if( !isPcMw )
126  {
127  *isInfeasible = TRUE;
128  break;
129  }
130 
131  if( graph_pc_knotIsFixedTerm(g, k) )
132  {
133  *isInfeasible = TRUE;
134  break;
135  }
136 
137  for( a = g->inpbeg[k]; a != EAT_LAST; a = g->ieat[a] )
138  {
139  const int node = g->tail[a];
140  if( gmark[node] && node != newroot )
141  {
142  result[a] = CONNECT;
143  break;
144  }
145  }
146  if( a == EAT_LAST )
147  {
148  for( a = g->inpbeg[k]; a != EAT_LAST; a = g->ieat[a] )
149  {
150  const int node = g->tail[a];
151  if( node == newroot )
152  {
153  result[a] = CONNECT;
154  break;
155  }
156  }
157  }
158  else
159  {
160  gmark[k] = TRUE;
161  }
162  }
163  }
164  }
165 
166 
167 #ifndef NDEBUG
168  if( *isInfeasible == FALSE )
169  {
170  GRAPH* g_hacky = (GRAPH*) g;
171  const int realroot = g->source;
172  g_hacky->source = newroot;
173  assert(solstp_isValid(scip, g_hacky, result));
174  g_hacky->source = realroot;
175 
176  for( int k = 0; k < nnodes; k++ )
177  {
178  if( !gmark[k] )
179  {
180  for( int a = g->outbeg[k]; a != EAT_LAST; a = g->oeat[a] )
181  {
182  assert(result[a] == UNKNOWN);
183  assert(result[flipedge(a)] == UNKNOWN);
184  }
185  }
186  }
187  }
188 #endif
189 
190  SCIPfreeBufferArray(scip, &queue);
191  SCIPfreeBufferArray(scip, &gmark);
192 
193  return SCIP_OKAY;
194 }
195 
196 
197 /** Deletes subtree from given node, marked by dfspos.
198  * NOTE: recursive method. */
199 static
201  const GRAPH* g, /**< graph structure */
202  int subtree_root, /**< root of the subtree */
203  int dfspos[], /**< array to mark DFS positions of nodes */
204  int result[], /**< ST edges */
205  STP_Bool connected[] /**< ST nodes */
206 )
207 {
208  const int dfspos_root = dfspos[subtree_root];
209 
210  assert(dfspos_root > 0);
211  assert(connected[subtree_root]);
212  assert(g->mark[subtree_root]);
213 
214  connected[subtree_root] = FALSE;
215  g->mark[subtree_root] = FALSE;
216 
217  SCIPdebugMessage("strong prune deletes tree vertex %d \n", subtree_root);
218 
219  for( int e = g->outbeg[subtree_root]; e != EAT_LAST; e = g->oeat[e] )
220  {
221  if( result[e] == CONNECT )
222  {
223  const int neighbor = g->head[e];
224 
225  assert(dfspos[neighbor] >= 0);
226  assert(!graph_pc_knotIsDummyTerm(g, neighbor));
227  assert(dfspos[neighbor] != dfspos_root);
228 
229  /* is neighbor a DFS child of the root? */
230  if( dfspos[neighbor] > dfspos_root)
231  {
232  result[e] = UNKNOWN;
233 #ifdef SCIP_DEBUG
234  SCIPdebugMessage("strong prune deletes tree edge ");
235  graph_edge_printInfo(g, e);
236 #endif
237  pcsubtreeDelete(g, neighbor, dfspos, result, connected);
238  }
239  }
240  }
241 }
242 
243 
244 /** Deletes subtree from given node, marked by dfspos.
245  * NOTE: recursive method. */
246 static
248  const CSR* csr_orgcosts, /**< CSR */
249  int subtree_root, /**< root of the subtree */
250  int* RESTRICT dfspos, /**< array to mark DFS positions of nodes */
251  int* RESTRICT result, /**< ST edges */
252  STP_Bool* RESTRICT connected /**< ST nodes */
253 )
254 {
255  const int dfspos_root = dfspos[subtree_root];
256  const int rootedges_start = csr_orgcosts->start[subtree_root];
257  const int rootedges_end = csr_orgcosts->start[subtree_root + 1];
258 
259  assert(dfspos_root > 0);
260  assert(connected[subtree_root]);
261 
262  connected[subtree_root] = FALSE;
263 
264  SCIPdebugMessage("strong prune deletes tree vertex %d \n", subtree_root);
265 
266  for( int e = rootedges_start; e != rootedges_end; e++ )
267  {
268  if( result[e] == CONNECT )
269  {
270  const int neighbor = csr_orgcosts->head[e];
271 
272  assert(dfspos[neighbor] >= 0);
273  assert(dfspos[neighbor] != dfspos_root);
274 
275  /* is neighbor a DFS child of the root? */
276  if( dfspos[neighbor] > dfspos_root)
277  {
278  result[e] = UNKNOWN;
279  pcsubtreeDelete_csr(csr_orgcosts, neighbor, dfspos, result, connected);
280  }
281  }
282  }
283 }
284 
285 
286 /** Prunes subtree from given node such that it becomes most profitable and returns the profit.
287  * NOTE: recursive method. */
288 static
290  const GRAPH* g, /**< graph structure */
291  const SCIP_Real* cost, /**< edge costs */
292  int subtree_root, /**< root of the subtree */
293  int* RESTRICT dfspos, /**< array to mark DFS positions of nodes */
294  int* RESTRICT result, /**< ST edges */
295  STP_Bool* RESTRICT connected, /**< ST nodes */
296  int* RESTRICT dfscount /**< counter */
297 )
298 {
299  SCIP_Real profit = g->prize[subtree_root];
300 
301  if( !graph_pc_isPc(g) )
302  {
303  assert(graph_pc_isMw(g));
304 
305  if( LT(profit, 0.0) )
306  profit = 0.0;
307  }
308 
309  assert(0 <= *dfscount && *dfscount < g->knots);
310 
311  dfspos[subtree_root] = ++(*dfscount);
312 
313  SCIPdebugMessage("strong-prune from root %d \n", subtree_root);
314 
315  for( int e = g->outbeg[subtree_root]; e >= 0; e = g->oeat[e] )
316  {
317  if( result[e] == CONNECT )
318  {
319  const int neighbor = g->head[e];
320 
321  assert(dfspos[neighbor] >= 0);
322  assert(!graph_pc_knotIsDummyTerm(g, neighbor));
323 
324  /* not visited yet? */
325  if( dfspos[neighbor] == 0 )
326  {
327  const SCIP_Real neighbor_profit = pcsubtreePruneForProfit(g, cost, neighbor, dfspos, result, connected, dfscount);
328  const SCIP_Real extension_profit = neighbor_profit - cost[e];
329 
330  if( LT(extension_profit, 0.0) )
331  {
332  result[e] = UNKNOWN;
333 #ifdef SCIP_DEBUG
334  SCIPdebugMessage("strong prune deletes tree edge ");
335  graph_edge_printInfo(g, e);
336 #endif
337  pcsubtreeDelete(g, neighbor, dfspos, result, connected);
338  }
339  else
340  {
341  profit += extension_profit;
342  }
343  }
344  }
345  }
346 
347  return profit;
348 }
349 
350 
351 
352 /** Prunes subtree from given node such that it becomes most profitable and returns the profit.
353  * NOTE: recursive method. */
354 static
356  const CSR* csr_orgcosts, /**< CSR */
357  const SCIP_Real* prize, /**< the prize */
358  SCIP_Bool isPc, /**< is PC? */
359  int subtree_root, /**< root of the subtree */
360  int* RESTRICT dfspos, /**< array to mark DFS positions of nodes */
361  int* RESTRICT result, /**< ST edges */
362  STP_Bool* RESTRICT connected, /**< ST nodes */
363  int* RESTRICT dfscount /**< counter */
364 )
365 {
366  const SCIP_Real* const orgcosts_csr = csr_orgcosts->cost;
367  const int rootedges_start = csr_orgcosts->start[subtree_root];
368  const int rootedges_end = csr_orgcosts->start[subtree_root + 1];
369  const int* const heads_csr = csr_orgcosts->head;
370  SCIP_Real profit = prize[subtree_root];
371 
372  if( !isPc )
373  {
374  /* NOTE: for MW any negative prize is already counted with the edge costs! */
375  if( LT(profit, 0.0) )
376  profit = 0.0;
377  }
378 
379  assert(0 <= *dfscount && *dfscount < csr_orgcosts->nnodes);
380  assert(rootedges_start <= rootedges_end);
381 
382  dfspos[subtree_root] = ++(*dfscount);
383 
384  SCIPdebugMessage("strong-prune from root %d \n", subtree_root);
385 
386  for( int e = rootedges_start; e != rootedges_end; e++ )
387  {
388  if( result[e] == CONNECT )
389  {
390  const int neighbor = heads_csr[e];
391 
392  assert(dfspos[neighbor] >= 0);
393 
394  /* not visited yet? */
395  if( dfspos[neighbor] == 0 )
396  {
397  const SCIP_Real neighbor_profit = pcsubtreePruneForProfit_csr(csr_orgcosts, prize, isPc, neighbor, dfspos,
398  result, connected, dfscount);
399  const SCIP_Real extension_profit = neighbor_profit - orgcosts_csr[e];
400 
401  if( LE(extension_profit, 0.0) )
402  {
403  result[e] = UNKNOWN;
404  pcsubtreeDelete_csr(csr_orgcosts, neighbor, dfspos, result, connected);
405  }
406  else
407  {
408  profit += extension_profit;
409  }
410  }
411  }
412  }
413 
414  return profit;
415 }
416 
417 
418 /** computes trivial solution and sets result edges */
419 static inline
421  const GRAPH* g, /**< graph structure */
422  const STP_Bool* connected, /**< ST nodes */
423  int* RESTRICT result /**< MST solution, which does not include artificial terminals */
424 )
425 {
426  const int root = g->source;
427  const int* const gOeat = g->oeat;
428  const int* const gHead = g->head;
429 
430 #ifndef NEDBUG
431  for( int i = 0; i < g->edges; i++ )
432  assert(UNKNOWN == result[i]);
433 #endif
434 
435  for( int a = g->outbeg[root]; a >= 0; a = gOeat[a] )
436  {
437  const int head = gHead[a];
438  if( graph_pc_knotIsDummyTerm(g, head) )
439  {
440  assert(!connected || connected[head]);
441  result[a] = CONNECT;
442  }
443  }
444 }
445 
446 
447 /** computes MST on marked graph and sets result edges */
448 static inline
450  SCIP* scip, /**< SCIP data structure */
451  const GRAPH* g, /**< graph structure */
452  const SCIP_Real* cost, /**< edge costs */
453  int root, /**< root of solution */
454  int* result /**< MST solution, which does not include artificial terminals */
455 )
456 {
457  PATH* mst;
458  const int nnodes = graph_get_nNodes(g);
459  const int* const gmark = g->mark;
460 
461  SCIP_CALL( SCIPallocBufferArray(scip, &mst, nnodes) );
462  graph_path_exec(scip, g, MST_MODE, root, cost, mst);
463 
464  for( int i = 0; i < nnodes; i++ )
465  {
466  if( gmark[i] && (mst[i].edge != UNKNOWN) )
467  {
468  assert(g->path_state[i] == CONNECT);
469  assert(g->head[mst[i].edge] == i);
470  assert(result[mst[i].edge] == -1);
471 
472  result[mst[i].edge] = CONNECT;
473  }
474  }
475 
476  SCIPfreeBufferArray(scip, &mst);
477 
478  return SCIP_OKAY;
479 }
480 
481 
482 /** mark nodes of the solution in the graph */
483 static inline
485  const STP_Bool* connected, /**< ST nodes */
486  const GRAPH* g /**< graph structure */
487  )
488 {
489  int* RESTRICT gmark = g->mark;
490  const int nnodes = graph_get_nNodes(g);
491  const SCIP_Bool rpcmw = graph_pc_isRootedPcMw(g);
492 
493  assert(g->extended);
494 
495  if( rpcmw )
496  {
497  for( int i = 0; i < nnodes; i++ )
498  {
499  if( connected[i] && !graph_pc_knotIsDummyTerm(g, i) )
500  gmark[i] = TRUE;
501  else
502  gmark[i] = FALSE;
503 
504  assert(gmark[i] || !graph_pc_knotIsFixedTerm(g, i));
505  }
506 
507  assert(gmark[g->source]);
508  }
509  else
510  {
511  const int* const gterm = g->term;
512 
513  for( int i = 0; i < nnodes; i++ )
514  {
515  if( connected[i] && !Is_term(gterm[i]) )
516  gmark[i] = TRUE;
517  else
518  gmark[i] = FALSE;
519  }
520  }
521 }
522 
523 
524 /** mark nodes of the solution in the graph */
525 static inline
527  const GRAPH* g, /**< graph structure */
528  STP_Bool* RESTRICT connected /**< ST nodes */
529  )
530 {
531  const int nnodes = graph_get_nNodes(g);
532  const SCIP_Bool rpcmw = graph_pc_isRootedPcMw(g);
533 
534  assert(g->extended);
535 
536  if( rpcmw )
537  {
538  const int* const gGrad = g->grad;
539 
540  for( int i = 0; i < nnodes; i++ )
541  {
542  if( gGrad[i] == 2 )
543  {
544  if( graph_pc_knotIsDummyTerm(g, i) )
545  connected[i] = FALSE;
546  }
547  else
548  {
549  assert(!graph_pc_knotIsDummyTerm(g, i));
550  }
551 
552  assert(connected[i] || !graph_pc_knotIsFixedTerm(g, i));
553  }
554 
555  assert(connected[g->source]);
556  }
557  else
558  {
559  const int* const gterm = g->term;
560 
561  for( int i = 0; i < nnodes; i++ )
562  {
563  if( Is_term(gterm[i]) )
564  connected[i] = FALSE;
565  }
566  }
567 }
568 
569 
570 /** prune a Steiner tree in such a way that all leaves are terminals */
571 static inline
573  const GRAPH* g, /**< graph structure */
574  int* result, /**< MST solution, which does not include artificial terminals */
575  STP_Bool* connected /**< ST nodes */
576  )
577 {
578  const int nnodes = graph_get_nNodes(g);
579  int count;
580 
581  SCIPdebugMessage("starting (simple) pruning \n");
582 
583  do
584  {
585  count = 0;
586 
587  for( int i = nnodes - 1; i >= 0; --i )
588  {
589  int j;
590  if( !g->mark[i] || g->path_state[i] != CONNECT || Is_term(g->term[i]) )
591  continue;
592 
593  for( j = g->outbeg[i]; j != EAT_LAST; j = g->oeat[j] )
594  if( result[j] == CONNECT )
595  break;
596 
597  if( j == EAT_LAST )
598  {
599  /* there has to be exactly one incoming edge
600  */
601  assert(!Is_term(g->term[i]) && !Is_pseudoTerm(g->term[i]));
602 
603  for( j = g->inpbeg[i]; j != EAT_LAST; j = g->ieat[j] )
604  {
605  if( result[j] == CONNECT )
606  {
607  SCIPdebugMessage("prune delete vertex %d \n", i);
608 #ifdef SCIP_DEBUG
609  SCIPdebugMessage("prune delete edge ");
610  graph_edge_printInfo(g, j);
611 #endif
612 
613  result[j] = UNKNOWN;
614  g->mark[i] = FALSE;
615  connected[i] = FALSE;
616  count++;
617  break;
618  }
619  }
620  assert(j != EAT_LAST);
621  }
622  }
623  }
624  while( count > 0 );
625 
626 #ifndef NDEBUG
627  /* make sure there is no unconnected vertex */
628  for( int i = 0; i < nnodes; i++ )
629  {
630  if( connected[i] && i != g->source )
631  {
632  int j;
633  for( j = g->inpbeg[i]; j != EAT_LAST; j = g->ieat[j] )
634  {
635  if( result[j] == CONNECT )
636  break;
637  }
638 
639  assert(j != EAT_LAST);
640  }
641  }
642 #endif
643 }
644 
645 
646 /** prunes the Steiner tree in such a way that all leaves are terminals */
647 static
649  const GRAPH* g, /**< graph structure */
650  const MST* mst, /**< the MST */
651  int* RESTRICT result, /**< ST edges (need to be set to UNKNOWN) */
652  STP_Bool* RESTRICT connected /**< ST nodes */
653  )
654 {
655  const CSR* const csr = mst->csr;
656  const int* const csr_start = csr->start;
657  const int nnodes = graph_get_nNodes(g);
658  int count;
659 
660  SCIPdebugMessage("starting (simple, CSR) pruning \n");
661 
662  do
663  {
664  count = 0;
665 
666  for( int i = 0; i < nnodes; i++ )
667  {
668  int outedge;
669 
670  if( !connected[i] || Is_term(g->term[i]) )
671  continue;
672 
673  for( outedge = csr_start[i]; outedge != csr_start[i + 1]; outedge++ )
674  {
675  if( result[outedge] == CONNECT )
676  break;
677  }
678 
679  /* no outgoing edge? */
680  if( outedge == csr_start[i + 1] )
681  {
682  /* there has to be exactly one incoming edge -> remove it */
683 
684  const int inedge = mst->nodes_predEdge[i];
685  assert(inedge != UNKNOWN);
686  assert(result[inedge] == CONNECT);
687 
688  SCIPdebugMessage("prune delete vertex %d \n", i);
689 
690  result[inedge] = UNKNOWN;
691  connected[i] = FALSE;
692  count++;
693  }
694  }
695  }
696  while( count > 0 );
697 }
698 
699 
700 /** computes MST on marked graph and sets result edges */
701 static inline
703  const GRAPH* g, /**< graph structure */
704  const STP_Bool* connected, /**< ST nodes */
705  int root, /**< root of solution */
706  MST* mst, /**< the MST */
707  int* RESTRICT result /**< MST solution, which does not include artificial terminals */
708 )
709 {
710  const int nnodes = graph_get_nNodes(g);
711  const int* predEdge;
712 
713  mst_computeOnMarked(g, connected, root, mst);
714  predEdge = mst->nodes_predEdge;
715 
716  for( int i = 0; i < nnodes; i++ )
717  {
718  if( connected[i] && (predEdge[i] != UNKNOWN) )
719  {
720  assert(mst->csr->head[predEdge[i]] == i);
721  assert(result[predEdge[i]] == UNKNOWN);
722 
723  result[predEdge[i]] = CONNECT;
724  }
725  }
726 }
727 
728 /** Finds optimal prize-collecting Steiner tree on given tree. */
729 static
731  SCIP* scip, /**< SCIP data structure */
732  const GRAPH* g, /**< graph structure */
733  const SCIP_Real* cost, /**< edge costs */
734  int solroot, /**< root of the solution */
735  int* result, /**< ST edges */
736  STP_Bool* connected /**< ST nodes */
737 )
738 {
739  int* dfspos;
740  const int nnodes = graph_get_nNodes(g);
741  int dfscount = 0;
742  SCIP_Real profit;
743 #ifndef NDEBUG
744  const int nsoledges = solstp_getNedges(g, result);
745 #endif
746 
747  assert(solroot >= 0);
748  assert(connected[solroot]);
749  assert(graph_pc_isPcMw(g));
750  assert(!graph_pc_knotIsDummyTerm(g, solroot));
751  assert(graph_pc_isMw(g) || graph_pc_costsEqualOrgCosts(scip, g, cost));
752  assert(g->extended);
753 
754  /* todo find best root? */
755 
756  SCIP_CALL( SCIPallocBufferArray(scip, &dfspos, nnodes) );
757 
758  BMSclearMemoryArray(dfspos, nnodes);
759 
760  /* compute the subtree */
761  profit = pcsubtreePruneForProfit(g, cost, solroot, dfspos, result, connected, &dfscount);
762 
763  assert(nsoledges + 1 == dfscount);
764 
765  if( LT(profit, 0.0) )
766  {
767  assert(!graph_pc_isRootedPcMw(g));
768  assert(!Is_anyTerm(g->term[solroot]));
769  assert(EQ(g->prize[solroot], 0.0));
770 
771  // todo can this ever happen?
772  // if so, better have a flag here, because we dont wannt set edges to dummies here...
773  return SCIP_ERROR;
774 // SCIPdebugMessage("Best subtree is negative! Take empty solution \n");
775 // pcsolGetTrivialEdges(g, connected, result);
776  }
777 
778  SCIPfreeBufferArray(scip, &dfspos);
779 
780  return SCIP_OKAY;
781 }
782 
783 
784 
785 /** Finds optimal prize-collecting Steiner tree on given tree. */
786 static
788  SCIP* scip, /**< SCIP data structure */
789  const GRAPH* g, /**< graph structure */
790  const CSR* csr_orgcosts, /**< CSR */
791  int solroot, /**< root of the solution */
792  int* result, /**< ST edges */
793  STP_Bool* connected /**< ST nodes */
794 )
795 {
796  int* dfspos;
797  SCIP_Real profit;
798  const int nnodes = graph_get_nNodes(g);
799  int dfscount = 0;
800 #ifndef NDEBUG
801  const int nsoledges = solstp_getNedgesBounded(g, result, graph_csr_getNedges(csr_orgcosts));
802 #endif
803  const SCIP_Bool isPc = graph_pc_isPc(g);
804 
805  assert(solroot >= 0);
806  assert(connected[solroot]);
807  assert(graph_pc_isPcMw(g));
808  assert(!graph_pc_knotIsDummyTerm(g, solroot));
809  assert(g->extended);
810  assert(nnodes == csr_orgcosts->nnodes);
811 
812 
813  SCIP_CALL( SCIPallocBufferArray(scip, &dfspos, nnodes) );
814 
815  BMSclearMemoryArray(dfspos, nnodes);
816 
817  /* compute the subtree */
818 
819  profit = pcsubtreePruneForProfit_csr(csr_orgcosts, g->prize, isPc, solroot, dfspos, result, connected, &dfscount);
820 
821  assert(nsoledges + 1 == dfscount);
822 
823  SCIPfreeBufferArray(scip, &dfspos);
824 
825  if( LT(profit, 0.0) )
826  {
827  return SCIP_ERROR;
828  }
829 
830  return SCIP_OKAY;
831 }
832 
833 
834 
835 /** prune a Steiner tree in such a way that all leaves are terminals */
836 static
838  SCIP* scip, /**< SCIP data structure */
839  const GRAPH* g, /**< graph structure */
840  const SCIP_Real* cost, /**< edge costs */
841  int* result, /**< ST edges, which need to be set to UNKNOWN */
842  STP_Bool* connected /**< ST nodes */
843  )
844 {
845  PATH* mst;
846  int count;
847  const int nnodes = graph_get_nNodes(g);
848 #ifndef NEDBUG
849  int nconnected = 0;
850 #endif
851 
852  assert(scip != NULL);
853  assert(cost != NULL);
854  assert(result != NULL);
855  assert(connected != NULL);
856 
857 #ifndef NEDBUG
858  for( int i = 0; i < g->edges; i++ )
859  assert(UNKNOWN == result[i]);
860 
861  for( int i = nnodes - 1; i >= 0; --i )
862  if( connected[i] )
863  nconnected++;
864 
865  assert(nconnected >= g->terms);
866  assert(g->source >= 0 && g->source < nnodes);
867 #endif
868 
869  SCIP_CALL( SCIPallocBufferArray(scip, &mst, nnodes) );
870 
871  /* compute the MST */
872  for( int i = nnodes - 1; i >= 0; --i )
873  g->mark[i] = connected[i];
874 
875  graph_path_exec(scip, g, MST_MODE, g->source, cost, mst);
876 
877  for( int i = nnodes - 1; i >= 0; --i )
878  {
879  if( connected[i] && (mst[i].edge != -1) )
880  {
881  assert(g->head[mst[i].edge] == i);
882  assert(result[mst[i].edge] == UNKNOWN);
883 
884  result[mst[i].edge] = 0;
885  }
886  }
887 
888  /* prune */
889  do
890  {
891  SCIPdebug(fputc('C', stdout));
892  SCIPdebug(fflush(stdout));
893 
894  count = 0;
895 
896  for( int i = nnodes - 1; i >= 0; --i )
897  {
898  int j;
899 
900  if( !g->mark[i] )
901  continue;
902 
903  if( g->term[i] == 0 )
904  continue;
905 
906  for( j = g->outbeg[i]; j != EAT_LAST; j = g->oeat[j] )
907  if( result[j] == 0 )
908  break;
909 
910  if( j == EAT_LAST )
911  {
912  /* there has to be exactly one incoming edge
913  */
914  for( j = g->inpbeg[i]; j != EAT_LAST; j = g->ieat[j] )
915  {
916  if( result[j] == 0 )
917  {
918  result[j] = -1;
919  g->mark[i] = FALSE;
920  connected[i] = FALSE;
921  count++;
922  break;
923  }
924  }
925  }
926  }
927  }
928  while( count > 0 );
929 
930  SCIPfreeBufferArray(scip, &mst);
931 
932  return SCIP_OKAY;
933 }
934 
935 
936 /** Prunes the Steiner tree in such a way that all leaves are terminals:
937  * 1. Builds MST
938  * 2. Removes non-terminal leaves repeatedly */
939 static
941  const GRAPH* g, /**< graph structure */
942  MST* mst, /**< the MST */
943  int* RESTRICT result, /**< ST edges (need to be set to UNKNOWN) */
944  STP_Bool* RESTRICT connected /**< ST nodes */
945  )
946 {
947  assert(g && mst && result && connected);
948 
949 #ifndef NDEBUG
950  {
951  const int nedges_csr = graph_csr_getNedges(mst->csr);
952  for( int i = 0; i < nedges_csr; i++ )
953  assert(UNKNOWN == result[i]);
954  }
955 #endif
956 
957  /* 1. build MST on solution nodes */
958  solGetMstEdges_csr(g, connected, g->source, mst, result);
959 
960  /* 2. prune MST */
961  stpsolPrune_csr(g, mst, result, connected);
962 
963  return SCIP_OKAY;
964 }
965 
966 
967 /* prune the (rooted) prize collecting Steiner tree in such a way that all leaves are terminals
968  * NOTE: graph is not really const, mark is changed! todo */
969 static
971  SCIP* scip, /**< SCIP data structure */
972  const GRAPH* g, /**< graph structure */
973  const SCIP_Real* cost, /**< edge costs */
974  int* result, /**< ST edges (need to be set to UNKNOWN) */
975  STP_Bool* connected /**< ST nodes */
976  )
977 {
978  const SCIP_Bool rpcmw = graph_pc_isRootedPcMw(g);
979  int solroot = g->source;
980 
981 #ifndef NDEBUG
982  int* result_dbg;
983  STP_Bool* connected_dbg;
984  const int nedges = graph_get_nEdges(g);
985  for( int i = 0; i < nedges; i++ )
986  assert(UNKNOWN == result[i]);
987 #endif
988 
989  assert(scip && cost && result && connected);
990  assert(g->extended);
991  assert(graph_pc_isPcMw(g));
992 
993  pcsolMarkGraphNodes(connected, g);
994 
995  if( !rpcmw )
996  {
997  solroot = solstp_pcGetSolRoot(scip, g, connected);
998 
999  /* trivial solution? */
1000  if( solroot == -1 )
1001  {
1002  printf("trivial solution in pruning \n");
1003 
1004  pcsolGetTrivialEdges(g, connected, result);
1005 
1006  return SCIP_OKAY;
1007  }
1008  }
1009 
1010  assert(0 <= solroot && solroot < g->knots);
1011  assert(g->mark[solroot]);
1012  SCIPdebugMessage("(non-artificial) solution root=%d \n", solroot);
1013 
1014  SCIP_CALL( pcsolGetMstEdges(scip, g, cost, solroot, result) );
1015 
1016 #ifndef NDEBUG
1017  for( int i = 0; i < g->knots; ++i )
1018  assert((g->path_state[i] == CONNECT) == g->mark[i]);
1019 
1020  SCIP_CALL( SCIPallocBufferArray(scip, &result_dbg, nedges) );
1021  SCIP_CALL( SCIPallocBufferArray(scip, &connected_dbg, g->knots) );
1022 
1023  BMScopyMemoryArray(result_dbg, result, nedges);
1024  BMScopyMemoryArray(connected_dbg, connected, g->knots);
1025 #endif
1026 
1027  SCIP_CALL( strongPruneSteinerTreePc(scip, g, cost, solroot, result, connected) );
1028 
1029  solstp_pcConnectDummies(g, solroot, result, connected);
1030 
1031  /* simple pruning */
1032  pcsolPrune(g, result, connected);
1033  assert(!stpsol_pruningIsPossible(g, result, connected));
1034 
1035 #ifndef NDEBUG
1036  solstp_pcConnectDummies(g, solroot, result_dbg, connected_dbg);
1037  pcsolPrune(g, result_dbg, connected_dbg);
1038 
1039  assert(LE(solstp_getObjBounded(g, result, 0.0, nedges), solstp_getObjBounded(g, result_dbg, 0.0, nedges)));
1040 
1041  SCIPfreeBufferArray(scip, &connected_dbg);
1042  SCIPfreeBufferArray(scip, &result_dbg);
1043 #endif
1044 
1045  assert(solstp_isValid(scip, g, result));
1046 
1047  return SCIP_OKAY;
1048 }
1049 
1050 
1051 
1052 /* prune the (rooted) prize collecting Steiner tree in such a way that all leaves are terminals
1053  * NOTE: graph is not really const, mark is changed! todo */
1054 static
1056  SCIP* scip, /**< SCIP data structure */
1057  const GRAPH* g, /**< graph structure */
1058  MST* mst, /**< the MST */
1059  int* RESTRICT result, /**< ST edges (need to be set to UNKNOWN) */
1060  STP_Bool* RESTRICT connected /**< ST nodes */
1061  )
1062 {
1063  const SCIP_Bool rpcmw = graph_pc_isRootedPcMw(g);
1064  int solroot = g->source;
1065 
1066 #ifndef NDEBUG
1067  {
1068  const int nedges_csr = graph_csr_getNedges(mst->csr);
1069  for( int i = 0; i < nedges_csr; i++ )
1070  assert(UNKNOWN == result[i]);
1071 
1072  assert(scip && result && connected);
1073  assert(g->extended);
1074  assert(graph_pc_isPcMw(g));
1075  }
1076 #endif
1077 
1078  pcsolMarkGraphNodes_csr(g, connected);
1079 
1080  if( !rpcmw )
1081  {
1082  solroot = solstp_pcGetSolRoot(scip, g, connected);
1083 
1084  /* trivial solution? */
1085  if( solroot == -1 )
1086  {
1087  printf("trivial solution in pruning \n");
1088  // pcsolGetTrivialEdges(g, connected, result); // does not work for CSR!
1089  return SCIP_ERROR;
1090  }
1091  }
1092 
1093  assert(0 <= solroot && solroot < g->knots);
1094  assert(connected[solroot]);
1095  SCIPdebugMessage("(non-artificial) solution root=%d \n", solroot);
1096 
1097  solGetMstEdges_csr(g, connected, solroot, mst, result);
1098 
1099  SCIP_CALL( strongPruneSteinerTreePc_csr(scip, g, mst->csr, solroot, result, connected) );
1100 
1101  return SCIP_OKAY;
1102 }
1103 
1104 
1105 
1106 
1107 /** mark endpoints of edges in given list */
1108 static inline
1110  const GRAPH* g, /**< graph data structure */
1111  STP_Bool* RESTRICT solnode, /**< solution nodes array (TRUE/FALSE) */
1112  IDX* listnode /**< edge list */
1113  )
1114 {
1115  IDX* curr;
1116 
1117  assert(g != NULL);
1118  assert(solnode != NULL);
1119 
1120  curr = listnode;
1121 
1122  while( curr != NULL )
1123  {
1124  const int i = curr->index;
1125 
1126  solnode[g->head[i]] = TRUE;
1127  solnode[g->tail[i]] = TRUE;
1128 
1129  curr = curr->parent;
1130  }
1131 }
1132 
1133 /*
1134  * Interface methods
1135  */
1136 
1137 
1138 /** Gets root of solution for unrooted PC/MW.
1139  * Returns -1 if the solution is empty. */
1141  SCIP* scip, /**< SCIP data structure */
1142  const GRAPH* g, /**< graph structure */
1143  const STP_Bool* connected /**< ST nodes */
1144  )
1145 {
1146  int proot = -1;
1147  const int nnodes = graph_get_nNodes(g);
1148 
1149  assert(g && connected);
1150  assert(graph_pc_isPcMw(g));
1151 
1152  if( graph_pc_isRootedPcMw(g) )
1153  {
1154  return g->source;
1155  }
1156 
1157  /* todo remove this hack, better ask for the SCIP stage */
1158  if( SCIPprobdataGetNTerms(scip) == g->terms && SCIPprobdataGetNNodes(scip) == nnodes )
1159  {
1160  int min = nnodes;
1161  const int* termsorder = SCIPprobdataGetPctermsorder(scip);
1162 
1163  for( int k = 0; k < nnodes; k++ )
1164  {
1165  if( termsorder[k] < min && connected[k] )
1166  {
1167  assert(Is_pseudoTerm(g->term[k]));
1168 
1169  min = termsorder[k];
1170  proot = k;
1171  }
1172  }
1173 
1174  assert(min >= 0);
1175  assert(proot == -1 || min < nnodes);
1176  }
1177  else
1178  {
1179  const int* const gOeat = g->oeat;
1180  const int* const gHead = g->head;
1181  const int* const gTerm = g->term;
1182  const int groot = g->source;
1183 
1184  for( int a = g->outbeg[groot]; a >= 0; a = gOeat[a] )
1185  {
1186  const int head = gHead[a];
1187  if( !Is_term(gTerm[head]) && connected[head] )
1188  {
1189  proot = head;
1190  break;
1191  }
1192  }
1193  }
1194 
1195  return proot;
1196 }
1197 
1198 
1199 /** connects dummy terminals to given (pre-) PC solution */
1201  const GRAPH* g, /**< graph structure */
1202  int solroot, /**< root of solution */
1203  int* RESTRICT result, /**< MST solution, which does not include artificial terminals */
1204  STP_Bool* RESTRICT connected /**< ST nodes */
1205  )
1206 {
1207  const int* const gTerm = g->term;
1208  const int nnodes = graph_get_nNodes(g);
1209  const SCIP_Bool rpcmw = graph_pc_isRootedPcMw(g);
1210  const int gRoot = g->source;
1211 
1212  assert(graph_pc_isPcMw(g));
1213 
1214  /* connect all terminals */
1215  for( int i = 0; i < nnodes; i++ )
1216  {
1217  if( Is_term(gTerm[i]) && i != gRoot )
1218  {
1219  const SCIP_Bool isFixedTerm = graph_pc_knotIsFixedTerm(g, i);
1220 
1221  assert(isFixedTerm || g->grad[i] == 2);
1222  assert(isFixedTerm || g->inpbeg[i] >= 0);
1223 
1224  if( isFixedTerm )
1225  {
1226  assert(rpcmw);
1227  assert(connected[i]);
1228  continue;
1229  }
1230  else
1231  {
1232  const int e1 = g->inpbeg[i];
1233  const int e2 = g->ieat[e1];
1234  const int k1 = g->tail[e1];
1235  const int k2 = g->tail[e2];
1236 
1237  connected[i] = TRUE;
1238 
1239  assert(graph_pc_knotIsDummyTerm(g, i));
1240  assert(g->ieat[e2] == EAT_LAST);
1241  assert(g->grad[i] == 2);
1242  assert(k1 == gRoot || k2 == gRoot);
1243 
1244  if( k1 != gRoot && connected[k1] )
1245  result[e1] = CONNECT;
1246  else if( k2 != gRoot && connected[k2] )
1247  result[e2] = CONNECT;
1248  else if( k1 == gRoot )
1249  result[e1] = CONNECT;
1250  else if( k2 == gRoot )
1251  result[e2] = CONNECT;
1252 
1253  /* xor: exactly one of e1 and e2 is used */
1254  assert((result[e1] != CONNECT) != (result[e2] != CONNECT));
1255  }
1256  }
1257  else if( i == solroot && !rpcmw )
1258  {
1259  int e1;
1260  for( e1 = g->inpbeg[i]; e1 != EAT_LAST; e1 = g->ieat[e1] )
1261  {
1262  if( g->tail[e1] == gRoot )
1263  break;
1264  }
1265 
1266  assert(e1 != EAT_LAST);
1267  result[e1] = CONNECT;
1268  }
1269  }
1270 
1271  if( !rpcmw )
1272  connected[gRoot] = TRUE;
1273 
1274  assert(connected[gRoot]);
1275 }
1276 
1277 
1278 /** add new solution to SCIP */
1280  SCIP* scip, /**< SCIP data structure */
1281  const GRAPH* g, /**< graph structure */
1282  const int* soledge, /**< solution */
1283  SCIP_HEUR* heur, /**< heuristic data or NULL */
1284  SCIP_Bool* success /**< denotes whether the new solution has been successfully added */
1285  )
1286 {
1287  SCIP_Real* nval;
1288  const int nedges = graph_get_nEdges(g);
1289 
1290  assert(scip && soledge);
1291  assert(solstp_isValid(scip, g, soledge));
1292 
1293  SCIP_CALL( SCIPallocBufferArray(scip, &nval, nedges) );
1294 
1295  for( int e = 0; e < nedges; e++ )
1296  nval[e] = (CONNECT == soledge[e]) ? 1.0 : 0.0;
1297 
1298  SCIP_CALL(SCIPprobdataAddNewSol(scip, nval, heur, success));
1299 
1300  SCIPfreeBufferArray(scip, &nval);
1301 
1302  return SCIP_OKAY;
1303 }
1304 
1305 
1306 /** (simple) pruning of given solution possible? */
1308  const GRAPH* g, /**< graph structure */
1309  const int* result, /**< ST edges */
1310  const STP_Bool* connected /**< ST nodes */
1311  )
1312 {
1313  const int nnodes = graph_get_nNodes(g);
1314  const SCIP_Bool isPc = graph_pc_isPc(g);
1315 
1316  for( int i = 0; i < nnodes; i++ )
1317  {
1318  int outedge;
1319 
1320  if( !connected[i] )
1321  continue;
1322 
1323  if( Is_term(g->term[i]) || Is_pseudoTerm(g->term[i]) )
1324  continue;
1325 
1326  for( outedge = g->outbeg[i]; outedge != EAT_LAST; outedge = g->oeat[outedge] )
1327  if( result[outedge] == CONNECT )
1328  break;
1329 
1330  if( outedge == EAT_LAST )
1331  {
1332  int e;
1333 
1334  if( isPc && graph_pc_knotIsNonLeafTerm(g, i) )
1335  {
1336  assert(g->prize && g->cost_org_pc);
1337 
1338  for( e = g->inpbeg[i]; e != EAT_LAST; e = g->ieat[e] )
1339  if( result[e] == CONNECT )
1340  break;
1341 
1342  assert(e != EAT_LAST);
1343 
1344  if( GE(g->prize[i], g->cost_org_pc[e]) )
1345  continue;
1346  }
1347 
1348  for( e = g->inpbeg[i]; e != EAT_LAST; e = g->ieat[e] )
1349  if( result[e] == CONNECT )
1350  break;
1351 
1352  if( e != EAT_LAST && EQ(g->cost[e], 0.0) )
1353  {
1354  continue;
1355  }
1356 
1357  return TRUE;
1358  }
1359  }
1360 
1361  return FALSE;
1362 }
1363 
1364 /** Prune solution given by included nodes.
1365  * NOTE: For PC/RPC this method will get the original edge costs before pruning! */
1367  SCIP* scip, /**< SCIP data structure */
1368  const GRAPH* g, /**< graph structure */
1369  int* result, /**< ST edges (out) */
1370  STP_Bool* connected /**< ST nodes (in/out) */
1371  )
1372 {
1373  const int nedges = graph_get_nEdges(g);
1374 
1375  assert(scip && result && connected);
1376  assert(g->stp_type != STP_DCSTP);
1377 
1378  for( int e = 0; e < nedges; e++ )
1379  result[e] = UNKNOWN;
1380 
1381  if( graph_pc_isPcMw(g) )
1382  {
1383  SCIP_Real* edgecosts = NULL;
1384  assert(g->extended);
1385 
1386  /* do we have biased edge costs? */
1387  if( graph_pc_isPc(g) )
1388  {
1389  SCIP_CALL( SCIPallocBufferArray(scip, &edgecosts, nedges) );
1390 
1391  graph_pc_getOrgCosts(scip, g, edgecosts);
1392  }
1393  else
1394  {
1395  edgecosts = g->cost;
1396  }
1397 
1398  SCIP_CALL( pruneSteinerTreePc(scip, g, edgecosts, result, connected) );
1399 
1400  if( graph_pc_isPc(g) )
1401  SCIPfreeBufferArray(scip, &edgecosts);
1402  }
1403  else
1404  {
1405  SCIP_CALL( pruneSteinerTreeStp(scip, g, g->cost, result, connected) );
1406  }
1407 
1408  assert(solstp_isValid(scip, g, result));
1409 
1410  return SCIP_OKAY;
1411 }
1412 
1413 
1414 /** prune solution given by included nodes */
1416  SCIP* scip, /**< SCIP data structure */
1417  const GRAPH* g, /**< graph structure */
1418  int* result, /**< ST edges */
1419  STP_Bool* connected /**< ST nodes */
1420  )
1421 {
1422  assert(scip && g && result && connected);
1423  assert(g->stp_type != STP_DHCSTP);
1424 
1425  SCIP_CALL( solstp_prune(scip, g, result, connected) );
1426 
1427  return SCIP_OKAY;
1428 }
1429 
1430 
1431 /** prune solution given by included edges */
1433  SCIP* scip, /**< SCIP data structure */
1434  const GRAPH* g, /**< graph structure */
1435  int* result /**< ST edges */
1436  )
1437 {
1438  STP_Bool* connected;
1439  const int nnodes = graph_get_nNodes(g);
1440  const int nedges = graph_get_nEdges(g);
1441 
1442  assert(scip && result);
1443  assert(solstp_isValid(scip, g, result));
1444 
1445  SCIP_CALL( SCIPallocBufferArray(scip, &connected, nnodes) );
1446 
1447  for( int k = 0; k < nnodes; k++ )
1448  connected[k] = FALSE;
1449 
1450  for( int e = 0; e < nedges; e++ )
1451  {
1452  if( CONNECT == result[e] )
1453  {
1454  connected[g->head[e]] = TRUE;
1455  connected[g->tail[e]] = TRUE;
1456  }
1457  }
1458 
1459 #ifdef SCIP_DEBUG
1460  SCIPdebugMessage("prune from edges: \n");
1461  solstp_print(g, result);
1462 #endif
1463 
1464  SCIP_CALL( solstp_pruneFromNodes(scip, g, result, connected) );
1465 
1466  SCIPfreeBufferArray(scip, &connected);
1467 
1468  return SCIP_OKAY;
1469 }
1470 
1471 
1472 /** Prunes solution with respect to the provided edges costs.
1473  * NOTE: method exists purely for optimization, so that unbiased costs for PC do not have to computed again! */
1475  SCIP* scip, /**< SCIP data structure */
1476  const GRAPH* g, /**< graph structure */
1477  const SCIP_Real* cost, /**< edge costs (original edge costs for PC!) */
1478  int* RESTRICT result, /**< ST edges */
1479  STP_Bool* RESTRICT connected /**< ST nodes */
1480  )
1481 {
1482  const int nedges = graph_get_nEdges(g);
1483 
1484  assert(scip && result && connected);
1485 
1486  if( g->stp_type != STP_DHCSTP )
1487  {
1488  for( int e = 0; e < nedges; e++ )
1489  result[e] = UNKNOWN;
1490  }
1491 
1492  if( graph_pc_isPcMw(g) )
1493  {
1494  if( graph_pc_isPc(g) )
1495  {
1496  assert(cost);
1497  assert(graph_pc_costsEqualOrgCosts(scip, g, cost));
1498  SCIP_CALL( pruneSteinerTreePc(scip, g, cost, result, connected) );
1499  }
1500  else
1501  {
1502  assert(!cost);
1503  SCIP_CALL( pruneSteinerTreePc(scip, g, g->cost, result, connected) );
1504  }
1505  }
1506  else
1507  SCIP_CALL( pruneSteinerTreeStp(scip, g, (g->stp_type != STP_DHCSTP) ? g->cost : cost, result, connected) );
1508 
1509  return SCIP_OKAY;
1510 }
1511 
1512 
1513 /** Prunes solution with respect to the provided edges costs.
1514  * CSR version! */
1516  SCIP* scip, /**< SCIP data structure */
1517  const GRAPH* g, /**< graph structure */
1518  SPATHS* spaths, /**< shortest paths;
1519  NOTE: distances and preds not valid afterwards!
1520  hacky, but improves cache-efficiency */
1521  int* RESTRICT result /**< ST edges */
1522  )
1523 {
1524  const int nnodes = spaths->csr->nnodes;
1525  const int nedges = spaths->csr->start[nnodes];
1526 
1527  assert(scip && result);
1528  assert(nedges <= g->edges);
1529 
1530  assert(g->stp_type != STP_DHCSTP && "does not work because DHCSTP uses different edge costs");
1531 
1532  for( int e = 0; e < nedges; e++ )
1533  result[e] = UNKNOWN;
1534 
1535  if( graph_pc_isPcMw(g) )
1536  {
1537  MST mst = { .csr = spaths->csr_orgcosts, .dheap = spaths->dheap, .nodes_dist = spaths->nodes_dist,
1538  .nodes_predEdge = spaths->nodes_pred};
1539 
1540  assert(graph_pc_isPc(g) || graph_csr_costsAreInSync(g, mst.csr, g->cost));
1541 
1542  SCIP_CALL( pruneSteinerTreePc_csr(scip, g, &mst, result, spaths->nodes_isConnected) );
1543  }
1544  else
1545  {
1546  MST mst = { .csr = spaths->csr_orgcosts, .dheap = spaths->dheap,
1547  .nodes_dist = spaths->nodes_dist, .nodes_predEdge = spaths->nodes_pred };
1548 
1549  assert(graph_csr_costsAreInSync(g, mst.csr, g->cost));
1550 
1551  pruneSteinerTreeStp_csr(g, &mst, result, spaths->nodes_isConnected);
1552  }
1553 
1554  return SCIP_OKAY;
1555 }
1556 
1557 
1558 /** changes solution according to given root */
1560  SCIP* scip, /**< SCIP data structure */
1561  const GRAPH* g, /**< the graph */
1562  int* result, /**< solution array (CONNECT/UNKNOWN) */
1563  int newroot /**< the new root */
1564  )
1565 {
1566  SCIP_Bool isInfeasible;
1567  assert(scip && g && result);
1568 
1569  SCIP_CALL( reroot(scip, g, result, newroot, &isInfeasible) );
1570 
1571  assert(!isInfeasible);
1572 
1573  return SCIP_OKAY;
1574 }
1575 
1576 
1577 
1578 /** changes solution according to given root; also checks for infeasibility */
1580  SCIP* scip, /**< SCIP data structure */
1581  GRAPH* g, /**< the graph */
1582  int* result, /**< solution array (CONNECT/UNKNOWN) */
1583  int newroot, /**< the new root */
1584  SCIP_Bool* isInfeasible /**< infeasible? */
1585  )
1586 {
1587  assert(scip && g && result && isInfeasible);
1588 
1589  SCIP_CALL( reroot(scip, g, result, newroot, isInfeasible) );
1590 
1591  return SCIP_OKAY;
1592 }
1593 
1594 
1595 /** checks whether edge(s) of given primal solution have been deleted */
1597  SCIP* scip, /**< SCIP data structure */
1598  const GRAPH* graph, /**< graph data structure */
1599  const int* result /**< solution array, indicating whether an edge is in the solution */
1600  )
1601 {
1602  const int nedges = graph_get_nEdges(graph);
1603 
1604  assert(scip && result);
1605 
1606  if( graph_typeIsDirected(graph) )
1607  {
1608  for( int e = 0; e < nedges; e++ )
1609  {
1610  if( result[e] == CONNECT && (graph->oeat[e] == EAT_FREE || GE(graph->cost[e], FARAWAY)) )
1611  return FALSE;
1612  }
1613  }
1614  else
1615  {
1616  for( int e = 0; e < nedges; e++ )
1617  {
1618  if( result[e] == CONNECT && graph->oeat[e] == EAT_FREE )
1619  return FALSE;
1620  }
1621  }
1622 
1623  return TRUE;
1624 }
1625 
1626 
1627 /** is the node contained in the solution? */
1629  const GRAPH* g, /**< graph data structure */
1630  const int* result, /**< solution array, indicating whether an edge is in the solution */
1631  int node /**< node to check for */
1632  )
1633 {
1634  assert(g && result);
1635  assert(node >= 0 && node < g->knots);
1636 
1637  for( int e = g->outbeg[node]; e != EAT_LAST; e = g->oeat[e] )
1638  {
1639  if( result[e] == CONNECT || result[flipedge(e)] == CONNECT )
1640  {
1641  return TRUE;
1642  }
1643  }
1644 
1645  return FALSE;
1646 }
1647 
1648 
1649 /** verifies whether a given primal solution is feasible */
1651  SCIP* scip, /**< SCIP data structure */
1652  const GRAPH* graph, /**< graph data structure */
1653  const int* result /**< solution array, indicating whether an edge is in the solution */
1654  )
1655 {
1656  SCIP_Bool isValid;
1657  int* queue = NULL;
1658  STP_Bool* reached = NULL;
1659  int size;
1660  int nterms;
1661  int termcount;
1662  const int nnodes = graph_get_nNodes(graph);
1663  const int root = graph->source;
1664  SCIP_Bool countpseudo;
1665 
1666  assert(scip && result);
1667  assert(root >= 0);
1668 
1669 #ifndef NDEBUG
1670  for( int e = 0; e < graph->edges; ++e )
1671  assert(graph->stp_type == STP_DCSTP || result[e] == CONNECT || result[e] == UNKNOWN);
1672 #endif
1673 
1674  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &reached, nnodes) );
1675  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &queue, nnodes) );
1676 
1677  if( graph_pc_isPcMw(graph) && !graph->extended )
1678  {
1679  countpseudo = TRUE;
1680  nterms = graph_pc_nProperPotentialTerms(graph);
1681 
1682  if( graph_pc_isRootedPcMw(graph) )
1683  {
1684  nterms += graph_pc_nFixedTerms(graph);
1685  }
1686  else
1687  {
1688  nterms++;
1689  }
1690  }
1691  else
1692  {
1693  countpseudo = FALSE;
1694  nterms = graph->terms;
1695  }
1696 
1697  for( int i = 0; i < nnodes; i++ )
1698  reached[i] = FALSE;
1699 
1700  /* BFS until all terminals are reached */
1701 
1702  termcount = 1;
1703  size = 0;
1704  reached[root] = TRUE;
1705  queue[size++] = root;
1706 
1707  while( size )
1708  {
1709  const int node = queue[--size];
1710 
1711  for( int e = graph->outbeg[node]; e != EAT_LAST; e = graph->oeat[e] )
1712  {
1713  if( result[e] == CONNECT )
1714  {
1715  const int i = graph->head[e];
1716 
1717  /* cycle? */
1718  if( reached[i] )
1719  {
1720  SCIPfreeBufferArray(scip, &queue);
1721  SCIPfreeBufferArray(scip, &reached);
1722 
1723  SCIPdebugMessage("solution contains a cycle ... \n");
1724  return FALSE;
1725  }
1726 
1727  if( countpseudo )
1728  {
1729  if( Is_pseudoTerm(graph->term[i]) || graph_pc_knotIsFixedTerm(graph, i) )
1730  termcount++;
1731  }
1732  else
1733  {
1734  if( Is_term(graph->term[i]) )
1735  termcount++;
1736  }
1737 
1738  reached[i] = TRUE;
1739  queue[size++] = i;
1740  }
1741  }
1742  }
1743 
1744  isValid = (termcount == nterms);
1745 
1746 #ifdef SCIP_DEBUG
1747  if( !isValid )
1748  {
1749  printf("termcount %d graph->terms %d \n", termcount, nterms);
1750  printf("root %d \n", root);
1751 
1752  for( int i = 0; i < nnodes; i++ )
1753  {
1754  const int isMandatoryTerm = countpseudo?
1755  (Is_pseudoTerm(graph->term[i]) || graph_pc_knotIsFixedTerm(graph, i)) : Is_term(graph->term[i]);
1756 
1757  if( !reached[i] && isMandatoryTerm )
1758  {
1759  if( graph_pc_isPc(graph) && graph_pc_termIsNonLeafTerm(graph, i) )
1760  continue;
1761 
1762  printf("fail: ");
1763  graph_knot_printInfo(graph, i);
1764 
1765  for( int e = graph->inpbeg[i]; e != EAT_LAST; e = graph->ieat[e] )
1766  {
1767  printf("...neighbor: ");
1768  graph_knot_printInfo(graph, graph->tail[e]);
1769  }
1770  }
1771  }
1772  solstp_print(graph, result);
1773  }
1774 #endif
1775 
1776  if( isValid && graph->stp_type == STP_DCSTP )
1777  {
1778  assert(graph->maxdeg);
1779  for( int i = 0; i < nnodes; i++ )
1780  {
1781  int deg = 0;
1782  for( int e = graph->outbeg[i]; e != EAT_LAST; e = graph->oeat[e] )
1783  {
1784  if( result[e] == CONNECT || result[flipedge(e)] == CONNECT )
1785  deg++;
1786  }
1787 
1788  if( deg > graph->maxdeg[i] )
1789  {
1790 #ifdef SCIP_DEBUG
1791  SCIPdebugMessage("maximum degree violated (%d > %d) for ", deg, graph->maxdeg[i]);
1792  graph_knot_printInfo(graph, i);
1793 #endif
1794  isValid = FALSE;
1795  break;
1796  }
1797  }
1798  }
1799 
1800  SCIPfreeBufferArray(scip, &queue);
1801  SCIPfreeBufferArray(scip, &reached);
1802 
1803  return isValid;
1804 }
1805 
1806 
1807 /** prints given solution */
1809  const GRAPH* graph, /**< graph data structure */
1810  const int* result /**< solution array, indicating whether an edge is in the solution */
1811  )
1812 {
1813  const int nedges = graph_get_nEdges(graph);
1814 
1815  assert(result);
1816 
1817  printf("solution tree edges: \n");
1818 
1819  for( int e = 0; e < nedges; ++e )
1820  {
1821  assert(result[e] == CONNECT || result[e] == UNKNOWN);
1822 
1823  if( CONNECT == result[e] )
1824  {
1825  printf(" ");
1826  graph_edge_printInfo(graph, e);
1827  }
1828  }
1829 }
1830 
1831 
1832 /** compute solution value for given edge-solution array (CONNECT/UNKNOWN) and offset */
1834  const GRAPH* g, /**< the graph */
1835  const int* soledge, /**< solution */
1836  SCIP_Real offset, /**< offset */
1837  int nedges /**< number of edges */
1838  )
1839 {
1840  register SCIP_Real obj = offset;
1841  const SCIP_Real* const edgecost = g->cost;
1842 
1843  assert(nedges == g->edges);
1844  assert(!graph_pc_isPcMw(g) || g->extended);
1845 
1846  for( int e = 0; e < nedges; e++ )
1847  {
1848  assert(soledge[e] == CONNECT || soledge[e] == UNKNOWN);
1849 
1850  if( soledge[e] == CONNECT )
1851  obj += edgecost[e];
1852  }
1853 
1854  return obj;
1855 }
1856 
1857 
1858 /** compute solution value for given edge-solution array (CONNECT/UNKNOWN) and offset */
1860  const GRAPH* g, /**< the graph */
1861  const int* soledge, /**< solution */
1862  SCIP_Real offset /**< offset */
1863  )
1864 {
1865  assert(g);
1866 
1867  return solstp_getObjBounded(g, soledge, offset, g->edges);
1868 }
1869 
1870 
1871 /** compute solution value for given edge-solution array */
1873  const GRAPH* g, /**< the graph */
1874  const CSR* csr, /**< the csr */
1875  const int* soledge_csr, /**< solution (CONNECT/UNKNOWN) */
1876  const STP_Bool* solnode /**< solution vertices (TRUE/FALSE) */
1877  )
1878 {
1879  const int nnodes = graph_get_nNodes(g);
1880  const int nedges_csr = graph_csr_getNedges(csr);
1881  const SCIP_Real* const edgecost_csr = csr->cost;
1882  const SCIP_Real* const prize = g->prize;
1883  const int* const gTerm = g->term;
1884  register SCIP_Real obj = 0.0;
1885  const SCIP_Bool isPc = graph_pc_isPc(g);
1886 
1887  assert(graph_pc_isPcMw(g));
1888  assert(g->extended);
1889  assert(nnodes == csr->nnodes);
1890  assert(nedges_csr <= g->edges);
1891 
1892  for( int e = 0; e < nedges_csr; e++ )
1893  {
1894  assert(soledge_csr[e] == CONNECT || soledge_csr[e] == UNKNOWN);
1895 
1896  if( soledge_csr[e] == CONNECT )
1897  obj += edgecost_csr[e];
1898  }
1899 
1900  for( int k = 0; k < nnodes; k++ )
1901  {
1902  if( solnode[k] )
1903  continue;
1904 
1905  if( Is_pseudoTerm(gTerm[k]) )
1906  {
1907  assert(g->grad[k] >= 1);
1908  obj += prize[k];
1909  }
1910  else if( isPc && Is_nonleafTerm(gTerm[k]) )
1911  {
1912  obj += prize[k];
1913  }
1914  }
1915 
1916  return obj;
1917 }
1918 
1919 
1920 /** compute solution value for given edge-solution array */
1922  const GRAPH* g, /**< the graph */
1923  const CSR* csr, /**< the csr */
1924  const int* soledge_csr, /**< solution (CONNECT/UNKNOWN) */
1925  const STP_Bool* solnode /**< solution vertices (TRUE/FALSE) */
1926  )
1927 {
1928  const int nedges_csr = graph_csr_getNedges(csr);
1929  const SCIP_Real* const edgecost_csr = csr->cost;
1930  register SCIP_Real obj = 0.0;
1931 
1932  assert(!graph_pc_isPcMw(g));
1933  assert(graph_get_nNodes(g) == csr->nnodes);
1934  assert(nedges_csr <= g->edges);
1935 
1936  for( int e = 0; e < nedges_csr; e++ )
1937  {
1938  assert(soledge_csr[e] == CONNECT || soledge_csr[e] == UNKNOWN);
1939 
1940  if( soledge_csr[e] == CONNECT )
1941  obj += edgecost_csr[e];
1942  }
1943 
1944  return obj;
1945 }
1946 
1947 
1948 /** gets STP solution from SCIP solution */
1950  SCIP* scip, /**< SCIP data structure */
1951  SCIP_SOL* scipsol, /**< SCIP solution data structure */
1952  const GRAPH* g, /**< the graph */
1953  int* soledges /**< solution (CONNECT/UNKNOWN) */
1954  )
1955 {
1956  const SCIP_Real* xval;
1957  const int nedges = graph_get_nEdges(g);
1958 
1959  assert(scip && scipsol && soledges);
1960 
1961  xval = SCIPprobdataGetXval(scip, scipsol);
1962  assert(xval);
1963 
1964  for( int e = 0; e < nedges; e++ )
1965  {
1966  if( EQ(xval[e], 1.0) )
1967  soledges[e] = CONNECT;
1968  else
1969  soledges[e] = UNKNOWN;
1970  }
1971 }
1972 
1973 
1974 
1975 /** converts solution from CSR to graph based */
1977  SCIP* scip, /**< SCIP data structure */
1978  const GRAPH* g, /**< the graph */
1979  const CSR* csr, /**< the CSR */
1980  const int* soledge_csr, /**< CSR solution (CONNECT/UNKNOWN) */
1981  STP_Bool* RESTRICT solnode, /**< solution vertices (TRUE/FALSE) in/out! */
1982  int* RESTRICT soledge_g /**< graph solution (CONNECT/UNKNOWN) out */
1983 )
1984 {
1985  const int nedges_g = graph_get_nEdges(g);
1986  const int nedges_csr = graph_csr_getNedges(csr);
1987  const int* const edgeid = csr->edge_id;
1988 
1989  assert(solnode && soledge_csr && soledge_g);
1990  assert(edgeid);
1991  assert(0 <= nedges_csr && nedges_csr <= nedges_g);
1992 
1993  for( int i = 0; i < nedges_g; i++ )
1994  {
1995  soledge_g[i] = UNKNOWN;
1996  }
1997 
1998  for( int i = 0; i < nedges_csr; i++ )
1999  {
2000  if( CONNECT == soledge_csr[i] )
2001  {
2002  const int edge_g = edgeid[i];
2003 
2004  assert(0 <= edge_g && edge_g < nedges_g);
2005  assert(UNKNOWN == soledge_g[edge_g]);
2006 
2007  soledge_g[edge_g] = CONNECT;
2008  }
2009  }
2010 
2011  if( graph_pc_isPcMw(g) )
2012  {
2013  const int solroot = solstp_pcGetSolRoot(scip, g, solnode);
2014  solstp_pcConnectDummies(g, solroot, soledge_g, solnode);
2015  }
2016 }
2017 
2018 
2019 /** sets trivial solution (all UNKNOWN) */
2021  const GRAPH* g, /**< the graph */
2022  int* soledge /**< solution */
2023  )
2024 {
2025  const int nedges = graph_get_nEdges(g);
2026 
2027  assert(soledge);
2028 
2029  for( int e = 0; e < nedges; e++ )
2030  {
2031  soledge[e] = UNKNOWN;
2032  }
2033 
2034  if( graph_pc_isPcMw(g) )
2035  pcsolGetTrivialEdges(g, NULL, soledge);
2036 }
2037 
2038 
2039 /** computes number of edges in solution value */
2041  const GRAPH* g, /**< the graph */
2042  const int* soledge /**< solution */
2043  )
2044 {
2045  const int nedges = graph_get_nEdges(g);
2046  int edgecount = 0;
2047 
2048  assert(soledge);
2049 
2050  for( int e = 0; e < nedges; e++ )
2051  if( soledge[e] == CONNECT )
2052  edgecount++;
2053 
2054  return edgecount;
2055 }
2056 
2057 /** computes number of edges in solution value */
2059  const GRAPH* g, /**< the graph */
2060  const int* soledge, /**< solution */
2061  int nedges /**< the (first) number of edges to consider */
2062  )
2063 {
2064  int edgecount = 0;
2065 
2066  assert(nedges <= graph_get_nEdges(g));
2067  assert(soledge);
2068 
2069  for( int e = 0; e < nedges; e++ )
2070  if( soledge[e] == CONNECT )
2071  edgecount++;
2072 
2073  return edgecount;
2074 }
2075 
2076 
2077 /** marks vertices for given edge-solution array (CONNECT/UNKNOWN) */
2079  const GRAPH* g, /**< the graph */
2080  const int* result, /**< solution array (CONNECT/UNKNOWN) */
2081  STP_Bool* solnode /**< marks whether node is in solution */
2082 )
2083 {
2084  const int nedges = g->edges;
2085  const int nnodes = g->knots;
2086 
2087  assert(g && result && solnode);
2088 
2089  for( int i = 0; i < nnodes; i++ )
2090  solnode[i] = FALSE;
2091 
2092  solnode[g->source] = TRUE;
2093 
2094  for( int e = 0; e < nedges; e++ )
2095  {
2096  if( result[e] == CONNECT )
2097  {
2098  assert(g->oeat[e] != EAT_FREE);
2099 
2100  solnode[g->head[e]] = TRUE;
2101  }
2102  }
2103 
2104 #ifndef NDEBUG
2105  for( int e = 0; e < nedges; e++ )
2106  if( result[e] == CONNECT )
2107  assert(solnode[g->head[e]] && solnode[g->tail[e]]);
2108 #endif
2109 }
2110 
2111 
2112 
2113 /** marks vertices for given edge-solution array (both CONNECT/UNKNOWN) */
2115  const GRAPH* g, /**< the graph */
2116  const int* soledge, /**< solution array (CONNECT/UNKNOWN) */
2117  int* solnode /**< marks whether node is in solution */
2118 )
2119 {
2120  const int nedges = g->edges;
2121  const int nnodes = g->knots;
2122 
2123  assert(g && soledge && solnode);
2124 
2125  for( int i = 0; i < nnodes; i++ )
2126  solnode[i] = UNKNOWN;
2127 
2128  solnode[g->source] = CONNECT;
2129 
2130  for( int e = 0; e < nedges; e++ )
2131  {
2132  if( soledge[e] == CONNECT )
2133  {
2134  assert(g->oeat[e] != EAT_FREE);
2135 
2136  solnode[g->head[e]] = CONNECT;
2137  }
2138  }
2139 
2140 #ifndef NDEBUG
2141  for( int e = 0; e < nedges; e++ )
2142  if( soledge[e] == CONNECT )
2143  assert(solnode[g->head[e]] == CONNECT && solnode[g->tail[e]] == CONNECT);
2144 #endif
2145 }
2146 
2147 /** get original solution */
2149  SCIP* scip, /**< SCIP data structure */
2150  const GRAPH* transgraph, /**< the transformed graph */
2151  const GRAPH* orggraph, /**< the original graph */
2152  const int* transsoledge, /**< solution for transformed problem */
2153  int* orgsoledge /**< new retransformed solution */
2154 )
2155 {
2156  STP_Bool* orgnodearr;
2157  const int transnedges = transgraph->edges;
2158  const int orgnnodes = orggraph->knots;
2159  const SCIP_Bool pcmw = graph_pc_isPcMw(transgraph);
2160 
2161  assert(transgraph != NULL && orggraph != NULL && transsoledge != NULL && orgsoledge != NULL);
2162  assert(transgraph->ancestors != NULL);
2163  assert(transgraph->stp_type == orggraph->stp_type);
2164 
2165  SCIP_CALL( SCIPallocBufferArray(scip, &orgnodearr, orgnnodes) );
2166 
2167  for( int k = 0; k < orgnnodes; k++ )
2168  orgnodearr[k] = FALSE;
2169 
2170  for( int e = 0; e < transnedges; e++ )
2171  if( transsoledge[e] == CONNECT )
2172  setNodeList(orggraph, orgnodearr, graph_edge_getAncestors(transgraph, e));
2173 
2174  /* retransform edges fixed during graph reduction */
2175  setNodeList(orggraph, orgnodearr, graph_getFixedges(transgraph));
2176 
2177  if( pcmw )
2178  {
2179  // potentially single-vertex solution?
2180  if( graph_pc_isRootedPcMw(transgraph) && transgraph->terms == 1 && graph_pc_nFixedTerms(orggraph) == 1 )
2181  orgnodearr[orggraph->source] = TRUE;
2182 
2183  SCIP_CALL( solstp_markPcancestors(scip, transgraph->pcancestors, orggraph->tail, orggraph->head, orgnnodes,
2184  orgnodearr, NULL, NULL, NULL, NULL ) );
2185  }
2186 
2187  /* prune solution (in original graph) */
2188  SCIP_CALL( solstp_prune(scip, orggraph, orgsoledge, orgnodearr) );
2189 
2190  SCIPfreeBufferArray(scip, &orgnodearr);
2191 
2192  assert(solstp_isValid(scip, orggraph, orgsoledge));
2193 
2194  return SCIP_OKAY;
2195 }
2196 
2197 
2198 
2199 /** mark original solution */
2201  SCIP* scip, /**< SCIP data structure */
2202  IDX** pcancestors, /**< the ancestors */
2203  const int* tails, /**< tails array */
2204  const int* heads, /**< heads array */
2205  int orgnnodes, /**< original number of nodes */
2206  STP_Bool* solnodemark, /**< solution nodes mark array */
2207  STP_Bool* soledgemark, /**< solution edges mark array or NULL */
2208  int* solnodequeue, /**< solution nodes queue or NULL */
2209  int* nsolnodes, /**< number of solution nodes or NULL */
2210  int* nsoledges /**< number of solution edges or NULL */
2211 )
2212 {
2213  int* queue;
2214  int nnodes;
2215  int nedges = (nsoledges != NULL)? *nsoledges : 0;
2216  int qstart;
2217  int qend;
2218 
2219  assert(scip != NULL && tails != NULL && heads != NULL && pcancestors != NULL && solnodemark != NULL);
2220 
2221  if( solnodequeue != NULL )
2222  queue = solnodequeue;
2223  else
2224  SCIP_CALL( SCIPallocBufferArray(scip, &queue, orgnnodes) );
2225 
2226  if( nsolnodes == NULL )
2227  {
2228  assert(solnodequeue == NULL);
2229  nnodes = 0;
2230  for( int k = 0; k < orgnnodes; k++ )
2231  if( solnodemark[k] )
2232  queue[nnodes++] = k;
2233  }
2234  else
2235  {
2236  nnodes = *nsolnodes;
2237  assert(solnodequeue != NULL);
2238  }
2239 
2240  qstart = 0;
2241  qend = nnodes;
2242 
2243  while( qend != qstart )
2244  {
2245  int k = qstart;
2246 
2247  assert(qstart < qend);
2248  qstart = qend;
2249 
2250  for( ; k < qend; k++ )
2251  {
2252  const int ancestornode = queue[k];
2253 
2254  assert(solnodemark[ancestornode]);
2255 
2256  for( IDX* curr = pcancestors[ancestornode]; curr != NULL; curr = curr->parent )
2257  {
2258  const int ancestoredge = curr->index;
2259  assert(tails[ancestoredge] < orgnnodes && heads[ancestoredge] < orgnnodes);
2260 
2261  if( soledgemark != NULL && !soledgemark[ancestoredge] )
2262  {
2263  soledgemark[ancestoredge] = TRUE;
2264  nedges++;
2265  }
2266  if( !solnodemark[tails[ancestoredge]] )
2267  {
2268  solnodemark[tails[ancestoredge]] = TRUE;
2269  queue[nnodes++] = tails[ancestoredge];
2270  }
2271  if( !solnodemark[heads[ancestoredge]] )
2272  {
2273  solnodemark[heads[ancestoredge]] = TRUE;
2274  queue[nnodes++] = heads[ancestoredge];
2275  }
2276  }
2277  }
2278  qend = nnodes;
2279  }
2280 
2281  if( nsolnodes != NULL )
2282  *nsolnodes = nnodes;
2283 
2284  if( nsoledges != NULL )
2285  *nsoledges = nedges;
2286 
2287  if( solnodequeue == NULL )
2288  SCIPfreeBufferArray(scip, &queue);
2289 
2290  return SCIP_OKAY;
2291 }
static SCIP_RETCODE pruneSteinerTreePc_csr(SCIP *scip, const GRAPH *g, MST *mst, int *RESTRICT result, STP_Bool *RESTRICT connected)
Definition: solstp.c:1055
static void pcsubtreeDelete(const GRAPH *g, int subtree_root, int dfspos[], int result[], STP_Bool connected[])
Definition: solstp.c:200
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
static volatile int nterms
Definition: interrupt.c:38
SCIP_Bool graph_pc_isMw(const GRAPH *)
SCIP_RETCODE solstp_addSolToProb(SCIP *scip, const GRAPH *g, const int *soledge, SCIP_HEUR *heur, SCIP_Bool *success)
Definition: solstp.c:1279
int *RESTRICT head
Definition: graphdefs.h:224
SCIP_Bool graph_typeIsDirected(const GRAPH *)
Definition: graph_stats.c:83
int * head
Definition: graphdefs.h:141
int source
Definition: graphdefs.h:195
int SCIPprobdataGetNTerms(SCIP *scip)
SCIP_Bool graph_pc_isRootedPcMw(const GRAPH *)
#define Is_term(a)
Definition: graphdefs.h:102
SCIP_Bool graph_csr_costsAreInSync(const GRAPH *, const CSR *, const SCIP_Real *)
Definition: graph_util.c:1448
signed int edge
Definition: graphdefs.h:287
Shortest path based algorithms for Steiner problems.
SCIP_RETCODE solstp_pruneFromNodes(SCIP *scip, const GRAPH *g, int *result, STP_Bool *connected)
Definition: solstp.c:1415
int terms
Definition: graphdefs.h:192
static SCIP_RETCODE pruneSteinerTreeStp(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int *result, STP_Bool *connected)
Definition: solstp.c:837
static SCIP_RETCODE reroot(SCIP *scip, const GRAPH *g, int *result, int newroot, SCIP_Bool *isInfeasible)
Definition: solstp.c:43
void solstp_pcConnectDummies(const GRAPH *g, int solroot, int *RESTRICT result, STP_Bool *RESTRICT connected)
Definition: solstp.c:1200
int graph_pc_nFixedTerms(const GRAPH *)
const CSR * csr
Definition: shortestpath.h:50
void graph_path_exec(SCIP *, const GRAPH *, int, int, const SCIP_Real *, PATH *)
Definition: graph_path.c:541
SCIP_RETCODE solstp_getOrg(SCIP *scip, const GRAPH *transgraph, const GRAPH *orggraph, const int *transsoledge, int *orgsoledge)
Definition: solstp.c:2148
SCIP_RETCODE solstp_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: solstp.c:2200
includes methods for Steiner tree problem solutions
int *RESTRICT maxdeg
Definition: graphdefs.h:206
void graph_knot_printInfo(const GRAPH *, int)
Definition: graph_stats.c:151
static SCIP_RETCODE strongPruneSteinerTreePc_csr(SCIP *scip, const GRAPH *g, const CSR *csr_orgcosts, int solroot, int *result, STP_Bool *connected)
Definition: solstp.c:787
#define EAT_FREE
Definition: graphdefs.h:57
#define FALSE
Definition: def.h:87
static SCIP_Real pcsubtreePruneForProfit_csr(const CSR *csr_orgcosts, const SCIP_Real *prize, SCIP_Bool isPc, int subtree_root, int *RESTRICT dfspos, int *RESTRICT result, STP_Bool *RESTRICT connected, int *RESTRICT dfscount)
Definition: solstp.c:355
int *RESTRICT inpbeg
Definition: graphdefs.h:202
SCIP_Real * cost
Definition: graphdefs.h:142
int *RESTRICT path_state
Definition: graphdefs.h:256
SCIP_Bool solstp_isUnreduced(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1596
Problem data for stp problem.
#define TRUE
Definition: def.h:86
#define SCIPdebug(x)
Definition: pub_message.h:84
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
#define STP_DCSTP
Definition: graphdefs.h:47
int *RESTRICT nodes_predEdge
Definition: mst.h:46
void solstp_convertCsrToGraph(SCIP *scip, const GRAPH *g, const CSR *csr, const int *soledge_csr, STP_Bool *RESTRICT solnode, int *RESTRICT soledge_g)
Definition: solstp.c:1976
minimum spanning tree based algorithms for Steiner problems
SCIP_RETCODE solstp_pruneFromTmHeur(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int *RESTRICT result, STP_Bool *RESTRICT connected)
Definition: solstp.c:1474
static SCIP_RETCODE pcsolGetMstEdges(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int root, int *result)
Definition: solstp.c:449
SCIP_Real *RESTRICT nodes_dist
Definition: shortestpath.h:55
int graph_csr_getNedges(const CSR *)
Definition: graph_util.c:1536
#define EAT_LAST
Definition: graphdefs.h:58
#define SCIPdebugMessage
Definition: pub_message.h:87
#define FARAWAY
Definition: graphdefs.h:89
SCIP_Real solstp_pcGetObjCsr(const GRAPH *g, const CSR *csr, const int *soledge_csr, const STP_Bool *solnode)
Definition: solstp.c:1872
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
#define Is_nonleafTerm(a)
Definition: graphdefs.h:104
SCIP_Real * cost_org_pc
Definition: graphdefs.h:222
int * start
Definition: graphdefs.h:140
int solstp_getNedgesBounded(const GRAPH *g, const int *soledge, int nedges)
Definition: solstp.c:2058
static void setNodeList(const GRAPH *g, STP_Bool *RESTRICT solnode, IDX *listnode)
Definition: solstp.c:1109
STP_Bool *RESTRICT nodes_isConnected
Definition: shortestpath.h:58
void solstp_getStpFromSCIPsol(SCIP *scip, SCIP_SOL *scipsol, const GRAPH *g, int *soledges)
Definition: solstp.c:1949
int *RESTRICT mark
Definition: graphdefs.h:198
SCIP_Bool graph_pc_termIsNonLeafTerm(const GRAPH *, int)
void mst_computeOnMarked(const GRAPH *g, const STP_Bool *nodes_isMarked, int startnode, MST *mst)
Definition: mst.c:223
SCIP_RETCODE solstp_rerootInfeas(SCIP *scip, GRAPH *g, int *result, int newroot, SCIP_Bool *isInfeasible)
Definition: solstp.c:1579
static SCIP_RETCODE strongPruneSteinerTreePc(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int solroot, int *result, STP_Bool *connected)
Definition: solstp.c:730
int *RESTRICT oeat
Definition: graphdefs.h:231
#define LE(a, b)
Definition: portab.h:83
#define GE(a, b)
Definition: portab.h:85
void solstp_print(const GRAPH *graph, const int *result)
Definition: solstp.c:1808
SCIP_Bool extended
Definition: graphdefs.h:267
int stp_type
Definition: graphdefs.h:264
IDX ** ancestors
Definition: graphdefs.h:234
static void pcsubtreeDelete_csr(const CSR *csr_orgcosts, int subtree_root, int *RESTRICT dfspos, int *RESTRICT result, STP_Bool *RESTRICT connected)
Definition: solstp.c:247
SCIP_Real * prize
Definition: graphdefs.h:210
SCIP_RETCODE SCIPprobdataAddNewSol(SCIP *scip, SCIP_Real *nval, SCIP_HEUR *heur, SCIP_Bool *success)
int *RESTRICT grad
Definition: graphdefs.h:201
static void pcsolGetTrivialEdges(const GRAPH *g, const STP_Bool *connected, int *RESTRICT result)
Definition: solstp.c:420
#define NULL
Definition: lpi_spx1.cpp:155
#define STP_DHCSTP
Definition: graphdefs.h:52
#define EQ(a, b)
Definition: portab.h:79
static void pcsolMarkGraphNodes(const STP_Bool *connected, const GRAPH *g)
Definition: solstp.c:484
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
static SCIP_RETCODE pruneSteinerTreePc(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int *result, STP_Bool *connected)
Definition: solstp.c:970
IDX ** pcancestors
Definition: graphdefs.h:235
#define MST_MODE
Definition: graphdefs.h:98
SCIP_Real solstp_getObjCsr(const GRAPH *g, const CSR *csr, const int *soledge_csr, const STP_Bool *solnode)
Definition: solstp.c:1921
#define LT(a, b)
Definition: portab.h:81
unsigned char STP_Bool
Definition: portab.h:34
int SCIPprobdataGetNNodes(SCIP *scip)
const CSR * csr_orgcosts
Definition: shortestpath.h:52
SCIP_RETCODE solstp_pruneFromEdges(SCIP *scip, const GRAPH *g, int *result)
Definition: solstp.c:1432
static void stpsolPrune_csr(const GRAPH *g, const MST *mst, int *RESTRICT result, STP_Bool *RESTRICT connected)
Definition: solstp.c:648
void solstp_getTrivialSol(const GRAPH *g, int *soledge)
Definition: solstp.c:2020
SCIP_Real solstp_getObjBounded(const GRAPH *g, const int *soledge, SCIP_Real offset, int nedges)
Definition: solstp.c:1833
static SCIP_Real pcsubtreePruneForProfit(const GRAPH *g, const SCIP_Real *cost, int subtree_root, int *RESTRICT dfspos, int *RESTRICT result, STP_Bool *RESTRICT connected, int *RESTRICT dfscount)
Definition: solstp.c:289
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
SCIP_Bool solstp_containsNode(const GRAPH *g, const int *result, int node)
Definition: solstp.c:1628
#define SCIP_Bool
Definition: def.h:84
int *RESTRICT ieat
Definition: graphdefs.h:230
int *RESTRICT tail
Definition: graphdefs.h:223
#define flipedge(edge)
Definition: graphdefs.h:84
SCIP_Bool stpsol_pruningIsPossible(const GRAPH *g, const int *result, const STP_Bool *connected)
Definition: solstp.c:1307
int graph_pc_nProperPotentialTerms(const GRAPH *)
IDX * graph_getFixedges(const GRAPH *)
int *RESTRICT term
Definition: graphdefs.h:196
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
void graph_edge_printInfo(const GRAPH *, int)
Definition: graph_stats.c:133
SCIP_Bool graph_pc_knotIsNonLeafTerm(const GRAPH *, int)
const CSR * csr
Definition: mst.h:43
SCIP_Bool graph_pc_isPc(const GRAPH *)
#define CONNECT
Definition: graphdefs.h:87
Portable definitions.
int * edge_id
Definition: graphdefs.h:143
#define Is_pseudoTerm(a)
Definition: graphdefs.h:103
static void solGetMstEdges_csr(const GRAPH *g, const STP_Bool *connected, int root, MST *mst, int *RESTRICT result)
Definition: solstp.c:702
int *RESTRICT nodes_pred
Definition: shortestpath.h:56
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *, int)
SCIP_Real * cost
Definition: graphdefs.h:221
void solstp_setVertexFromEdgeConn(const GRAPH *g, const int *soledge, int *solnode)
Definition: solstp.c:2114
SCIP_RETCODE solstp_reroot(SCIP *scip, const GRAPH *g, int *result, int newroot)
Definition: solstp.c:1559
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
SCIP_VAR * a
Definition: circlepacking.c:57
static void pcsolMarkGraphNodes_csr(const GRAPH *g, STP_Bool *RESTRICT connected)
Definition: solstp.c:526
int solstp_pcGetSolRoot(SCIP *scip, const GRAPH *g, const STP_Bool *connected)
Definition: solstp.c:1140
#define SCIP_Real
Definition: def.h:177
SCIP_Real * SCIPprobdataGetXval(SCIP *scip, SCIP_SOL *sol)
int *RESTRICT outbeg
Definition: graphdefs.h:204
int edges
Definition: graphdefs.h:219
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
void graph_pc_getOrgCosts(SCIP *, const GRAPH *, SCIP_Real *)
void solstp_setVertexFromEdge(const GRAPH *g, const int *result, STP_Bool *solnode)
Definition: solstp.c:2078
SCIP_Bool graph_pc_costsEqualOrgCosts(SCIP *, const GRAPH *, const SCIP_Real *)
static SCIP_RETCODE pruneSteinerTreeStp_csr(const GRAPH *g, MST *mst, int *RESTRICT result, STP_Bool *RESTRICT connected)
Definition: solstp.c:940
#define UNKNOWN
Definition: sepa_mcf.c:4095
#define nnodes
Definition: gastrans.c:65
static void pcsolPrune(const GRAPH *g, int *result, STP_Bool *connected)
Definition: solstp.c:572
int solstp_getNedges(const GRAPH *g, const int *soledge)
Definition: solstp.c:2040
int * SCIPprobdataGetPctermsorder(SCIP *scip)
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:123
SCIP_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
struct Int_List_Node * parent
Definition: misc_stp.h:91
#define SCIP_CALL_ABORT(x)
Definition: def.h:363
#define Is_anyTerm(a)
Definition: graphdefs.h:105
SCIP_RETCODE solstp_prune(SCIP *scip, const GRAPH *g, int *result, STP_Bool *connected)
Definition: solstp.c:1366
SCIP_Real solstp_getObj(const GRAPH *g, const int *soledge, SCIP_Real offset)
Definition: solstp.c:1859
IDX * graph_edge_getAncestors(const GRAPH *, int)
SCIP_RETCODE solstp_pruneFromTmHeur_csr(SCIP *scip, const GRAPH *g, SPATHS *spaths, int *RESTRICT result)
Definition: solstp.c:1515