SCIP
Solving Constraint Integer Programs
scip_expr.c File Reference
Detailed Description
public functions to work with algebraic expressions
Definition in file scip_expr.c.
#include <string.h>#include <ctype.h>#include "scip/scip_expr.h"#include "scip/expr.h"#include "scip/set.h"#include "scip/misc.h"#include "scip/scip_copy.h"#include "scip/scip_mem.h"#include "scip/scip_message.h"#include "scip/scip_prob.h"#include "scip/scip_var.h"#include "scip/scip_sol.h"#include "scip/pub_var.h"#include "scip/struct_scip.h"#include "scip/struct_mem.h"#include "scip/struct_stat.h"#include "scip/expr_value.h"#include "scip/expr_var.h"#include "scip/expr_sum.h"#include "scip/expr_product.h"#include "scip/expr_pow.h"Go to the source code of this file.
Data Structures | |
| struct | COPY_MAPEXPR_DATA |
| struct | COMMONSUBEXPR_HASH_DATA |
Parsing methods (internal) | |
Here is an attempt at defining the grammar of an expression. We use upper case names for variables (in the grammar sense) and terminals are between "". Loosely speaking, a Base will be any "block", a Factor is a Base to a power, a Term is a product of Factors and an Expression is a sum of terms. The actual definition:
Expression -> ["+" | "-"] Term { ("+" | "-" | "number *") ] Term }
Term -> Factor { ("*" | "/" ) Factor }
Factor -> Base [ "^" "number" | "^(" "number" ")" ]
Base -> "number" | "<varname>" | "(" Expression ")" | Op "(" OpExpression ")
</pre>
where [a|b] means a or b or none, (a|b) means a or b, {a} means 0 or more a.
Note that Op and OpExpression are undefined. Op corresponds to the name of an expression handler and
OpExpression to whatever string the expression handler accepts (through its parse method).
parse(Expr|Term|Base) returns an SCIP_EXPR
\xrefitem todo 262.<pre> Term -> Factor { ("*" | "/" | "^") Factor } | |
| #define | debugParse while( FALSE ) printf |
| static SCIP_RETCODE | parseExpr (SCIP *scip, SCIP_HASHMAP *vartoexprvarmap, const char *expr, const char **newpos, SCIP_EXPR **exprtree, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata) |
| static SCIP_RETCODE | parseBase (SCIP *scip, SCIP_HASHMAP *vartoexprvarmap, const char *expr, const char **newpos, SCIP_EXPR **basetree, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata) |
| static SCIP_RETCODE | parseFactor (SCIP *scip, SCIP_Bool isdenominator, SCIP_HASHMAP *vartoexprvarmap, const char *expr, const char **newpos, SCIP_EXPR **factortree, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata) |
| static SCIP_RETCODE | parseTerm (SCIP *scip, SCIP_HASHMAP *vartoexprvarmap, const char *expr, const char **newpos, SCIP_EXPR **termtree, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata) |
Macro Definition Documentation
◆ debugParse
| #define debugParse while( FALSE ) printf |
Definition at line 144 of file scip_expr.c.
Function Documentation
◆ SCIP_DECL_EXPR_MAPEXPR()
|
static |
variable expression mapping callback to call when copying expressions (within same or different SCIPs)
Definition at line 81 of file scip_expr.c.
References COPY_MAPEXPR_DATA::consmap, FALSE, COPY_MAPEXPR_DATA::global, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcreateExprVar(), SCIPgetVarCopy(), SCIPgetVarExprVar(), SCIPisExprVar(), COPY_MAPEXPR_DATA::valid, and COPY_MAPEXPR_DATA::varmap.
◆ parseExpr()
|
static |
parses an expression and builds a sum-expression with children
Expression -> ["+" | "-"] Term { ("+" | "-" | "number *") ] Term }
- Parameters
-
scip SCIP data structure vartoexprvarmap hashmap to map between scip vars and var expressions expr expr that we are parsing newpos buffer to store the position of expr where we finished reading exprtree buffer to store the expr parsed by Expr ownercreatedata data to pass to ownercreate
Definition at line 529 of file scip_expr.c.
References debugParse, NULL, parseTerm(), SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_READERROR, SCIP_Real, SCIPappendExprSumExpr(), SCIPcreateExprSum(), SCIPerrorMessage, SCIPexprIsValue(), SCIPgetValueExprValue(), SCIPisFinite, SCIPisInfinity(), SCIPreleaseExpr(), SCIPskipSpace(), and SCIPstrToRealValue().
Referenced by parseBase(), and SCIPparseExpr().
◆ parseBase()
|
static |
Parses base to build a value, variable, sum, or function-like ("func(...)") expression.
Base -> "number" | "<varname>" | "(" Expression ")" | Op "(" OpExpression ")
- Parameters
-
scip SCIP data structure vartoexprvarmap hashmap to map between SCIP vars and var expressions expr expr that we are parsing newpos buffer to store the position of expr where we finished reading basetree buffer to store the expr parsed by Base ownercreatedata data to pass to ownercreate
Definition at line 165 of file scip_expr.c.
References debugParse, NULL, parseExpr(), SCIP_Bool, SCIP_CALL, SCIP_INVALIDDATA, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_READERROR, SCIP_Real, SCIP_SPACECONTROL, SCIPcreateExprValue(), SCIPcreateExprVar(), SCIPerrorMessage, SCIPexprCapture(), SCIPexprhdlrParseExpr(), SCIPfindExprhdlr(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPisFinite, SCIPisInfinity(), SCIPparseVarName(), SCIPreleaseExpr(), SCIPskipSpace(), SCIPstrToRealValue(), and SCIPvarGetName().
Referenced by parseFactor().
◆ parseFactor()
|
static |
Parses a factor and builds a product-expression if there is an exponent, otherwise returns the base expression.
Factor -> Base [ "^" "number" | "^(" "number" ")" ]
- Parameters
-
scip SCIP data structure isdenominator whether factor is in the denominator vartoexprvarmap hashmap to map between scip vars and var expressions expr expr that we are parsing newpos buffer to store the position of expr where we finished reading factortree buffer to store the expr parsed by Factor ownercreatedata data to pass to ownercreate
Definition at line 322 of file scip_expr.c.
References debugParse, parseBase(), SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_READERROR, SCIP_Real, SCIPcreateExprPow(), SCIPerrorMessage, SCIPisFinite, SCIPisInfinity(), SCIPreleaseExpr(), SCIPskipSpace(), and SCIPstrToRealValue().
Referenced by parseTerm().
◆ parseTerm()
|
static |
Parses a term and builds a product-expression, where each factor is a child.
Term -> Factor { ("*" | "/" ) Factor }
- Parameters
-
scip SCIP data structure vartoexprvarmap hashmap to map between scip vars and var expressions expr expr that we are parsing newpos buffer to store the position of expr where we finished reading termtree buffer to store the expr parsed by Term ownercreatedata data to pass to ownercreate
Definition at line 450 of file scip_expr.c.
References debugParse, FALSE, parseFactor(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_READERROR, SCIPappendExprChild(), SCIPcreateExprProduct(), SCIPreleaseExpr(), SCIPskipSpace(), and TRUE.
Referenced by parseExpr().
◆ findEqualExpr()
|
static |
returns an equivalent expression for a given expression if possible
it adds the expression to key2expr if the map does not contain the key
- Parameters
-
set global SCIP settings expr expression to replace key2expr mapping of hashes to expressions newexpr pointer to store an equivalent expression (NULL if there is none)
Definition at line 674 of file scip_expr.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPexprCompare(), SCIPmultihashInsert(), SCIPmultihashRetrieveNext(), and TRUE.
Referenced by SCIPreplaceCommonSubexpressions().
◆ SCIP_DECL_HASHGETKEY()
|
static |
get key of hash element
Definition at line 728 of file scip_expr.c.
◆ SCIP_DECL_HASHKEYEQ()
|
static |
checks if two expressions are structurally the same
Definition at line 735 of file scip_expr.c.
References NULL, SCIPexprCompare(), and COMMONSUBEXPR_HASH_DATA::set.
◆ SCIP_DECL_HASHKEYVAL()
|
static |
get value of hash element when comparing with another expression
Definition at line 754 of file scip_expr.c.
References COMMONSUBEXPR_HASH_DATA::hashiterator, NULL, SCIPexpriterGetExprUserData(), and SCIP_EXPRITER_USERDATA::uintval.
◆ hashExpr()
|
static |
hashes an expression using an already existing iterator
The iterator must by of type DFS with allowrevisit=FALSE and only the leaveexpr stage enabled. The hashes of all visited expressions will be stored in the iterators expression data.
- Parameters
-
set global SCIP settings bufmem buffer memory expr expression to hash hashiterator iterator to use for hashing nvisitedexprs counter to increment by the number of expressions visited, or NULL
Definition at line 774 of file scip_expr.c.
References BMSallocBufferMemoryArray, BMSfreeBufferMemoryArray, BMSreallocBufferMemoryArray, NULL, SCIP_ALLOC, SCIP_CALL, SCIP_EXPRITER_LEAVEEXPR, SCIP_OKAY, SCIPexprGetChildren(), SCIPexprGetHdlr(), SCIPexprGetNChildren(), SCIPexprhdlrHashExpr(), SCIPexpriterGetExprUserData(), SCIPexpriterGetNext(), SCIPexpriterGetStageDFS(), SCIPexpriterIsEnd(), SCIPexpriterRestartDFS(), SCIPexpriterSetCurrentUserData(), SCIPsetCalcMemGrowSize(), and SCIP_EXPRITER_USERDATA::uintval.
Referenced by SCIPhashExpr(), and SCIPreplaceCommonSubexpressions().