Scippy

SCIP

Solving Constraint Integer Programs

graph_pcbase.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 graph_pcbase.c
17  * @brief includes several methods for prize-collecting Steiner problem graphs
18  * @author Daniel Rehfeldt
19  *
20  * This file contains several basic methods to process prize-collecting Steiner problem graphs and kinsmen
21  * such as the maximum-weight connected subgraph problem.
22  *
23  */
24 
25 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
26 
27 //#define SCIP_DEBUG
28 #include "scip/misc.h"
29 #include <stdio.h>
30 #include <stdlib.h>
31 #include <string.h>
32 #include <assert.h>
33 #include "solstp.h"
34 #include "portab.h"
35 #include "graph.h"
36 
37 
38 
39 /*
40  * local functions
41  */
42 
43 
44 /** remove non-leaf terminals by edge weight shifting (call before graph transformation was performed) */
45 static inline
47  SCIP* scip, /**< SCIP */
48  GRAPH* g /**< the graph */
49 )
50 {
51  const int nnodes = g->knots;
52 
53  assert(!g->extended);
54 
55  for( int k = 0; k < nnodes; k++ )
56  {
57  if( !Is_term(g->term[k]) )
58  continue;
59 
60  if( graph_pc_termIsNonLeafTerm(g, k) )
61  {
63  }
64  }
65 }
66 
67 
68 /** gets original edge costs, when in extended mode */
69 static
71  SCIP* scip, /**< SCIP data structure */
72  GRAPH* graph /**< the graph */
73 )
74 {
75  const int nedges = graph->edges;
76  const SCIP_Real* const cost_org = graph->cost_org_pc;
77  SCIP_Real* const RESTRICT edgecosts = graph->cost;
78 
79  assert(scip && edgecosts && cost_org);
80  assert(graph->extended && graph_pc_isPcMw(graph));
81 
82  assert(graph_pc_transOrgAreConistent(scip, graph, TRUE));
83 
84  for( int e = 0; e < nedges; ++e )
85  {
86  assert(graph_edge_isBlocked(graph, e) == EQ(edgecosts[e], BLOCKED_MINOR) || EQ(edgecosts[e], BLOCKED));
87 
88  if( !EQ(edgecosts[e], BLOCKED_MINOR) && !EQ(edgecosts[e], BLOCKED) )
89  edgecosts[e] = cost_org[e];
90  }
91 }
92 
93 
94 /** gets original edge costs, when in extended mode and in presolving state */
95 static
97  SCIP* scip, /**< SCIP data structure */
98  GRAPH* graph /**< the graph */
99 )
100 {
101  const int nedges = graph->edges;
102  const SCIP_Real* const cost_org = graph->cost_org_pc;
103  SCIP_Real* const RESTRICT edgecosts = graph->cost;
104 
105  assert(scip && edgecosts && cost_org);
106  assert(graph->extended && graph_pc_isPcMw(graph));
107 
108  assert(graph_pc_transOrgAreConistent(scip, graph, TRUE));
109 
110 #ifndef NDEBUG
111  for( int e = 0; e < nedges; ++e )
112  {
113  assert(!graph_edge_isBlocked(graph, e));
114  }
115 #endif
116  BMScopyMemoryArray(edgecosts, cost_org, nedges);
117 }
118 
119 
120 
121 /* deletes dummy terminal to given node and edge from pseudo-root (if existent).
122  * Furthermore, makes i a non-terminal, if makeNonTerminal is set */
123 static
125  SCIP* scip, /**< SCIP data structure */
126  GRAPH* g, /**< graph data structure */
127  int i, /**< index of the terminal */
128  SCIP_Bool makeNonTerminal /**< make i a non-terminal?*/
129  )
130 {
131  int e;
132  int dummyterm;
133  const SCIP_Bool has_pseudoroot = !graph_pc_isRootedPcMw(g);
134 
135  assert(g && scip);
136  assert(g->term2edge && g->prize);
137  assert((!g->extended && Is_term(g->term[i])) || (g->extended && Is_pseudoTerm(g->term[i])));
138  assert(!graph_pc_knotIsFixedTerm(g, i));
139  assert(i != g->source);
140 
141  /* get edge from i to its artificial terminal */
142  e = g->term2edge[i];
143  assert(e >= 0);
144 
145  dummyterm = g->head[e];
146  assert(dummyterm != g->source);
147  assert(g->grad[dummyterm] == 2);
148 
149  /* delete edge and unmark artificial terminal */
150  graph_knot_chg(g, dummyterm, STP_TERM_NONE);
151  graph_edge_del(scip, g, e, TRUE);
152  g->term2edge[dummyterm] = TERM2EDGE_NOTERM;
153 
154  /* delete remaining incident edge of artificial terminal */
155  e = g->inpbeg[dummyterm];
156 
157  assert(e != EAT_LAST);
158  assert(g->source == g->tail[e]);
159  assert(SCIPisEQ(scip, g->prize[i], g->cost[e]));
160 
161 #ifndef NDEBUG
162  g->cost[e] = 0.0;
163 #endif
164 
165  graph_edge_del(scip, g, e, TRUE);
166 
167  assert(g->inpbeg[dummyterm] == EAT_LAST && g->grad[dummyterm] == 0);
168 
169  if( has_pseudoroot )
170  {
171  const int edgeRoot2i = graph_pc_getRoot2PtermEdge(g, i);
172 
173 #ifndef NDEBUG
174  g->cost[edgeRoot2i] = 0.0;
175 #endif
176  assert(SCIPisEQ(scip, g->cost[edgeRoot2i], 0.0));
177  graph_edge_del(scip, g, edgeRoot2i, TRUE);
178  }
179 
180  if( makeNonTerminal )
181  {
183  g->term2edge[i] = TERM2EDGE_NOTERM;
184  g->prize[i] = 0.0;
185  }
186 }
187 
188 /** is given terminal the last terminal? */
189 static inline
191  GRAPH* g, /**< the graph */
192  int t /**< terminal */
193 )
194 {
195  assert(graph_pc_isPcMw(g));
196  assert(g && g->term2edge);
197  assert(!g->extended);
198  assert(Is_term(g->term[t]));
199  assert(!graph_pc_knotIsFixedTerm(g, t) && !graph_pc_knotIsNonLeafTerm(g, t));
200 
201  if( !graph_pc_isRootedPcMw(g) && g->grad[g->source] <= 2 )
202  {
203  return TRUE;
204  }
205 
206  return FALSE;
207 }
208 
209 
210 
211 /** changes incident edges after prize of node was changed */
212 static inline
214  GRAPH* g, /**< the graph */
215  int node /**< the node */
216  )
217 {
218  const SCIP_Real newprize = g->prize[node];
219  const SCIP_Real incost = (newprize > 0.0) ? 0.0 : -newprize;
220 
221  assert(!graph_pc_knotIsDummyTerm(g, node));
222 
223  for( int e = g->inpbeg[node]; e >= 0; e = g->ieat[e] )
224  {
225  const int tail = g->tail[e];
226  if( !graph_pc_knotIsDummyTerm(g, tail) )
227  {
228  g->cost[e] = incost;
229  }
230  }
231 }
232 
233 
234 /** contract an edge of rooted prize-collecting Steiner tree problem or maximum-weight connected subgraph problem
235  * such that this edge is incident to least one fixed terminal */
236 static
238  SCIP* scip, /**< SCIP data structure */
239  GRAPH* g, /**< the graph */
240  int* solnode, /**< solution nodes or NULL */
241  int t, /**< tail node to be contracted (surviving node) */
242  int s, /**< head node to be contracted */
243  int ets /**< edge from t to s */
244 )
245 {
246  assert(ets >= 0);
247  assert(g->tail[ets] == t && g->head[ets] == s);
248  assert(graph_pc_isRootedPcMw(g));
249  assert(!g->extended);
250  assert(graph_pc_knotIsFixedTerm(g, s) || graph_pc_knotIsFixedTerm(g, t));
251 
252  SCIP_CALL(graph_fixed_moveNodePc(scip, s, g));
253  SCIP_CALL(graph_fixed_addEdge(scip, ets, g));
254 
255  if( !graph_pc_knotIsFixedTerm(g, s) )
256  {
257  assert(graph_pc_knotIsFixedTerm(g, t));
258 
259  if( Is_term(g->term[s]) )
260  graph_pc_termToNonTerm(scip, g, s);
261  }
262  else
263  {
264  if( !graph_pc_knotIsFixedTerm(g, t) )
265  {
266  assert(!graph_pc_isMw(g)); // currently does not work due to offset issue in graph_pc_knotTofixedTerm!
267  assert(g->source != t);
268  assert(SCIPisEQ(scip, g->prize[s], FARAWAY));
269 
270  graph_pc_knotToFixedTerm(scip, g, t, NULL);
271  }
272 
273  graph_pc_fixedTermToNonTerm(scip, g, s);
274  }
275 
276  /* contract s into t */
277  SCIP_CALL(graph_knot_contract(scip, g, solnode, t, s));
278 
279  return SCIP_OKAY;
280 }
281 
282 
283 
284 /** contract an edge of (rooted) prize-collecting Steiner tree problem or maximum-weight connected subgraph problem
285  * such that this edge is NOT incident to least one fixed terminal */
286 static
288  SCIP* scip, /**< SCIP data structure */
289  GRAPH* g, /**< the graph */
290  int* solnode, /**< solution nodes or NULL */
291  int t, /**< tail node to be contracted (surviving node) */
292  int s, /**< head node to be contracted */
293  int ets, /**< edge from t to s */
294  int term4offset /**< terminal to add offset to */
295 )
296 {
297  const SCIP_Bool isMw = graph_pc_isMw(g);
298 
299  assert(ets >= 0);
300  assert(g->tail[ets] == t && g->head[ets] == s);
301  assert(Is_term(g->term[term4offset]));
302  assert(!graph_pc_knotIsFixedTerm(g, s) && !graph_pc_knotIsFixedTerm(g, t));
303 
304  SCIP_CALL( graph_pc_contractNodeAncestors(scip, g, t, s, ets) );
305 
306  /* are both end-points of the edge to be contracted terminals? */
307  if( Is_term(g->term[t]) && Is_term(g->term[s]) )
308  {
309  const SCIP_Real prize_s = g->prize[s];
310 
311  graph_pc_termToNonTerm(scip, g, s);
312 
313  if( !graph_pc_knotIsFixedTerm(g, term4offset) )
314  graph_pc_subtractPrize(scip, g, g->cost[ets] - prize_s, term4offset);
315  }
316  else
317  {
318  if( !graph_pc_knotIsFixedTerm(g, term4offset) )
319  {
320  if( isMw )
321  graph_pc_subtractPrize(scip, g, -(g->prize[s]), term4offset);
322  else
323  graph_pc_subtractPrize(scip, g, g->cost[ets], term4offset);
324  }
325 
326  if( Is_term(g->term[s]) )
327  graph_pc_termToNonTerm(scip, g, s);
328  }
329 
330  /* contract s into t */
331  SCIP_CALL( graph_knot_contract(scip, g, solnode, t, s) );
332 
333  if( isMw )
334  {
335  if( Is_term(g->term[term4offset]) && LE(g->prize[term4offset], 0.0) )
336  graph_pc_termToNonTerm(scip, g, t);
337 
338  return SCIP_OKAY;
339  }
340 
341  if( Is_term(g->term[t]) )
342  {
343  if( graph_pc_evalTermIsNonLeaf(scip, g, t) || g->grad[t] == 0 )
344  {
345  if( g->term2edge[t] != TERM2EDGE_NONLEAFTERM )
346  {
347  assert(g->term2edge[t] >= 0);
348 
349  graph_pc_termToNonLeafTerm(scip, g, t, FALSE);
350  }
351  }
352  else
353  {
354  assert(TERM2EDGE_NONLEAFTERM != g->term2edge[t] && "currently not supported");
355  /* NOTE: this case could happen, but not with current contraction calls; would need to keep edges for extension in this case */
356  }
357  }
358  else
359  {
360  assert(g->term2edge[t] == TERM2EDGE_NOTERM);
361  }
362 
363  return SCIP_OKAY;
364 }
365 
366 
367 
368 
369 /** initializes biased data */
370 static
372  const GRAPH* graph, /**< graph data structure */
373  SCIP_Real* RESTRICT costbiased, /**< biased costs */
374  SCIP_Real* RESTRICT prizebiased /**< biased prizes */
375 )
376 {
377  const int nnodes = graph_get_nNodes(graph);
378  const SCIP_Bool isRpc = graph_pc_isRootedPcMw(graph);
379  const int root = graph->source;
380 
381  assert(graph_pc_isPc(graph));
382 
383  BMScopyMemoryArray(costbiased, graph->cost, graph->edges);
384 
385  for( int k = 0; k < nnodes; k++ )
386  {
387  if( Is_pseudoTerm(graph->term[k]) && graph->grad[k] != 0 )
388  {
389  SCIP_Real mincost = FARAWAY;
390 
391  /* get the minimum cost among all incoming arcs */
392  for( int e = graph->inpbeg[k]; e != EAT_LAST; e = graph->ieat[e] )
393  {
394  const int tail = graph->tail[e];
395 
396  if( !isRpc && tail == root )
397  continue;
398 
399  if( graph->cost[e] < mincost )
400  {
401  assert(!Is_term(graph->term[tail]) || graph_pc_knotIsFixedTerm(graph, tail));
402  assert(!graph_pc_knotIsDummyTerm(graph, tail));
403  assert(tail != root || isRpc);
404 
405  mincost = graph->cost[e];
406  }
407  }
408 
409  mincost = MIN(mincost, graph->prize[k]);
410 
411  /** apply the minimum */
412  for( int e = graph->inpbeg[k]; e != EAT_LAST; e = graph->ieat[e] )
413  {
414  const int tail = graph->tail[e];
415 
416  if( !isRpc && tail == root )
417  continue;
418 
419  if( GE(graph->cost[e], FARAWAY) )
420  {
421  assert(Is_term(graph->term[tail]));
422  continue;
423  }
424 
425  assert(!Is_term(graph->term[tail]) || graph_pc_knotIsFixedTerm(graph, tail));
426  assert(!graph_pc_knotIsDummyTerm(graph, tail));
427 
428  costbiased[e] -= mincost;
429  assert(GE(costbiased[e], 0.0));
430  }
431 
432  prizebiased[k] = graph->prize[k] - mincost;
433  assert(GE(prizebiased[k], 0.0));
434  }
435  else
436  {
437  if( isRpc && graph_pc_knotIsFixedTerm(graph, k) )
438  prizebiased[k] = graph->prize[k];
439  else
440  prizebiased[k] = 0.0;
441  }
442  }
443 }
444 
445 
446 /** initializes biased data */
447 static
449  const GRAPH* graph, /**< graph data structure */
450  SCIP_Real* RESTRICT costbiased, /**< biased costs */
451  SCIP_Real* RESTRICT prizebiased /**< biased prizes */
452 )
453 {
454  const int nnodes = graph_get_nNodes(graph);
455  const SCIP_Bool isRmw = graph_pc_isRootedPcMw(graph);
456  const int root = graph->source;
457 
458  assert(graph_pc_isMw(graph));
459 
460  BMScopyMemoryArray(costbiased, graph->cost, graph->edges);
461 
462  for( int k = 0; k < nnodes; k++ )
463  {
464  if( Is_pseudoTerm(graph->term[k]) && graph->grad[k] != 0 )
465  {
466  SCIP_Real mincost = FARAWAY;
467 
468  /* get the minimum cost among all outgoing arcs */
469  for( int e = graph->outbeg[k]; e != EAT_LAST; e = graph->oeat[e] )
470  {
471  const int head = graph->head[e];
472 
473  if( graph_pc_knotIsDummyTerm(graph, head) )
474  continue;
475 
476  if( !isRmw && head == root )
477  continue;
478 
479  if( graph->cost[e] < mincost )
480  {
481  assert(head != root || isRmw);
482  mincost = graph->cost[e];
483  }
484  }
485 
486  mincost = MIN(mincost, graph->prize[k]);
487 
488  /** apply the minimum */
489  for( int e = graph->inpbeg[k]; e != EAT_LAST; e = graph->ieat[e] )
490  {
491  const int tail = graph->tail[e];
492 
493  if( !isRmw && tail == root )
494  continue;
495 
496  assert(EQ(costbiased[e], graph->cost[e]));
497 
498  if( GE(costbiased[e], FARAWAY) )
499  {
500  assert(Is_term(graph->term[tail]));
501  continue;
502  }
503 
504  assert(!graph_pc_knotIsDummyTerm(graph, tail));
505  assert(GE(mincost, 0.0) && LT(mincost, FARAWAY));
506  assert(EQ(costbiased[e], 0.0));
507 
508  costbiased[e] = -mincost;
509  }
510 
511  prizebiased[k] = graph->prize[k] - mincost;
512  assert(GE(prizebiased[k], 0.0));
513  }
514  else
515  {
516  if( isRmw && graph_pc_knotIsFixedTerm(graph, k) )
517  {
518  assert(EQ(graph->prize[k], FARAWAY));
519  prizebiased[k] = FARAWAY;
520  }
521  else
522  prizebiased[k] = 0.0;
523  }
524  }
525 }
526 
527 
528 /*
529  * Interface methods
530  */
531 
532 
533 #if 0
534 /** transforms an MWCSP to an SAP */
535 SCIP_RETCODE graph_MwcsToSap(
536  SCIP* scip, /**< SCIP data structure */
537  GRAPH* graph, /**< the graph */
538  SCIP_Real* maxweights /**< array containing the weight of each node */
539  )
540 {
541  int e;
542  int i;
543  int nnodes;
544  int nterms = 0;
545 
546  assert(maxweights != NULL);
547  assert(scip != NULL);
548  assert(graph != NULL);
549  assert(graph->cost != NULL);
550  assert(graph->terms == 0);
551 
552  nnodes = graph->knots;
553 
554  /* count number of terminals, modify incoming edges for non-terminals */
555  for( i = 0; i < nnodes; i++ )
556  {
557  if( SCIPisLT(scip, maxweights[i], 0.0) )
558  {
559  for( e = graph->inpbeg[i]; e != EAT_LAST; e = graph->ieat[e] )
560  {
561  graph->cost[e] -= maxweights[i];
562  }
563  }
564  else
565  {
566  graph_knot_chg(graph, i, 0);
567  nterms++;
568  }
569  }
570  nterms = 0;
571  for( i = 0; i < nnodes; i++ )
572  {
573  graph->prize[i] = maxweights[i];
574  if( Is_term(graph->term[i]) )
575  {
576  assert(SCIPisGE(scip, maxweights[i], 0.0));
577  nterms++;
578  }
579  else
580  {
581  assert(SCIPisLT(scip, maxweights[i], 0.0));
582  }
583  }
584  assert(nterms == graph->terms);
585  graph->stp_type = STP_MWCSP;
586 
587  SCIP_CALL( graph_PcToSap(scip, graph) );
588  assert(graph->stp_type == STP_MWCSP);
589  return SCIP_OKAY;
590 }
591 
592 
593 /** alters the graph for prize collecting problems */
594 SCIP_RETCODE graph_PcToSap(
595  SCIP* scip, /**< SCIP data structure */
596  GRAPH* graph /**< the graph */
597  )
598 {
599  SCIP_Real* prize;
600  int k;
601  int root;
602  int node;
603  int nnodes;
604  int nterms;
605  int pseudoroot;
606 
607  assert(graph != NULL);
608  assert(graph->prize != NULL);
609  assert(graph->knots == graph->ksize);
610  assert(graph->edges == graph->esize);
611 
612  prize = graph->prize;
613  nnodes = graph->knots;
614  nterms = graph->terms;
615  graph->norgmodelknots = nnodes;
616  graph->norgmodeledges = graph->edges;
617 
618  /* for each terminal, except for the root, one node and three edges (i.e. six arcs) are to be added */
619  SCIP_CALL( graph_resize(scip, graph, (graph->ksize + graph->terms + 2), (graph->esize + graph->terms * 8) , -1) );
620 
621  /* create a new nodes */
622  for( k = 0; k < nterms; ++k )
623  graph_knot_add(graph, -1);
624 
625  /* new pseudo-root */
626  pseudoroot = graph->knots;
627  graph_knot_add(graph, -1);
628 
629  /* new root */
630  root = graph->knots;
631  graph_knot_add(graph, 0);
632 
633  nterms = 0;
634  for( k = 0; k < nnodes; ++k )
635  {
636  /* is the kth node a terminal other than the root? */
637  if( Is_term(graph->term[k]) )
638  {
639  /* the copied node */
640  node = nnodes + nterms;
641  nterms++;
642 
643  /* switch the terminal property, mark k */
644  graph_knot_chg(graph, k, -2);
645  graph_knot_chg(graph, node, 0);
646  assert(SCIPisGE(scip, prize[k], 0.0));
647 
648  /* add one edge going from the root to the 'copied' terminal and one going from the former terminal to its copy */
649  graph_edge_add(scip, graph, root, k, BLOCKED, FARAWAY);
650  graph_edge_add(scip, graph, pseudoroot, node, prize[k], FARAWAY);
651  graph_edge_add(scip, graph, k, node, 0.0, FARAWAY);
652  graph_edge_add(scip, graph, k, pseudoroot, 0.0, FARAWAY);
653  }
654  else if( graph->stp_type != STP_MWCSP )
655  {
656  prize[k] = 0;
657  }
658  }
659  graph->source = root;
660  graph->extended = TRUE;
661  assert((nterms + 1) == graph->terms);
662  if( graph->stp_type != STP_MWCSP )
663  graph->stp_type = STP_PCSPG;
664 
665  return SCIP_OKAY;
666 }
667 #endif
668 
669 
670 /** shift costs of non-leaf terminals (call right after transformation to extended has been performed) */
672  SCIP* scip, /**< SCIP */
673  GRAPH* g /**< the graph */
674 )
675 {
676  const int nnodes = g->knots;
677  SCIP_Real* const cost = g->cost;
678 
679 #ifndef NDEBUG
680  assert(g->cost_org_pc);
681  assert(graph_pc_isPc(g));
682  assert(g->extended);
683 
684  for( int e = 0; e < g->edges; e++ )
685  {
686  if( g->oeat[e] == EAT_LAST )
687  continue;
688 
689  assert(SCIPisEQ(scip, cost[e], cost[flipedge(e)]) || SCIPisGE(scip, cost[e], FARAWAY) || SCIPisGE(scip, cost[flipedge(e)], FARAWAY));
690  }
691 #endif
692 
693  for( int k = 0; k < nnodes; k++ )
694  {
695  if( Is_nonleafTerm(g->term[k]) )
696  {
697  const SCIP_Real prize = g->prize[k];
698 
699  assert(SCIPisGE(scip, prize, 0.0));
700 
701  for( int e = g->inpbeg[k]; e != EAT_LAST; e = g->ieat[e] )
702  {
703  assert(SCIPisLT(scip, cost[e], FARAWAY));
704  assert(SCIPisLT(scip, cost[flipedge(e)], FARAWAY));
705 
706  if( graph_edge_isBlocked(g, e) )
707  continue;
708 
709  cost[e] -= prize;
710  assert(SCIPisGE(scip, cost[e], 0.0));
711 
712  if( cost[e] < 0.0 )
713  cost[e] = 0.0;
714  }
715  }
716  }
717 }
718 
719 
720 /** initializes term2edge array */
722  SCIP* scip, /**< SCIP data structure */
723  GRAPH* g, /**< the graph */
724  int size /**< the size */
725  )
726 {
727  assert(scip && g);
728  assert(!g->term2edge);
729  assert(size > 0);
730 
731  SCIP_CALL(SCIPallocMemoryArray(scip, &(g->term2edge), size));
732 
733  for( int i = 0; i < size; i++ )
734  g->term2edge[i] = TERM2EDGE_NOTERM;
735 
736  return SCIP_OKAY;
737 }
738 
739 
740 /** allocates prizes array for PC and MW problems */
742  SCIP* scip, /**< SCIP data structure */
743  GRAPH* g, /**< the graph */
744  int sizeprize /**< size of prize array to allocate (or -1) */
745  )
746 {
747  assert(scip != NULL);
748  assert(g != NULL);
749  assert(NULL == g->prize);
750  assert(sizeprize > 0);
751 
752  SCIP_CALL( SCIPallocMemoryArray(scip, &(g->prize), sizeprize) );
753 
754  for( int i = 0; i < sizeprize; i++ )
755  g->prize[i] = -FARAWAY;
756 
757  return SCIP_OKAY;
758 }
759 
760 
761 // todo this method should be static once subgraph method is finished
762 /** allocates and initializes arrays for subgraph PC/MW */
764  SCIP* scip, /**< SCIP data structure */
765  GRAPH* subgraph /**< the subgraph */
766  )
767 {
768  int ksize;
769  int esize;
770 
771  assert(scip && subgraph);
772  assert(graph_pc_isPcMw(subgraph));
773 
774  ksize = subgraph->ksize;
775  esize = subgraph->esize;
776 
777  assert(ksize > 0 && ksize >= subgraph->knots);
778  assert(esize > 0 && esize >= subgraph->edges);
779 
780  SCIP_CALL( graph_pc_initPrizes(scip, subgraph, ksize) );
781  SCIP_CALL( graph_pc_initTerm2Edge(scip, subgraph, ksize) );
782 
783  assert(!subgraph->cost_org_pc);
784 
785  if( graph_pc_isPc(subgraph) )
786  {
787  SCIP_CALL( SCIPallocMemoryArray(scip, &(subgraph->cost_org_pc), esize) );
788  }
789 
790  return SCIP_OKAY;
791 }
792 
793 // todo this method should be static once subgraph method is finished
794 /** allocates and initializes arrays for subgraph PC/MW */
796  SCIP* scip, /**< SCIP data structure */
797  GRAPH* subgraph /**< the subgraph */
798  )
799 {
800  if( graph_pc_isPcMw(subgraph) )
801  {
802  assert(scip);
803  assert(subgraph->term2edge && subgraph->prize);
804  assert(subgraph->extended);
805  assert(subgraph->source >= 0);
806  assert(!graph_pc_isPcMw(subgraph) || Is_term(subgraph->term[subgraph->source]));
807  assert((graph_pc_isPc(subgraph)) == (subgraph->cost_org_pc != NULL));
808  }
809 
810  return SCIP_OKAY;
811 }
812 
813 
814 /** changes graph of PC and MW problems needed for presolving routines */
816  SCIP* scip, /**< SCIP data structure */
817  GRAPH* g /**< the graph */
818  )
819 {
820  int prev;
821  const int root = g->source;
822  const int nedges = g->edges;
823 
824  if( g->stp_type == STP_RPCSPG )
825  return SCIP_OKAY;
826 
827  assert(scip != NULL && g != NULL);
828  assert(g->rootedgeprevs == NULL);
829  assert(nedges > 0 && g->grad[root] > 0);
830 
831  SCIP_CALL( SCIPallocMemoryArray(scip, &(g->rootedgeprevs), nedges) );
832 
833  for( int e = 0; e < nedges; e++ )
834  g->rootedgeprevs[e] = -1;
835 
836  prev = g->outbeg[root];
837  assert(prev != EAT_LAST);
838 
839  for( int e = g->oeat[prev]; e != EAT_LAST; e = g->oeat[e] )
840  {
841  g->rootedgeprevs[e] = prev;
842  prev = e;
843  }
844 
845  prev = g->inpbeg[root];
846  assert(prev != EAT_LAST);
847 
848  for( int e = g->ieat[prev]; e != EAT_LAST; e = g->ieat[e] )
849  {
850  g->rootedgeprevs[e] = prev;
851  prev = e;
852  }
853 
854  return SCIP_OKAY;
855 }
856 
857 /** changes graph of PC and MW problems needed after exiting presolving routines */
859  SCIP* scip, /**< SCIP data structure */
860  GRAPH* g /**< the graph */
861  )
862 {
863  assert(scip != NULL && g != NULL);
864 
865  if( g->stp_type == STP_RPCSPG )
866  return;
867 
868  assert(g->rootedgeprevs != NULL);
869 
870  SCIPfreeMemoryArray(scip, &(g->rootedgeprevs));
871 }
872 
873 /** checks consistency of term2edge array */
875  SCIP* scip, /**< SCIP data structure */
876  const GRAPH* g /**< the graph */
877 )
878 {
879  const int root = g->source;
880  const SCIP_Bool rooted = graph_pc_isRootedPcMw(g);
881  const SCIP_Bool isExtended = g->extended;
882 
883  assert(scip && g && g->term2edge);
884  assert(graph_pc_isPcMw(g));
885 
886  if( g->term2edge[root] != TERM2EDGE_FIXEDTERM )
887  {
888  SCIPdebugMessage("term2edge root consistency \n");
889  return FALSE;
890  }
891 
892  for( int i = 0; i < g->knots; i++ )
893  {
894  if( rooted && graph_pc_knotIsFixedTerm(g, i) && !SCIPisEQ(scip, g->prize[i], FARAWAY) )
895  {
896  SCIPdebugMessage("inconsistent prize for fixed terminal %d \n", i);
897  return FALSE;
898  }
899 
900  if( i == root )
901  continue;
902 
903  if( !isExtended && Is_term(g->term[i]) && graph_pc_realDegree(g, i, graph_pc_knotIsFixedTerm(g, i)) )
904  {
905  const SCIP_Bool isNonLeaf = (g->term2edge[i] == TERM2EDGE_NONLEAFTERM);
906 
907  if( isNonLeaf )
908  {
909  const SCIP_Bool isNonLeaf_evaluate = graph_pc_evalTermIsNonLeaf(scip, g, i);
910  if( !isNonLeaf_evaluate )
911  {
912  SCIPdebugMessage("term2edge consistency fail0 %d \n", i);
913  graph_knot_printInfo(g, i);
914  printf("isNonLeaf=%ud isNonLeaf_evaluate=%ud \n", isNonLeaf, isNonLeaf_evaluate);
915 
916  return FALSE;
917  }
918  }
919  }
920 
921  if( Is_anyTerm(g->term[i])
922  && !graph_pc_knotIsFixedTerm(g, i)
924  && g->term2edge[i] < 0 )
925  {
926  SCIPdebugMessage("term2edge consistency fail1 %d \n", i);
927  return FALSE;
928  }
929 
930  if( !Is_anyTerm(g->term[i]) && g->term2edge[i] != TERM2EDGE_NOTERM )
931  {
932  SCIPdebugMessage("term2edge consistency fail2 %d \n", i);
933  return FALSE;
934  }
935 
936  if( isExtended && Is_nonleafTerm(g->term[i]) && g->term2edge[i] != TERM2EDGE_NONLEAFTERM )
937  {
938  SCIPdebugMessage("term2edge consistency fail2b %d \n", i);
939  return FALSE;
940  }
941 
942  if( !isExtended && g->term2edge[i] == TERM2EDGE_NONLEAFTERM && !Is_term(g->term[i]) )
943  {
944  SCIPdebugMessage("term2edge consistency fail2c %d \n", i);
945  return FALSE;
946  }
947 
948  if( Is_pseudoTerm(g->term[i]) )
949  {
950  int k = -1;
951  int e;
952 
953  for( e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
954  {
955  k = g->head[e];
956  if( Is_term(g->term[k]) && !graph_pc_knotIsFixedTerm(g, k) )
957  break;
958  }
959  assert(e != EAT_LAST);
960  assert(k >= 0);
961 
962  if( g->term2edge[i] != e )
963  {
964  SCIPdebugMessage("term2edge consistency fail3 %d \n", i);
965  return FALSE;
966  }
967 
968  if( g->term2edge[k] != flipedge(e) )
969  {
970  SCIPdebugMessage("term2edge consistency fail4 %d \n", i);
971  return FALSE;
972  }
973  }
974  }
975  return TRUE;
976 }
977 
978 
979 /** transformed problem consistent to original one? Call only for extended graph */
981  SCIP* scip, /**< SCIP data structure */
982  const GRAPH* graph, /**< the graph */
983  SCIP_Bool verbose /**< be verbose? */
984  )
985 {
986  const int nedges = graph->edges;
987  const SCIP_Real* const cost = graph->cost;
988  const SCIP_Real* const cost_org = graph->cost_org_pc;
989 
990  assert(graph->cost_org_pc && graph->prize);
991  assert(graph->extended);
992  assert(graph_pc_isPcMw(graph));
993 
994  for( int e = 0; e < nedges; e++ )
995  {
996  int head;
997 
998  if( graph->oeat[e] == EAT_FREE )
999  continue;
1000 
1001  if( graph_edge_isBlocked(graph, e) )
1002  continue;
1003 
1004  head = graph->head[e];
1005 
1006  if( Is_nonleafTerm(graph->term[head]) )
1007  {
1008  const SCIP_Real prize = graph->prize[head];
1009  assert(SCIPisGE(scip, prize, 0.0));
1010  assert(SCIPisLT(scip, cost_org[e], FARAWAY));
1011 
1012  if( !SCIPisEQ(scip, cost_org[e], cost[e] + prize) )
1013  {
1014  if( verbose )
1015  {
1016  graph_edge_printInfo(graph, e);
1017  printf("cost_org=%f cost=%f prize=%f \n", cost_org[e], cost[e],
1018  prize);
1019  }
1020 
1021  return FALSE;
1022  }
1023  }
1024  else
1025  {
1026  if( !SCIPisEQ(scip, cost_org[e], cost[e]) )
1027  {
1028  if( verbose )
1029  {
1030  graph_edge_printInfo(graph, e);
1031  printf("cost_org=%f cost=%f \n", cost_org[e], cost[e]);
1032  }
1033 
1034  return FALSE;
1035  }
1036  }
1037  }
1038 
1039  return TRUE;
1040 }
1041 
1042 
1043 /** change property of node to be a non-terminal; prize is not changed! */
1045  GRAPH* g, /**< the graph */
1046  int node /**< node to be changed */
1047  )
1048 {
1049  assert(g);
1050  assert(node >= 0 && node < g->knots);
1051 
1052  assert(graph_pc_isPcMw(g));
1053  assert(g->term2edge);
1054 
1055  g->term2edge[node] = TERM2EDGE_NOTERM;
1056 
1057  graph_knot_chg(g, node, STP_TERM_NONE);
1058 }
1059 
1060 
1061 /** change property of node to be a terminal; prize is changed, but no edges are deleted! */
1063  GRAPH* g, /**< the graph */
1064  int node /**< node to be changed */
1065  )
1066 {
1067  assert(g);
1068  assert(node >= 0 && node < g->knots);
1069  assert(g->term2edge && g->prize);
1070 
1071  g->term2edge[node] = TERM2EDGE_FIXEDTERM;
1072  g->prize[node] = FARAWAY;
1073 
1074  graph_knot_chg(g, node, STP_TERM);
1075 }
1076 
1077 
1078 /** Makes a node a fixed terminal */
1080  SCIP* scip, /**< SCIP data structure */
1081  GRAPH* g, /**< graph data structure */
1082  int node, /**< node */
1083  SCIP_Real* offset /**< offset needed for RMW, or NULL */
1084  )
1085 {
1086  const SCIP_Bool isMw = graph_pc_isMw(g);
1087  assert(scip);
1088  assert(g->prize && g->term2edge);
1089  assert(node != g->source);
1090  assert(!graph_pc_knotIsFixedTerm(g, node));
1091  assert(graph_pc_isRootedPcMw(g));
1092 
1093  if( Is_term(g->term[node]) )
1094  {
1095  assert(!g->extended);
1096 
1097  if( isMw || !graph_pc_termIsNonLeafTerm(g, node) )
1098  termDeleteExtension(scip, g, node, TRUE);
1099  }
1100  else if( Is_pseudoTerm(g->term[node]) )
1101  {
1102  assert(g->extended);
1103 
1104  termDeleteExtension(scip, g, node, TRUE);
1105  }
1106 
1107  graph_knot_chg(g, node, STP_TERM_NONE);
1108  g->term2edge[node] = TERM2EDGE_NOTERM;
1109 
1110  graph_pc_nonTermToFixedTerm(g, node, offset);
1111 }
1112 
1113 
1114 /** makes a non-terminal node a fixed terminal */
1116  GRAPH* g, /**< graph data structure */
1117  int node, /**< node */
1118  SCIP_Real* offset /**< offset needed for RMW, or NULL */
1119  )
1120 {
1121  const SCIP_Bool isMw = graph_pc_isMw(g);
1122  assert(g->prize && g->term2edge);
1123  assert(!graph_pc_knotIsFixedTerm(g, node));
1124  assert(graph_pc_isRootedPcMw(g));
1125  assert(!Is_term(g->term[node]));
1126  assert(!Is_pseudoTerm(g->term[node]));
1127  assert(!graph_pc_knotIsDummyTerm(g, node));
1128  assert(g->term2edge[node] == TERM2EDGE_NOTERM);
1129  assert(g->term[node] == STP_TERM_NONE);
1130 
1131  if( isMw && g->grad[node] > 0 )
1132  {
1133  const SCIP_Real incost = g->cost[g->inpbeg[node]];
1134 
1135  if( offset != NULL && node != g->source )
1136  {
1137  (*offset) += incost;
1138  }
1139 
1140  for( int e = g->inpbeg[node]; e != EAT_LAST; e = g->ieat[e] )
1141  {
1142  assert(EQ(g->cost[e], incost));
1143 
1144  g->cost[e] = 0.0;
1145  }
1146  }
1147 
1148  graph_knot_chg(g, node, STP_TERM);
1149  g->prize[node] = FARAWAY;
1150  g->term2edge[node] = TERM2EDGE_FIXEDTERM;
1151 
1152  assert(graph_pc_knotIsFixedTerm(g, node));
1153 }
1154 
1155 
1156 /** Makes a non-fixed terminal a non-terminal.
1157  * Also sets the prize to 0.0 for (R)PC! */
1159  SCIP* scip, /**< SCIP data structure */
1160  GRAPH* g, /**< graph data structure */
1161  int term /**< terminal to be unfixed */
1162  )
1163 {
1164  assert(graph_pc_isPcMw(g));
1165  assert(term != g->source);
1166  assert(!graph_pc_knotIsFixedTerm(g, term));
1167  assert(!g->extended);
1168  assert(Is_anyTerm(g->term[term]));
1169 
1170  if( graph_pc_isPc(g) )
1171  {
1172  if( !graph_pc_termIsNonLeafTerm(g, term) )
1173  termDeleteExtension(scip, g, term, FALSE);
1174 
1175  g->prize[term] = 0.0;
1176  }
1177  else
1178  {
1179  termDeleteExtension(scip, g, term, FALSE);
1180  }
1181 
1183 
1184  assert(!Is_anyTerm(g->term[term]));
1185 }
1186 
1187 
1188 /** Makes a fixed terminal a non-terminal */
1190  SCIP* scip, /**< SCIP data structure */
1191  GRAPH* g, /**< graph data structure */
1192  int term /**< terminal to be unfixed */
1193  )
1194 {
1195  assert(graph_pc_isPcMw(g));
1196  assert(term != g->source);
1197  assert(graph_pc_knotIsFixedTerm(g, term));
1198 
1199  graph_knot_chg(g, term, STP_TERM_NONE);
1200  g->term2edge[term] = TERM2EDGE_NOTERM;
1201  g->prize[term] = 0.0;
1202 
1203  assert(!graph_pc_knotIsFixedTerm(g, term));
1204  assert(!Is_anyTerm(g->term[term]));
1205 }
1206 
1207 
1208 /** change property of (non-fixed) terminal to be a non-leaf terminal
1209  * NOTE: if force == FALSE, then nothing is done if term is the last terminal */
1211  SCIP* scip, /**< SCIP data structure */
1212  GRAPH* g, /**< the graph */
1213  int term, /**< terminal to be changed */
1214  SCIP_Bool force /**< force the transformation? Should usually be FALSE */
1215  )
1216 {
1217  assert(graph_pc_isPcMw(g));
1218  assert(g && g->term2edge);
1219  assert(!g->extended);
1220  assert(Is_term(g->term[term]));
1221  assert(!graph_pc_knotIsFixedTerm(g, term) && !graph_pc_knotIsNonLeafTerm(g, term));
1222 
1223  if( force || !isLastTerm(g, term) )
1224  {
1225  termDeleteExtension(scip, g, term, FALSE);
1226  g->term2edge[term] = TERM2EDGE_NONLEAFTERM;
1227  }
1228 }
1229 
1230 
1231 /** is the edge part of the extended graph? */
1233  const GRAPH* g, /**< the graph */
1234  int edge /**< edge to be checked */
1235  )
1236 {
1237  const int tail = g->tail[edge];
1238  const int head = g->head[edge];
1239 
1240  assert(graph_pc_isPcMw(g));
1241  assert(edge >= 0 && edge < g->edges);
1242 
1243  if( graph_pc_knotIsDummyTerm(g, tail) || graph_pc_knotIsDummyTerm(g, head) )
1244  {
1245  assert(EQ(g->cost[edge], FARAWAY) || EQ(g->cost[flipedge(edge)], FARAWAY));
1246 
1247  return TRUE;
1248  }
1249 
1250  assert(LT(g->cost[edge], FARAWAY) && LT(g->cost[flipedge(edge)], FARAWAY));
1251 
1252  return FALSE;
1253 }
1254 
1255 
1256 /** check whether node is fixed terminal */
1258  const GRAPH* g, /**< the graph */
1259  int node /**< node to be checked */
1260  )
1261 {
1262  assert(g);
1263  assert(node >= 0 && node < g->knots);
1264  assert(g->term2edge);
1265  assert(g->prize);
1266 
1267 #ifndef NDEBUG
1268  if( TERM2EDGE_FIXEDTERM == g->term2edge[node] )
1269  {
1270  assert(Is_term(g->term[node]));
1271  assert(node == g->source || g->prize[node] == FARAWAY);
1272  }
1273 
1274  if( (TERM2EDGE_FIXEDTERM == g->term2edge[node]) && node != g->source && graph_pc_isMw(g) )
1275  {
1276  for( int e = g->inpbeg[node]; e != EAT_LAST; e = g->ieat[e] )
1277  {
1278  assert(EQ(g->cost[e], 0.0));
1279  }
1280  }
1281 #endif
1282 
1283  return (TERM2EDGE_FIXEDTERM == g->term2edge[node]);
1284 }
1285 
1286 
1287 /** check whether node is proper potential terminal */
1289  const GRAPH* g, /**< the graph */
1290  int node /**< node to be checked */
1291  )
1292 {
1293  assert(g);
1294  assert(graph_pc_isPcMw(g));
1295  assert(node >= 0 && node < g->knots);
1296  assert(g->term2edge && g->prize);
1297 
1298  if( g->extended )
1299  {
1300  return Is_pseudoTerm(g->term[node]);
1301  }
1302 
1303  if( g->term2edge[node] >= 0 && Is_term(g->term[node]) )
1304  {
1305  assert(!graph_pc_knotIsDummyTerm(g, node));
1306 
1307  return TRUE;
1308  }
1309 
1310  return FALSE;
1311 }
1312 
1313 
1314 /** is there no vertex of higher prize? */
1316  const GRAPH* g, /**< graph data structure */
1317  int i /**< the node to be checked */
1318  )
1319 {
1320  SCIP_Real maxprize = -1.0;
1321  const int nnodes = graph_get_nNodes(g);
1322  const SCIP_Real* const prize = g->prize;
1323 
1324  assert(i >= 0 && i < nnodes);
1325  assert(graph_pc_isPc(g));
1326  assert(!graph_pc_knotIsDummyTerm(g, i));
1327 
1328  if( g->stp_type == STP_RPCSPG )
1329  {
1330  return (graph_pc_knotIsFixedTerm(g, i));
1331  }
1332 
1333  for( int k = 0; k < nnodes; k++ )
1334  {
1335  if( prize[k] > maxprize && LT(prize[k], FARAWAY) )
1336  maxprize = prize[k];
1337  }
1338 
1339  return (EQ(g->prize[i], maxprize));
1340 }
1341 
1342 
1343 /** check whether node is a dummy (pseudo) terminal */
1345  const GRAPH* g, /**< the graph */
1346  int node /**< node to be checked */
1347  )
1348 {
1349  assert(g != NULL);
1350  assert(node >= 0);
1351  assert(node < g->knots);
1352  assert(graph_pc_isPcMw(g));
1353  assert(graph_pc_knotIsFixedTerm(g, g->source));
1354 
1355  if( node == g->source && !graph_pc_isRootedPcMw(g) )
1356  return TRUE;
1357 
1358  if( g->extended )
1359  {
1360  if( Is_term(g->term[node]) && !graph_pc_knotIsFixedTerm(g, node) )
1361  {
1362  assert(g->grad[node] == 2 );
1363 
1364  return TRUE;
1365  }
1366  }
1367  else
1368  {
1369  if( Is_pseudoTerm(g->term[node]) )
1370  {
1371  assert(g->grad[node] == 2 );
1372  assert(!graph_pc_knotIsFixedTerm(g, node));
1373 
1374  return TRUE;
1375  }
1376  }
1377 
1378  return FALSE;
1379 }
1380 
1381 
1382 /** check whether node is a terminal AND is not a leaf (or not contained) in at least one optimal tree */
1384  const GRAPH* g, /**< the graph */
1385  int node /**< node to be checked */
1386  )
1387 {
1388  assert(g);
1389  assert(node >= 0 && node < g->knots);
1390 
1391  if( !Is_anyTerm(g->term[node]) )
1392  return FALSE;
1393 
1394  return graph_pc_termIsNonLeafTerm(g, node);
1395 }
1396 
1397 
1398 /** changes prize of a node */
1400  GRAPH* g, /**< the graph */
1401  SCIP_Real newprize, /**< new prize */
1402  int node /**< the node */
1403  )
1404 {
1405  const SCIP_Bool isMw = (g->stp_type == STP_MWCSP || g->stp_type == STP_RMWCSP);
1406  assert(graph_pc_isPcMw(g));
1407  assert(isMw || Is_term(g->term[node]));
1408 
1409  if( Is_term(g->term[node]) )
1410  {
1411  const int twin = graph_pc_getTwinTerm(g, node);
1412  const int root2edge = graph_pc_getRoot2PtermEdge(g, twin);
1413 
1414  assert(GE(newprize, 0.0));
1415  assert(graph_pc_knotIsPropPotTerm(g, node));
1416  assert(EQ(g->prize[node], g->cost[root2edge]));
1417 
1418  g->cost[root2edge] = newprize;
1419  }
1420 
1421  g->prize[node] = newprize;
1422 
1423  if( isMw )
1424  {
1425  mwKnotUpdateIncEdges(g, node);
1426  }
1427 }
1428 
1429 
1430 /** check whether terminal is not a leaf (or not contained) in at least one optimal tree */
1432  const GRAPH* g, /**< the graph */
1433  int term /**< terminal to be checked */
1434  )
1435 {
1436  SCIP_Bool isNonLeafTerm = FALSE;
1437 
1438  assert(g && g->term2edge);
1439  assert(term >= 0 && term < g->knots);
1440  assert(Is_anyTerm(g->term[term]));
1441 
1442  if( graph_pc_knotIsFixedTerm(g, term) )
1443  {
1444  isNonLeafTerm = FALSE;
1445  }
1446  else if( g->extended )
1447  {
1448  isNonLeafTerm = Is_nonleafTerm(g->term[term]);
1449  }
1450  else
1451  {
1452  /* original graph: */
1453  assert(Is_term(g->term[term]) || Is_pseudoTerm(g->term[term]));
1454 
1455  isNonLeafTerm = (g->term2edge[term] == TERM2EDGE_NONLEAFTERM);
1456 
1457  assert(!(Is_pseudoTerm(g->term[term]) && isNonLeafTerm));
1458  }
1459 
1460  assert(!isNonLeafTerm || g->term2edge[term] == TERM2EDGE_NONLEAFTERM);
1461 
1462  return isNonLeafTerm;
1463 }
1464 
1465 
1466 /** is terminal a non-leaf? Checked by evaluation of the current graph */
1468  SCIP* scip, /**< SCIP */
1469  const GRAPH* g, /**< the graph */
1470  int term /**< terminal to be checked */
1471  )
1472 {
1473  SCIP_Bool isNonLeaf = TRUE;
1474 
1475  assert(graph_pc_isPcMw(g));
1476  assert(!g->extended);
1477  assert(Is_term(g->term[term]));
1478  assert(!graph_pc_knotIsFixedTerm(g, term));
1479 
1480  if( graph_pc_realDegree(g, term, FALSE) == 0 )
1481  return FALSE;
1482 
1483  for( int e = g->inpbeg[term]; e != EAT_LAST; e = g->ieat[e] )
1484  {
1485  const int neighbor = g->tail[e];
1486 
1487  if( !graph_pc_knotIsDummyTerm(g, neighbor) && SCIPisLT(scip, g->cost[e], g->prize[term]) )
1488  {
1489  assert(neighbor != g->source || graph_pc_isRootedPcMw(g));
1490  isNonLeaf = FALSE;
1491  break;
1492  }
1493  }
1494 
1495  return isNonLeaf;
1496 }
1497 
1498 
1499 /** check whether terminal is not a leaf in at least one optimal tree */
1501  const GRAPH* g, /**< the graph */
1502  int* termmark /**< terminal mark (2 for proper terminal, 1 for non-proper terminal, 0 otherwise) */
1503 )
1504 {
1505  const int nnodes = g->knots;
1506 
1507  assert(!g->extended);
1508 
1509  assert(g && termmark);
1510 
1511  for( int i = 0; i < nnodes; i++ )
1512  {
1513  if( Is_term(g->term[i]) )
1514  {
1515  if( graph_pc_termIsNonLeafTerm(g, i) )
1516  termmark[i] = 1;
1517  else
1518  termmark[i] = 2;
1519  }
1520  else
1521  {
1522  termmark[i] = 0;
1523  }
1524  }
1525 }
1526 
1527 
1528 /** Enforces given pseudo-terminal without deleting edges.
1529  * I.e. the terminal is part of any optimal solution. */
1531  SCIP* scip, /**< SCIP data */
1532  GRAPH* graph, /**< graph */
1533  int pterm /**< the pseudo-terminal */
1534 )
1535 {
1536  const int dummyterm = graph_pc_getTwinTerm(graph, pterm);
1537  const int root2term = graph_pc_getRoot2PtermEdge(graph, dummyterm);
1538 
1539  assert(scip && graph);
1540  assert(!graph_pc_knotIsDummyTerm(graph, pterm));
1541  assert(graph_pc_knotIsDummyTerm(graph, dummyterm));
1542  assert(graph_pc_knotIsPropPotTerm(graph, pterm));
1543  assert(SCIPisEQ(scip, graph->cost[root2term], graph->prize[pterm]));
1544 
1545  /* don't change because of weird prize sum in reduce.c */
1546  if( SCIPisLT(scip, graph->prize[pterm], BLOCKED_MINOR) )
1547  {
1548  graph->prize[pterm] = BLOCKED_MINOR;
1549  graph->cost[root2term] = BLOCKED_MINOR;
1550  }
1551 }
1552 
1553 
1554 /** Enforces non-leaf terminal without deleting edges.
1555  * I.e. the terminal is part of any optimal solution. */
1557  SCIP* scip, /**< SCIP data */
1558  GRAPH* graph, /**< graph */
1559  int nonleafterm /**< the terminal */
1560 )
1561 {
1562  assert(scip && graph);
1563  assert(graph_pc_isPc(graph) && graph->extended);
1564  assert(graph_pc_knotIsNonLeafTerm(graph, nonleafterm));
1565 
1566  if( graph_pc_isRootedPcMw(graph) )
1567  {
1568  assert(!graph_pc_isMw(graph));
1569 
1570  /* make it a proper fixed terminal */
1571  graph_pc_knotToFixedTermProperty(graph, nonleafterm);
1572 
1573  if( graph_pc_isPc(graph) )
1574  {
1575  assert(graph->cost_org_pc);
1576 
1577  for( int e = graph->inpbeg[nonleafterm]; e != EAT_LAST; e = graph->ieat[e] )
1578  graph->cost[e] = graph->cost_org_pc[e];
1579  }
1580  }
1581  else if( SCIPisLT(scip, graph->prize[nonleafterm], BLOCKED) )
1582  {
1583  /* don't change because of weird prize sum in reduce_base.c */
1584  // graph->prize[nonleafterm] = BLOCKED_MINOR; // todo quite hacky, because it destroys the invariant of non-leaf terms!
1585  }
1586 }
1587 
1588 /** is non-leaf term enforced? */
1590  SCIP* scip, /**< SCIP data */
1591  const GRAPH* graph, /**< graph */
1592  int nonleafterm /**< the terminal */
1593 )
1594 {
1595  assert(scip && graph);
1596  assert(graph_pc_isPcMw(graph) && graph->extended);
1597  assert(graph_pc_knotIsNonLeafTerm(graph, nonleafterm));
1598 
1599  return SCIPisEQ(scip, graph->prize[nonleafterm], BLOCKED_MINOR);
1600 }
1601 
1602 
1603 /** Tries to enforce node without deleting or adding edges.
1604  * I.e. the terminal is part of any optimal solution.
1605  * Is not always possible! */
1607  SCIP* scip, /**< SCIP data */
1608  GRAPH* graph, /**< graph */
1609  int term, /**< the terminal */
1610  SCIP_Real* offset /**< pointer to the offset, for RMW only */
1611 )
1612 {
1613  assert(graph_pc_isPcMw(graph));
1614 
1615  if( graph->extended )
1616  {
1617  /* nothing to enforce? */
1618  if( Is_term(graph->term[term]) )
1619  return;
1620 
1621  if( Is_pseudoTerm(graph->term[term]) )
1622  {
1623  graph_pc_enforcePseudoTerm(scip, graph, term);
1624  }
1625  else if( graph_pc_isRootedPcMw(graph) && !graph_pc_knotIsNonLeafTerm(graph, term) )
1626  {
1627  graph_pc_nonTermToFixedTerm(graph, term, offset);
1628  }
1629  }
1630  else
1631  {
1632  if( graph_pc_knotIsFixedTerm(graph, term) )
1633  return;
1634 
1635  if( !graph_pc_isMw(graph) && graph_pc_knotIsNonLeafTerm(graph, term) )
1636  {
1637  if( graph_pc_isRootedPcMw(graph) )
1638  graph_pc_knotToFixedTermProperty(graph, term);
1639 
1640  return;
1641  }
1642 
1643  if( Is_term(graph->term[term]) )
1644  {
1645  assert(graph_pc_knotIsPropPotTerm(graph, term));
1646 
1647  graph_pc_enforcePseudoTerm(scip, graph, term);
1648  }
1649  else if( graph_pc_isRootedPcMw(graph) )
1650  {
1651  assert(!graph_pc_knotIsDummyTerm(graph, term));
1652 
1653  graph_pc_nonTermToFixedTerm(graph, term, offset);
1654  }
1655  }
1656 }
1657 
1658 
1659 /** Updates prize-collecting data for an edge added to subgraph of given graph 'orggraph'.
1660  * Needs to be called right before corresponding edge is added */
1662  const GRAPH* orggraph, /**< original graph */
1663  const int* nodemapOrg2sub, /**< node mapping from original to subgraph */
1664  int orgedge, /**< original edge */
1665  GRAPH* subgraph /**< the subgraph */
1666 )
1667 {
1668  const int orgtail = orggraph->tail[orgedge];
1669  const int orghead = orggraph->head[orgedge];
1670  const int newtail = nodemapOrg2sub[orgtail];
1671  const int newhead = nodemapOrg2sub[orghead];
1672 
1673  assert(subgraph);
1674  assert(subgraph->term2edge);
1675  assert(orggraph->term2edge);
1676  assert(newtail >= 0);
1677  assert(newhead >= 0);
1678  assert(orggraph->extended);
1679  assert(subgraph->extended);
1680 
1681  if( orggraph->term2edge[orgtail] >= 0 && orggraph->term2edge[orghead] >= 0 && orggraph->term[orgtail] != orggraph->term[orghead] )
1682  {
1683  assert(Is_anyTerm(subgraph->term[newtail]) && Is_anyTerm(subgraph->term[newhead]));
1684  assert(Is_anyTerm(orggraph->term[orgtail]) && Is_anyTerm(orggraph->term[orghead]));
1685  assert(orggraph->source != orgtail && orggraph->source != orghead);
1686  assert(flipedge(subgraph->edges) == subgraph->edges + 1);
1687 
1688  subgraph->term2edge[newtail] = subgraph->edges;
1689  subgraph->term2edge[newhead] = subgraph->edges + 1;
1690  }
1691 
1692 #ifndef NDEBUG
1693  if( TERM2EDGE_NOTERM == orggraph->term2edge[orgtail] )
1694  assert(TERM2EDGE_NOTERM == subgraph->term2edge[newtail]);
1695 
1696  if( TERM2EDGE_NOTERM == orggraph->term2edge[orghead] )
1697  assert(TERM2EDGE_NOTERM == subgraph->term2edge[newhead]);
1698 #endif
1699 
1700  /* now save the terminal states if there are any */
1701 
1702  if( orggraph->term2edge[orgtail] < 0 )
1703  subgraph->term2edge[newtail] = orggraph->term2edge[orgtail];
1704 
1705  if( orggraph->term2edge[orghead] < 0 )
1706  subgraph->term2edge[newhead] = orggraph->term2edge[orghead];
1707 
1708  assert(subgraph->edges + 1 < subgraph->esize);
1709  assert(subgraph->edges + 1 < orggraph->edges);
1710 
1711  /* now save the original costs */
1712  if( graph_pc_isPc(orggraph) )
1713  {
1714  assert(subgraph->cost_org_pc);
1715  subgraph->cost_org_pc[subgraph->edges] = orggraph->cost_org_pc[orgedge];
1716  subgraph->cost_org_pc[subgraph->edges + 1] = orggraph->cost_org_pc[flipedge(orgedge)];
1717  }
1718 }
1719 
1720 
1721 /** gets number of undeleted, original edges (not going to dummy terminals) */
1723  const GRAPH* graph /**< the graph */
1724 )
1725 {
1726  int norgedges = 0;
1727  const int nedges = graph_get_nEdges(graph);
1728 
1729  for( int e = 0; e < nedges; ++e )
1730  {
1731  const int tail = graph->tail[e];
1732  const int head = graph->head[e];
1733 
1734  /* edge deleted? */
1735  if( graph->oeat[e] == EAT_FREE )
1736  continue;
1737 
1738  if( !graph_pc_knotIsDummyTerm(graph, tail) && !graph_pc_knotIsDummyTerm(graph, head) )
1739  {
1740  assert(LT(graph->cost[e], FARAWAY));
1741 
1742  norgedges++;
1743  }
1744  }
1745 
1746  return norgedges;
1747 }
1748 
1749 
1750 /** gets ratio of remaining nodes/edges */
1752  const GRAPH* graph, /**< graph */
1753  SCIP_Real* ratio_nodes, /**< nodes ratio */
1754  SCIP_Real* ratio_edges /**< edges ratio */
1755 )
1756 {
1757  int nnodes_real = 0;
1758  int nedges_real = 0;
1759  const SCIP_Bool isRooted = graph_pc_isRootedPcMw(graph);
1760  const int nnodes = graph->knots;
1761  const int norgmodelknots = graph->norgmodelknots;
1762  const int norgmodeledges = graph->norgmodeledges;
1763  const int pseudoroot = (isRooted ? -1 : graph->source);
1764 
1765  assert(ratio_nodes && ratio_edges);
1766  assert(graph_pc_isPcMw(graph));
1767  assert(graph->extended);
1768 
1769  /* todo somewhat hacky...but otherwise there is a problem if the graph vanished during presolving, because term2edge
1770  * array does not exist */
1771  if( graph->terms == 1 )
1772  {
1773  assert(graph->edges == 0);
1774 
1775  *ratio_nodes = 0.0;
1776  *ratio_edges = 0.0;
1777  return;
1778  }
1779 
1780  for( int i = 0; i < nnodes; i++ )
1781  {
1782  if( pseudoroot == i )
1783  continue;
1784 
1785  if( graph_pc_knotIsDummyTerm(graph, i) )
1786  continue;
1787 
1788  if( graph->grad[i] == 0 )
1789  continue;
1790 
1791  assert(!Is_term(graph->term[i]) || isRooted);
1792 
1793  nnodes_real++;
1794  nedges_real += graph->grad[i];
1795 
1796  if( Is_pseudoTerm(graph->term[i]) )
1797  {
1798  if( isRooted )
1799  nedges_real -= 1;
1800  else
1801  nedges_real -= 2;
1802  }
1803 
1804  if( isRooted && i == graph->source )
1805  {
1806  nedges_real -= graph_pc_nNonFixedTerms(graph);
1807  }
1808  }
1809 
1810  assert(1 <= nnodes_real && nnodes_real <= norgmodelknots);
1811  assert(nedges_real <= norgmodeledges);
1812  assert(2 <= norgmodeledges);
1813  assert(norgmodeledges % 2 == 0);
1814  assert(nedges_real % 2 == 0);
1815 
1816 #ifdef SCIP_DEBUG
1817  printf("norgmodelknots=%d \n", norgmodelknots);
1818  printf("norgmodeledges=%d \n", norgmodeledges);
1819  printf("nnodes_real=%d \n", nnodes_real);
1820  printf("nedges_real=%d \n", nedges_real);
1821 #endif
1822 
1823  *ratio_nodes = (SCIP_Real) nnodes_real / (SCIP_Real) norgmodelknots;
1824  *ratio_edges = (SCIP_Real) nedges_real / (SCIP_Real) norgmodeledges;
1825 }
1826 
1827 
1828 /** gets original edge costs, when in extended mode */
1830  SCIP* scip, /**< SCIP data structure */
1831  const GRAPH* graph, /**< the graph */
1832  SCIP_Real* edgecosts /**< original costs to be filled */
1833 )
1834 {
1835  const int nedges = graph_get_nEdges(graph);
1836  const SCIP_Real* const cost_org = graph->cost_org_pc;
1837 
1838  assert(scip && edgecosts);
1839  assert(graph->extended && graph_pc_isPcMw(graph));
1840 
1841  assert(graph_pc_transOrgAreConistent(scip, graph, TRUE));
1842 
1843  if( SCIPgetStage(scip) < SCIP_STAGE_INITSOLVE )
1844  {
1845  BMScopyMemoryArray(edgecosts, cost_org, nedges);
1846 
1847 #ifndef NDEBUG
1848  for( int e = 0; e < nedges; ++e )
1849  {
1850  assert(!graph_edge_isBlocked(graph, e));
1851  }
1852 #endif
1853  }
1854  else
1855  {
1856  BMScopyMemoryArray(edgecosts, graph->cost, nedges);
1857 
1858  for( int e = 0; e < nedges; ++e )
1859  {
1860  const SCIP_Bool edgeIsBlocked = EQ(graph->cost[e], BLOCKED_MINOR) || EQ(graph->cost[e], BLOCKED);
1861  assert(edgeIsBlocked == graph_edge_isBlocked(graph, e));
1862 
1863  if( !edgeIsBlocked )
1864  edgecosts[e] = cost_org[e];
1865  }
1866  }
1867 }
1868 
1869 
1870 /** gets original edge costs for CSR, when in extended mode */
1872  SCIP* scip, /**< SCIP data structure */
1873  const GRAPH* g, /**< the graph */
1874  CSR* csr /**< CSR */
1875 )
1876 {
1877  const SCIP_Real* const gCosts = g->cost;
1878  const SCIP_Real* const gCosts_org = g->cost_org_pc;
1879  SCIP_Real* RESTRICT csrCosts = csr->cost;
1880  const int* const edgeid = csr->edge_id;
1881  const int nnodes = graph_get_nNodes(g);
1882  const int nedges = csr->start[nnodes];
1883 
1884  assert(edgeid && gCosts && gCosts_org);
1885  assert(nnodes >= 1 && nedges >= 0);
1886  assert(csr->nnodes == nnodes);
1887  assert(nedges <= csr->nedges_max);
1888  assert(nedges <= graph_get_nEdges(g));
1889  assert(g->extended && graph_pc_isPc(g));
1890  assert(graph_pc_transOrgAreConistent(scip, g, TRUE));
1891 
1892  for( int i = 0; i < nedges; i++ )
1893  {
1894  const int edge_g = edgeid[i];
1895  const SCIP_Bool edgeIsBlocked = EQ(gCosts[edge_g], BLOCKED_MINOR) || EQ(gCosts[edge_g], BLOCKED);
1896 
1897  assert(0 <= edge_g && edge_g < g->edges);
1898  assert(edgeIsBlocked == graph_edge_isBlocked(g, edge_g));
1899 
1900  if( edgeIsBlocked )
1901  {
1902  csrCosts[i] = gCosts[edge_g];
1903  }
1904  else
1905  {
1906  csrCosts[i] = gCosts_org[edge_g];
1907  }
1908  }
1909 }
1910 
1911 
1912 /** are the given costs equal to the original edge costs? */
1914  SCIP* scip, /**< SCIP data structure */
1915  const GRAPH* graph, /**< the graph */
1916  const SCIP_Real* edgecosts /**< edge costs to be checked */
1917 )
1918 {
1919  SCIP_Real* costorg;
1920  const int nedges = graph_get_nEdges(graph);
1921  SCIP_Bool isEqual = TRUE;
1922 
1923  assert(scip && edgecosts);
1924 
1925  SCIP_CALL_ABORT( SCIPallocMemoryArray(scip, &costorg, nedges) );
1926  graph_pc_getOrgCosts(scip, graph, costorg);
1927 
1928  for( int e = 0; e < nedges; ++e )
1929  {
1930  if( !EQ(edgecosts[e], costorg[e]) )
1931  {
1932  isEqual = FALSE;
1933  break;
1934  }
1935  }
1936 
1937  SCIPfreeMemoryArray(scip, &costorg);
1938 
1939  return isEqual;
1940 }
1941 
1942 
1943 /** mark original graph (without dummy terminals) */
1945  GRAPH* g /**< the graph */
1946 )
1947 {
1948  const int root = g->source;
1949  const int nnodes = g->knots;
1950 
1951  assert(g != NULL);
1952  assert(graph_pc_isPcMw(g));
1953  assert(g->extended);
1954 
1955  for( int k = 0; k < nnodes; k++ )
1956  g->mark[k] = (g->grad[k] > 0);
1957 
1958  for( int e = g->outbeg[root]; e != EAT_LAST; e = g->oeat[e] )
1959  {
1960  const int head = g->head[e];
1961 
1962  if( graph_pc_knotIsDummyTerm(g, head) )
1963  {
1964  g->mark[head] = FALSE;
1965  assert(g->grad[head] == 2);
1966  assert(GT(g->cost[e], 0.0));
1967  }
1968  }
1969 
1970  if( !graph_pc_isRootedPcMw(g) )
1971  g->mark[root] = FALSE;
1972 }
1973 
1974 
1975 /** mark terminals and switch terminal property to original terminals */
1977  SCIP* scip, /**< SCIP data structure */
1978  GRAPH* graph /**< the graph */
1979  )
1980 {
1981  const int nnodes = graph_get_nNodes(graph);
1982 
1983  assert(scip);
1984  assert(graph->extended && graph_pc_isPcMw(graph));
1985 
1986  /* restore original edge weights */
1987  if( graph_pc_isPc(graph) )
1988  {
1989  if( (SCIPgetStage(scip) < SCIP_STAGE_INITSOLVE) )
1990  setCostToOrgPcPreState(scip, graph);
1991  else
1992  setCostToOrgPc(scip, graph);
1993  }
1994 
1995  /* swap terminal properties and mark original graph */
1996  for( int k = 0; k < nnodes; k++ )
1997  {
1998  if( Is_pseudoTerm(graph->term[k]) || Is_nonleafTerm(graph->term[k]) )
1999  {
2000  assert(!Is_term(graph->term[k]));
2001 
2002  graph_knot_chg(graph, k, STP_TERM);
2003  }
2004  else if( Is_term(graph->term[k]) && !graph_pc_knotIsFixedTerm(graph, k) )
2005  {
2006  assert(k != graph->source);
2007 
2008  graph_knot_chg(graph, k, STP_TERM_PSEUDO);
2009  }
2010  }
2011 
2012  graph->extended = FALSE;
2013 
2014  graph_mark(graph);
2015 }
2016 
2017 /** mark transformed graph and adapt terminal properties to transformed graph */
2019  SCIP* scip, /**< SCIP data structure */
2020  GRAPH* graph /**< the graph */
2021  )
2022 {
2023  const int nnodes = graph->knots;;
2024 
2025  assert(scip);
2026  assert(!graph->extended);
2027  assert(graph_pc_isPcMw(graph));
2028 
2029  /* adapt terminal properties for non-leaf terminals (so far not explicitly marked) */
2030  if( graph_pc_isPc(graph) )
2031  markNonLeafTerms_2trans(scip, graph);
2032 
2033  /* adapt terminal properties and mark transformed graph */
2034  for( int k = 0; k < nnodes; k++ )
2035  {
2036  if( Is_pseudoTerm(graph->term[k]) )
2037  {
2038  graph_knot_chg(graph, k, STP_TERM);
2039  }
2040  else if( Is_term(graph->term[k]) && !graph_pc_knotIsFixedTerm(graph, k) )
2041  {
2042  assert(k != graph->source);
2043  graph_knot_chg(graph, k, STP_TERM_PSEUDO);
2044  }
2045  }
2046 
2047  graph->extended = TRUE;
2048 
2049  graph_mark(graph);
2050 
2051  /* restore transformed edge weights (shift) after storing original ones */
2052  if( graph_pc_isPc(graph) )
2053  {
2054  assert(graph->cost_org_pc);
2055  BMScopyMemoryArray(graph->cost_org_pc, graph->cost, graph->edges);
2056 
2057  graph_pc_shiftNonLeafCosts(scip, graph);
2058  }
2059 }
2060 
2061 /** graph_pc_2org if extended */
2063  SCIP* scip, /**< SCIP data structure */
2064  GRAPH* graph /**< the graph */
2065  )
2066 {
2067  assert(graph && scip);
2068 
2069  if( !graph->extended )
2070  return;
2071 
2072  graph_pc_2org(scip, graph);
2073 }
2074 
2075 /** graph_pc_2trans if not extended */
2077  SCIP* scip, /**< SCIP data structure */
2078  GRAPH* graph /**< the graph */
2079  )
2080 {
2081  assert(graph && scip);
2082 
2083  if( graph->extended )
2084  return;
2085 
2086  graph_pc_2trans(scip, graph);
2087 }
2088 
2089 
2090 /* returns sum of positive vertex weights */
2092  SCIP* scip, /**< SCIP data structure */
2093  const GRAPH* graph /**< the graph */
2094  )
2095 {
2096  SCIP_Real prizesum = 0.0;
2097 
2098  assert(scip != NULL);
2099  assert(graph != NULL);
2100  assert(graph->prize != NULL);
2101  assert(!graph->extended);
2102 
2103  for( int i = 0; i < graph->knots; i++ )
2104  if( Is_term(graph->term[i]) && i != graph->source && SCIPisLT(scip, graph->prize[i], BLOCKED) )
2105  prizesum += graph->prize[i];
2106 
2107  return prizesum;
2108 }
2109 
2110 
2111 /* returns degree of non-root vertex in non-extended graph */
2113  const GRAPH* g, /**< graph data structure */
2114  int i, /**< the vertex to be checked */
2115  SCIP_Bool fixedterm /**< fixed terminal? */
2116 )
2117 {
2118  const int ggrad = g->grad[i];
2119  const SCIP_Bool isRooted = graph_pc_isRootedPcMw(g);
2120  const SCIP_Bool isMw = graph_pc_isMw(g);
2121  int newgrad;
2122 
2123  assert(g != NULL);
2124  assert(graph_pc_isPcMw(g));
2125  assert(!g->extended);
2126  assert(!Is_pseudoTerm(g->term[i]));
2127  assert(i != g->source || graph_pc_isRootedPcMw(g));
2128  assert(fixedterm == graph_pc_knotIsFixedTerm(g, i));
2129 
2130  if( !Is_term(g->term[i]) || fixedterm )
2131  {
2132  newgrad = ggrad;
2133  }
2134  else if( !isMw && graph_pc_knotIsNonLeafTerm(g, i) )
2135  {
2136  newgrad = ggrad;
2137  }
2138  else if( isRooted )
2139  {
2140  assert(Is_term(g->term[i]));
2141 
2142  newgrad = ggrad - 1;
2143  }
2144  else
2145  {
2146  assert(Is_term(g->term[i]));
2147 
2148  newgrad = ggrad - 2;
2149  }
2150 
2151  return newgrad;
2152 }
2153 
2154 
2155 /** adapts SAP deriving from PCST or MWCS problem with new big M */
2157  SCIP_Real bigM, /**< new big M value */
2158  GRAPH* graph, /**< the SAP graph */
2159  SCIP_Real* offset /**< the offset */
2160  )
2161 {
2162  SCIP_Real oldbigM;
2163  const int root = graph->source;
2164 
2165  assert(bigM > 0.0);
2166  assert(graph != NULL && offset != NULL);
2167  assert(graph->outbeg[root] >= 0);
2168 
2169  oldbigM = graph->cost[graph->outbeg[root]];
2170  assert(oldbigM > 0.0);
2171 
2172  *offset += (oldbigM - bigM);
2173 
2174  SCIPdebugMessage("new vs old %f, %f \n", bigM, oldbigM);
2175 
2176  for( int e = graph->outbeg[root]; e != EAT_LAST; e = graph->oeat[e] )
2177  {
2178  assert(EQ(graph->cost[e], oldbigM));
2179  graph->cost[e] = bigM;
2180  }
2181 }
2182 
2183 
2184 /** initializes biased data structures */
2186  const GRAPH* graph, /**< graph data structure */
2187  SCIP_Real* RESTRICT costbiased, /**< biased costs */
2188  SCIP_Real* RESTRICT prizebiased /**< biased prizes */
2189 )
2190 {
2191  assert(graph && costbiased && prizebiased);
2192  assert(graph->extended);
2193  assert(graph_pc_knotIsFixedTerm(graph, graph->source));
2194  assert(graph_pc_isPcMw(graph));
2195 
2196  if( graph_pc_isPc(graph) )
2197  {
2198  getBiasedPc(graph, costbiased, prizebiased);
2199  }
2200  else
2201  {
2202  assert(graph_pc_isMw(graph));
2203  getBiasedMw(graph, costbiased, prizebiased);
2204  }
2205 }
2206 
2207 
2208 /** returns offset generated by non-leaf terminals */
2210  SCIP* scip, /**< SCIP data structure */
2211  const GRAPH* graph /**< graph data structure */
2212 )
2213 {
2214  SCIP_Real offset = 0.0;
2215  const int nnodes = graph_get_nNodes(graph);
2216 
2217  assert(scip);
2218  assert(graph->stp_type == STP_RPCSPG || graph->stp_type == STP_PCSPG);
2219 
2220  for( int i = 0; i < nnodes; ++i )
2221  {
2222  if( graph_pc_knotIsNonLeafTerm(graph, i) )
2223  {
2224  assert(SCIPisGT(scip, graph->prize[i], 0.0));
2225  offset += graph->prize[i];
2226  }
2227  }
2228 
2229  return offset;
2230 }
2231 
2232 
2233 /** Deletes a terminal for a (rooted) prize-collecting problem.
2234  * Note that the prize of the terminal is not changed! */
2236  SCIP* scip, /**< SCIP data structure */
2237  GRAPH* g, /**< graph data structure */
2238  int term, /**< terminal to be deleted */
2239  SCIP_Real* offset /**< pointer to the offset */
2240  )
2241 {
2242  int grad = g->grad[term];
2243 
2244  assert(g && scip && offset);
2245  assert(g->term2edge && g->prize);
2246  assert(graph_pc_isPcMw(g));
2247  assert(Is_term(g->term[term]));
2248  assert(!graph_pc_knotIsFixedTerm(g, term));
2249 
2250  assert(term != g->source);
2251 
2252  if( !g->extended && graph_pc_termIsNonLeafTerm(g, term) )
2253  {
2254  *offset += g->prize[term];
2256  graph_knot_del(scip, g, term, TRUE);
2257  g->prize[term] = 0.0;
2258  }
2259  else
2260  {
2261  int e;
2262  int twin = UNKNOWN;
2263 
2264  /* delete terminal */
2265 
2266  while( (e = g->outbeg[term]) != EAT_LAST )
2267  {
2268  const int i1 = g->head[e];
2269 
2270  if( Is_pseudoTerm(g->term[i1]) && g->source != i1 )
2271  twin = g->head[e];
2272 
2273  graph_edge_del(scip, g, e, TRUE);
2274  }
2275 
2276  assert(g->grad[term] == 0);
2277  assert(twin != UNKNOWN);
2278  assert(twin == graph_pc_getTwinTerm(g, term));
2279 
2280  if( g->extended )
2281  {
2282  assert(SCIPisZero(scip, g->prize[term]));
2283 
2284  *offset += g->prize[twin];
2285  g->prize[twin] = 0.0;
2286  }
2287  else
2288  {
2289  assert(SCIPisZero(scip, g->prize[twin]));
2290 
2291  *offset += g->prize[term];
2292  g->prize[term] = 0.0;
2293  }
2294 
2296 
2297  /* delete twin */
2298 
2300  g->mark[twin] = FALSE;
2301  grad += g->grad[twin] - 1;
2302 
2303  graph_knot_del(scip, g, twin, TRUE);
2304  }
2305 
2306  g->mark[term] = FALSE;
2307 
2308  assert(SCIPisZero(scip, g->prize[term]));
2309 
2310  return grad;
2311 }
2312 
2313 
2314 /** subtract a given sum from the prize of a terminal */
2316  SCIP* scip, /**< SCIP data structure */
2317  GRAPH* g, /**< the graph */
2318  SCIP_Real cost, /**< cost to be subtracted */
2319  int i /**< the terminal */
2320  )
2321 {
2322  assert(scip && g);
2323  assert(!g->extended);
2324  assert(Is_term(g->term[i]));
2325  assert(!graph_pc_knotIsFixedTerm(g, i) && i != g->source);
2326 
2327  g->prize[i] -= cost;
2328 
2329  assert(SCIPisGE(scip, g->prize[i], 0.0) || graph_pc_isPcMw(g));
2330 
2331  /* do we need to adapt edge cost as well? */
2332  if( graph_pc_isMw(g) || !graph_pc_termIsNonLeafTerm(g, i) )
2333  {
2334  const int twinterm = graph_pc_getTwinTerm(g, i);
2335  const int root2twin = graph_pc_getRoot2PtermEdge(g, twinterm);
2336 
2337  assert(!g->mark[twinterm]);
2338  assert(g->tail[root2twin] == g->source && g->head[root2twin] == twinterm);
2339 
2340  g->cost[root2twin] -= cost;
2341 
2342  assert(SCIPisEQ(scip, g->prize[i], g->cost[root2twin]));
2343  }
2344  else
2345  {
2346  assert(graph_pc_isPc(g));
2347  }
2348 }
2349 
2350 
2351 /** contract ancestors of an edge of (rooted) prize-collecting Steiner tree problem or maximum-weight connected subgraph problem */
2353  SCIP* scip, /**< SCIP data structure */
2354  GRAPH* g, /**< the graph */
2355  int t, /**< tail node to be contracted (surviving node) */
2356  int s, /**< head node to be contracted */
2357  int ets /**< edge from t to s or -1 */
2358  )
2359 {
2360  assert(g != NULL);
2361  assert(scip != NULL);
2362 
2363  if( ets < 0 )
2364  {
2365  assert(ets == -1);
2366 
2367  for( ets = g->outbeg[t]; ets != EAT_LAST; ets = g->oeat[ets] )
2368  if( g->head[ets] == s )
2369  break;
2370  }
2371 
2372  assert(ets >= 0 && ets < g->edges);
2373 
2374  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->pcancestors[t]), g->pcancestors[s], NULL) );
2375  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->pcancestors[s]), g->pcancestors[t], NULL) );
2376 
2379 
2380  return SCIP_OKAY;
2381 }
2382 
2383 
2384 /** contract an edge of (rooted) prize-collecting Steiner tree problem or maximum-weight connected subgraph problem */
2386  SCIP* scip, /**< SCIP data structure */
2387  GRAPH* g, /**< the graph */
2388  int* solnode, /**< solution nodes or NULL */
2389  int t, /**< tail node to be contracted (surviving node) */
2390  int s, /**< head node to be contracted */
2391  int term4offset /**< terminal to add offset to */
2392  )
2393 {
2394  int ets;
2395 
2396  assert(scip && g);
2397  assert(Is_term(g->term[term4offset]));
2398  assert(!g->extended);
2399  assert(g->source != s);
2400 
2401  /* get edge from t to s */
2402  for( ets = g->outbeg[t]; ets != EAT_LAST; ets = g->oeat[ets] )
2403  {
2404  if( g->head[ets] == s )
2405  break;
2406  }
2407 
2408  assert(ets != EAT_LAST);
2409 
2411  {
2412  SCIP_CALL( contractEdgeWithFixedEnd(scip, g, solnode, t, s, ets) );
2413  }
2414  else
2415  {
2416  assert(!graph_pc_isRootedPcMw(g) || (s != g->source && t != g->source));
2417  SCIP_CALL( contractEdgeNoFixedEnd(scip, g, solnode, t, s, ets, term4offset) );
2418  }
2419 
2420  assert(g->grad[s] == 0);
2421  assert(TERM2EDGE_NOTERM == g->term2edge[s]);
2422  assert(!Is_anyTerm(g->term[s]));
2423  assert(SCIPisEQ(scip, g->prize[s], 0.0) || graph_pc_isMw(g));
2424 
2425  if( graph_pc_isMw(g) )
2426  {
2427  g->prize[s] = 0.0;
2428  mwKnotUpdateIncEdges(g, t);
2429  }
2430 
2431  SCIPdebugMessage("PcMw contraction: %d into %d, saved in %d \n", s, t, term4offset);
2432 
2433  return SCIP_OKAY;
2434 }
2435 
2436 
2437 /** contract an edge of (rooted) prize-collecting Steiner tree problem or maximum-weight connected subgraph problem;
2438  * method decides whether to contract s into t or vice-versa. Offset is added to surviving node */
2440  SCIP* scip, /**< SCIP data structure */
2441  GRAPH* g, /**< the graph */
2442  int* solnode, /**< solution nodes or NULL */
2443  int t, /**< tail node to be contracted */
2444  int s /**< head node to be contracted */
2445  )
2446 {
2447  assert(g);
2448 
2449  if( graph_pc_termIsNonLeafTerm(g, t) )
2450  SCIP_CALL( graph_pc_contractEdge(scip, g, solnode, s, t, s) );
2451  else if( graph_pc_termIsNonLeafTerm(g, s) )
2452  SCIP_CALL( graph_pc_contractEdge(scip, g, solnode, t, s, t) );
2453  else if( (g->grad[s] >= g->grad[t] || s == g->source) && t != g->source )
2454  SCIP_CALL( graph_pc_contractEdge(scip, g, solnode, s, t, s) );
2455  else
2456  SCIP_CALL( graph_pc_contractEdge(scip, g, solnode, t, s, t) );
2457 
2458  return SCIP_OKAY;
2459 }
2460 
2461 
2462 /** is this graph a prize-collecting variant? */
2464  const GRAPH* g /**< the graph */
2465 )
2466 {
2467  const int type = g->stp_type;
2468  assert(g != NULL);
2469 
2470  return (type == STP_PCSPG || type == STP_RPCSPG);
2471 }
2472 
2473 
2474 /** is this graph a maximum-weight variant? */
2476  const GRAPH* g /**< the graph */
2477 )
2478 {
2479  const int type = g->stp_type;
2480  assert(g != NULL);
2481 
2482  return (type == STP_MWCSP || type == STP_RMWCSP || type == STP_BRMWCSP);
2483 }
2484 
2485 
2486 /** is this graph a prize-collecting or maximum-weight variant? */
2488  const GRAPH* g /**< the graph */
2489 )
2490 {
2491  const int type = g->stp_type;
2492  assert(g != NULL);
2493 
2494  return (type == STP_PCSPG || type == STP_RPCSPG || type == STP_MWCSP || type == STP_RMWCSP || type == STP_BRMWCSP);
2495 }
2496 
2497 
2498 /** get edge from root to (pseudo) terminal */
2500  const GRAPH* graph, /**< the graph */
2501  int pseudoterm /**< the pseudo terminal */
2502 )
2503 {
2504  int rootedge = -1;
2505  const int root = graph->source;
2506 
2507  assert(graph != NULL);
2508  assert(pseudoterm >= 0 && pseudoterm < graph->knots);
2509 
2510  for( int e = graph->inpbeg[pseudoterm]; e != EAT_LAST; e = graph->ieat[e] )
2511  {
2512  if( graph->tail[e] == root )
2513  {
2514  rootedge = e;
2515  break;
2516  }
2517  }
2518 
2519  assert(rootedge >= 0);
2520 
2521  return rootedge;
2522 }
2523 
2524 
2525 /** get number of fixed terminals (not counting the aritificial root) */
2527  const GRAPH* graph /**< the graph */
2528 )
2529 {
2530  int nfixterms = 0;
2531  const int nnodes = graph->knots;
2532  assert(graph != NULL);
2533  assert(graph_pc_isPcMw(graph));
2534 
2535  if( !graph_pc_isRootedPcMw(graph) )
2536  return 0;
2537 
2538  for( int k = 0; k < nnodes; k++ )
2539  if( graph_pc_knotIsFixedTerm(graph, k) )
2540  nfixterms++;
2541 
2542  return nfixterms;
2543 }
2544 
2545 
2546 /** Returns number of non-fixed terminals.
2547  * Note that it is equal to the number of the proper potential terminals
2548  * if g->extended, because in this case the non-leaf terminals are not marked explicitly. */
2550  const GRAPH* graph /**< the graph */
2551 )
2552 {
2553  assert(graph != NULL);
2554  assert(graph_pc_isPcMw(graph));
2555 
2556  if( !graph_pc_isRootedPcMw(graph) )
2557  return (graph->terms - 1);
2558 
2559  return (graph->terms - graph_pc_nFixedTerms(graph));
2560 }
2561 
2562 
2563 /** returns number of non-leaf terminals */
2565  const GRAPH* graph /**< the graph */
2566 )
2567 {
2568  const int nnodes = graph_get_nNodes(graph);
2569  int nnonleafs = 0;
2570 
2571  assert(graph_pc_isPcMw(graph));
2572 
2573  for( int i = 0; i < nnodes; ++i )
2574  if( graph_pc_knotIsNonLeafTerm(graph, i) )
2575  nnonleafs++;
2576 
2577  return nnonleafs;
2578 }
2579 
2580 
2581 /** returns number of proper potential terminals (potential terminals excluding non-leaf terminals) */
2583  const GRAPH* graph /**< the graph */
2584 )
2585 {
2586  int nppterms;
2587 
2588  assert(graph != NULL);
2589  assert(graph_pc_isPcMw(graph));
2590 
2591  if( graph->extended )
2592  nppterms = graph_pc_nNonFixedTerms(graph);
2593  else
2594  nppterms = graph_pc_nNonFixedTerms(graph) - graph_pc_nNonLeafTerms(graph);
2595 
2596  assert(nppterms >= 0);
2597 
2598  return nppterms;
2599 }
2600 
2601 
2602 /** compute solution value for given edge-solution array (CONNECT/UNKNOWN) and offset, takes prizes into account! */
2604  SCIP* scip, /**< SCIP data structure */
2605  const GRAPH* g, /**< the graph */
2606  const int* soledge, /**< solution */
2607  SCIP_Real offset /**< offset */
2608  )
2609 {
2610  const int nnodes = graph_get_nNodes(g);
2611  const int nedges = graph_get_nEdges(g);
2612  const SCIP_Real* const edgecost = g->cost;
2613  SCIP_Real obj = offset;
2614 
2615  assert(graph_pc_isPcMw(g));
2616 
2617  for( int e = 0; e < nedges; e++ )
2618  if( soledge[e] == CONNECT )
2619  obj += edgecost[e];
2620 
2621  /* there are no non-leaf terminals for MWCSP, so return already */
2622  if( !graph_pc_isPc(g) )
2623  return obj;
2624 
2625  if( g->extended )
2626  {
2627  obj += graph_pc_getNonLeafTermOffset(scip, g);
2628  }
2629  else
2630  {
2631  STP_Bool* solnode;
2632 
2633  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &solnode, nnodes) );
2634 
2635  solstp_setVertexFromEdge(g, soledge, solnode);
2636 
2637  for( int i = 0; i < nnodes; ++i )
2638  {
2639  if( !solnode[i] && graph_pc_knotIsNonLeafTerm(g, i) )
2640  {
2641  assert(SCIPisGT(scip, g->prize[i], 0.0));
2642  obj += g->prize[i];
2643  }
2644  }
2645 
2646  SCIPfreeBufferArray(scip, &solnode);
2647  }
2648 
2649  return obj;
2650 }
2651 
2652 /** get twin-terminal */
2654  const GRAPH* g, /**< the graph */
2655  int vertex /**< the vertex */
2656 )
2657 {
2658  assert(g && g->term2edge);
2659  assert(graph_pc_isPcMw(g));
2660  assert(Is_anyTerm(g->term[vertex]));
2661  assert(g->term2edge[vertex] >= 0 && g->term2edge[vertex] < g->edges);
2662  assert(g->tail[g->term2edge[vertex]] == vertex);
2663 
2664  return g->head[g->term2edge[vertex]];
2665 }
2666 
2667 
2668 /** is this graph a un-rooted prize-collecting or rooted maximum-weight variant? */
2670  const GRAPH* g /**< the graph */
2671 )
2672 {
2673  const int type = g->stp_type;
2674  assert(g != NULL);
2675 
2676  return (type == STP_PCSPG || type == STP_MWCSP);
2677 }
2678 
2679 
2680 /** is this graph a rooted prize-collecting or rooted maximum-weight variant? */
2682  const GRAPH* g /**< the graph */
2683 )
2684 {
2685  const int type = g->stp_type;
2686  assert(g != NULL);
2687 
2688  return (type == STP_RPCSPG || type == STP_RMWCSP || type == STP_BRMWCSP);
2689 }
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
void graph_knot_chg(GRAPH *, int, int)
Definition: graph_node.c:86
static volatile int nterms
Definition: interrupt.c:38
SCIP_Bool graph_pc_isMw(const GRAPH *g)
int *RESTRICT head
Definition: graphdefs.h:224
void graph_edge_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_edge.c:368
void graph_pc_shiftNonLeafCosts(SCIP *scip, GRAPH *g)
Definition: graph_pcbase.c:671
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
static void markNonLeafTerms_2trans(SCIP *scip, GRAPH *g)
Definition: graph_pcbase.c:46
int source
Definition: graphdefs.h:195
SCIP_RETCODE graph_fixed_addEdge(SCIP *, int, GRAPH *)
SCIP_Real graph_pc_solGetObj(SCIP *scip, const GRAPH *g, const int *soledge, SCIP_Real offset)
#define Is_term(a)
Definition: graphdefs.h:102
static void getBiasedMw(const GRAPH *graph, SCIP_Real *RESTRICT costbiased, SCIP_Real *RESTRICT prizebiased)
Definition: graph_pcbase.c:448
void graph_pc_enforceNonLeafTerm(SCIP *scip, GRAPH *graph, int nonleafterm)
int graph_pc_getTwinTerm(const GRAPH *g, int vertex)
void graph_pc_getBiased(const GRAPH *graph, SCIP_Real *RESTRICT costbiased, SCIP_Real *RESTRICT prizebiased)
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
void graph_pc_2org(SCIP *scip, GRAPH *graph)
int terms
Definition: graphdefs.h:192
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *g, int node)
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void graph_mark(GRAPH *)
Definition: graph_base.c:1130
int norgmodeledges
Definition: graphdefs.h:215
includes methods for Steiner tree problem solutions
SCIP_Bool graph_pc_isRootedPcMw(const GRAPH *g)
void graph_pc_knotToNonTermProperty(GRAPH *g, int node)
int graph_pc_nNonLeafTerms(const GRAPH *graph)
void graph_knot_printInfo(const GRAPH *, int)
Definition: graph_stats.c:151
#define TERM2EDGE_NONLEAFTERM
Definition: graphdefs.h:74
#define TERM2EDGE_NOTERM
Definition: graphdefs.h:72
#define EAT_FREE
Definition: graphdefs.h:57
#define FALSE
Definition: def.h:87
int *RESTRICT inpbeg
Definition: graphdefs.h:202
void graph_pc_markOrgGraph(GRAPH *g)
SCIP_Real * cost
Definition: graphdefs.h:142
static SCIP_RETCODE contractEdgeWithFixedEnd(SCIP *scip, GRAPH *g, int *solnode, int t, int s, int ets)
Definition: graph_pcbase.c:237
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
SCIP_Bool graph_pc_knotIsPropPotTerm(const GRAPH *g, int node)
void graph_pc_presolExit(SCIP *scip, GRAPH *g)
Definition: graph_pcbase.c:858
SCIP_RETCODE graph_knot_contract(SCIP *, GRAPH *, int *, int, int)
Definition: graph_node.c:264
#define EAT_LAST
Definition: graphdefs.h:58
void graph_pc_getOrgCostsCsr(SCIP *scip, const GRAPH *g, CSR *csr)
static SCIP_Bool isLastTerm(GRAPH *g, int t)
Definition: graph_pcbase.c:190
#define SCIPdebugMessage
Definition: pub_message.h:87
#define FARAWAY
Definition: graphdefs.h:89
int graph_pc_nNonFixedTerms(const GRAPH *graph)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#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
static void mwKnotUpdateIncEdges(GRAPH *g, int node)
Definition: graph_pcbase.c:213
void graph_pc_termMarkProper(const GRAPH *g, int *termmark)
int * start
Definition: graphdefs.h:140
SCIP_RETCODE graph_resize(SCIP *, GRAPH *, int, int, int)
Definition: graph_base.c:744
SCIP_Bool graph_pc_term2edgeIsConsistent(SCIP *scip, const GRAPH *g)
Definition: graph_pcbase.c:874
SCIP_Bool graph_pc_isUnrootedPcMw(const GRAPH *g)
#define STP_TERM_NONE
Definition: graphdefs.h:62
SCIP_RETCODE graph_pc_contractEdge(SCIP *scip, GRAPH *g, int *solnode, int t, int s, int term4offset)
int *RESTRICT mark
Definition: graphdefs.h:198
SCIP_Real graph_pc_getNonLeafTermOffset(SCIP *scip, const GRAPH *graph)
int graph_pc_getRoot2PtermEdge(const GRAPH *graph, int pseudoterm)
SCIP_RETCODE graph_pc_contractNodeAncestors(SCIP *scip, GRAPH *g, int t, int s, int ets)
int *RESTRICT oeat
Definition: graphdefs.h:231
#define BLOCKED_MINOR
Definition: graphdefs.h:91
#define LE(a, b)
Definition: portab.h:83
#define GE(a, b)
Definition: portab.h:85
SCIP_RETCODE SCIPintListNodeAppendCopy(SCIP *scip, IDX **node1, IDX *node2, SCIP_Bool *conflict)
Definition: misc_stp.c:197
SCIP_Bool extended
Definition: graphdefs.h:267
int stp_type
Definition: graphdefs.h:264
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void graph_pc_knotToFixedTerm(SCIP *scip, GRAPH *g, int node, SCIP_Real *offset)
SCIP_Real * prize
Definition: graphdefs.h:210
#define TERM2EDGE_FIXEDTERM
Definition: graphdefs.h:73
SCIP_Bool graph_pc_edgeIsExtended(const GRAPH *g, int edge)
void graph_edge_add(SCIP *, GRAPH *, int, int, double, double)
int *RESTRICT grad
Definition: graphdefs.h:201
void graph_knot_add(GRAPH *, int)
Definition: graph_node.c:64
internal miscellaneous methods
#define NULL
Definition: lpi_spx1.cpp:155
#define STP_RMWCSP
Definition: graphdefs.h:54
#define EQ(a, b)
Definition: portab.h:79
void graph_knot_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_node.c:111
SCIP_Bool graph_pc_knotHasMaxPrize(const GRAPH *g, int i)
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
int * term2edge
Definition: graphdefs.h:208
IDX ** pcancestors
Definition: graphdefs.h:235
void graph_pc_enforcePseudoTerm(SCIP *scip, GRAPH *graph, int pterm)
#define STP_PCSPG
Definition: graphdefs.h:44
#define LT(a, b)
Definition: portab.h:81
void graph_pc_termToNonTerm(SCIP *scip, GRAPH *g, int term)
void graph_pc_getOrgCosts(SCIP *scip, const GRAPH *graph, SCIP_Real *edgecosts)
void graph_pc_fixedTermToNonTerm(SCIP *scip, GRAPH *g, int term)
unsigned char STP_Bool
Definition: portab.h:34
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
int graph_pc_nProperPotentialTerms(const GRAPH *graph)
#define GT(a, b)
Definition: portab.h:84
#define SCIP_Bool
Definition: def.h:84
#define STP_TERM_NONLEAF
Definition: graphdefs.h:64
int *RESTRICT ieat
Definition: graphdefs.h:230
void graph_pc_adaptSap(SCIP_Real bigM, GRAPH *graph, SCIP_Real *offset)
int *RESTRICT tail
Definition: graphdefs.h:223
void graph_pc_2trans(SCIP *scip, GRAPH *graph)
SCIP_RETCODE graph_fixed_moveNodePc(SCIP *, int, GRAPH *)
SCIP_Bool graph_pc_costsEqualOrgCosts(SCIP *scip, const GRAPH *graph, const SCIP_Real *edgecosts)
#define flipedge(edge)
Definition: graphdefs.h:84
#define STP_TERM
Definition: graphdefs.h:61
static SCIP_RETCODE contractEdgeNoFixedEnd(SCIP *scip, GRAPH *g, int *solnode, int t, int s, int ets, int term4offset)
Definition: graph_pcbase.c:287
void graph_pc_termToNonLeafTerm(SCIP *scip, GRAPH *g, int term, SCIP_Bool force)
static void setCostToOrgPc(SCIP *scip, GRAPH *graph)
Definition: graph_pcbase.c:70
SCIP_RETCODE graph_pc_contractEdgeUnordered(SCIP *scip, GRAPH *g, int *solnode, int t, int s)
void graph_pc_getReductionRatios(const GRAPH *graph, SCIP_Real *ratio_nodes, SCIP_Real *ratio_edges)
SCIP_Bool graph_pc_isPcMw(const GRAPH *g)
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
int graph_pc_getNorgEdges(const GRAPH *graph)
int graph_pc_realDegree(const GRAPH *g, int i, SCIP_Bool fixedterm)
static void getBiasedPc(const GRAPH *graph, SCIP_Real *RESTRICT costbiased, SCIP_Real *RESTRICT prizebiased)
Definition: graph_pcbase.c:371
#define CONNECT
Definition: graphdefs.h:87
Portable definitions.
static void setCostToOrgPcPreState(SCIP *scip, GRAPH *graph)
Definition: graph_pcbase.c:96
SCIP_Real graph_pc_getPosPrizeSum(SCIP *scip, const GRAPH *graph)
SCIP_RETCODE graph_pc_initTerm2Edge(SCIP *scip, GRAPH *g, int size)
Definition: graph_pcbase.c:721
SCIP_Bool graph_pc_nonLeafTermIsEnforced(SCIP *scip, const GRAPH *graph, int nonleafterm)
int * edge_id
Definition: graphdefs.h:143
SCIP_Bool graph_pc_isPc(const GRAPH *g)
#define Is_pseudoTerm(a)
Definition: graphdefs.h:103
void graph_pc_knotToFixedTermProperty(GRAPH *g, int node)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real * cost
Definition: graphdefs.h:221
#define STP_TERM_PSEUDO
Definition: graphdefs.h:63
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *g, int node)
int *RESTRICT rootedgeprevs
Definition: graphdefs.h:227
void graph_pc_nonTermToFixedTerm(GRAPH *g, int node, SCIP_Real *offset)
void graph_pc_enforceNode(SCIP *scip, GRAPH *graph, int term, SCIP_Real *offset)
#define SCIP_Real
Definition: def.h:177
#define BLOCKED
Definition: graphdefs.h:90
int esize
Definition: graphdefs.h:218
static void termDeleteExtension(SCIP *scip, GRAPH *g, int i, SCIP_Bool makeNonTerminal)
Definition: graph_pcbase.c:124
void graph_pc_knotChgPrize(GRAPH *g, SCIP_Real newprize, int node)
int *RESTRICT outbeg
Definition: graphdefs.h:204
#define STP_BRMWCSP
Definition: graphdefs.h:55
void graph_pc_updateSubgraphEdge(const GRAPH *orggraph, const int *nodemapOrg2sub, int orgedge, GRAPH *subgraph)
SCIP_RETCODE graph_pc_initSubgraph(SCIP *scip, GRAPH *subgraph)
Definition: graph_pcbase.c:763
SCIP_RETCODE graph_pc_initPrizes(SCIP *scip, GRAPH *g, int sizeprize)
Definition: graph_pcbase.c:741
int edges
Definition: graphdefs.h:219
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
void solstp_setVertexFromEdge(const GRAPH *g, const int *result, STP_Bool *solnode)
Definition: solstp.c:2078
void graph_pc_2transcheck(SCIP *scip, GRAPH *graph)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
int ksize
Definition: graphdefs.h:189
int graph_pc_deleteTerm(SCIP *scip, GRAPH *g, int term, SCIP_Real *offset)
#define UNKNOWN
Definition: sepa_mcf.c:4095
int graph_pc_nFixedTerms(const GRAPH *graph)
SCIP_RETCODE graph_pc_finalizeSubgraph(SCIP *scip, GRAPH *subgraph)
Definition: graph_pcbase.c:795
#define nnodes
Definition: gastrans.c:65
void graph_pc_subtractPrize(SCIP *scip, GRAPH *g, SCIP_Real cost, int i)
void graph_pc_2orgcheck(SCIP *scip, GRAPH *graph)
#define SCIP_CALL_ABORT(x)
Definition: def.h:363
#define Is_anyTerm(a)
Definition: graphdefs.h:105
SCIP_RETCODE graph_pc_presolInit(SCIP *scip, GRAPH *g)
Definition: graph_pcbase.c:815
SCIP_Bool graph_edge_isBlocked(const GRAPH *, int)
Definition: graph_stats.c:94
#define STP_RPCSPG
Definition: graphdefs.h:45
#define STP_MWCSP
Definition: graphdefs.h:51
SCIP_Bool graph_pc_transOrgAreConistent(SCIP *scip, const GRAPH *graph, SCIP_Bool verbose)
Definition: graph_pcbase.c:980
IDX * graph_edge_getAncestors(const GRAPH *, int)
int norgmodelknots
Definition: graphdefs.h:187
SCIP_Bool graph_pc_evalTermIsNonLeaf(SCIP *scip, const GRAPH *g, int term)
SCIP_Bool graph_pc_termIsNonLeafTerm(const GRAPH *g, int term)
SCIP_Bool graph_pc_knotIsNonLeafTerm(const GRAPH *g, int node)