# SCIP

Solving Constraint Integer Programs

graph_base.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file graph_base.c
17  * @brief includes several methods for Steiner problem graphs
18  * @author Thorsten Koch
19  * @author Daniel Rehfeldt
20  *
21  * This file contains several basic methods to process Steiner problem graphs.
22  * A graph can not be reduced in terms of edge or node size, but edges can be marked as
23  * EAT_FREE (to not be used anymore) and nodes may have degree one.
24  * The method 'graph_pack()' can be used to build a new graph that discards these nodes and edges.
25  *
26  */
27
28 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
29
30 /*lint -esym(766,stdlib.h) -esym(766,malloc.h) */
31 /*lint -esym(766,string.h) */
32 //#define SCIP_DEBUG
33
34 #include "scip/misc.h"
35 #include <stdio.h>
36 #include <stdlib.h>
37 #include <string.h>
38 #include <assert.h>
39 #include "portab.h"
40 #include "misc_stp.h"
41 #include "graph.h"
42 #include "reduce.h"
43 #include "stpvector.h"
44 #include "heur_tm.h"
45
46
47 /** is the PC/MW part of the given graph valid? */
48 static
50  SCIP* scip, /**< SCIP */
51  const GRAPH* g, /**< the graph */
52  SCIP_Bool* nodevisited /**< array */
53  )
54 {
55  int nFixedTerms = 0;
56  int nProperTerms = 0;
57  int nPseudoTerms = 0;
58  int nNonLeafTerms = 0;
59  const int nnodes = g->knots;
60  const int root = g->source;
61  const SCIP_Bool isExtended = g->extended;
62  const SCIP_Bool isRooted = graph_pc_isRootedPcMw(g);
63
64  assert(graph_pc_isPcMw(g));
65  assert(g->prize != NULL);
66  assert(g->term2edge != NULL);
67
68  assert(graph_pc_term2edgeIsConsistent(scip, g));
69
70  for( int k = 0; k < nnodes; k++ )
71  {
72  if( graph_pc_knotIsFixedTerm(g, k) )
73  {
74  assert(isRooted || k == root);
75
76  nFixedTerms++;
77
78  continue;
79  }
80
81  assert(k != root);
82
83  if( graph_pc_knotIsNonLeafTerm(g, k) )
84  {
85  nNonLeafTerms++;
86  }
87  /* is k a terminal in the original graph? */
88  else if( (isExtended ? Is_pseudoTerm(g->term[k]) : Is_term(g->term[k])) )
89  {
90  nPseudoTerms++;
91  }
92  /* is k an artificial (newly added) terminal? */
93  else if( (isExtended ? Is_term(g->term[k]) : Is_pseudoTerm(g->term[k])) )
94  {
95  int e;
96  int e2;
97  int pterm = -1;
98  const int term = k;
99
100  nProperTerms++;
101
102  if( g->grad[k] != 2 )
103  {
104  SCIPdebugMessage("terminal degree != 2 for %d \n", k);
105  return FALSE;
106  }
107
108  for( e = g->inpbeg[term]; e != EAT_LAST; e = g->ieat[e] )
109  if( g->tail[e] == root )
110  break;
111
112  if( e == EAT_LAST )
113  {
114  SCIPdebugMessage("no edge to root for term %d \n", term);
115  return FALSE;
116  }
117
118  for( e2 = g->outbeg[term]; e2 != EAT_LAST; e2 = g->oeat[e2] )
119  {
121  if( (isExtended ? Is_pseudoTerm(g->term[pterm]) : Is_term(g->term[pterm])) && pterm != root )
122  break;
123  }
124
125  if( e2 == EAT_LAST)
126  {
127  SCIPdebugMessage("no terminal for dummy %d \n", g->head[e2]);
128  return FALSE;
129  }
130
131  assert(pterm >= 0);
132  assert(pterm != root);
133
134  if( e2 != g->term2edge[term] )
135  {
136  SCIPdebugMessage("term2edge for node %d faulty \n", term);
137  return FALSE;
138  }
139
140  if( !EQ(g->cost[e], g->prize[pterm]) )
141  {
142  SCIPdebugMessage("prize mismatch for node %d: %f!=%f \n", pterm, g->cost[e], g->prize[pterm]);
143  return FALSE;
144  }
145  }
146  } /* for k = 0; k < nnodes; k++ */
147
148  if( nProperTerms != nPseudoTerms )
149  {
150  SCIPdebugMessage("wrong nPseudoTerms terminal count: %d != %d \n", nProperTerms, nPseudoTerms);
151
152  return FALSE;
153  }
154
155  if( isExtended )
156  {
157  /* non-leaf terms are not part of g->terms */
158  if( (nProperTerms + nFixedTerms) != g->terms )
159  {
160  SCIPdebugMessage("wrong overall terminal count(1): %d != %d \n", nProperTerms + nFixedTerms, g->terms);
161
162  return FALSE;
163  }
164  }
165  else
166  {
167  if( (nProperTerms + nNonLeafTerms + nFixedTerms) != g->terms )
168  {
169  SCIPdebugMessage("wrong overall terminal count(2): %d != %d \n", nProperTerms + nNonLeafTerms + nFixedTerms - 1, g->terms);
170
171  return FALSE;
172  }
173  }
174
175  if( isRooted )
176  {
177  SCIP_CALL_ABORT( graph_trail_costAware(scip, g, g->source, nodevisited) );
178
179  for( int k = 0; k < nnodes; k++ )
180  {
181  if( graph_pc_knotIsFixedTerm(g, k) && !nodevisited[k] )
182  {
183  SCIPdebugMessage("disconnected fixed terminal %d \n", k);
184  return FALSE;
185  }
186  }
187  }
188
189  if( isRooted && graph_pc_isMw(g) )
190  {
191  for( int k = 0; k < nnodes; k++ )
192  {
193  if( !graph_pc_knotIsFixedTerm(g, k))
194  continue;
195
196  for( int e = g->inpbeg[k]; e != EAT_LAST; e = g->ieat[e] )
197  {
198  if( !EQ(g->cost[e], 0.0) )
199  {
200  if( k == g->source && graph_pc_knotIsDummyTerm(g, g->tail[e]) )
201  continue;
202
203  SCIPdebugMessage("non-zero incoming arc for fixed MW terminal %d \n", k);
204  return FALSE;
205  }
206  }
207  }
208  }
209
210  return TRUE;
211 }
212
213
214 /** do changes for Pc/Mw variants for vanished graph */
215 static
217  SCIP* scip, /**< SCIP data structure */
218  GRAPH* g_old /**< the old graph */
219  )
220 {
221  int term = -1;
222  const int nnodes_old = g_old->knots;
223
224  if( graph_pc_isRootedPcMw(g_old) )
225  return SCIP_OKAY;
226
227  for( int i = 0; i < nnodes_old; ++i )
228  {
229  if( graph_pc_knotIsNonLeafTerm(g_old, i) )
230  {
231  assert(-1 == term);
232  assert(g_old->source != i);
233
234  term = i;
235  break;
236  }
237  }
238
239  assert(term >= 0);
240  assert(graph_pc_termIsNonLeafTerm(g_old, term));
241
242  SCIP_CALL( graph_fixed_addNodePc(scip, term, g_old) );
243
244  return SCIP_OKAY;
245 }
246
247
248 /** do changes for Pc/Mw variants */
249 static
251  SCIP* scip, /**< SCIP data structure */
252  int nnodes_new, /**< number of nodes */
253  GRAPH* g_old, /**< the old graph */
254  GRAPH* g_new /**< the new graph */
255  )
256 {
257  assert(nnodes_new > 0);
258  assert(graph_pc_isPcMw(g_old));
259
260  assert(g_new->ksize == nnodes_new);
261
262  SCIP_CALL( graph_pc_initSubgraph(scip, g_new) );
263
264  if( g_old->stp_type == STP_BRMWCSP )
265  SCIP_CALL( SCIPallocMemoryArray(scip, &(g_new->costbudget), nnodes_new) );
266
267  return SCIP_OKAY;
268 }
269
270 /** add nodes to new graph during graph packing */
271 static
273  SCIP* scip, /**< SCIP data structure */
274  GRAPH* g_old, /**< the old graph */
275  GRAPH* g_new /**< the new graph */
276  )
277 {
278  const int oldnnodes = graph_get_nNodes(g_old);
279  const SCIP_Bool rpcmw = graph_pc_isRootedPcMw(g_old);
280  const SCIP_Bool pcmw = graph_pc_isPcMw(g_old);
281
282  if( rpcmw )
283  {
284  for( int i = 0; i < oldnnodes; i++ )
285  g_old->mark[i] = (g_old->grad[i] > 0);
286
287  for( int e = g_old->outbeg[g_old->source]; e != EAT_LAST; e =
288  g_old->oeat[e] )
289  {
290  const int i = g_old->head[e];
291
292  if( SCIPisGT(scip, g_old->cost[e], 0.0) && Is_term(g_old->term[i])
293  && g_old->term2edge[i] >= 0 )
294  {
295  g_old->mark[i] = FALSE;
297  }
298  }
299  }
300
301  for( int i = 0; i < oldnnodes; i++ )
302  {
303  if( g_old->grad[i] > 0 )
304  {
305  if( pcmw )
306  {
307  if( !Is_term(g_old->term[i]) || (rpcmw && g_old->mark[i]) )
308  g_new->prize[g_new->knots] = g_old->prize[i];
309  else
310  g_new->prize[g_new->knots] = 0.0;
311  }
312
313  if( g_old->stp_type == STP_BRMWCSP )
314  {
315  if( !Is_term(g_old->term[i]) || (g_old->mark[i]) )
316  g_new->costbudget[g_new->knots] = g_old->costbudget[i];
317  else
318  g_new->costbudget[g_new->knots] = 0.0;
319  }
321  }
322  }
323 }
324
325
326 /** adds pseudo-ancestor to new graph during graph packing */
327 static
329  SCIP* scip, /**< SCIP data structure */
330  const GRAPH* g_old, /**< the old graph */
331  GRAPH* g_new /**< the new graph */
332  )
333 {
334  const int oldnacestors = graph_getNpseudoAncestors(g_old);
335  const int oldnedges = graph_get_nEdges(g_old);
336  int e_new = 0;
337
338  SCIP_CALL( graph_initPseudoAncestors(scip, g_new) );
339
340  if( oldnacestors == 0 )
341  return SCIP_OKAY;
342
344
345  for( int e_old = 0; e_old < oldnedges; e_old += 2 )
346  {
347  if( g_old->ieat[e_old] != EAT_FREE )
348  {
349  const int* ancestors;
350  const int nancestors = graph_edge_nPseudoAncestors(g_old, e_old);
351  SCIP_Bool conflict = FALSE;
352
353  if( nancestors == 0 )
354  {
355  e_new += 2;
356  continue;
357  }
358
359  ancestors = graph_edge_getPseudoAncestors(g_old, e_old);
360  assert(ancestors);
361
362  SCIP_CALL( graph_pseudoAncestors_appendCopyArrayToEdge(scip, e_new, ancestors, nancestors, g_new, &conflict) );
363  assert(!conflict);
364  assert(graph_edge_nPseudoAncestors(g_new, e_new) == nancestors);
365  assert(graph_edge_nPseudoAncestors(g_new, e_new + 1) == nancestors);
366
367  e_new += 2;
368  }
369  }
370
371  assert(e_new == g_new->edges);
372
373  // printf("added %d pseudo ancestors \n", oldnacestors);
374
375  return SCIP_OKAY;
376 }
377
378
379 /** adds edges to new graph during graph packing */
380 static
382  SCIP* scip, /**< SCIP data structure */
383  const int* old2newNode, /**< node mapping */
384  GRAPH* g_old, /**< the old graph */
385  int nnodes, /**< number of nodes for new graph */
386  int nedges, /**< number of edges for new graph */
387  GRAPH* g_new /**< the new graph */
388  )
389 {
390  const int oldnedges = graph_get_nEdges(g_old);
391
392  SCIP_CALL( SCIPallocMemoryArray(scip, &(g_new->ancestors), nedges) );
393
395  for( int e_old = 0; e_old < oldnedges; e_old += 2 )
396  {
397  int e_new;
398  if( g_old->ieat[e_old] == EAT_FREE )
399  {
400  assert(g_old->oeat[e_old] == EAT_FREE);
401  assert(g_old->ieat[e_old + 1] == EAT_FREE);
402  assert(g_old->oeat[e_old + 1] == EAT_FREE);
403
404  graph_edge_delHistory(scip, g_old, e_old);
405  continue;
406  }
407
408  assert(g_old->oeat[e_old] != EAT_FREE);
409  assert(g_old->ieat[e_old + 1] != EAT_FREE);
410  assert(g_old->oeat[e_old + 1] != EAT_FREE);
411  assert(old2newNode[g_old->tail[e_old]] >= 0);
413
414  e_new = g_new->edges;
415  assert(e_new % 2 == 0);
416
417  g_new->ancestors[e_new] = g_old->ancestors[e_old];
418  g_new->ancestors[e_new + 1] = g_old->ancestors[e_old + 1];
419
420  assert(old2newNode[g_old->tail[e_old]] < nnodes && old2newNode[g_old->head[e_old]] < nnodes);
421
422  graph_edge_addSubgraph(scip, g_old, old2newNode, e_old, g_new);
423
424  g_old->ancestors[e_old] = g_old->ancestors[e_old + 1] = NULL;
425  }
426
427  assert(nedges == g_new->edges);
428
429  SCIP_CALL( packPseudoAncestors(scip, g_old, g_new) );
430
431  return SCIP_OKAY;
432 }
433
434 /*
435  * global functions
436  */
437
438
439 /** builds complete graph (Kn) with unit edge weights and no terminals */
441  SCIP* scip, /**< SCIP data structure */
442  GRAPH** g, /**< new graph */
443  int nnodes /**< number of nodes */
444  )
445 {
446  const int nedges = nnodes * (nnodes - 1);
447  GRAPH* graph;
448
449  assert(scip && g);
450  assert(nnodes >= 1);
451
452  SCIP_CALL( graph_init(scip, g, nnodes, nedges, 1) );
453
454  graph = *g;
455
456  for( int k = 0; k < nnodes; k++ )
458
459  for( int k = 0; k < nnodes - 1; k++ )
460  for( int k2 = nnodes - 1; k2 >= k + 1; k2-- )
461  graph_edge_add(scip, graph, k, k2, 1.0, 1.0);
462
463  return SCIP_OKAY;
464 }
465
466
467 /* get compressed sparse row arrays representing current graph */
469  const GRAPH* g, /**< the graph */
470  int* RESTRICT edgearr, /**< original edge array [0,...,nedges - 1] */
471  int* RESTRICT tailarr, /**< tail of csr edge [0,...,nedges - 1] */
472  int* RESTRICT start, /**< start array [0,...,nnodes] */
473  int* nnewedges /**< pointer to store number of new edges */
474  )
475 {
476  int i = 0;
477  const int nnodes = g->knots;
478
479  assert(g != NULL);
480  assert(tailarr != NULL);
481  assert(edgearr != NULL);
482  assert(start != NULL);
483
484  for( int k = 0; k < nnodes; k++ )
485  {
486  start[k] = i;
487  for( int e = g->inpbeg[k]; e >= 0; e = g->ieat[e] )
488  {
489  edgearr[i] = e;
490  tailarr[i++] = g->tail[e] + 1;
491  }
492  }
493
494  *nnewedges = i;
495  start[nnodes] = i;
496 }
497
498
499 /** get edge costs */
501  const GRAPH* graph, /**< the graph */
502  SCIP_Real* RESTRICT cost, /**< reduced edge costs */
503  SCIP_Real* RESTRICT costrev /**< reduced reverse edge costs */
504 )
505 {
506  const int nedges = graph_get_nEdges(graph);
507  const SCIP_Real* const gcost = graph->cost;
508
509  assert(cost && costrev);
510
511  for( int e = 0; e < nedges; e++ )
512  {
513  cost[e] = gcost[e];
514  costrev[e] = gcost[flipedge(e)];
515  assert(GE(cost[e], 0.0));
516  }
517 }
518
519
520 /** gets reversed edge costs */
522  const GRAPH* graph, /**< the graph */
523  SCIP_Real* RESTRICT costrev /**< reduced reverse edge costs */
524 )
525 {
526  const int nedges = graph_get_nEdges(graph);
527  const SCIP_Real* const gcost = graph->cost;
528
529  assert(costrev);
530
531  for( int e = 0; e < nedges; e++ )
532  {
533  costrev[e] = gcost[flipedge(e)];
534  assert(GE(costrev[e], 0.0));
535  }
536 }
537
538
539 /* modifies 'isterm' to mark whether node is a terminal (or proper terminal for PC) */
541  const GRAPH* g, /**< the graph */
542  SCIP_Bool* isterm /**< marks whether node is a terminal (or proper terminal for PC) */
543 )
544 {
545  const int nnodes = g->knots;
546  const SCIP_Bool pcmw = graph_pc_isPcMw(g);
547
548  assert(g && isterm);
549  assert(!pcmw || !g->extended);
550
551  for( int i = 0; i < nnodes; i++ )
552  {
553  isterm[i] = FALSE;
554
555  if( Is_term(g->term[i]) )
556  {
557  if( pcmw && graph_pc_termIsNonLeafTerm(g, i) )
558  continue;
559
560  isterm[i] = TRUE;
561  }
562  }
563 }
564
565
566 /** gets terminals */
568  const GRAPH* g, /**< the graph */
569  int* terms /**< array of size g->terms */
570 )
571 {
572  int nterms = 0;
573  const int nnodes = graph_get_nNodes(g);
574
575  assert(terms);
576
577  for( int i = 0; i < nnodes; i++ )
578  {
579  if( Is_term(g->term[i]) )
580  terms[nterms++] = i;
581  }
582
583  assert(g->terms == nterms);
584 }
585
586
587 /** gets randomly permuted terminals */
589  SCIP* scip, /**< SCIP data structure */
590  const GRAPH* g, /**< the graph */
591  int* terms /**< array of size g->terms */
592 )
593 {
594  SCIP_RANDNUMGEN* rand;
595  SCIP_CALL( SCIPcreateRandom(scip, &rand, g->terms, TRUE) );
596
597  graph_getTerms(g, terms);
598  SCIPrandomPermuteIntArray(rand, terms, 0, g->terms);
599
600  SCIPfreeRandom(scip, &rand);
601
602  return SCIP_OKAY;
603 }
604
605
606 /** initialize graph */
608  SCIP* scip, /**< SCIP data structure */
609  GRAPH** g, /**< new graph */
610  int ksize, /**< slots for nodes */
611  int esize, /**< slots for edges */
612  int layers /**< number of layers (only needed for packing, otherwise 1) */
613  )
614 {
615  GRAPH* p;
616
617  assert(ksize > 0);
618  assert(ksize < INT_MAX);
619  assert(esize >= 0);
620  assert(esize < INT_MAX);
621  assert(layers > 0);
622  assert(layers < SHRT_MAX);
623
624  SCIP_CALL( SCIPallocMemory(scip, g) );
625  p = *g;
626  assert(p != NULL);
627
628  p->ancestors = NULL;
629  p->pcancestors = NULL;
630  p->fixedcomponents = NULL;
631  p->orgtail = NULL;
633  p->rootedgeprevs = NULL;
634  p->norgmodelterms = 0;
635  p->norgmodelknots = 0;
636  p->norgmodeledges = 0;
637  p->ksize = ksize;
638  p->orgknots = 0;
639  p->orgedges = 0;
640  p->knots = 0;
641  p->terms = 0;
642  p->grid_dim = -1;
643  p->orgsource = UNKNOWN;
644  p->stp_type = UNKNOWN;
645  p->layers = layers;
646  p->hoplimit = UNKNOWN;
647  p->extended = FALSE;
648  p->source = -1;
649  p->is_packed = FALSE;
651  p->cost_org_pc = NULL;
652  p->contracttrace = NULL;
653
654  SCIP_CALL( SCIPallocMemoryArray(scip, &(p->term), ksize) );
655  SCIP_CALL( SCIPallocMemoryArray(scip, &(p->mark), ksize) );
656  SCIP_CALL( SCIPallocMemoryArray(scip, &(p->grad), ksize) );
657  SCIP_CALL( SCIPallocMemoryArray(scip, &(p->inpbeg), ksize) );
658  SCIP_CALL( SCIPallocMemoryArray(scip, &(p->outbeg), ksize) );
659  SCIP_CALL( SCIPallocMemoryArray(scip, &(p->cost), esize) );
660  SCIP_CALL( SCIPallocMemoryArray(scip, &(p->tail), esize) );
661  SCIP_CALL( SCIPallocMemoryArray(scip, &(p->head), esize) );
662  SCIP_CALL( SCIPallocMemoryArray(scip, &(p->ieat), esize) );
663  SCIP_CALL( SCIPallocMemoryArray(scip, &(p->oeat), esize) );
664
665  p->esize = esize;
666  p->edges = 0;
667  p->mincut_nnodes = 0;
668  p->mincut_nedges = 0;
669  p->prize = NULL;
670  p->maxdeg = NULL;
671  p->grid_coordinates = NULL;
672  p->grid_ncoords = NULL;
673  p->mincut_dist = NULL;
675  p->mincut_numb = NULL;
676  p->mincut_prev = NULL;
677  p->mincut_next = NULL;
678  p->mincut_temp = NULL;
679  p->mincut_e = NULL;
680  p->mincut_x = NULL;
681  p->mincut_r = NULL;
682  p->path_heap = NULL;
683  p->path_state = NULL;
684  p->term2edge = NULL;
685  p->budget = -1.0;
686  p->costbudget = NULL;
687  p->csr_storage = NULL;
688  p->dcsr_storage = NULL;
689  p->pseudoancestors = NULL;
690
691  return SCIP_OKAY;
692 }
693
694 /** initialize data structures required to keep track of reductions */
696  SCIP* scip, /**< SCIP data structure */
697  GRAPH* graph /**< graph */
698  )
699 {
700  IDX** pcancestors; /* ancestor lists array (over all nodes) */
701  const int nedges = graph_get_nEdges(graph);
702  const int* tail = graph->tail;
704  int* orgtail;
706  const SCIP_Bool isPcMw = graph_pc_isPcMw(graph);
707
708  assert(scip);
710  assert(!graph->ancestors);
711  assert(nedges > 0);
712
713  SCIP_CALL( graph_initPseudoAncestors(scip, graph) );
714
715  SCIP_CALL( SCIPallocMemoryArray(scip, &(graph->orgtail), nedges) );
716  SCIP_CALL( SCIPallocMemoryArray(scip, &(graph->orghead), nedges) );
717
718  orgtail = graph->orgtail;
720
721  BMScopyMemoryArray(orgtail, tail, nedges);
723
724  if( isPcMw )
725  {
726  const int nnodes = graph->knots;
727
728  SCIP_CALL( SCIPallocMemoryArray(scip, &(graph->pcancestors), nnodes) );
729
730  pcancestors = graph->pcancestors;
731
732  for( int k = 0; k < nnodes; k++ )
733  pcancestors[k] = NULL;
734  }
735
736  SCIP_CALL( SCIPallocMemoryArray(scip, &(graph->ancestors), nedges) );
737  SCIP_CALL( graph_initAncestors(scip, graph) );
738
739  return SCIP_OKAY;
740 }
741
742
743 /** enlarge given graph */
745  SCIP* scip, /**< SCIP data structure */
746  GRAPH* g, /**< graph to be resized */
747  int ksize, /**< new node slots */
748  int esize, /**< new edge slots */
749  int layers /**< layers (set to -1 by default) */
750  )
751 {
752  assert(scip != NULL);
753  assert(g != NULL);
754  assert((ksize < 0) || (ksize >= g->knots));
755  assert((esize < 0) || (esize >= g->edges));
756  assert((layers < 0) || (layers >= g->layers));
757
758  if( (layers > 0) && (layers != g->layers) )
759  g->layers = layers;
760
761  if( (ksize > 0) && (ksize != g->ksize) )
762  {
763  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->term), ksize) );
764  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->mark), ksize) );
765  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->grad), ksize) );
766  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->inpbeg), ksize) );
767  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->outbeg), ksize) );
768
769  if( g->prize != NULL)
770  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->prize), ksize) );
771
772  if( g->costbudget != NULL)
773  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->costbudget), ksize) );
774
775  if( g->term2edge != NULL)
776  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->term2edge), ksize) );
777
778  g->ksize = ksize;
779  }
780  if( (esize > 0) && (esize != g->esize) )
781  {
782  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->cost), esize) );
783  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->tail), esize) );
784  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->head), esize) );
785  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->ieat), esize) );
786  SCIP_CALL( SCIPreallocMemoryArray(scip, &(g->oeat), esize) );
787
788  g->esize = esize;
789  }
790
791  return SCIP_OKAY;
792 }
793
794
795 /** free the graph */
797  SCIP* scip, /**< SCIP data structure */
798  GRAPH** graph, /**< graph to be freed */
799  SCIP_Bool final /**< delete ancestor data structures? */
800  )
801 {
802  GRAPH* p;
803
804  assert(scip != NULL);
805  assert(graph != NULL);
806
807  p = *graph;
808  assert(p != NULL);
809
811  graph_mincut_exit(scip, p);
812
813  if( graph_path_exists(p) )
814  graph_path_exit(scip, p);
815
816  graph_freeHistory(scip, p);
817
818  if( final )
819  graph_freeHistoryDeep(scip, p);
820
821  SCIPfreeMemoryArrayNull(scip, &(p->prize));
822  SCIPfreeMemoryArrayNull(scip, &(p->costbudget));
823  SCIPfreeMemoryArrayNull(scip, &(p->term2edge));
824
825  if( p->csr_storage != NULL )
826  graph_free_csr(scip, p);
827
828  if( p->dcsr_storage != NULL )
829  graph_free_dcsr(scip, p);
830
831  if( p->stp_type == STP_DCSTP )
832  {
833  SCIPfreeMemoryArray(scip, &(p->maxdeg));
834  }
835  else if( p->stp_type == STP_RSMT )
836  {
837  if( p->grid_coordinates != NULL )
838  {
839  assert(p->grid_coordinates != NULL);
840  for( int i = p->grid_dim - 1; i >= 0; i-- )
841  SCIPfreeMemoryArray(scip, &(p->grid_coordinates[i]));
842
844  }
845
846  if( p->grid_ncoords != NULL )
847  SCIPfreeMemoryArray(scip, &(p->grid_ncoords));
848  }
849
850  SCIPfreeMemoryArray(scip, &(p->oeat));
851  SCIPfreeMemoryArray(scip, &(p->ieat));
853  SCIPfreeMemoryArray(scip, &(p->tail));
854  SCIPfreeMemoryArray(scip, &(p->cost));
855  SCIPfreeMemoryArray(scip, &(p->outbeg));
856  SCIPfreeMemoryArray(scip, &(p->inpbeg));
858  SCIPfreeMemoryArray(scip, &(p->mark));
859  SCIPfreeMemoryArray(scip, &(p->term));
862
863  SCIPfreeMemory(scip, graph);
864 }
865
866
867 /** frees the history */
869  SCIP* scip, /**< SCIP data */
870  GRAPH* p /**< graph data */
871  )
872 {
874
875  if( p->pseudoancestors != NULL )
876  graph_freePseudoAncestors(scip, p);
877
878  if( p->ancestors != NULL )
879  {
880  const int nedges = p->edges;
881
882  for( int e = nedges - 1; e >= 0; e-- )
883  {
884  IDX* curr = p->ancestors[e];
885  while( curr != NULL )
886  {
887  p->ancestors[e] = curr->parent;
888  SCIPfreeBlockMemory(scip, &(curr));
889  curr = p->ancestors[e];
890  }
891  }
892  SCIPfreeMemoryArray(scip, &(p->ancestors));
893  }
894
895  assert(p->pseudoancestors == NULL && p->ancestors == NULL);
896 }
897
898
899 /** frees the deep history */
901  SCIP* scip, /**< SCIP data */
902  GRAPH* p /**< graph data */
903  )
904 {
905  assert(scip != NULL);
906  assert(p != NULL);
907  assert(p->path_heap == NULL);
908  assert(p->path_state == NULL);
909
910  if( p->pcancestors != NULL )
911  {
912  for( int e = p->norgmodelknots - 1; e >= 0; e-- )
913  {
914  IDX* curr = p->pcancestors[e];
915  while( curr != NULL )
916  {
917  p->pcancestors[e] = curr->parent;
918  SCIPfreeBlockMemory(scip, &(curr));
919  curr = p->pcancestors[e];
920  }
921  }
922  SCIPfreeMemoryArray(scip, &(p->pcancestors));
923  }
924
925  if( p->orgtail != NULL )
926  {
928
930  SCIPfreeMemoryArray(scip, &(p->orgtail));
931  }
932
933  if( p->fixedcomponents )
934  graph_free_fixed(scip, p);
935 }
936
937
938 /** copy the graph */
940  SCIP* scip, /**< SCIP data structure */
941  const GRAPH* orggraph, /**< original graph */
942  GRAPH** copygraph /**< graph to be created */
943  )
944 {
945  const GRAPH* p = orggraph;
946  assert(p != NULL);
947
948  SCIP_CALL( graph_init(scip, copygraph, p->ksize, p->esize, p->layers) );
949
950  SCIP_CALL( graph_copyData(scip, orggraph, *copygraph) );
951
952  return SCIP_OKAY;
953 }
954
955
956 /** copy the data of the graph */
958  SCIP* scip, /**< SCIP data structure */
959  const GRAPH* orgraph, /**< original graph */
960  GRAPH* copygraph /**< graph to be copied to */
961  )
962 {
963  GRAPH* g_copy = copygraph;
964  const GRAPH* g_org = orgraph;
965  const int ksize = g_org->ksize;
966  const int esize = g_org->esize;
967
968  assert(scip != NULL);
969  assert(orgraph != NULL);
970  assert(copygraph != NULL);
971  assert(ksize == g_copy->ksize && ksize > 0);
972  assert(esize == g_copy->esize && esize >= 0);
973  assert(g_org->dcsr_storage == NULL && g_org->csr_storage == NULL);
974
975  g_copy->norgmodeledges = g_org->norgmodeledges;
976  g_copy->norgmodelknots = g_org->norgmodelknots;
977  g_copy->norgmodelterms = g_org->norgmodelterms;
978  g_copy->knots = g_org->knots;
979  g_copy->terms = g_org->terms;
980  g_copy->edges = g_org->edges;
981  g_copy->source = g_org->source;
982  g_copy->orgsource = g_org->orgsource;
983  g_copy->orgedges = g_org->orgedges;
984  g_copy->orgknots = g_org->orgknots;
985  g_copy->grid_dim = g_org->grid_dim;
986  g_copy->stp_type = g_org->stp_type;
987  g_copy->hoplimit = g_org->hoplimit;
988  g_copy->extended = g_org->extended;
989  g_copy->budget = g_org->budget;
990  g_copy->is_packed = g_org->is_packed;
992
993  BMScopyMemoryArray(g_copy->term, g_org->term, ksize);
994  BMScopyMemoryArray(g_copy->mark, g_org->mark, ksize);
996  BMScopyMemoryArray(g_copy->inpbeg, g_org->inpbeg, ksize);
997  BMScopyMemoryArray(g_copy->outbeg, g_org->outbeg, ksize);
998  BMScopyMemoryArray(g_copy->cost, g_org->cost, esize);
999  BMScopyMemoryArray(g_copy->tail, g_org->tail, esize);
1001  BMScopyMemoryArray(g_copy->ieat, g_org->ieat, esize);
1002  BMScopyMemoryArray(g_copy->oeat, g_org->oeat, esize);
1003
1004  if( graph_pc_isPcMw(g_copy) )
1005  {
1006  const SCIP_Bool brpcmw = (g_copy->stp_type == STP_BRMWCSP);
1007
1008  assert(g_copy->extended && g_org->extended);
1009
1010  if( g_copy->costbudget != NULL )
1011  {
1012  assert(brpcmw);
1013  SCIPfreeMemoryArray(scip, &(g_copy->costbudget));
1014  }
1015
1016  if( brpcmw )
1017  {
1018  SCIP_CALL(SCIPallocMemoryArray(scip, &(g_copy->costbudget), g_copy->knots));
1019  BMScopyMemoryArray(g_copy->costbudget, g_org->costbudget, g_copy->knots);
1020  }
1021
1022  SCIPfreeMemoryArrayNull(scip, &(g_copy->prize));
1023  SCIPfreeMemoryArrayNull(scip, &(g_copy->term2edge));
1024  SCIPfreeMemoryArrayNull(scip, &(g_copy->cost_org_pc));
1025  SCIP_CALL(SCIPallocMemoryArray(scip, &(g_copy->prize), g_copy->knots));
1026  SCIP_CALL(SCIPallocMemoryArray(scip, &(g_copy->term2edge), g_copy->knots));
1027
1028  if( graph_pc_isPc(g_org) )
1029  {
1030  assert(g_org->cost_org_pc != NULL);
1031  SCIP_CALL(SCIPallocMemoryArray(scip, &(g_copy->cost_org_pc), g_copy->edges));
1032  BMScopyMemoryArray(g_copy->cost_org_pc, g_org->cost_org_pc, g_copy->edges);
1033  }
1034  else
1035  {
1036  g_copy->cost_org_pc = NULL;
1037  }
1038
1039  assert(g_org->prize != NULL);
1040  BMScopyMemoryArray(g_copy->prize, g_org->prize, g_copy->knots);
1041
1042 #ifndef NDEBUG
1043  for( int k = 0; k < g_copy->knots; k++ )
1044  {
1045  if( Is_term(g_org->term[k]) && (!graph_pc_isRootedPcMw(g_copy) || !graph_pc_knotIsFixedTerm(g_org, k)) )
1046  assert(EQ(g_copy->prize[k], 0.0));
1047  }
1048 #endif
1049
1050  assert(g_org->term2edge != NULL);
1051  BMScopyMemoryArray(g_copy->term2edge, g_org->term2edge, g_copy->knots);
1052  }
1053  else if( g_copy->stp_type == STP_DCSTP )
1054  {
1055  assert(g_org->maxdeg != NULL);
1056
1057  SCIP_CALL(SCIPallocMemoryArray(scip, &(g_copy->maxdeg), g_copy->knots));
1058
1059  for( int k = 0; k < g_copy->knots; k++ )
1060  g_copy->maxdeg[k] = g_org->maxdeg[k];
1061  }
1062  else if( g_org->stp_type == STP_RSMT )
1063  {
1064  assert(g_org->grid_ncoords != NULL);
1065  assert(g_org->grid_coordinates != NULL);
1066  assert(g_org->grid_dim > 0);
1067
1068  SCIP_CALL(SCIPallocMemoryArray(scip, &(g_copy->grid_coordinates), g_org->grid_dim));
1069
1071  for( int k = 0; k < g_org->grid_dim; k++ )
1072  {
1073  SCIP_CALL(SCIPallocMemoryArray(scip, &(g_copy->grid_coordinates[k]), g_org->terms)); /*lint !e866*/
1074  BMScopyMemoryArray(g_copy->grid_coordinates[k], g_org->grid_coordinates[k], g_org->terms); /*lint !e866*/
1075  }
1076  SCIP_CALL(SCIPallocMemoryArray(scip, &(g_copy->grid_ncoords), g_org->grid_dim));
1077
1078  BMScopyMemoryArray(g_copy->grid_ncoords, g_org->grid_ncoords, g_org->grid_dim);
1079  }
1080
1081  assert(graph_valid(scip, g_copy));
1082
1083  return SCIP_OKAY;
1084 }
1085
1086
1087 /** copies the pseudo-ancestors */
1089  SCIP* scip, /**< SCIP data structure */
1090  const GRAPH* orggraph, /**< original graph */
1091  GRAPH* copygraph /**< graph to be created */
1092  )
1093 {
1094  const int nedges = graph_get_nEdges(orggraph);
1095  const int nancestors_all = graph_getNpseudoAncestors(orggraph);
1096  assert(orggraph && copygraph);
1097  assert(orggraph->edges == copygraph->edges);
1098  assert(graph_getNpseudoAncestors(copygraph) == 0);
1099
1100  if( nancestors_all == 0 )
1101  return SCIP_OKAY;
1102
1104
1105  for( int e = 0; e < nedges; e += 2 )
1106  {
1107  if( orggraph->ieat[e] != EAT_FREE )
1108  {
1109  const int* ancestors;
1110  const int nancestors = graph_edge_nPseudoAncestors(orggraph, e);
1111  SCIP_Bool conflict = FALSE;
1112
1113  if( nancestors == 0 )
1114  continue;
1115
1116  ancestors = graph_edge_getPseudoAncestors(orggraph, e);
1117  assert(ancestors);
1118
1119  SCIP_CALL( graph_pseudoAncestors_appendCopyArrayToEdge(scip, e, ancestors, nancestors, copygraph, &conflict) );
1120  assert(!conflict);
1121  }
1122  }
1123
1124  return SCIP_OKAY;
1125 }
1126
1127
1128
1129 /** marks the current graph */
1131  GRAPH* g /**< the graph */
1132  )
1133 {
1134  const int nnodes = graph_get_nNodes(g);
1135  const int root = g->source;
1137  int* RESTRICT isMarked = g->mark;
1138
1139  for( int k = 0; k < nnodes; k++ )
1140  isMarked[k] = (grad[k] > 0);
1141
1142  isMarked[root] = TRUE;
1143
1144  if( graph_pc_isPcMw(g) && !g->extended )
1145  {
1146  for( int k = 0; k < nnodes; k++ )
1147  {
1148  if( Is_pseudoTerm(g->term[k]) )
1149  isMarked[k] = FALSE;
1150  else if( Is_term(g->term[k]) )
1151  isMarked[k] = TRUE;
1152  }
1153
1154  if( graph_pc_isRootedPcMw(g) )
1155  isMarked[root] = TRUE;
1156  else
1157  isMarked[root] = FALSE;
1158  }
1159
1160  assert(graph_isMarked(g));
1161 }
1162
1163
1164 /** is the current graph properly marked? */
1166  const GRAPH* g /**< the graph */
1167  )
1168 {
1169  assert(g);
1170
1171  if( graph_pc_isPcMw(g) && !g->extended )
1172  {
1173  const int nnodes = g->knots;
1174  const int root = g->source;
1175  const int rooted = graph_pc_isRootedPcMw(g);
1176
1177  for( int k = 0; k < nnodes; k++ )
1178  {
1179  if( Is_pseudoTerm(g->term[k]) || (!rooted && k == root) )
1180  {
1181  assert(g->grad[k] == 2 || k == root);
1182
1183  if( g->mark[k] )
1184  {
1185  graph_knot_printInfo(g, k);
1186  printf("pseudo-terminal %d is marked \n", k);
1187  return FALSE;
1188  }
1189  }
1190  else
1191  {
1192  if( g->mark[k] != (g->grad[k] > 0) )
1193  {
1194  if( k == root && g->mark[k] )
1195  continue;
1196
1197  if( Is_term(g->term[k]) && g->mark[k] )
1198  continue;
1199
1200  graph_knot_printInfo(g, k);
1202  return FALSE;
1203  }
1204  }
1205  }
1206
1207  if( rooted )
1208  {
1209  if( !g->mark[root] )
1210  {
1211  printf("root not marked \n");
1212  return FALSE;
1213  }
1214  }
1215  }
1216  else
1217  {
1218  const int nnodes = g->knots;
1219
1220  for( int k = 0; k < nnodes; k++ )
1221  {
1222  if( g->mark[k] != (g->grad[k] > 0) )
1223  {
1224  if( k == g->source && g->mark[k] )
1225  continue;
1226
1227  graph_knot_printInfo(g, k);
1229  return FALSE;
1230  }
1231  }
1232  }
1233
1234  return TRUE;
1235 }
1236
1237
1238
1239 /** is the current graph already set up? (with history and path) */
1241  const GRAPH* g /**< the graph */
1242  )
1243 {
1244  assert(g);
1245  assert((g->orgtail == NULL) == (g->ancestors == NULL));
1246
1247  return (g->ancestors != NULL);
1248 }
1249
1250
1252  const GRAPH* p /**< the graph */
1253  )
1254 {
1255  int i;
1256
1257  assert(p != NULL);
1258
1259  for(i = 0; i < p->knots; i++)
1261  (void)printf("Knot %d, term=%d, grad=%d, inpbeg=%d, outbeg=%d\n",
1262  i, p->term[i], p->grad[i], p->inpbeg[i], p->outbeg[i]);
1263
1264  (void)fputc('\n', stdout);
1265
1266  for(i = 0; i < p->edges; i++)
1267  if (p->ieat[i] != EAT_FREE)
1268  (void)printf("Edge %d, cost=%g, tail=%d, head=%d, ieat=%d, oeat=%d\n",
1269  i, p->cost[i], p->tail[i], p->head[i], p->ieat[i], p->oeat[i]);
1270
1271  (void)fputc('\n', stdout);
1272 }
1273
1274
1275 /** reinsert all hidden edges */
1277  GRAPH* g /**< the graph */
1278  )
1279 {/*lint --e{850}*/
1281  int tail;
1282  int e;
1283
1284  assert(g != NULL);
1285
1286  for( e = 0; e < g->edges; e++ )
1287  {
1288  if( g->ieat[e] == EAT_HIDE )
1289  {
1290  assert(e % 2 == 0);
1291  assert(g->oeat[e] == EAT_HIDE);
1292
1294  tail = g->tail[e];
1295
1298
1300  g->oeat[e] = g->outbeg[tail];
1302  g->outbeg[tail] = e;
1303
1304  e++;
1305
1306  assert(g->ieat[e] == EAT_HIDE);
1307  assert(g->oeat[e] == EAT_HIDE);
1310
1312  tail = g->tail[e];
1314  g->oeat[e] = g->outbeg[tail];
1316  g->outbeg[tail] = e;
1317  }
1318  }
1319 }
1320
1321
1322 /** Packs the graph, i.e. builds a new graph that discards deleted edges and nodes.
1323  * The original graph is deleted. */
1325  SCIP* scip, /**< SCIP data structure */
1326  GRAPH* graph, /**< the graph */
1327  GRAPH** newgraph, /**< the new graph */
1328  REDSOL* redsol, /**< reduce solution or NULL */
1329  SCIP_Bool verbose /**< verbose? */
1330  )
1331 {
1332  GRAPH *g_old;
1333  GRAPH *g_new;
1334  int* old2newNode;
1335  const int oldnnodes = graph_get_nNodes(graph);
1336  const int oldnedges = graph_get_nEdges(graph);
1337  int nnodes = 0;
1338  int nedges = 0;
1339  const SCIP_Bool pcmw = graph_pc_isPcMw(graph);
1340  SCIP_Bool graphHasVanished = FALSE;
1341
1342  assert(scip && newgraph);
1343  assert(graph_valid(scip, graph));
1344  assert(!graph->is_packed);
1345
1346  g_old = graph;
1347
1348  SCIP_CALL( SCIPallocBufferArray(scip, &old2newNode, oldnnodes) );
1349
1350  if( verbose )
1351  printf("Reduced graph: ");
1352
1353  /* build node mapping */
1354  for( int i = 0; i < oldnnodes; i++ )
1355  {
1356  if( g_old->grad[i] > 0 )
1357  old2newNode[i] = nnodes++;
1358  else
1359  old2newNode[i] = -1;
1360  }
1361
1362  /* graph vanished? */
1363  if( nnodes == 0 )
1364  {
1365  SCIPfreeBufferArray(scip, &old2newNode);
1366  old2newNode = NULL;
1367  if( verbose )
1368  printf(" graph vanished!\n");
1369
1370  nnodes = 1;
1371  graphHasVanished = TRUE;
1372
1373  if( pcmw )
1374  {
1375  SCIP_CALL( packPcMwVanished(scip, g_old) );
1376  }
1377  }
1378
1379  /* count surviving edges */
1380  for( int i = 0; i < oldnedges; i++ )
1381  {
1382  if( g_old->oeat[i] != EAT_FREE )
1383  {
1384  assert(g_old->ieat[i] != EAT_FREE);
1385  nedges++;
1386  }
1387  }
1388
1389  assert(nnodes > 1 || nedges == 0);
1390  SCIP_CALL( graph_init(scip, newgraph, nnodes, nedges, g_old->layers) );
1391  g_new = *newgraph;
1392  g_new->norgmodelknots = g_old->norgmodelknots;
1393  g_new->norgmodelterms = g_old->norgmodelterms;
1394  g_new->norgmodeledges = g_old->norgmodeledges;
1395  g_new->orgsource = g_old->orgsource;
1396  g_new->orgtail = g_old->orgtail;
1398  g_new->orgknots = g_old->knots;
1399  g_new->orgedges = g_old->edges;
1400  g_new->stp_type = g_old->stp_type;
1401  g_new->maxdeg = g_old->maxdeg;
1402  g_new->grid_dim = g_old->grid_dim;
1403  g_new->grid_ncoords = g_old->grid_ncoords;
1404  g_new->grid_coordinates = g_old->grid_coordinates;
1405  g_new->pcancestors = g_old->pcancestors;
1406  g_new->fixedcomponents = g_old->fixedcomponents;
1407  g_new->hoplimit = g_old->hoplimit;
1408  g_new->extended = g_old->extended;
1409  g_new->budget = g_old->budget;
1410  g_new->is_packed = TRUE;
1411
1412  if( graphHasVanished )
1413  {
1414  assert(!old2newNode);
1415
1416  g_new->ancestors = NULL;
1417  graph_free(scip, &g_old, FALSE);
1418
1419  if( g_new->stp_type == STP_RSMT )
1420  {
1421  g_new->grid_ncoords = NULL;
1422  g_new->grid_coordinates = NULL;
1423  }
1424
1426  g_new->source = 0;
1427
1428  return SCIP_OKAY;
1429  }
1430
1431  assert(nnodes >= 2 && nedges >= 1);
1432
1433  if( pcmw )
1434  {
1435  SCIP_CALL( packPcMwInit(scip, nnodes, g_old, g_new) );
1436  }
1437
1438  if( redsol )
1439  {
1440  reduce_solPack(g_old, old2newNode, nnodes, redsol);
1441  }
1442
1443  /* add nodes (of positive degree) to new graph */
1444  packNodes(scip, g_old, g_new);
1445
1447  assert(Is_term(g_new->term[old2newNode[g_old->source]]));
1448  g_new->source = old2newNode[g_old->source];
1449  assert(!graph_pc_isRootedPcMw(graph) || FARAWAY == g_new->prize[g_new->source]);
1450
1451  /* NOTE: also handles ancestors */
1452  SCIP_CALL( packEdges(scip, old2newNode, g_old, nnodes, nedges, g_new) );
1453
1454  SCIPfreeBufferArray(scip, &old2newNode);
1455
1456  SCIP_CALL( graph_pc_finalizeSubgraph(scip, g_new) );
1457
1458  if( graph_pc_isPc(g_new) )
1459  {
1460  SCIP_Real* offset = reduce_solGetOffsetPointer(redsol);
1461  *offset += graph_pc_getNonLeafTermOffset(scip, g_new);
1462  }
1463
1464  if( g_old->path_heap != NULL )
1465  graph_path_exit(scip, g_old);
1466
1467  g_old->stp_type = UNKNOWN;
1468  graph_free(scip, &g_old, FALSE);
1469
1470  assert(graph_valid(scip, g_new));
1471
1472  if( verbose )
1473  printf("Nodes: %d Edges: %d Terminals: %d\n", g_new->knots, g_new->edges, g_new->terms);
1474
1475  return SCIP_OKAY;
1476 }
1477
1478
1479 /** is the given graph valid? */
1481  SCIP* scip, /**< scip struct */
1482  const GRAPH* g /**< the graph */
1483  )
1484 {
1485  int nterms;
1486  const int nnodes = g->knots;
1487  const int nedges = g->edges;
1488  SCIP_Bool isValid = TRUE;
1489  SCIP_Bool* nodevisited = NULL;
1490
1491  assert(scip && g);
1492  nterms = g->terms;
1493
1494  for( int k = 0; k < nnodes; k++ )
1495  {
1496  int e;
1497
1498  if( Is_term(g->term[k]) )
1499  nterms--;
1500
1501  for( e = g->inpbeg[k]; e != EAT_LAST; e = g->ieat[e] )
1502  if( g->head[e] != k )
1503  break;
1504
1505  if( e != EAT_LAST )
1506  {
1507  isValid = FALSE;
1508  SCIPdebugMessage("*** Graph invalid: Head invalid, Knot %d, Edge %d, Tail=%d, Head=%d\n",
1510
1511  goto EXIT;
1512  }
1513
1514  for( e = g->outbeg[k]; e != EAT_LAST; e = g->oeat[e] )
1515  if( g->tail[e] != k )
1516  break;
1517
1518  if( e != EAT_LAST )
1519  {
1520  isValid = FALSE;
1521  SCIPdebugMessage("*** Graph invalid: Tail invalid, Knot %d, Edge %d, Tail=%d, Head=%d\n",
1523
1524  goto EXIT;
1525  }
1526  }
1527
1528  if( nterms != 0 )
1529  {
1530  isValid = FALSE;
1531  SCIPdebugMessage("*** Graph invalid: Wrong Terminal count, count is %d, should be %d\n",
1532  g->terms, g->terms - nterms);
1533
1534  goto EXIT;
1535  }
1536
1537  if( (g->source < 0 ) || (g->source >= g->knots) || (g->term[g->source] != 0) )
1538  {
1539  isValid = FALSE;
1540  SCIPdebugMessage("*** Graph invalid: Source invalid, Layer %d, Source %d, Terminal %d\n",
1541  0, g->source, g->term[g->source]);
1542
1543  goto EXIT;
1544  }
1545
1546  for( int e = 0; e < nedges; e += 2 )
1547  {
1548  if( (g->ieat[e] == EAT_FREE) && (g->oeat[e] == EAT_FREE)
1549  && (g->ieat[e + 1] == EAT_FREE) && (g->oeat[e + 1] == EAT_FREE) )
1550  {
1551  continue;
1552  }
1553
1554  if( (g->ieat[e] == EAT_FREE) || (g->oeat[e] == EAT_FREE)
1555  || (g->ieat[e + 1] == EAT_FREE) || (g->oeat[e + 1] == EAT_FREE) )
1556  {
1557  isValid = FALSE;
1558  SCIPdebugMessage("*** Graph invalid: FREE invalid, Edge %d/%d\n",
1559  e, e + 1);
1560
1561  goto EXIT;
1562  }
1563
1564  if( (g->head[e] != g->tail[e + 1]) || (g->tail[e] != g->head[e + 1]) )
1565  {
1566  isValid = FALSE;
1567  SCIPdebugMessage("*** Graph invalid: Anti invalid, Edge %d/%d, Tail=%d/%d, Head=%d/%d\n",
1568  e, e + 1, g->head[e], g->tail[e + 1], g->tail[e], g->head[e + 1]);
1569
1570  goto EXIT;
1571  }
1572  }
1573
1574  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &nodevisited, nnodes) );
1575  SCIP_CALL_ABORT( graph_trail_arr(scip, g, g->source, nodevisited) );
1576
1577  for( int k = 0; k < nnodes; k++ )
1578  {
1579  if( (g->grad[k] == 0) && ((g->inpbeg[k] != EAT_LAST) || (g->outbeg[k] != EAT_LAST)) )
1580  {
1581  isValid = FALSE;
1582  SCIPdebugMessage("*** Graph invalid: Knot %d with Grad 0 has Edges\n", k);
1583
1584  goto EXIT;
1585  }
1586
1587  if( !nodevisited[k] && ((g->grad[k] > 0) || (Is_term(g->term[k]))) )
1588  {
1589  if( graph_pc_isPcMw(g) && !graph_pc_knotIsFixedTerm(g, k) )
1590  {
1591  continue;
1592  }
1593
1594  isValid = FALSE;
1595 #ifdef SCIP_DEBUG
1596  graph_knot_printInfo(g, k);
1597  SCIPdebugMessage("*** Graph invalid: Knot %d not connected\n", k);
1598 #endif
1599
1600  goto EXIT;
1601  }
1602  }
1603
1604  if( isValid && graph_pc_isPcMw(g) )
1605  {
1606  isValid = graphisValidPcMw(scip, g, nodevisited);
1607  }
1608
1609
1610  EXIT:
1611
1612  SCIPfreeBufferArrayNull(scip, &nodevisited);
1613  return isValid;
1614 }
1615
1616
1617
1618 /** is the given input graph valid? */
1620  SCIP* scip, /**< scip struct */
1621  const GRAPH* g /**< the graph */
1622  )
1623 {
1624  const int nnodes = graph_get_nNodes(g);
1625  int nterms = g->terms;
1626  SCIP_Bool isValid = TRUE;
1627  SCIP_Bool* nodevisited = NULL;
1628
1629  assert(scip && g);
1630
1631  for( int k = 0; k < nnodes; k++ )
1632  {
1633  int e;
1634
1635  if( Is_term(g->term[k]) )
1636  nterms--;
1637
1638  for( e = g->inpbeg[k]; e != EAT_LAST; e = g->ieat[e] )
1639  if( g->head[e] != k )
1640  break;
1641
1642  if( e != EAT_LAST )
1643  {
1644  isValid = FALSE;
1645  SCIPerrorMessage("Input graph invalid: Head invalid, node %d, edge %d->%d \n",
1646  k, g->tail[e] + 1, g->head[e] + 1);
1647
1648  goto EXIT;
1649  }
1650
1651  for( e = g->outbeg[k]; e != EAT_LAST; e = g->oeat[e] )
1652  if( g->tail[e] != k )
1653  break;
1654
1655  if( e != EAT_LAST )
1656  {
1657  isValid = FALSE;
1658  SCIPerrorMessage("Input graph invalid: Tail invalid, node %d, edge %d->%d \n",
1659  k, g->tail[e] + 1, g->head[e] + 1);
1660
1661  goto EXIT;
1662  }
1663  }
1664
1665  if( nterms != 0 )
1666  {
1667  isValid = FALSE;
1668  SCIPerrorMessage("Input graph invalid: Wrong number of terminals, count is %d, should be %d\n",
1669  g->terms, g->terms - nterms);
1670
1671  goto EXIT;
1672  }
1673
1674  if( (g->source < 0 ) || (g->source >= g->knots) || (g->term[g->source] != 0) )
1675  {
1676  isValid = FALSE;
1677  SCIPerrorMessage("Input graph invalid: Root invalid, root %d, terminal state %d\n",
1678  g->source + 1, g->term[g->source]);
1679
1680  goto EXIT;
1681  }
1682
1683  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &nodevisited, nnodes) );
1684  SCIP_CALL_ABORT( graph_trail_arr(scip, g, g->source, nodevisited) );
1685
1686  for( int k = 0; k < nnodes; k++ )
1687  {
1688  if( (g->grad[k] == 0) && ((g->inpbeg[k] != EAT_LAST) || (g->outbeg[k] != EAT_LAST)) )
1689  {
1690  isValid = FALSE;
1691  SCIPerrorMessage("Input graph invalid: Node %d of degree 0 has edges \n", k + 1);
1692
1693  goto EXIT;
1694  }
1695
1696  if( !nodevisited[k] && ((g->grad[k] > 0) || (Is_term(g->term[k]))) )
1697  {
1698  if( graph_pc_isPcMw(g) && !graph_pc_knotIsFixedTerm(g, k) )
1699  {
1700  continue;
1701  }
1702
1703  isValid = FALSE;
1704  SCIPerrorMessage("Input graph invalid: Node %d not connected to terminal node %d \n", k + 1, g->source + 1);
1705
1706  goto EXIT;
1707  }
1708  }
1709
1710  if( isValid && graph_pc_isPcMw(g) )
1711  {
1712  isValid = graphisValidPcMw(scip, g, nodevisited);
1713
1714  if( !isValid )
1715  {
1716  SCIPerrorMessage("Input graph invalid (non-standard Steiner tree specific error) \n");
1717  }
1718  }
1719
1720
1721  EXIT:
1722
1723  SCIPfreeBufferArrayNull(scip, &nodevisited);
1724  return isValid;
1725 }
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
int graph_edge_nPseudoAncestors(const GRAPH *, int)
static volatile int nterms
Definition: interrupt.c:38
int *RESTRICT mincut_e
Definition: graphdefs.h:250
SCIP_Bool graph_pc_isMw(const GRAPH *)
void graph_show(const GRAPH *p)
Definition: graph_base.c:1251
Definition: graphdefs.h:224
int *RESTRICT mincut_x
Definition: graphdefs.h:251
int *RESTRICT orgtail
Definition: graphdefs.h:225
int source
Definition: graphdefs.h:195
SCIP_Bool graph_pc_isRootedPcMw(const GRAPH *)
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip_mem.h:72
#define Is_term(a)
Definition: graphdefs.h:102
SCIP_RETCODE graph_copy(SCIP *scip, const GRAPH *orggraph, GRAPH **copygraph)
Definition: graph_base.c:939
SCIP_Bool graph_validInput(SCIP *scip, const GRAPH *g)
Definition: graph_base.c:1619
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
int terms
Definition: graphdefs.h:192
SCIP_Bool graph_mincut_isInitialized(const GRAPH *)
Definition: graph_mcut.c:1139
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
void graph_free_dcsr(SCIP *, GRAPH *)
Definition: graph_util.c:1807
int norgmodeledges
Definition: graphdefs.h:215
int *RESTRICT maxdeg
Definition: graphdefs.h:206
static SCIP_RETCODE packPcMwVanished(SCIP *scip, GRAPH *g_old)
Definition: graph_base.c:216
SCIP_Bool graph_pc_term2edgeIsConsistent(SCIP *, const GRAPH *)
Definition: graph_pcbase.c:874
void graph_knot_printInfo(const GRAPH *, int)
Definition: graph_stats.c:151
SCIP_RETCODE graph_fixed_addNodePc(SCIP *, int, GRAPH *)
int *RESTRICT mincut_temp
Definition: graphdefs.h:249
#define EAT_FREE
Definition: graphdefs.h:57
#define FALSE
Definition: def.h:87
int *RESTRICT inpbeg
Definition: graphdefs.h:202
int *RESTRICT path_state
Definition: graphdefs.h:256
#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
#define STP_DCSTP
Definition: graphdefs.h:47
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
#define EAT_LAST
Definition: graphdefs.h:58
#define SCIPdebugMessage
Definition: pub_message.h:87
#define FARAWAY
Definition: graphdefs.h:89
SCIP_Real graph_pc_getNonLeafTermOffset(SCIP *, const GRAPH *)
SCIP_Real * costbudget
Definition: graphdefs.h:211
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_Real * cost_org_pc
Definition: graphdefs.h:222
Definition: graphdefs.h:226
header only, simple implementation of an STL like vector
SCIP_Bool graph_valid(SCIP *scip, const GRAPH *g)
Definition: graph_base.c:1480
CSR * csr_storage
Definition: graphdefs.h:270
void graph_getEdgeCosts(const GRAPH *graph, SCIP_Real *RESTRICT cost, SCIP_Real *RESTRICT costrev)
Definition: graph_base.c:500
SCIP_RETCODE graph_initAncestors(SCIP *, GRAPH *)
int *RESTRICT mark
Definition: graphdefs.h:198
void graph_getEdgeRevCosts(const GRAPH *graph, SCIP_Real *RESTRICT costrev)
Definition: graph_base.c:521
SCIP_Bool graph_pc_termIsNonLeafTerm(const GRAPH *, int)
SCIP_RETCODE graph_pack(SCIP *scip, GRAPH *graph, GRAPH **newgraph, REDSOL *redsol, SCIP_Bool verbose)
Definition: graph_base.c:1324
SCIP_RETCODE graph_init(SCIP *scip, GRAPH **g, int ksize, int esize, int layers)
Definition: graph_base.c:607
SCIP_RETCODE graph_pc_initSubgraph(SCIP *, GRAPH *)
Definition: graph_pcbase.c:763
void graph_mark(GRAPH *g)
Definition: graph_base.c:1130
static SCIP_Bool graphisValidPcMw(SCIP *scip, const GRAPH *g, SCIP_Bool *nodevisited)
Definition: graph_base.c:49
#define STP_RSMT
Definition: graphdefs.h:49
int *RESTRICT oeat
Definition: graphdefs.h:231
#define GE(a, b)
Definition: portab.h:85
int *RESTRICT mincut_dist
Definition: graphdefs.h:243
miscellaneous methods used for solving Steiner problems
SCIP_Bool withInexactReductions
Definition: graphdefs.h:266
void graph_freePseudoAncestors(SCIP *, GRAPH *)
SCIP_Bool extended
Definition: graphdefs.h:267
int stp_type
Definition: graphdefs.h:264
IDX ** ancestors
Definition: graphdefs.h:234
int orgedges
Definition: graphdefs.h:220
FIXED * fixedcomponents
Definition: graphdefs.h:237
#define SCIPerrorMessage
Definition: pub_message.h:55
void graph_free_fixed(SCIP *, GRAPH *)
void graph_edge_addSubgraph(SCIP *, const GRAPH *, const int *, int, GRAPH *)
Definition: graph_edge.c:341
SCIP_Real budget
Definition: graphdefs.h:212
PSEUDOANS * pseudoancestors
Definition: graphdefs.h:236
SCIP_RETCODE graph_pseudoAncestors_appendCopyArrayToEdge(SCIP *, int, const int *, int, GRAPH *, SCIP_Bool *)
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:128
SCIP_Real * prize
Definition: graphdefs.h:210
void graph_edge_add(SCIP *, GRAPH *, int, int, double, double)
#define SCIPreallocMemoryArray(scip, ptr, newnum)
Definition: scip_mem.h:61
Definition: graphdefs.h:201
Definition: graph_node.c:64
void graph_freeHistoryDeep(SCIP *scip, GRAPH *p)
Definition: graph_base.c:900
static void packNodes(SCIP *scip, GRAPH *g_old, GRAPH *g_new)
Definition: graph_base.c:272
internal miscellaneous methods
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_RETCODE graph_initPseudoAncestors(SCIP *, GRAPH *)
#define EQ(a, b)
Definition: portab.h:79
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
int mincut_nedges
Definition: graphdefs.h:242
int * term2edge
Definition: graphdefs.h:208
IDX ** pcancestors
Definition: graphdefs.h:235
int orgknots
Definition: graphdefs.h:191
SCIP_RETCODE graph_copyData(SCIP *scip, const GRAPH *orgraph, GRAPH *copygraph)
Definition: graph_base.c:957
Definition: graphdefs.h:244
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
static SCIP_RETCODE packPcMwInit(SCIP *scip, int nnodes_new, GRAPH *g_old, GRAPH *g_new)
Definition: graph_base.c:250
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
void graph_getIsTermArray(const GRAPH *g, SCIP_Bool *isterm)
Definition: graph_base.c:540
SCIP_RETCODE graph_pc_finalizeSubgraph(SCIP *, GRAPH *)
Definition: graph_pcbase.c:795
#define SCIP_Bool
Definition: def.h:84
int *RESTRICT ieat
Definition: graphdefs.h:230
int *RESTRICT path_heap
Definition: graphdefs.h:255
void graph_mincut_exit(SCIP *, GRAPH *)
Definition: graph_mcut.c:1175
void reduce_solPack(const GRAPH *, const int *, int, REDSOL *)
Definition: reduce_sol.c:846
int *RESTRICT tail
Definition: graphdefs.h:223
SCIP_Bool graph_isMarked(const GRAPH *g)
Definition: graph_base.c:1165
void SCIPrandomPermuteIntArray(SCIP_RANDNUMGEN *randnumgen, int *array, int begin, int end)
Definition: misc.c:10044
#define flipedge(edge)
Definition: graphdefs.h:84
static SCIP_RETCODE packEdges(SCIP *scip, const int *old2newNode, GRAPH *g_old, int nnodes, int nedges, GRAPH *g_new)
Definition: graph_base.c:381
const int * graph_edge_getPseudoAncestors(const GRAPH *, int)
int *RESTRICT term
Definition: graphdefs.h:196
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
SCIP_RETCODE graph_getTermsRandom(SCIP *scip, const GRAPH *g, int *terms)
Definition: graph_base.c:588
SCIP_RETCODE graph_resize(SCIP *scip, GRAPH *g, int ksize, int esize, int layers)
Definition: graph_base.c:744
SCIP_Bool graph_pc_knotIsNonLeafTerm(const GRAPH *, int)
void graph_edge_delHistory(SCIP *, GRAPH *, int)
Definition: graph_edge.c:466
int mincut_nnodes
Definition: graphdefs.h:241
int *RESTRICT mincut_prev
Definition: graphdefs.h:247
SCIP_RETCODE graph_trail_costAware(SCIP *, const GRAPH *, int, SCIP_Bool *)
Definition: graph_util.c:353
void graph_path_exit(SCIP *, GRAPH *)
Definition: graph_path.c:515
int grid_dim
Definition: graphdefs.h:259
SCIP_Bool graph_pc_isPc(const GRAPH *)
int ** grid_coordinates
Definition: graphdefs.h:261
Portable definitions.
int *RESTRICT mincut_numb
Definition: graphdefs.h:246
int layers
Definition: graphdefs.h:193
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
void graph_free(SCIP *scip, GRAPH **graph, SCIP_Bool final)
Definition: graph_base.c:796
SCIP_RETCODE graph_trail_arr(SCIP *, const GRAPH *, int, SCIP_Bool *)
Definition: graph_util.c:336
#define Is_pseudoTerm(a)
Definition: graphdefs.h:103
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
SCIP_RETCODE graph_buildCompleteGraph(SCIP *scip, GRAPH **g, int nnodes)
Definition: graph_base.c:440
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *, int)
SCIP_Real * cost
Definition: graphdefs.h:221
int *RESTRICT rootedgeprevs
Definition: graphdefs.h:227
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
SCIP_Real * reduce_solGetOffsetPointer(REDSOL *)
Definition: reduce_sol.c:1285
int * contracttrace
Definition: graphdefs.h:238
SCIP_Bool graph_isSetUp(const GRAPH *g)
Definition: graph_base.c:1240
#define SCIP_Real
Definition: def.h:177
int esize
Definition: graphdefs.h:218
SCIP_RETCODE graph_copyPseudoAncestors(SCIP *scip, const GRAPH *orggraph, GRAPH *copygraph)
Definition: graph_base.c:1088
static SCIP_RETCODE packPseudoAncestors(SCIP *scip, const GRAPH *g_old, GRAPH *g_new)
Definition: graph_base.c:328
void graph_free_csr(SCIP *, GRAPH *)
Definition: graph_util.c:1623
int *RESTRICT outbeg
Definition: graphdefs.h:204
#define STP_BRMWCSP
Definition: graphdefs.h:55
shortest paths based primal heuristics for Steiner problems
int edges
Definition: graphdefs.h:219
int graph_getNpseudoAncestors(const GRAPH *)
int * grid_ncoords
Definition: graphdefs.h:260
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
void graph_getTerms(const GRAPH *g, int *terms)
Definition: graph_base.c:567
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
int ksize
Definition: graphdefs.h:189
void graph_uncover(GRAPH *g)
Definition: graph_base.c:1276
#define UNKNOWN
Definition: sepa_mcf.c:4095
SCIP_RETCODE graph_initHistory(SCIP *scip, GRAPH *graph)
Definition: graph_base.c:695
int *RESTRICT mincut_r
Definition: graphdefs.h:252
#define EAT_HIDE
Definition: graphdefs.h:59
#define nnodes
Definition: gastrans.c:65
DCSR * dcsr_storage
Definition: graphdefs.h:271
struct Int_List_Node * parent
Definition: misc_stp.h:91
int norgmodelterms
Definition: graphdefs.h:188
#define SCIP_CALL_ABORT(x)
Definition: def.h:363
int hoplimit
Definition: graphdefs.h:216
SCIP_Bool is_packed
Definition: graphdefs.h:265
void graph_freeHistory(SCIP *scip, GRAPH *p)
Definition: graph_base.c:868
includes various reduction methods for Steiner tree problems
void graph_getCsr(const GRAPH *g, int *RESTRICT edgearr, int *RESTRICT tailarr, int *RESTRICT start, int *nnewedges)
Definition: graph_base.c:468
SCIP_Bool graph_path_exists(const GRAPH *)
Definition: graph_path.c:497
int *RESTRICT mincut_next
Definition: graphdefs.h:248
int norgmodelknots
Definition: graphdefs.h:187
int orgsource
Definition: graphdefs.h:194