# SCIP

Solving Constraint Integer Programs

graph_edge.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_edge.c
17  * @brief includes graph edge methods for Steiner problems
18  * @author Daniel Rehfeldt
19  *
20  * Graph edge 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  * Local methods
34  */
35
36 inline static
38  GRAPH* g, /**< the graph */
39  int e /**< the edge to be removed */
40  )
41 {
42  int i;
44  const int tail = g->tail[e];
45
46  assert(graph_edge_isInRange(g, e));
47
48  if( g->inpbeg[head] == e )
49  {
51  }
52  else
53  {
54  if( g->rootedgeprevs != NULL && head == g->source )
55  {
56  i = g->rootedgeprevs[e];
57  assert(g->ieat[i] == e);
58  if( g->ieat[e] >= 0 )
59  g->rootedgeprevs[g->ieat[e]] = i;
60  }
61  else
62  {
63  for( i = g->inpbeg[head]; g->ieat[i] != e; i = g->ieat[i] )
64  {
65  assert(i >= 0);
66  }
67  }
68
69  g->ieat[i] = g->ieat[e];
70  }
71
72  if( g->outbeg[tail] == e )
73  {
74  g->outbeg[tail] = g->oeat[e];
75  }
76  else
77  {
78  if( g->rootedgeprevs != NULL && tail == g->source )
79  {
80  i = g->rootedgeprevs[e];
81  assert(g->oeat[i] == e);
82  if( g->oeat[e] >= 0 )
83  g->rootedgeprevs[g->oeat[e]] = i;
84  }
85  else
86  {
87  for( i = g->outbeg[tail]; g->oeat[i] != e; i = g->oeat[i] )
88  {
89  assert(i >= 0);
90  }
91  }
92
93  g->oeat[i] = g->oeat[e];
94  }
95 }
96
97 /*
98  * Interface methods
99  */
100
101
102 /** redirects given edge eki */
104  SCIP* scip, /**< SCIP data structure */
105  GRAPH* g, /**< the graph */
106  int eki, /**< the edge */
107  int k, /**< new tail */
108  int j, /**< new head */
109  SCIP_Real cost, /**< new cost */
110  SCIP_Bool forcedelete, /**< delete edge eki if it is not used? */
111  SCIP_Bool checkexist /**< check if there is already an edge kj */
112  )
113 {
114  int e;
115
116  assert(scip && g);
117  assert(SCIPisGE(scip, cost, 0.0));
118
119  if( forcedelete )
120  graph_edge_del(NULL, g, eki, FALSE);
121
122  if( checkexist )
123  {
124  for( e = g->outbeg[k]; e != EAT_LAST; e = g->oeat[e] )
125  {
126  assert(g->tail[e] == k);
127
128  if( g->head[e] == j )
129  break;
130  }
131  }
132  else
133  {
134 #ifndef NDEBUG
135  /* make sure that the edge does not exist! */
136  for( e = g->outbeg[k]; e != EAT_LAST; e = g->oeat[e] )
137  {
138  assert(g->tail[e] == k);
139
140  if( g->head[e] == j )
141  break;
142  }
143  assert(e == EAT_LAST);
144 #endif
145
146  e = EAT_LAST;
147  }
148
149  /* does edge already exist? */
150  if( e != EAT_LAST )
151  {
152  /* correct cost */
153  if( SCIPisGT(scip, g->cost[e], cost) )
154  {
155  g->cost[e] = cost;
156  g->cost[Edge_anti(e)] = cost;
157  }
158  else
159  {
160  e = -1;
161  }
162  }
163  else
164  {
165  assert(graph_edge_isInRange(g, eki));
166
167  if( !forcedelete && g->ieat[eki] != EAT_FREE )
168  graph_edge_del(NULL, g, eki, FALSE);
169
170  assert(g->oeat[eki] == EAT_FREE);
171
172  e = eki;
173
176
177  g->cost[e] = cost;
179  g->tail[e] = k;
180  g->ieat[e] = g->inpbeg[j];
181  g->oeat[e] = g->outbeg[k];
182  g->inpbeg[j] = e;
183  g->outbeg[k] = e;
184
185  e = Edge_anti(eki);
186
187  g->cost[e] = cost;
189  g->tail[e] = j;
190  g->ieat[e] = g->inpbeg[k];
191  g->oeat[e] = g->outbeg[j];
192  g->inpbeg[k] = e;
193  g->outbeg[j] = e;
194  return eki;
195  }
196  return e;
197 }
198
199 /** reinsert an edge to replace two other edges */
201  SCIP* scip, /**< SCIP data structure */
202  GRAPH* g, /**< the graph */
203  int edge, /**< edge to reinsert */
204  int tail, /**< new tail */
206  SCIP_Real cost, /**< new edge cost */
207  int ancestornode, /**< node to copy ancestors from or -1 */
208  SINGLETONANS* ancestorsBackward, /**< backwards (edge) ancestors */
209  SINGLETONANS* ancestorsForward, /**< forward (edge) ancestors */
210  int* insertedge, /**< pointer to inserted edge or -1 */
211  SCIP_Bool* conflict /**< does the newly edge contain conflicts? (i.e. is redundant) */
212  )
213 {
214  const int newedge = graph_edge_redirect(scip, g, edge, tail, head, cost, FALSE, TRUE);
215
216  assert(ancestorsBackward && ancestorsForward && insertedge && conflict);
217  assert(ancestornode >= 0 || ancestornode == -1);
218
219  *conflict = FALSE;
220
221  /* is there a new edge? */
222  if( newedge >= 0 )
223  {
224  IDX* const ancestorsBack = ancestorsBackward->ancestors;
225  IDX* const revancestorsBack = ancestorsBackward->revancestors;
226  IDX* const ancestorsFor = ancestorsForward->ancestors;
227  IDX* const revancestorsFor = ancestorsForward->revancestors;
228
229  assert(ancestorsBack && ancestorsFor);
230  assert((revancestorsBack == NULL) == graph_typeIsUndirected(g));
231  assert((revancestorsFor == NULL) == graph_typeIsUndirected(g));
232
233  graph_edge_delHistory(scip, g, newedge);
234
235  if( !revancestorsBack )
236  {
237  const int edge_even = Edge_even(newedge);
238  assert(graph_typeIsUndirected(g));
239  assert(edge_even == flipedge(newedge) || edge_even == newedge);
240
241  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[edge_even]), ancestorsBack, NULL) );
242  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[edge_even]), ancestorsFor, NULL) );
243  }
244  else
245  {
246  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[newedge]), revancestorsBack, NULL) );
247  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[newedge]), ancestorsFor, NULL) );
248  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[Edge_anti(newedge)]), ancestorsBack, NULL) );
249  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[Edge_anti(newedge)]), revancestorsFor, NULL) );
250  }
251
252  SCIP_CALL( graph_pseudoAncestors_appendCopySingToEdge(scip, newedge, ancestorsBackward, TRUE, g, conflict) );
253  assert(!(*conflict));
254
255  SCIP_CALL( graph_pseudoAncestors_appendCopySingToEdge(scip, newedge, ancestorsForward, TRUE, g, conflict) );
256
257  /* ancestor node given?*/
258  if( ancestornode >= 0 )
259  {
260  const int edge_even = Edge_even(newedge);
261
262  assert(graph_pc_isPcMw(g));
263
264  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(g->ancestors[edge_even]), g->pcancestors[ancestornode], NULL) );
265
266  if( !(*conflict) )
267  SCIP_CALL( graph_pseudoAncestors_appendCopyNodeToEdge(scip, newedge, ancestornode, TRUE, g, conflict) );
268  }
269  }
270
271  *insertedge = newedge;
272
273  return SCIP_OKAY;
274 }
275
276
277 /** add a new edge to the graph */
279  SCIP* scip, /**< SCIP data structure */
280  GRAPH* g, /**< the graph */
281  int tail, /**< tail of the new edge */
283  SCIP_Real cost1, /**< tail to head cost */
284  SCIP_Real cost2 /**< head to tail cost */
285  )
286 {
287  int e;
288
289  assert(g != NULL);
290  assert(SCIPisGE(scip, cost1, 0.0) || SCIPisEQ(scip, cost1, (double) UNKNOWN));
291  assert(SCIPisGE(scip, cost2, 0.0) || SCIPisEQ(scip, cost2, (double) UNKNOWN));
292  assert(tail >= 0);
293  assert(tail < g->knots);
296
297  assert(g->esize >= g->edges + 2);
298
299  e = g->edges;
300
303
304  if( cost1 != UNKNOWN )
305  g->cost[e] = cost1;
306  g->tail[e] = tail;
309  g->oeat[e] = g->outbeg[tail];
311  g->outbeg[tail] = e;
312
313  e++;
314
315  if( cost2 != UNKNOWN )
316  g->cost[e] = cost2;
319  g->ieat[e] = g->inpbeg[tail];
321  g->inpbeg[tail] = e;
323
324  g->edges += 2;
325 }
326
327 /** add a bi-edge to the graph */
329  SCIP* scip, /**< SCIP data structure */
330  GRAPH* g, /**< the graph */
331  int tail, /**< tail of the new edge */
333  SCIP_Real cost /**< head to tail cost */
334  )
335 {
337 }
338
339
340 /** add a new edge to a subgraph */
342  SCIP* scip, /**< SCIP data structure */
343  const GRAPH* orggraph, /**< original graph */
344  const int* nodemapOrg2sub, /**< node mapping from original to subgraph */
345  int orgedge, /**< original edge */
346  GRAPH* subgraph /**< the subgraph */
347  )
348 {
349  const int e = orgedge;
350  const int orgtail = orggraph->tail[e];
352  const int newtail = nodemapOrg2sub[orgtail];
354
355  assert(e >= 0 && e < orggraph->edges);
356
357  if( graph_pc_isPcMw(orggraph) )
358  {
359  assert(orggraph->extended);
361  }
362
364 }
365
366
367 /** delete an edge from standard data structure */
369  SCIP* scip, /**< SCIP data structure */
370  GRAPH* g, /**< the graph */
371  int e, /**< the edge */
372  SCIP_Bool freeancestors /**< free edge ancestors? */
373  )
374 {
375  assert(g);
376  assert(e >= 0 && e < g->edges);
377
378  if( freeancestors && g->ancestors )
379  {
380  graph_edge_delHistory(scip, g, e);
381  }
382
383  /* delete first arc */
384  e -= e % 2;
385  assert(g->head[e] == g->tail[e + 1]);
386  assert(g->tail[e] == g->head[e + 1]);
387
390
391  removeEdge(g, e);
392
393  assert(g->ieat[e] != EAT_FREE);
394  assert(g->ieat[e] != EAT_HIDE);
395  assert(g->oeat[e] != EAT_FREE);
396  assert(g->oeat[e] != EAT_HIDE);
397
398  g->ieat[e] = EAT_FREE;
399  g->oeat[e] = EAT_FREE;
400
401  /* delete second arc */
402  e++;
403  removeEdge(g, e);
404
405  assert(g->ieat[e] != EAT_FREE);
406  assert(g->ieat[e] != EAT_HIDE);
407  assert(g->oeat[e] != EAT_FREE);
408  assert(g->oeat[e] != EAT_HIDE);
409
410  g->ieat[e] = EAT_FREE;
411  g->oeat[e] = EAT_FREE;
412
413  assert(g->tail[e] >= 0 && g->tail[e] < g->knots);
415 }
416
417 /** delete an edge from standard, DCSR (if existent) and CSR (if existent) data structures */
419  SCIP* scip, /**< SCIP data structure */
420  GRAPH* g, /**< the graph */
421  int e, /**< the edge */
422  SCIP_Bool freeancestors /**< free edge ancestors? */
423  )
424 {
425  assert(scip && g);
426  assert(e >= 0 && e < g->edges);
427
428  if( g->dcsr_storage )
429  {
430  int csredge;
431  assert(graph_valid_dcsr(g, FALSE));
432
433  csredge = g->dcsr_storage->id2csredge[e];
434  graph_dcsr_deleteEdgeBi(scip, g->dcsr_storage, csredge);
435
436  assert(graph_valid_dcsr(g, FALSE));
437  }
438
439  if( g->csr_storage )
440  {
441  assert(0 && "not yet supported");
442  }
443
444  graph_edge_del(scip, g, e, freeancestors);
445 }
446
447 /** deletes edges marked by given array */
449  SCIP* scip, /**< SCIP data structure */
450  GRAPH* g, /**< the graph */
451  const SCIP_Bool* edge_deletable, /**< marks edges to delete (of size nedges / 2) */
452  SCIP_Bool freeancestors /**< free edge ancestors? */
453  )
454 {
455  const int nedges = g->edges;
456
457  assert(g && edge_deletable);
458
459  for( int e = 0; e < nedges / 2; e++ )
460  if( edge_deletable[e] )
461  graph_edge_del(scip, g, e * 2, freeancestors);
462 }
463
464
465 /** free the history of an edge */
467  SCIP* scip, /**< SCIP data */
468  GRAPH* g, /**< graph data */
469  int edge /**< edge for which to free the history */
470  )
471 {
472  assert(scip && g);
473  assert(edge >= 0 && edge < g->edges);
474
475  SCIPintListNodeFree(scip, &(g->ancestors[edge]));
476  SCIPintListNodeFree(scip, &(g->ancestors[flipedge_Uint(edge)]));
477
478  graph_edge_delPseudoAncestors(scip, edge, g);
479 }
480
481
482 /** hide edge */
484  GRAPH* g, /**< the graph */
485  int e /**< the edge */
486  )
487 {
488  assert(g != NULL);
489  assert(e >= 0);
490  assert(e < g->edges);
491
492  /* Immer mit der ersten von beiden Anfangen
493  */
494  e -= e % 2;
495
496  assert(g->head[e] == g->tail[e + 1]);
497  assert(g->tail[e] == g->head[e + 1]);
498
501
502  removeEdge(g, e);
503
504  assert(g->ieat[e] != EAT_FREE);
505  assert(g->ieat[e] != EAT_HIDE);
506  assert(g->oeat[e] != EAT_FREE);
507  assert(g->oeat[e] != EAT_HIDE);
508
509  g->ieat[e] = EAT_HIDE;
510  g->oeat[e] = EAT_HIDE;
511
512  e++;
513
514  removeEdge(g, e);
515
516  assert(g->ieat[e] != EAT_FREE);
517  assert(g->ieat[e] != EAT_HIDE);
518  assert(g->oeat[e] != EAT_FREE);
519  assert(g->oeat[e] != EAT_HIDE);
520
521  g->ieat[e] = EAT_HIDE;
522  g->oeat[e] = EAT_HIDE;
523 }
void graph_edge_delPseudoAncestors(SCIP *, int, GRAPH *)
void graph_edge_delFull(SCIP *scip, GRAPH *g, int e, SCIP_Bool freeancestors)
Definition: graph_edge.c:418
Definition: graphdefs.h:224
int source
Definition: graphdefs.h:195
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE graph_pseudoAncestors_appendCopyNodeToEdge(SCIP *, int, int, SCIP_Bool, GRAPH *, SCIP_Bool *)
void graph_dcsr_deleteEdgeBi(SCIP *, DCSR *, int)
Definition: graph_util.c:1894
#define EAT_FREE
Definition: graphdefs.h:57
#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
#define EAT_LAST
Definition: graphdefs.h:58
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
CSR * csr_storage
Definition: graphdefs.h:270
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
SCIP_Bool extended
Definition: graphdefs.h:267
IDX ** ancestors
Definition: graphdefs.h:234
SCIP_RETCODE graph_pseudoAncestors_appendCopySingToEdge(SCIP *, int, const SINGLETONANS *, SCIP_Bool, GRAPH *, SCIP_Bool *)
Definition: graphdefs.h:201
int graph_edge_redirect(SCIP *scip, GRAPH *g, int eki, int k, int j, SCIP_Real cost, SCIP_Bool forcedelete, SCIP_Bool checkexist)
Definition: graph_edge.c:103
static void removeEdge(GRAPH *g, int e)
Definition: graph_edge.c:37
void graph_edge_delHistory(SCIP *scip, GRAPH *g, int edge)
Definition: graph_edge.c:466
#define NULL
Definition: lpi_spx1.cpp:155
#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
SCIP_Bool graph_valid_dcsr(const GRAPH *, SCIP_Bool verbose)
Definition: graph_util.c:1919
#define SCIP_Bool
Definition: def.h:84
int *RESTRICT ieat
Definition: graphdefs.h:230
int *RESTRICT tail
Definition: graphdefs.h:223
#define flipedge(edge)
Definition: graphdefs.h:84
void graph_pc_updateSubgraphEdge(const GRAPH *, const int *, int, GRAPH *)
#define flipedge_Uint(edge)
Definition: graphdefs.h:85
void graph_edge_hide(GRAPH *g, int e)
Definition: graph_edge.c:483
void graph_edge_delBlocked(SCIP *scip, GRAPH *g, const SCIP_Bool *edge_deletable, SCIP_Bool freeancestors)
Definition: graph_edge.c:448
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
SCIP_Bool graph_edge_isInRange(const GRAPH *, int)
Definition: graph_stats.c:110
int *RESTRICT rootedgeprevs
Definition: graphdefs.h:227
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
void graph_edge_del(SCIP *scip, GRAPH *g, int e, SCIP_Bool freeancestors)
Definition: graph_edge.c:368
#define SCIP_Real
Definition: def.h:177
int esize
Definition: graphdefs.h:218
Definition: graph_edge.c:328
int *RESTRICT outbeg
Definition: graphdefs.h:204
int edges
Definition: graphdefs.h:219
SCIP_RETCODE graph_edge_reinsert(SCIP *scip, GRAPH *g, int edge, int tail, int head, SCIP_Real cost, int ancestornode, SINGLETONANS *ancestorsBackward, SINGLETONANS *ancestorsForward, int *insertedge, SCIP_Bool *conflict)
Definition: graph_edge.c:200
void graph_edge_add(SCIP *scip, GRAPH *g, int tail, int head, SCIP_Real cost1, SCIP_Real cost2)
Definition: graph_edge.c:278
#define UNKNOWN
Definition: sepa_mcf.c:4095
#define EAT_HIDE
Definition: graphdefs.h:59
DCSR * dcsr_storage
Definition: graphdefs.h:271
void graph_edge_addSubgraph(SCIP *scip, const GRAPH *orggraph, const int *nodemapOrg2sub, int orgedge, GRAPH *subgraph)
Definition: graph_edge.c:341
#define Edge_even(a)
Definition: graphdefs.h:107