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 pub_misc.h 26 * @ingroup PUBLICCOREAPI 27 * @brief public data structures and miscellaneous methods 28 * @author Tobias Achterberg 29 * @author Gerald Gamrath 30 * @author Stefan Heinz 31 * @author Gregor Hendel 32 * @author Michael Winkler 33 * @author Kati Wolter 34 * 35 * This file contains a bunch of data structures and miscellaneous methods: 36 * 37 * - \ref DataStructures "Data structures" 38 * - \ref MiscellaneousMethods "Miscellaneous Methods" 39 */ 40 41 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 42 43 #ifndef __SCIP_PUB_MISC_H__ 44 #define __SCIP_PUB_MISC_H__ 45 46 /* on SunOS, the function finite(a) (for the SCIPisFinite macro below) is declared in ieeefp.h */ 47 #ifdef __sun 48 #include <ieeefp.h> 49 #endif 50 #include <math.h> 51 52 #include "scip/def.h" 53 #include "blockmemshell/memory.h" 54 #include "scip/type_retcode.h" 55 #include "scip/type_misc.h" 56 #include "scip/type_message.h" 57 #include "scip/type_var.h" 58 #include "scip/pub_misc_select.h" 59 #include "scip/pub_misc_sort.h" 60 #include "scip/pub_misc_linear.h" 61 #include "scip/pub_misc_rowprep.h" 62 63 /* in optimized mode some of the function are handled via defines, for that the structs are needed */ 64 #ifdef NDEBUG 65 #include "scip/struct_misc.h" 66 #endif 67 68 #ifdef __cplusplus 69 extern "C" { 70 #endif 71 72 /* 73 * methods for statistical tests 74 */ 75 76 /**@defgroup STATISTICALTESTS Statistical tests 77 * @ingroup MiscellaneousMethods 78 * @brief public methods for statistical tests 79 * 80 * Below are the public methods for statistical tests inside of \SCIP 81 * 82 * @{ 83 */ 84 85 /** get critical value of a Student-T distribution for a given number of degrees of freedom at a confidence level */ 86 SCIP_EXPORT 87 SCIP_Real SCIPstudentTGetCriticalValue( 88 SCIP_CONFIDENCELEVEL clevel, /**< (one-sided) confidence level */ 89 int df /**< degrees of freedom */ 90 ); 91 92 /** compute a t-value for the hypothesis that x and y are from the same population; Assuming that 93 * x and y represent normally distributed random samples with equal variance, the returned value 94 * comes from a Student-T distribution with countx + county - 2 degrees of freedom; this 95 * value can be compared with a critical value (see also SCIPstudentTGetCriticalValue()) at 96 * a predefined confidence level for checking if x and y significantly differ in location 97 */ 98 SCIP_EXPORT 99 SCIP_Real SCIPcomputeTwoSampleTTestValue( 100 SCIP_Real meanx, /**< the mean of the first distribution */ 101 SCIP_Real meany, /**< the mean of the second distribution */ 102 SCIP_Real variancex, /**< the variance of the x-distribution */ 103 SCIP_Real variancey, /**< the variance of the y-distribution */ 104 SCIP_Real countx, /**< number of samples of x */ 105 SCIP_Real county /**< number of samples of y */ 106 ); 107 108 /** returns the value of the Gauss error function evaluated at a given point */ 109 SCIP_EXPORT 110 SCIP_Real SCIPerf( 111 SCIP_Real x /**< value to evaluate */ 112 ); 113 114 /** get critical value of a standard normal distribution at a given confidence level */ 115 SCIP_EXPORT 116 SCIP_Real SCIPnormalGetCriticalValue( 117 SCIP_CONFIDENCELEVEL clevel /**< (one-sided) confidence level */ 118 ); 119 120 /** calculates the cumulative distribution P(-infinity <= x <= value) that a normally distributed 121 * random variable x takes a value between -infinity and parameter \p value. 122 * 123 * The distribution is given by the respective mean and deviation. This implementation 124 * uses the error function erf(). 125 */ 126 SCIP_EXPORT 127 SCIP_Real SCIPnormalCDF( 128 SCIP_Real mean, /**< the mean value of the distribution */ 129 SCIP_Real variance, /**< the square of the deviation of the distribution */ 130 SCIP_Real value /**< the upper limit of the calculated distribution integral */ 131 ); 132 133 /**@} */ 134 135 /**@defgroup Regression Linear Regression 136 * @ingroup MiscellaneousMethods 137 * @brief methods for linear regression 138 * 139 * Below are the public methods for incremental linear regression of observations pairs \f$(X_i,Y_i), i=1\dots,n\f$ 140 * 141 * @{ 142 */ 143 144 /** returns the number of observations of this regression */ 145 SCIP_EXPORT 146 int SCIPregressionGetNObservations( 147 SCIP_REGRESSION* regression /**< regression data structure */ 148 ); 149 150 /** return the current slope of the regression */ 151 SCIP_EXPORT 152 SCIP_Real SCIPregressionGetSlope( 153 SCIP_REGRESSION* regression /**< regression data structure */ 154 ); 155 156 /** get the current y-intercept of the regression */ 157 SCIP_EXPORT 158 SCIP_Real SCIPregressionGetIntercept( 159 SCIP_REGRESSION* regression /**< regression data structure */ 160 ); 161 162 /** removes an observation (x,y) from the regression */ 163 SCIP_EXPORT 164 void SCIPregressionRemoveObservation( 165 SCIP_REGRESSION* regression, /**< regression data structure */ 166 SCIP_Real x, /**< X of observation */ 167 SCIP_Real y /**< Y of the observation */ 168 ); 169 170 /** update regression by a new observation (x,y) */ 171 SCIP_EXPORT 172 void SCIPregressionAddObservation( 173 SCIP_REGRESSION* regression, /**< regression data structure */ 174 SCIP_Real x, /**< X of observation */ 175 SCIP_Real y /**< Y of the observation */ 176 ); 177 178 /** reset regression data structure */ 179 SCIP_EXPORT 180 void SCIPregressionReset( 181 SCIP_REGRESSION* regression /**< regression data structure */ 182 ); 183 184 /** creates and resets a regression */ 185 SCIP_EXPORT 186 SCIP_RETCODE SCIPregressionCreate( 187 SCIP_REGRESSION** regression /**< regression data structure */ 188 ); 189 190 /** frees a regression */ 191 SCIP_EXPORT 192 void SCIPregressionFree( 193 SCIP_REGRESSION** regression /**< regression data structure */ 194 ); 195 196 /**@} */ 197 198 /* 199 */ 200 201 /**@defgroup GMLgraph GML Graphical Printing 202 * @ingroup MiscellaneousMethods 203 * @brief GML graph printing methods 204 * 205 * For a detailed format decription see http://docs.yworks.com/yfiles/doc/developers-guide/gml.html 206 * 207 * @{ 208 */ 209 210 211 /** writes a node section to the given graph file */ 212 SCIP_EXPORT 213 void SCIPgmlWriteNode( 214 FILE* file, /**< file to write to */ 215 unsigned int id, /**< id of the node */ 216 const char* label, /**< label of the node */ 217 const char* nodetype, /**< type of the node, or NULL */ 218 const char* fillcolor, /**< color of the node's interior, or NULL */ 219 const char* bordercolor /**< color of the node's border, or NULL */ 220 ); 221 222 /** writes a node section including weight to the given graph file */ 223 SCIP_EXPORT 224 void SCIPgmlWriteNodeWeight( 225 FILE* file, /**< file to write to */ 226 unsigned int id, /**< id of the node */ 227 const char* label, /**< label of the node */ 228 const char* nodetype, /**< type of the node, or NULL */ 229 const char* fillcolor, /**< color of the node's interior, or NULL */ 230 const char* bordercolor, /**< color of the node's border, or NULL */ 231 SCIP_Real weight /**< weight of node */ 232 ); 233 234 /** writes an edge section to the given graph file */ 235 SCIP_EXPORT 236 void SCIPgmlWriteEdge( 237 FILE* file, /**< file to write to */ 238 unsigned int source, /**< source node id of the node */ 239 unsigned int target, /**< target node id of the edge */ 240 const char* label, /**< label of the edge, or NULL */ 241 const char* color /**< color of the edge, or NULL */ 242 ); 243 244 /** writes an arc section to the given graph file */ 245 SCIP_EXPORT 246 void SCIPgmlWriteArc( 247 FILE* file, /**< file to write to */ 248 unsigned int source, /**< source node id of the node */ 249 unsigned int target, /**< target node id of the edge */ 250 const char* label, /**< label of the edge, or NULL */ 251 const char* color /**< color of the edge, or NULL */ 252 ); 253 254 /** writes the starting line to a GML graph file, does not open a file */ 255 SCIP_EXPORT 256 void SCIPgmlWriteOpening( 257 FILE* file, /**< file to write to */ 258 SCIP_Bool directed /**< is the graph directed */ 259 ); 260 261 /** writes the ending lines to a GML graph file, does not close a file */ 262 SCIP_EXPORT 263 void SCIPgmlWriteClosing( 264 FILE* file /**< file to close */ 265 ); 266 267 /** writes the opening line to a dot graph file, does not open a file */ 268 SCIP_EXPORT 269 void SCIPdotWriteOpening( 270 FILE* file /**< file to write to */ 271 ); 272 273 /** adds a node to the dot graph */ 274 SCIP_EXPORT 275 void SCIPdotWriteNode( 276 FILE* file, /**< file to write to */ 277 int node, /**< node id */ 278 const char* label, /**< node label */ 279 const char* nodetype, /**< type of the node, or NULL */ 280 const char* fillcolor, /**< color of the node's interior, or NULL */ 281 const char* bordercolor /**< color of the node's border, or NULL */ 282 ); 283 284 /** adds an arc (edge) between two nodes in the dot graph */ 285 SCIP_EXPORT 286 void SCIPdotWriteArc( 287 FILE* file, /**< file to write to */ 288 int source, /**< source node id of the node */ 289 int target, /**< target node id of the edge */ 290 const char* color /**< color of the edge, or NULL */ 291 ); 292 293 /** writes the closing line to a dot graph file, does not close a file */ 294 SCIP_EXPORT 295 void SCIPdotWriteClosing( 296 FILE* file /**< file to write to */ 297 ); 298 299 /**@} */ 300 301 /* 302 * Sparse solution 303 */ 304 305 /**@defgroup SparseSol Sparse Solution 306 * @ingroup DataStructures 307 * @brief sparse storage for multiple integer solutions 308 * 309 * @{ 310 */ 311 312 /** creates a sparse solution */ 313 SCIP_EXPORT 314 SCIP_RETCODE SCIPsparseSolCreate( 315 SCIP_SPARSESOL** sparsesol, /**< pointer to store the created sparse solution */ 316 SCIP_VAR** vars, /**< variables in the sparse solution, must not contain continuous variables */ 317 int nvars, /**< number of variables to store, size of the lower and upper bound arrays */ 318 SCIP_Bool cleared /**< should the lower and upper bound arrays be cleared (entries set to 0) */ 319 ); 320 321 /** frees sparse solution */ 322 SCIP_EXPORT 323 void SCIPsparseSolFree( 324 SCIP_SPARSESOL** sparsesol /**< pointer to a sparse solution */ 325 ); 326 327 /** returns the variables in the given sparse solution */ 328 SCIP_EXPORT 329 SCIP_VAR** SCIPsparseSolGetVars( 330 SCIP_SPARSESOL* sparsesol /**< a sparse solution */ 331 ); 332 333 /** returns the number of variables in the given sparse solution */ 334 SCIP_EXPORT 335 int SCIPsparseSolGetNVars( 336 SCIP_SPARSESOL* sparsesol /**< a sparse solution */ 337 ); 338 339 /** returns the the lower bound array for all variables for a given sparse solution */ 340 SCIP_EXPORT 341 SCIP_Longint* SCIPsparseSolGetLbs( 342 SCIP_SPARSESOL* sparsesol /**< a sparse solution */ 343 ); 344 345 /** returns the the upper bound array for all variables for a given sparse solution */ 346 SCIP_EXPORT 347 SCIP_Longint* SCIPsparseSolGetUbs( 348 SCIP_SPARSESOL* sparsesol /**< a sparse solution */ 349 ); 350 351 /** constructs the first solution of sparse solution (all variables are set to their lower bound value */ 352 SCIP_EXPORT 353 void SCIPsparseSolGetFirstSol( 354 SCIP_SPARSESOL* sparsesol, /**< sparse solutions */ 355 SCIP_Longint* sol, /**< array to store the first solution */ 356 int nvars /**< number of variables */ 357 ); 358 359 /** constructs the next solution of the sparse solution and return whether there was one more or not */ 360 SCIP_EXPORT 361 SCIP_Bool SCIPsparseSolGetNextSol( 362 SCIP_SPARSESOL* sparsesol, /**< sparse solutions */ 363 SCIP_Longint* sol, /**< current solution array which get changed to the next solution */ 364 int nvars /**< number of variables */ 365 ); 366 367 /**@} */ 368 369 370 /* 371 * Queue 372 */ 373 374 /**@defgroup Queue Queue 375 * @ingroup DataStructures 376 * @brief circular FIFO queue 377 * 378 * @{ 379 */ 380 381 382 /** creates a (circular) queue, best used if the size will be fixed or will not be increased that much */ 383 SCIP_EXPORT 384 SCIP_RETCODE SCIPqueueCreate( 385 SCIP_QUEUE** queue, /**< pointer to the new queue */ 386 int initsize, /**< initial number of available element slots */ 387 SCIP_Real sizefac /**< memory growing factor applied, if more element slots are needed */ 388 ); 389 390 391 /** frees queue, but not the data elements themselves */ 392 SCIP_EXPORT 393 void SCIPqueueFree( 394 SCIP_QUEUE** queue /**< pointer to a queue */ 395 ); 396 397 /** clears the queue, but doesn't free the data elements themselves */ 398 SCIP_EXPORT 399 void SCIPqueueClear( 400 SCIP_QUEUE* queue /**< queue */ 401 ); 402 403 /** inserts pointer element at the end of the queue */ 404 SCIP_EXPORT 405 SCIP_RETCODE SCIPqueueInsert( 406 SCIP_QUEUE* queue, /**< queue */ 407 void* elem /**< element to be inserted */ 408 ); 409 410 /** inserts unsigned integer element at the end of the queue */ 411 SCIP_EXPORT 412 SCIP_RETCODE SCIPqueueInsertUInt( 413 SCIP_QUEUE* queue, /**< queue */ 414 unsigned int elem /**< element to be inserted */ 415 ); 416 417 /** removes and returns the first element of the queue, or NULL if no element exists */ 418 SCIP_EXPORT 419 void* SCIPqueueRemove( 420 SCIP_QUEUE* queue /**< queue */ 421 ); 422 423 /** removes and returns the first unsigned integer element of the queue, or UNIT_MAX if no element exists */ 424 SCIP_EXPORT 425 unsigned int SCIPqueueRemoveUInt( 426 SCIP_QUEUE* queue /**< queue */ 427 ); 428 429 /** returns the first element of the queue without removing it, or NULL if no element exists */ 430 SCIP_EXPORT 431 void* SCIPqueueFirst( 432 SCIP_QUEUE* queue /**< queue */ 433 ); 434 435 /** returns the first unsigned integer element of the queue without removing it, or UINT_MAX if no element exists */ 436 SCIP_EXPORT 437 unsigned int SCIPqueueFirstUInt( 438 SCIP_QUEUE* queue /**< queue */ 439 ); 440 441 /** returns whether the queue is empty */ 442 SCIP_EXPORT 443 SCIP_Bool SCIPqueueIsEmpty( 444 SCIP_QUEUE* queue /**< queue */ 445 ); 446 447 /** returns the number of elements in the queue */ 448 SCIP_EXPORT 449 int SCIPqueueNElems( 450 SCIP_QUEUE* queue /**< queue */ 451 ); 452 453 /**@} */ 454 455 /* 456 * Priority Queue 457 */ 458 459 /**@defgroup PriorityQueue Priority Queue 460 * @ingroup DataStructures 461 * @brief priority queue with O(1) access to the minimum element 462 * 463 * @{ 464 */ 465 466 /** creates priority queue */ 467 SCIP_EXPORT 468 SCIP_RETCODE SCIPpqueueCreate( 469 SCIP_PQUEUE** pqueue, /**< pointer to a priority queue */ 470 int initsize, /**< initial number of available element slots */ 471 SCIP_Real sizefac, /**< memory growing factor applied, if more element slots are needed */ 472 SCIP_DECL_SORTPTRCOMP((*ptrcomp)), /**< data element comparator */ 473 SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)) /**< callback to act on position change of elem in priority queue, or NULL */ 474 ); 475 476 /** frees priority queue, but not the data elements themselves */ 477 SCIP_EXPORT 478 void SCIPpqueueFree( 479 SCIP_PQUEUE** pqueue /**< pointer to a priority queue */ 480 ); 481 482 /** clears the priority queue, but doesn't free the data elements themselves */ 483 SCIP_EXPORT 484 void SCIPpqueueClear( 485 SCIP_PQUEUE* pqueue /**< priority queue */ 486 ); 487 488 /** inserts element into priority queue */ 489 SCIP_EXPORT 490 SCIP_RETCODE SCIPpqueueInsert( 491 SCIP_PQUEUE* pqueue, /**< priority queue */ 492 void* elem /**< element to be inserted */ 493 ); 494 495 /** delete element at specified position, maintaining the heap property */ 496 SCIP_EXPORT 497 void SCIPpqueueDelPos( 498 SCIP_PQUEUE* pqueue, /**< priority queue */ 499 int pos /**< position of element that should be deleted */ 500 ); 501 502 /** removes and returns best element from the priority queue */ 503 SCIP_EXPORT 504 void* SCIPpqueueRemove( 505 SCIP_PQUEUE* pqueue /**< priority queue */ 506 ); 507 508 /** returns the best element of the queue without removing it */ 509 SCIP_EXPORT 510 void* SCIPpqueueFirst( 511 SCIP_PQUEUE* pqueue /**< priority queue */ 512 ); 513 514 /** returns the number of elements in the queue */ 515 SCIP_EXPORT 516 int SCIPpqueueNElems( 517 SCIP_PQUEUE* pqueue /**< priority queue */ 518 ); 519 520 /** returns the elements of the queue; changing the returned array may destroy the queue's ordering! */ 521 SCIP_EXPORT 522 void** SCIPpqueueElems( 523 SCIP_PQUEUE* pqueue /**< priority queue */ 524 ); 525 526 /** return the position of @p elem in the priority queue, or -1 if element is not found */ 527 SCIP_EXPORT 528 int SCIPpqueueFind( 529 SCIP_PQUEUE* pqueue, /**< priority queue */ 530 void* elem /**< element to be inserted */ 531 ); 532 533 /**@} */ 534 535 536 /* 537 * Hash Table 538 */ 539 540 /**@defgroup HashTable Hash Table 541 * @ingroup DataStructures 542 * @brief hash table that resolves conflicts by probing 543 * 544 *@{ 545 */ 546 547 /* fast 2-universal hash functions for two to seven 32bit elements with 32bit output */ 548 549 #define SCIPhashSignature64(a) (UINT64_C(0x8000000000000000)>>((UINT32_C(0x9e3779b9) * ((uint32_t)(a)))>>26)) 550 551 #define SCIPhashTwo(a, b) ((uint32_t)((((uint32_t)(a) + 0xd37e9a1ce2148403ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) )>>32)) 552 553 #define SCIPhashThree(a, b, c) ((uint32_t)((((uint32_t)(a) + 0xbd5c89185f082658ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) + \ 554 (uint32_t)(c) * 0xd37e9a1ce2148403ULL)>>32 )) 555 556 #define SCIPhashFour(a, b, c, d) ((uint32_t)((((uint32_t)(a) + 0xbd5c89185f082658ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) + \ 557 ((uint32_t)(c) + 0xd37e9a1ce2148403ULL) * ((uint32_t)(d) + 0x926f2d4dc4a67218ULL))>>32 )) 558 559 #define SCIPhashFive(a, b, c, d, e) ((uint32_t)((((uint32_t)(a) + 0xbd5c89185f082658ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) + \ 560 ((uint32_t)(c) + 0xd37e9a1ce2148403ULL) * ((uint32_t)(d) + 0x926f2d4dc4a67218ULL) + \ 561 (uint32_t)(e) * 0xf48d4cd331e14327ULL)>>32 )) 562 563 #define SCIPhashSix(a, b, c, d, e, f) ((uint32_t)((((uint32_t)(a) + 0xbd5c89185f082658ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) + \ 564 ((uint32_t)(c) + 0xd37e9a1ce2148403ULL) * ((uint32_t)(d) + 0x926f2d4dc4a67218ULL) + \ 565 ((uint32_t)(e) + 0xf48d4cd331e14327ULL) * ((uint32_t)(f) + 0x80791a4edfc44c75ULL))>>32 )) 566 567 #define SCIPhashSeven(a, b, c, d, e, f, g) ((uint32_t)((((uint32_t)(a) + 0xbd5c89185f082658ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) + \ 568 ((uint32_t)(c) + 0xd37e9a1ce2148403ULL) * ((uint32_t)(d) + 0x926f2d4dc4a67218ULL) + \ 569 ((uint32_t)(e) + 0xf48d4cd331e14327ULL) * ((uint32_t)(f) + 0x80791a4edfc44c75ULL) + \ 570 (uint32_t)(g) * 0x7f497d9ba3bd83c0ULL)>>32 )) 571 572 /** computes a hashcode for double precision floating point values containing 573 * 15 significant bits, the sign and the exponent 574 */ 575 INLINE static 576 uint32_t SCIPrealHashCode(double x) 577 { 578 int theexp; 579 return (((uint32_t)(uint16_t)(int16_t)ldexp(frexp(x, &theexp), 15))<<16) | (uint32_t)(uint16_t)theexp; 580 } 581 582 /** creates a hash table */ 583 SCIP_EXPORT 584 SCIP_RETCODE SCIPhashtableCreate( 585 SCIP_HASHTABLE** hashtable, /**< pointer to store the created hash table */ 586 BMS_BLKMEM* blkmem, /**< block memory used to store hash table entries */ 587 int tablesize, /**< size of the hash table */ 588 SCIP_DECL_HASHGETKEY((*hashgetkey)), /**< gets the key of the given element */ 589 SCIP_DECL_HASHKEYEQ ((*hashkeyeq)), /**< returns TRUE iff both keys are equal */ 590 SCIP_DECL_HASHKEYVAL((*hashkeyval)), /**< returns the hash value of the key */ 591 void* userptr /**< user pointer */ 592 ); 593 594 /** frees the hash table */ 595 SCIP_EXPORT 596 void SCIPhashtableFree( 597 SCIP_HASHTABLE** hashtable /**< pointer to the hash table */ 598 ); 599 600 /** removes all elements of the hash table 601 * 602 * @note From a performance point of view you should not fill and clear a hash table too often since the clearing can 603 * be expensive. Clearing is done by looping over all buckets and removing the hash table lists one-by-one. 604 * 605 * @deprecated Please use SCIPhashtableRemoveAll() 606 */ 607 SCIP_EXPORT 608 SCIP_DEPRECATED 609 void SCIPhashtableClear( 610 SCIP_HASHTABLE* hashtable /**< hash table */ 611 ); 612 613 /** inserts element in hash table (multiple inserts of same element override the previous entry) */ 614 SCIP_EXPORT 615 SCIP_RETCODE SCIPhashtableInsert( 616 SCIP_HASHTABLE* hashtable, /**< hash table */ 617 void* element /**< element to insert into the table */ 618 ); 619 620 /** inserts element in hash table (multiple insertion of same element is checked and results in an error) */ 621 SCIP_EXPORT 622 SCIP_RETCODE SCIPhashtableSafeInsert( 623 SCIP_HASHTABLE* hashtable, /**< hash table */ 624 void* element /**< element to insert into the table */ 625 ); 626 627 /** retrieve element with key from hash table, returns NULL if not existing */ 628 SCIP_EXPORT 629 void* SCIPhashtableRetrieve( 630 SCIP_HASHTABLE* hashtable, /**< hash table */ 631 void* key /**< key to retrieve */ 632 ); 633 634 /** returns whether the given element exists in the table */ 635 SCIP_EXPORT 636 SCIP_Bool SCIPhashtableExists( 637 SCIP_HASHTABLE* hashtable, /**< hash table */ 638 void* element /**< element to search in the table */ 639 ); 640 641 /** removes element from the hash table, if it exists */ 642 SCIP_EXPORT 643 SCIP_RETCODE SCIPhashtableRemove( 644 SCIP_HASHTABLE* hashtable, /**< hash table */ 645 void* element /**< element to remove from the table */ 646 ); 647 648 /** removes all elements of the hash table */ 649 SCIP_EXPORT 650 void SCIPhashtableRemoveAll( 651 SCIP_HASHTABLE* hashtable /**< hash table */ 652 ); 653 654 /** returns number of hash table elements */ 655 SCIP_EXPORT 656 SCIP_Longint SCIPhashtableGetNElements( 657 SCIP_HASHTABLE* hashtable /**< hash table */ 658 ); 659 660 /** gives the number of entries in the internal arrays of a hash table */ 661 SCIP_EXPORT 662 int SCIPhashtableGetNEntries( 663 SCIP_HASHTABLE* hashtable /**< hash table */ 664 ); 665 666 /** gives the element at the given index or NULL if entry at that index has no element */ 667 SCIP_EXPORT 668 void* SCIPhashtableGetEntry( 669 SCIP_HASHTABLE* hashtable, /**< hash table */ 670 int entryidx /**< index of hash table entry */ 671 ); 672 673 /** returns the load of the given hash table in percentage */ 674 SCIP_EXPORT 675 SCIP_Real SCIPhashtableGetLoad( 676 SCIP_HASHTABLE* hashtable /**< hash table */ 677 ); 678 679 /** prints statistics about hash table usage */ 680 SCIP_EXPORT 681 void SCIPhashtablePrintStatistics( 682 SCIP_HASHTABLE* hashtable, /**< hash table */ 683 SCIP_MESSAGEHDLR* messagehdlr /**< message handler */ 684 ); 685 686 /**@} */ 687 688 /* 689 * MultiHash Table 690 */ 691 692 /**@defgroup MultiHash Multi Hash table 693 * @ingroup DataStructures 694 * @brief hash table that resolves conflicts by queueing, thereby allowing for duplicate entries 695 * 696 *@{ 697 */ 698 699 /** returns a reasonable hash table size (a prime number) that is at least as large as the specified value */ 700 SCIP_EXPORT 701 int SCIPcalcMultihashSize( 702 int minsize /**< minimal size of the hash table */ 703 ); 704 705 /** creates a multihash table */ 706 SCIP_EXPORT 707 SCIP_RETCODE SCIPmultihashCreate( 708 SCIP_MULTIHASH** multihash, /**< pointer to store the created multihash table */ 709 BMS_BLKMEM* blkmem, /**< block memory used to store multihash table entries */ 710 int tablesize, /**< size of the hash table */ 711 SCIP_DECL_HASHGETKEY((*hashgetkey)), /**< gets the key of the given element */ 712 SCIP_DECL_HASHKEYEQ ((*hashkeyeq)), /**< returns TRUE iff both keys are equal */ 713 SCIP_DECL_HASHKEYVAL((*hashkeyval)), /**< returns the hash value of the key */ 714 void* userptr /**< user pointer */ 715 ); 716 717 /** frees the multihash table */ 718 SCIP_EXPORT 719 void SCIPmultihashFree( 720 SCIP_MULTIHASH** multihash /**< pointer to the multihash table */ 721 ); 722 723 /** inserts element in multihash table (multiple inserts of same element possible) 724 * 725 * @note A pointer to a multihashlist returned by SCIPmultihashRetrieveNext() might get invalid when adding an element 726 * to the hash table, due to dynamic resizing. 727 */ 728 SCIP_EXPORT 729 SCIP_RETCODE SCIPmultihashInsert( 730 SCIP_MULTIHASH* multihash, /**< multihash table */ 731 void* element /**< element to insert into the table */ 732 ); 733 734 /** inserts element in multihash table (multiple insertion of same element is checked and results in an error) 735 * 736 * @note A pointer to a multihashlist returned by SCIPmultihashRetrieveNext() might get invalid when adding a new 737 * element to the multihash table, due to dynamic resizing. 738 */ 739 SCIP_EXPORT 740 SCIP_RETCODE SCIPmultihashSafeInsert( 741 SCIP_MULTIHASH* multihash, /**< multihash table */ 742 void* element /**< element to insert into the table */ 743 ); 744 745 /** retrieve element with key from multihash table, returns NULL if not existing */ 746 SCIP_EXPORT 747 void* SCIPmultihashRetrieve( 748 SCIP_MULTIHASH* multihash, /**< multihash table */ 749 void* key /**< key to retrieve */ 750 ); 751 752 /** retrieve element with key from multihash table, returns NULL if not existing 753 * can be used to retrieve all entries with the same key (one-by-one) 754 * 755 * @note The returned multimultihashlist pointer might get invalid when adding a new element to the multihash table. 756 */ 757 SCIP_EXPORT 758 void* SCIPmultihashRetrieveNext( 759 SCIP_MULTIHASH* multihash, /**< multihash table */ 760 SCIP_MULTIHASHLIST** multihashlist, /**< input: entry in hash table list from which to start searching, or NULL 761 * output: entry in hash table list corresponding to element after 762 * retrieved one, or NULL */ 763 void* key /**< key to retrieve */ 764 ); 765 766 /** returns whether the given element exists in the multihash table */ 767 SCIP_EXPORT 768 SCIP_Bool SCIPmultihashExists( 769 SCIP_MULTIHASH* multihash, /**< multihash table */ 770 void* element /**< element to search in the table */ 771 ); 772 773 /** removes element from the multihash table, if it exists */ 774 SCIP_EXPORT 775 SCIP_RETCODE SCIPmultihashRemove( 776 SCIP_MULTIHASH* multihash, /**< multihash table */ 777 void* element /**< element to remove from the table */ 778 ); 779 780 /** removes all elements of the multihash table 781 * 782 * @note From a performance point of view you should not fill and clear a hash table too often since the clearing can 783 * be expensive. Clearing is done by looping over all buckets and removing the hash table lists one-by-one. 784 */ 785 SCIP_EXPORT 786 void SCIPmultihashRemoveAll( 787 SCIP_MULTIHASH* multihash /**< multihash table */ 788 ); 789 790 /** returns number of multihash table elements */ 791 SCIP_EXPORT 792 SCIP_Longint SCIPmultihashGetNElements( 793 SCIP_MULTIHASH* multihash /**< multihash table */ 794 ); 795 796 /** returns the load of the given multihash table in percentage */ 797 SCIP_EXPORT 798 SCIP_Real SCIPmultihashGetLoad( 799 SCIP_MULTIHASH* multihash /**< multihash table */ 800 ); 801 802 /** prints statistics about multihash table usage */ 803 SCIP_EXPORT 804 void SCIPmultihashPrintStatistics( 805 SCIP_MULTIHASH* multihash, /**< multihash table */ 806 SCIP_MESSAGEHDLR* messagehdlr /**< message handler */ 807 ); 808 809 /** standard hash key comparator for string keys */ 810 SCIP_EXPORT 811 SCIP_DECL_HASHKEYEQ(SCIPhashKeyEqString); 812 813 /** standard hashing function for string keys */ 814 SCIP_EXPORT 815 SCIP_DECL_HASHKEYVAL(SCIPhashKeyValString); 816 817 /** gets the element as the key */ 818 SCIP_EXPORT 819 SCIP_DECL_HASHGETKEY(SCIPhashGetKeyStandard); 820 821 /** returns TRUE iff both keys(pointer) are equal */ 822 SCIP_EXPORT 823 SCIP_DECL_HASHKEYEQ(SCIPhashKeyEqPtr); 824 825 /** returns the hash value of the key */ 826 SCIP_EXPORT 827 SCIP_DECL_HASHKEYVAL(SCIPhashKeyValPtr); 828 829 /**@} */ 830 831 832 /* 833 * Hash Map 834 */ 835 836 /**@defgroup HashMap Hash Map 837 * @ingroup DataStructures 838 * @brief hash map to store key-value pairs (called \p origin and \p image) 839 * 840 * @{ 841 */ 842 843 /** creates a hash map mapping pointers to pointers */ 844 SCIP_EXPORT 845 SCIP_RETCODE SCIPhashmapCreate( 846 SCIP_HASHMAP** hashmap, /**< pointer to store the created hash map */ 847 BMS_BLKMEM* blkmem, /**< block memory used to store hash map entries */ 848 int mapsize /**< size of the hash map */ 849 ); 850 851 /** frees the hash map */ 852 SCIP_EXPORT 853 void SCIPhashmapFree( 854 SCIP_HASHMAP** hashmap /**< pointer to the hash map */ 855 ); 856 857 /** inserts new origin->image pair in hash map (must not be called for already existing origins!) */ 858 SCIP_EXPORT 859 SCIP_RETCODE SCIPhashmapInsert( 860 SCIP_HASHMAP* hashmap, /**< hash map */ 861 void* origin, /**< origin to set image for */ 862 void* image /**< new image for origin */ 863 ); 864 865 /** inserts new origin->image pair in hash map (must not be called for already existing origins!) */ 866 SCIP_EXPORT 867 SCIP_RETCODE SCIPhashmapInsertInt( 868 SCIP_HASHMAP* hashmap, /**< hash map */ 869 void* origin, /**< origin to set image for */ 870 int image /**< new image for origin */ 871 ); 872 873 /** inserts new origin->image pair in hash map (must not be called for already existing origins!) */ 874 SCIP_EXPORT 875 SCIP_RETCODE SCIPhashmapInsertReal( 876 SCIP_HASHMAP* hashmap, /**< hash map */ 877 void* origin, /**< origin to set image for */ 878 SCIP_Real image /**< new image for origin */ 879 ); 880 881 /** retrieves image of given origin from the hash map, or NULL if no image exists */ 882 SCIP_EXPORT 883 void* SCIPhashmapGetImage( 884 SCIP_HASHMAP* hashmap, /**< hash map */ 885 void* origin /**< origin to retrieve image for */ 886 ); 887 888 /** retrieves image of given origin from the hash map, or INT_MAX if no image exists */ 889 SCIP_EXPORT 890 int SCIPhashmapGetImageInt( 891 SCIP_HASHMAP* hashmap, /**< hash map */ 892 void* origin /**< origin to retrieve image for */ 893 ); 894 895 /** retrieves image of given origin from the hash map, or SCIP_INVALID if no image exists */ 896 SCIP_EXPORT 897 SCIP_Real SCIPhashmapGetImageReal( 898 SCIP_HASHMAP* hashmap, /**< hash map */ 899 void* origin /**< origin to retrieve image for */ 900 ); 901 902 /** sets image for given origin in the hash map, either by modifying existing origin->image pair or by appending a 903 * new origin->image pair 904 */ 905 SCIP_EXPORT 906 SCIP_RETCODE SCIPhashmapSetImage( 907 SCIP_HASHMAP* hashmap, /**< hash map */ 908 void* origin, /**< origin to set image for */ 909 void* image /**< new image for origin */ 910 ); 911 912 /** sets image for given origin in the hash map, either by modifying existing origin->image pair or by appending a 913 * new origin->image pair 914 */ 915 SCIP_EXPORT 916 SCIP_RETCODE SCIPhashmapSetImageInt( 917 SCIP_HASHMAP* hashmap, /**< hash map */ 918 void* origin, /**< origin to set image for */ 919 int image /**< new image for origin */ 920 ); 921 922 /** sets image for given origin in the hash map, either by modifying existing origin->image pair or by appending a 923 * new origin->image pair 924 */ 925 SCIP_EXPORT 926 SCIP_RETCODE SCIPhashmapSetImageReal( 927 SCIP_HASHMAP* hashmap, /**< hash map */ 928 void* origin, /**< origin to set image for */ 929 SCIP_Real image /**< new image for origin */ 930 ); 931 932 /** checks whether an image to the given origin exists in the hash map */ 933 SCIP_EXPORT 934 SCIP_Bool SCIPhashmapExists( 935 SCIP_HASHMAP* hashmap, /**< hash map */ 936 void* origin /**< origin to search for */ 937 ); 938 939 /** removes origin->image pair from the hash map, if it exists */ 940 SCIP_EXPORT 941 SCIP_RETCODE SCIPhashmapRemove( 942 SCIP_HASHMAP* hashmap, /**< hash map */ 943 void* origin /**< origin to remove from the list */ 944 ); 945 946 /** prints statistics about hash map usage */ 947 SCIP_EXPORT 948 void SCIPhashmapPrintStatistics( 949 SCIP_HASHMAP* hashmap, /**< hash map */ 950 SCIP_MESSAGEHDLR* messagehdlr /**< message handler */ 951 ); 952 953 /** indicates whether a hash map has no entries */ 954 SCIP_EXPORT 955 SCIP_Bool SCIPhashmapIsEmpty( 956 SCIP_HASHMAP* hashmap /**< hash map */ 957 ); 958 959 /** gives the number of elements in a hash map */ 960 SCIP_EXPORT 961 int SCIPhashmapGetNElements( 962 SCIP_HASHMAP* hashmap /**< hash map */ 963 ); 964 965 /** gives the number of entries in the internal arrays of a hash map */ 966 SCIP_EXPORT 967 int SCIPhashmapGetNEntries( 968 SCIP_HASHMAP* hashmap /**< hash map */ 969 ); 970 971 /** gives the hashmap entry at the given index or NULL if entry has no element */ 972 SCIP_EXPORT 973 SCIP_HASHMAPENTRY* SCIPhashmapGetEntry( 974 SCIP_HASHMAP* hashmap, /**< hash map */ 975 int entryidx /**< index of hash map entry */ 976 ); 977 978 /** gives the origin of the hashmap entry */ 979 SCIP_EXPORT 980 void* SCIPhashmapEntryGetOrigin( 981 SCIP_HASHMAPENTRY* entry /**< hash map entry */ 982 ); 983 984 /** gives the image of the hashmap entry */ 985 SCIP_EXPORT 986 void* SCIPhashmapEntryGetImage( 987 SCIP_HASHMAPENTRY* entry /**< hash map entry */ 988 ); 989 990 /** gives the image of the hashmap entry */ 991 SCIP_EXPORT 992 int SCIPhashmapEntryGetImageInt( 993 SCIP_HASHMAPENTRY* entry /**< hash map entry */ 994 ); 995 996 /** gives the image of the hashmap entry */ 997 SCIP_EXPORT 998 SCIP_Real SCIPhashmapEntryGetImageReal( 999 SCIP_HASHMAPENTRY* entry /**< hash map entry */ 1000 ); 1001 1002 /** sets pointer image of a hashmap entry */ 1003 SCIP_EXPORT 1004 void SCIPhashmapEntrySetImage( 1005 SCIP_HASHMAPENTRY* entry, /**< hash map entry */ 1006 void* image /**< new image */ 1007 ); 1008 1009 /** sets integer image of a hashmap entry */ 1010 SCIP_EXPORT 1011 void SCIPhashmapEntrySetImageInt( 1012 SCIP_HASHMAPENTRY* entry, /**< hash map entry */ 1013 int image /**< new image */ 1014 ); 1015 1016 /** sets real image of a hashmap entry */ 1017 SCIP_EXPORT 1018 void SCIPhashmapEntrySetImageReal( 1019 SCIP_HASHMAPENTRY* entry, /**< hash map entry */ 1020 SCIP_Real image /**< new image */ 1021 ); 1022 1023 /** removes all entries in a hash map. */ 1024 SCIP_EXPORT 1025 SCIP_RETCODE SCIPhashmapRemoveAll( 1026 SCIP_HASHMAP* hashmap /**< hash map */ 1027 ); 1028 1029 /**@} */ 1030 1031 1032 /* 1033 * Hash Set 1034 */ 1035 1036 /**@defgroup HashSet Hash Set 1037 * @ingroup DataStructures 1038 * @brief very lightweight hash set of pointers 1039 * 1040 * @{ 1041 */ 1042 1043 /** creates a hash set of pointers */ 1044 SCIP_EXPORT 1045 SCIP_RETCODE SCIPhashsetCreate( 1046 SCIP_HASHSET** hashset, /**< pointer to store the created hash set */ 1047 BMS_BLKMEM* blkmem, /**< block memory used to store hash set entries */ 1048 int size /**< initial size of the hash set; it is guaranteed that the set is not 1049 * resized if at most that many elements are inserted */ 1050 ); 1051 1052 /** frees the hash set */ 1053 SCIP_EXPORT 1054 void SCIPhashsetFree( 1055 SCIP_HASHSET** hashset, /**< pointer to the hash set */ 1056 BMS_BLKMEM* blkmem /**< block memory used to store hash set entries */ 1057 ); 1058 1059 /** inserts new element into the hash set */ 1060 SCIP_EXPORT 1061 SCIP_RETCODE SCIPhashsetInsert( 1062 SCIP_HASHSET* hashset, /**< hash set */ 1063 BMS_BLKMEM* blkmem, /**< block memory used to store hash set entries */ 1064 void* element /**< element to insert */ 1065 ); 1066 1067 /** checks whether an element exists in the hash set */ 1068 SCIP_EXPORT 1069 SCIP_Bool SCIPhashsetExists( 1070 SCIP_HASHSET* hashset, /**< hash set */ 1071 void* element /**< element to search for */ 1072 ); 1073 1074 /** removes an element from the hash set, if it exists */ 1075 SCIP_EXPORT 1076 SCIP_RETCODE SCIPhashsetRemove( 1077 SCIP_HASHSET* hashset, /**< hash set */ 1078 void* element /**< origin to remove from the list */ 1079 ); 1080 1081 /** prints statistics about hash set usage */ 1082 SCIP_EXPORT 1083 void SCIPhashsetPrintStatistics( 1084 SCIP_HASHSET* hashset, /**< hash set */ 1085 SCIP_MESSAGEHDLR* messagehdlr /**< message handler */ 1086 ); 1087 1088 /** indicates whether a hash set has no entries */ 1089 SCIP_EXPORT 1090 SCIP_Bool SCIPhashsetIsEmpty( 1091 SCIP_HASHSET* hashset /**< hash set */ 1092 ); 1093 1094 /** gives the number of elements in a hash set */ 1095 SCIP_EXPORT 1096 int SCIPhashsetGetNElements( 1097 SCIP_HASHSET* hashset /**< hash set */ 1098 ); 1099 1100 /** gives the number of slots of a hash set */ 1101 SCIP_EXPORT 1102 int SCIPhashsetGetNSlots( 1103 SCIP_HASHSET* hashset /**< hash set */ 1104 ); 1105 1106 /** gives the array of hash set slots; contains all elements in indetermined order and may contain NULL values */ 1107 SCIP_EXPORT 1108 void** SCIPhashsetGetSlots( 1109 SCIP_HASHSET* hashset /**< hash set */ 1110 ); 1111 1112 /** removes all entries in a hash set. */ 1113 SCIP_EXPORT 1114 void SCIPhashsetRemoveAll( 1115 SCIP_HASHSET* hashset /**< hash set */ 1116 ); 1117 1118 #ifdef NDEBUG 1119 1120 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and 1121 * speed up the algorithms. 1122 */ 1123 1124 #define SCIPhashsetIsEmpty(hashset) ((hashset)->nelements == 0) 1125 #define SCIPhashsetGetNElements(hashset) ((hashset)->nelements) 1126 #define SCIPhashsetGetNSlots(hashset) (1u << (64 - (hashset)->shift)) 1127 #define SCIPhashsetGetSlots(hashset) ((hashset)->slots) 1128 1129 #endif 1130 1131 /**@} */ 1132 1133 1134 /* 1135 * Activity 1136 */ 1137 1138 /**@defgroup ResourceActivity Resource Activity 1139 * @ingroup DataStructures 1140 * @brief ressource activity data structure 1141 * 1142 * @{ 1143 */ 1144 1145 /** create a resource activity */ 1146 SCIP_EXPORT 1147 SCIP_RETCODE SCIPactivityCreate( 1148 SCIP_RESOURCEACTIVITY** activity, /**< pointer to store the resource activity */ 1149 SCIP_VAR* var, /**< start time variable of the activity */ 1150 int duration, /**< duration of the activity */ 1151 int demand /**< demand of the activity */ 1152 ); 1153 1154 /** frees a resource activity */ 1155 SCIP_EXPORT 1156 void SCIPactivityFree( 1157 SCIP_RESOURCEACTIVITY** activity /**< pointer to the resource activity */ 1158 ); 1159 1160 #ifndef NDEBUG 1161 1162 /** returns the start time variable of the resource activity */ 1163 SCIP_EXPORT 1164 SCIP_VAR* SCIPactivityGetVar( 1165 SCIP_RESOURCEACTIVITY* activity /**< resource activity */ 1166 ); 1167 1168 /** returns the duration of the resource activity */ 1169 SCIP_EXPORT 1170 int SCIPactivityGetDuration( 1171 SCIP_RESOURCEACTIVITY* activity /**< resource activity */ 1172 ); 1173 1174 /** returns the demand of the resource activity */ 1175 SCIP_EXPORT 1176 int SCIPactivityGetDemand( 1177 SCIP_RESOURCEACTIVITY* activity /**< resource activity */ 1178 ); 1179 1180 /** returns the energy of the resource activity */ 1181 SCIP_EXPORT 1182 int SCIPactivityGetEnergy( 1183 SCIP_RESOURCEACTIVITY* activity /**< resource activity */ 1184 ); 1185 1186 #else 1187 1188 #define SCIPactivityGetVar(activity) ((activity)->var) 1189 #define SCIPactivityGetDuration(activity) ((activity)->duration) 1190 #define SCIPactivityGetDemand(activity) ((activity)->demand) 1191 #define SCIPactivityGetEnergy(activity) ((activity)->duration * (activity)->demand) 1192 1193 #endif 1194 1195 /**@} */ 1196 1197 1198 /* 1199 * Resource Profile 1200 */ 1201 1202 /**@defgroup ResourceProfile Resource Profile 1203 * @ingroup DataStructures 1204 * @brief ressource profile data structure 1205 * 1206 * @{ 1207 */ 1208 1209 /** creates resource profile */ 1210 SCIP_EXPORT 1211 SCIP_RETCODE SCIPprofileCreate( 1212 SCIP_PROFILE** profile, /**< pointer to store the resource profile */ 1213 int capacity /**< resource capacity */ 1214 ); 1215 1216 /** frees given resource profile */ 1217 SCIP_EXPORT 1218 void SCIPprofileFree( 1219 SCIP_PROFILE** profile /**< pointer to the resource profile */ 1220 ); 1221 1222 /** output of the given resource profile */ 1223 SCIP_EXPORT 1224 void SCIPprofilePrint( 1225 SCIP_PROFILE* profile, /**< resource profile to output */ 1226 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 1227 FILE* file /**< output file (or NULL for standard output) */ 1228 ); 1229 1230 /** returns the capacity of the resource profile */ 1231 SCIP_EXPORT 1232 int SCIPprofileGetCapacity( 1233 SCIP_PROFILE* profile /**< resource profile to use */ 1234 ); 1235 1236 /** returns the number time points of the resource profile */ 1237 SCIP_EXPORT 1238 int SCIPprofileGetNTimepoints( 1239 SCIP_PROFILE* profile /**< resource profile to use */ 1240 ); 1241 1242 /** returns the time points of the resource profile */ 1243 SCIP_EXPORT 1244 int* SCIPprofileGetTimepoints( 1245 SCIP_PROFILE* profile /**< resource profile to use */ 1246 ); 1247 1248 /** returns the loads of the resource profile */ 1249 SCIP_EXPORT 1250 int* SCIPprofileGetLoads( 1251 SCIP_PROFILE* profile /**< resource profile to use */ 1252 ); 1253 1254 /** returns the time point for given position of the resource profile */ 1255 SCIP_EXPORT 1256 int SCIPprofileGetTime( 1257 SCIP_PROFILE* profile, /**< resource profile to use */ 1258 int pos /**< position */ 1259 ); 1260 1261 /** returns the loads of the resource profile at the given position */ 1262 SCIP_EXPORT 1263 int SCIPprofileGetLoad( 1264 SCIP_PROFILE* profile, /**< resource profile */ 1265 int pos /**< position */ 1266 ); 1267 1268 /** returns if the given time point exists in the resource profile and stores the position of the given time point if it 1269 * exists; otherwise the position of the next smaller existing time point is stored 1270 */ 1271 SCIP_EXPORT 1272 SCIP_Bool SCIPprofileFindLeft( 1273 SCIP_PROFILE* profile, /**< resource profile to search */ 1274 int timepoint, /**< time point to search for */ 1275 int* pos /**< pointer to store the position */ 1276 ); 1277 1278 /** insert a core into resource profile; if the core is non-empty the resource profile will be updated otherwise nothing 1279 * happens 1280 */ 1281 SCIP_EXPORT 1282 SCIP_RETCODE SCIPprofileInsertCore( 1283 SCIP_PROFILE* profile, /**< resource profile to use */ 1284 int left, /**< left side of the core */ 1285 int right, /**< right side of the core */ 1286 int height, /**< height of the core */ 1287 int* pos, /**< pointer to store the first position were it gets infeasible */ 1288 SCIP_Bool* infeasible /**< pointer to store if the core does not fit due to capacity */ 1289 ); 1290 1291 /** subtracts the height from the resource profile during core time */ 1292 SCIP_EXPORT 1293 SCIP_RETCODE SCIPprofileDeleteCore( 1294 SCIP_PROFILE* profile, /**< resource profile to use */ 1295 int left, /**< left side of the core */ 1296 int right, /**< right side of the core */ 1297 int height /**< height of the core */ 1298 ); 1299 1300 /** return the earliest possible starting point within the time interval [lb,ub] for a given core (given by its height 1301 * and duration) 1302 */ 1303 SCIP_EXPORT 1304 int SCIPprofileGetEarliestFeasibleStart( 1305 SCIP_PROFILE* profile, /**< resource profile to use */ 1306 int est, /**< earliest starting time of the given core */ 1307 int lst, /**< latest starting time of the given core */ 1308 int duration, /**< duration of the core */ 1309 int height, /**< height of the core */ 1310 SCIP_Bool* infeasible /**< pointer store if the corer cannot be inserted */ 1311 ); 1312 1313 /** return the latest possible starting point within the time interval [lb,ub] for a given core (given by its height and 1314 * duration) 1315 */ 1316 SCIP_EXPORT 1317 int SCIPprofileGetLatestFeasibleStart( 1318 SCIP_PROFILE* profile, /**< resource profile to use */ 1319 int lb, /**< earliest possible start point */ 1320 int ub, /**< latest possible start point */ 1321 int duration, /**< duration of the core */ 1322 int height, /**< height of the core */ 1323 SCIP_Bool* infeasible /**< pointer store if the core cannot be inserted */ 1324 ); 1325 1326 /**@} */ 1327 1328 /* 1329 * Directed graph 1330 */ 1331 1332 /**@addtogroup DirectedGraph 1333 * 1334 * @{ 1335 */ 1336 1337 /** resize directed graph structure */ 1338 SCIP_EXPORT 1339 SCIP_RETCODE SCIPdigraphResize( 1340 SCIP_DIGRAPH* digraph, /**< directed graph */ 1341 int nnodes /**< new number of nodes */ 1342 ); 1343 1344 /** sets the sizes of the successor lists for the nodes in a directed graph and allocates memory for the lists */ 1345 SCIP_EXPORT 1346 SCIP_RETCODE SCIPdigraphSetSizes( 1347 SCIP_DIGRAPH* digraph, /**< directed graph */ 1348 int* sizes /**< sizes of the successor lists */ 1349 ); 1350 1351 /** frees given directed graph structure */ 1352 SCIP_EXPORT 1353 void SCIPdigraphFree( 1354 SCIP_DIGRAPH** digraph /**< pointer to the directed graph */ 1355 ); 1356 1357 /** add (directed) arc and a related data to the directed graph structure 1358 * 1359 * @note if the arc is already contained, it is added a second time 1360 */ 1361 SCIP_EXPORT 1362 SCIP_RETCODE SCIPdigraphAddArc( 1363 SCIP_DIGRAPH* digraph, /**< directed graph */ 1364 int startnode, /**< start node of the arc */ 1365 int endnode, /**< start node of the arc */ 1366 void* data /**< data that should be stored for the arc; or NULL */ 1367 ); 1368 1369 /** add (directed) arc to the directed graph structure, if it is not contained, yet 1370 * 1371 * @note if there already exists an arc from startnode to endnode, the new arc is not added, 1372 * even if its data is different 1373 */ 1374 SCIP_EXPORT 1375 SCIP_RETCODE SCIPdigraphAddArcSafe( 1376 SCIP_DIGRAPH* digraph, /**< directed graph */ 1377 int startnode, /**< start node of the arc */ 1378 int endnode, /**< start node of the arc */ 1379 void* data /**< data that should be stored for the arc; or NULL */ 1380 ); 1381 1382 /** sets the number of successors to a given value */ 1383 SCIP_EXPORT 1384 SCIP_RETCODE SCIPdigraphSetNSuccessors( 1385 SCIP_DIGRAPH* digraph, /**< directed graph */ 1386 int node, /**< node for which the number of successors has to be changed */ 1387 int nsuccessors /**< new number of successors */ 1388 ); 1389 1390 /** returns the number of nodes of the given digraph */ 1391 SCIP_EXPORT 1392 int SCIPdigraphGetNNodes( 1393 SCIP_DIGRAPH* digraph /**< directed graph */ 1394 ); 1395 1396 /** returns the node data, or NULL if no data exist */ 1397 SCIP_EXPORT 1398 void* SCIPdigraphGetNodeData( 1399 SCIP_DIGRAPH* digraph, /**< directed graph */ 1400 int node /**< node for which the node data is returned */ 1401 ); 1402 1403 /** sets the node data */ 1404 SCIP_EXPORT 1405 void SCIPdigraphSetNodeData( 1406 SCIP_DIGRAPH* digraph, /**< directed graph */ 1407 void* dataptr, /**< user node data pointer, or NULL */ 1408 int node /**< node for which the node data is returned */ 1409 ); 1410 1411 /** returns the total number of arcs in the given digraph */ 1412 SCIP_EXPORT 1413 int SCIPdigraphGetNArcs( 1414 SCIP_DIGRAPH* digraph /**< directed graph */ 1415 ); 1416 1417 /** returns the number of successor nodes of the given node */ 1418 SCIP_EXPORT 1419 int SCIPdigraphGetNSuccessors( 1420 SCIP_DIGRAPH* digraph, /**< directed graph */ 1421 int node /**< node for which the number of outgoing arcs is returned */ 1422 ); 1423 1424 /** returns the array of indices of the successor nodes; this array must not be changed from outside */ 1425 SCIP_EXPORT 1426 int* SCIPdigraphGetSuccessors( 1427 SCIP_DIGRAPH* digraph, /**< directed graph */ 1428 int node /**< node for which the array of outgoing arcs is returned */ 1429 ); 1430 1431 /** returns the array of data corresponding to the arcs originating at the given node, or NULL if no data exist; this 1432 * array must not be changed from outside 1433 */ 1434 SCIP_EXPORT 1435 void** SCIPdigraphGetSuccessorsData( 1436 SCIP_DIGRAPH* digraph, /**< directed graph */ 1437 int node /**< node for which the data corresponding to the outgoing arcs is returned */ 1438 ); 1439 1440 /** identifies the articulation points in a given directed graph 1441 * uses the helper recursive function findArticulationPointsUtil 1442 */ 1443 SCIP_EXPORT 1444 SCIP_RETCODE SCIPdigraphGetArticulationPoints( 1445 SCIP_DIGRAPH* digraph, /**< directed graph */ 1446 int** articulations, /**< array to store the sorted node indices of the computed articulation points, or NULL */ 1447 int* narticulations /**< number of the computed articulation points, or NULL */ 1448 ); 1449 1450 /** Compute undirected connected components on the given graph. 1451 * 1452 * @note For each arc, its reverse is added, so the graph does not need to be the directed representation of an 1453 * undirected graph. 1454 */ 1455 SCIP_EXPORT 1456 SCIP_RETCODE SCIPdigraphComputeUndirectedComponents( 1457 SCIP_DIGRAPH* digraph, /**< directed graph */ 1458 int minsize, /**< all components with less nodes are ignored */ 1459 int* components, /**< array with as many slots as there are nodes in the directed graph 1460 * to store for each node the component to which it belongs 1461 * (components are numbered 0 to ncomponents - 1); or NULL, if components 1462 * are accessed one-by-one using SCIPdigraphGetComponent() */ 1463 int* ncomponents /**< pointer to store the number of components; or NULL, if the 1464 * number of components is accessed by SCIPdigraphGetNComponents() */ 1465 ); 1466 1467 /** Computes all strongly connected components of an undirected connected component with Tarjan's Algorithm. 1468 * The resulting strongly connected components are sorted topologically (starting from the end of the 1469 * strongcomponents array). 1470 * 1471 * @note In general a topological sort of the strongly connected components is not unique. 1472 */ 1473 SCIP_EXPORT 1474 SCIP_RETCODE SCIPdigraphComputeDirectedComponents( 1475 SCIP_DIGRAPH* digraph, /**< directed graph */ 1476 int compidx, /**< number of the undirected connected component */ 1477 int* strongcomponents, /**< array to store the strongly connected components 1478 * (length >= size of the component) */ 1479 int* strongcompstartidx, /**< array to store the start indices of the strongly connected 1480 * components (length >= size of the component) */ 1481 int* nstrongcomponents /**< pointer to store the number of strongly connected 1482 * components */ 1483 ); 1484 1485 /** Performes an (almost) topological sort on the undirected components of the given directed graph. The undirected 1486 * components should be computed before using SCIPdigraphComputeUndirectedComponents(). 1487 * 1488 * @note In general a topological sort is not unique. Note, that there might be directed cycles, that are randomly 1489 * broken, which is the reason for having only almost topologically sorted arrays. 1490 */ 1491 SCIP_EXPORT 1492 SCIP_RETCODE SCIPdigraphTopoSortComponents( 1493 SCIP_DIGRAPH* digraph /**< directed graph */ 1494 ); 1495 1496 /** returns the number of previously computed undirected components for the given directed graph */ 1497 SCIP_EXPORT 1498 int SCIPdigraphGetNComponents( 1499 SCIP_DIGRAPH* digraph /**< directed graph */ 1500 ); 1501 1502 /** Returns the previously computed undirected component of the given number for the given directed graph. 1503 * If the components were sorted using SCIPdigraphTopoSortComponents(), the component is (almost) topologically sorted. 1504 */ 1505 SCIP_EXPORT 1506 void SCIPdigraphGetComponent( 1507 SCIP_DIGRAPH* digraph, /**< directed graph */ 1508 int compidx, /**< number of the component to return */ 1509 int** nodes, /**< pointer to store the nodes in the component; or NULL, if not needed */ 1510 int* nnodes /**< pointer to store the number of nodes in the component; 1511 * or NULL, if not needed */ 1512 ); 1513 1514 /** frees the component information for the given directed graph */ 1515 SCIP_EXPORT 1516 void SCIPdigraphFreeComponents( 1517 SCIP_DIGRAPH* digraph /**< directed graph */ 1518 ); 1519 1520 /** output of the given directed graph via the given message handler */ 1521 SCIP_EXPORT 1522 void SCIPdigraphPrint( 1523 SCIP_DIGRAPH* digraph, /**< directed graph */ 1524 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 1525 FILE* file /**< output file (or NULL for standard output) */ 1526 ); 1527 1528 /** prints the given directed graph structure in GML format into the given file */ 1529 SCIP_EXPORT 1530 void SCIPdigraphPrintGml( 1531 SCIP_DIGRAPH* digraph, /**< directed graph */ 1532 FILE* file /**< file to write to */ 1533 ); 1534 1535 1536 /** output of the given directed graph via the given message handler */ 1537 SCIP_EXPORT 1538 void SCIPdigraphPrintComponents( 1539 SCIP_DIGRAPH* digraph, /**< directed graph */ 1540 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 1541 FILE* file /**< output file (or NULL for standard output) */ 1542 ); 1543 1544 /**@} */ 1545 1546 /* 1547 * Binary search tree 1548 */ 1549 1550 /**@defgroup BinaryTree Binary Search Tree 1551 * @ingroup DataStructures 1552 * @brief binary search tree data structure 1553 *@{ 1554 */ 1555 1556 /** creates a binary tree node with sorting value and user data */ 1557 SCIP_EXPORT 1558 SCIP_RETCODE SCIPbtnodeCreate( 1559 SCIP_BT* tree, /**< binary search tree */ 1560 SCIP_BTNODE** node, /**< pointer to store the created search node */ 1561 void* dataptr /**< user node data pointer, or NULL */ 1562 ); 1563 1564 /** frees the binary node including the rooted subtree 1565 * 1566 * @note The user pointer (object) is not freed. If needed, it has to be done by the user. 1567 */ 1568 SCIP_EXPORT 1569 void SCIPbtnodeFree( 1570 SCIP_BT* tree, /**< binary tree */ 1571 SCIP_BTNODE** node /**< node to be freed */ 1572 ); 1573 1574 /** returns the user data pointer stored in that node */ 1575 SCIP_EXPORT 1576 void* SCIPbtnodeGetData( 1577 SCIP_BTNODE* node /**< node */ 1578 ); 1579 1580 /** returns the parent which can be NULL if the given node is the root */ 1581 SCIP_EXPORT 1582 SCIP_BTNODE* SCIPbtnodeGetParent( 1583 SCIP_BTNODE* node /**< node */ 1584 ); 1585 1586 /** returns left child which can be NULL if the given node is a leaf */ 1587 SCIP_EXPORT 1588 SCIP_BTNODE* SCIPbtnodeGetLeftchild( 1589 SCIP_BTNODE* node /**< node */ 1590 ); 1591 1592 /** returns right child which can be NULL if the given node is a leaf */ 1593 SCIP_EXPORT 1594 SCIP_BTNODE* SCIPbtnodeGetRightchild( 1595 SCIP_BTNODE* node /**< node */ 1596 ); 1597 1598 /** returns the sibling of the node or NULL if does not exist */ 1599 SCIP_EXPORT 1600 SCIP_BTNODE* SCIPbtnodeGetSibling( 1601 SCIP_BTNODE* node /**< node */ 1602 ); 1603 1604 /** returns whether the node is a root node */ 1605 SCIP_EXPORT 1606 SCIP_Bool SCIPbtnodeIsRoot( 1607 SCIP_BTNODE* node /**< node */ 1608 ); 1609 1610 /** returns whether the node is a leaf */ 1611 SCIP_EXPORT 1612 SCIP_Bool SCIPbtnodeIsLeaf( 1613 SCIP_BTNODE* node /**< node */ 1614 ); 1615 1616 /** returns TRUE if the given node is left child */ 1617 SCIP_EXPORT 1618 SCIP_Bool SCIPbtnodeIsLeftchild( 1619 SCIP_BTNODE* node /**< node */ 1620 ); 1621 1622 /** returns TRUE if the given node is right child */ 1623 SCIP_EXPORT 1624 SCIP_Bool SCIPbtnodeIsRightchild( 1625 SCIP_BTNODE* node /**< node */ 1626 ); 1627 1628 #ifdef NDEBUG 1629 1630 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and 1631 * speed up the algorithms. 1632 */ 1633 1634 #define SCIPbtnodeGetData(node) ((node)->dataptr) 1635 #define SCIPbtnodeGetParent(node) ((node)->parent) 1636 #define SCIPbtnodeGetLeftchild(node) ((node)->left) 1637 #define SCIPbtnodeGetRightchild(node) ((node)->right) 1638 #define SCIPbtnodeGetSibling(node) ((node)->parent == NULL ? NULL : \ 1639 (node)->parent->left == (node) ? (node)->parent->right : (node)->parent->left) 1640 #define SCIPbtnodeIsRoot(node) ((node)->parent == NULL) 1641 #define SCIPbtnodeIsLeaf(node) ((node)->left == NULL && (node)->right == NULL) 1642 #define SCIPbtnodeIsLeftchild(node) ((node)->parent == NULL ? FALSE : (node)->parent->left == (node) ? TRUE : FALSE) 1643 #define SCIPbtnodeIsRightchild(node) ((node)->parent == NULL ? FALSE : (node)->parent->right == (node) ? TRUE : FALSE) 1644 1645 #endif 1646 1647 /** sets the give node data 1648 * 1649 * @note The old user pointer is not freed. 1650 */ 1651 SCIP_EXPORT 1652 void SCIPbtnodeSetData( 1653 SCIP_BTNODE* node, /**< node */ 1654 void* dataptr /**< node user data pointer */ 1655 ); 1656 1657 /** sets parent node 1658 * 1659 * @note The old parent including the rooted subtree is not delete. 1660 */ 1661 SCIP_EXPORT 1662 void SCIPbtnodeSetParent( 1663 SCIP_BTNODE* node, /**< node */ 1664 SCIP_BTNODE* parent /**< new parent node, or NULL */ 1665 ); 1666 1667 /** sets left child 1668 * 1669 * @note The old left child including the rooted subtree is not delete. 1670 */ 1671 SCIP_EXPORT 1672 void SCIPbtnodeSetLeftchild( 1673 SCIP_BTNODE* node, /**< node */ 1674 SCIP_BTNODE* left /**< new left child, or NULL */ 1675 ); 1676 1677 /** sets right child 1678 * 1679 * @note The old right child including the rooted subtree is not delete. 1680 */ 1681 SCIP_EXPORT 1682 void SCIPbtnodeSetRightchild( 1683 SCIP_BTNODE* node, /**< node */ 1684 SCIP_BTNODE* right /**< new right child, or NULL */ 1685 ); 1686 1687 /** creates an binary tree */ 1688 SCIP_EXPORT 1689 SCIP_RETCODE SCIPbtCreate( 1690 SCIP_BT** tree, /**< pointer to store the created binary tree */ 1691 BMS_BLKMEM* blkmem /**< block memory used to create nodes */ 1692 ); 1693 1694 /** frees binary tree 1695 * 1696 * @note The user pointers (object) of the search nodes are not freed. If needed, it has to be done by the user. 1697 */ 1698 SCIP_EXPORT 1699 void SCIPbtFree( 1700 SCIP_BT** tree /**< pointer to binary tree */ 1701 ); 1702 1703 /** prints the binary tree in GML format into the given file */ 1704 SCIP_EXPORT 1705 void SCIPbtPrintGml( 1706 SCIP_BT* tree, /**< binary tree */ 1707 FILE* file /**< file to write to */ 1708 ); 1709 1710 /** returns whether the binary tree is empty (has no nodes) */ 1711 SCIP_EXPORT 1712 SCIP_Bool SCIPbtIsEmpty( 1713 SCIP_BT * tree /**< binary tree */ 1714 ); 1715 1716 /** returns the root node of the binary tree or NULL if the binary tree is empty */ 1717 SCIP_EXPORT 1718 SCIP_BTNODE* SCIPbtGetRoot( 1719 SCIP_BT* tree /**< tree to be evaluated */ 1720 ); 1721 1722 #ifdef NDEBUG 1723 1724 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and 1725 * speed up the algorithms. 1726 */ 1727 1728 #define SCIPbtIsEmpty(tree) (tree->root == NULL) 1729 #define SCIPbtGetRoot(tree) (tree->root) 1730 1731 #endif 1732 1733 /** sets root node 1734 * 1735 * @note The old root including the rooted subtree is not delete. 1736 */ 1737 SCIP_EXPORT 1738 void SCIPbtSetRoot( 1739 SCIP_BT* tree, /**< tree to be evaluated */ 1740 SCIP_BTNODE* root /**< new root, or NULL */ 1741 ); 1742 1743 /**@} */ 1744 1745 /**@addtogroup DisjointSet 1746 * 1747 * @{ 1748 */ 1749 1750 /* 1751 * disjoint set data structure 1752 */ 1753 1754 /** clears the disjoint set (union find) structure \p djset */ 1755 SCIP_EXPORT 1756 void SCIPdisjointsetClear( 1757 SCIP_DISJOINTSET* djset /**< disjoint set (union find) data structure */ 1758 ); 1759 1760 /** finds and returns the component identifier of this \p element */ 1761 SCIP_EXPORT 1762 int SCIPdisjointsetFind( 1763 SCIP_DISJOINTSET* djset, /**< disjoint set (union find) data structure */ 1764 int element /**< element to be found */ 1765 ); 1766 1767 /** merges the components containing the elements \p p and \p q */ 1768 SCIP_EXPORT 1769 void SCIPdisjointsetUnion( 1770 SCIP_DISJOINTSET* djset, /**< disjoint set (union find) data structure */ 1771 int p, /**< first element */ 1772 int q, /**< second element */ 1773 SCIP_Bool forcerepofp /**< force representative of p to be new representative */ 1774 ); 1775 1776 /** returns the number of independent components in this disjoint set (union find) data structure */ 1777 SCIP_EXPORT 1778 int SCIPdisjointsetGetComponentCount( 1779 SCIP_DISJOINTSET* djset /**< disjoint set (union find) data structure */ 1780 ); 1781 1782 /** returns the size (number of nodes) of this disjoint set (union find) data structure */ 1783 SCIP_EXPORT 1784 int SCIPdisjointsetGetSize( 1785 SCIP_DISJOINTSET* djset /**< disjoint set (union find) data structure */ 1786 ); 1787 1788 /** @} */ 1789 1790 /* 1791 * Numerical methods 1792 */ 1793 1794 /**@defgroup NumericalMethods Numerical Methods 1795 * @ingroup MiscellaneousMethods 1796 * @brief commonly used numerical methods 1797 * 1798 * @{ 1799 */ 1800 1801 /** returns the machine epsilon: the smallest number eps > 0, for which 1.0 + eps > 1.0 */ 1802 SCIP_EXPORT 1803 SCIP_Real SCIPcalcMachineEpsilon( 1804 void 1805 ); 1806 1807 /** returns the next representable value of from in the direction of to */ 1808 SCIP_EXPORT 1809 SCIP_Real SCIPnextafter( 1810 SCIP_Real from, /**< value from which the next representable value should be returned */ 1811 SCIP_Real to /**< direction in which the next representable value should be returned */ 1812 ); 1813 1814 /** calculates the greatest common divisor of the two given values */ 1815 SCIP_EXPORT 1816 SCIP_Longint SCIPcalcGreComDiv( 1817 SCIP_Longint val1, /**< first value of greatest common devisor calculation */ 1818 SCIP_Longint val2 /**< second value of greatest common devisor calculation */ 1819 ); 1820 1821 /** calculates the smallest common multiple of the two given values */ 1822 SCIP_EXPORT 1823 SCIP_Longint SCIPcalcSmaComMul( 1824 SCIP_Longint val1, /**< first value of smallest common multiple calculation */ 1825 SCIP_Longint val2 /**< second value of smallest common multiple calculation */ 1826 ); 1827 1828 /** calculates a binomial coefficient n over m, choose m elements out of n, maximal value will be 33 over 16 (because 1829 * the n=33 is the last line in the Pascal's triangle where each entry fits in a 4 byte value), an error occurs due to 1830 * big numbers or an negative value m (and m < n) and -1 will be returned 1831 */ 1832 SCIP_EXPORT 1833 SCIP_Longint SCIPcalcBinomCoef( 1834 int n, /**< number of different elements */ 1835 int m /**< number to choose out of the above */ 1836 ); 1837 1838 /** calculates hash for floating-point number by using Fibonacci hashing */ 1839 SCIP_EXPORT 1840 unsigned int SCIPcalcFibHash( 1841 SCIP_Real v /**< number to hash */ 1842 ); 1843 1844 #ifdef NDEBUG 1845 1846 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and 1847 * speed up the algorithms. 1848 */ 1849 1850 #define SCIPcalcFibHash(v) ((v) >= 0 ? ((unsigned long long)((v) * 2654435769)) % UINT_MAX : ((unsigned long long)(-(v) * 683565275)) % UINT_MAX ) 1851 1852 #endif 1853 1854 /** converts a real number into a (approximate) rational representation, and returns TRUE iff the conversion was 1855 * successful 1856 */ 1857 SCIP_EXPORT 1858 SCIP_Bool SCIPrealToRational( 1859 SCIP_Real val, /**< real value r to convert into rational number */ 1860 SCIP_Real mindelta, /**< minimal allowed difference r - q of real r and rational q = n/d */ 1861 SCIP_Real maxdelta, /**< maximal allowed difference r - q of real r and rational q = n/d */ 1862 SCIP_Longint maxdnom, /**< maximal denominator allowed */ 1863 SCIP_Longint* nominator, /**< pointer to store the nominator n of the rational number */ 1864 SCIP_Longint* denominator /**< pointer to store the denominator d of the rational number */ 1865 ); 1866 1867 /** tries to find a value, such that all given values, if scaled with this value become integral in relative allowed 1868 * difference in between mindelta and maxdelta 1869 */ 1870 SCIP_EXPORT 1871 SCIP_RETCODE SCIPcalcIntegralScalar( 1872 SCIP_Real* vals, /**< values to scale */ 1873 int nvals, /**< number of values to scale */ 1874 SCIP_Real mindelta, /**< minimal relative allowed difference of scaled coefficient s*c and integral i */ 1875 SCIP_Real maxdelta, /**< maximal relative allowed difference of scaled coefficient s*c and integral i */ 1876 SCIP_Longint maxdnom, /**< maximal denominator allowed in rational numbers */ 1877 SCIP_Real maxscale, /**< maximal allowed scalar */ 1878 SCIP_Real* intscalar, /**< pointer to store scalar that would make the coefficients integral, or NULL */ 1879 SCIP_Bool* success /**< stores whether returned value is valid */ 1880 ); 1881 1882 /** given a (usually very small) interval, tries to find a rational number with simple denominator (i.e. a small 1883 * number, probably multiplied with powers of 10) out of this interval; returns TRUE iff a valid rational 1884 * number inside the interval was found 1885 */ 1886 SCIP_EXPORT 1887 SCIP_Bool SCIPfindSimpleRational( 1888 SCIP_Real lb, /**< lower bound of the interval */ 1889 SCIP_Real ub, /**< upper bound of the interval */ 1890 SCIP_Longint maxdnom, /**< maximal denominator allowed for resulting rational number */ 1891 SCIP_Longint* nominator, /**< pointer to store the nominator n of the rational number */ 1892 SCIP_Longint* denominator /**< pointer to store the denominator d of the rational number */ 1893 ); 1894 1895 /** given a (usually very small) interval, selects a value inside this interval; it is tried to select a rational number 1896 * with simple denominator (i.e. a small number, probably multiplied with powers of 10); 1897 * if no valid rational number inside the interval was found, selects the central value of the interval 1898 */ 1899 SCIP_EXPORT 1900 SCIP_Real SCIPselectSimpleValue( 1901 SCIP_Real lb, /**< lower bound of the interval */ 1902 SCIP_Real ub, /**< upper bound of the interval */ 1903 SCIP_Longint maxdnom /**< maximal denominator allowed for resulting rational number */ 1904 ); 1905 1906 /** Performs the Newton Procedure from a given starting point to compute a root of the given function with 1907 * specified precision and maximum number of iterations. If the procedure fails, SCIP_INVALID is returned. 1908 */ 1909 SCIP_EXPORT 1910 SCIP_Real SCIPcalcRootNewton( 1911 SCIP_DECL_NEWTONEVAL((*function)), /**< pointer to function for which roots are computed */ 1912 SCIP_DECL_NEWTONEVAL((*derivative)), /**< pointer to derivative of above function */ 1913 SCIP_Real* params, /**< parameters needed for function (can be NULL) */ 1914 int nparams, /**< number of parameters (can be 0) */ 1915 SCIP_Real x, /**< starting point */ 1916 SCIP_Real eps, /**< tolerance */ 1917 int k /**< iteration limit */ 1918 ); 1919 1920 /* The C99 standard defines the function (or macro) isfinite. 1921 * On MacOS X, isfinite is also available. 1922 * From the BSD world, there comes a function finite. 1923 * On SunOS, finite is also available. 1924 * In the MS compiler world, there is a function _finite. 1925 * As last resort, we check whether x == x does not hold, but this works only for NaN's, not for infinities! 1926 */ 1927 #if _XOPEN_SOURCE >= 600 || defined(_ISOC99_SOURCE) || _POSIX_C_SOURCE >= 200112L || defined(__APPLE__) 1928 #define SCIPisFinite isfinite 1929 #elif defined(_BSD_SOURCE) || defined(__sun) 1930 #define SCIPisFinite finite 1931 #elif defined(_MSC_VER) 1932 #define SCIPisFinite _finite 1933 #else 1934 #define SCIPisFinite(x) ((x) == (x)) 1935 #endif 1936 1937 /* In debug mode, the following methods are implemented as function calls to ensure 1938 * type validity. 1939 */ 1940 1941 /** returns the relative difference: (val1-val2)/max(|val1|,|val2|,1.0) */ 1942 SCIP_EXPORT 1943 SCIP_Real SCIPrelDiff( 1944 SCIP_Real val1, /**< first value to be compared */ 1945 SCIP_Real val2 /**< second value to be compared */ 1946 ); 1947 1948 #ifdef NDEBUG 1949 1950 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and 1951 * speed up the algorithms. 1952 */ 1953 1954 #define SCIPrelDiff(val1, val2) ( ((val1)-(val2))/(MAX3(1.0,REALABS(val1),REALABS(val2))) ) 1955 1956 #endif 1957 1958 /** computes the gap from the primal and the dual bound */ 1959 SCIP_EXPORT 1960 SCIP_Real SCIPcomputeGap( 1961 SCIP_Real eps, /**< the value treated as zero */ 1962 SCIP_Real inf, /**< the value treated as infinity */ 1963 SCIP_Real primalbound, /**< the primal bound */ 1964 SCIP_Real dualbound /**< the dual bound */ 1965 ); 1966 1967 /**@} */ 1968 1969 1970 /* 1971 * Random Numbers 1972 */ 1973 1974 /**@defgroup RandomNumbers Random Numbers 1975 * @ingroup MiscellaneousMethods 1976 * @brief structures and methods for pseudo random number generation 1977 * 1978 *@{ 1979 */ 1980 1981 /** returns a random integer between minrandval and maxrandval 1982 * 1983 * @deprecated Please use SCIPrandomGetInt() to request a random integer. 1984 */ 1985 SCIP_EXPORT 1986 SCIP_DEPRECATED 1987 int SCIPgetRandomInt( 1988 int minrandval, /**< minimal value to return */ 1989 int maxrandval, /**< maximal value to return */ 1990 unsigned int* seedp /**< pointer to seed value */ 1991 ); 1992 1993 1994 /** returns a random integer between minrandval and maxrandval */ 1995 SCIP_EXPORT 1996 int SCIPrandomGetInt( 1997 SCIP_RANDNUMGEN* randgen, /**< random number generator data */ 1998 int minrandval, /**< minimal value to return */ 1999 int maxrandval /**< maximal value to return */ 2000 ); 2001 2002 /** draws a random subset of disjoint elements from a given set of disjoint elements; 2003 * this implementation is suited for the case that nsubelems is considerably smaller then nelems 2004 */ 2005 SCIP_EXPORT 2006 SCIP_RETCODE SCIPrandomGetSubset( 2007 SCIP_RANDNUMGEN* randgen, /**< random number generator */ 2008 void** set, /**< original set, from which elements should be drawn */ 2009 int nelems, /**< number of elements in original set */ 2010 void** subset, /**< subset in which drawn elements should be stored */ 2011 int nsubelems /**< number of elements that should be drawn and stored */ 2012 ); 2013 2014 /** returns a random real between minrandval and maxrandval */ 2015 SCIP_EXPORT 2016 SCIP_Real SCIPrandomGetReal( 2017 SCIP_RANDNUMGEN* randgen, /**< random number generator data */ 2018 SCIP_Real minrandval, /**< minimal value to return */ 2019 SCIP_Real maxrandval /**< maximal value to return */ 2020 ); 2021 2022 /** returns a random real between minrandval and maxrandval 2023 * 2024 * @deprecated Please use SCIPrandomGetReal() to request a random real. 2025 */ 2026 SCIP_EXPORT 2027 SCIP_DEPRECATED 2028 SCIP_Real SCIPgetRandomReal( 2029 SCIP_Real minrandval, /**< minimal value to return */ 2030 SCIP_Real maxrandval, /**< maximal value to return */ 2031 unsigned int* seedp /**< pointer to seed value */ 2032 ); 2033 2034 /** draws a random subset of disjoint elements from a given set of disjoint elements; 2035 * this implementation is suited for the case that nsubelems is considerably smaller then nelems 2036 * 2037 * @deprecated Please use SCIPrandomGetSubset() 2038 */ 2039 SCIP_EXPORT 2040 SCIP_DEPRECATED 2041 SCIP_RETCODE SCIPgetRandomSubset( 2042 void** set, /**< original set, from which elements should be drawn */ 2043 int nelems, /**< number of elements in original set */ 2044 void** subset, /**< subset in which drawn elements should be stored */ 2045 int nsubelems, /**< number of elements that should be drawn and stored */ 2046 unsigned int randseed /**< seed value for random generator */ 2047 ); 2048 2049 /**@} */ 2050 2051 /* 2052 * Permutations / Shuffling 2053 */ 2054 2055 /**@defgroup PermutationsShuffling Permutations Shuffling 2056 * @ingroup MiscellaneousMethods 2057 * @brief methods for shuffling arrays 2058 * 2059 * @{ 2060 */ 2061 2062 /** swaps two ints */ 2063 SCIP_EXPORT 2064 void SCIPswapInts( 2065 int* value1, /**< pointer to first integer */ 2066 int* value2 /**< pointer to second integer */ 2067 ); 2068 2069 /** swaps two real values */ 2070 SCIP_EXPORT 2071 void SCIPswapReals( 2072 SCIP_Real* value1, /**< pointer to first real value */ 2073 SCIP_Real* value2 /**< pointer to second real value */ 2074 ); 2075 2076 /** swaps the addresses of two pointers */ 2077 SCIP_EXPORT 2078 void SCIPswapPointers( 2079 void** pointer1, /**< first pointer */ 2080 void** pointer2 /**< second pointer */ 2081 ); 2082 2083 /** randomly shuffles parts of an integer array using the Fisher-Yates algorithm 2084 * 2085 * @deprecated Please use SCIPrandomPermuteIntArray() 2086 */ 2087 SCIP_EXPORT 2088 SCIP_DEPRECATED 2089 void SCIPpermuteIntArray( 2090 int* array, /**< array to be shuffled */ 2091 int begin, /**< first included index that should be subject to shuffling 2092 * (0 for first array entry) 2093 */ 2094 int end, /**< first excluded index that should not be subject to shuffling 2095 * (array size for last array entry) 2096 */ 2097 unsigned int* randseed /**< seed value for the random generator */ 2098 ); 2099 2100 /** randomly shuffles parts of an integer array using the Fisher-Yates algorithm */ 2101 SCIP_EXPORT 2102 void SCIPrandomPermuteIntArray( 2103 SCIP_RANDNUMGEN* randgen, /**< random number generator */ 2104 int* array, /**< array to be shuffled */ 2105 int begin, /**< first included index that should be subject to shuffling 2106 * (0 for first array entry) 2107 */ 2108 int end /**< first excluded index that should not be subject to shuffling 2109 * (array size for last array entry) 2110 */ 2111 ); 2112 2113 /** randomly shuffles parts of an array using the Fisher-Yates algorithm */ 2114 SCIP_EXPORT 2115 void SCIPrandomPermuteArray( 2116 SCIP_RANDNUMGEN* randgen, /**< random number generator */ 2117 void** array, /**< array to be shuffled */ 2118 int begin, /**< first included index that should be subject to shuffling 2119 * (0 for first array entry) 2120 */ 2121 int end /**< first excluded index that should not be subject to shuffling 2122 * (array size for last array entry) 2123 */ 2124 ); 2125 2126 /** randomly shuffles parts of an array using the Fisher-Yates algorithm 2127 * 2128 * @deprecated Please use SCIPrandomPermuteArray() 2129 */ 2130 SCIP_EXPORT 2131 SCIP_DEPRECATED 2132 void SCIPpermuteArray( 2133 void** array, /**< array to be shuffled */ 2134 int begin, /**< first included index that should be subject to shuffling 2135 * (0 for first array entry) 2136 */ 2137 int end, /**< first excluded index that should not be subject to shuffling 2138 * (array size for last array entry) 2139 */ 2140 unsigned int* randseed /**< pointer to seed value for the random generator */ 2141 ); 2142 2143 /**@} */ 2144 2145 2146 /* 2147 * Arrays 2148 */ 2149 2150 /**@defgroup Arrays Arrays 2151 * @ingroup MiscellaneousMethods 2152 * @brief miscellaneous methods for arrays 2153 * 2154 * @{ 2155 */ 2156 2157 2158 /** computes set intersection (duplicates removed) of two integer arrays that are ordered ascendingly 2159 * 2160 * @deprecated Switch to SCIPcomputeArraysIntersectionInt(). 2161 */ 2162 SCIP_DEPRECATED 2163 SCIP_EXPORT 2164 SCIP_RETCODE SCIPcomputeArraysIntersection( 2165 int* array1, /**< first array (in ascending order) */ 2166 int narray1, /**< number of entries of first array */ 2167 int* array2, /**< second array (in ascending order) */ 2168 int narray2, /**< number of entries of second array */ 2169 int* intersectarray, /**< intersection of array1 and array2 2170 * (note: it is possible to use array1 for this input argument) */ 2171 int* nintersectarray /**< pointer to store number of entries of intersection array 2172 * (note: it is possible to use narray1 for this input argument) */ 2173 ); 2174 2175 /** computes set intersection (duplicates removed) of two integer arrays that are ordered ascendingly */ 2176 SCIP_EXPORT 2177 void SCIPcomputeArraysIntersectionInt( 2178 int* array1, /**< first array (in ascending order) */ 2179 int narray1, /**< number of entries of first array */ 2180 int* array2, /**< second array (in ascending order) */ 2181 int narray2, /**< number of entries of second array */ 2182 int* intersectarray, /**< intersection of array1 and array2 2183 * (note: it is possible to use array1 for this input argument) */ 2184 int* nintersectarray /**< pointer to store number of entries of intersection array 2185 * (note: it is possible to use narray1 for this input argument) */ 2186 ); 2187 2188 /** computes set intersection (duplicates removed) of two void-pointer arrays that are ordered ascendingly */ 2189 SCIP_EXPORT 2190 void SCIPcomputeArraysIntersectionPtr( 2191 void** array1, /**< first array (in ascending order) */ 2192 int narray1, /**< number of entries of first array */ 2193 void** array2, /**< second array (in ascending order) */ 2194 int narray2, /**< number of entries of second array */ 2195 SCIP_DECL_SORTPTRCOMP((*ptrcomp)), /**< data element comparator */ 2196 void** intersectarray, /**< intersection of array1 and array2 2197 * (note: it is possible to use array1 for this input argument) */ 2198 int* nintersectarray /**< pointer to store number of entries of intersection array 2199 * (note: it is possible to use narray1 for this input argument) */ 2200 ); 2201 2202 /** computes set difference (duplicates removed) of two integer arrays that are ordered ascendingly 2203 * 2204 * @deprecated Switch to SCIPcomputeArraysSetminusInt(). 2205 */ 2206 SCIP_DEPRECATED 2207 SCIP_EXPORT 2208 SCIP_RETCODE SCIPcomputeArraysSetminus( 2209 int* array1, /**< first array (in ascending order) */ 2210 int narray1, /**< number of entries of first array */ 2211 int* array2, /**< second array (in ascending order) */ 2212 int narray2, /**< number of entries of second array */ 2213 int* setminusarray, /**< array to store entries of array1 that are not an entry of array2 2214 * (note: it is possible to use array1 for this input argument) */ 2215 int* nsetminusarray /**< pointer to store number of entries of setminus array 2216 * (note: it is possible to use narray1 for this input argument) */ 2217 ); 2218 2219 /** computes set difference (duplicates removed) of two integer arrays that are ordered ascendingly */ 2220 SCIP_EXPORT 2221 void SCIPcomputeArraysSetminusInt( 2222 int* array1, /**< first array (in ascending order) */ 2223 int narray1, /**< number of entries of first array */ 2224 int* array2, /**< second array (in ascending order) */ 2225 int narray2, /**< number of entries of second array */ 2226 int* setminusarray, /**< array to store entries of array1 that are not an entry of array2 2227 * (note: it is possible to use array1 for this input argument) */ 2228 int* nsetminusarray /**< pointer to store number of entries of setminus array 2229 * (note: it is possible to use narray1 for this input argument) */ 2230 ); 2231 2232 /**@} */ 2233 2234 2235 /* 2236 * Strings 2237 */ 2238 2239 /**@defgroup StringMethods String Methods 2240 * @ingroup MiscellaneousMethods 2241 * @brief commonly used methods for strings 2242 * 2243 *@{ 2244 */ 2245 2246 /** copies characters from 'src' to 'dest', copying is stopped when either the 'stop' character is reached or after 2247 * 'cnt' characters have been copied, whichever comes first. 2248 * 2249 * @note undefined behaviuor on overlapping arrays 2250 */ 2251 SCIP_EXPORT 2252 int SCIPmemccpy( 2253 char* dest, /**< destination pointer to copy to */ 2254 const char* src, /**< source pointer to copy to */ 2255 char stop, /**< character when found stop copying */ 2256 unsigned int cnt /**< maximal number of characters to copy too */ 2257 ); 2258 2259 /** prints an error message containing of the given string followed by a string describing the current system error; 2260 * prefers to use the strerror_r method, which is threadsafe; on systems where this method does not exist, 2261 * NO_STRERROR_R should be defined (see INSTALL), in this case, srerror is used which is not guaranteed to be 2262 * threadsafe (on SUN-systems, it actually is) 2263 */ 2264 SCIP_EXPORT 2265 void SCIPprintSysError( 2266 const char* message /**< first part of the error message, e.g. the filename */ 2267 ); 2268 2269 /** extracts tokens from strings - wrapper method for strtok_r() */ 2270 SCIP_EXPORT 2271 char* SCIPstrtok( 2272 char* s, /**< string to parse */ 2273 const char* delim, /**< delimiters for parsing */ 2274 char** ptrptr /**< pointer to working char pointer - must stay the same while parsing */ 2275 ); 2276 2277 /** translates the given string into a string where symbols ", ', and spaces are escaped with a \ prefix */ 2278 SCIP_EXPORT 2279 void SCIPescapeString( 2280 char* t, /**< target buffer to store escaped string */ 2281 int bufsize, /**< size of buffer t */ 2282 const char* s /**< string to transform into escaped string */ 2283 ); 2284 2285 /** increases string pointer as long as it refers to a space character or an explicit space control sequence */ 2286 SCIP_EXPORT 2287 SCIP_RETCODE SCIPskipSpace( 2288 char** s /**< pointer to string pointer */ 2289 ); 2290 2291 /** safe version of snprintf */ 2292 SCIP_EXPORT 2293 int SCIPsnprintf( 2294 char* t, /**< target string */ 2295 int len, /**< length of the string to copy */ 2296 const char* s, /**< source string */ 2297 ... /**< further parameters */ 2298 ); 2299 2300 /** safe version of strncpy 2301 * 2302 * Copies string in s to t using at most @a size-1 nonzero characters (strncpy copies size characters). It always adds 2303 * a terminating zero char. Does not pad the remaining string with zero characters (unlike strncpy). Returns the number 2304 * of copied nonzero characters, if the length of s is at most size - 1, and returns size otherwise. Thus, the original 2305 * string was truncated if the return value is size. 2306 */ 2307 SCIP_EXPORT 2308 int SCIPstrncpy( 2309 char* t, /**< target string */ 2310 const char* s, /**< source string */ 2311 int size /**< maximal size of t */ 2312 ); 2313 2314 /** extract the next token as a integer value if it is one; in case no value is parsed the endptr is set to @p str 2315 * 2316 * @return Returns TRUE if a value could be extracted, otherwise FALSE 2317 */ 2318 SCIP_EXPORT 2319 SCIP_Bool SCIPstrToIntValue( 2320 const char* str, /**< string to search */ 2321 int* value, /**< pointer to store the parsed value */ 2322 char** endptr /**< pointer to store the final string position if successfully parsed, otherwise @p str */ 2323 ); 2324 2325 /** extract the next token as a double value if it is one; in case a value is parsed the endptr is set to @p str 2326 * 2327 * @return Returns TRUE if a value could be extracted, otherwise FALSE 2328 */ 2329 SCIP_EXPORT 2330 SCIP_Bool SCIPstrToRealValue( 2331 const char* str, /**< string to search */ 2332 SCIP_Real* value, /**< pointer to store the parsed value */ 2333 char** endptr /**< pointer to store the final string position if successfully parsed, otherwise @p str */ 2334 ); 2335 2336 /** copies the first size characters between a start and end character of str into token, if no error occurred endptr 2337 * will point to the position after the read part, otherwise it will point to @p str 2338 */ 2339 SCIP_EXPORT 2340 void SCIPstrCopySection( 2341 const char* str, /**< string to search */ 2342 char startchar, /**< character which defines the beginning */ 2343 char endchar, /**< character which defines the ending */ 2344 char* token, /**< string to store the copy */ 2345 int size, /**< size of the token char array */ 2346 char** endptr /**< pointer to store the final string position if successfully parsed, otherwise @p str */ 2347 ); 2348 2349 /** checks whether a given string t appears at the beginning of the string s (up to spaces at beginning) */ 2350 SCIP_EXPORT 2351 SCIP_Bool SCIPstrAtStart( 2352 const char* s, /**< string to search in */ 2353 const char* t, /**< string to search for */ 2354 size_t tlen /**< length of t */ 2355 ); 2356 2357 /**@} */ 2358 2359 /* 2360 * File methods 2361 */ 2362 2363 /**@defgroup FileMethods File Methods 2364 * @ingroup MiscellaneousMethods 2365 * @brief commonly used file methods 2366 * 2367 * @{ 2368 */ 2369 2370 /** returns, whether the given file exists */ 2371 SCIP_EXPORT 2372 SCIP_Bool SCIPfileExists( 2373 const char* filename /**< file name */ 2374 ); 2375 2376 /** splits filename into path, name, and extension */ 2377 SCIP_EXPORT 2378 void SCIPsplitFilename( 2379 char* filename, /**< filename to split; is destroyed (but not freed) during process */ 2380 char** path, /**< pointer to store path, or NULL if not needed */ 2381 char** name, /**< pointer to store name, or NULL if not needed */ 2382 char** extension, /**< pointer to store extension, or NULL if not needed */ 2383 char** compression /**< pointer to store compression extension, or NULL if not needed */ 2384 ); 2385 2386 /**@} */ 2387 2388 #ifdef __cplusplus 2389 } 2390 #endif 2391 2392 #endif 2393