Scippy

SCIP

Solving Constraint Integer Programs

graph_util.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_util.c
17  * @brief includes graph utility methods for Steiner problems
18  * @author Daniel Rehfeldt
19  *
20  * Graph utility methods for Steiner problems, such as CSR data structure
21  *
22  */
23 
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
25 
26 /*lint -esym(766,stdlib.h) -esym(766,malloc.h) */
27 /*lint -esym(766,string.h) */
28 
29 #define DHEAP_MAX_KEY (1e20)
30 #define DHEAP_MIN_KEY -(1e20)
31 
32 #include "graph.h"
33 #include "reduce.h"
34 #include "portab.h"
35 
36 
37 /** CSR like graph storage */
39 {
40  int* all_starts; /**< all start positions (size datasize_max) */
41  int* all_heads; /**< all edge heads (size datasize_max) */
42  SCIP_Real* all_costs; /**< all edge costs (size datasize_max) */
43  int* csr_ptrsStart; /**< gives start index to start of start array (size ncsrs_max + 1) */
44  int* csr_ptrsData; /**< gives start index to start of heads/costs arrays (size ncsrs_max + 1) */
45  SCIP_Bool* csr_isEmpty; /**< per entry: is empty? (size ncsrs_max) */
46  int datasize_max; /**< maximum size of depository */
47  int ncsrs_curr; /**< current number of CSRS */
48  int ncsrs_max; /**< maximum number of CSRS */
49 #ifndef NDEBUG
50  SCIP_Real* csr_weight; /**< sum of edge weights of CSR (size ncsrs_max) */
51  int* csr_nedges; /**< per entry: number of (directed!) edges (size ncsrs_max) */
52  int* csr_nnodes; /**< per entry: number of nodes (size ncsrs_max) */
53 #endif
54 };
55 
56 
57 
58 /** traverses the graph from vertex 'start' and marks all reached nodes */
59 static
61  SCIP* scip, /**< SCIP */
62  const GRAPH* g, /**< the new graph */
63  int start, /**< node to start from */
64  SCIP_Bool costAware, /**< be cost aware? */
65  SCIP_Bool* nodevisited /**< marks which node has been visited */
66  )
67 {
68  int* RESTRICT stackarr;
69  int stacksize;
70  const int nnodes = g->knots;
71 
72  for( int i = 0; i < nnodes; i++ )
73  nodevisited[i] = FALSE;
74 
75  nodevisited[start] = TRUE;
76 
77  if( g->grad[start] == 0 )
78  return SCIP_OKAY;
79 
80  stacksize = 0;
81 
82  SCIP_CALL(SCIPallocBufferArray(scip, &stackarr, nnodes));
83 
84  stackarr[stacksize++] = start;
85 
86  /* DFS loop */
87  while( stacksize != 0 )
88  {
89  const int node = stackarr[--stacksize];
90 
91  /* traverse outgoing arcs */
92  for( int a = g->outbeg[node]; a != EAT_LAST; a = g->oeat[a] )
93  {
94  const int head = g->head[a];
95 
96  if( !nodevisited[head] )
97  {
98  if( costAware && GE(g->cost[a], FARAWAY) )
99  continue;
100 
101  nodevisited[head] = TRUE;
102  stackarr[stacksize++] = head;
103  }
104  }
105  }
106  SCIPfreeBufferArray(scip, &stackarr);
107 
108  return SCIP_OKAY;
109 }
110 
111 #ifndef NDEBUG
112 /** has the CSR been initialized? */
113 static
115  const CSR* csr, /**< pointer to CSR struct to fill */
116  SCIP_Bool verbose /**< be verbose? */
117  )
118 {
119  assert(csr);
120 
121  for( int i = 0; i <= csr->nnodes; i++ )
122  {
123  if( csr->start[i] < 0 )
124  {
125  if( verbose )
126  printf("CSR not set: unset start pointer for entry %d \n", i);
127 
128  return FALSE;
129  }
130  }
131 
132 
133  for( int i = 0; i < csr->nedges_max; i++ )
134  {
135  if( LT(csr->cost[i], 0.0) )
136  {
137  if( verbose )
138  printf("CSR not set: negative cost for entry %d \n", i);
139 
140  return FALSE;
141  }
142  }
143 
144  for( int i = 0; i < csr->nedges_max; i++ )
145  {
146  if( csr->head[i] < 0 )
147  {
148  if( verbose )
149  printf("CSR not set: unset head for entry %d \n", i);
150 
151  return FALSE;
152  }
153  }
154 
155  return TRUE;
156 }
157 
158 
159 /** de-initialize CSR (in debug mode) */
160 static
162  CSR* csr /**< pointer to CSR struct to fill */
163 )
164 {
165  for( int i = 0; i <= csr->nnodes; i++ )
166  csr->start[i] = -1;
167 
168  for( int i = 0; i < csr->nedges_max; i++ )
169  csr->cost[i] = -1.0;
170 
171  for( int i = 0; i < csr->nedges_max; i++ )
172  csr->head[i] = -1;
173 }
174 
175 
176 /** cleaning (in debug mode) */
177 static
179  CSRDEPO* depository /**< the depository */
180 )
181 {
182  const int ncsrs_max = depository->ncsrs_max;
183  const int datasize_max = depository->datasize_max;
184 
185  assert(depository->csr_ptrsStart[0] == 0);
186  assert(depository->csr_ptrsData[0] == 0);
187 
188  for( int i = 0; i < ncsrs_max; ++i )
189  {
190  depository->csr_nedges[i] = -1;
191  depository->csr_nnodes[i] = -1;
192  depository->csr_weight[i] = -1.0;
193  }
194 
195  for( int i = 0; i <= ncsrs_max; ++i )
196  {
197  depository->csr_ptrsStart[i] = -1;
198  depository->csr_ptrsData[i] = -1;
199  }
200 
201  for( int i = 0; i < datasize_max; ++i )
202  {
203  depository->all_starts[i] = -1;
204  depository->all_heads[i] = -1;
205  depository->all_costs[i] = -1.0;
206  }
207 
208  depository->csr_ptrsStart[0] = 0;
209  depository->csr_ptrsData[0] = 0;
210 }
211 
212 
213 /** gets top CSR edge weight */
214 static
216  const CSR* csr /**< pointer to CSR struct to fill */
217 )
218 {
219  SCIP_Real weight = 0.0;
220 
221  assert(csr);
222 
223  for( int i = 0; i < csr->nedges_max; i++ )
224  weight += csr->cost[i];
225 
226  return weight;
227 }
228 
229 
230 /** gets top CSR edge weight */
231 static
233  const CSRDEPO* depository /**< the depository */
234 )
235 {
236  CSR topcsr;
237  const int topindex = depository->ncsrs_curr - 1;
238 
239  graph_csrdepo_getCSR(depository, topindex, &topcsr);
240 
241  return csrdepoCsrWeight(&topcsr);
242 }
243 #endif
244 
245 
246 /** gets top index */
247 static inline
249  const CSRDEPO* depository /**< the depository */
250 )
251 {
252  assert(depository);
253  assert(depository->ncsrs_curr >= 1);
254 
255  return (depository->ncsrs_curr - 1);
256 }
257 
258 
259 
260 /** gets number of nodes of CSR stored at position 'index' */
261 static inline
263  const CSRDEPO* depository, /**< the depository */
264  int index /**< the index of the CSR */
265  )
266 {
267  assert(index >= 0 && index < depository->ncsrs_curr);
268 
269 #ifndef NDEBUG
270  {
271  const int nnodes = depository->csr_ptrsStart[index + 1] - depository->csr_ptrsStart[index] - 1;
272  assert(nnodes == depository->csr_nnodes[index]);
273  assert(nnodes >= 0);
274  }
275 #endif
276 
277  return (depository->csr_ptrsStart[index + 1] - depository->csr_ptrsStart[index] - 1);
278 }
279 
280 
281 /** gets number of edges of CSR stored at position 'index' */
282 static inline
284  const CSRDEPO* depository, /**< the depository */
285  int index /**< the index of the CSR */
286  )
287 {
288  assert(index >= 0 && index < depository->ncsrs_curr);
289 
290 #ifndef NDEBUG
291  {
292  const int nedges = depository->csr_ptrsData[index + 1] - depository->csr_ptrsData[index];
293  assert(nedges == depository->csr_nedges[index]);
294  }
295 #endif
296 
297 
298  return (depository->csr_ptrsData[index + 1] - depository->csr_ptrsData[index]);
299 }
300 
301 
302 /** fills the CSR structure */
303 static inline
305  const CSRDEPO* depository, /**< the depository */
306  int index, /**< the index */
307  CSR* csr /**< pointer to CSR struct to fill */
308 )
309 {
310  const int nnodes = csrdepoGetNnodes(depository, index);
311  const int nedges = csrdepoGetNedges(depository, index);
312  const int ptr_start = depository->csr_ptrsStart[index];
313  const int ptr_data = depository->csr_ptrsData[index];
314 
315  assert(ptr_start >= 0);
316  assert(ptr_data >= 0);
317 
318  /* fill the entries of the CSR */
319  csr->edge_id = NULL;
320  csr->start = &(depository->all_starts[ptr_start]);
321  csr->head = &(depository->all_heads[ptr_data]);
322  csr->cost = &(depository->all_costs[ptr_data]);
323  csr->nedges_max = nedges;
324  csr->nnodes = nnodes;
325 }
326 
327 
328 /*
329  * Misc
330  */
331 
332 
333 
334 
335 /** traverses the graph from vertex 'start' and marks all reached nodes */
337  SCIP* scip, /**< SCIP */
338  const GRAPH* g, /**< the new graph */
339  int start, /**< node to start from */
340  SCIP_Bool* nodevisited /**< marks which node has been visited */
341  )
342 {
343  assert(g && scip && nodevisited);
344  assert(start >= 0 && start < g->knots);
345 
346  trail(scip, g, start, FALSE, nodevisited);
347 
348  return SCIP_OKAY;
349 }
350 
351 
352 /** traverses the graph and marks all reached nodes, does not take edge of cost >= FARAWAY */
354  SCIP* scip, /**< SCIP */
355  const GRAPH* g, /**< the new graph */
356  int start, /**< node to start from */
357  SCIP_Bool* nodevisited /**< marks which node has been visited */
358  )
359 {
360  assert(g && scip && nodevisited);
361  assert(start >= 0 && start < g->knots);
362 
363  trail(scip, g, start, TRUE, nodevisited);
364 
365  return SCIP_OKAY;
366 }
367 
368 
369 /** checks whether all terminals are reachable from root */
371  SCIP* scip, /**< scip struct */
372  const GRAPH* g, /**< the new graph */
373  SCIP_Bool* reachable /**< are they reachable? */
374  )
375 {
376  const int nnodes = g->knots;
377  SCIP_Bool* nodevisited;
378 
379  assert(g != NULL);
380  assert(reachable != NULL);
381 
382  *reachable = TRUE;
383 
384  SCIP_CALL( SCIPallocBufferArray(scip, &nodevisited, nnodes) );
385  SCIP_CALL( graph_trail_arr(scip, g, g->source, nodevisited) );
386 
387  for( int k = 0; k < nnodes; k++ )
388  {
389  if( Is_term(g->term[k]) && !nodevisited[k] )
390  {
391  *reachable = FALSE;
392  break;
393  }
394  }
395 
396  SCIPfreeBufferArray(scip, &nodevisited);
397 
398  return SCIP_OKAY;
399 }
400 
401 
402 /*
403  * distinguishes a terminal as the root; with centertype
404  * = CENTER_OK : Do nothing
405  * = CENTER_DEG : find maximum degree
406  * = CENTER_SUM : find the minimum distance sum
407  * = CENTER_MIN : find the minimum largest distance
408  * = CENTER_ALL : find the minimum distance sum to all knots
409  */
411  SCIP* scip, /**< SCIP data structure */
412  const GRAPH* g, /**< graph data structure */
413  int centertype, /**< type of root selection */
414  int* central_term /**< pointer to store the selected (terminal) vertex */
415  )
416 {
417  PATH* path;
418  double* cost;
419  int i;
420  int k;
421  int center = -1;
422  int degree = 0;
423  double sum;
424  double max;
425  double minimum = FARAWAY;
426  double maximum = 0.0;
427  double oldval = 0.0;
428  const int nnodes = graph_get_nNodes(g);
429 
430  assert(g->layers == 1);
431  assert(centertype == STP_CENTER_OK || centertype == STP_CENTER_DEG ||
432  centertype == STP_CENTER_SUM || centertype == STP_CENTER_MIN || centertype == STP_CENTER_ALL );
433 
434  *central_term = g->source;
435 
436  assert(g->stp_type != STP_NWPTSPG );
437 
438 
439  if( centertype == STP_CENTER_OK || g->grad[g->source] == 0)
440  {
441  assert(Is_term(g->term[*central_term]));
442 
443  return SCIP_OKAY;
444  }
445 
446  /* Find knot of maximum degree.
447  */
448  if( centertype == STP_CENTER_DEG )
449  {
450  degree = 0;
451 
452  for( i = 0; i < nnodes; i++ )
453  {
454  if( Is_term(g->term[i]) && (g->grad[i] > degree) )
455  {
456  degree = g->grad[i];
457  center = i;
458  }
459  }
460 
461  assert(degree > 0);
462  assert(Is_term(g->term[center]));
463 
464  *central_term = center;
465 
466  return SCIP_OKAY;
467  }
468 
469  /* For the other methods we need the shortest paths */
470  SCIP_CALL( SCIPallocBufferArray(scip, &path, nnodes) );
471  SCIP_CALL( SCIPallocBufferArray(scip, &cost, g->edges) );
472 
473  assert(path != NULL);
474  assert(cost != NULL);
475 
476  for( i = 0; i < nnodes; i++ )
477  g->mark[i] = TRUE;
478 
479  for( i = 0; i < g->edges; i++ )
480  cost[i] = 1.0;
481 
482  for( i = 0; i < nnodes; i++ )
483  {
484  if (!Is_term(g->term[i]))
485  continue;
486 
487  if( g->stp_type == STP_NWPTSPG && graph_knotIsNWLeaf(g, i) )
488  continue;
489 
490  graph_path_exec(scip, g, FSP_MODE, i, cost, path);
491 
492  sum = 0.0;
493  max = 0.0;
494 
495  for( k = 0; k < nnodes; k++ )
496  {
497  assert((path[k].edge >= 0) || (k == i));
498  assert((path[k].edge >= 0) || (path[k].dist == 0));
499 
500  if( Is_term(g->term[k]) || (centertype == STP_CENTER_ALL) )
501  {
502  sum += path[k].dist;
503 
504  if( path[k].dist > max )
505  max = path[k].dist;
506  }
507  }
508 
509  if( (centertype == STP_CENTER_SUM) || (centertype == STP_CENTER_ALL) )
510  {
511  if( sum < minimum )
512  {
513  minimum = sum;
514  center = i;
515  }
516  if( sum > maximum )
517  maximum = sum;
518 
519  if( i == g->source )
520  oldval = sum;
521  }
522  else
523  {
524  assert(centertype == STP_CENTER_MIN);
525 
526  /* If the maximum distance to terminal ist shorter or if
527  * it is of the same length but the degree of the knot is
528  * higher, we change the center.
529  */
530  if( SCIPisLT(scip, max, minimum) || (SCIPisEQ(scip, max, minimum) && (g->grad[i] > degree)) )
531  {
532  minimum = max;
533  center = i;
534  degree = g->grad[i];
535  }
536  if( max > maximum )
537  maximum = max;
538 
539  if( i == g->source )
540  oldval = max;
541  }
542  }
543  assert(center >= 0);
544  assert(Is_term(g->term[center]));
545 
546  SCIPfreeBufferArray(scip, &cost);
547  SCIPfreeBufferArray(scip, &path);
548 
549  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Central Terminal is %d (min=%g, max=%g, old=%g)\n",
550  center, minimum, maximum, oldval);
551 
552  assert(Is_term(g->term[center]));
553  *central_term = center;
554 
555  return SCIP_OKAY;
556 }
557 
558 
559 /** builds mapping from original vertices to non-zero degree ones */
561  const GRAPH* g, /**< the graph */
562  int* map /**< map */
563 )
564 {
565  int nodescount = 0;
566  const int nnodes = graph_get_nNodes(g);
567 
568  assert(map);
569 
570  for( int i = 0; i < nnodes; i++ )
571  {
572  if( g->grad[i] == 0 )
573  {
574  map[i] = UNKNOWN;
575  }
576  else
577  {
578  map[i] = nodescount++;
579  }
580  }
581 }
582 
583 
584 
585 /*
586  * CSR Depository
587  */
588 
589 /** initializes CSR depository */
591  SCIP* scip, /**< SCIP data structure */
592  int ncsrs_max, /**< maximum number of CSRs */
593  int datasize_max, /**< the maximum capacity */
594  CSRDEPO** depository /**< the depository */
595  )
596 {
597  CSRDEPO* depo;
598 
599  assert(scip);
600  assert(ncsrs_max >= 1);
601  assert(ncsrs_max < datasize_max);
602 
603  SCIP_CALL( SCIPallocMemory(scip, depository) );
604 
605  depo = *depository;
606 
607  SCIP_CALL( SCIPallocMemoryArray(scip, &(depo->all_starts), datasize_max) );
608  SCIP_CALL( SCIPallocMemoryArray(scip, &(depo->all_heads), datasize_max) );
609  SCIP_CALL( SCIPallocMemoryArray(scip, &(depo->all_costs), datasize_max) );
610 
611  SCIP_CALL( SCIPallocMemoryArray(scip, &(depo->csr_ptrsStart), ncsrs_max + 1) );
612  SCIP_CALL( SCIPallocMemoryArray(scip, &(depo->csr_ptrsData), ncsrs_max + 1) );
613  SCIP_CALL( SCIPallocMemoryArray(scip, &(depo->csr_isEmpty), ncsrs_max) );
614 
615  depo->ncsrs_curr = 0;
616  depo->ncsrs_max = ncsrs_max;
617  depo->datasize_max = datasize_max;
618 
619  depo->csr_ptrsStart[0] = 0;
620  depo->csr_ptrsData[0] = 0;
621 
622 #ifndef NDEBUG
623  SCIP_CALL( SCIPallocMemoryArray(scip, &(depo->csr_nedges), ncsrs_max) );
624  SCIP_CALL( SCIPallocMemoryArray(scip, &(depo->csr_nnodes), ncsrs_max) );
625  SCIP_CALL( SCIPallocMemoryArray(scip, &(depo->csr_weight), ncsrs_max) );
626 
627  csrdepoCleanDebug(depo);
628 #endif
629 
630  assert(graph_csrdepo_isEmpty(*depository));
631 
632  return SCIP_OKAY;
633 }
634 
635 
636 /** frees CSR depository */
638  SCIP* scip, /**< SCIP data structure */
639  CSRDEPO** depository /**< the depository */
640  )
641 {
642  CSRDEPO* depo;
643 
644  assert(scip && depository && *depository);
645 
646  depo = *depository;
647 
648 #ifndef NDEBUG
649  SCIPfreeMemoryArray(scip, &(depo->csr_nnodes));
650  SCIPfreeMemoryArray(scip, &(depo->csr_nedges));
651  SCIPfreeMemoryArray(scip, &(depo->csr_weight));
652 #endif
653 
654  SCIPfreeMemoryArray(scip, &(depo->csr_isEmpty));
655  SCIPfreeMemoryArray(scip, &(depo->csr_ptrsData));
656  SCIPfreeMemoryArray(scip, &(depo->csr_ptrsStart));
657 
658  SCIPfreeMemoryArray(scip, &(depo->all_costs));
659  SCIPfreeMemoryArray(scip, &(depo->all_heads));
660  SCIPfreeMemoryArray(scip, &(depo->all_starts));
661 
662  SCIPfreeMemory(scip, depository);
663 }
664 
665 
666 /** gets CSR from depository */
668  const CSRDEPO* depository, /**< the depository */
669  int index, /**< the index of the CSR to get */
670  CSR* csr /**< pointer to CSR struct to fill */
671  )
672 {
673  assert(depository && csr);
674  assert(index >= 0 && index < depository->ncsrs_curr);
675  assert(!depository->csr_isEmpty[index]);
676 
677  csrdepoFillCSR(depository, index, csr);
678 
679  assert(csr->start[0] == 0);
680 }
681 
682 
683 /** gets top (last added) CSR from depository */
685  const CSRDEPO* depository, /**< the depository */
686  CSR* csr /**< pointer to CSR struct to fill */
687  )
688 {
689  assert(depository && csr);
690  assert(depository->ncsrs_curr >= 1);
691  assert(!graph_csrdepo_hasEmptyTop(depository));
692 
693  graph_csrdepo_getCSR(depository, csrdepoGetTopIndex(depository), csr);
694 
695 #ifndef NDEBUG
696  {
697  const SCIP_Real weight_org = depository->csr_weight[csrdepoGetTopIndex(depository)];
698  const SCIP_Real weight_real = csrdepoCsrWeight(csr);
699 
700  assert(EQ(weight_org, weight_real));
701  }
702 #endif
703  assert(csrdepoCsrIsSet(csr, FALSE));
704 
705 }
706 
707 
708 /** gets current size of data (from all CSRs) in depository */
710  const CSRDEPO* depository /**< the depository */
711  )
712 {
713  assert(depository);
714  assert(depository->ncsrs_curr >= 0);
715 
716  if( depository->ncsrs_curr == 0 )
717  {
718  return 0;
719  }
720  else
721  {
722  const int top_index = csrdepoGetTopIndex(depository);
723  const int top_nedges = csrdepoGetNedges(depository, top_index);
724  const int top_nnodes = csrdepoGetNnodes(depository, top_index);
725  const int datasize_edges = depository->csr_ptrsData[top_index] + top_nedges;
726  const int datasize_nodes = depository->csr_ptrsStart[top_index] + top_nnodes + 1;
727  const int datasize = MAX(datasize_edges, datasize_nodes);
728 
729 #ifndef NDEBUG
730  assert(top_nedges >= 0);
731  assert(top_nnodes >= 0);
732  assert(datasize <= depository->datasize_max);
733 #endif
734 
735  return datasize;
736  }
737 }
738 
739 
740 /** gets number of CSRs in depository */
742  const CSRDEPO* depository /**< the depository */
743  )
744 {
745  assert(depository);
746  assert(depository->ncsrs_curr >= 0);
747 
748  return depository->ncsrs_curr;
749 }
750 
751 
752 /** removes top of CSR depository */
754  CSRDEPO* depository /**< the depository */
755  )
756 {
757  assert(depository);
758  assert(depository->ncsrs_curr >= 1);
759 
760 #ifndef NDEBUG
761  {
762  CSR csr;
763  const int top_index = csrdepoGetTopIndex(depository);
764 
765  csrdepoFillCSR(depository, top_index, &csr);
766  csrdepoCsrUnsetDebug(&csr);
767 
768  depository->csr_nedges[top_index] = -1;
769  depository->csr_nnodes[top_index] = -1;
770  depository->csr_weight[top_index] = -1.0;
771  }
772 #endif
773 
774  depository->ncsrs_curr--;
775 
776  assert(graph_csrdepo_isEmpty(depository) || !graph_csrdepo_hasEmptyTop(depository));
777 }
778 
779 
780 /** cleans CSR depository */
782  CSRDEPO* depository /**< the depository */
783  )
784 {
785  assert(depository);
786 
787  for( int i = depository->ncsrs_curr - 1; i >= 0; --i )
788  {
789  graph_csrdepo_removeTop(depository);
790  }
791 
792 #ifndef NDEBUG
793  assert(graph_csrdepo_isEmpty(depository));
794  csrdepoCleanDebug(depository);
795 #endif
796 }
797 
798 
799 /** adds empty top to CSR depository */
801  CSRDEPO* depository, /**< the depository */
802  int nnodes, /**< nodes of new top */
803  int nedges /**< number of (directed!) edges of new top */
804  )
805 {
806  int topindex;
807 
808  assert(depository);
809  assert(nnodes >= 1 && nedges >= 0);
810  assert(graph_csrdepo_isEmpty(depository) || !graph_csrdepo_hasEmptyTop(depository));
811  assert(MAX(nnodes + 1, nedges) + graph_csrdepo_getDataSize(depository) < depository->datasize_max);
812  assert(depository->ncsrs_curr < depository->ncsrs_max);
813 
814  depository->ncsrs_curr++;
815 
816  topindex = csrdepoGetTopIndex(depository);
817 
818  depository->csr_ptrsStart[topindex + 1] = depository->csr_ptrsStart[topindex] + nnodes + 1;
819  depository->csr_ptrsData[topindex + 1] = depository->csr_ptrsData[topindex] + nedges;
820  depository->csr_isEmpty[topindex] = TRUE;
821 
822 #ifndef NDEBUG
823  assert(-1 == depository->csr_nnodes[topindex]);
824  assert(-1 == depository->csr_nedges[topindex]);
825  assert(EQ(depository->csr_weight[topindex], -1.0));
826 
827  depository->csr_nnodes[topindex] = nnodes;
828  depository->csr_nedges[topindex] = nedges;
829 
830  assert(graph_csrdepo_hasEmptyTop(depository));
831 #endif
832 }
833 
834 
835 /** adds empty top for tree to CSR depository */
837  CSRDEPO* depository, /**< the depository */
838  int nnodes /**< nodes of new top */
839  )
840 {
841  const int nedges = 2 * (nnodes - 1);
842 
843  assert(nnodes >= 1);
844  assert(nedges >= 0);
845 
846  graph_csrdepo_addEmptyTop(depository, nnodes, nedges);
847 }
848 
849 
850 /** is the CSR depository empty? */
852  const CSRDEPO* depository /**< the depository */
853  )
854 {
855  assert(depository);
856  assert(depository->ncsrs_curr >= 0);
857 
858  return (depository->ncsrs_curr == 0);
859 }
860 
861 
862 /** is top of CSR depository empty? */
864  const CSRDEPO* depository /**< the depository */
865  )
866 {
867  const int topindex = csrdepoGetTopIndex(depository);
868 
869  return depository->csr_isEmpty[topindex];
870 }
871 
872 
873 /** Gets empty top of current depository. */
875  const CSRDEPO* depository, /**< the depository */
876  CSR* csr /**< pointer to csr struct to fill */
877  )
878 {
879  const int topindex = csrdepoGetTopIndex(depository);
880 
881  assert(depository->csr_isEmpty[topindex]);
882  assert(topindex >= 0 && topindex < depository->ncsrs_max);
883  assert(csr);
884 
885  csrdepoFillCSR(depository, topindex, csr);
886 }
887 
888 
889 /** Sets formerly empty top to marked. */
891  CSRDEPO* depository /**< the depository */
892  )
893 {
894  const int topindex = csrdepoGetTopIndex(depository);
895 
896  assert(depository->csr_isEmpty[topindex]);
897  assert(EQ(depository->csr_weight[topindex], -1.0));
898 
899  depository->csr_isEmpty[topindex] = FALSE;
900 
901 #ifndef NDEBUG
902  depository->csr_weight[topindex] = csrdepoGetTopWeight(depository);
903 #endif
904 }
905 
906 
907 /** Prints depository. */
909  const CSRDEPO* depository /**< the depository */
910  )
911 {
912  CSR csr;
913  const int ncsrs = graph_csrdepo_getNcsrs(depository);
914 
915  printf("csrdepo (size=%d) contains: \n", ncsrs);
916 
917  for( int i = 0; i < ncsrs; ++i )
918  {
919  graph_csrdepo_getCSR(depository, i, &csr);
920 
921 #ifndef NDEBUG
922  printf("level %d: n=%d, m=%d w=%f \n", i, csr.nnodes, csr.nedges_max, depository->csr_weight[i] / 2.0);
923 #else
924  printf("level %d: n=%d, m=%d \n", i, csr.nnodes, csr.nedges_max);
925 
926 #endif
927  }
928 
929 }
930 
931 
932 /*
933  * Dijkstra heap
934  */
935 
936 /** clean the heap */
937 void
939  SCIP_Bool cleanposition, /**< clean position array? */
940  DHEAP* heap /**< the heap */
941  )
942 {
943  int* const position = heap->position;
944  const int capacity = heap->capacity;
945 
946  assert(heap && position);
947 
948  heap->size = 0;
949 
950  if( cleanposition )
951  {
952  for( int i = 0; i < capacity; i++ )
953  position[i] = UNKNOWN;
954 
955  assert(graph_heap_isClean(heap));
956  }
957 }
958 
959 
960 /** is the heap clean? */
961 SCIP_Bool
963  const DHEAP* heap /**< the heap */
964  )
965 {
966  const int* const position = heap->position;
967  const int capacity = heap->capacity;
968 
969  assert(heap && position);
970 
971  if( heap->size != 0 )
972  {
973  SCIPdebugMessage("heap size not 0! (=%d)\n", heap->size);
974  return FALSE;
975  }
976 
977  for( int i = 0; i < capacity; i++ )
978  {
979  if( UNKNOWN != position[i] )
980  {
981  SCIPdebugMessage("position %d is not clean \n", i);
982  return FALSE;
983  }
984  }
985 
986  return TRUE;
987 }
988 
989 
990 
991 /** creates new heap. If entries array is provided, it must be of size capacity + 2 */
993  SCIP* scip, /**< SCIP */
994  int capacity, /**< heap capacity */
995  int* position, /**< heap position array or NULL */
996  DENTRY* entries, /**< entries array or NULL */
997  DHEAP** heap /**< the heap */
998  )
999 {
1000  int* position_heap;
1001  DENTRY* entries_heap;
1002 
1003  assert(scip && heap);
1004  assert(capacity >= 1);
1005 
1006  SCIP_CALL( SCIPallocMemory(scip, heap) );
1007 
1008  if( position )
1009  position_heap = position;
1010  else
1011  SCIP_CALL( SCIPallocMemoryArray(scip, &(position_heap), capacity) );
1012 
1013  if( entries )
1014  entries_heap = entries;
1015  else
1016  SCIP_CALL( SCIPallocMemoryArray(scip, &(entries_heap), capacity + 2) );
1017 
1018  (*heap)->capacity = capacity;
1019  (*heap)->position = position_heap;
1020  (*heap)->entries = entries_heap;
1021 
1022  /* sentinel */
1023  entries_heap[0].key = DHEAP_MIN_KEY;
1024 
1025  /* debug sentinel */
1026  entries_heap[capacity + 1].key = DHEAP_MAX_KEY;
1027 
1028  graph_heap_clean(TRUE, *heap);
1029 
1030  return SCIP_OKAY;
1031 }
1032 
1033 /** frees the heap */
1035  SCIP* scip, /**< SCIP */
1036  SCIP_Bool freePositions, /**< free positions array? */
1037  SCIP_Bool freeEntries, /**< free entries array? */
1038  DHEAP** heap /**< the heap */
1039  )
1040 {
1041  assert(scip && heap);
1042 
1043  if( freePositions )
1044  SCIPfreeMemoryArray(scip, &((*heap)->position));
1045 
1046  if( freeEntries )
1047  SCIPfreeMemoryArray(scip, &((*heap)->entries));
1048 
1049  SCIPfreeMemory(scip, heap);
1050 }
1051 
1052 /** deletes heap minimum */
1054  int* node, /**< pointer to value of minimum */
1055  SCIP_Real* key, /**< pointer to key of minimum */
1056  DHEAP* heap /**< the heap */
1057  )
1058 {
1059  *key = heap->entries[1].key;
1060 
1061  graph_heap_deleteMinGetNode(node, heap);
1062 }
1063 
1064 /** deletes heap minimum */
1066  int* node, /**< pointer to node stored in minimum (set by method) */
1067  DHEAP* heap /**< the heap */
1068  )
1069 {
1070  assert(node);
1071  *node = graph_heap_deleteMinReturnNode(heap);
1072 }
1073 
1074 
1075 /** deletes heap minimum and returns corresponding node */
1077  DHEAP* heap /**< the heap */
1078  )
1079 {
1080  int* const RESTRICT position = heap->position;
1081  DENTRY* const RESTRICT entries = heap->entries;
1082  SCIP_Real fill;
1083  int parent;
1084  int hole = 1;
1085  int child = 2;
1086  int node;
1087  const int lastentry = heap->size--;
1088 
1089  assert(heap && position && entries);
1090  assert(heap->size >= 0);
1091 
1092  node = entries[1].node;
1093 
1094  assert(position[node] == 1);
1095 
1096  position[node] = CONNECT;
1097 
1098  /* move down along min-path */
1099  while( child < lastentry )
1100  {
1101  const SCIP_Real key1 = entries[child].key;
1102  const SCIP_Real key2 = entries[child + 1].key;
1103  assert(hole >= 1);
1104  assert(key1 < DHEAP_MAX_KEY && key2 < DHEAP_MAX_KEY);
1105 
1106  /* second child with smaller key? */
1107  if( key1 > key2 )
1108  {
1109  entries[hole].key = key2;
1110  child++;
1111  }
1112  else
1113  {
1114  entries[hole].key = key1;
1115  }
1116 
1117  assert(entries[hole].node >= 0 && entries[hole].node < heap->capacity);
1118 
1119  entries[hole].node = entries[child].node;
1120  position[entries[hole].node] = hole;
1121 
1122  hole = child;
1123  child *= 2;
1124  }
1125 
1126  /* now hole is at last tree level, fill it with last heap entry and move it up */
1127 
1128  fill = entries[lastentry].key;
1129  parent = hole / 2;
1130 
1131  assert(fill < DHEAP_MAX_KEY && entries[parent].key < DHEAP_MAX_KEY);
1132 
1133  while( entries[parent].key > fill )
1134  {
1135  assert(hole >= 1);
1136 
1137  entries[hole] = entries[parent];
1138 
1139  assert(entries[hole].node >= 0 && entries[hole].node < heap->capacity);
1140 
1141  position[entries[hole].node] = hole;
1142  hole = parent;
1143  parent /= 2;
1144 
1145  assert(entries[parent].key < DHEAP_MAX_KEY);
1146  }
1147 
1148  /* finally, fill the hole */
1149  entries[hole].key = fill;
1150  entries[hole].node = entries[lastentry].node;
1151 
1152  assert(entries[hole].node >= 0 && entries[hole].node < heap->capacity);
1153 
1154  if( hole != lastentry )
1155  position[entries[hole].node] = hole;
1156 
1157 #ifndef NDEBUG
1158  entries[lastentry].key = DHEAP_MAX_KEY; /* set debug sentinel */
1159 #endif
1160 
1161  return node;
1162 }
1163 
1164 
1165 /** corrects node position in heap according to new key (or newly inserts the node) */
1167  int node, /**< the node */
1168  SCIP_Real newkey, /**< the new key (needs to be smaller than current one) */
1169  DHEAP* heap /**< the heap */
1170  )
1171 {
1172  int* const RESTRICT position = heap->position;
1173  DENTRY* const RESTRICT entries = heap->entries;
1174  int hole;
1175  int parent;
1176  SCIP_Real parentkey;
1177 
1178  assert(heap && position && entries);
1179  assert(newkey < DHEAP_MAX_KEY && newkey > DHEAP_MIN_KEY);
1180  assert(heap->size <= heap->capacity);
1181  assert(node >= 0 && node <= heap->capacity);
1182  assert(position[node] != CONNECT);
1183 
1184  /* node not yet in heap? */
1185  if( position[node] == UNKNOWN )
1186  {
1187  assert(heap->size < heap->capacity);
1188  hole = ++(heap->size);
1189  }
1190  else
1191  {
1192  assert(position[node] >= 1);
1193  hole = position[node];
1194 
1195  assert(entries[hole].node == node);
1196  assert(GE(entries[hole].key, newkey));
1197  }
1198 
1199  parent = hole / 2;
1200  parentkey = entries[parent].key;
1201 
1202  assert(parentkey < DHEAP_MAX_KEY);
1203 
1204  /* move hole up */
1205  while( parentkey > newkey )
1206  {
1207  assert(hole >= 1);
1208 
1209  entries[hole].key = parentkey;
1210  entries[hole].node = entries[parent].node;
1211  position[entries[hole].node] = hole;
1212  hole = parent;
1213  parent /= 2;
1214  parentkey = entries[parent].key;
1215  assert(parentkey < DHEAP_MAX_KEY);
1216  }
1217 
1218  /* fill the hole */
1219  entries[hole].key = newkey;
1220  entries[hole].node = node;
1221  position[node] = hole;
1222 }
1223 
1224 
1225 /*
1226  * CSR
1227  */
1228 
1229 
1230 /** allocates empty (and invalid!) CSR storage */
1232  SCIP* scip, /**< SCIP data structure */
1233  int nnodes, /**< nodes */
1234  int nedges, /**< edges */
1235  CSR** csr /**< CSR */
1236  )
1237 {
1238  CSR* csrd;
1239 
1240  assert(scip);
1241  assert(nnodes >= 1 && nedges >= 0);
1242 
1243  SCIP_CALL( SCIPallocMemory(scip, csr) );
1244 
1245  csrd = *csr;
1246 
1247  csrd->nedges_max = nedges;
1248  csrd->nnodes = nnodes;
1249 
1250  SCIP_CALL( SCIPallocMemoryArray(scip, &(csrd->start), nnodes + 1) );
1251 
1252  if( nedges == 0 )
1253  {
1254  csrd->head = NULL;
1255  csrd->cost = NULL;
1256  }
1257  else
1258  {
1259  SCIP_CALL( SCIPallocMemoryArray(scip, &(csrd->head), nedges) );
1260  SCIP_CALL( SCIPallocMemoryArray(scip, &(csrd->cost), nedges) );
1261  }
1262 
1263  csrd->edge_id = NULL;
1264 
1265  return SCIP_OKAY;
1266 }
1267 
1268 
1269 /** allocates empty (and invalid!) CSR storage */
1271  SCIP* scip, /**< SCIP data structure */
1272  int nnodes, /**< nodes */
1273  int nedges, /**< edges */
1274  CSR** csr /**< CSR */
1275  )
1276 {
1277  CSR* csrd;
1278 
1279  SCIP_CALL( graph_csr_alloc(scip, nnodes, nedges, csr) );
1280 
1281  csrd = *csr;
1282 
1283  if( nedges == 0 )
1284  {
1285  csrd->edge_id = NULL;
1286  }
1287  else
1288  {
1289  SCIP_CALL( SCIPallocMemoryArray(scip, &(csrd->edge_id), nedges) );
1290  }
1291 
1292  return SCIP_OKAY;
1293 }
1294 
1295 
1296 /** Changes edge costs.
1297  * NOTE: for PC/MW no dummy nodes are considered! */
1299  const GRAPH* g, /**< the graph */
1300  const SCIP_Real* edgecosts, /**< edge costs (w.r.t graph 'g') */
1301  CSR* csr /**< CSR */
1302  )
1303 {
1304  int* RESTRICT start_csr;
1305  SCIP_Real* cost_csr;
1306  const int nnodes = graph_get_nNodes(g);
1307  const int* const gOeat = g->oeat;
1308  const int* const gHead = g->head;
1309  const SCIP_Bool pcmw = graph_pc_isPcMw(g);
1310 
1311  assert(csr && edgecosts);
1312  assert(nnodes >= 1);
1313  assert(csr->nnodes == nnodes);
1314  assert(csr->nedges_max >= graph_get_nEdges(g));
1315 
1316  start_csr = csr->start;
1317  cost_csr = csr->cost;
1318 
1319  assert(0 == start_csr[0]);
1320 
1321  for( int k = 0; k < nnodes; k++ )
1322  {
1323  int pos = start_csr[k];
1324 
1325  if( !pcmw || !graph_pc_knotIsDummyTerm(g, k) )
1326  {
1327  for( int e = g->outbeg[k]; e >= 0; e = gOeat[e] )
1328  {
1329  if( pcmw && graph_pc_knotIsDummyTerm(g, gHead[e]) )
1330  continue;
1331 
1332  assert(edgecosts[e] < FARAWAY && edgecosts[flipedge(e)] < FARAWAY);
1333  assert(gHead[e] == csr->head[pos] );
1334  assert(NULL == csr->edge_id || e == csr->edge_id[pos]);
1335 
1336  cost_csr[pos++] = edgecosts[e];
1337  }
1338  }
1339 
1340  assert((pos == start_csr[k] + g->grad[k]) || pcmw);
1341  assert(start_csr[k + 1] == pos);
1342  }
1343 
1344  assert(start_csr[nnodes] <= g->edges);
1345  assert(graph_csr_isValid(csr, TRUE));
1346 }
1347 
1348 
1349 /** Builds CSR storage from graph and cost array.
1350  * NOTE: for PC/MW no dummy nodes are considered! */
1352  const GRAPH* g, /**< the graph */
1353  const SCIP_Real* edgecosts, /**< edge costs (w.r.t graph 'g') */
1354  CSR* csr /**< CSR */
1355  )
1356 {
1357  int* RESTRICT start_csr;
1358  int* RESTRICT head_csr;
1359  int* RESTRICT edgeid_csr;
1360  SCIP_Real* cost_csr;
1361  const int nnodes = graph_get_nNodes(g);
1362  const int* const gOeat = g->oeat;
1363  const int* const gHead = g->head;
1364  const SCIP_Bool pcmw = graph_pc_isPcMw(g);
1365  SCIP_Bool hasEdgeId;
1366 
1367  assert(csr && edgecosts);
1368  assert(nnodes >= 1);
1369  assert(csr->nnodes == nnodes);
1370  assert(csr->nedges_max >= graph_get_nEdges(g));
1371 
1372  start_csr = csr->start;
1373  head_csr = csr->head;
1374  cost_csr = csr->cost;
1375  edgeid_csr = csr->edge_id;
1376 
1377  hasEdgeId = (edgeid_csr != NULL);
1378 
1379  /* now fill the data in */
1380 
1381  start_csr[0] = 0;
1382 
1383  for( int k = 0; k < nnodes; k++ )
1384  {
1385  int pos = start_csr[k];
1386 
1387  if( !pcmw || !graph_pc_knotIsDummyTerm(g, k) )
1388  {
1389  for( int e = g->outbeg[k]; e >= 0; e = gOeat[e] )
1390  {
1391  const int ehead = gHead[e];
1392 
1393  if( pcmw && graph_pc_knotIsDummyTerm(g, ehead) )
1394  continue;
1395 
1396  /* NOTE: STP_DCSTP might happen, because we change the edge weight during dual-ascent */
1397  assert(graph_typeIsDirected(g) || g->stp_type == STP_DCSTP
1398  || (edgecosts[e] < FARAWAY && edgecosts[flipedge(e)] < FARAWAY));
1399 
1400  head_csr[pos] = ehead;
1401  if( hasEdgeId )
1402  edgeid_csr[pos] = e;
1403  cost_csr[pos++] = edgecosts[e];
1404  }
1405  }
1406 
1407  assert((pos == start_csr[k] + g->grad[k]) || pcmw);
1408 
1409  start_csr[k + 1] = pos;
1410  }
1411 
1412  assert(start_csr[nnodes] <= g->edges);
1413  assert(graph_csr_isValid(csr, TRUE));
1414 }
1415 
1416 
1417 /** builds CSR costs from given edgecosts array */
1419  const GRAPH* g, /**< the graph */
1420  const CSR* csr, /**< CSR */
1421  const SCIP_Real* edgecosts_g, /**< edge costs (w.r.t graph 'g') */
1422  SCIP_Real* RESTRICT edgecosts_csr /**< new edgecosts for CSR */
1423  )
1424 {
1425  const int* const edgeid = csr->edge_id;
1426  const int nnodes = graph_get_nNodes(g);
1427  const int nedges = csr->start[nnodes];
1428 
1429  assert(edgeid);
1430  assert(nnodes >= 1);
1431  assert(csr->nnodes == nnodes);
1432  assert(nedges <= csr->nedges_max);
1433  assert(nedges <= graph_get_nEdges(g));
1434  assert(edgecosts_csr && edgecosts_g);
1435 
1436  for( int i = 0; i < nedges; i++ )
1437  {
1438  const int edge_g = edgeid[i];
1439 
1440  assert(0 <= edge_g && edge_g < g->edges);
1441 
1442  edgecosts_csr[i] = edgecosts_g[edge_g];
1443  }
1444 }
1445 
1446 
1447 /** are CSR and graph costs corresponding? */
1449  const GRAPH* g, /**< the graph */
1450  const CSR* csr, /**< CSR */
1451  const SCIP_Real* edgecosts_g /**< edge costs w.r.t graph 'g' */
1452 )
1453 {
1454  const SCIP_Real* const edgecosts_csr = csr->cost;
1455  const int* const edgeid = csr->edge_id;
1456  const int nnodes = graph_get_nNodes(g);
1457  const int nedges = csr->start[nnodes];
1458 
1459  assert(edgeid);
1460  assert(nnodes >= 1);
1461  assert(csr->nnodes == nnodes);
1462  assert(nedges <= csr->nedges_max);
1463  assert(nedges <= graph_get_nEdges(g));
1464  assert(edgecosts_csr && edgecosts_g);
1465 
1466  for( int i = 0; i < nedges; i++ )
1467  {
1468  const int edge_g = edgeid[i];
1469 
1470  assert(0 <= edge_g && edge_g < g->edges);
1471 
1472  if( !EQ(edgecosts_csr[i], edgecosts_g[edge_g]) )
1473  {
1474  return FALSE;
1475  }
1476  }
1477 
1478  return TRUE;
1479 }
1480 
1481 
1482 /** copies CSR storage */
1484  const CSR* csr_in, /**< CSR source */
1485  CSR* csr_out /**< CSR target */
1486  )
1487 {
1488  assert(csr_in && csr_out);
1489  assert(csr_in->nnodes == csr_out->nnodes);
1490  assert(csr_in->nedges_max == csr_out->nedges_max);
1491  assert(csr_in->nnodes > 0 && csr_in->nedges_max >= 0);
1492 
1493  assert(graph_csr_isValid(csr_in, FALSE));
1494  assert((csr_out->edge_id != NULL) == (csr_in->edge_id != NULL));
1495 
1496  BMScopyMemoryArray(csr_out->start, csr_in->start, csr_in->nnodes + 1);
1497 
1498  if( csr_in->nedges_max > 0 )
1499  {
1500  BMScopyMemoryArray(csr_out->head, csr_in->head, csr_in->nedges_max);
1501  BMScopyMemoryArray(csr_out->cost, csr_in->cost, csr_in->nedges_max);
1502 
1503  if( csr_out->edge_id != NULL )
1504  {
1505  BMScopyMemoryArray(csr_out->edge_id, csr_in->edge_id, csr_in->nedges_max);
1506  }
1507  }
1508 
1509  assert(graph_csr_isValid(csr_out, FALSE));
1510 }
1511 
1512 
1513 /** prints CSR storage */
1515  const CSR* csr /**< CSR to print */
1516 )
1517 {
1518  assert(csr);
1519  assert(graph_csr_isValid(csr, FALSE));
1520 
1521  printf("CSR with n=%d, m=%d; edges: \n", csr->nnodes, csr->nedges_max);
1522 
1523  for( int k = 0; k < csr->nnodes; k++ )
1524  {
1525  for( int j = csr->start[k]; j != csr->start[k + 1]; ++j )
1526  {
1527  const int head = csr->head[j];
1528  const SCIP_Real cost = csr->cost[j];
1529 
1530  printf(" %d->%d, c=%f \n", k, head, cost);
1531  }
1532  }
1533 }
1534 
1535 /** gets currently used CSR edges */
1537  const CSR* csr /**< CSR to print */
1538 )
1539 {
1540  int nnodes;
1541  assert(csr);
1542  assert(csr->start);
1543 
1544  nnodes = csr->nnodes;
1545 
1546  assert(nnodes >= 0);
1547  assert(csr->start[nnodes] >= 0);
1548  assert(csr->start[nnodes] <= csr->nedges_max);
1549 
1550  return csr->start[nnodes];
1551 }
1552 
1553 /** frees dynamic CSR storage */
1555  SCIP* scip, /**< SCIP data structure */
1556  CSR** csr /**< CSR */
1557  )
1558 {
1559  CSR* csrd;
1560 
1561  assert(scip && csr);
1562 
1563  csrd = *csr;
1564 
1565  assert(csrd);
1566  assert(csrd->nnodes >= 1);
1567  assert(csrd->cost);
1568  assert(csrd->head);
1569  assert(csrd->start);
1570 
1571  SCIPfreeMemoryArrayNull(scip, &(csrd->edge_id));
1572  SCIPfreeMemoryArrayNull(scip, &(csrd->cost));
1573  SCIPfreeMemoryArrayNull(scip, &(csrd->head));
1574  SCIPfreeMemoryArray(scip, &(csrd->start));
1575 
1576  SCIPfreeMemory(scip, csr);
1577 }
1578 
1579 
1580 /** initializes CSR storage of graph */
1582  SCIP* scip, /**< SCIP data structure */
1583  GRAPH* g /**< the graph */
1584  )
1585 {
1586  assert(scip && g);
1587  assert(g->knots >= 1);
1588  assert(g->csr_storage == NULL);
1589 
1590  SCIP_CALL( graph_csr_alloc(scip, g->knots, g->edges, &(g->csr_storage)) );
1591 
1592  graph_csr_build(g, g->cost, g->csr_storage);
1593 
1594  assert(graph_valid_csr(g, TRUE));
1595 
1596  return SCIP_OKAY;
1597 }
1598 
1599 
1600 
1601 
1602 /** initializes CSR storage of graph */
1604  SCIP* scip, /**< SCIP data structure */
1605  GRAPH* g /**< the graph */
1606  )
1607 {
1608  assert(scip && g);
1609  assert(g->knots >= 1);
1610  assert(g->csr_storage == NULL);
1611 
1612  SCIP_CALL( graph_csr_allocWithEdgeId(scip, g->knots, g->edges, &(g->csr_storage)) );
1613 
1614  graph_csr_build(g, g->cost, g->csr_storage);
1615 
1616  assert(graph_valid_csr(g, TRUE));
1617 
1618  return SCIP_OKAY;
1619 }
1620 
1621 
1622 /** frees dynamic CSR storage of graph */
1624  SCIP* scip, /**< SCIP data structure */
1625  GRAPH* g /**< the graph */
1626  )
1627 {
1628  assert(g->csr_storage);
1629 
1630  graph_csr_free(scip, &(g->csr_storage));
1631 
1632  assert(g->csr_storage == NULL);
1633 }
1634 
1635 
1636 /** is CSR storage valid? */
1638  const CSR* csr, /**< the CSR graph */
1639  SCIP_Bool verbose /**< be verbose? */
1640 )
1641 {
1642  const int* start = csr->start;
1643  const int nnodes = csr->nnodes;
1644  const int nedges = start[nnodes];
1645  const int* head = csr->head;
1646 
1647  /* NOTE: we might have more edge capacity */
1648 
1649  if( start[0] != 0 )
1650  {
1651  if( verbose )
1652  printf("CSR: start first corrupted \n");
1653 
1654  return FALSE;
1655  }
1656 
1657  if( nedges > csr->nedges_max )
1658  {
1659  if( verbose )
1660  printf("CSR: start last corrupted %d!=%d \n", start[nnodes], nedges);
1661 
1662  return FALSE;
1663  }
1664 
1665  for( int i = 0; i < nnodes; i++ )
1666  {
1667  if( start[i] > start[i + 1] )
1668  {
1669  if( verbose )
1670  printf("CSR: ranges corrupted \n");
1671 
1672  return FALSE;
1673  }
1674  }
1675 
1676  for( int i = 0; i < nedges; i++ )
1677  {
1678  const int v = head[i];
1679 
1680  if( v < 0 || v >= nnodes )
1681  {
1682  if( verbose )
1683  printf("CSR: neighbor entry corrupted \n");
1684 
1685  return FALSE;
1686  }
1687  }
1688 
1689  return TRUE;
1690 }
1691 
1692 
1693 /** is CSR storage of graph valid? */
1695  const GRAPH* g, /**< the graph */
1696  SCIP_Bool verbose /**< be verbose? */
1697 )
1698 {
1699  const CSR* csr = g->csr_storage;
1700 
1701  assert(csr && csr->head && csr->cost);
1702 
1703  if( csr->nnodes != g->knots || csr->nedges_max != g->edges )
1704  {
1705  if( verbose )
1706  printf("CSR: wrong node/edge count \n");
1707 
1708  return FALSE;
1709  }
1710 
1711  return graph_csr_isValid(csr, verbose);
1712 }
1713 
1714 
1715 /*
1716  * DCSR
1717  */
1718 
1719 
1720 /** initializes dynamic CSR storage */
1722  SCIP* scip, /**< SCIP data structure */
1723  GRAPH* g /**< the graph */
1724  )
1725 {
1726  DCSR* dcsr;
1727  RANGE* range_csr;
1728  int* head_csr;
1729  int* edgeid_csr;
1730  int* id2csr_csr;
1731  SCIP_Real* cost_csr;
1732  const int nedges = g->edges;
1733  const int nnodes = g->knots;
1734  const SCIP_Bool pcmw = graph_pc_isPcMw(g);
1735 
1736  assert(scip && g);
1737  assert(nnodes >= 1);
1738  assert(g->dcsr_storage == NULL);
1739  assert(!pcmw || !g->extended);
1740 
1741  SCIP_CALL( SCIPallocMemory(scip, &dcsr) );
1742  g->dcsr_storage = dcsr;
1743 
1744  dcsr->nedges = nedges;
1745  dcsr->nnodes = nnodes;
1746 
1747  SCIP_CALL( SCIPallocMemoryArray(scip, &(range_csr), nnodes) );
1748  SCIP_CALL( SCIPallocMemoryArray(scip, &(head_csr), nedges) );
1749  SCIP_CALL( SCIPallocMemoryArray(scip, &(edgeid_csr), nedges) );
1750  SCIP_CALL( SCIPallocMemoryArray(scip, &(id2csr_csr), nedges) );
1751  SCIP_CALL( SCIPallocMemoryArray(scip, &(cost_csr), nedges) );
1752 
1753  dcsr->range = range_csr;
1754  dcsr->head = head_csr;
1755  dcsr->edgeid = edgeid_csr;
1756  dcsr->id2csredge = id2csr_csr;
1757  dcsr->cost = cost_csr;
1758  dcsr->cost2 = NULL;
1759  dcsr->cost3 = NULL;
1760 
1761  graph_mark(g);
1762 
1763  /* now fill the data in */
1764 
1765  for( int e = 0; e < nedges; e++ )
1766  id2csr_csr[e] = -1;
1767 
1768  range_csr[0].start = 0;
1769 
1770  for( int k = 0; k < nnodes; k++ )
1771  {
1772  int pos = range_csr[k].start;
1773 
1774  if( !pcmw || g->mark[k] )
1775  {
1776  for( int e = g->outbeg[k]; e != EAT_LAST; e = g->oeat[e] )
1777  {
1778  const int ehead = g->head[e];
1779 
1780  if( pcmw && !g->mark[ehead] )
1781  continue;
1782 
1783  assert(g->cost[e] < FARAWAY && g->cost[flipedge(e)] < FARAWAY);
1784 
1785  id2csr_csr[e] = pos;
1786  head_csr[pos] = ehead;
1787  edgeid_csr[pos] = e;
1788  cost_csr[pos++] = g->cost[e];
1789  }
1790  }
1791 
1792  assert(pos == range_csr[k].start + g->grad[k] || pcmw);
1793 
1794  range_csr[k].end = pos;
1795 
1796  if( k != nnodes - 1 )
1797  range_csr[k + 1].start = range_csr[k].end;
1798  }
1799 
1800  assert(range_csr[nnodes - 1].end <= nedges);
1801  assert(graph_valid_dcsr(g, TRUE));
1802 
1803  return SCIP_OKAY;
1804 }
1805 
1806 /** frees dynamic CSR storage */
1808  SCIP* scip, /**< SCIP data structure */
1809  GRAPH* g /**< the graph */
1810  )
1811 {
1812  DCSR* dcsr = g->dcsr_storage;
1813 
1814  assert(scip && g);
1815  assert(dcsr != NULL && dcsr->nnodes >= 1);
1816 
1817  SCIPfreeMemoryArray(scip, &(dcsr->cost));
1818  SCIPfreeMemoryArray(scip, &(dcsr->id2csredge));
1819  SCIPfreeMemoryArray(scip, &(dcsr->edgeid));
1820  SCIPfreeMemoryArray(scip, &(dcsr->head));
1821  SCIPfreeMemoryArray(scip, &(dcsr->range));
1822 
1823  SCIPfreeMemory(scip, &(g->dcsr_storage));
1824 
1825  assert(g->dcsr_storage == NULL);
1826 }
1827 
1828 /** updates dynamic CSR storage */
1830  SCIP* scip, /**< SCIP data structure */
1831  GRAPH* g /**< the graph */
1832  )
1833 {
1834  assert(scip && g);
1835 
1836  assert(0 && "implement"); // check whether enough edges and nodes, otherwise reallocate
1837 }
1838 
1839 /** deletes CSR indexed edge */
1841  DCSR* dcsr, /**< DCSR container */
1842  int tail, /**< tail of edge */
1843  int e_csr /**< CSR indexed edge */
1844 )
1845 {
1846  RANGE* const range = dcsr->range;
1847  int* const head = dcsr->head;
1848  int* const edgeid = dcsr->edgeid;
1849  int* const id2csredge = dcsr->id2csredge;
1850  SCIP_Real* const cost = dcsr->cost;
1851  SCIP_Real* const cost2 = dcsr->cost2;
1852  SCIP_Real* const cost3 = dcsr->cost3;
1853  int last;
1854 
1855  assert(dcsr);
1856  assert(tail >= 0 && tail < dcsr->nnodes);
1857  assert(e_csr >= 0 && e_csr < dcsr->nedges);
1858  assert(range[tail].start <= e_csr && e_csr < range[tail].end);
1859 
1860  last = --(range[tail].end);
1861 
1862 #ifndef NDEBUG
1863  id2csredge[edgeid[e_csr]] = -1;
1864 #endif
1865 
1866  /* e_csr not already deleted? */
1867  if( e_csr != last )
1868  {
1869  head[e_csr] = head[last];
1870  edgeid[e_csr] = edgeid[last];
1871  id2csredge[edgeid[last]] = e_csr;
1872  cost[e_csr] = cost[last];
1873 
1874  if( cost2 )
1875  cost2[e_csr] = cost2[last];
1876 
1877  if( cost3 )
1878  cost3[e_csr] = cost3[last];
1879  }
1880 
1881 #ifndef NDEBUG
1882  head[last] = -1;
1883  edgeid[last] = -1;
1884  cost[last] = -FARAWAY;
1885  if( cost2 )
1886  cost2[last] = -FARAWAY;
1887  if( cost3 )
1888  cost3[last] = -FARAWAY;
1889 #endif
1890 
1891 }
1892 
1893 /** deletes CSR indexed edge and anti-parallel one */
1895  SCIP* scip, /**< SCIP data structure */
1896  DCSR* dcsr, /**< DCSR container */
1897  int e_csr /**< CSR indexed edge */
1898 )
1899 {
1900  int* const head = dcsr->head;
1901  int* const edgeid = dcsr->edgeid;
1902  int* const id2csredge = dcsr->id2csredge;
1903  const int erev_csr = id2csredge[flipedge(edgeid[e_csr])];
1904  const int i1 = head[erev_csr];
1905  const int i2 = head[e_csr];
1906 
1907  assert(scip && dcsr);
1908  assert(e_csr >= 0 && edgeid[e_csr] >= 0);
1909  assert(erev_csr >= 0);
1910  assert(SCIPisEQ(scip, dcsr->cost[e_csr], dcsr->cost[erev_csr]));
1911 
1912  SCIPdebugMessage("delete %d %d \n", i1, i2);
1913 
1914  graph_dcsr_deleteEdge(dcsr, i2, erev_csr);
1915  graph_dcsr_deleteEdge(dcsr, i1, e_csr);
1916 }
1917 
1918 /** is DCSR storage of graph valid? */
1920  const GRAPH* g, /**< the graph */
1921  SCIP_Bool verbose /**< be verbose? */
1922 )
1923 {
1924  const DCSR* const dcsr = g->dcsr_storage;
1925  const RANGE* const range = dcsr->range;
1926  const int* const head = dcsr->head;
1927  const int* const edgeid = dcsr->edgeid;
1928  const int* const id2csredge = dcsr->id2csredge;
1929  const int nnodes = dcsr->nnodes;
1930  const int nedges = dcsr->nedges;
1931 
1932  assert(g && dcsr && range && head && edgeid && id2csredge);
1933 
1934  if( nnodes != g->knots || nedges != g->edges )
1935  {
1936  if( verbose )
1937  printf("DCSR: wrong node/edge cound \n");
1938  return FALSE;
1939  }
1940 
1941  for( int i = 0; i < nnodes; i++ )
1942  {
1943  const int start = range[i].start;
1944  const int end = range[i].end;
1945 
1946  if( start > end )
1947  {
1948  if( verbose )
1949  printf("DCSR: ranges corrupted \n");
1950 
1951  return FALSE;
1952  }
1953 
1954  for( int e = start; e < end; e++ )
1955  {
1956  const int ordedge = edgeid[e];
1957 
1958  assert(ordedge >= 0 && ordedge < nedges);
1959 
1960  if( id2csredge[ordedge] != e )
1961  {
1962  if( verbose )
1963  printf("DCSR: id assignment corrupted \n");
1964 
1965  return FALSE;
1966  }
1967 
1968  if( head[e] != g->head[ordedge] || i != g->tail[ordedge] )
1969  {
1970  if( verbose )
1971  printf("DCSR: edge assignment corrupted \n");
1972 
1973  printf(" %d == %d %d == %d \n", head[e], g->head[ordedge], i, g->tail[ordedge]);
1974 
1975  return FALSE;
1976  }
1977  }
1978  }
1979 
1980  return TRUE;
1981 }
1982 
1983 /*
1984  * Limited Dijkstra storage
1985  */
1986 
1987 
1988 /** initializes (allocates and fills) limited Dijkstra structure members */
1990  SCIP* scip, /**< SCIP */
1991  const GRAPH* g, /**< the graph */
1992  DIJK** dijkdata /**< data for limited Dijkstra */
1993 )
1994 {
1995  DIJK* dijk;
1996  const int nnodes = g->knots;
1997  SCIP_Real* RESTRICT distance;
1998  STP_Bool* RESTRICT visited;
1999 
2000  assert(scip && g && dijkdata);
2001 
2002  SCIP_CALL( SCIPallocMemory(scip, dijkdata) );
2003 
2004  dijk = *dijkdata;
2005 
2006  SCIP_CALL( SCIPallocMemoryArray(scip, &(dijk->node_distance), nnodes) );
2007  SCIP_CALL( SCIPallocMemoryArray(scip, &(dijk->visitlist), nnodes) );
2008  SCIP_CALL( SCIPallocMemoryArray(scip, &(dijk->node_visited), nnodes) );
2009 
2010  dijk->node_bias = NULL;
2011 
2012  SCIP_CALL( graph_heap_create(scip, nnodes, NULL, NULL, &(dijk->dheap)) );
2013 
2014  dijk->nvisits = -1;
2015  dijk->edgelimit = -1;
2016 
2017  distance = dijk->node_distance;
2018  visited = dijk->node_visited;
2019 
2020  for( int k = 0; k < nnodes; k++ )
2021  {
2022  visited[k] = FALSE;
2023  distance[k] = FARAWAY;
2024  }
2025 
2026  return SCIP_OKAY;
2027 }
2028 
2029 
2030 /** initializes PC shifts per node */
2032  SCIP* scip, /**< SCIP */
2033  const GRAPH* g, /**< the graph */
2034  DIJK* dijkdata /**< data for limited Dijkstra */
2035 )
2036 {
2037  const int nnodes = graph_get_nNodes(g);
2038  const int pseudoroot = graph_pc_isRootedPcMw(g) ? -1 : g->source;
2039  const SCIP_Real* const costs = g->cost;
2040  SCIP_Real* RESTRICT pc_costshift;
2041 
2042  assert(scip && dijkdata);
2043  assert(!dijkdata->node_bias);
2044  assert(graph_pc_isPc(g));
2045  assert(!g->extended);
2046 
2047  SCIP_CALL( SCIPallocMemoryArray(scip, &(dijkdata->node_bias), nnodes) );
2048 
2049  pc_costshift = dijkdata->node_bias;
2050 
2051  for( int k = 0; k < nnodes; k++ )
2052  {
2053  if( Is_term(g->term[k]) && k != pseudoroot )
2054  {
2055  SCIP_Real mincost = g->prize[k];
2056 
2057  for( int e = g->inpbeg[k]; e != EAT_LAST; e = g->ieat[e] )
2058  {
2059  if( g->tail[e] == pseudoroot )
2060  continue;
2061 
2062  if( costs[e] < mincost )
2063  mincost = costs[e];
2064  }
2065 
2066  pc_costshift[k] = mincost;
2067 
2068  assert(GT(pc_costshift[k], 0.0));
2069  }
2070  else
2071  {
2072  assert(EQ(g->prize[k], 0.0) || (EQ(g->prize[k], FARAWAY) && k == pseudoroot));
2073 
2074  pc_costshift[k] = 0.0;
2075  }
2076  }
2077 
2078  return SCIP_OKAY;
2079 }
2080 
2081 
2082 /** cleans limited Dijkstra structure members */
2084  const GRAPH* g, /**< the graph */
2085  DIJK* dijkdata /**< data for limited Dijkstra */
2086 )
2087 {
2088  const int nnodes = g->knots;
2089  STP_Bool* const visited = dijkdata->node_visited;
2090  SCIP_Real* const distance = dijkdata->node_distance;
2091  dijkdata->nvisits = -1;
2092  dijkdata->edgelimit = -1;
2093 
2094  for( int k = 0; k < nnodes; k++ )
2095  {
2096  visited[k] = FALSE;
2097  distance[k] = FARAWAY;
2098  }
2099 
2100  graph_heap_clean(TRUE, dijkdata->dheap);
2101 }
2102 
2103 
2104 /** reset data of limited Dijkstra structure */
2106  const GRAPH* g, /**< the graph */
2107  DIJK* dijkdata /**< data for limited Dijkstra */
2108 )
2109 {
2110  const int* const visitlist = dijkdata->visitlist;
2111  SCIP_Real* RESTRICT distance = dijkdata->node_distance;
2112  STP_Bool* RESTRICT visited = dijkdata->node_visited;
2113  int* RESTRICT state = dijkdata->dheap->position;
2114  const int nvisits = dijkdata->nvisits;
2115 
2116  assert(dijkdata && g);
2117  assert(nvisits >= 0);
2118 
2119  for( int k = 0; k < nvisits; k++ )
2120  {
2121  const int node = visitlist[k];
2122  assert(node >= 0 && node < g->knots);
2123 
2124  visited[node] = FALSE;
2125  distance[node] = FARAWAY;
2126  state[node] = UNKNOWN;
2127  }
2128 
2129  graph_heap_clean(FALSE, dijkdata->dheap);
2130 
2131 #ifndef NDEBUG
2132  for( int k = 0; k < g->knots; k++ )
2133  {
2134  assert(visited[k] == FALSE);
2135  assert(state[k] == UNKNOWN);
2136  assert(distance[k] == FARAWAY);
2137  }
2138 #endif
2139 }
2140 
2141 
2142 /** frees limited Dijkstra structure member */
2144  SCIP* scip, /**< SCIP */
2145  DIJK** dijkdata /**< data for limited Dijkstra */
2146 )
2147 {
2148  DIJK* dijk = *dijkdata;
2149 
2150  SCIPfreeMemoryArrayNull(scip, &(dijk->node_bias));
2151  SCIPfreeMemoryArray(scip, &(dijk->node_distance));
2152  SCIPfreeMemoryArray(scip, &(dijk->visitlist));
2153  SCIPfreeMemoryArray(scip, &(dijk->node_visited));
2154 
2155  graph_heap_free(scip, TRUE, TRUE, &(dijk->dheap));
2156 
2157  SCIPfreeMemoryArray(scip, dijkdata);
2158 }
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
static int csrdepoGetTopIndex(const CSRDEPO *depository)
Definition: graph_util.c:248
int * visitlist
Definition: graphdefs.h:314
void graph_csrdepo_free(SCIP *scip, CSRDEPO **depository)
Definition: graph_util.c:637
int *RESTRICT head
Definition: graphdefs.h:224
SCIP_Bool graph_typeIsDirected(const GRAPH *)
Definition: graph_stats.c:83
void graph_csr_print(const CSR *csr)
Definition: graph_util.c:1514
int * head
Definition: graphdefs.h:141
int source
Definition: graphdefs.h:195
void graph_heap_deleteMin(int *node, SCIP_Real *key, DHEAP *heap)
Definition: graph_util.c:1053
#define FSP_MODE
Definition: graphdefs.h:99
SCIP_Bool graph_pc_isRootedPcMw(const GRAPH *)
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip_mem.h:72
#define Is_term(a)
Definition: graphdefs.h:102
int start
Definition: graphdefs.h:152
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
void graph_csrdepo_emptyTopSetMarked(CSRDEPO *depository)
Definition: graph_util.c:890
SCIP_RETCODE graph_csrdepo_init(SCIP *scip, int ncsrs_max, int datasize_max, CSRDEPO **depository)
Definition: graph_util.c:590
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
static void csrdepoFillCSR(const CSRDEPO *depository, int index, CSR *csr)
Definition: graph_util.c:304
void graph_path_exec(SCIP *, const GRAPH *, int, int, const SCIP_Real *, PATH *)
Definition: graph_path.c:541
void graph_mark(GRAPH *)
Definition: graph_base.c:1130
SCIP_RETCODE graph_findCentralTerminal(SCIP *scip, const GRAPH *g, int centertype, int *central_term)
Definition: graph_util.c:410
static SCIP_RETCODE trail(SCIP *scip, const GRAPH *g, int start, SCIP_Bool costAware, SCIP_Bool *nodevisited)
Definition: graph_util.c:60
#define DHEAP_MAX_KEY
Definition: graph_util.c:29
#define FALSE
Definition: def.h:87
SCIP_RETCODE graph_init_csrWithEdgeId(SCIP *scip, GRAPH *g)
Definition: graph_util.c:1603
int *RESTRICT inpbeg
Definition: graphdefs.h:202
void graph_csr_buildCosts(const GRAPH *g, const CSR *csr, const SCIP_Real *edgecosts_g, SCIP_Real *RESTRICT edgecosts_csr)
Definition: graph_util.c:1418
SCIP_Real * cost
Definition: graphdefs.h:142
SCIP_Real * cost2
Definition: graphdefs.h:165
void graph_heap_free(SCIP *scip, SCIP_Bool freePositions, SCIP_Bool freeEntries, DHEAP **heap)
Definition: graph_util.c:1034
#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
static void csrdepoCsrUnsetDebug(CSR *csr)
Definition: graph_util.c:161
#define STP_DCSTP
Definition: graphdefs.h:47
void graph_csrdepo_addEmptyTop(CSRDEPO *depository, int nnodes, int nedges)
Definition: graph_util.c:800
SCIP_Real * cost
Definition: graphdefs.h:164
SCIP_Real * node_bias
Definition: graphdefs.h:319
void graph_dijkLimited_free(SCIP *scip, DIJK **dijkdata)
Definition: graph_util.c:2143
#define STP_CENTER_OK
Definition: graphdefs.h:66
#define EAT_LAST
Definition: graphdefs.h:58
#define SCIPdebugMessage
Definition: pub_message.h:87
#define FARAWAY
Definition: graphdefs.h:89
void graph_csrdepo_getTopCSR(const CSRDEPO *depository, CSR *csr)
Definition: graph_util.c:684
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_Real csrdepoCsrWeight(const CSR *csr)
Definition: graph_util.c:215
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
int * start
Definition: graphdefs.h:140
void graph_csrdepo_print(const CSRDEPO *depository)
Definition: graph_util.c:908
void graph_csrdepo_removeTop(CSRDEPO *depository)
Definition: graph_util.c:753
static void csrdepoCleanDebug(CSRDEPO *depository)
Definition: graph_util.c:178
SCIP_Real * node_distance
Definition: graphdefs.h:316
CSR * csr_storage
Definition: graphdefs.h:270
SCIP_RETCODE graph_dijkLimited_init(SCIP *scip, const GRAPH *g, DIJK **dijkdata)
Definition: graph_util.c:1989
SCIP_Bool graph_valid_dcsr(const GRAPH *g, SCIP_Bool verbose)
Definition: graph_util.c:1919
int *RESTRICT mark
Definition: graphdefs.h:198
void graph_free_csr(SCIP *scip, GRAPH *g)
Definition: graph_util.c:1623
void graph_csr_copy(const CSR *csr_in, CSR *csr_out)
Definition: graph_util.c:1483
SCIP_Bool graph_knotIsNWLeaf(const GRAPH *, int)
Definition: graph_node.c:35
SCIP_Real * cost3
Definition: graphdefs.h:166
SCIP_Bool graph_heap_isClean(const DHEAP *heap)
Definition: graph_util.c:962
int * position
Definition: graphdefs.h:305
int *RESTRICT oeat
Definition: graphdefs.h:231
#define GE(a, b)
Definition: portab.h:85
SCIP_Real key
Definition: graphdefs.h:296
void graph_dcsr_deleteEdge(DCSR *dcsr, int tail, int e_csr)
Definition: graph_util.c:1840
SCIP_Bool extended
Definition: graphdefs.h:267
SCIP_RETCODE graph_csr_allocWithEdgeId(SCIP *scip, int nnodes, int nedges, CSR **csr)
Definition: graph_util.c:1270
void graph_csr_build(const GRAPH *g, const SCIP_Real *edgecosts, CSR *csr)
Definition: graph_util.c:1351
int stp_type
Definition: graphdefs.h:264
#define STP_CENTER_SUM
Definition: graphdefs.h:68
SCIP_RETCODE graph_dijkLimited_initPcShifts(SCIP *scip, const GRAPH *g, DIJK *dijkdata)
Definition: graph_util.c:2031
void graph_heap_correct(int node, SCIP_Real newkey, DHEAP *heap)
Definition: graph_util.c:1166
static int csrdepoGetNnodes(const CSRDEPO *depository, int index)
Definition: graph_util.c:262
DHEAP * dheap
Definition: graphdefs.h:315
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: graphdefs.h:294
SCIP_Real * prize
Definition: graphdefs.h:210
static SCIP_Real csrdepoGetTopWeight(const CSRDEPO *depository)
Definition: graph_util.c:232
int nedges_max
Definition: graphdefs.h:144
SCIP_Real dist
Definition: graphdefs.h:286
int *RESTRICT grad
Definition: graphdefs.h:201
void graph_csr_chgCosts(const GRAPH *g, const SCIP_Real *edgecosts, CSR *csr)
Definition: graph_util.c:1298
SCIP_Bool graph_valid_csr(const GRAPH *g, SCIP_Bool verbose)
Definition: graph_util.c:1694
#define NULL
Definition: lpi_spx1.cpp:155
void graph_csrdepo_getEmptyTop(const CSRDEPO *depository, CSR *csr)
Definition: graph_util.c:874
#define EQ(a, b)
Definition: portab.h:79
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_RETCODE graph_heap_create(SCIP *scip, int capacity, int *position, DENTRY *entries, DHEAP **heap)
Definition: graph_util.c:992
static SCIP_Bool csrdepoCsrIsSet(const CSR *csr, SCIP_Bool verbose)
Definition: graph_util.c:114
void graph_buildOrgNodesToReducedMap(const GRAPH *g, int *map)
Definition: graph_util.c:560
static int csrdepoGetNedges(const CSRDEPO *depository, int index)
Definition: graph_util.c:283
void graph_dcsr_deleteEdgeBi(SCIP *scip, DCSR *dcsr, int e_csr)
Definition: graph_util.c:1894
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
Definition: graph_load.c:93
#define LT(a, b)
Definition: portab.h:81
void graph_dijkLimited_reset(const GRAPH *g, DIJK *dijkdata)
Definition: graph_util.c:2105
void graph_csrdepo_addEmptyTopTree(CSRDEPO *depository, int nnodes)
Definition: graph_util.c:836
unsigned char STP_Bool
Definition: portab.h:34
SCIP_RETCODE graph_trail_costAware(SCIP *scip, const GRAPH *g, int start, SCIP_Bool *nodevisited)
Definition: graph_util.c:353
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define GT(a, b)
Definition: portab.h:84
SCIP_Bool graph_csrdepo_hasEmptyTop(const CSRDEPO *depository)
Definition: graph_util.c:863
SCIP_Bool graph_csr_costsAreInSync(const GRAPH *g, const CSR *csr, const SCIP_Real *edgecosts_g)
Definition: graph_util.c:1448
#define SCIP_Bool
Definition: def.h:84
SCIP_RETCODE graph_csr_alloc(SCIP *scip, int nnodes, int nedges, CSR **csr)
Definition: graph_util.c:1231
int *RESTRICT ieat
Definition: graphdefs.h:230
#define STP_NWPTSPG
Definition: graphdefs.h:48
void graph_dijkLimited_clean(const GRAPH *g, DIJK *dijkdata)
Definition: graph_util.c:2083
#define DHEAP_MIN_KEY
Definition: graph_util.c:30
int graph_csrdepo_getDataSize(const CSRDEPO *depository)
Definition: graph_util.c:709
int *RESTRICT tail
Definition: graphdefs.h:223
#define flipedge(edge)
Definition: graphdefs.h:84
#define MAX(x, y)
Definition: tclique_def.h:83
SCIP_Bool graph_csr_isValid(const CSR *csr, SCIP_Bool verbose)
Definition: graph_util.c:1637
void graph_csrdepo_getCSR(const CSRDEPO *depository, int index, CSR *csr)
Definition: graph_util.c:667
void graph_heap_clean(SCIP_Bool cleanposition, DHEAP *heap)
Definition: graph_util.c:938
int *RESTRICT term
Definition: graphdefs.h:196
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
void graph_csrdepo_clean(CSRDEPO *depository)
Definition: graph_util.c:781
void graph_csr_free(SCIP *scip, CSR **csr)
Definition: graph_util.c:1554
SCIP_Bool graph_pc_isPc(const GRAPH *)
#define CONNECT
Definition: graphdefs.h:87
SCIP_RETCODE graph_init_csr(SCIP *scip, GRAPH *g)
Definition: graph_util.c:1581
DENTRY * entries
Definition: graphdefs.h:306
Portable definitions.
SCIP_Bool graph_csrdepo_isEmpty(const CSRDEPO *depository)
Definition: graph_util.c:851
int graph_csrdepo_getNcsrs(const CSRDEPO *depository)
Definition: graph_util.c:741
int layers
Definition: graphdefs.h:193
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
int graph_heap_deleteMinReturnNode(DHEAP *heap)
Definition: graph_util.c:1076
int * edge_id
Definition: graphdefs.h:143
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
void graph_update_dcsr(SCIP *scip, GRAPH *g)
Definition: graph_util.c:1829
SCIP_Real * cost
Definition: graphdefs.h:221
#define STP_CENTER_MIN
Definition: graphdefs.h:69
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
SCIP_VAR * a
Definition: circlepacking.c:57
SCIP_RETCODE graph_trail_arr(SCIP *scip, const GRAPH *g, int start, SCIP_Bool *nodevisited)
Definition: graph_util.c:336
#define SCIP_Real
Definition: def.h:177
int *RESTRICT outbeg
Definition: graphdefs.h:204
#define STP_CENTER_ALL
Definition: graphdefs.h:70
int edges
Definition: graphdefs.h:219
STP_Bool * node_visited
Definition: graphdefs.h:317
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
SCIP_RETCODE graph_termsReachable(SCIP *scip, const GRAPH *g, SCIP_Bool *reachable)
Definition: graph_util.c:370
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
void graph_free_dcsr(SCIP *scip, GRAPH *g)
Definition: graph_util.c:1807
#define UNKNOWN
Definition: sepa_mcf.c:4095
#define nnodes
Definition: gastrans.c:65
DCSR * dcsr_storage
Definition: graphdefs.h:271
#define STP_CENTER_DEG
Definition: graphdefs.h:67
SCIP_RETCODE graph_init_dcsr(SCIP *scip, GRAPH *g)
Definition: graph_util.c:1721
includes various reduction methods for Steiner tree problems
int graph_csr_getNedges(const CSR *csr)
Definition: graph_util.c:1536
void graph_heap_deleteMinGetNode(int *node, DHEAP *heap)
Definition: graph_util.c:1065