SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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 */
62#endif
63
64/*
65 * local functions
66 */
67
68#ifdef SCIP_DEBUG_EXPRITER
69/** obtain current backtrace and store it in iterinitbacktrace */
70static
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);
84
85 if( subscipdepth > MAXSUBSCIPDEPTH )
86 return;
87
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
103static
104void 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}*/
132static
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
142static
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 */
193static
195 SCIP_EXPRITER* iterator, /**< expression iterator */
196 int size /**< minimum requires size */
197 )
198{
199 assert(iterator != NULL);
200 assert(iterator->blkmem != NULL);
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 */
217static
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 */
233static
235 SCIP_EXPRITER* iterator /**< expression iterator */
236 )
237{
238 SCIP_EXPR* expr;
239 int childidx;
240
241 assert(iterator != NULL);
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 */
285static
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);
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 */
336static
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 */
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);
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 {
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);
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 {
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;
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;
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);
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);
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);
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);
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 {
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);
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 */
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}
#define SCIP_ALLOC(x)
Definition def.h:399
#define TRUE
Definition def.h:95
#define SCIP_CALL_ABORT(x)
Definition def.h:367
#define SCIPABORT()
Definition def.h:360
#define SCIP_CALL(x)
Definition def.h:388
private functions to work with algebraic expressions
static SCIP_EXPR * doBfsNext(SCIP_EXPRITER *iterator)
Definition expriter.c:286
static SCIP_EXPR * doDfsNext(SCIP_EXPRITER *iterator)
Definition expriter.c:337
#define storeBacktrace(subscipdepth, iterpos)
Definition expriter.c:129
static void printBacktraces(int subscipdepth)
Definition expriter.c:133
static SCIP_RETCODE ensureStackSize(SCIP_EXPRITER *iterator, int size)
Definition expriter.c:194
#define MINBFSSIZE
Definition expriter.c:45
static void deinit(SCIP_EXPRITER *iterator)
Definition expriter.c:143
void SCIPexpriterFree(SCIP_EXPRITER **iterator)
Definition expriter.c:445
static void reverseTopologicalInsert(SCIP_EXPRITER *iterator, SCIP_EXPR *expr)
Definition expriter.c:218
#define MINDFSSIZE
Definition expriter.c:44
static SCIP_EXPR * doReverseTopologicalNext(SCIP_EXPRITER *iterator)
Definition expriter.c:234
SCIP_RETCODE SCIPexpriterCreate(SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_EXPRITER **iterator)
Definition expriter.c:426
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition expr.c:3801
SCIP_Bool SCIPexpriterIsEnd(SCIP_EXPRITER *iterator)
Definition expriter.c:968
SCIP_EXPR * SCIPexpriterSkipDFS(SCIP_EXPRITER *iterator)
Definition expriter.c:929
SCIP_EXPRITER_USERDATA SCIPexpriterGetCurrentUserData(SCIP_EXPRITER *iterator)
Definition expriter.c:755
void SCIPexpriterSetExprUserData(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_USERDATA userdata)
Definition expriter.c:821
SCIP_EXPR * SCIPexpriterGetCurrent(SCIP_EXPRITER *iterator)
Definition expriter.c:682
void SCIPexpriterSetStagesDFS(SCIP_EXPRITER *iterator, SCIP_EXPRITER_STAGE stopstages)
Definition expriter.c:663
SCIP_Bool SCIPexpriterIsInit(SCIP_EXPRITER *iterator)
Definition expriter.c:484
SCIP_EXPR * SCIPexpriterRestartDFS(SCIP_EXPRITER *iterator, SCIP_EXPR *expr)
Definition expriter.c:629
SCIP_EXPR * SCIPexpriterGetParentDFS(SCIP_EXPRITER *iterator)
Definition expriter.c:739
void SCIPexpriterSetCurrentUserData(SCIP_EXPRITER *iterator, SCIP_EXPRITER_USERDATA userdata)
Definition expriter.c:805
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
Definition expriter.c:857
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
Definition expr.c:3811
void SCIPexpriterSetChildUserData(SCIP_EXPRITER *iterator, SCIP_EXPRITER_USERDATA userdata)
Definition expriter.c:837
int SCIPexpriterGetChildIdxDFS(SCIP_EXPRITER *iterator)
Definition expriter.c:706
SCIP_EXPRITER_USERDATA SCIPexpriterGetChildUserDataDFS(SCIP_EXPRITER *iterator)
Definition expriter.c:770
SCIP_EXPRITER_STAGE SCIPexpriterGetStageDFS(SCIP_EXPRITER *iterator)
Definition expriter.c:695
SCIP_RETCODE SCIPexpriterInit(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
Definition expriter.c:500
SCIP_EXPRITER_USERDATA SCIPexpriterGetExprUserData(SCIP_EXPRITER *iterator, SCIP_EXPR *expr)
Definition expriter.c:789
SCIP_EXPR * SCIPexpriterGetChildExprDFS(SCIP_EXPRITER *iterator)
Definition expriter.c:720
void SCIPqueueFree(SCIP_QUEUE **queue)
Definition misc.c:967
SCIP_RETCODE SCIPqueueCreate(SCIP_QUEUE **queue, int initsize, SCIP_Real sizefac)
Definition misc.c:943
void SCIPqueueClear(SCIP_QUEUE *queue)
Definition misc.c:978
SCIP_RETCODE SCIPqueueInsert(SCIP_QUEUE *queue, void *elem)
Definition misc.c:1029
SCIP_Bool SCIPqueueIsEmpty(SCIP_QUEUE *queue)
Definition misc.c:1184
void * SCIPqueueRemove(SCIP_QUEUE *queue)
Definition misc.c:1080
return SCIP_OKAY
assert(minobj< SCIPgetCutoffbound(scip))
#define NULL
Definition lpi_spx1.cpp:161
#define BMSfreeBlockMemory(mem, ptr)
Definition memory.h:467
#define BMSfreeBlockMemoryArray(mem, ptr, num)
Definition memory.h:469
#define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum)
Definition memory.h:460
#define BMSallocClearBlockMemory(mem, ptr)
Definition memory.h:454
struct BMS_BlkMem BMS_BLKMEM
Definition memory.h:439
#define SCIPerrorMessage
Definition pub_message.h:64
public data structures and miscellaneous methods
SCIP_EXPRITER_TYPE itertype
SCIP_EXPRITER_STAGE dfsstage
SCIP_QUEUE * queue
BMS_BLKMEM * blkmem
SCIP_Bool initialized
SCIP_EXPR ** dfsexprs
SCIP_STAT * stat
SCIP_Longint visitedtag
SCIP_EXPR * curr
unsigned int stopstages
SCIP_EXPRITERDATA iterdata[SCIP_EXPRITER_MAXNACTIVE]
SCIP_EXPR ** children
SCIP_Longint exprlastvisitedtag
int nactiveexpriter
int subscipdepth
structure definitions related to algebraic expressions
datastructures for problem statistics
#define SCIP_EXPRITER_MAXNACTIVE
Definition type_expr.h:673
struct SCIP_ExprIterData SCIP_EXPRITERDATA
Definition type_expr.h:703
#define SCIP_EXPRITER_VISITINGCHILD
Definition type_expr.h:677
SCIP_EXPRITER_TYPE
Definition type_expr.h:697
@ SCIP_EXPRITER_BFS
Definition type_expr.h:699
@ SCIP_EXPRITER_DFS
Definition type_expr.h:700
@ SCIP_EXPRITER_RTOPOLOGIC
Definition type_expr.h:698
#define SCIP_EXPRITER_VISITEDCHILD
Definition type_expr.h:678
#define SCIP_EXPRITER_LEAVEEXPR
Definition type_expr.h:679
#define SCIP_EXPRITER_ENTEREXPR
Definition type_expr.h:676
unsigned int SCIP_EXPRITER_STAGE
Definition type_expr.h:683
@ SCIP_MAXDEPTHLEVEL
enum SCIP_Retcode SCIP_RETCODE