Scippy

SCIP

Solving Constraint Integer Programs

graph_sub.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_sub.c
17  * @brief includes several methods for Steiner problem sub-graphs
18  * @author Daniel Rehfeldt
19  *
20  * This file contains several basic methods to process subgraph of Steiner problem graphs.
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 SCIP_DEBUG
30 
31 #include "scip/misc.h"
32 #include <stdio.h>
33 #include <stdlib.h>
34 #include <assert.h>
35 #include "portab.h"
36 #include "graph.h"
37 #include "stpvector.h"
38 
39 
40 
41 /** edge transfer */
42 typedef struct edge_transfer
43 {
49 } EDGETRANS;
50 
51 
52 
53 /** in/out */
55 {
56  STP_Vectype(int) org_bordernodes;
57  STP_Vectype(int) org_spareedges;
58  int* org_contractRecord;
59  int* edgemap_subToOrg; /**< edges map */
60  int* nodemap_subToOrg; /**< node map */
61  int* nodemap_orgToSub; /**< node map */
62  int org_nnodes;
63  int sub_nnodes;
64  int sub_nedges;
65  SCIP_Bool rootIsTransfered;
66  SCIP_Bool useEdgeMap;
67  SCIP_Bool useNewHistory;
68 };
69 
70 
71 /*
72  * local methods
73  */
74 
75 
76 
77 /** initializes subgraph */
78 static
80  const GRAPH* orggraph, /**< original graph */
81  SUBINOUT* subinout /**< data structure for handling inclusion/exclusion of sub-problems */
82  )
83 {
84  int* RESTRICT nodemap_orgToSub = subinout->nodemap_orgToSub;
85  int* RESTRICT nodemap_subToOrg = subinout->nodemap_subToOrg;
86  const int nnodes = graph_get_nNodes(orggraph);
87  const int* const isMarked = orggraph->mark;
88  int sub_n = 0;
89  int sub_m = 0;
90 #ifdef SCIP_DEBUG
91  int sub_t = 0;
92 #endif
93 
94  for( int i = 0; i < nnodes; i++ )
95  {
96  if( !isMarked[i] )
97  {
98  nodemap_orgToSub[i] = -1;
99  continue;
100  }
101 
102  nodemap_subToOrg[sub_n] = i;
103  nodemap_orgToSub[i] = sub_n;
104 
105  sub_n++;
106 
107 #ifdef SCIP_DEBUG
108  if( Is_term(orggraph->term[i]) )
109  sub_t++;
110 #endif
111 
112  for( int e = orggraph->outbeg[i]; e != EAT_LAST; e = orggraph->oeat[e] )
113  {
114  const int head = orggraph->head[e];
115  if( isMarked[head] )
116  {
117  sub_m++;
118  }
119  }
120  }
121 
122  assert(sub_m % 2 == 0);
123 
124  subinout->sub_nnodes = sub_n;
125  subinout->sub_nedges = sub_m;
126 
127 #ifdef SCIP_DEBUG
128  printf("subgraph: nodes=%d, edges=%d, terms=%d \n", sub_n, sub_m, sub_t);
129 #endif
130 }
131 
132 
133 /** helper */
134 static
136  const GRAPH* orggraph, /**< original graph */
137  SUBINOUT* subinout, /**< data structure for handling inclusion/exclusion of sub-problems */
138  GRAPH* subgraph /**< graph to fill */
139  )
140 {
141  const int* const nodemap_subToOrg = subinout->nodemap_subToOrg;
142  const int ksize = subgraph->ksize;
143  assert(subgraph->source == -1);
144 
145  for( int i = 0; i < ksize; i++ )
146  {
147  const int orgnode = nodemap_subToOrg[i];
148  assert(graph_knot_isInRange(orggraph, orgnode));
149 
150  if( Is_term(orggraph->term[orgnode]) )
151  {
152  graph_knot_add(subgraph, STP_TERM);
153  if( subgraph->source == -1 )
154  subgraph->source = i;
155 
156  if( orggraph->source == orgnode )
157  {
158  subgraph->source = i;
159  subinout->rootIsTransfered = TRUE;
160  }
161  }
162  else
163  {
164  graph_knot_add(subgraph, STP_TERM_NONE);
165  }
166  }
167 
168  assert(subgraph->knots == ksize);
169  assert(subgraph->source != -1);
170 }
171 
172 
173 /** helper */
174 static
176  SCIP* scip, /**< SCIP data structure */
177  GRAPH* orggraph, /**< original graph */
178  SCIP_Bool moveFixedEdges, /**< move fixed edges? */
179  GRAPH* subgraph /**< graph to fill */
180  )
181 {
182  assert(subgraph->esize >= 2);
183 
184  SCIP_CALL( SCIPallocMemoryArray(scip, &(subgraph->ancestors), subgraph->esize) );
185 
186  SCIP_CALL( graph_initPseudoAncestorsSized(scip, subgraph->esize, subgraph) );
187 
188  if( graph_getNpseudoAncestors(orggraph) > 0 )
190 
191  assert(graph_getNpseudoAncestors(orggraph) == graph_getNpseudoAncestors(subgraph));
192 
193  SCIP_CALL( graph_copyFixed(scip, orggraph, moveFixedEdges, subgraph) );
194 
195  return SCIP_OKAY;
196 }
197 
198 
199 /** helper */
200 static
202  SCIP* scip, /**< SCIP data structure */
203  SCIP_Bool useNewHistory, /**< use new history? */
204  SCIP_Bool moveEdges, /**< move edges and in particular their history? */
205  const EDGETRANS* edgetrans, /**< helper for edge transfer */
206  GRAPH* source_graph, /**< source graph */
207  GRAPH* target_graph /**< graph to fill */
208  )
209 {
210  const int source_edge = edgetrans->source_edge;
211  const int target_edge = edgetrans->target_edge;
212  const int target_tail = edgetrans->target_tail;
213  const int target_head = edgetrans->target_head;
214  const int target_edgeRev = flipedge(target_edge);
215 
216  assert(graph_edge_isInRange(source_graph, source_edge));
217  assert(graph_knot_isInRange(target_graph, target_tail));
218  assert(graph_knot_isInRange(target_graph, target_head));
219 
220  if( !useNewHistory )
221  {
222  IDX** ancestors = target_graph->ancestors;
223  const int npseudoancestors = graph_edge_nPseudoAncestors(source_graph, source_edge);
224  SCIP_Bool conflict = FALSE;
225  const int target_edgeEven = Edge_even(target_edge);
226 
227  assert(graph_typeIsUndirected(source_graph)); /* NOTE: otherwise ancestor copy would not be correct */
228 
229  if( npseudoancestors != 0 )
230  {
231  const int* const pseudoancestors = graph_edge_getPseudoAncestors(source_graph, source_edge);
232  assert(pseudoancestors);
233 
234  SCIP_CALL( graph_pseudoAncestors_appendCopyArrayToEdge(scip, target_edge, pseudoancestors, npseudoancestors, target_graph, &conflict));
235  assert(!conflict);
236  }
237  assert(graph_edge_nPseudoAncestors(target_graph, target_edge) == npseudoancestors);
238  assert(graph_edge_nPseudoAncestors(target_graph, target_edgeRev) == npseudoancestors);
239 
240  ancestors[target_edge] = NULL;
241  ancestors[target_edgeRev] = NULL;
242 
243  if( moveEdges )
244  {
245  ancestors[target_edgeEven] = graph_edge_getAncestors(source_graph, source_edge);
246  source_graph->ancestors[source_edge] = source_graph->ancestors[flipedge(source_edge)] = NULL;
247  }
248  else
249  {
250  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(ancestors[target_edgeEven]),
251  graph_edge_getAncestors(source_graph, source_edge), &conflict) );
252  }
253  assert(!conflict);
254  }
255 
256  assert(EQ(source_graph->cost[source_edge], source_graph->cost[flipedge(source_edge)]));
257 
258  if( edgetrans->redirectEdge )
259  {
260  (void) graph_edge_redirect(scip, target_graph, target_edge, target_tail, target_head,
261  source_graph->cost[source_edge], FALSE, FALSE);
262  }
263  else
264  {
265  graph_edge_add(scip, target_graph, target_tail, target_head, source_graph->cost[source_edge], source_graph->cost[source_edge]);
266  }
267 
268  return SCIP_OKAY;
269 }
270 
271 
272 /** contracts border nodes of subgraph with remaining */
273 static
275  const GRAPH* subgraph, /**< sub graph */
276  const GRAPH* orggraph, /**< original graph */
277  SUBINOUT* subinout /**< helper */
278  )
279 {
280  int* const nodemap_subToOrg = subinout->nodemap_subToOrg;
281  const int* const contractRecord = subinout->org_contractRecord;
282  const int nnodes_sub = graph_get_nNodes(subgraph);
283 
284  for( int i = 0; i < nnodes_sub; i++ )
285  {
286  if( subgraph->grad[i] != 0 || Is_term(subgraph->term[i]) )
287  {
288  int orgnode = nodemap_subToOrg[i];
289 
290  if( orggraph->grad[orgnode] == 0 )
291  {
292  orgnode = contractRecord[orgnode];
293 
294  if( orgnode != -1 )
295  {
296  assert(graph_knot_isInRange(orggraph, orgnode));
297  nodemap_subToOrg[i] = orgnode;
298  }
299  else
300  {
301  assert(orggraph->terms == 1);
302  }
303  }
304  }
305 
306 #ifndef NDEBUG
307  if( subgraph->grad[i] == 0 && Is_term(subgraph->term[i]) )
308  assert(subgraph->terms == 1);
309 #endif
310  }
311 
312 #ifndef NDEBUG
313  for( int i = 0; i < nnodes_sub; i++ )
314  {
315  if( Is_term(subgraph->term[i]) )
316  {
317  const int orgnode = nodemap_subToOrg[i];
318  assert(Is_term(orggraph->term[orgnode]));
319  }
320  }
321 #endif
322 }
323 
324 
325 /** helper */
326 static
328  SCIP* scip, /**< SCIP data structure */
329  GRAPH* orggraph, /**< original graph */
330  SUBINOUT* subinout, /**< data structure for inserting/extracting sub-problem */
331  GRAPH* subgraph /**< graph to fill */
332  )
333 {
334  const int* const isMarked = orggraph->mark;
335  int* RESTRICT edgemap_subToOrg = subinout->edgemap_subToOrg;
336  const int* const nodemap_subToOrg = subinout->nodemap_subToOrg;
337  const int* const nodemap_orgToSub = subinout->nodemap_orgToSub;
338  const int subnnodes = graph_get_nNodes(subgraph);
339  const SCIP_Bool useEdgeMap = subinout->useEdgeMap;
340 
341  for( int i = 0; i < subnnodes; i++ )
342  {
343  const int orgtail = nodemap_subToOrg[i];
344  assert(graph_knot_isInRange(orggraph, orgtail));
345 
346  for( int e = orggraph->outbeg[orgtail]; e != EAT_LAST; e = orggraph->oeat[e] )
347  {
348  const int orghead = orggraph->head[e];
349 
350  assert(isMarked[orgtail]);
351  assert(orgtail == orggraph->tail[e]);
352 
353  /* NOTE: avoid double inclusion of edge */
354  if( isMarked[orghead] && orghead > orgtail )
355  {
356  const int subhead = nodemap_orgToSub[orghead];
357  const EDGETRANS edgetransfer = { .source_edge = e, .target_edge = subgraph->edges,
358  .target_tail = i, .target_head = subhead, .redirectEdge = FALSE };
359  assert(graph_knot_isInRange(subgraph, subhead));
360  assert(nodemap_orgToSub[orgtail] == i);
361 
362  if( useEdgeMap )
363  {
364  assert(edgemap_subToOrg);
365  edgemap_subToOrg[subgraph->edges] = e;
366  edgemap_subToOrg[subgraph->edges + 1] = flipedge(e);
367  }
368 
369  SCIP_CALL( extractSubgraphAddEdge(scip, subinout->useNewHistory, FALSE, &edgetransfer, orggraph, subgraph) );
370  }
371  }
372  }
373 
374  subgraph->orgedges = MAX(orggraph->edges, orggraph->orgedges);
375  assert(subgraph->edges == subgraph->esize);
376 
377  return SCIP_OKAY;
378 }
379 
380 
381 /** collects border nodes (cut vertices) of subgraph */
382 static
384  SCIP* scip, /**< SCIP data structure */
385  const GRAPH* orggraph, /**< original graph */
386  const GRAPH* subgraph, /**< sub graph */
387  SUBINOUT* subinout /**< data structure for handling inclusion/exclusion of sub-problems */
388  )
389 {
390  const int* const isMarked = orggraph->mark;
391  const int subnnodes = graph_get_nNodes(subgraph);
392  const int* const nodemap_subToOrg = subinout->nodemap_subToOrg;
393 
394  assert(StpVecGetSize(subinout->org_bordernodes) == 0);
395 
396  for( int i = 0; i < subnnodes; i++ )
397  {
398  const int orgnode = nodemap_subToOrg[i];
399  assert(graph_knot_isInRange(orggraph, orgnode));
400  assert(isMarked[orgnode]);
401 
402  for( int e = orggraph->outbeg[orgnode]; e != EAT_LAST; e = orggraph->oeat[e] )
403  {
404  const int orghead = orggraph->head[e];
405 
406  if( !isMarked[orghead] )
407  {
408  StpVecPushBack(scip, subinout->org_bordernodes, orgnode);
409  SCIPdebugMessage("added border node %d (subnode=%d) \n", orgnode, i);
410 
411  assert(Is_term(subgraph->term[i]));
412  break;
413  }
414  }
415  }
416 
417  SCIPdebugMessage("number of collected border nodes %d \n", StpVecGetSize(subinout->org_bordernodes));
418 }
419 
420 
421 /** contracts border nodes of subgraph with remaining */
422 static
424  SCIP* scip, /**< SCIP data structure */
425  const GRAPH* subgraph, /**< sub graph */
426  SUBINOUT* subinout, /**< helper */
427  GRAPH* orggraph /**< original graph */
428  )
429 {
430  const int* const nodemap_subToOrg = subinout->nodemap_subToOrg;
431  const int* const nodemap_orgToSub = subinout->nodemap_orgToSub;
432  int* const contractRecord = subinout->org_contractRecord;
433  STP_Vectype(int) bordernodes = subinout->org_bordernodes;
434 
435  SCIPdebugMessage("number of border nodes to contract: %d \n", StpVecGetSize(subinout->org_bordernodes));
436 
437  for( int i = 0; i < StpVecGetSize(bordernodes); i++ )
438  {
439  const int orgnode = bordernodes[i];
440  const int subnode = nodemap_orgToSub[orgnode];
441 
442  assert(graph_knot_isInRange(orggraph, orgnode));
443  assert(graph_knot_isInRange(subgraph, subnode));
444  assert(orggraph->grad[orgnode] > 0);
445 
446  if( subgraph->grad[subnode] == 0 )
447  {
448  int subnode_traced;
449  int orgnode_traced;
450 
451  if( Is_term(subgraph->term[subnode]) )
452  {
453  assert(!graph_knot_hasContractTrace(subnode, subgraph));
454  assert(subgraph->terms == 1);
455  continue;
456  }
457  SCIPdebugMessage("border subnode %d orgnode %d \n", subnode, orgnode);
458 
459  subnode_traced = graph_contractTrace(subnode, subgraph);
460  orgnode_traced = nodemap_subToOrg[subnode_traced];
461 
462  SCIPdebugMessage("traced %d to %d \n", orgnode, orgnode_traced);
463  SCIPdebugMessage("contracting %d->%d \n", orgnode, orgnode_traced);
464 
465  /* NOTE: orgnode_traced survives */
466  SCIP_CALL( graph_knot_contract(scip, orggraph, NULL, orgnode_traced, orgnode) );
467  assert(contractRecord[orgnode] == -1 && contractRecord[orgnode_traced] == -1);
468  contractRecord[orgnode] = orgnode_traced;
469  }
470  }
471 
472  if( bordernodes )
473  StpVecClear(bordernodes);
474 
475  return SCIP_OKAY;
476 }
477 
478 
479 /** builds subgraph */
480 static
482  SCIP* scip, /**< SCIP data structure */
483  GRAPH* orggraph, /**< original graph */
484  SUBINOUT* subinout, /**< data structure for handling inclusion/exclusion of sub-problems */
485  GRAPH** subgraph /**< graph to be created */
486  )
487 {
488  GRAPH* subg;
489 
490  extractSubgraphGetSizeAndMap(orggraph, subinout);
491 
492  SCIP_CALL( graph_init(scip, subgraph, subinout->sub_nnodes, subinout->sub_nedges, 1) );
493  subg = *subgraph;
494  assert(subg->ksize == subinout->sub_nnodes);
495  assert(subg->esize == subinout->sub_nedges);
496 
497  if( graph_typeIsSpgLike(orggraph) )
498  subg->stp_type = STP_SPG;
499 
500  extractSubgraphAddNodes(orggraph, subinout, subg);
501  if( !subinout->useNewHistory )
502  {
503  SCIP_CALL( extractSubgraphInitHistory(scip, orggraph, TRUE, subg) );
504  }
505  SCIP_CALL( extractSubgraphAddEdgesWithHistory(scip, orggraph, subinout, subg) );
506 
507  SCIP_CALL( graph_path_init(scip, subg) );
508  SCIP_CALL( graph_initContractTracing(scip, subg) );
509 
510  return SCIP_OKAY;
511 }
512 
513 
514 /** helper */
515 static
517  SCIP* scip, /**< SCIP data structure */
518  GRAPH* subgraph, /**< sub-graph */
519  GRAPH* orggraph /**< original graph */
520  )
521 {
522  const int npseudoans_sub = graph_getNpseudoAncestors(subgraph);
523  const int npseudoans_org = graph_getNpseudoAncestors(orggraph);
524 
525  assert(npseudoans_org <= npseudoans_sub);
526 
527  if( npseudoans_org < npseudoans_sub )
528  graph_addPseudoAncestors(npseudoans_sub - npseudoans_org, orggraph);
529 
530  assert(graph_getNpseudoAncestors(subgraph) == graph_getNpseudoAncestors(orggraph));
531 
532  if( orggraph->fixedcomponents )
533  {
534  graph_fixed_resetMoved(orggraph);
535  graph_free_fixed(scip, orggraph);
536  }
537  assert(orggraph->fixedcomponents == NULL);
538 
539  orggraph->fixedcomponents = subgraph->fixedcomponents;
540 
541  assert(graph_getNfixpseudonodes(subgraph) == graph_getNfixpseudonodes(orggraph));
542  subgraph->fixedcomponents = NULL;
543 }
544 
545 
546 /** helper */
547 static
549  SCIP* scip, /**< SCIP data structure */
550  GRAPH* subgraph, /**< graph to be inserted */
551  SUBINOUT* subinsertion, /**< data structure for handling inclusion/exclusion of sub-problems */
552  GRAPH* orggraph /**< original graph */
553  )
554 {
555  STP_Vectype(int) spareedges = subinsertion->org_spareedges;
556  int sparecount = StpVecGetSize(spareedges) - 1;
557  const int* nodemap_subToOrg = subinsertion->nodemap_subToOrg;
558  const int sub_nedges = graph_get_nEdges(subgraph);
559 
560  assert(sparecount >= 0);
561 
562  for( int e = 0; e < sub_nedges; e += 2 )
563  {
564  assert(sparecount >= 0 || subgraph->oeat[e] == EAT_FREE);
565  assert(sparecount == StpVecGetSize(spareedges) - 1);
566 
567  if( subgraph->oeat[e] != EAT_FREE )
568  {
569  const int orgtail = nodemap_subToOrg[subgraph->tail[e]];
570  const int orghead = nodemap_subToOrg[subgraph->head[e]];
571  const EDGETRANS edgetransfer = { .source_edge = e,
572  .target_edge = spareedges[sparecount],
573  .target_tail = orgtail, .target_head = orghead,
574  .redirectEdge = TRUE };
575  assert(graph_knot_isInRange(orggraph, orgtail));
576  assert(graph_knot_isInRange(orggraph, orghead));
577  assert(graph_edge_isDeleted(orggraph, spareedges[sparecount]));
578 
579  SCIP_CALL( extractSubgraphAddEdge(scip, FALSE, TRUE, &edgetransfer, subgraph, orggraph) );
580  StpVecPopBack(spareedges);
581  sparecount--;
582  }
583  }
584 
585  return SCIP_OKAY;
586 }
587 
588 
589 /** helper */
590 static
592  const GRAPH* subgraph, /**< graph to be inserted */
593  SUBINOUT* subinout, /**< data structure for handling inclusion/exclusion of sub-problems */
594  GRAPH* orggraph /**< original graph */
595  )
596 {
597  const int* nodemap_subToOrg = subinout->nodemap_subToOrg;
598  const int sub_nnodes = graph_get_nNodes(subgraph);
599  int* const org_contracttrace = orggraph->contracttrace;
600 
601  assert(nodemap_subToOrg);
602 
603  for( int subnode = 0; subnode < sub_nnodes; subnode++ )
604  {
605  const int orgnode = nodemap_subToOrg[subnode];
606 
607  graph_knot_chg(orggraph, orgnode, subgraph->term[subnode]);
608 
609  if( org_contracttrace && graph_knot_hasContractTrace(subnode, subgraph) && orggraph->grad[orgnode] == 0 )
610  {
611  const int i_traced = graph_contractTrace(subnode, subgraph);
612  const int orgnode_traced = nodemap_subToOrg[i_traced];
613  assert(org_contracttrace[orgnode] == -1);
614  assert(subgraph->grad[subnode] == 0);
615 
616  org_contracttrace[orgnode] = orgnode_traced;
617  }
618  }
619 
620  if( subinout->rootIsTransfered )
621  {
622  assert(graph_knot_isInRange(subgraph, subgraph->source));
623 
624  orggraph->source = nodemap_subToOrg[subgraph->source];
625  assert(Is_term(orggraph->term[orggraph->source]));
626  }
627 
628  return SCIP_OKAY;
629 }
630 
631 
632 /** helper */
633 static
635  SCIP* scip, /**< SCIP data structure */
636  const GRAPH* subgraph, /**< graph to be inserted */
637  SUBINOUT* subinout, /**< data structure for handling inclusion/exclusion of sub-problems */
638  GRAPH* orggraph /**< original graph */
639  )
640 {
641  const int* nodemap_orgToSub = subinout->nodemap_orgToSub;
642  const int* nodemap_subToOrg = subinout->nodemap_subToOrg;
643  const int sub_nnodes = graph_get_nNodes(subgraph);
644 
645  assert(nodemap_orgToSub && nodemap_subToOrg);
646 
647  for( int i = 0; i < sub_nnodes; i++ )
648  {
649  const int orgnode = nodemap_subToOrg[i];
650  int e = orggraph->outbeg[orgnode];
651 
652  while( e != EAT_LAST )
653  {
654  const int enext = orggraph->oeat[e];
655  const int orghead = orggraph->head[e];
656 
657  /* does the head correspond to subgraph? */
658  if( nodemap_orgToSub[orghead] >= 0 )
659  {
660  assert(graph_knot_isInRange(subgraph, nodemap_orgToSub[orghead]));
661  StpVecPushBack(scip, subinout->org_spareedges, e);
662  graph_edge_del(scip, orggraph, e, TRUE);
663  }
664 
665  e = enext;
666  }
667  }
668 
669  return SCIP_OKAY;
670 }
671 
672 
673 /** builds subgraph */
674 static
676  SCIP* scip, /**< SCIP data structure */
677  GRAPH* subgraph, /**< graph to be inserted */
678  SUBINOUT* subinout, /**< data structure for inserting/extracting sub-problem */
679  GRAPH* orggraph /**< original graph */
680  )
681 {
682  assert(StpVecGetSize(subinout->org_spareedges) == 0);
683  assert(subgraph->edges <= orggraph->edges);
684  assert(subgraph->knots <= orggraph->knots);
685  assert(subinout->sub_nnodes == subgraph->knots);
686  assert(subinout->org_nnodes == orggraph->knots);
687 
688  reinsertSubgraphTransferFixedHistory(scip, subgraph, orggraph);
689  SCIP_CALL( reinsertSubgraphDeleteOldEdges(scip, subgraph, subinout, orggraph) );
690  SCIP_CALL( reinsertSubgraphTransferEdges(scip, subgraph, subinout, orggraph) );
691  SCIP_CALL( reinsertSubgraphTransferTerminals(subgraph, subinout, orggraph) );
692 
693  SCIP_CALL( borderNodesContract(scip, subgraph, subinout, orggraph) );
694  reinsertSubgraphAdaptSubToOrgMap(subgraph, orggraph, subinout);
695 
696  StpVecClear(subinout->org_spareedges);
697 
698  return SCIP_OKAY;
699 }
700 
701 
702 /*
703  * Interface methods
704  */
705 
706 
707 
708 /** Obtains a new subgraph corresponding to marked nodes.
709  * Also fills a node map from the new to the original nodes.
710  * Creates a shallow copy and moves parts wrt ancestor information:
711  * ancestors and pseudo-ancestors are kept/moved and will be modified also for original graph! */
713  SCIP* scip, /**< SCIP data structure */
714  GRAPH* orggraph, /**< original graph */
715  SUBINOUT* subinout, /**< data structure for inserting/extracting sub-problem */
716  GRAPH** subgraph /**< graph to be created */
717  )
718 {
719  assert(scip && orggraph && subinout);
720  assert(subinout->org_nnodes == orggraph->knots);
721  assert(!graph_pc_isPcMw(orggraph) && "not yet supported");
722 
723  SCIP_CALL( extractSubgraphBuild(scip, orggraph, subinout, subgraph) );
724 
725  borderNodesCollect(scip, orggraph, *subgraph, subinout);
726  (*subgraph)->withInexactReductions = orggraph->withInexactReductions;
727 
728  return SCIP_OKAY;
729 }
730 
731 
732 /** initializes */
734  SCIP* scip, /**< SCIP data structure */
735  const GRAPH* orggraph, /**< original graph */
736  SUBINOUT** subinout /**< data structure for handling inclusion/exclusion of sub-problems */
737  )
738 {
739  SUBINOUT* sub;
740  const int nnodes = graph_get_nNodes(orggraph);
741 
742  assert(scip && orggraph);
743 
744  SCIP_CALL( SCIPallocMemory(scip, subinout) );
745  sub = *subinout;
746 
747  sub->org_nnodes = nnodes;
748  sub->sub_nnodes = -1;
749  sub->sub_nedges = -1;
750  sub->rootIsTransfered = FALSE;
751  sub->useNewHistory = FALSE;
752 
753  sub->edgemap_subToOrg = NULL;
754  SCIP_CALL( SCIPallocMemoryArray(scip, &(sub->org_contractRecord), nnodes) );
755  SCIP_CALL( SCIPallocMemoryArray(scip, &(sub->nodemap_subToOrg), nnodes) );
756  SCIP_CALL( SCIPallocMemoryArray(scip, &(sub->nodemap_orgToSub), nnodes) );
757  sub->org_spareedges = NULL;
758  sub->org_bordernodes = NULL;
759  sub->useEdgeMap = FALSE;
760 
761  for( int i = 0; i < nnodes; i++ )
762  sub->org_contractRecord[i] = -1;
763 
764  return SCIP_OKAY;
765 }
766 
767 
768 /** activates */
770  const GRAPH* orggraph, /**< original graph */
771  SUBINOUT* subinout /**< data structure for handling inclusion/exclusion of sub-problems */
772  )
773 {
774  const int nedges = graph_get_nEdges(orggraph);
775 
776  assert(subinout);
777  assert(!subinout->useEdgeMap);
778  assert(!subinout->edgemap_subToOrg);
779 
780  SCIP_CALL( SCIPallocMemoryArray(scip, &(subinout->edgemap_subToOrg), nedges) );
781  subinout->useEdgeMap = TRUE;
782 
783  return SCIP_OKAY;
784 }
785 
786 
787 /** activates */
789  SUBINOUT* subinout /**< data structure for handling inclusion/exclusion of sub-problems */
790  )
791 {
792  assert(subinout);
793  assert(!subinout->useNewHistory);
794 
795  subinout->useNewHistory = TRUE;
796 }
797 
798 /** gets nodes map */
800  const SUBINOUT* subinout /**< data structure for handling inclusion/exclusion of sub-problems */
801  )
802 {
803  assert(subinout);
804  assert(subinout->nodemap_subToOrg);
805 
806 
807  return subinout->nodemap_subToOrg;
808 }
809 
810 
811 /** gets edge map */
813  const SUBINOUT* subinout /**< data structure for handling inclusion/exclusion of sub-problems */
814  )
815 {
816  assert(subinout);
817  assert(subinout->useEdgeMap);
818  assert(subinout->edgemap_subToOrg);
819 
820  return subinout->edgemap_subToOrg;
821 }
822 
823 
824 /** gets nodes map */
826  const SUBINOUT* subinout /**< data structure for handling inclusion/exclusion of sub-problems */
827  )
828 {
829  assert(subinout);
830  assert(subinout->nodemap_orgToSub);
831 
832  return subinout->nodemap_orgToSub;
833 }
834 
835 
836 /** get contraction record for cut nodes (-1 if no contraction) */
838  const SUBINOUT* subinout /**< data structure for handling inclusion/exclusion of sub-problems */
839  )
840 {
841  assert(subinout);
842 
843  return subinout->org_contractRecord;
844 }
845 
846 
847 /** new history per subproblem is being used? */
849  const SUBINOUT* subinout /**< data structure for handling inclusion/exclusion of sub-problems */
850  )
851 {
852  assert(subinout);
853 
854  return subinout->useNewHistory;
855 }
856 
857 
858 /** frees */
860  SCIP* scip, /**< SCIP data structure */
861  SUBINOUT** subinout /**< data structure for handling inclusion/exclusion of sub-problems */
862  )
863 {
864  SUBINOUT* sub;
865 
866  assert(scip && subinout);
867 
868  sub = *subinout;
869 
870  StpVecFree(scip, sub->org_bordernodes);
871  StpVecFree(scip, sub->org_spareedges);
872  SCIPfreeMemoryArrayNull(scip, &(sub->edgemap_subToOrg));
873  SCIPfreeMemoryArray(scip, &(sub->nodemap_orgToSub));
874  SCIPfreeMemoryArray(scip, &(sub->nodemap_subToOrg));
875  SCIPfreeMemoryArray(scip, &(sub->org_contractRecord));
876 
877  SCIPfreeMemory(scip, subinout);
878 }
879 
880 
881 /** cleans */
883  SCIP* scip, /**< SCIP data structure */
884  SUBINOUT* subinout /**< data structure for handling inclusion/exclusion of sub-problems */
885  )
886 {
887  assert(scip && subinout);
888 
889  if( subinout->org_bordernodes )
890  StpVecClear(subinout->org_bordernodes);
891 }
892 
893 
894 /** gets ancestor */
896  int node, /**< node to get ancestors for */
897  const SUBINOUT* subinout /**< data structure for handling inclusion/exclusion of sub-problems */
898  )
899 {
900  int ancestor;
901  const int* record;
902 
903  assert(subinout);
904  assert(subinout->org_contractRecord);
905  assert(0 <= node && node < subinout->org_nnodes);
906 
907  record = subinout->org_contractRecord;
908 
909  for( ancestor = node; record[ancestor] != -1; ancestor = record[ancestor] )
910  {
911  assert(0 <= ancestor && ancestor < subinout->org_nnodes);
912  }
913 
914  return ancestor;
915 }
916 
917 
918 /** completes history
919  * NOTE: necessary to allocate block memory on subscip */
921  SCIP* scip, /**< SCIP data structure */
922  const int* edgemap_subToOrg, /**< maps edges of subgraph to original graph */
923  GRAPH* orggraph, /**< original graph */
924  GRAPH* subgraph /**< graph to fill */
925  )
926 {
927  const int nedges = graph_get_nEdges(subgraph);
928  const int* tail = subgraph->tail;
929  const int* head = subgraph->head;
930  int* orgtail;
931  int* orghead;
932  SCIP_Bool moveFixedEdges;
933 
934  assert(scip);
935  assert(!subgraph->orgtail && !subgraph->orghead);
936  assert(!subgraph->pseudoancestors);
937  assert(nedges >= 2);
938  assert(edgemap_subToOrg);
939 
940  moveFixedEdges = FALSE;
941  SCIP_CALL( extractSubgraphInitHistory(scip, orggraph, moveFixedEdges, subgraph) );
942  /* NOTE we want to have only the fixed pseudo-ancestor, or we get into trouble with the retransformation */
943 
944  if( orggraph->fixedcomponents )
945  graph_free_fixedEdgesOnly(scip, subgraph);
946 
947  SCIP_CALL( SCIPallocMemoryArray(scip, &(subgraph->orgtail), nedges) );
948  SCIP_CALL( SCIPallocMemoryArray(scip, &(subgraph->orghead), nedges) );
949 
950  orgtail = subgraph->orgtail;
951  orghead = subgraph->orghead;
952 
953  BMScopyMemoryArray(orgtail, tail, nedges);
954  BMScopyMemoryArray(orghead, head, nedges);
955 
956  for( int e = 0; e < nedges; e += 2 )
957  {
958  const int orgedge = edgemap_subToOrg[e];
959  const int npseudoancestors = graph_edge_nPseudoAncestors(orggraph, orgedge);
960 
961  assert(EQ(orggraph->cost[orgedge], subgraph->cost[e]));
962 
963  if( npseudoancestors != 0 )
964  {
965  const int* const pseudoancestors = graph_edge_getPseudoAncestors(orggraph, orgedge);
966  SCIP_Bool conflict = FALSE;
967  assert(pseudoancestors);
968  assert(graph_edge_nPseudoAncestors(subgraph, e) == 0);
969 
970  SCIP_CALL( graph_pseudoAncestors_appendCopyArrayToEdge(scip, e, pseudoancestors, npseudoancestors, subgraph, &conflict));
971  assert(!conflict);
972  }
973  }
974 
975  SCIP_CALL( graph_initAncestors(scip, subgraph) );
976 
977  return SCIP_OKAY;
978 }
979 
980 
981 /** reinserts extracted (and modified) subgraph; also deletes subgraph.
982  * Dual to "graph_subgraphExtract" */
984  SCIP* scip, /**< SCIP data structure */
985  SUBINOUT* subinout, /**< data structure for handling inclusion/exclusion of sub-problems */
986  GRAPH* orggraph, /**< original graph */
987  GRAPH** subgraph /**< graph to be reinserted (and freed) */
988  )
989 {
990  GRAPH* subg;
991  assert(scip && subinout && orggraph && subgraph);
992  assert(*subgraph);
993  assert(!graph_pc_isPcMw(orggraph) && "not yet supported");
994  assert(graph_valid(scip, orggraph));
995 
996  subg = *subgraph;
997  SCIP_CALL( reinsertSubgraph(scip, subg, subinout, orggraph) );
998 
999  graph_path_exit(scip, subg);
1000 
1001  if( subg->orgtail != NULL )
1002  {
1003  assert(subinout->useNewHistory);
1004  assert(subg->orghead != NULL);
1005 
1006  SCIPfreeMemoryArray(scip, &(subg->orghead));
1007  SCIPfreeMemoryArray(scip, &(subg->orgtail));
1008  }
1009 
1010  assert(!subg->fixedcomponents);
1011  /* NOTE: fixed components are not deleted */
1012  graph_free(scip, subgraph, FALSE);
1013 
1014  assert(graph_valid(scip, orggraph));
1015 
1016  return SCIP_OKAY;
1017 }
1018 
1019 
1020 /** frees extracted subgraph.
1021  * NOTE: fixed history components are not deleted */
1023  SCIP* scip, /**< SCIP data structure */
1024  GRAPH** subgraph /**< graph to be freed */
1025  )
1026 {
1027  assert(scip && subgraph);
1028 
1029  graph_path_exit(scip, *subgraph);
1030  graph_free(scip, subgraph, FALSE);
1031 }
#define STP_Vectype(type)
Definition: stpvector.h:44
static void extractSubgraphAddNodes(const GRAPH *orggraph, SUBINOUT *subinout, GRAPH *subgraph)
Definition: graph_sub.c:135
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
int graph_edge_nPseudoAncestors(const GRAPH *, int)
void graph_knot_chg(GRAPH *, int, int)
Definition: graph_node.c:86
#define StpVecGetSize(vec)
Definition: stpvector.h:139
#define StpVecClear(vec)
Definition: stpvector.h:134
int *RESTRICT head
Definition: graphdefs.h:224
void graph_edge_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_edge.c:368
int *RESTRICT orgtail
Definition: graphdefs.h:225
int source
Definition: graphdefs.h:195
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip_mem.h:72
#define Is_term(a)
Definition: graphdefs.h:102
SCIP_Bool graph_subinoutUsesNewHistory(const SUBINOUT *subinout)
Definition: graph_sub.c:848
static void reinsertSubgraphAdaptSubToOrgMap(const GRAPH *subgraph, const GRAPH *orggraph, SUBINOUT *subinout)
Definition: graph_sub.c:274
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
SCIP_Bool graph_valid(SCIP *, const GRAPH *)
Definition: graph_base.c:1480
int terms
Definition: graphdefs.h:192
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
int graph_contractTrace(int, const GRAPH *)
void graph_free(SCIP *, GRAPH **, SCIP_Bool)
Definition: graph_base.c:796
SCIP_RETCODE graph_path_init(SCIP *, GRAPH *)
Definition: graph_path.c:480
SCIP_RETCODE graph_initPseudoAncestorsSized(SCIP *, int, GRAPH *)
#define EAT_FREE
Definition: graphdefs.h:57
#define FALSE
Definition: def.h:87
void graph_subinoutActivateNewHistory(SUBINOUT *subinout)
Definition: graph_sub.c:788
static void extractSubgraphGetSizeAndMap(const GRAPH *orggraph, SUBINOUT *subinout)
Definition: graph_sub.c:79
#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
#define StpVecPopBack(vec)
Definition: stpvector.h:178
static SCIP_RETCODE reinsertSubgraphTransferEdges(SCIP *scip, GRAPH *subgraph, SUBINOUT *subinsertion, GRAPH *orggraph)
Definition: graph_sub.c:548
SCIP_RETCODE graph_knot_contract(SCIP *, GRAPH *, int *, int, int)
Definition: graph_node.c:264
#define EAT_LAST
Definition: graphdefs.h:58
#define STP_SPG
Definition: graphdefs.h:42
#define SCIPdebugMessage
Definition: pub_message.h:87
void graph_subinoutClean(SCIP *scip, SUBINOUT *subinout)
Definition: graph_sub.c:882
static SCIP_RETCODE reinsertSubgraphTransferTerminals(const GRAPH *subgraph, SUBINOUT *subinout, GRAPH *orggraph)
Definition: graph_sub.c:591
int *RESTRICT orghead
Definition: graphdefs.h:226
header only, simple implementation of an STL like vector
SCIP_RETCODE graph_subgraphReinsert(SCIP *scip, SUBINOUT *subinout, GRAPH *orggraph, GRAPH **subgraph)
Definition: graph_sub.c:983
int target_edge
Definition: graph_sub.c:47
#define STP_TERM_NONE
Definition: graphdefs.h:62
SCIP_RETCODE graph_initAncestors(SCIP *, GRAPH *)
int *RESTRICT mark
Definition: graphdefs.h:198
SCIP_RETCODE graph_subgraphCompleteNewHistory(SCIP *scip, const int *edgemap_subToOrg, GRAPH *orggraph, GRAPH *subgraph)
Definition: graph_sub.c:920
const int * graph_subinoutGetOrgToSubNodeMap(const SUBINOUT *subinout)
Definition: graph_sub.c:825
int *RESTRICT oeat
Definition: graphdefs.h:231
SCIP_Bool redirectEdge
Definition: graph_sub.c:48
SCIP_Bool withInexactReductions
Definition: graphdefs.h:266
SCIP_RETCODE SCIPintListNodeAppendCopy(SCIP *scip, IDX **node1, IDX *node2, SCIP_Bool *conflict)
Definition: misc_stp.c:197
int stp_type
Definition: graphdefs.h:264
int graph_getNfixpseudonodes(const GRAPH *)
IDX ** ancestors
Definition: graphdefs.h:234
int orgedges
Definition: graphdefs.h:220
FIXED * fixedcomponents
Definition: graphdefs.h:237
void graph_free_fixed(SCIP *, GRAPH *)
PSEUDOANS * pseudoancestors
Definition: graphdefs.h:236
const int * graph_subinoutGetSubToOrgEdgeMap(const SUBINOUT *subinout)
Definition: graph_sub.c:812
SCIP_RETCODE graph_pseudoAncestors_appendCopyArrayToEdge(SCIP *, int, const int *, int, GRAPH *, SCIP_Bool *)
void graph_free_fixedEdgesOnly(SCIP *, GRAPH *)
void graph_edge_add(SCIP *, GRAPH *, int, int, double, double)
int *RESTRICT grad
Definition: graphdefs.h:201
void graph_knot_add(GRAPH *, int)
Definition: graph_node.c:64
internal miscellaneous methods
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_Bool graph_knot_hasContractTrace(int, const GRAPH *)
SCIP_RETCODE graph_copyFixed(SCIP *, GRAPH *, SCIP_Bool, GRAPH *)
#define EQ(a, b)
Definition: portab.h:79
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
void graph_fixed_resetMoved(GRAPH *)
SCIP_RETCODE graph_initContractTracing(SCIP *, GRAPH *)
static SCIP_RETCODE extractSubgraphBuild(SCIP *scip, GRAPH *orggraph, SUBINOUT *subinout, GRAPH **subgraph)
Definition: graph_sub.c:481
#define SCIP_Bool
Definition: def.h:84
SCIP_Bool graph_edge_isDeleted(const GRAPH *, int)
Definition: graph_stats.c:121
void graph_subgraphFree(SCIP *scip, GRAPH **subgraph)
Definition: graph_sub.c:1022
SCIP_RETCODE graph_subinoutActivateEdgeMap(const GRAPH *orggraph, SUBINOUT *subinout)
Definition: graph_sub.c:769
int *RESTRICT tail
Definition: graphdefs.h:223
static SCIP_RETCODE extractSubgraphAddEdgesWithHistory(SCIP *scip, GRAPH *orggraph, SUBINOUT *subinout, GRAPH *subgraph)
Definition: graph_sub.c:327
#define flipedge(edge)
Definition: graphdefs.h:84
#define MAX(x, y)
Definition: tclique_def.h:83
#define STP_TERM
Definition: graphdefs.h:61
const int * graph_edge_getPseudoAncestors(const GRAPH *, int)
SCIP_RETCODE graph_subinoutInit(SCIP *scip, const GRAPH *orggraph, SUBINOUT **subinout)
Definition: graph_sub.c:733
int *RESTRICT term
Definition: graphdefs.h:196
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
static SCIP_RETCODE extractSubgraphInitHistory(SCIP *scip, GRAPH *orggraph, SCIP_Bool moveFixedEdges, GRAPH *subgraph)
Definition: graph_sub.c:175
static void reinsertSubgraphTransferFixedHistory(SCIP *scip, GRAPH *subgraph, GRAPH *orggraph)
Definition: graph_sub.c:516
const int * graph_subinoutGetContractionRecord(const SUBINOUT *subinout)
Definition: graph_sub.c:837
void graph_path_exit(SCIP *, GRAPH *)
Definition: graph_path.c:515
int target_tail
Definition: graph_sub.c:45
Portable definitions.
SCIP_Bool graph_typeIsUndirected(const GRAPH *)
Definition: graph_stats.c:69
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
SCIP_RETCODE graph_subgraphExtract(SCIP *scip, GRAPH *orggraph, SUBINOUT *subinout, GRAPH **subgraph)
Definition: graph_sub.c:712
SCIP_Real * cost
Definition: graphdefs.h:221
SCIP_Bool graph_edge_isInRange(const GRAPH *, int)
Definition: graph_stats.c:110
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
int * contracttrace
Definition: graphdefs.h:238
void graph_subinoutFree(SCIP *scip, SUBINOUT **subinout)
Definition: graph_sub.c:859
int esize
Definition: graphdefs.h:218
void graph_addPseudoAncestors(int, GRAPH *)
#define StpVecFree(scip, vec)
Definition: stpvector.h:149
const int * graph_subinoutGetSubToOrgNodeMap(const SUBINOUT *subinout)
Definition: graph_sub.c:799
int *RESTRICT outbeg
Definition: graphdefs.h:204
static SCIP_RETCODE reinsertSubgraph(SCIP *scip, GRAPH *subgraph, SUBINOUT *subinout, GRAPH *orggraph)
Definition: graph_sub.c:675
int edges
Definition: graphdefs.h:219
int graph_getNpseudoAncestors(const GRAPH *)
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
SCIP_Bool graph_knot_isInRange(const GRAPH *, int)
Definition: graph_node.c:52
int ksize
Definition: graphdefs.h:189
#define nnodes
Definition: gastrans.c:65
#define StpVecPushBack(scip, vec, value)
Definition: stpvector.h:163
SCIP_RETCODE graph_init(SCIP *, GRAPH **, int, int, int)
Definition: graph_base.c:607
int source_edge
Definition: graph_sub.c:44
int graph_knot_getContractionRecordAncestor(int node, const SUBINOUT *subinout)
Definition: graph_sub.c:895
SCIP_Bool graph_typeIsSpgLike(const GRAPH *)
Definition: graph_stats.c:57
static void borderNodesCollect(SCIP *scip, const GRAPH *orggraph, const GRAPH *subgraph, SUBINOUT *subinout)
Definition: graph_sub.c:383
static SCIP_RETCODE reinsertSubgraphDeleteOldEdges(SCIP *scip, const GRAPH *subgraph, SUBINOUT *subinout, GRAPH *orggraph)
Definition: graph_sub.c:634
static SCIP_RETCODE borderNodesContract(SCIP *scip, const GRAPH *subgraph, SUBINOUT *subinout, GRAPH *orggraph)
Definition: graph_sub.c:423
#define Edge_even(a)
Definition: graphdefs.h:107
int target_head
Definition: graph_sub.c:46
static SCIP_RETCODE extractSubgraphAddEdge(SCIP *scip, SCIP_Bool useNewHistory, SCIP_Bool moveEdges, const EDGETRANS *edgetrans, GRAPH *source_graph, GRAPH *target_graph)
Definition: graph_sub.c:201
IDX * graph_edge_getAncestors(const GRAPH *, int)
struct edge_transfer EDGETRANS