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