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 ") 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 | |
#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) |
Definition at line 144 of file scip_expr.c.
Referenced by parseBase(), parseExpr(), parseFactor(), and parseTerm().
|
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 assert(), COPY_MAPEXPR_DATA::consmap, FALSE, COPY_MAPEXPR_DATA::global, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcreateExprVar(), SCIPgetVarCopy(), SCIPgetVarExprVar(), SCIPisExprVar(), COPY_MAPEXPR_DATA::valid, valid, and COPY_MAPEXPR_DATA::varmap.
|
static |
parses an expression and builds a sum-expression with children
Expression -> ["+" | "-"] Term { ("+" | "-" | "number *") ] Term }
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 517 of file scip_expr.c.
References assert(), debugParse, NULL, parseTerm(), SCIP_CALL, SCIP_OKAY, SCIP_READERROR, SCIP_Real, SCIPappendExprSumExpr(), SCIPcreateExprSum(), SCIPexprIsValue(), SCIPgetValueExprValue(), SCIPreleaseExpr(), SCIPskipSpace(), and SCIPstrToRealValue().
Referenced by parseBase(), and SCIPparseExpr().
|
static |
Parses base to build a value, variable, sum, or function-like ("func(...)") expression.
Base -> "number" | "<varname>" | "(" Expression ")" | Op "(" OpExpression ")
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 assert(), debugParse, i, NULL, parseExpr(), SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_READERROR, SCIP_Real, SCIP_SPACECONTROL, SCIPcreateExprValue(), SCIPcreateExprVar(), SCIPerrorMessage, SCIPexprCapture(), SCIPexprhdlrParseExpr(), SCIPfindExprhdlr(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPparseVarName(), SCIPreleaseExpr(), SCIPskipSpace(), SCIPstrToRealValue(), SCIPvarGetName(), and var.
Referenced by parseFactor().
|
static |
Parses a factor and builds a product-expression if there is an exponent, otherwise returns the base expression.
Factor -> Base [ "^" "number" | "^(" "number" ")" ]
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 317 of file scip_expr.c.
References debugParse, parseBase(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_READERROR, SCIP_Real, SCIPcreateExprPow(), SCIPerrorMessage, SCIPreleaseExpr(), SCIPskipSpace(), and SCIPstrToRealValue().
Referenced by parseTerm().
|
static |
Parses a term and builds a product-expression, where each factor is a child.
Term -> Factor { ("*" | "/" ) Factor }
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 438 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().
|
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
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 655 of file scip_expr.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPexprCompare(), SCIPmultihashInsert(), SCIPmultihashRetrieveNext(), and TRUE.
Referenced by SCIPreplaceCommonSubexpressions().
|
static |
get key of hash element
Definition at line 709 of file scip_expr.c.
|
static |
checks if two expressions are structurally the same
Definition at line 716 of file scip_expr.c.
References assert(), NULL, SCIPexprCompare(), and COMMONSUBEXPR_HASH_DATA::set.
|
static |
get value of hash element when comparing with another expression
Definition at line 735 of file scip_expr.c.
References assert(), COMMONSUBEXPR_HASH_DATA::hashiterator, NULL, SCIPexpriterGetExprUserData(), and SCIP_EXPRITER_USERDATA::uintval.
|
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.
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 755 of file scip_expr.c.
References assert(), BMSallocBufferMemoryArray, BMSfreeBufferMemoryArray, BMSreallocBufferMemoryArray, i, 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().