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