Scippy

SCIP

Solving Constraint Integer Programs

expriter.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-2024 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file expriter.c
26  * @ingroup OTHER_CFILES
27  * @brief functions for iterating over algebraic expressions
28  * @author Benjamin Mueller
29  * @author Stefan Vigerske
30  */
31 
32 /* enable this to record where active iterators were initialized
33  * (not thread-safe; problematic when using several SCIP instances concurrently)
34  */
35 /* #define SCIP_DEBUG_EXPRITER */
36 
37 #include <assert.h>
38 
39 #include "scip/expr.h"
40 #include "scip/pub_misc.h"
41 #include "scip/pub_message.h"
42 #include "scip/struct_expr.h"
43 #include "scip/struct_stat.h"
44 
45 #define MINDFSSIZE 16 /**< minimum stack size for DFS*/
46 #define MINBFSSIZE 16 /**< minimum queue size for BFS */
47 
48 #ifdef SCIP_DEBUG_EXPRITER
49 #include <execinfo.h>
50 #include <string.h>
51 #include <stdlib.h>
52 
53 #define MAXSUBSCIPDEPTH 10 /**< minimal subscip-depth to no longer store backtrace */
54 #define MAXBACKTRACE 20 /**< maximal length of backtrace to store */
55 
56 /** backtrace when iterator was initialized
57  * - store per subscip-depth (easier than storing per SCIP instance)
58  * - store per iterator position that can be active concurrently
59  * - one string for each entry in backtrace
60  * - each entry up to 200 characters
61  */
62 char iterinitbacktrace[MAXSUBSCIPDEPTH][SCIP_EXPRITER_MAXNACTIVE][MAXBACKTRACE][200];
63 #endif
64 
65 /*
66  * local functions
67  */
68 
69 #ifdef SCIP_DEBUG_EXPRITER
70 /** obtain current backtrace and store it in iterinitbacktrace */
71 static
72 void storeBacktrace(
73  int subscipdepth, /**< current subscip depth */
74  int iterpos /**< iterator position where to store backtrace */
75  )
76 {
77  void* array[MAXBACKTRACE];
78  char** strings;
79  int size;
80  int i;
81 
82  assert(subscipdepth >= 0);
83  assert(iterpos >= 0);
84  assert(iterpos < SCIP_EXPRITER_MAXNACTIVE);
85 
86  if( subscipdepth > MAXSUBSCIPDEPTH )
87  return;
88 
89  size = backtrace(array, MAXBACKTRACE);
90  strings = backtrace_symbols(array, size);
91  if( strings == NULL )
92  size = 0;
93 
94  for( i = 0; i < size; i++ )
95  strncpy(iterinitbacktrace[subscipdepth][iterpos][i], strings[i], sizeof(iterinitbacktrace[0][0][0]));
96 
97  /* '\0' for remining backtrace entries */
98  while( size < MAXBACKTRACE )
99  iterinitbacktrace[subscipdepth][iterpos][size++][0] = '\0';
100 
101  free(strings);
102 }
103 
104 static
105 void printBacktraces(
106  int subscipdepth /**< current subscip depth */
107  )
108 {
109  int i, j;
110 
111  assert(subscipdepth >= 0);
112  if( subscipdepth >= MAXSUBSCIPDEPTH )
113  {
114  SCIPerrorMessage("subscip depth %d too high to report active iterators", subscipdepth);
115  return;
116  }
117 
118  for( i = 0; i < SCIP_EXPRITER_MAXNACTIVE-1; ++i )
119  {
120  SCIPerrorMessage("Active iterator %d created at:\n", i);
121  for( j = 0; j < MAXBACKTRACE; ++j )
122  {
123  if( iterinitbacktrace[subscipdepth][i][j][0] == '\0' )
124  break;
125  SCIPerrorMessage(" %s\n", iterinitbacktrace[subscipdepth][i][j]);
126  }
127  }
128 }
129 #else
130 #define storeBacktrace(subscipdepth, iterpos)
131 
132 /*lint -e{715}*/
133 static
135  int subscipdepth /**< current subscip depth */
136  )
137 { /*lint --e{715}*/
138  SCIPerrorMessage("Rebuild with SCIP_DEBUG_EXPRITER defined in src/scip/expriter.c to see where currently "
139  "active iterators were initialized.\n");
140 }
141 #endif
142 
143 static
144 void deinit(
145  SCIP_EXPRITER* iterator /**< expression iterator */
146  )
147 {
148  assert(iterator != NULL );
149 
150  if( !iterator->initialized )
151  return;
152 
153  if( iterator->iterindex >= 0 )
154  {
155  /* the iterindex must be the one of the last initialized iterator */
156  assert(iterator->iterindex == iterator->stat->nactiveexpriter-1);
157 
158  /* tell core that this iterator is no longer active */
159  --iterator->stat->nactiveexpriter;
160 
161  iterator->iterindex = -1;
162  }
163 
164  switch( iterator->itertype )
165  {
166  case SCIP_EXPRITER_BFS :
167  {
168  assert(iterator->queue != NULL);
169 
170  SCIPqueueFree(&iterator->queue);
171 
172  break;
173  }
174 
176  {
177  assert(iterator->dfsnvisited != NULL);
178  assert(iterator->dfsexprs != NULL);
179 
180  /* free dfs arrays */
181  BMSfreeBlockMemoryArray(iterator->blkmem, &iterator->dfsnvisited, iterator->dfssize);
182  BMSfreeBlockMemoryArray(iterator->blkmem, &iterator->dfsexprs, iterator->dfssize);
183  iterator->dfssize = 0;
184 
185  break;
186  }
187 
188  case SCIP_EXPRITER_DFS :
189  default: break;
190  }
191 }
192 
193 /** ensures minimum stack size of iterator's data */
194 static
196  SCIP_EXPRITER* iterator, /**< expression iterator */
197  int size /**< minimum requires size */
198  )
199 {
200  assert(iterator != NULL);
201  assert(iterator->blkmem != NULL);
202  assert(iterator->itertype == SCIP_EXPRITER_RTOPOLOGIC);
203  assert(size >= 0);
204 
205  if( size > iterator->dfssize )
206  {
207  int newsize = size * 2;
208 
209  SCIP_ALLOC( BMSreallocBlockMemoryArray(iterator->blkmem, &iterator->dfsexprs, iterator->dfssize, newsize) );
210  SCIP_ALLOC( BMSreallocBlockMemoryArray(iterator->blkmem, &iterator->dfsnvisited, iterator->dfssize, newsize) );
211  iterator->dfssize = newsize;
212  }
213 
214  return SCIP_OKAY;
215 }
216 
217 /** adds an expression to the DFS stack */
218 static
220  SCIP_EXPRITER* iterator, /**< expression iterator */
221  SCIP_EXPR* expr /**< expression */
222  )
223 {
224  assert(iterator != NULL);
225  assert(expr != NULL);
226 
227  SCIP_CALL_ABORT( ensureStackSize(iterator, iterator->dfsnexprs + 1) );
228  iterator->dfsexprs[iterator->dfsnexprs] = expr;
229  iterator->dfsnvisited[iterator->dfsnexprs] = 0;
230  ++(iterator->dfsnexprs);
231 }
232 
233 /** moves to the next expression according to a reverse topological order */
234 static
236  SCIP_EXPRITER* iterator /**< expression iterator */
237  )
238 {
239  SCIP_EXPR* expr;
240  int childidx;
241 
242  assert(iterator != NULL);
243  assert(iterator->itertype == SCIP_EXPRITER_RTOPOLOGIC);
244 
245  /* no expression left */
246  if( iterator->dfsnexprs == 0 )
247  return NULL;
248 
249  /* get expression on the top of the stack */
250  expr = iterator->dfsexprs[iterator->dfsnexprs - 1];
251  childidx = iterator->dfsnvisited[iterator->dfsnexprs - 1];
252 
253  /* remove the expression if all children have been visited */
254  if( childidx >= SCIPexprGetNChildren(expr) )
255  {
256  --(iterator->dfsnexprs);
257  return expr;
258  }
259  /* go to the next child */
260  else
261  {
262  SCIP_EXPR* child = SCIPexprGetChildren(expr)[childidx];
263  assert(child != NULL);
264 
265  /* mark that the child has been visited */
266  ++(iterator->dfsnvisited[iterator->dfsnexprs-1]);
267 
268  /* do left-most step */
269  while( SCIPexprGetNChildren(child) > 0 )
270  {
271  /* add child to the DFS stack */
272  reverseTopologicalInsert(iterator, child);
273 
274  /* mark that the child has been visited; note that child is on top of the DFS stack */
275  ++(iterator->dfsnvisited[iterator->dfsnexprs-1]);
276 
277  child = SCIPexprGetChildren(child)[0];
278  }
279 
280  /* return last child; NOTE this child is not been added to the stack */
281  return child;
282  }
283 }
284 
285 /** moves to the next expression according to the BFS rule */
286 static
288  SCIP_EXPRITER* iterator /**< expression iterator */
289  )
290 {
291  SCIP_EXPR* expr;
292  int i;
293 
294  assert(iterator != NULL);
295  assert(iterator->itertype == SCIP_EXPRITER_BFS);
296  assert(iterator->queue != NULL);
297 
298  /* no expression left */
299  if( SCIPqueueIsEmpty(iterator->queue) )
300  return NULL;
301 
302  expr = (SCIP_EXPR*) SCIPqueueRemove(iterator->queue);
303  assert(expr != NULL);
304 
305  assert(iterator->visitedtag == 0 || iterator->iterindex >= 0);
306  assert(iterator->visitedtag == 0 || iterator->iterindex < SCIP_EXPRITER_MAXNACTIVE);
307  /* we should have set the visitedtag when adding the expression to the queue */
308  assert(iterator->visitedtag == 0 || expr->iterdata[iterator->iterindex].visitedtag == iterator->visitedtag);
309 
310  /* add all (possibly non-visited) children to the queue */
311  for( i = 0; i < SCIPexprGetNChildren(expr); ++i )
312  {
313  SCIP_EXPR* child = SCIPexprGetChildren(expr)[i];
314  assert(child != NULL);
315 
316  if( iterator->visitedtag != 0 )
317  {
318  assert(iterator->iterindex >= 0);
319  assert(iterator->iterindex < SCIP_EXPRITER_MAXNACTIVE);
320 
321  /* skip children that have already been visited or have already been added to the queue */
322  if( child->iterdata[iterator->iterindex].visitedtag == iterator->visitedtag )
323  continue;
324 
325  /* mark child as being in the queue (will be inserted next) */
326  child->iterdata[iterator->iterindex].visitedtag = iterator->visitedtag;
327  }
328 
329  /* add child to the queue */
330  SCIP_CALL_ABORT( SCIPqueueInsert(iterator->queue, child) );
331  }
332 
333  return expr;
334 }
335 
336 /** moves to the next expression according to the DFS rule */
337 static
339  SCIP_EXPRITER* iterator /**< expression iterator */
340  )
341 {
342  SCIP_EXPRITERDATA* iterdata;
343 
344  assert(iterator != NULL);
345  assert(iterator->itertype == SCIP_EXPRITER_DFS);
346  assert(iterator->iterindex >= 0);
347 
348  if( iterator->curr == NULL )
349  return NULL;
350 
351  iterdata = &iterator->curr->iterdata[iterator->iterindex];
352 
353  switch( iterator->dfsstage )
354  {
356  /* consider next child */
357  ++iterdata->currentchild;
358  /* fall through */ /* no break */ /*lint -fallthrough*/
359 
361  {
362  /* if there is an unvisited child (left), then go into visitingchild stage, otherwise go to leave stage */
363  iterator->dfsstage = SCIP_EXPRITER_LEAVEEXPR; /* expect that we will leave expr, and change mind to visitingchild below */
364  while( iterdata->currentchild < iterator->curr->nchildren )
365  {
366  if( iterator->visitedtag == 0 || iterator->visitedtag != iterator->curr->children[iterdata->currentchild]->iterdata[iterator->iterindex].visitedtag )
367  {
368  /* if visitedtag is not used or child "currentchild" has not been visited yet, then go into visitingchild stage for this child */
370  break;
371  }
372  ++iterdata->currentchild;
373  }
374  /* if leaving expr, then currentchild should be at nchildren */
375  assert(iterator->dfsstage == SCIP_EXPRITER_VISITINGCHILD || iterdata->currentchild == iterator->curr->nchildren);
376  /* if visiting child, then currentchild should be a valid index */
377  assert(iterator->dfsstage == SCIP_EXPRITER_LEAVEEXPR || iterdata->currentchild < iterator->curr->nchildren);
378  /* if visiting child, then either we don't care whether we visited it already or it has not been visited yet */
379  assert(iterator->dfsstage == SCIP_EXPRITER_LEAVEEXPR || iterator->visitedtag == 0
380  || iterator->visitedtag != iterator->curr->children[iterdata->currentchild]->iterdata[iterator->iterindex].visitedtag);
381 
382  return iterator->curr;
383  }
384 
386  {
387  SCIP_EXPR* child;
388 
389  assert(iterdata->currentchild < iterator->curr->nchildren);
390 
391  /* remember the parent and set the first child that should be visited of the new root */
392  child = iterator->curr->children[iterdata->currentchild];
393  child->iterdata[iterator->iterindex].parent = iterator->curr;
394  child->iterdata[iterator->iterindex].currentchild = 0;
395 
396  /* visit child */
397  iterator->dfsstage = SCIP_EXPRITER_ENTEREXPR;
398 
399  return child;
400  }
401 
403  {
404  /* go back to parent expression */
405 
406  /* remember that this expression has been visited */
407  iterdata->visitedtag = iterator->visitedtag;
408 
409  /* be in visitedchild stage for the parent */
411 
412  return iterdata->parent;
413  }
414 
415  default:
416  /* unknown stage */
417  SCIPABORT();
418  return NULL;
419  }
420 }
421 
422 /*
423  * private functions (expr.h)
424  */
425 
426 /** creates an expression iterator */
428  SCIP_STAT* stat, /**< dynamic problem statistics */
429  BMS_BLKMEM* blkmem, /**< block memory */
430  SCIP_EXPRITER** iterator /**< buffer to store expression iterator */
431  )
432 {
433  assert(stat != NULL);
434  assert(blkmem != NULL);
435  assert(iterator != NULL);
436 
437  SCIP_ALLOC( BMSallocClearBlockMemory(blkmem, iterator) );
438 
439  (*iterator)->stat = stat;
440  (*iterator)->blkmem = blkmem;
441 
442  return SCIP_OKAY;
443 }
444 
445 /** frees an expression iterator */
447  SCIP_EXPRITER** iterator /**< pointer to the expression iterator */
448  )
449 {
450  assert(iterator != NULL);
451  assert(*iterator != NULL);
452  assert((*iterator)->blkmem != NULL);
453 
454  deinit(*iterator);
455 
456  assert((*iterator)->queue == NULL);
457  assert((*iterator)->dfsnvisited == NULL);
458  assert((*iterator)->dfsexprs == NULL);
459 
460  /* free iterator */
461  BMSfreeBlockMemory((*iterator)->blkmem, iterator);
462 }
463 
464 /*
465  * public functions (pub_expr.h)
466  */
467 
468 #ifdef NDEBUG
469 #undef SCIPexpriterIsInit
470 #undef SCIPexpriterGetCurrent
471 #undef SCIPexpriterGetStageDFS
472 #undef SCIPexpriterGetChildIdxDFS
473 #undef SCIPexpriterGetChildExprDFS
474 #undef SCIPexpriterGetParentDFS
475 #undef SCIPexpriterGetCurrentUserData
476 #undef SCIPexpriterGetChildUserDataDFS
477 #undef SCIPexpriterGetExprUserData
478 #undef SCIPexpriterSetCurrentUserData
479 #undef SCIPexpriterSetExprUserData
480 #undef SCIPexpriterSetChildUserData
481 #undef SCIPexpriterIsEnd
482 #endif
483 
484 /** returns whether expression iterator is currently initialized */
486  SCIP_EXPRITER* iterator /**< expression iterator */
487  )
488 {
489  assert(iterator != NULL);
490 
491  return iterator->initialized;
492 }
493 
494 /** initializes an expression iterator
495  *
496  * @note If `expr` is NULL, then iterator will be set into ended-state (SCIPexpriterIsEnd() is TRUE). Useful if following with SCIPexpriterRestartDFS().
497  *
498  * If type is DFS, then `stopstages` will be set to \ref SCIP_EXPRITER_ENTEREXPR.
499  * Use `SCIPexpriterSetStagesDFS` to change this.
500  */
502  SCIP_EXPRITER* iterator, /**< expression iterator */
503  SCIP_EXPR* expr, /**< expression of the iterator, can be NULL */
504  SCIP_EXPRITER_TYPE type, /**< type of expression iterator */
505  SCIP_Bool allowrevisit /**< whether expression are allowed to be visited more than once */
506  )
507 {
508  assert(iterator != NULL);
509 
510  deinit(iterator);
511 
512  /* store the new type of the iterator */
513  iterator->itertype = type;
514 
515  /* get iterindex, if necessary */
516  if( !allowrevisit || type == SCIP_EXPRITER_DFS )
517  {
518  if( iterator->stat->nactiveexpriter + 1 >= SCIP_EXPRITER_MAXNACTIVE )
519  {
520  SCIPerrorMessage("Maximal number of active expression iterators reached at subscip-depth %d.\n",
521  iterator->stat->subscipdepth);
522  printBacktraces(iterator->stat->subscipdepth);
523  return SCIP_MAXDEPTHLEVEL;
524  }
525 
526  iterator->iterindex = iterator->stat->nactiveexpriter++;
527 
528  storeBacktrace(iterator->stat->subscipdepth, iterator->iterindex);
529  }
530  else
531  {
532  iterator->iterindex = -1;
533  }
534 
535  /* get new tag to recognize visited expressions */
536  if( !allowrevisit )
537  {
538  iterator->visitedtag = ++iterator->stat->exprlastvisitedtag;
539  }
540  else
541  {
542  iterator->visitedtag = 0L;
543  }
544 
545  switch( iterator->itertype )
546  {
547  case SCIP_EXPRITER_BFS:
548  {
549  SCIP_CALL( SCIPqueueCreate(&iterator->queue, MINBFSSIZE, 2.0) );
550 
551  assert(iterator->queue != NULL);
552  SCIPqueueClear(iterator->queue);
553 
554  if( expr == NULL )
555  {
556  iterator->curr = NULL;
557  break;
558  }
559 
560  SCIP_CALL( SCIPqueueInsert(iterator->queue, expr) );
561 
562  if( iterator->visitedtag != 0 )
563  {
564  assert(iterator->iterindex >= 0);
565  assert(iterator->iterindex < SCIP_EXPRITER_MAXNACTIVE);
566  assert(expr->iterdata[iterator->iterindex].visitedtag != iterator->visitedtag);
567 
568  /* mark expression as being in the queue */
569  expr->iterdata[iterator->iterindex].visitedtag = iterator->visitedtag;
570  }
571 
572  iterator->curr = SCIPexpriterGetNext(iterator);
573  break;
574  }
575 
577  {
578  SCIP_CALL( ensureStackSize(iterator, MINDFSSIZE) );
579 
580  if( expr != NULL )
581  {
582  reverseTopologicalInsert(iterator, expr);
583  iterator->curr = SCIPexpriterGetNext(iterator);
584  }
585  else
586  {
587  iterator->curr = NULL;
588  }
589 
590  break;
591  }
592 
593  case SCIP_EXPRITER_DFS :
594  {
595  assert(iterator->iterindex >= 0);
596 
598  iterator->curr = expr;
599 
600  if( expr == NULL )
601  break;
602 
603  expr->iterdata[iterator->iterindex].currentchild = 0;
604  expr->iterdata[iterator->iterindex].parent = NULL;
605  iterator->dfsstage = SCIP_EXPRITER_ENTEREXPR;
606 
607  break;
608  }
609  }
610 
611  iterator->initialized = TRUE;
612 
613  return SCIP_OKAY;
614 }
615 
616 /** restarts an already initialized expression iterator in DFS mode
617  *
618  * The expression iterator will continue from the given expression, not revisiting expressions that
619  * this iterator has already been visited (if initialized with `allowrevisit=FALSE`) and giving access
620  * to the same iterator specified expression data that may have been set already.
621  * Also the stop-stages are not reset.
622  *
623  * If revisiting is forbidden and given expr has already been visited, then the iterator will behave
624  * as on the end of iteration (SCIPexpriterIsEnd() is TRUE).
625  * If the enterexpr stage is not one of the stop stages, then the iterator will be moved forward
626  * (SCIPexpriterGetNext() is called).
627  *
628  * @return The current expression.
629  */
631  SCIP_EXPRITER* iterator, /**< expression iterator */
632  SCIP_EXPR* expr /**< expression of the iterator */
633  )
634 {
635  assert(iterator != NULL);
636  assert(iterator->initialized);
637  assert(iterator->itertype == SCIP_EXPRITER_DFS);
638 
639  /* if we forbid revisiting and root expr has already been visited, then set curr to NULL, that is, be at end of iterator */
640  if( iterator->visitedtag > 0 && expr->iterdata[iterator->iterindex].visitedtag == iterator->visitedtag )
641  {
642  iterator->curr = NULL;
643  return NULL;
644  }
645 
646  /* set current to given expr, make it the root, and set stage to enterexpr */
647  iterator->curr = expr;
648  expr->iterdata[iterator->iterindex].currentchild = 0;
649  expr->iterdata[iterator->iterindex].parent = NULL;
650  iterator->dfsstage = SCIP_EXPRITER_ENTEREXPR;
651 
652  if( (iterator->stopstages & SCIP_EXPRITER_ENTEREXPR) == 0 )
653  return SCIPexpriterGetNext(iterator);
654 
655  return iterator->curr;
656 }
657 
658 /** specifies in which stages to stop a DFS iterator
659  *
660  * Parameter `stopstages` should be a bitwise OR of different \ref SCIP_EXPRITER_STAGE values
661  *
662  * If the current stage is not one of the `stopstages`, then the iterator will be moved on.
663  */
665  SCIP_EXPRITER* iterator, /**< expression iterator */
666  SCIP_EXPRITER_STAGE stopstages /**< the stages in which to stop when iterating via DFS */
667  )
668 {
669  assert(iterator != NULL);
670 
671  if( (iterator->dfsstage & stopstages) == 0 )
672  {
673  iterator->stopstages = stopstages;
674  (void) SCIPexpriterGetNext(iterator);
675  }
676  else
677  {
678  iterator->stopstages = stopstages;
679  }
680 }
681 
682 /** gets the current expression that the expression iterator points to */
684  SCIP_EXPRITER* iterator /**< expression iterator */
685  )
686 {
687  assert(iterator != NULL);
688 
689  return iterator->curr;
690 }
691 
692 /** gets the current stage that the expression iterator is in when using DFS
693  *
694  * If the iterator has finished (SCIPexpriterIsEnd() is TRUE), then the stage is undefined.
695  */
697  SCIP_EXPRITER* iterator /**< expression iterator */
698  )
699 {
700  assert(iterator != NULL);
701  assert(iterator->itertype == SCIP_EXPRITER_DFS);
702 
703  return iterator->dfsstage;
704 }
705 
706 /** gets the index of the child that the expression iterator considers when in DFS mode and stage \ref SCIP_EXPRITER_VISITINGCHILD or \ref SCIP_EXPRITER_VISITEDCHILD */
708  SCIP_EXPRITER* iterator /**< expression iterator */
709  )
710 {
711  assert(iterator != NULL);
712  assert(iterator->curr != NULL);
713  assert(iterator->iterindex >= 0);
714  assert(iterator->itertype == SCIP_EXPRITER_DFS);
715  assert(iterator->dfsstage == SCIP_EXPRITER_VISITINGCHILD || iterator->dfsstage == SCIP_EXPRITER_VISITEDCHILD);
716 
717  return iterator->curr->iterdata[iterator->iterindex].currentchild;
718 }
719 
720 /** gets the child expression that the expression iterator considers when in DFS mode and stage \ref SCIP_EXPRITER_VISITINGCHILD or \ref SCIP_EXPRITER_VISITEDCHILD */
722  SCIP_EXPRITER* iterator /**< expression iterator */
723  )
724 {
725  assert(iterator != NULL);
726  assert(iterator->curr != NULL);
727  assert(iterator->iterindex >= 0);
728  assert(iterator->itertype == SCIP_EXPRITER_DFS);
729  assert(iterator->dfsstage == SCIP_EXPRITER_VISITINGCHILD || iterator->dfsstage == SCIP_EXPRITER_VISITEDCHILD);
730  assert(iterator->curr->iterdata[iterator->iterindex].currentchild >= 0);
731  assert(iterator->curr->iterdata[iterator->iterindex].currentchild < iterator->curr->nchildren);
732 
733  return iterator->curr->children[iterator->curr->iterdata[iterator->iterindex].currentchild];
734 }
735 
736 /** gives the parent of the current expression of an expression iteration if in DFS mode
737  *
738  * @return the expression from which the current expression has been accessed
739  */
741  SCIP_EXPRITER* iterator /**< expression iterator */
742  )
743 {
744  assert(iterator != NULL);
745  assert(iterator->curr != NULL);
746  assert(iterator->iterindex >= 0);
747  assert(iterator->itertype == SCIP_EXPRITER_DFS);
748 
749  return iterator->curr->iterdata[iterator->iterindex].parent;
750 }
751 
752 /** gives the iterator specific user data of the current expression
753  *
754  * @note The expression iterator mode must be DFS or another mode with allowrevisit=FALSE
755  */
757  SCIP_EXPRITER* iterator /**< expression iterator */
758  )
759 {
760  assert(iterator != NULL);
761  assert(iterator->curr != NULL);
762  assert(iterator->iterindex >= 0);
763 
764  return iterator->curr->iterdata[iterator->iterindex].userdata;
765 }
766 
767 /** gives the iterator specific user data of the current expressions current child
768  *
769  * @note The expression iterator mode must be in DFS mode and stage \ref SCIP_EXPRITER_VISITINGCHILD or \ref SCIP_EXPRITER_VISITEDCHILD
770  */
772  SCIP_EXPRITER* iterator /**< expression iterator */
773  )
774 {
775  assert(iterator != NULL);
776  assert(iterator->curr != NULL);
777  assert(iterator->iterindex >= 0);
778  assert(iterator->itertype == SCIP_EXPRITER_DFS);
779  assert(iterator->dfsstage == SCIP_EXPRITER_VISITINGCHILD || iterator->dfsstage == SCIP_EXPRITER_VISITEDCHILD);
780  assert(iterator->curr->iterdata[iterator->iterindex].currentchild >= 0);
781  assert(iterator->curr->iterdata[iterator->iterindex].currentchild < iterator->curr->nchildren);
782 
783  return iterator->curr->children[iterator->curr->iterdata[iterator->iterindex].currentchild]->iterdata[iterator->iterindex].userdata;
784 }
785 
786 /** gives the iterator specific user data of a given expression
787  *
788  * @note The expression iterator mode must be DFS or another mode with allowrevisit=FALSE
789  */
791  SCIP_EXPRITER* iterator, /**< expression iterator */
792  SCIP_EXPR* expr /**< expression for which to get the userdata of this iterator */
793  )
794 {
795  assert(iterator != NULL);
796  assert(expr != NULL);
797  assert(iterator->iterindex >= 0);
798 
799  return expr->iterdata[iterator->iterindex].userdata;
800 }
801 
802 /** sets the iterator specific user data of the current expression for an expression iteration if in DFS mode
803  *
804  * @note The expression iterator mode must be DFS or another mode with allowrevisit=FALSE
805  */
807  SCIP_EXPRITER* iterator, /**< expression iterator */
808  SCIP_EXPRITER_USERDATA userdata /**< data to be stored */
809  )
810 {
811  assert(iterator != NULL);
812  assert(iterator->curr != NULL);
813  assert(iterator->iterindex >= 0);
814 
815  iterator->curr->iterdata[iterator->iterindex].userdata = userdata;
816 }
817 
818 /** sets the iterator specific user data of a given expression
819  *
820  * @note The expression iterator mode must be DFS or another mode with allowrevisit=FALSE
821  */
823  SCIP_EXPRITER* iterator, /**< expression iterator */
824  SCIP_EXPR* expr, /**< expression where to set iterator data */
825  SCIP_EXPRITER_USERDATA userdata /**< data to be stored in current child */
826  )
827 {
828  assert(iterator != NULL);
829  assert(iterator->iterindex >= 0);
830 
831  expr->iterdata[iterator->iterindex].userdata = userdata;
832 }
833 
834 /** sets the iterator specific user data of the current expressions current child
835  *
836  * @note The expression iterator mode must be in DFS mode and stage \ref SCIP_EXPRITER_VISITINGCHILD or \ref SCIP_EXPRITER_VISITEDCHILD
837  */
839  SCIP_EXPRITER* iterator, /**< expression iterator */
840  SCIP_EXPRITER_USERDATA userdata /**< data to be stored in current child */
841  )
842 {
843  assert(iterator != NULL);
844  assert(iterator->curr != NULL);
845  assert(iterator->iterindex >= 0);
846  assert(iterator->itertype == SCIP_EXPRITER_DFS);
847  assert(iterator->dfsstage == SCIP_EXPRITER_VISITINGCHILD || iterator->dfsstage == SCIP_EXPRITER_VISITEDCHILD);
848  assert(iterator->curr->iterdata[iterator->iterindex].currentchild >= 0);
849  assert(iterator->curr->iterdata[iterator->iterindex].currentchild < iterator->curr->nchildren);
850 
851  iterator->curr->children[iterator->curr->iterdata[iterator->iterindex].currentchild]->iterdata[iterator->iterindex].userdata = userdata;
852 }
853 
854 /** moves the iterator to the next expression according to the mode of the expression iterator
855  *
856  * @return the next expression, if any, and NULL otherwise
857  */
859  SCIP_EXPRITER* iterator /**< expression iterator */
860  )
861 {
862  /* move to the next expression according to iterator type */
863  switch( iterator->itertype )
864  {
865  case SCIP_EXPRITER_BFS:
866  {
867  iterator->curr = doBfsNext(iterator);
868  break;
869  }
870 
872  {
873  iterator->curr = doReverseTopologicalNext(iterator);
874  if( iterator->visitedtag != 0 )
875  {
876  assert(iterator->iterindex >= 0);
877  assert(iterator->iterindex < SCIP_EXPRITER_MAXNACTIVE);
878 
879  /* skip already visited expressions */
880  while( iterator->curr != NULL )
881  {
882  if( iterator->curr->iterdata[iterator->iterindex].visitedtag == iterator->visitedtag )
883  {
884  /* if curr has already been visited, get next one
885  * TODO this isn't really efficient, since we still walk through already visited expressions
886  */
887  iterator->curr = doReverseTopologicalNext(iterator);
888  }
889  else
890  {
891  /* curr has not been visited yet, so mark it as visited and interrupt loop */
892  iterator->curr->iterdata[iterator->iterindex].visitedtag = iterator->visitedtag;
893  break;
894  }
895  }
896  }
897  break;
898  }
899 
900  case SCIP_EXPRITER_DFS :
901  {
902  assert(iterator->iterindex >= 0);
903 
904  /* get next until we are in a stopstage again
905  * this might give expressions more than once, depending on what the stopstages are
906  */
907  do
908  {
909  iterator->curr = doDfsNext(iterator);
910  }
911  while( iterator->curr != NULL && (iterator->dfsstage & iterator->stopstages) == 0 );
912 
913  break;
914  }
915  }
916 
917  return iterator->curr;
918 }
919 
920 /** moves a DFS iterator to one of the next expressions
921  *
922  * - If in \ref SCIP_EXPRITER_ENTEREXPR stage, then all children of that expression will be skipped.
923  * If \ref SCIP_EXPRITER_LEAVEEXPR is one of the `stopstages`, then it will be the next stage. Otherwise, the iterator will move further on (go to the parent, etc).
924  * - If in \ref SCIP_EXPRITER_VISITINGCHILD stage, then the child that was going to be visited next will be skipped and the iterator will be moved on to the next child (if any).
925  * - If in \ref SCIP_EXPRITER_VISITEDCHILD stage, then all remaining children will be skipped and we move on to the \ref SCIP_EXPRITER_LEAVEEXPR stage (if a stop stage, otherwise further on).
926  * - It is not allowed to call this function when in \ref SCIP_EXPRITER_LEAVEEXPR stage.
927  *
928  * @return the next expression, if any, and NULL otherwise
929  */
931  SCIP_EXPRITER* iterator /**< expression iterator */
932  )
933 {
934  assert(iterator != NULL);
935  assert(iterator->curr != NULL);
936  assert(iterator->itertype == SCIP_EXPRITER_DFS);
937  assert(iterator->iterindex >= 0);
938 
939  switch( iterator->dfsstage )
940  {
943  {
944  /* move directly to leaveexpr */
945  iterator->dfsstage = SCIP_EXPRITER_LEAVEEXPR;
946  /* if leaveexpr is not a stopstage, then move on */
947  while( iterator->curr != NULL && (iterator->dfsstage & iterator->stopstages) == 0 )
948  iterator->curr = doDfsNext(iterator);
949  return iterator->curr;
950  }
951 
953  {
954  /* skip the child to be visited */
955  /* pretend we just visited this child and get next */
957  return SCIPexpriterGetNext(iterator);
958  }
959 
961  default :
962  SCIPerrorMessage("SCIPexpriterSkipDFS called in invalid stage %u", iterator->dfsstage);
963  SCIPABORT();
964  return iterator->curr;
965  }
966 }
967 
968 /** returns whether the iterator visited all expressions already */
970  SCIP_EXPRITER* iterator /**< expression iterator */
971  )
972 {
973  assert(iterator != NULL);
974 
975  return iterator->curr == NULL;
976 }
#define NULL
Definition: def.h:267
SCIP_RETCODE SCIPexpriterInit(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
Definition: expriter.c:501
static void deinit(SCIP_EXPRITER *iterator)
Definition: expriter.c:144
SCIP_Bool initialized
Definition: struct_expr.h:208
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition: expr.c:3854
SCIP_EXPR * SCIPexpriterGetParentDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:740
static SCIP_EXPR * doDfsNext(SCIP_EXPRITER *iterator)
Definition: expriter.c:338
static void reverseTopologicalInsert(SCIP_EXPRITER *iterator, SCIP_EXPR *expr)
Definition: expriter.c:219
int nactiveexpriter
Definition: struct_stat.h:276
SCIP_EXPR * SCIPexpriterSkipDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:930
SCIP_RETCODE SCIPqueueInsert(SCIP_QUEUE *queue, void *elem)
Definition: misc.c:1079
structure definitions related to algebraic expressions
private functions to work with algebraic expressions
BMS_BLKMEM * blkmem
Definition: struct_expr.h:205
#define TRUE
Definition: def.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_EXPRITER_TYPE
Definition: type_expr.h:712
void SCIPexpriterSetChildUserData(SCIP_EXPRITER *iterator, SCIP_EXPRITER_USERDATA userdata)
Definition: expriter.c:838
SCIP_Bool SCIPexpriterIsInit(SCIP_EXPRITER *iterator)
Definition: expriter.c:485
static SCIP_EXPR * doBfsNext(SCIP_EXPRITER *iterator)
Definition: expriter.c:287
SCIP_EXPRITER_USERDATA SCIPexpriterGetChildUserDataDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:771
static SCIP_RETCODE ensureStackSize(SCIP_EXPRITER *iterator, int size)
Definition: expriter.c:195
SCIP_Bool SCIPqueueIsEmpty(SCIP_QUEUE *queue)
Definition: misc.c:1234
SCIP_EXPRITER_USERDATA SCIPexpriterGetCurrentUserData(SCIP_EXPRITER *iterator)
Definition: expriter.c:756
#define SCIP_EXPRITER_ENTEREXPR
Definition: type_expr.h:692
#define SCIP_EXPRITER_VISITEDCHILD
Definition: type_expr.h:694
SCIP_EXPR * SCIPexpriterGetCurrent(SCIP_EXPRITER *iterator)
Definition: expriter.c:683
int nchildren
Definition: struct_expr.h:110
void SCIPqueueClear(SCIP_QUEUE *queue)
Definition: misc.c:1028
SCIP_EXPRITER_USERDATA SCIPexpriterGetExprUserData(SCIP_EXPRITER *iterator, SCIP_EXPR *expr)
Definition: expriter.c:790
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
Definition: expr.c:3864
void SCIPexpriterFree(SCIP_EXPRITER **iterator)
Definition: expriter.c:446
int * dfsnvisited
Definition: struct_expr.h:216
#define storeBacktrace(subscipdepth, iterpos)
Definition: expriter.c:130
#define SCIPerrorMessage
Definition: pub_message.h:64
SCIP_Longint visitedtag
Definition: struct_expr.h:212
#define SCIP_CALL(x)
Definition: def.h:380
int SCIPexpriterGetChildIdxDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:707
struct SCIP_ExprIterData SCIP_EXPRITERDATA
Definition: type_expr.h:719
SCIP_EXPRITER_TYPE itertype
Definition: struct_expr.h:209
void SCIPqueueFree(SCIP_QUEUE **queue)
Definition: misc.c:1017
SCIP_EXPR ** dfsexprs
Definition: struct_expr.h:215
#define BMSfreeBlockMemory(mem, ptr)
Definition: memory.h:465
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:91
SCIP_EXPR * SCIPexpriterRestartDFS(SCIP_EXPRITER *iterator, SCIP_EXPR *expr)
Definition: expriter.c:630
SCIP_RETCODE SCIPexpriterCreate(SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_EXPRITER **iterator)
Definition: expriter.c:427
static void printBacktraces(int subscipdepth)
Definition: expriter.c:134
void SCIPexpriterSetExprUserData(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_USERDATA userdata)
Definition: expriter.c:822
SCIP_QUEUE * queue
Definition: struct_expr.h:221
#define BMSfreeBlockMemoryArray(mem, ptr, num)
Definition: memory.h:467
SCIP_EXPRITER_STAGE dfsstage
Definition: struct_expr.h:224
SCIP_EXPR ** children
Definition: struct_expr.h:112
SCIP_EXPR * curr
Definition: struct_expr.h:210
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
Definition: expriter.c:858
SCIP_EXPR * SCIPexpriterGetChildExprDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:721
datastructures for problem statistics
void SCIPexpriterSetStagesDFS(SCIP_EXPRITER *iterator, SCIP_EXPRITER_STAGE stopstages)
Definition: expriter.c:664
#define SCIP_EXPRITER_MAXNACTIVE
Definition: type_expr.h:689
SCIP_RETCODE SCIPqueueCreate(SCIP_QUEUE **queue, int initsize, SCIP_Real sizefac)
Definition: misc.c:993
#define MINDFSSIZE
Definition: expriter.c:45
SCIP_EXPRITER_STAGE SCIPexpriterGetStageDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:696
void SCIPexpriterSetCurrentUserData(SCIP_EXPRITER *iterator, SCIP_EXPRITER_USERDATA userdata)
Definition: expriter.c:806
public methods for message output
static SCIP_EXPR * doReverseTopologicalNext(SCIP_EXPRITER *iterator)
Definition: expriter.c:235
SCIP_STAT * stat
Definition: struct_expr.h:206
SCIP_Longint exprlastvisitedtag
Definition: struct_stat.h:126
void * SCIPqueueRemove(SCIP_QUEUE *queue)
Definition: misc.c:1130
unsigned int stopstages
Definition: struct_expr.h:225
#define SCIP_EXPRITER_LEAVEEXPR
Definition: type_expr.h:695
unsigned int SCIP_EXPRITER_STAGE
Definition: type_expr.h:699
#define SCIP_EXPRITER_VISITINGCHILD
Definition: type_expr.h:693
#define MINBFSSIZE
Definition: expriter.c:46
SCIP_Bool SCIPexpriterIsEnd(SCIP_EXPRITER *iterator)
Definition: expriter.c:969
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:437
#define SCIP_CALL_ABORT(x)
Definition: def.h:359
SCIP_EXPRITERDATA iterdata[SCIP_EXPRITER_MAXNACTIVE]
Definition: struct_expr.h:115
#define SCIP_ALLOC(x)
Definition: def.h:391
#define BMSallocClearBlockMemory(mem, ptr)
Definition: memory.h:452
#define SCIPABORT()
Definition: def.h:352
#define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum)
Definition: memory.h:458
int subscipdepth
Definition: struct_stat.h:217