Scippy

SCIP

Solving Constraint Integer Programs

graph_node.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_node.c
17  * @brief includes graph node methods for Steiner problems
18  * @author Daniel Rehfeldt
19  *
20  * Graph node methods for Steiner problems
21  *
22  */
23 
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
25 
26 /*lint -esym(766,stdlib.h) -esym(766,malloc.h) */
27 /*lint -esym(766,string.h) */
28 
29 #include "graph.h"
30 #include "portab.h"
31 
32 
33 
34 /* is the vertex a leaf (for NWPTSPG) */
36  const GRAPH* g, /**< the graph */
37  int vertex /**< the vertex */
38 )
39 {
40  int e;
41  assert(g != NULL && g->stp_type == STP_NWPTSPG);
42 
43  for( e = g->outbeg[vertex]; e != EAT_LAST; e = g->oeat[e] )
44  if( LT(g->cost[e], FARAWAY) )
45  break;
46 
47  return (e == EAT_LAST );
48 }
49 
50 
51 /** is node in range? */
53  const GRAPH* g, /**< the graph */
54  int k /**< the node */
55  )
56 {
57  assert(g);
58 
59  return (0 <= k && k < g->knots);
60 }
61 
62 
63 /** add a vertex */
65  GRAPH* p, /**< the graph */
66  int term /**< terminal property */
67  )
68 {
69  assert(p != NULL);
70  assert(p->ksize > p->knots);
71  assert(term < p->layers);
72 
73  p->term [p->knots] = term;
74  p->mark [p->knots] = TRUE;
75  p->grad [p->knots] = 0;
76  p->inpbeg[p->knots] = EAT_LAST;
77  p->outbeg[p->knots] = EAT_LAST;
78 
79  if( Is_term(term) )
80  p->terms++;
81 
82  p->knots++;
83 }
84 
85 /** change terminal property of a vertex */
87  GRAPH* p, /**< the graph */
88  int node, /**< node to be changed */
89  int term /**< terminal property */
90  )
91 {
92  assert(p != NULL);
93  assert(node >= 0);
94  assert(node < p->knots);
95  assert(term == STP_TERM || term == STP_TERM_NONE || term == STP_TERM_NONLEAF || term == STP_TERM_PSEUDO);
96 
97  if( term != p->term[node] )
98  {
99  if( Is_term(p->term[node]) )
100  p->terms--;
101 
102  p->term[node] = term;
103 
104  if( Is_term(p->term[node]) )
105  p->terms++;
106  }
107 }
108 
109 
110 /** deletes node */
112  SCIP* scip, /**< SCIP data structure */
113  GRAPH* g, /**< the graph */
114  int k, /**< the node */
115  SCIP_Bool freeancestors /**< free edge ancestors? */
116  )
117 {
118  assert(scip && g);
119  assert(graph_knot_isInRange(g, k));
120 
121  while( g->outbeg[k] != EAT_LAST )
122  graph_edge_del(scip, g, g->outbeg[k], freeancestors);
123 
124  assert(g->grad[k] == 0);
125  assert(g->outbeg[k] == EAT_LAST && g->inpbeg[k] == EAT_LAST);
126 }
127 
128 
129 
130 /** deletes node, and also adapts DCSR storage */
132  SCIP* scip, /**< SCIP data structure */
133  GRAPH* g, /**< the graph */
134  int k, /**< the node */
135  SCIP_Bool freeancestors /**< free edge ancestors? */
136  )
137 {
138  assert(scip && g);
139  assert(graph_knot_isInRange(g, k));
140 
141  if( g->dcsr_storage )
142  {
143  while( g->outbeg[k] != EAT_LAST )
144  graph_edge_delFull(scip, g, g->outbeg[k], freeancestors);
145  }
146  else
147  {
148  while( g->outbeg[k] != EAT_LAST )
149  graph_edge_del(scip, g, g->outbeg[k], freeancestors);
150  }
151 
152  assert(g->grad[k] == 0);
153  assert(g->outbeg[k] == EAT_LAST && g->inpbeg[k] == EAT_LAST);
154 }
155 
156 
157 /** pseudo deletes non-terminal of degree 2 */
159  SCIP* scip, /**< SCIP data structure */
160  int vertex, /**< the vertex to replace */
161  SCIP_Real edgecost, /**< new edge cost */
162  int ancestornode, /**< node to copy ancestors from or -1 */
163  GRAPH* g, /**< the graph */
164  SCIP_Bool* edgeEliminated /**< edge eliminated? (due to conflict) */
165  )
166 {
167  IDX* ancestors1;
168  IDX* ancestors2;
169  int* pseudoancestors1 = NULL;
170  int* pseudoancestors2 = NULL;
171  const int e1 = g->outbeg[vertex];
172  const int e2 = g->oeat[e1];
173  const int i1 = g->head[e1];
174  const int i2 = g->head[e2];
175  const int npseudoancestors1 = graph_edge_nPseudoAncestors(g, e1);
176  const int npseudoancestors2 = graph_edge_nPseudoAncestors(g, e2);
177  int newedge;
178  SCIP_Bool conflict = FALSE;
179 
180  assert(scip && g);
181  assert(vertex >= 0 && vertex < g->knots);
182  assert(!Is_term(g->term[vertex]));
183  assert(g->grad[vertex] == 2);
184  assert(e1 >= 0 && e2 >= 0);
185  assert(SCIPisEQ(scip, g->cost[e1], g->cost[flipedge(e1)]));
186  assert(SCIPisEQ(scip, g->cost[e2], g->cost[flipedge(e2)]));
187  assert(graph_valid_pseudoAncestors(scip, g));
188  assert(graph_typeIsUndirected(g));
189 
190  *edgeEliminated = FALSE;
191 
192  if( npseudoancestors1 > 0 )
193  {
194  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pseudoancestors1), npseudoancestors1) );
195  BMScopyMemoryArray(pseudoancestors1, graph_edge_getPseudoAncestors(g, e1), npseudoancestors1);
196  }
197 
198  if( npseudoancestors2 > 0 )
199  {
200  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pseudoancestors2), npseudoancestors2) );
201  BMScopyMemoryArray(pseudoancestors2, graph_edge_getPseudoAncestors(g, e2), npseudoancestors2);
202  }
203 
204  ancestors1 = graph_edge_getAncestors(g, e1);
205  ancestors2 = graph_edge_getAncestors(g, e2);
206 
207  g->ancestors[e1] = g->ancestors[flipedge(e1)] = NULL;
208  g->ancestors[e2] = g->ancestors[flipedge(e2)] = NULL;
209 
210  newedge = graph_edge_redirect(scip, g, e1, i2, i1, edgecost, FALSE, TRUE);
211 
212  assert(ancestornode >= 0 || ancestornode == -1);
213 
214  /* is there a new edge? */
215  if( newedge >= 0 )
216  {
217  const int edge_even = Edge_even(newedge);
218 
219  graph_edge_delHistory(scip, g, newedge);
220 
221  g->ancestors[edge_even] = ancestors1;
222  SCIPintListNodeAppend(g->ancestors[edge_even], ancestors2);
223 
224  SCIP_CALL( graph_pseudoAncestors_appendCopyArrayToEdge(scip, newedge, pseudoancestors1, npseudoancestors1, g, &conflict) );
225  assert(!conflict);
226  SCIP_CALL( graph_pseudoAncestors_appendCopyArrayToEdge(scip, newedge, pseudoancestors2, npseudoancestors2, g, &conflict) );
227 
228  /* ancestor node given?*/
229  if( ancestornode >= 0 )
230  {
231  assert(graph_pc_isPcMw(g));
232 
233  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[edge_even]), g->pcancestors[ancestornode], NULL) );
234 
235  if( !conflict )
236  SCIP_CALL( graph_pseudoAncestors_appendCopyNodeToEdge(scip, newedge, ancestornode, TRUE, g, &conflict) );
237  }
238  }
239  else
240  {
241  SCIPintListNodeFree(scip, &ancestors1);
242  SCIPintListNodeFree(scip, &ancestors2);
243  }
244 
245  graph_knot_del(scip, g, vertex, TRUE);
246 
247  SCIPfreeBlockMemoryArrayNull(scip, &pseudoancestors1, npseudoancestors1);
248  SCIPfreeBlockMemoryArrayNull(scip, &pseudoancestors2, npseudoancestors2);
249 
250  if( conflict )
251  {
252  SCIPdebugMessage("conflict in graph_knot_replaceDeg2 \n");
253  assert(newedge >= 0);
254  graph_edge_del(scip, g, newedge, TRUE);
255  *edgeEliminated = TRUE;
256  }
257 
258  return SCIP_OKAY;
259 }
260 
261 
262 
263 /** contracts node s into node t */
265  SCIP* scip, /**< SCIP data structure */
266  GRAPH* g, /**< graph data structure */
267  int* solnode, /**< node array to mark whether an node is part of a given solution (CONNECT),
268  or NULL */
269  int t, /**< tail node to be contracted (surviving node) */
270  int s /**< head node to be contracted */
271  )
272 {
273  SCIP_Real* incost = NULL;
274  SCIP_Real* outcost = NULL;
275  SINGLETONANS* ancestors = NULL;
276  int* mark = NULL;
277  int* edge = NULL;
278  int* knot = NULL;
279  int slc = 0;
280  int sgrad;
281  const SCIP_Bool isUndirected = graph_typeIsUndirected(g);
282 
283  assert(g && scip);
284  assert(graph_knot_isInRange(g, t));
285  assert(graph_knot_isInRange(g, s));
286  assert(t != s);
287 
288  /* save solution nodes? */
289  if( solnode )
290  {
291  if( solnode[s] == CONNECT )
292  solnode[t] = CONNECT;
293  }
294 
295  /* trace contractions? */
296  if( g->contracttrace )
297  {
298  assert(g->contracttrace[s] == -1);
299  g->contracttrace[s] = t;
300  SCIPdebugMessage("contract trace %d->%d \n", s, t);
301  }
302 
303  /* change terminal property */
304  if( Is_term(g->term[s]) )
305  {
306  graph_knot_chg(g, t, g->term[s]);
307  graph_knot_chg(g, s, -1);
308  }
309 
310  /* retain root */
311  if( g->source == s )
312  g->source = t;
313 
314  sgrad = g->grad[s];
315  if( sgrad >= 1 )
316  {
317  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &incost, sgrad) );
318  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &outcost, sgrad) );
319  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &mark, sgrad) );
320  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &edge, sgrad) );
321  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &knot, sgrad) );
322  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &ancestors, sgrad) );
323  }
324 
325  /* store edges to be moved/removed */
326  for( int es = g->outbeg[s]; es != EAT_LAST; es = g->oeat[es] )
327  {
328  assert(g->tail[es] == s);
329 
330  if( g->head[es] != t )
331  {
332  assert(ancestors && mark && incost && outcost && edge && knot);
333  assert(slc < sgrad);
334 
335  SCIP_CALL( graph_singletonAncestors_init(scip, g, es, &(ancestors[slc])) );
336  mark[slc] = FALSE;
337  edge[slc] = es;
338  knot[slc] = g->head[es];
339  outcost[slc] = g->cost[es];
340  incost[slc] = g->cost[Edge_anti(es)];
341  slc++;
342  }
343  }
344 
345  assert(slc == sgrad - 1 || slc == sgrad);
346 
347  /* traverse edges */
348  for( int i = 0; i < slc; i++ )
349  {
350  int et;
351  const int ihead = knot[i];
352 
353  assert(knot != NULL && outcost != NULL && incost != NULL && mark != NULL);
354 
355  /* search for an edge out of t with same head as current edge */
356 
357  if( g->grad[ihead] >= g->grad[t] )
358  {
359  for( et = g->outbeg[t]; et >= 0; et = g->oeat[et] )
360  if( g->head[et] == ihead )
361  break;
362  }
363  else
364  {
365  for( et = g->inpbeg[ihead]; et >= 0; et = g->ieat[et] )
366  if( g->tail[et] == t )
367  break;
368  }
369 
370  /* does such an edge not exist? */
371  if( et == EAT_LAST )
372  {
373  mark[i] = TRUE;
374  }
375  else
376  {
377  const int anti = flipedge_Uint(et);
378  SCIP_Bool copyPseudoancestors = FALSE;
379  assert(et != EAT_LAST);
380 
381  /* This is for nodes with edges to s and t.
382  * Need to adjust the out and in costs of the edge
383  */
384 
385  if( isUndirected && SCIPisGT(scip, g->cost[et], outcost[i]) && SCIPisGT(scip, g->cost[anti], incost[i]) )
386  copyPseudoancestors = TRUE;
387 
388  if( copyPseudoancestors )
389  graph_edge_delPseudoAncestors(scip, et, g);
390 
391  /* NOTE: even in the undirected case there might be different anti-parallel weights for PC/MW */
392  if( isUndirected )
393  {
394  assert((SCIPisGT(scip, g->cost[et], outcost[i]) && SCIPisGT(scip, g->cost[anti], incost[i]))
395  || (SCIPisLE(scip, g->cost[et], outcost[i]) && SCIPisLE(scip, g->cost[anti], incost[i])));
396 
397  if( SCIPisGT(scip, g->cost[et], outcost[i]) )
398  {
399  const int even = Edge_even(et);
400 
401  assert(!g->ancestors[et] || !g->ancestors[anti]);
402  assert(g->ancestors[even]);
403  assert(SCIPisGT(scip, g->cost[anti], incost[i]));
404 
405  SCIPintListNodeFree(scip, &(g->ancestors[even]));
406  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[even]), ancestors[i].ancestors, NULL) );
407 
408  g->cost[et] = outcost[i];
409  g->cost[anti] = incost[i];
410  }
411  }
412  else
413  {
414  if( SCIPisGT(scip, g->cost[et], outcost[i]) )
415  {
416  SCIPintListNodeFree(scip, &((g->ancestors)[et]));
417  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &((g->ancestors)[et]), ancestors[i].ancestors, NULL) );
418 
419  assert(graph_edge_nPseudoAncestors(g, et) == 0);
420  g->cost[et] = outcost[i];
421  }
422 
423  if( SCIPisGT(scip, g->cost[anti], incost[i]) )
424  {
425  SCIPintListNodeFree(scip, &(g->ancestors[anti]));
426  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &((g->ancestors)[anti]), ancestors[i].revancestors, NULL) );
427 
428  assert(graph_edge_nPseudoAncestors(g, anti) == 0);
429  g->cost[anti] = incost[i];
430  }
431  }
432 
433  if( copyPseudoancestors )
434  {
435  SCIP_Bool conflict;
436  SCIP_CALL( graph_pseudoAncestors_appendCopySingToEdge(scip, et, &(ancestors[i]), FALSE, g, &conflict) );
437  assert(!conflict);
438  }
439  }
440  }
441 
442  /* insert edges */
443  for( int i = 0; i < slc; i++ )
444  {
445  assert(mark && ancestors && knot && outcost && incost);
446 
447  if( mark[i] )
448  {
449  int es = g->outbeg[s];
450  const int head = knot[i];
451  const int tail = t;
452  SCIP_Bool conflict;
453 
454  assert(es != EAT_LAST);
455 
456  graph_edge_del(scip, g, es, TRUE);
457  assert(!g->ancestors[es] && !g->ancestors[flipedge(es)]);
458 
459  if( isUndirected )
460  {
461  const int even = Edge_even(es);
462  assert(ancestors[i].ancestors && !ancestors[i].revancestors);
463  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[even]), ancestors[i].ancestors, NULL) );
464  }
465 
466  if( !isUndirected )
467  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[es]), ancestors[i].ancestors, NULL) );
468 
469  SCIP_CALL( graph_pseudoAncestors_appendCopySingToEdge(scip, es, &(ancestors[i]), FALSE, g, &conflict) );
470  assert(!conflict);
471 
472  g->grad[head]++;
473  g->grad[tail]++;
474 
475  g->cost[es] = outcost[i];
476  g->tail[es] = tail;
477  g->head[es] = head;
478  g->ieat[es] = g->inpbeg[head];
479  g->oeat[es] = g->outbeg[tail];
480  g->inpbeg[head] = es;
481  g->outbeg[tail] = es;
482 
483  es = Edge_anti(es);
484 
485  if( !isUndirected )
486  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[es]), ancestors[i].revancestors, NULL) );
487 
488  g->cost[es] = incost[i];
489  g->tail[es] = head;
490  g->head[es] = tail;
491  g->ieat[es] = g->inpbeg[tail];
492  g->oeat[es] = g->outbeg[head];
493  g->inpbeg[tail] = es;
494  g->outbeg[head] = es;
495  }
496  }
497 
498  /* delete remaining edges */
499  graph_knot_del(scip, g, s, TRUE);
500 
501  if( sgrad >= 1 )
502  {
503  assert(ancestors && knot && outcost && edge && mark && incost);
504 
505  for( int i = 0; i < slc; i++ )
506  graph_singletonAncestors_freeMembers(scip, &(ancestors[i]));
507 
508  SCIPfreeBlockMemoryArray(scip, &ancestors, sgrad);
509  SCIPfreeBlockMemoryArray(scip, &knot, sgrad);
510  SCIPfreeBlockMemoryArray(scip, &edge, sgrad);
511  SCIPfreeBlockMemoryArray(scip, &mark, sgrad);
512  SCIPfreeBlockMemoryArray(scip, &outcost, sgrad);
513  SCIPfreeBlockMemoryArray(scip, &incost, sgrad);
514  }
515 
516  return SCIP_OKAY;
517 }
518 
519 
520 /** contract an edge, given index and by its endpoints, which is to be fixed */
522  SCIP* scip, /**< SCIP data structure */
523  GRAPH* g, /**< graph data structure */
524  int* solnode, /**< node array to mark whether an node is part of a given solution (CONNECT),
525  or NULL */
526  int edge, /**< the edge */
527  int t, /**< tail node to be contracted (surviving node) */
528  int s /**< head node to be contracted */
529  )
530 {
531  SCIP_CALL( graph_fixed_addEdge(scip, edge, g) );
532  SCIP_CALL( graph_knot_contract(scip, g, solnode, t, s) );
533 
534  return SCIP_OKAY;
535 }
536 
537 
538 /** contract endpoint of lower degree into endpoint of higher degree */
540  SCIP* scip, /**< SCIP data structure */
541  GRAPH* g, /**< graph data structure */
542  int* solnode, /**< node array to mark whether an node is part of a given solution (CONNECT),
543  or NULL */
544  int t, /**< tail node to be contracted */
545  int s /**< head node to be contracted */
546  )
547 {
548  assert(g != NULL);
549 
550  if( g->grad[t] >= g->grad[s] )
551  SCIP_CALL( graph_knot_contract(scip, g, solnode, t, s) );
552  else
553  SCIP_CALL( graph_knot_contract(scip, g, solnode, s, t) );
554 
555  return SCIP_OKAY;
556 }
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
void graph_edge_delPseudoAncestors(SCIP *, int, GRAPH *)
SCIP_RETCODE graph_singletonAncestors_init(SCIP *, const GRAPH *, int, SINGLETONANS *)
int graph_edge_nPseudoAncestors(const GRAPH *, int)
void graph_knot_chg(GRAPH *p, int node, int term)
Definition: graph_node.c:86
SCIP_Bool graph_valid_pseudoAncestors(SCIP *, const GRAPH *)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
int *RESTRICT head
Definition: graphdefs.h:224
void graph_edge_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_edge.c:368
int source
Definition: graphdefs.h:195
SCIP_RETCODE graph_fixed_addEdge(SCIP *, int, GRAPH *)
#define Is_term(a)
Definition: graphdefs.h:102
void graph_knot_add(GRAPH *p, int term)
Definition: graph_node.c:64
int terms
Definition: graphdefs.h:192
int mark
Definition: graph_load.c:266
SCIP_RETCODE graph_pseudoAncestors_appendCopyNodeToEdge(SCIP *, int, int, SCIP_Bool, GRAPH *, SCIP_Bool *)
#define FALSE
Definition: def.h:87
int *RESTRICT inpbeg
Definition: graphdefs.h:202
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
int graph_edge_redirect(SCIP *, GRAPH *, int, int, int, SCIP_Real, SCIP_Bool, SCIP_Bool)
Definition: graph_edge.c:103
SCIP_Bool graph_knotIsNWLeaf(const GRAPH *g, int vertex)
Definition: graph_node.c:35
#define EAT_LAST
Definition: graphdefs.h:58
#define SCIPdebugMessage
Definition: pub_message.h:87
#define FARAWAY
Definition: graphdefs.h:89
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define STP_TERM_NONE
Definition: graphdefs.h:62
int *RESTRICT mark
Definition: graphdefs.h:198
void SCIPintListNodeFree(SCIP *scip, IDX **node)
Definition: misc_stp.c:325
int *RESTRICT oeat
Definition: graphdefs.h:231
SCIP_RETCODE SCIPintListNodeAppendCopy(SCIP *scip, IDX **node1, IDX *node2, SCIP_Bool *conflict)
Definition: misc_stp.c:197
int stp_type
Definition: graphdefs.h:264
IDX ** ancestors
Definition: graphdefs.h:234
SCIP_RETCODE graph_pseudoAncestors_appendCopySingToEdge(SCIP *, int, const SINGLETONANS *, SCIP_Bool, GRAPH *, SCIP_Bool *)
SCIP_RETCODE graph_pseudoAncestors_appendCopyArrayToEdge(SCIP *, int, const int *, int, GRAPH *, SCIP_Bool *)
SCIP_Bool graph_knot_isInRange(const GRAPH *g, int k)
Definition: graph_node.c:52
int *RESTRICT grad
Definition: graphdefs.h:201
SCIP_RETCODE graph_knot_contractLowdeg2High(SCIP *scip, GRAPH *g, int *solnode, int t, int s)
Definition: graph_node.c:539
#define NULL
Definition: lpi_spx1.cpp:155
void graph_knot_del(SCIP *scip, GRAPH *g, int k, SCIP_Bool freeancestors)
Definition: graph_node.c:111
#define Edge_anti(a)
Definition: graphdefs.h:106
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
IDX ** pcancestors
Definition: graphdefs.h:235
#define LT(a, b)
Definition: portab.h:81
void graph_edge_delFull(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_edge.c:418
#define SCIP_Bool
Definition: def.h:84
#define STP_TERM_NONLEAF
Definition: graphdefs.h:64
int *RESTRICT ieat
Definition: graphdefs.h:230
#define STP_NWPTSPG
Definition: graphdefs.h:48
void SCIPintListNodeAppend(IDX *node1, IDX *node2)
Definition: misc_stp.c:309
int *RESTRICT tail
Definition: graphdefs.h:223
#define flipedge(edge)
Definition: graphdefs.h:84
#define STP_TERM
Definition: graphdefs.h:61
void graph_singletonAncestors_freeMembers(SCIP *, SINGLETONANS *)
const int * graph_edge_getPseudoAncestors(const GRAPH *, int)
int *RESTRICT term
Definition: graphdefs.h:196
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
#define flipedge_Uint(edge)
Definition: graphdefs.h:85
void graph_edge_delHistory(SCIP *, GRAPH *, int)
Definition: graph_edge.c:466
#define CONNECT
Definition: graphdefs.h:87
SCIP_RETCODE graph_knot_replaceDeg2(SCIP *scip, int vertex, SCIP_Real edgecost, int ancestornode, GRAPH *g, SCIP_Bool *edgeEliminated)
Definition: graph_node.c:158
Portable definitions.
SCIP_Bool graph_typeIsUndirected(const GRAPH *)
Definition: graph_stats.c:69
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real * cost
Definition: graphdefs.h:221
#define STP_TERM_PSEUDO
Definition: graphdefs.h:63
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
SCIP_RETCODE graph_knot_contractFixed(SCIP *scip, GRAPH *g, int *solnode, int edge, int t, int s)
Definition: graph_node.c:521
int * contracttrace
Definition: graphdefs.h:238
#define SCIP_Real
Definition: def.h:177
int *RESTRICT outbeg
Definition: graphdefs.h:204
SCIP_RETCODE graph_knot_contract(SCIP *scip, GRAPH *g, int *solnode, int t, int s)
Definition: graph_node.c:264
int ksize
Definition: graphdefs.h:189
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:102
DCSR * dcsr_storage
Definition: graphdefs.h:271
#define Edge_even(a)
Definition: graphdefs.h:107
IDX * graph_edge_getAncestors(const GRAPH *, int)
void graph_knot_delFull(SCIP *scip, GRAPH *g, int k, SCIP_Bool freeancestors)
Definition: graph_node.c:131