# SCIP

Solving Constraint Integer Programs

graph_history.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_history.c
17  * @brief includes graph ancestor methods for Steiner problems
18  * @author Daniel Rehfeldt
19  *
20  * Graph ancestor methods for Steiner problems. Usually used to reconstruct a graph after reductions
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 #include <assert.h>
29 #include "graph.h"
30 #include "portab.h"
31
32
33 /** fixed graph components, typedef FIXED */
35 {
36  IDX* fixedges; /**< fixed edges */
37  int* fixpseudonodes; /**< fixed psuedo eliminated nodes */
38  int nfixnodes; /**< number of fixed nodes */
39  SCIP_Bool movedFrom; /**< ancestor information moved away? */
40 };
41
42 /** blocked pseudo ancestors */
44 {
45  int** blocks; /**< blocks of ancestors (of size nblocks) */
46  int* sizes; /**< current number of ancestors (of size nblocks) */
47  int* capacities; /**< current capacities of ancestors (of size nblocks) */
48  int nblocks; /**< number of ancestor blocks */
49 } BLOCKANS;
50
51 /** node ancestors resulting from pseudo-elimination, typedef PSEUDOANS */
53 {
54  BLOCKANS* ans_halfedges; /**< (half) edge ancestors */
55  BLOCKANS* ans_nodes; /**< (pc/mw) node ancestors */
56  int nnodes; /**< number of nodes */
57  int halfnedges; /**< half number of edges */
58  int nAllPseudoancestors;/**< number of pseudo-ancestors */
59 };
60
61
62 /** get next power of 2 number; assumes number >= 1 and number < UINT_MAX */
63 static inline
65 {
66  uint32_t n = (uint32_t) number;
67  assert(number >= 1);
68
69  n--;
70  n |= n >> 1;
71  n |= n >> 2;
72  n |= n >> 4;
73  n |= n >> 8;
74  n |= n >> 16;
75  n++;
76  SCIPdebugMessage("pow2 %d from number %d \n", n, number);
77
78  assert(n < INT_MAX );
79  assert((int) n >= number && (int) n <= 2 * number);
80  assert(number >= 1);
81
82  return (int) n;
83 }
84
85
86 /** mark ancestors of given edge */
87 static
89  const GRAPH* graph, /**< graph data structure */
90  int edge, /**< edge to use */
91  int* ancestormark /**< ancestor mark array */
92  )
93 {
94  assert(edge >= 0);
95
96  for( IDX* curr = graph->ancestors[edge]; curr != NULL; curr = curr->parent )
97  {
98  const unsigned idx = ((unsigned) curr->index) / 2;
99
100  assert(curr->index >= 0 && idx < (unsigned) (MAX(graph->edges, graph->orgedges) / 2));
101
102  if( ancestormark[idx] )
103  return TRUE;
104
105  ancestormark[idx] = 1;
106  }
107
108  return FALSE;
109 }
110
111
112 /** unmark ancestors of given edge */
113 static
115  const GRAPH* graph, /**< graph data structure */
116  int edge, /**< edge to use */
117  int* ancestormark /**< ancestor mark array */
118  )
119 {
120  assert(edge >= 0);
121
122  for( IDX* curr = graph->ancestors[edge]; curr != NULL; curr = curr->parent )
123  {
124  assert(curr->index >= 0 && curr->index / 2 < (MAX(graph->edges, graph->orgedges) / 2));
125  ancestormark[((unsigned) curr->index) / 2] = 0;
126  }
127 }
128
129
130 /** initialize */
131 static
133  int nblocks, /**< number of ancestor blocks */
134  BLOCKANS** blockedans /**< blocked pseudo-ancestors */
135 )
136 {
137  int** blocks;
138  int* sizes;
139  int* capacities;
140
141  assert(nblocks > 0);
142
143  SCIP_CALL( SCIPallocMemory(scip, blockedans) );
144
145  (*blockedans)->nblocks = nblocks;
146
147  SCIP_CALL( SCIPallocMemoryArray(scip, &(blocks), nblocks) );
148  SCIP_CALL( SCIPallocMemoryArray(scip, &(sizes), nblocks) );
149  SCIP_CALL( SCIPallocMemoryArray(scip, &(capacities), nblocks) );
150
151  for( int k = 0; k < nblocks; k++ )
152  {
153  blocks[k] = NULL;
154  sizes[k] = 0;
155  capacities[k] = 0;
156  }
157
158  (*blockedans)->blocks = blocks;
159  (*blockedans)->sizes = sizes;
160  (*blockedans)->capacities = capacities;
161
162  return SCIP_OKAY;
163 }
164
165
166 /** free */
167 static inline
169  SCIP* scip, /**< SCIP data structure */
170  int block_id, /**< id for which to free pseudo ancestors */
171  BLOCKANS* blockedans /**< blocked pseudo-ancestors */
172 )
173 {
174  const int capacity = blockedans->capacities[block_id];
175
176  assert(scip && blockedans && blockedans->sizes && blockedans->capacities);
177  assert(block_id >= 0 && block_id < blockedans->nblocks);
178  assert(capacity >= 0);
179
180  if( capacity > 0 )
181  {
182  assert(blockedans->blocks[block_id]);
183  SCIPfreeBlockMemoryArray(scip, &(blockedans->blocks[block_id]), capacity);
184
185  blockedans->sizes[block_id] = 0;
186  blockedans->capacities[block_id] = 0;
187  }
188
189  assert(blockedans->sizes[block_id] == 0);
190  assert(blockedans->capacities[block_id] == 0);
191  assert(blockedans->blocks[block_id] == NULL);
192 }
193
194
195 /** free */
196 static
198  SCIP* scip, /**< SCIP data structure */
199  BLOCKANS** blockedans /**< blocked pseudo-ancestors */
200 )
201 {
202  BLOCKANS* const ancestors = (*blockedans);
203  int* const * blocks = ancestors->blocks;
204  const int* sizes = ancestors->sizes;
205  const int* capacities = ancestors->capacities;
206  const int nblocks = ancestors->nblocks;
207
208  assert(blockedans && ancestors);
209  assert(nblocks >= 1);
210  assert(capacities && sizes && blocks);
211
212  for( int e = nblocks - 1; e >= 0; --e )
213  blockedAncestors_freeBlock(scip, e, ancestors);
214
215  SCIPfreeMemoryArray(scip, &sizes);
216  SCIPfreeMemoryArray(scip, &capacities);
217  SCIPfreeMemoryArray(scip, &blocks);
218
219  SCIPfreeMemoryArray(scip, blockedans);
220 }
221
222
223 /** hash ancestors of given entry */
224 static inline
226  const BLOCKANS* blockedans, /**< blocked pseudo-ancestors */
227  int block_id, /**< entry for which to reallocate */
228  int* hasharr /**< hash array for pseudo ancestors */
229 )
230 {
231  const int nancestors = blockedans->sizes[block_id];
232  const int* const ancestorsblock = blockedans->blocks[block_id];
233
234  assert(blockedans && hasharr);
235  assert(block_id >= 0 && block_id < blockedans->nblocks);
236  assert(nancestors >= 0);
237
238  for( int k = 0; k < nancestors; k++ )
239  {
240  const int a = ancestorsblock[k];
241  assert(a >= 0 && hasharr[a] == 0);
242
243  hasharr[a] = 1;
244  }
245 }
246
247
248 /** unhash nAncestorsToClean many ancestors */
249 static inline
251  const BLOCKANS* blockedans, /**< blocked pseudo-ancestors */
252  int block_id, /**< entry for which to reallocate */
253  int nAncestorsToClean, /**< number of (first) ancestors to use for clean, or -1 to clean all */
254  int* hasharr /**< hash array for pseudo ancestors */
255 )
256 {
257  const int* const ancestorsblock = blockedans->blocks[block_id];
258  const int n = (nAncestorsToClean >= 0) ? nAncestorsToClean : blockedans->sizes[block_id];
259
260  assert(blockedans && hasharr);
261  assert(block_id >= 0 && block_id < blockedans->nblocks);
262  assert(nAncestorsToClean >= 0 || nAncestorsToClean == -1);
263
264  for( int k = 0; k < n; k++ )
265  {
266  const int a = ancestorsblock[k];
267  assert(a >= 0);
268  assert(hasharr[a] == 1);
269
270  hasharr[a] = 0;
271  }
272 }
273
274
275 /** hash ancestors of given entry with possible conflicts */
276 static inline
278  const BLOCKANS* blockedans, /**< blocked pseudo-ancestors */
279  int block_id, /**< entry for which to reallocate */
280  SCIP_Bool revertIfConflict, /**< break on conflict? */
281  SCIP_Bool* conflict, /**< conflict? */
282  int* hasharr /**< hash array for pseudo ancestors */
283 )
284 {
285  int k;
286  const int nancestors = blockedans->sizes[block_id];
287  const int* const ancestorsblock = blockedans->blocks[block_id];
288
289  assert(blockedans && hasharr);
290  assert(block_id >= 0 && block_id < blockedans->nblocks);
291  assert(nancestors >= 0);
292
293  *conflict = FALSE;
294
295  for( k = 0; k < nancestors; k++ )
296  {
297  const int a = ancestorsblock[k];
298  assert(a >= 0 );
299  assert(hasharr[a] == 0 || hasharr[a] == 1);
300
301  if( hasharr[a] == 1 )
302  {
303  *conflict = TRUE;
304
305  if( revertIfConflict )
306  break;
307  }
308
309  hasharr[a] = 1;
310  }
311
312  /* do we need to clean up? */
313  if( *conflict && revertIfConflict )
314  {
315  assert(k < nancestors);
316
317  for( int k2 = 0; k2 < k; k2++ )
318  {
319  const int a = ancestorsblock[k2];
320  assert(a >= 0 );
321  assert(hasharr[a] == 1);
322
323  hasharr[a] = 0;
324  }
325  }
326 }
327
328
329 /** unhash ancestors of given entry with possible conflicts */
330 static inline
332  const BLOCKANS* blockedans, /**< blocked pseudo-ancestors */
333  int block_id, /**< entry for which to reallocate */
334  int* hasharr /**< hash array for pseudo ancestors */
335 )
336 {
337  const int nancestors = blockedans->sizes[block_id];
338  const int* const ancestorsblock = blockedans->blocks[block_id];
339
340  assert(blockedans && hasharr);
341  assert(block_id >= 0 && block_id < blockedans->nblocks);
342  assert(nancestors >= 0);
343
344  for( int k = 0; k < nancestors; k++ )
345  {
346  const int a = ancestorsblock[k];
347  assert(a >= 0 );
348  assert(hasharr[a] == 0 || hasharr[a] == 1);
349
350  hasharr[a] = 0;
351  }
352 }
353
354
355 /** ancestor already hashed? */
356 static inline
358  const BLOCKANS* blockedans, /**< blocked pseudo-ancestors */
359  int ancestor, /**< ancestor to check */
360  const int* hasharr /**< hash array for pseudo ancestors*/
361 )
362 {
363  assert(blockedans && hasharr);
364  assert(hasharr[ancestor] == 0 || hasharr[ancestor] == 1);
365
366  return (hasharr[ancestor] == 1);
367 }
368
369
370 /** any ancestors of given entry are already hashed? */
371 static inline
373  const BLOCKANS* blockedans, /**< blocked pseudo-ancestors */
374  int block_id, /**< entry for which to check for conflicts */
375  const int* hasharr /**< hash array for pseudo ancestors */
376 )
377 {
378  const int nancestors = blockedans->sizes[block_id];
379  const int* const ancestorsblock = blockedans->blocks[block_id];
380
381  assert(blockedans && hasharr);
382  assert(block_id >= 0 && block_id < blockedans->nblocks);
383  assert(nancestors >= 0);
384
385  for( int k = 0; k < nancestors; k++ )
386  {
387  const int a = ancestorsblock[k];
388  assert(a >= 0 );
389  assert(hasharr[a] == 0 || hasharr[a] == 1);
390
391  if( 1 == hasharr[a] )
392  return TRUE;
393  }
394
395  return FALSE;
396 }
397
398
399 /** reallocate ancestor array of given entry */
400 static inline
402  SCIP* scip, /**< SCIP data structure */
403  int block_id, /**< entry for which to reallocate */
404  int capacity_new, /**< the new capacity */
405  BLOCKANS* blockedans /**< blocked pseudo-ancestors */
406 )
407 {
408  const int capacity_old = blockedans->capacities[block_id];
409
410  assert(scip && blockedans);
411  assert(block_id >= 0 && block_id < blockedans->nblocks);
412  assert(capacity_old >= 0 && capacity_new > capacity_old);
413  assert(capacity_new >= 1);
414
415  if( capacity_old == 0 )
416  {
417  assert(blockedans->blocks[block_id] == NULL);
418  assert(blockedans->sizes[block_id] == 0);
419
420  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(blockedans->blocks[block_id]), capacity_new) );
421  }
422  else
423  {
424  assert(blockedans->blocks[block_id] != NULL);
425  assert(capacity_old >= 1);
426
427  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(blockedans->blocks[block_id]), capacity_old, capacity_new) );
428  }
429
430  blockedans->capacities[block_id] = capacity_new;
431
432  return SCIP_OKAY;
433 }
434
435
436 /** pseudo ancestors of given block without conflicts? */
437 static inline
439  int block_id, /**< entry for which to reallocate */
440  const BLOCKANS* blockedans, /**< blocked pseudo-ancestors */
441  int* hasharr /**< clean hash array for pseudo ancestors */
442 )
443 {
444  SCIP_Bool conflict;
445
446  assert(blockedans);
447  assert(block_id >= 0 && block_id < blockedans->nblocks);
448
449  blockedAncestors_hashDirty(blockedans, block_id, FALSE, &conflict, hasharr);
450  blockedAncestors_unhashDirty(blockedans, block_id, hasharr);
451
452  return !conflict;
453 }
454
455
456 /** appends copy of pseudo ancestors of source to target */
457 static
459  SCIP* scip, /**< SCIP data structure */
460  int block_target, /**< target block */
461  const int* ancestors_source, /**< ancestors to append */
462  int size_source, /**< number of ancestors to append */
463  SCIP_Bool breakOnConflict, /**< break on conflict */
464  int hasharr_size, /**< size for hash array */
465  BLOCKANS* blockedans_target, /**< blocked pseudo-ancestors */
466  SCIP_Bool* conflict /**< conflict? */
467 )
468 {
469  int* ancestors_target;
470  int* hasharr;
471  int position_target;
472  const int size_target_org = blockedans_target->sizes[block_target];
473  const int size_targetPlusSource = size_target_org + size_source;
474
475  assert(size_source > 0);
476  assert(ancestors_source && blockedans_target);
477
478  SCIP_CALL( SCIPallocCleanBufferArray(scip, &hasharr, hasharr_size) );
479
480  /* need to realloc target ancestor array? */
481  if( size_targetPlusSource > blockedans_target->capacities[block_target] )
482  {
483  const int capacity_up = getNextPow2(size_targetPlusSource);
484  SCIP_CALL( blockedAncestors_realloc(scip, block_target, capacity_up, blockedans_target) );
485  }
486
487  ancestors_target = blockedans_target->blocks[block_target];
488
489  /* mark ancestors of target */
490  blockedAncestors_hash(blockedans_target, block_target, hasharr);
491
492  position_target = size_target_org;
493
494  /* add source to target */
495  for( int e = 0; e < size_source; e++ )
496  {
497  const int ancestor = ancestors_source[e];
498  assert(ancestor < hasharr_size);
499
500  if( blockedAncestors_hashIsHit(blockedans_target, ancestor, hasharr) )
501  {
502  *conflict = TRUE;
503
504  if( breakOnConflict )
505  break;
506
507  continue;
508  }
509
510  assert(position_target < blockedans_target->capacities[block_target]);
511
512  ancestors_target[position_target++] = ancestor;
513  }
514
515  assert(position_target <= size_targetPlusSource);
516  assert(position_target >= blockedans_target->sizes[block_target]);
517
518  blockedans_target->sizes[block_target] = position_target;
519
520  /* unmark ancestors of target */
521  blockedAncestors_unhashPartial(blockedans_target, block_target, size_target_org, hasharr);
522
523  SCIPfreeCleanBufferArray(scip, &hasharr);
524
525  return SCIP_OKAY;
526 }
527
528
529 /** appends copy of pseudo ancestors of source to target */
530 static
532  SCIP* scip, /**< SCIP data structure */
533  int block_target, /**< target block */
534  const BLOCKANS* blockedans_source, /**< blocked pseudo-ancestors */
535  int block_source, /**< source block */
536  SCIP_Bool breakOnConflict, /**< break on conflict */
537  int hasharr_size, /**< size of hash array */
538  BLOCKANS* blockedans_target, /**< blocked pseudo-ancestors */
539  SCIP_Bool* conflict /**< conflict? */
540 )
541 {
542  const int size_source = blockedans_source->sizes[block_source];
543
544  assert(scip && blockedans_source && blockedans_target && conflict);
545  assert(hasharr_size >= 1 && size_source >= 0);
546  assert(block_target >= 0 && block_target < blockedans_target->nblocks);
547  assert(block_source >= 0 && block_source < blockedans_source->nblocks);
548
549  *conflict = FALSE;
550
551  /* anything to append? */
552  if( size_source > 0 )
553  {
554  const int* const ancestors_source = blockedans_source->blocks[block_source];
555
556  SCIP_CALL( blockedAncestors_appendArray(scip, block_target, ancestors_source, size_source, breakOnConflict, hasharr_size, blockedans_target, conflict) );
557  }
558
559  return SCIP_OKAY;
560 }
561
562
563 /** adds pseudo ancestor to ancestor list of given block */
564 static
566  SCIP* scip, /**< SCIP data structure */
567  int block_target, /**< block for which to add pseudo ancestor */
568  int ancestor, /**< (index of) pseudo ancestor */
569  int hasharr_size, /**< size of hash array */
570  BLOCKANS* blockedans /**< blocked pseudo-ancestors */
571 )
572 {
573  int* const sizes = blockedans->sizes;
574  int* const capacities = blockedans->capacities;
575
576  assert(scip && blockedans);
577  assert(block_target >= 0 && block_target < blockedans->nblocks);
578  assert(ancestor < hasharr_size);
579
580  /* need to reallocate? */
581  if( sizes[block_target] == capacities[block_target] )
582  {
583  const int capacity_up = getNextPow2(sizes[block_target] + 1);
584  SCIP_CALL( blockedAncestors_realloc(scip, block_target, capacity_up, blockedans) );
585  }
586
587  assert(sizes[block_target] < capacities[block_target]);
588
589  blockedans->blocks[block_target][sizes[block_target]++] = ancestor;
590
591 #ifndef NDEBUG
592  {
593  int* hasharr;
594  assert(hasharr_size >= 1);
595  SCIP_CALL_ABORT( SCIPallocCleanBufferArray(scip, &hasharr, hasharr_size) );
596  assert(blockedAncestors_blockIsValid(block_target, blockedans, hasharr));
597  SCIPfreeCleanBufferArray(scip, &hasharr);
598  }
599 #endif
600
601  return SCIP_OKAY;
602 }
603
604
605 /** valid pseudo-ancestors (no conflicts)? */
606 static
608  SCIP* scip, /**< SCIP data structure */
609  int hasharr_size, /**< size of hash array */
610  const BLOCKANS* blockedans /**< blocked pseudo-ancestors */
611 )
612 {
613  int* hasharr;
614  SCIP_Bool isValid = TRUE;
615
616  assert(scip && blockedans);
617  assert(hasharr_size >= 1);
618
619  /* check whether sizes/capacities are correct */
620  for( int e = 0; e < blockedans->nblocks && isValid; e++ )
621  {
622  if( blockedans->sizes[e] > blockedans->capacities[e] )
623  isValid = FALSE;
624
625  if( blockedans->sizes[e] > 0 && blockedans->blocks[e] == NULL )
626  isValid = FALSE;
627
628  if( blockedans->capacities[e] > 0 && blockedans->blocks[e] == NULL )
629  isValid = FALSE;
630  }
631
632  SCIP_CALL_ABORT( SCIPallocCleanBufferArray(scip, &hasharr, hasharr_size) );
633
634  /* check whether there are conflict within the ancestor blocks */
635  for( int e = 0; e < blockedans->nblocks && isValid; e++ )
636  {
637  if( blockedans->blocks[e] != NULL && !blockedAncestors_blockIsValid(e, blockedans, hasharr) )
638  isValid = FALSE;
639  }
640
641  SCIPfreeCleanBufferArray(scip, &hasharr);
642
643  return isValid;
644 }
645
646
647 /** checks */
648 static
650  SCIP* scip, /**< SCIP data structure */
651  const GRAPH* g /**< the graph */
652  )
653 {
654  int *hasharr;
655  const int *fixednodes = graph_getFixpseudonodes(scip, g);
657  const int nfixednodes = graph_getNfixpseudonodes(g);
658  SCIP_Bool isValid = TRUE;
659
660  assert(arrsize >= nfixednodes);
661  SCIP_CALL_ABORT( SCIPallocClearMemoryArray(scip, &hasharr, arrsize) );
662
663  for( int k = 0; k < nfixednodes; k++ )
664  {
665  const int node = fixednodes[k];
666  assert(node >= 0 && node < arrsize);
667
668  if( hasharr[node] != 0 )
669  {
670  SCIPerrorMessage("fail for ancestor node %d (hashed twice) \n", node);
671  isValid = FALSE;
672  break;
673  }
674
675  hasharr[node] = 1;
676  }
677
678  SCIPfreeMemoryArray(scip, &hasharr);
679
680  return isValid;
681 }
682
683 /** initializes singleton edge ancestors */
685  SCIP* scip, /**< SCIP data structure */
686  const GRAPH* g, /**< the graph */
687  int edge, /**< edge to initialize from */
688  SINGLETONANS* singletonans /**< singleton edge ancestors */
689 )
690 {
691  SCIP_Bool conflict = FALSE;
692
693  assert(scip && g && singletonans);
694  assert(edge >= 0 && edge < g->edges);
695
696  singletonans->npseudoancestors = graph_edge_nPseudoAncestors(g, edge);
697  singletonans->edge = edge;
698  singletonans->ancestors = NULL;
699  singletonans->revancestors = NULL;
700
701  if( singletonans->npseudoancestors > 0 )
702  {
703  const int* const pseudoancestors = graph_edge_getPseudoAncestors(g, edge);
704  SCIP_CALL( SCIPallocMemoryArray(scip, &(singletonans->pseudoancestors), singletonans->npseudoancestors) );
705  BMScopyMemoryArray(singletonans->pseudoancestors, pseudoancestors, singletonans->npseudoancestors);
706  }
707  else
708  {
709  assert(singletonans->npseudoancestors == 0);
710  singletonans->pseudoancestors = NULL;
711  }
712
713  if( !g->ancestors[edge] || !g->ancestors[flipedge(edge)] )
714  {
715  assert(graph_typeIsUndirected(g));
716  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(singletonans->ancestors), graph_edge_getAncestors(g, edge), &conflict) );
717  assert(!conflict);
718  }
719  else
720  {
721  assert(!graph_typeIsUndirected(g));
722  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(singletonans->ancestors), g->ancestors[edge], &conflict) );
723  assert(!conflict);
724
725  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(singletonans->revancestors), g->ancestors[flipedge(edge)], &conflict) );
726  assert(!conflict);
727  }
728
729  return SCIP_OKAY;
730 }
731
732
733 /** initializes singleton edge ancestors */
735  SCIP* scip, /**< SCIP data structure */
736  SINGLETONANS* singletonans /**< singleton edge ancestors */
737 )
738 {
739  assert(scip && singletonans);
740  assert(singletonans->ancestors);
741  assert(singletonans->pseudoancestors || singletonans->npseudoancestors == 0);
742  assert(singletonans->npseudoancestors >= 0);
743
744  if( singletonans->npseudoancestors > 0 )
745  SCIPfreeMemoryArray(scip, &(singletonans->pseudoancestors));
746
747  SCIPintListNodeFree(scip, &(singletonans->ancestors));
748  SCIPintListNodeFree(scip, &(singletonans->revancestors));
749 }
750
751
752 /** valid ancestors (no conflicts)? */
754  SCIP* scip, /**< SCIP data structure */
755  const GRAPH* g /**< the graph */
756 )
757 {
758  int* edgemark;
759  const int nedges = g->edges;
760  const int nancestors = MAX(g->edges, g->orgedges) / 2;
761  const SCIP_Bool pcmw = graph_pc_isPcMw(g);
762  SCIP_Bool isValid = TRUE;
763
764  assert(scip != NULL && g != NULL);
765  assert(g->ancestors != NULL);
766
767  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &edgemark, nancestors) );
768
769  for( int e = 0; e < nancestors; e++ )
770  edgemark[e] = FALSE;
771
772  for( int e = 0; e < nedges; e += 2 )
773  {
774  SCIP_Bool conflict;
775
776  if( g->oeat[e] == EAT_FREE )
777  continue;
778
779  if( pcmw && !SCIPisEQ(scip, g->cost[e], g->cost[e + 1]) )
780  continue;
781
782  if( !g->ancestors[e] )
783  {
784  isValid = FALSE;
785  break;
786  }
787
788  if( graph_typeIsUndirected(g) && g->ancestors[e + 1] )
789  {
790  isValid = FALSE;
791  break;
792  }
793
794  conflict = ancestorsMarkConflict(g, e, edgemark);
795  ancestorsUnmarkConflict(g, e, edgemark);
796
797  if( conflict )
798  {
799  isValid = FALSE;
800  break;
801  }
802
803  conflict = ancestorsMarkConflict(g, e + 1, edgemark);
804  ancestorsUnmarkConflict(g, e + 1, edgemark);
805
806  if( conflict )
807  {
808  isValid = FALSE;
809  break;
810  }
811
812  }
813
814  SCIPfreeBufferArray(scip, &edgemark);
815
816  if( isValid && !g->withInexactReductions )
817  isValid = fixedPseudoAncestorsAreValid(scip, g);
818
819  return isValid;
820 }
821
822
823 /** hash ancestors of given edge */
825  const PSEUDOANS* pseudoancestors, /**< pseudo-ancestors */
826  int edge, /**< edge for which to hash */
827  int* hasharr /**< hash array */
828 )
829 {
830  const int halfedge = edge / 2;
831
832  assert(pseudoancestors && hasharr);
833  assert(halfedge >= 0 && halfedge < pseudoancestors->halfnedges);
834
835  blockedAncestors_hash(pseudoancestors->ans_halfedges, halfedge, hasharr);
836 }
837
838
839 /** hash ancestors of given node */
841  const PSEUDOANS* pseudoancestors, /**< pseudo-ancestors */
842  int node, /**< node for which to hash */
843  int* hasharr /**< hash array */
844 )
845 {
846  assert(pseudoancestors && hasharr);
847  assert(node >= 0 && node < pseudoancestors->nnodes);
848
849  blockedAncestors_hash(pseudoancestors->ans_nodes, node, hasharr);
850 }
851
852
853 /** unhash ancestors of given edge */
855  const PSEUDOANS* pseudoancestors, /**< pseudo-ancestors */
856  int edge, /**< edge for which to unhash */
857  int* hasharr /**< hash array */
858 )
859 {
860  const int halfedge = edge / 2;
861
862  assert(pseudoancestors && hasharr);
863  assert(halfedge >= 0 && halfedge < pseudoancestors->halfnedges);
864
865  blockedAncestors_unhashPartial(pseudoancestors->ans_halfedges, halfedge, -1, hasharr);
866 }
867
868
869 /** hash ancestors of given node */
871  const PSEUDOANS* pseudoancestors, /**< pseudo-ancestors */
872  int node, /**< node for which to unhash */
873  int* hasharr /**< hash array */
874 )
875 {
876  assert(pseudoancestors && hasharr);
877  assert(node >= 0 && node < pseudoancestors->nnodes);
878
879  blockedAncestors_unhashPartial(pseudoancestors->ans_nodes, node, -1, hasharr);
880 }
881
882
883 /** hash ancestors of given edge with possible conflicts */
885  const PSEUDOANS* pseudoancestors, /**< pseudo-ancestors */
886  int edge, /**< edge for which to hash */
887  SCIP_Bool revertIfConflict, /**< revert on conflict? */
888  SCIP_Bool* conflict, /**< conflict? */
889  int* hasharr /**< hash array */
890 )
891 {
892  const int halfedge = edge / 2;
893
894  assert(pseudoancestors && hasharr);
895  assert(halfedge >= 0 && halfedge < pseudoancestors->halfnedges);
896
897  blockedAncestors_hashDirty(pseudoancestors->ans_halfedges, halfedge, revertIfConflict, conflict, hasharr);
898 }
899
900
901 /** hash ancestors of given node with possible conflicts */
903  const PSEUDOANS* pseudoancestors, /**< pseudo-ancestors */
904  int node, /**< node for which to hash */
905  SCIP_Bool revertIfConflict, /**< revert on conflict? */
906  SCIP_Bool* conflict, /**< conflict? */
907  int* hasharr /**< hash array */
908 )
909 {
910  assert(pseudoancestors && hasharr);
911  assert(node >= 0 && node < pseudoancestors->nnodes);
912
913  blockedAncestors_hashDirty(pseudoancestors->ans_nodes, node, revertIfConflict, conflict, hasharr);
914 }
915
916
917 /** unhash ancestors of given edge with possible conflicts */
919  const PSEUDOANS* pseudoancestors, /**< pseudo-ancestors */
920  int edge, /**< edge for which to unhash */
921  int* hasharr /**< hash array */
922 )
923 {
924  const int halfedge = edge / 2;
925
926  assert(pseudoancestors && hasharr);
927  assert(halfedge >= 0 && halfedge < pseudoancestors->halfnedges);
928
929  blockedAncestors_unhashDirty(pseudoancestors->ans_halfedges, halfedge, hasharr);
930 }
931
932
933 /** hash ancestors of given node with possible conflicts */
935  const PSEUDOANS* pseudoancestors, /**< pseudo-ancestors */
936  int node, /**< node for which to unhash */
937  int* hasharr /**< hash array */
938 )
939 {
940  assert(pseudoancestors && hasharr);
941  assert(node >= 0 && node < pseudoancestors->nnodes);
942
943  blockedAncestors_unhashDirty(pseudoancestors->ans_nodes, node, hasharr);
944 }
945
946
947 /** any ancestors of given edge already hashed? */
949  const PSEUDOANS* pseudoancestors, /**< pseudo-ancestors */
950  int edge, /**< edge for which to check */
951  const int* hasharr /**< hash array */
952 )
953 {
954  const int block_id = edge / 2;
955
956  assert(pseudoancestors && hasharr);
957
958  return blockedAncestors_hashIsHitBlock(pseudoancestors->ans_halfedges, block_id, hasharr);
959 }
960
961 /** any ancestors of given node already hashed? */
963  const PSEUDOANS* pseudoancestors, /**< pseudo-ancestors */
964  int node, /**< node for which to check */
965  const int* hasharr /**< hash array */
966 )
967 {
968  assert(pseudoancestors && hasharr);
969
970  return blockedAncestors_hashIsHitBlock(pseudoancestors->ans_nodes, node, hasharr);
971 }
972
973
974 /** initializes edge ancestors */
976  SCIP* scip, /**< SCIP data structure */
977  GRAPH* g /**< the graph */
978 )
979 {
980  const int nedges = graph_get_nEdges(g);
981  IDX** ancestors = g->ancestors;
982
983  assert(ancestors);
984
985  if( graph_typeIsUndirected(g) )
986  {
987  for( int e = 0; e < nedges; e += 2 )
988  {
989  SCIP_CALL( SCIPallocBlockMemory(scip, &(ancestors[e])) ); /*lint !e866*/
990  ancestors[e + 1] = NULL;
991  ancestors[e]->index = e;
992  ancestors[e]->parent = NULL;
993  }
994  }
995  else
996  {
997  for( int e = 0; e < nedges; e++ )
998  {
999  SCIP_CALL( SCIPallocBlockMemory(scip, &(ancestors[e])) ); /*lint !e866*/
1000  ancestors[e]->index = e;
1001  ancestors[e]->parent = NULL;
1002  }
1003  }
1004
1005  return SCIP_OKAY;
1006 }
1007
1008
1009 /** any ancestors of given edges in conflict? */
1011  SCIP* scip, /**< SCIP data structure */
1012  const GRAPH* g, /**< the graph */
1013  const int* edges, /**< edges to check */
1014  int nedges /**< number of edges to check */
1015 )
1016 {
1017  const PSEUDOANS* const pseudoancestors = g->pseudoancestors;
1018  int* hasharr;
1019  int i;
1020  SCIP_Bool conflict = FALSE;
1021
1022  assert(g && edges);
1023
1025
1026  for( i = 0; i < nedges; i++ )
1027  {
1028  graph_pseudoAncestors_hashEdgeDirty(pseudoancestors, edges[i], TRUE, &conflict, hasharr);
1029
1030  if( conflict )
1031  break;
1032  }
1033
1034  for( int j = 0; j < i; j++ )
1035  graph_pseudoAncestors_unhashEdge(pseudoancestors, edges[j], hasharr);
1036
1037 #ifndef NDEBUG
1038  for( int j = 0; j < g->knots; j++ )
1039  assert(hasharr[0] == 0);
1040 #endif
1041
1042  SCIPfreeCleanBufferArray(scip, &hasharr);
1043
1044  return conflict;
1045 }
1046
1047
1048 /** initializes pseudo ancestors */
1050  SCIP* scip, /**< SCIP data structure */
1051  GRAPH* g /**< the graph */
1052 )
1053 {
1054  assert(scip && g);
1055  assert(g->pseudoancestors == NULL);
1056
1058
1059  return SCIP_OKAY;
1060 }
1061
1062
1063 /** initializes pseudo ancestors with given size */
1065  SCIP* scip, /**< SCIP data structure */
1066  int nedges, /**< number of edges to use */
1067  GRAPH* g /**< the graph */
1068 )
1069 {
1070  PSEUDOANS* pseudoancestors;
1071
1072  assert(scip && g);
1073  assert(g->pseudoancestors == NULL);
1074  assert(nedges > 0);
1075  assert(nedges % 2 == 0);
1076
1077  SCIP_CALL( SCIPallocMemory(scip, &pseudoancestors) );
1078
1079  g->pseudoancestors = pseudoancestors;
1080
1081  pseudoancestors->nnodes = g->knots;
1082  pseudoancestors->nAllPseudoancestors = 0;
1083  pseudoancestors->halfnedges = nedges / 2;
1084
1085  SCIP_CALL( blockedAncestors_init(pseudoancestors->halfnedges, &(pseudoancestors->ans_halfedges)) );
1086
1087  if( graph_pc_isPcMw(g) )
1088  {
1089  SCIP_CALL( blockedAncestors_init(g->knots, &(pseudoancestors->ans_nodes)) );
1090  }
1091  else
1092  {
1093  pseudoancestors->ans_nodes = NULL;
1094  }
1095
1096  return SCIP_OKAY;
1097 }
1098
1099
1100 /** frees pseudo ancestors */
1102  SCIP* scip, /**< SCIP data structure */
1103  GRAPH* g /**< the graph */
1104  )
1105 {
1106  PSEUDOANS* pseudoancestors;
1107
1108  assert(scip && g && g->pseudoancestors);
1109  assert(g->pseudoancestors->nAllPseudoancestors >= 0);
1110
1111  pseudoancestors = g->pseudoancestors;
1112
1113  blockedAncestors_free(scip, &(pseudoancestors->ans_halfedges));
1114
1115  if( pseudoancestors->ans_nodes )
1116  blockedAncestors_free(scip, &(pseudoancestors->ans_nodes));
1117
1118  assert(pseudoancestors->ans_halfedges == NULL);
1119  assert(pseudoancestors->ans_nodes == NULL);
1120
1121  SCIPfreeMemoryArray(scip, &(g->pseudoancestors));
1122
1123  assert(g->pseudoancestors == NULL);
1124 }
1125
1126
1127 /** frees pseudo ancestor block for given edge */
1129  SCIP* scip, /**< SCIP data structure */
1130  int edge_free, /**< edge for which to free pseudo ancestors */
1131  GRAPH* g /**< the graph */
1132 )
1133 {
1134  const int block_id = edge_free / 2;
1135
1136  assert(scip && g && g->pseudoancestors && g->pseudoancestors->ans_halfedges);
1137  assert(block_id >= 0 && block_id < g->pseudoancestors->halfnedges);
1138
1140 }
1141
1142
1143 /** frees pseudo ancestor block for given node */
1145  SCIP* scip, /**< SCIP data structure */
1146  int node_free, /**< node for which to free pseudo ancestors */
1147  GRAPH* g /**< the graph */
1148 )
1149 {
1150  assert(scip && g && g->pseudoancestors && g->pseudoancestors->ans_nodes);
1151  assert(graph_pc_isPcMw(g));
1152  assert(node_free >= 0 && node_free < g->pseudoancestors->nnodes);
1153
1155 }
1156
1157
1158 /** returns number of pseudo ancestors for given edge */
1160  const GRAPH* g, /**< the graph */
1161  int edge /**< edge for which to return number of pseudo ancestors */
1162  )
1163 {
1164  const int halfedge = edge / 2;
1165
1166  assert(g && g->pseudoancestors && g->pseudoancestors->ans_halfedges);
1167  assert(halfedge >= 0 && halfedge < g->pseudoancestors->halfnedges);
1168
1169  return g->pseudoancestors->ans_halfedges->sizes[halfedge];
1170 }
1171
1172
1173 /** returns number of pseudo ancestors for given node */
1175  const GRAPH* g, /**< the graph */
1176  int node /**< node for which to return number of pseudo ancestors */
1177  )
1178 {
1179  assert(g && g->pseudoancestors && g->pseudoancestors->ans_nodes);
1180  assert(node >= 0 && node < g->pseudoancestors->nnodes);
1181
1182  return g->pseudoancestors->ans_nodes->sizes[node];
1183 }
1184
1185
1186 /** returns pseudo ancestors for given edge */
1188  const GRAPH* g, /**< the graph */
1189  int edge /**< edge for which to return pseudo ancestors */
1190  )
1191 {
1192  const int halfedge = edge / 2;
1193
1194  assert(g && g->pseudoancestors && g->pseudoancestors->ans_halfedges);
1195  assert(halfedge >= 0 && halfedge < g->pseudoancestors->halfnedges);
1196
1197  return g->pseudoancestors->ans_halfedges->blocks[halfedge];
1198 }
1199
1200
1201 /** returns pseudo ancestors for given edge */
1203  const GRAPH* g, /**< the graph */
1204  int edge /**< edge for which to return ancestors */
1205  )
1206 {
1207  int e = edge;
1208
1209  assert(g);
1210  assert(graph_edge_isInRange(g, edge));
1211  assert(!graph_typeIsUndirected(g) || (g->ancestors[edge] == NULL) == (edge % 2 == 1));
1212
1213  if( !g->ancestors[edge] )
1214  {
1215  assert(graph_typeIsUndirected(g));
1216  e--;
1217  assert(e == flipedge(edge));
1218  }
1219  assert(g->ancestors[e]);
1220
1221  return g->ancestors[e];
1222 }
1223
1224
1225 /** prints pseudo ancestors for given node */
1227  const GRAPH* g, /**< the graph */
1228  int node /**< node for which to return pseudo ancestors */
1229  )
1230 {
1231  int* ancestors;
1232  int nancestors;
1233
1234  assert(g && g->pseudoancestors && g->pseudoancestors->ans_nodes);
1235  assert(node >= 0 && node < g->pseudoancestors->nnodes);
1236
1237  ancestors = g->pseudoancestors->ans_nodes->blocks[node];
1238  nancestors = g->pseudoancestors->ans_nodes->sizes[node];
1239
1240  printf("node %d \n", node);
1241
1242  for( int i = 0; i < nancestors; i++ )
1243  printf("...ancestor: %d \n", ancestors[i]);
1244 }
1245
1246
1247 /** prints pseudo ancestors for given edge */
1249  const GRAPH* g, /**< the graph */
1250  int edge /**< edge for which to return pseudo ancestors */
1251  )
1252 {
1253  const int halfedge = edge / 2;
1254  int* ancestors;
1255  int nancestors;
1256
1257  assert(g && g->pseudoancestors && g->pseudoancestors->ans_halfedges);
1258  assert(halfedge >= 0 && halfedge < g->pseudoancestors->halfnedges);
1259
1260  ancestors = g->pseudoancestors->ans_halfedges->blocks[halfedge];
1261  nancestors = g->pseudoancestors->ans_halfedges->sizes[halfedge];
1262
1263  for( int i = 0; i < nancestors; i++ )
1264  printf("...ancestor: %d \n", ancestors[i]);
1265 }
1266
1267
1268 /** returns pseudo ancestors for given node */
1270  const GRAPH* g, /**< the graph */
1271  int node /**< node for which to return pseudo ancestors */
1272  )
1273 {
1274  assert(g && g->pseudoancestors && g->pseudoancestors->ans_nodes);
1275  assert(node >= 0 && node < g->pseudoancestors->nnodes);
1276
1277  return g->pseudoancestors->ans_nodes->blocks[node];
1278 }
1279
1280
1281 /** returns number of pseudo-ancestors */
1283  const GRAPH* g /**< the graph */
1284  )
1285 {
1286  assert(g && g->pseudoancestors);
1287
1289 }
1290
1291
1292 /** adds new pseudo ancestor and provides index */
1294  GRAPH* g, /**< the graph (in/out) */
1295  int* pseudoancestor /**< gives the new pseudo ancestor index (out) */
1296  )
1297 {
1298  assert(pseudoancestor && g && g->pseudoancestors);
1299  assert(g->pseudoancestors->nAllPseudoancestors >= 0);
1301
1302  *pseudoancestor = (g->pseudoancestors->nAllPseudoancestors - 1);
1303 }
1304
1305
1306 /** adds n new pseudo ancestor */
1308  int nadd, /**< number of ancestors to add */
1309  GRAPH* g /**< the graph (in/out) */
1310  )
1311 {
1312  assert(g && g->pseudoancestors);
1313  assert(nadd > 0);
1314
1315  assert(g->pseudoancestors->nAllPseudoancestors >= 0);
1317 }
1318
1319
1320 /** returns minimum required number for hash array */
1322  const PSEUDOANS* pseudoancestors /**< pseudo-ancestors */
1323  )
1324 {
1325  assert(pseudoancestors);
1326  assert(pseudoancestors->nAllPseudoancestors >= 0);
1327  assert(getNextPow2(pseudoancestors->nAllPseudoancestors + 1) > pseudoancestors->nAllPseudoancestors);
1328
1329  return getNextPow2(pseudoancestors->nAllPseudoancestors + 1);
1330 }
1331
1332
1333 /** appends copy of pseudo ancestors of edge_source to edge_target */
1335  SCIP* scip, /**< SCIP data structure */
1336  int edge_target, /**< edge target */
1337  int edge_source, /**< edge source */
1338  SCIP_Bool revertIfConflict, /**< break on conflict */
1339  GRAPH* g, /**< the graph */
1340  SCIP_Bool* conflict /**< conflict? */
1341 )
1342 {
1343  PSEUDOANS* const pseudoancestors = g->pseudoancestors;
1344  const int hasharr_size = graph_pseudoAncestorsGetHashArraySize(pseudoancestors);
1345  const int target = edge_target / 2;
1346  const int source = edge_source / 2;
1347
1348  assert(scip && g && pseudoancestors && conflict);
1349
1350  SCIP_CALL( blockedAncestors_appendCopy(scip, target, pseudoancestors->ans_halfedges, source, revertIfConflict,
1351  hasharr_size, pseudoancestors->ans_halfedges, conflict) );
1352
1353  return SCIP_OKAY;
1354 }
1355
1356
1357 /** appends copy of pseudo ancestors of node source to node target */
1359  SCIP* scip, /**< SCIP data structure */
1360  int node_target, /**< node target */
1361  int node_source, /**< node source */
1362  SCIP_Bool revertIfConflict, /**< break on conflict */
1363  GRAPH* g, /**< the graph */
1364  SCIP_Bool* conflict /**< conflict? */
1365 )
1366 {
1367  PSEUDOANS* const pseudoancestors = g->pseudoancestors;
1368  const int hasharr_size = graph_pseudoAncestorsGetHashArraySize(pseudoancestors);
1369
1370  assert(scip && g && pseudoancestors && conflict);
1371
1372  SCIP_CALL( blockedAncestors_appendCopy(scip, node_target, pseudoancestors->ans_nodes, node_source, revertIfConflict,
1373  hasharr_size, pseudoancestors->ans_nodes, conflict) );
1374
1375  return SCIP_OKAY;
1376 }
1377
1378
1379 /** appends copy of pseudo ancestors of node source to edge target */
1381  SCIP* scip, /**< SCIP data structure */
1382  int edge_target, /**< edge target */
1383  int node_source, /**< node source */
1384  SCIP_Bool revertIfConflict, /**< break on conflict */
1385  GRAPH* g, /**< the graph */
1386  SCIP_Bool* conflict /**< conflict? */
1387 )
1388 {
1389  PSEUDOANS* const pseudoancestors = g->pseudoancestors;
1390  const int hasharr_size = graph_pseudoAncestorsGetHashArraySize(pseudoancestors);
1391  const int target = edge_target / 2;
1392
1393  assert(scip && g && pseudoancestors && conflict);
1394
1395  SCIP_CALL( blockedAncestors_appendCopy(scip, target, pseudoancestors->ans_nodes, node_source, revertIfConflict,
1396  hasharr_size, pseudoancestors->ans_halfedges, conflict) );
1397
1398  return SCIP_OKAY;
1399 }
1400
1401
1402 /** appends copy of pseudo ancestors of edge source to node target */
1404  SCIP* scip, /**< SCIP data structure */
1405  int node_target, /**< node target */
1406  int edge_source, /**< edge source */
1407  SCIP_Bool revertIfConflict, /**< break on conflict */
1408  GRAPH* g, /**< the graph */
1409  SCIP_Bool* conflict /**< conflict? */
1410 )
1411 {
1412  PSEUDOANS* const pseudoancestors = g->pseudoancestors;
1413  const int hasharr_size = graph_pseudoAncestorsGetHashArraySize(pseudoancestors);
1414  const int source = edge_source / 2;
1415
1416  assert(scip && g && pseudoancestors && conflict);
1417
1418  SCIP_CALL( blockedAncestors_appendCopy(scip, node_target, pseudoancestors->ans_halfedges, source, revertIfConflict,
1419  hasharr_size, pseudoancestors->ans_nodes, conflict) );
1420
1421  return SCIP_OKAY;
1422 }
1423
1424
1425 /** appends given of pseudo ancestors to edge target */
1427  SCIP* scip, /**< SCIP data structure */
1428  int edge_target, /**< edge target */
1429  const SINGLETONANS* source, /**< source */
1430  SCIP_Bool revertIfConflict, /**< break on conflict */
1431  GRAPH* g, /**< the graph */
1432  SCIP_Bool* conflict /**< conflict? */
1433 )
1434 {
1435  assert(scip && g && conflict && source);
1436
1437  *conflict = FALSE;
1438
1439  if( source->npseudoancestors > 0 )
1440  {
1441  const PSEUDOANS* const pseudoancestors = g->pseudoancestors;
1442  const int* const ancestors = source->pseudoancestors;
1443  const int target = edge_target / 2;
1444  const int nancestors = source->npseudoancestors;
1445  const int hasharr_size = graph_pseudoAncestorsGetHashArraySize(pseudoancestors);
1446
1447  assert(pseudoancestors);
1448
1449  SCIP_CALL( blockedAncestors_appendArray(scip, target, ancestors, nancestors, revertIfConflict, hasharr_size, pseudoancestors->ans_halfedges, conflict) );
1450  }
1451
1452  return SCIP_OKAY;
1453 }
1454
1455
1456
1457 /** appends copy of pseudo ancestors in array form to edge target */
1459  SCIP* scip, /**< SCIP data structure */
1460  int edge_target, /**< edge target */
1461  const int* ancestors, /**< pseudo ancestors array */
1462  int nancestors, /**< number of ancestors */
1463  GRAPH* g, /**< the graph */
1464  SCIP_Bool* conflict /**< conflict? */
1465 )
1466 {
1467  assert(scip && g && conflict);
1468  assert(nancestors >= 0);
1469
1470  *conflict = FALSE;
1471
1472  if( nancestors > 0 )
1473  {
1474  const PSEUDOANS* const pseudoancestors = g->pseudoancestors;
1475  const int target = edge_target / 2;
1476  const int hasharr_size = graph_pseudoAncestorsGetHashArraySize(pseudoancestors);
1477  const SCIP_Bool revertIfConflict = FALSE;
1478
1479  assert(ancestors);
1480  assert(pseudoancestors);
1481
1482  SCIP_CALL( blockedAncestors_appendArray(scip, target, ancestors, nancestors, revertIfConflict, hasharr_size, pseudoancestors->ans_halfedges, conflict) );
1483  }
1484
1485  return SCIP_OKAY;
1486 }
1487
1488 /** appends pseudo ancestors of edge_source to edge_target, ancestors for edge_source are deleted */
1490  SCIP* scip, /**< SCIP data structure */
1491  int edge_target, /**< target edge */
1492  int edge_source, /**< source edge */
1493  SCIP_Bool revertIfConflict, /**< break on conflict */
1494  GRAPH* g, /**< the graph */
1495  SCIP_Bool* conflict /**< conflict? */
1496 )
1497 {
1498  SCIP_CALL( graph_pseudoAncestors_appendCopyEdge(scip, edge_target, edge_source, revertIfConflict, g, conflict) );
1499  graph_edge_delPseudoAncestors(scip, edge_source, g);
1500
1501  return SCIP_OKAY;
1502 }
1503
1504
1505 /** appends pseudo ancestors of node source to node target, ancestors for source are deleted */
1507  SCIP* scip, /**< SCIP data structure */
1508  int node_target, /**< target node */
1509  int node_source, /**< source node */
1510  SCIP_Bool revertIfConflict, /**< break on conflict */
1511  GRAPH* g, /**< the graph */
1512  SCIP_Bool* conflict /**< conflict? */
1513 )
1514 {
1515  SCIP_CALL( graph_pseudoAncestors_appendCopyNode(scip, node_target, node_source, revertIfConflict, g, conflict) );
1516  graph_knot_delPseudoAncestors(scip, node_source, g);
1517
1518  return SCIP_OKAY;
1519 }
1520
1521
1522 /** adds pseudo ancestor to ancestor list of given edge */
1524  SCIP* scip, /**< SCIP data structure */
1525  int edge_target, /**< edge for which to add pseudo ancestor */
1526  int ancestor, /**< (index of) pseudo ancestor */
1527  GRAPH* g /**< the graph */
1528 )
1529 {
1530  PSEUDOANS* const pseudoancestors = g->pseudoancestors;
1531  const int hasharr_size = graph_pseudoAncestorsGetHashArraySize(pseudoancestors);
1532  const int target = edge_target / 2;
1533
1534  assert(scip && g && pseudoancestors);
1535  assert(target >= 0 && target < g->pseudoancestors->halfnedges);
1536  assert(ancestor >= 0 && ancestor < g->pseudoancestors->nAllPseudoancestors);
1537
1538  SCIP_CALL( blockedAncestors_addAncestor(scip, target, ancestor, hasharr_size, pseudoancestors->ans_halfedges) );
1539
1540  return SCIP_OKAY;
1541 }
1542
1543
1544 /** adds pseudo ancestor to ancestor list of given node */
1546  SCIP* scip, /**< SCIP data structure */
1547  int node_target, /**< node for which to add pseudo ancestor */
1548  int ancestor, /**< (index of) pseudo ancestor */
1549  GRAPH* g /**< the graph */
1550 )
1551 {
1552  PSEUDOANS* const pseudoancestors = g->pseudoancestors;
1553  const int hasharr_size = graph_pseudoAncestorsGetHashArraySize(pseudoancestors);
1554
1555  assert(scip && g && pseudoancestors);
1556  assert(graph_pc_isPcMw(g));
1557  assert(pseudoancestors->ans_nodes);
1558  assert(node_target >= 0 && node_target < g->pseudoancestors->nnodes);
1559  assert(ancestor >= 0 && ancestor < g->pseudoancestors->nAllPseudoancestors);
1560  assert(!graph_pc_knotIsDummyTerm(g, node_target));
1561
1562  SCIP_CALL( blockedAncestors_addAncestor(scip, node_target, ancestor, hasharr_size, pseudoancestors->ans_nodes) );
1563
1564  return SCIP_OKAY;
1565 }
1566
1567
1568 /** valid pseudo-ancestors (no conflicts)? */
1570  SCIP* scip, /**< SCIP data structure */
1571  const GRAPH* g /**< the graph */
1572 )
1573 {
1574  const PSEUDOANS* const pseudoancestors = g->pseudoancestors;
1575  const int hasharr_size = graph_pseudoAncestorsGetHashArraySize(pseudoancestors);
1576  SCIP_Bool isValid;
1577
1578  assert(scip && g && pseudoancestors);
1579
1580  isValid = blockedAncestors_isValid(scip, hasharr_size, pseudoancestors->ans_halfedges);
1581
1582  if( !isValid )
1583  return FALSE;
1584
1585  if( graph_pc_isPcMw(g) )
1586  {
1587  isValid = blockedAncestors_isValid(scip, hasharr_size, pseudoancestors->ans_nodes);
1588
1589  if( !isValid )
1590  return FALSE;
1591  }
1592
1593  return TRUE;
1594 }
1595
1596 #if 0
1597 /** check whether conflict for one edge */
1598 SCIP_RETCODE graph_checkConflict1_pseudoAncestors(
1599  SCIP* scip, /**< SCIP data structure */
1600  const GRAPH* g, /**< the graph */
1601  int edge1, /**< first edge */
1602  SCIP_Bool* conflict /**< conflict? */
1603 )
1604 {
1605  const int block_id1 = edge1 / 2;
1606
1607
1608  assert(scip && g && g->pseudoancestors);
1609  assert(block_id1 >= 0 && block_id1 < g->pseudoancestors->halfnedges);
1610
1611
1612  return SCIP_OKAY;
1613 }
1614 #endif
1615
1616
1617 /** initializes fixed */
1619  SCIP* scip, /**< SCIP data structure */
1620  GRAPH* g /**< the graph */
1621 )
1622 {
1623  FIXED* fixedcomponents;
1624
1625  assert(scip && g);
1626  assert(g->fixedcomponents == NULL);
1627
1628  SCIP_CALL( SCIPallocMemory(scip, &(g->fixedcomponents)) );
1629
1630  fixedcomponents = g->fixedcomponents;
1631
1632  fixedcomponents->fixedges = NULL;
1633  fixedcomponents->fixpseudonodes = NULL;
1634  fixedcomponents->nfixnodes = 0;
1635  fixedcomponents->movedFrom = FALSE;
1636
1637  return SCIP_OKAY;
1638 }
1639
1640
1641 /** frees fixed */
1643  SCIP* scip, /**< SCIP data structure */
1644  GRAPH* g /**< the graph */
1645  )
1646 {
1647  IDX* curr;
1648  FIXED* fixedcomponents = g->fixedcomponents;
1649
1650  assert(scip && g);
1651  assert(fixedcomponents != NULL);
1652  assert(fixedcomponents->nfixnodes >= 0);
1653
1654  if( fixedcomponents->nfixnodes > 0 )
1655  SCIPfreeBlockMemoryArray(scip, &(fixedcomponents->fixpseudonodes), fixedcomponents->nfixnodes);
1656
1657  curr = fixedcomponents->fixedges;
1658  while( curr != NULL )
1659  {
1660  fixedcomponents->fixedges = curr->parent;
1661  SCIPfreeBlockMemory(scip, &(curr));
1662
1663  curr = fixedcomponents->fixedges;
1664  }
1665
1666  SCIPfreeMemory(scip, &(g->fixedcomponents));
1667 }
1668
1669
1670 /** frees fixed edges */
1672  SCIP* scip, /**< SCIP data structure */
1673  GRAPH* g /**< the graph */
1674  )
1675 {
1676  IDX* curr;
1677  FIXED* fixedcomponents = g->fixedcomponents;
1678
1679  assert(scip && g);
1680  assert(fixedcomponents != NULL);
1681  assert(fixedcomponents->nfixnodes >= 0);
1682
1683  curr = fixedcomponents->fixedges;
1684  while( curr != NULL )
1685  {
1686  fixedcomponents->fixedges = curr->parent;
1687  SCIPfreeBlockMemory(scip, &(curr));
1688
1689  curr = fixedcomponents->fixedges;
1690
1691  assert(0 && "todo should not happen");
1692
1693  }
1694 }
1695
1696
1697 /** adds new fixed components */
1699  SCIP* scip, /**< SCIP data structure */
1700  IDX* edges, /**< edge to add or NULL */
1701  const int* pseudonodes, /**< nodes to add */
1702  int npseudonodes, /**< number of nodes to add */
1703  GRAPH* g /**< the graph */
1704 )
1705 {
1706  FIXED* fixedcomponents;
1707
1708  assert(scip && g);
1709  assert(npseudonodes >= 0);
1710
1711  if( g->fixedcomponents == NULL )
1712  SCIP_CALL( graph_init_fixed(scip, g) );
1713
1714  fixedcomponents = g->fixedcomponents;
1715  assert(!fixedcomponents->movedFrom);
1716
1717  if( edges )
1718  {
1719  SCIP_Bool conflict = FALSE;
1720
1721  SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(fixedcomponents->fixedges), edges, &conflict) );
1722  assert(!conflict);
1723  }
1724
1725  if( npseudonodes > 0 )
1726  {
1727  int nfixnnodes = fixedcomponents->nfixnodes;
1728  const int nfixnnodes_new = nfixnnodes + npseudonodes;
1729
1730  assert(pseudonodes);
1731
1732  if( nfixnnodes == 0 )
1733  {
1734  assert(!fixedcomponents->fixpseudonodes);
1735  assert(nfixnnodes_new == npseudonodes);
1736
1737  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(fixedcomponents->fixpseudonodes), nfixnnodes_new) );
1738  }
1739  else
1740  {
1741  assert(fixedcomponents->fixpseudonodes);
1742
1743  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(fixedcomponents->fixpseudonodes), nfixnnodes, nfixnnodes_new) );
1744  }
1745
1746  for( int i = 0; i < npseudonodes; i++ )
1747  fixedcomponents->fixpseudonodes[nfixnnodes++] = pseudonodes[i];
1748
1749  assert(nfixnnodes == nfixnnodes_new);
1750  fixedcomponents->nfixnodes = nfixnnodes_new;
1751
1752  assert(g->withInexactReductions || fixedPseudoAncestorsAreValid(scip, g));
1753  }
1754
1755  return SCIP_OKAY;
1756 }
1757
1758
1759 /** adds ancestors from given edges */
1761  SCIP* scip, /**< SCIP data structure */
1762  int edge, /**< edge */
1763  GRAPH* g /**< the graph */
1764 )
1765 {
1766  assert(scip && g);
1767  assert(edge >= 0 && edge < g->edges);
1768  assert(g->ancestors);
1769
1771  graph_edge_nPseudoAncestors(g, edge), g) );
1772
1773  return SCIP_OKAY;
1774 }
1775
1776
1777 /** adds ancestors from given edges */
1779  SCIP* scip, /**< SCIP data structure */
1780  int node, /**< node */
1781  GRAPH* g /**< the graph */
1782 )
1783 {
1784  assert(scip && g);
1785  assert(node >= 0 && node < g->knots);
1786  assert(graph_pc_isPcMw(g));
1787  assert(!graph_pc_knotIsDummyTerm(g, node)); /* todo really? */
1788  assert(g->ancestors && g->pcancestors);
1789
1791  graph_knot_nPseudoAncestors(g, node), g) );
1792
1793  return SCIP_OKAY;
1794 }
1795
1796
1797 /** moves ancestors from given edges */
1799  SCIP* scip, /**< SCIP data structure */
1800  int node, /**< node */
1801  GRAPH* g /**< the graph */
1802 )
1803 {
1804  assert(scip && g);
1805  assert(node >= 0 && node < g->knots);
1806  assert(graph_pc_isPcMw(g));
1807  assert(g->pcancestors);
1808
1809  SCIP_CALL( graph_fixed_addNodePc(scip, node, g) );
1810
1811  if( g->pcancestors[node] )
1812  SCIPintListNodeFree(scip, &(g->pcancestors[node]));
1813
1814  graph_knot_delPseudoAncestors(scip, node, g);
1815
1816  return SCIP_OKAY;
1817 }
1818
1819
1820 /** resets */
1822  GRAPH* g /**< the graph */
1823 )
1824 {
1825  assert(g);
1826
1827  if( g->fixedcomponents != NULL )
1828  {
1829  assert(g->fixedcomponents->movedFrom);
1831  }
1832 }
1833
1834
1835 /** initializes */
1837  SCIP* scip, /**< SCIP data structure */
1838  GRAPH* graph /**< graph */
1839  )
1840 {
1841  int* trace;
1842  const int nnodes = graph_get_nNodes(graph);
1843
1844  assert(scip);
1845  assert(!graph->contracttrace);
1846
1847  SCIP_CALL( SCIPallocMemoryArray(scip, &(trace), nnodes) );
1848
1849  for( int i = 0; i < nnodes; i++ )
1850  trace[i] = -1;
1851
1852  graph->contracttrace = trace;
1853
1854  return SCIP_OKAY;
1855 }
1856
1857
1858 /** has the node a contract trace? */
1860  int node, /**< node to trace back from */
1861  const GRAPH* graph /**< graph */
1862  )
1863 {
1864  assert(graph && graph->contracttrace);
1865  assert(graph_knot_isInRange(graph, node));
1866
1867  return (graph->contracttrace[node] != -1);
1868 }
1869
1870
1871 /** traces contraction back; returns traced node */
1873  int node, /**< node to trace back from */
1874  const GRAPH* graph /**< graph */
1875  )
1876 {
1877  const int* const trace = graph->contracttrace;
1878  int newnode;
1879
1880  assert(graph && trace);
1881  assert(graph_knot_isInRange(graph, node));
1882  assert(graph->grad[node] == 0);
1883  assert(trace[node] != -1);
1884
1885  for( newnode = node; trace[newnode] != -1; newnode = trace[newnode] )
1886  {
1887  assert(graph_knot_isInRange(graph, newnode));
1888  }
1889  assert(graph_knot_isInRange(graph, newnode));
1890
1891  return newnode;
1892 }
1893
1894 /** copies and potentially moves fixed components */
1896  SCIP* scip, /**< SCIP data structure */
1897  GRAPH* g, /**< the original graph */
1898  SCIP_Bool moveFixedEdges, /**< move fixed edges? If false, nothing is done! */
1899  GRAPH* g_copy /**< the copied graph */
1900 )
1901 {
1902  FIXED* fixed_copy;
1903  FIXED* fixed_org;
1904
1905  assert(scip && g && g_copy);
1906  assert(g_copy->fixedcomponents == NULL);
1907
1908  if( g->fixedcomponents == NULL )
1909  {
1910  return SCIP_OKAY;
1911  }
1912
1913  SCIP_CALL( graph_init_fixed(scip, g_copy) );
1914  fixed_copy = g_copy->fixedcomponents;
1915  fixed_org = g->fixedcomponents;
1916
1917  assert(fixed_copy && fixed_org);
1918
1919  if( moveFixedEdges )
1920  {
1921  assert(!fixed_org->movedFrom);
1922
1923  fixed_copy->fixedges = fixed_org->fixedges;
1924  fixed_org->fixedges = NULL;
1925  fixed_org->movedFrom = TRUE;
1926  }
1927
1928  fixed_copy->nfixnodes = fixed_org->nfixnodes;
1929  if( fixed_copy->nfixnodes > 0 )
1930  {
1931  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(fixed_copy->fixpseudonodes), fixed_copy->nfixnodes) );
1932  BMScopyMemoryArray(fixed_copy->fixpseudonodes, fixed_org->fixpseudonodes, fixed_copy->nfixnodes);
1933  }
1934  else
1935  {
1936  fixed_copy->fixpseudonodes = NULL;
1937  }
1938
1939  return SCIP_OKAY;
1940 }
1941
1942
1943 /** gets fixed edges */
1945  const GRAPH* g /**< the graph */
1946 )
1947 {
1948  assert(g);
1949
1950  if( !g->fixedcomponents )
1951  return NULL;
1952
1953  return g->fixedcomponents->fixedges;
1954 }
1955
1956 /** gets fixed pseudo eliminated nodes */
1958  SCIP* scip, /**< SCIP data structure */
1959  const GRAPH* g /**< the graph */
1960 )
1961 {
1962  assert(g && scip);
1963
1964  if( !g->fixedcomponents )
1965  return NULL;
1966
1967  return g->fixedcomponents->fixpseudonodes;
1968 }
1969
1970 /** gets number of fixed pseudo eliminated nodes */
1972  const GRAPH* g /**< the graph */
1973 )
1974 {
1975  assert(g);
1976
1977  if( !g->fixedcomponents )
1978  return 0;
1979
1980  return g->fixedcomponents->nfixnodes;
1981 }
void graph_fixed_resetMoved(GRAPH *g)
static SCIP_RETCODE blockedAncestors_appendCopy(SCIP *scip, int block_target, const BLOCKANS *blockedans_source, int block_source, SCIP_Bool breakOnConflict, int hasharr_size, BLOCKANS *blockedans_target, SCIP_Bool *conflict)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:90
SCIP_RETCODE graph_fixed_moveNodePc(SCIP *scip, int node, GRAPH *g)
static SCIP_RETCODE blockedAncestors_realloc(SCIP *scip, int block_id, int capacity_new, BLOCKANS *blockedans)
SCIP_Bool graph_valid_pseudoAncestors(SCIP *scip, const GRAPH *g)
SCIP_RETCODE graph_pseudoAncestors_appendCopyEdgeToNode(SCIP *scip, int node_target, int edge_source, SCIP_Bool revertIfConflict, GRAPH *g, SCIP_Bool *conflict)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
void graph_freePseudoAncestors(SCIP *scip, GRAPH *g)
int graph_pseudoAncestorsGetHashArraySize(const PSEUDOANS *pseudoancestors)
const int * graph_edge_getPseudoAncestors(const GRAPH *g, int edge)
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
static void blockedAncestors_unhashDirty(const BLOCKANS *blockedans, int block_id, int *hasharr)
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
void graph_singletonAncestors_freeMembers(SCIP *scip, SINGLETONANS *singletonans)
SCIP_RETCODE graph_pseudoAncestors_addToNode(SCIP *scip, int node_target, int ancestor, GRAPH *g)
SCIP_Bool graph_pseudoAncestors_edgeIsHashed(const PSEUDOANS *pseudoancestors, int edge, const int *hasharr)
static void blockedAncestors_hash(const BLOCKANS *blockedans, int block_id, int *hasharr)
void graph_pseudoAncestors_unhashNode(const PSEUDOANS *pseudoancestors, int node, int *hasharr)
static int getNextPow2(int number)
Definition: graph_history.c:64
#define EAT_FREE
Definition: graphdefs.h:57
#define FALSE
Definition: def.h:87
#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
void graph_edge_printPseudoAncestors(const GRAPH *g, int edge)
SCIP_RETCODE graph_singletonAncestors_init(SCIP *scip, const GRAPH *g, int edge, SINGLETONANS *singletonans)
BLOCKANS * ans_nodes
Definition: graph_history.c:55
void graph_pseudoAncestors_hashNodeDirty(const PSEUDOANS *pseudoancestors, int node, SCIP_Bool revertIfConflict, SCIP_Bool *conflict, int *hasharr)
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
#define SCIPdebugMessage
Definition: pub_message.h:87
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
#define SCIPallocClearMemoryArray(scip, ptr, num)
Definition: scip_mem.h:57
SCIP_RETCODE graph_pseudoAncestors_appendMoveEdge(SCIP *scip, int edge_target, int edge_source, SCIP_Bool revertIfConflict, GRAPH *g, SCIP_Bool *conflict)
static void blockedAncestors_free(SCIP *scip, BLOCKANS **blockedans)
void graph_knot_printPseudoAncestors(const GRAPH *g, int node)
static void blockedAncestors_freeBlock(SCIP *scip, int block_id, BLOCKANS *blockedans)
static SCIP_Bool fixedPseudoAncestorsAreValid(SCIP *scip, const GRAPH *g)
void SCIPintListNodeFree(SCIP *scip, IDX **node)
Definition: misc_stp.c:325
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:133
static SCIP_Bool blockedAncestors_hashIsHitBlock(const BLOCKANS *blockedans, int block_id, const int *hasharr)
int *RESTRICT oeat
Definition: graphdefs.h:231
const int * graph_knot_getPseudoAncestors(const GRAPH *g, int node)
int graph_knot_nPseudoAncestors(const GRAPH *g, int node)
static SCIP_Bool ancestorsMarkConflict(const GRAPH *graph, int edge, int *ancestormark)
Definition: graph_history.c:88
SCIP_RETCODE graph_initContractTracing(SCIP *scip, GRAPH *graph)
SCIP_Bool withInexactReductions
Definition: graphdefs.h:266
SCIP_RETCODE SCIPintListNodeAppendCopy(SCIP *scip, IDX **node1, IDX *node2, SCIP_Bool *conflict)
Definition: misc_stp.c:197
IDX ** ancestors
Definition: graphdefs.h:234
int orgedges
Definition: graphdefs.h:220
FIXED * fixedcomponents
Definition: graphdefs.h:237
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIP_RETCODE graph_pseudoAncestors_appendCopyArrayToEdge(SCIP *scip, int edge_target, const int *ancestors, int nancestors, GRAPH *g, SCIP_Bool *conflict)
PSEUDOANS * pseudoancestors
Definition: graphdefs.h:236
const int * graph_getFixpseudonodes(SCIP *scip, const GRAPH *g)
Definition: graphdefs.h:201
SCIP_RETCODE graph_copyFixed(SCIP *scip, GRAPH *g, SCIP_Bool moveFixedEdges, GRAPH *g_copy)
#define NULL
Definition: lpi_spx1.cpp:155
int knots
Definition: graphdefs.h:190
struct blocked_pseudo_ancestor BLOCKANS
#define SCIP_CALL(x)
Definition: def.h:384
IDX ** pcancestors
Definition: graphdefs.h:235
static SCIP_RETCODE blockedAncestors_init(int nblocks, BLOCKANS **blockedans)
SCIP_Bool graph_pseudoAncestors_nodeIsHashed(const PSEUDOANS *pseudoancestors, int node, const int *hasharr)
SCIP_RETCODE graph_initAncestors(SCIP *scip, GRAPH *g)
void graph_free_fixed(SCIP *scip, GRAPH *g)
static SCIP_Bool blockedAncestors_blockIsValid(int block_id, const BLOCKANS *blockedans, int *hasharr)
IDX * graph_getFixedges(const GRAPH *g)
void graph_free_fixedEdgesOnly(SCIP *scip, GRAPH *g)
void graph_pseudoAncestors_unhashEdge(const PSEUDOANS *pseudoancestors, int edge, int *hasharr)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define SCIP_Bool
Definition: def.h:84
void graph_pseudoAncestors_hashNode(const PSEUDOANS *pseudoancestors, int node, int *hasharr)
static SCIP_RETCODE blockedAncestors_appendArray(SCIP *scip, int block_target, const int *ancestors_source, int size_source, SCIP_Bool breakOnConflict, int hasharr_size, BLOCKANS *blockedans_target, SCIP_Bool *conflict)
static SCIP_Bool blockedAncestors_isValid(SCIP *scip, int hasharr_size, const BLOCKANS *blockedans)
void graph_addPseudoAncestor(GRAPH *g, int *pseudoancestor)
static SCIP_Bool blockedAncestors_hashIsHit(const BLOCKANS *blockedans, int ancestor, const int *hasharr)
#define flipedge(edge)
Definition: graphdefs.h:84
#define MAX(x, y)
Definition: tclique_def.h:83
void graph_knot_delPseudoAncestors(SCIP *scip, int node_free, GRAPH *g)
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
SCIP_RETCODE graph_initPseudoAncestors(SCIP *scip, GRAPH *g)
SCIP_RETCODE graph_fixed_add(SCIP *scip, IDX *edges, const int *pseudonodes, int npseudonodes, GRAPH *g)
SCIP_RETCODE graph_pseudoAncestors_appendCopyEdge(SCIP *scip, int edge_target, int edge_source, SCIP_Bool revertIfConflict, GRAPH *g, SCIP_Bool *conflict)
static long * number
SCIP_RETCODE graph_pseudoAncestors_appendCopyNode(SCIP *scip, int node_target, int node_source, SCIP_Bool revertIfConflict, GRAPH *g, SCIP_Bool *conflict)
SCIP_Bool graph_valid_ancestors(SCIP *scip, const GRAPH *g)
Portable definitions.
SCIP_Bool graph_typeIsUndirected(const GRAPH *)
Definition: graph_stats.c:69
static void blockedAncestors_hashDirty(const BLOCKANS *blockedans, int block_id, SCIP_Bool revertIfConflict, SCIP_Bool *conflict, int *hasharr)
SCIP_RETCODE graph_fixed_addEdge(SCIP *scip, int edge, GRAPH *g)
static void blockedAncestors_unhashPartial(const BLOCKANS *blockedans, int block_id, int nAncestorsToClean, int *hasharr)
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
static SCIP_RETCODE blockedAncestors_addAncestor(SCIP *scip, int block_target, int ancestor, int hasharr_size, BLOCKANS *blockedans)
BLOCKANS * ans_halfedges
Definition: graph_history.c:54
SCIP_RETCODE graph_pseudoAncestors_appendCopyNodeToEdge(SCIP *scip, int edge_target, int node_source, SCIP_Bool revertIfConflict, GRAPH *g, SCIP_Bool *conflict)
SCIP_RETCODE graph_pseudoAncestors_appendCopySingToEdge(SCIP *scip, int edge_target, const SINGLETONANS *source, SCIP_Bool revertIfConflict, GRAPH *g, SCIP_Bool *conflict)
static void ancestorsUnmarkConflict(const GRAPH *graph, int edge, int *ancestormark)
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
SCIP_Real * cost
Definition: graphdefs.h:221
SCIP_Bool graph_edge_isInRange(const GRAPH *, int)
Definition: graph_stats.c:110
IDX * graph_edge_getAncestors(const GRAPH *g, int edge)
void graph_pseudoAncestors_unhashEdgeDirty(const PSEUDOANS *pseudoancestors, int edge, int *hasharr)
int graph_getNfixpseudonodes(const GRAPH *g)
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
SCIP_VAR * a
Definition: circlepacking.c:57
int * contracttrace
Definition: graphdefs.h:238
SCIP_RETCODE graph_fixed_addNodePc(SCIP *scip, int node, GRAPH *g)
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:137
int edges
Definition: graphdefs.h:219
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
SCIP_Bool graph_pseudoAncestors_edgesInConflict(SCIP *scip, const GRAPH *g, const int *edges, int nedges)
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
SCIP_Bool graph_knot_isInRange(const GRAPH *, int)
Definition: graph_node.c:52
void graph_pseudoAncestors_hashEdgeDirty(const PSEUDOANS *pseudoancestors, int edge, SCIP_Bool revertIfConflict, SCIP_Bool *conflict, int *hasharr)
void graph_pseudoAncestors_hashEdge(const PSEUDOANS *pseudoancestors, int edge, int *hasharr)
int graph_edge_nPseudoAncestors(const GRAPH *g, int edge)
SCIP_RETCODE graph_init_fixed(SCIP *scip, GRAPH *g)
#define nnodes
Definition: gastrans.c:65
int graph_getNpseudoAncestors(const GRAPH *g)
SCIP_RETCODE graph_initPseudoAncestorsSized(SCIP *scip, int nedges, GRAPH *g)
SCIPallocBlockMemory(scip, subsol))
struct Int_List_Node * parent
Definition: misc_stp.h:91
#define SCIP_CALL_ABORT(x)
Definition: def.h:363
SCIP_RETCODE graph_pseudoAncestors_appendMoveNode(SCIP *scip, int node_target, int node_source, SCIP_Bool revertIfConflict, GRAPH *g, SCIP_Bool *conflict)
SCIP_RETCODE graph_pseudoAncestors_addToEdge(SCIP *scip, int edge_target, int ancestor, GRAPH *g)
int graph_contractTrace(int node, const GRAPH *graph)
void graph_pseudoAncestors_unhashNodeDirty(const PSEUDOANS *pseudoancestors, int node, int *hasharr)
SCIP_Bool graph_knot_hasContractTrace(int node, const GRAPH *graph)
void graph_edge_delPseudoAncestors(SCIP *scip, int edge_free, GRAPH *g)