Scippy

SCIP

Solving Constraint Integer Programs

pub_misc.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (c) 2002-2024 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
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
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
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
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
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
147  SCIP_REGRESSION* regression /**< regression data structure */
148  );
149 
150 /** return the current slope of the regression */
151 SCIP_EXPORT
153  SCIP_REGRESSION* regression /**< regression data structure */
154  );
155 
156 /** get the current y-intercept of the regression */
157 SCIP_EXPORT
159  SCIP_REGRESSION* regression /**< regression data structure */
160  );
161 
162 /** removes an observation (x,y) from the regression */
163 SCIP_EXPORT
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
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
181  SCIP_REGRESSION* regression /**< regression data structure */
182  );
183 
184 /** creates and resets a regression */
185 SCIP_EXPORT
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
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
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
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
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
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
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
330  SCIP_SPARSESOL* sparsesol /**< a sparse solution */
331  );
332 
333 /** returns the number of variables in the given sparse solution */
334 SCIP_EXPORT
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
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
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
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
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
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
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
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
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
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
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
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 void SCIPhashtableClear(
609  SCIP_HASHTABLE* hashtable /**< hash table */
610  );
611 
612 /** inserts element in hash table (multiple inserts of same element override the previous entry) */
613 SCIP_EXPORT
615  SCIP_HASHTABLE* hashtable, /**< hash table */
616  void* element /**< element to insert into the table */
617  );
618 
619 /** inserts element in hash table (multiple insertion of same element is checked and results in an error) */
620 SCIP_EXPORT
622  SCIP_HASHTABLE* hashtable, /**< hash table */
623  void* element /**< element to insert into the table */
624  );
625 
626 /** retrieve element with key from hash table, returns NULL if not existing */
627 SCIP_EXPORT
629  SCIP_HASHTABLE* hashtable, /**< hash table */
630  void* key /**< key to retrieve */
631  );
632 
633 /** returns whether the given element exists in the table */
634 SCIP_EXPORT
636  SCIP_HASHTABLE* hashtable, /**< hash table */
637  void* element /**< element to search in the table */
638  );
639 
640 /** removes element from the hash table, if it exists */
641 SCIP_EXPORT
643  SCIP_HASHTABLE* hashtable, /**< hash table */
644  void* element /**< element to remove from the table */
645  );
646 
647 /** removes all elements of the hash table */
648 SCIP_EXPORT
650  SCIP_HASHTABLE* hashtable /**< hash table */
651  );
652 
653 /** returns number of hash table elements */
654 SCIP_EXPORT
656  SCIP_HASHTABLE* hashtable /**< hash table */
657  );
658 
659 /** gives the number of entries in the internal arrays of a hash table */
660 SCIP_EXPORT
662  SCIP_HASHTABLE* hashtable /**< hash table */
663  );
664 
665 /** gives the element at the given index or NULL if entry at that index has no element */
666 SCIP_EXPORT
668  SCIP_HASHTABLE* hashtable, /**< hash table */
669  int entryidx /**< index of hash table entry */
670  );
671 
672 /** returns the load of the given hash table in percentage */
673 SCIP_EXPORT
675  SCIP_HASHTABLE* hashtable /**< hash table */
676  );
677 
678 /** prints statistics about hash table usage */
679 SCIP_EXPORT
681  SCIP_HASHTABLE* hashtable, /**< hash table */
682  SCIP_MESSAGEHDLR* messagehdlr /**< message handler */
683  );
684 
685 /**@} */
686 
687 /*
688  * MultiHash Table
689  */
690 
691 /**@defgroup MultiHash Multi Hash table
692  * @ingroup DataStructures
693  * @brief hash table that resolves conflicts by queueing, thereby allowing for duplicate entries
694  *
695  *@{
696  */
697 
698 /** returns a reasonable hash table size (a prime number) that is at least as large as the specified value */
699 SCIP_EXPORT
701  int minsize /**< minimal size of the hash table */
702  );
703 
704 /** creates a multihash table */
705 SCIP_EXPORT
707  SCIP_MULTIHASH** multihash, /**< pointer to store the created multihash table */
708  BMS_BLKMEM* blkmem, /**< block memory used to store multihash table entries */
709  int tablesize, /**< size of the hash table */
710  SCIP_DECL_HASHGETKEY((*hashgetkey)), /**< gets the key of the given element */
711  SCIP_DECL_HASHKEYEQ ((*hashkeyeq)), /**< returns TRUE iff both keys are equal */
712  SCIP_DECL_HASHKEYVAL((*hashkeyval)), /**< returns the hash value of the key */
713  void* userptr /**< user pointer */
714  );
715 
716 /** frees the multihash table */
717 SCIP_EXPORT
718 void SCIPmultihashFree(
719  SCIP_MULTIHASH** multihash /**< pointer to the multihash table */
720  );
721 
722 /** inserts element in multihash table (multiple inserts of same element possible)
723  *
724  * @note A pointer to a multihashlist returned by SCIPmultihashRetrieveNext() might get invalid when adding an element
725  * to the hash table, due to dynamic resizing.
726  */
727 SCIP_EXPORT
729  SCIP_MULTIHASH* multihash, /**< multihash table */
730  void* element /**< element to insert into the table */
731  );
732 
733 /** inserts element in multihash table (multiple insertion of same element is checked and results in an error)
734  *
735  * @note A pointer to a multihashlist returned by SCIPmultihashRetrieveNext() might get invalid when adding a new
736  * element to the multihash table, due to dynamic resizing.
737  */
738 SCIP_EXPORT
740  SCIP_MULTIHASH* multihash, /**< multihash table */
741  void* element /**< element to insert into the table */
742  );
743 
744 /** retrieve element with key from multihash table, returns NULL if not existing */
745 SCIP_EXPORT
747  SCIP_MULTIHASH* multihash, /**< multihash table */
748  void* key /**< key to retrieve */
749  );
750 
751 /** retrieve element with key from multihash table, returns NULL if not existing
752  * can be used to retrieve all entries with the same key (one-by-one)
753  *
754  * @note The returned multimultihashlist pointer might get invalid when adding a new element to the multihash table.
755  */
756 SCIP_EXPORT
758  SCIP_MULTIHASH* multihash, /**< multihash table */
759  SCIP_MULTIHASHLIST** multihashlist, /**< input: entry in hash table list from which to start searching, or NULL
760  * output: entry in hash table list corresponding to element after
761  * retrieved one, or NULL */
762  void* key /**< key to retrieve */
763  );
764 
765 /** returns whether the given element exists in the multihash table */
766 SCIP_EXPORT
768  SCIP_MULTIHASH* multihash, /**< multihash table */
769  void* element /**< element to search in the table */
770  );
771 
772 /** removes element from the multihash table, if it exists */
773 SCIP_EXPORT
775  SCIP_MULTIHASH* multihash, /**< multihash table */
776  void* element /**< element to remove from the table */
777  );
778 
779 /** removes all elements of the multihash table
780  *
781  * @note From a performance point of view you should not fill and clear a hash table too often since the clearing can
782  * be expensive. Clearing is done by looping over all buckets and removing the hash table lists one-by-one.
783  */
784 SCIP_EXPORT
786  SCIP_MULTIHASH* multihash /**< multihash table */
787  );
788 
789 /** returns number of multihash table elements */
790 SCIP_EXPORT
792  SCIP_MULTIHASH* multihash /**< multihash table */
793  );
794 
795 /** returns the load of the given multihash table in percentage */
796 SCIP_EXPORT
798  SCIP_MULTIHASH* multihash /**< multihash table */
799  );
800 
801 /** prints statistics about multihash table usage */
802 SCIP_EXPORT
804  SCIP_MULTIHASH* multihash, /**< multihash table */
805  SCIP_MESSAGEHDLR* messagehdlr /**< message handler */
806  );
807 
808 /** standard hash key comparator for string keys */
809 SCIP_EXPORT
810 SCIP_DECL_HASHKEYEQ(SCIPhashKeyEqString);
811 
812 /** standard hashing function for string keys */
813 SCIP_EXPORT
814 SCIP_DECL_HASHKEYVAL(SCIPhashKeyValString);
815 
816 /** gets the element as the key */
817 SCIP_EXPORT
818 SCIP_DECL_HASHGETKEY(SCIPhashGetKeyStandard);
819 
820 /** returns TRUE iff both keys(pointer) are equal */
821 SCIP_EXPORT
822 SCIP_DECL_HASHKEYEQ(SCIPhashKeyEqPtr);
823 
824 /** returns the hash value of the key */
825 SCIP_EXPORT
826 SCIP_DECL_HASHKEYVAL(SCIPhashKeyValPtr);
827 
828 /**@} */
829 
830 
831 /*
832  * Hash Map
833  */
834 
835 /**@defgroup HashMap Hash Map
836  * @ingroup DataStructures
837  * @brief hash map to store key-value pairs (called \p origin and \p image)
838  *
839  * @{
840  */
841 
842 /** creates a hash map mapping pointers to pointers */
843 SCIP_EXPORT
845  SCIP_HASHMAP** hashmap, /**< pointer to store the created hash map */
846  BMS_BLKMEM* blkmem, /**< block memory used to store hash map entries */
847  int mapsize /**< size of the hash map */
848  );
849 
850 /** frees the hash map */
851 SCIP_EXPORT
852 void SCIPhashmapFree(
853  SCIP_HASHMAP** hashmap /**< pointer to the hash map */
854  );
855 
856 /** inserts new origin->image pair in hash map (must not be called for already existing origins!) */
857 SCIP_EXPORT
859  SCIP_HASHMAP* hashmap, /**< hash map */
860  void* origin, /**< origin to set image for */
861  void* image /**< new image for origin */
862  );
863 
864 /** inserts new origin->image pair in hash map (must not be called for already existing origins!) */
865 SCIP_EXPORT
867  SCIP_HASHMAP* hashmap, /**< hash map */
868  void* origin, /**< origin to set image for */
869  int image /**< new image for origin */
870  );
871 
872 /** inserts new origin->image pair in hash map (must not be called for already existing origins!) */
873 SCIP_EXPORT
875  SCIP_HASHMAP* hashmap, /**< hash map */
876  void* origin, /**< origin to set image for */
877  SCIP_Real image /**< new image for origin */
878  );
879 
880 /** retrieves image of given origin from the hash map, or NULL if no image exists */
881 SCIP_EXPORT
882 void* SCIPhashmapGetImage(
883  SCIP_HASHMAP* hashmap, /**< hash map */
884  void* origin /**< origin to retrieve image for */
885  );
886 
887 /** retrieves image of given origin from the hash map, or INT_MAX if no image exists */
888 SCIP_EXPORT
890  SCIP_HASHMAP* hashmap, /**< hash map */
891  void* origin /**< origin to retrieve image for */
892  );
893 
894 /** retrieves image of given origin from the hash map, or SCIP_INVALID if no image exists */
895 SCIP_EXPORT
897  SCIP_HASHMAP* hashmap, /**< hash map */
898  void* origin /**< origin to retrieve image for */
899  );
900 
901 /** sets image for given origin in the hash map, either by modifying existing origin->image pair or by appending a
902  * new origin->image pair
903  */
904 SCIP_EXPORT
906  SCIP_HASHMAP* hashmap, /**< hash map */
907  void* origin, /**< origin to set image for */
908  void* image /**< new image for origin */
909  );
910 
911 /** sets image for given origin in the hash map, either by modifying existing origin->image pair or by appending a
912  * new origin->image pair
913  */
914 SCIP_EXPORT
916  SCIP_HASHMAP* hashmap, /**< hash map */
917  void* origin, /**< origin to set image for */
918  int image /**< new image for origin */
919  );
920 
921 /** sets image for given origin in the hash map, either by modifying existing origin->image pair or by appending a
922  * new origin->image pair
923  */
924 SCIP_EXPORT
926  SCIP_HASHMAP* hashmap, /**< hash map */
927  void* origin, /**< origin to set image for */
928  SCIP_Real image /**< new image for origin */
929  );
930 
931 /** checks whether an image to the given origin exists in the hash map */
932 SCIP_EXPORT
934  SCIP_HASHMAP* hashmap, /**< hash map */
935  void* origin /**< origin to search for */
936  );
937 
938 /** removes origin->image pair from the hash map, if it exists */
939 SCIP_EXPORT
941  SCIP_HASHMAP* hashmap, /**< hash map */
942  void* origin /**< origin to remove from the list */
943  );
944 
945 /** prints statistics about hash map usage */
946 SCIP_EXPORT
948  SCIP_HASHMAP* hashmap, /**< hash map */
949  SCIP_MESSAGEHDLR* messagehdlr /**< message handler */
950  );
951 
952 /** indicates whether a hash map has no entries */
953 SCIP_EXPORT
955  SCIP_HASHMAP* hashmap /**< hash map */
956  );
957 
958 /** gives the number of elements in a hash map */
959 SCIP_EXPORT
961  SCIP_HASHMAP* hashmap /**< hash map */
962  );
963 
964 /** gives the number of entries in the internal arrays of a hash map */
965 SCIP_EXPORT
967  SCIP_HASHMAP* hashmap /**< hash map */
968  );
969 
970 /** gives the hashmap entry at the given index or NULL if entry has no element */
971 SCIP_EXPORT
973  SCIP_HASHMAP* hashmap, /**< hash map */
974  int entryidx /**< index of hash map entry */
975  );
976 
977 /** gives the origin of the hashmap entry */
978 SCIP_EXPORT
980  SCIP_HASHMAPENTRY* entry /**< hash map entry */
981  );
982 
983 /** gives the image of the hashmap entry */
984 SCIP_EXPORT
986  SCIP_HASHMAPENTRY* entry /**< hash map entry */
987  );
988 
989 /** gives the image of the hashmap entry */
990 SCIP_EXPORT
992  SCIP_HASHMAPENTRY* entry /**< hash map entry */
993  );
994 
995 /** gives the image of the hashmap entry */
996 SCIP_EXPORT
998  SCIP_HASHMAPENTRY* entry /**< hash map entry */
999  );
1000 
1001 /** sets pointer image of a hashmap entry */
1002 SCIP_EXPORT
1004  SCIP_HASHMAPENTRY* entry, /**< hash map entry */
1005  void* image /**< new image */
1006  );
1007 
1008 /** sets integer image of a hashmap entry */
1009 SCIP_EXPORT
1011  SCIP_HASHMAPENTRY* entry, /**< hash map entry */
1012  int image /**< new image */
1013  );
1014 
1015 /** sets real image of a hashmap entry */
1016 SCIP_EXPORT
1018  SCIP_HASHMAPENTRY* entry, /**< hash map entry */
1019  SCIP_Real image /**< new image */
1020  );
1021 
1022 /** removes all entries in a hash map. */
1023 SCIP_EXPORT
1025  SCIP_HASHMAP* hashmap /**< hash map */
1026  );
1027 
1028 /**@} */
1029 
1030 
1031 /*
1032  * Hash Set
1033  */
1034 
1035 /**@defgroup HashSet Hash Set
1036  * @ingroup DataStructures
1037  * @brief very lightweight hash set of pointers
1038  *
1039  * @{
1040  */
1041 
1042 /** creates a hash set of pointers */
1043 SCIP_EXPORT
1045  SCIP_HASHSET** hashset, /**< pointer to store the created hash set */
1046  BMS_BLKMEM* blkmem, /**< block memory used to store hash set entries */
1047  int size /**< initial size of the hash set; it is guaranteed that the set is not
1048  * resized if at most that many elements are inserted */
1049  );
1050 
1051 /** frees the hash set */
1052 SCIP_EXPORT
1053 void SCIPhashsetFree(
1054  SCIP_HASHSET** hashset, /**< pointer to the hash set */
1055  BMS_BLKMEM* blkmem /**< block memory used to store hash set entries */
1056  );
1057 
1058 /** inserts new element into the hash set */
1059 SCIP_EXPORT
1061  SCIP_HASHSET* hashset, /**< hash set */
1062  BMS_BLKMEM* blkmem, /**< block memory used to store hash set entries */
1063  void* element /**< element to insert */
1064  );
1065 
1066 /** checks whether an element exists in the hash set */
1067 SCIP_EXPORT
1069  SCIP_HASHSET* hashset, /**< hash set */
1070  void* element /**< element to search for */
1071  );
1072 
1073 /** removes an element from the hash set, if it exists */
1074 SCIP_EXPORT
1076  SCIP_HASHSET* hashset, /**< hash set */
1077  void* element /**< origin to remove from the list */
1078  );
1079 
1080 /** prints statistics about hash set usage */
1081 SCIP_EXPORT
1083  SCIP_HASHSET* hashset, /**< hash set */
1084  SCIP_MESSAGEHDLR* messagehdlr /**< message handler */
1085  );
1086 
1087 /** indicates whether a hash set has no entries */
1088 SCIP_EXPORT
1090  SCIP_HASHSET* hashset /**< hash set */
1091  );
1092 
1093 /** gives the number of elements in a hash set */
1094 SCIP_EXPORT
1096  SCIP_HASHSET* hashset /**< hash set */
1097  );
1098 
1099 /** gives the number of slots of a hash set */
1100 SCIP_EXPORT
1102  SCIP_HASHSET* hashset /**< hash set */
1103  );
1104 
1105 /** gives the array of hash set slots; contains all elements in indetermined order and may contain NULL values */
1106 SCIP_EXPORT
1107 void** SCIPhashsetGetSlots(
1108  SCIP_HASHSET* hashset /**< hash set */
1109  );
1110 
1111 /** removes all entries in a hash set. */
1112 SCIP_EXPORT
1114  SCIP_HASHSET* hashset /**< hash set */
1115  );
1116 
1117 #ifdef NDEBUG
1118 
1119 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
1120  * speed up the algorithms.
1121  */
1122 
1123 #define SCIPhashsetIsEmpty(hashset) ((hashset)->nelements == 0)
1124 #define SCIPhashsetGetNElements(hashset) ((hashset)->nelements)
1125 #define SCIPhashsetGetNSlots(hashset) (1u << (64 - (hashset)->shift))
1126 #define SCIPhashsetGetSlots(hashset) ((hashset)->slots)
1127 
1128 #endif
1129 
1130 /**@} */
1131 
1132 
1133 /*
1134  * Activity
1135  */
1136 
1137 /**@defgroup ResourceActivity Resource Activity
1138  * @ingroup DataStructures
1139  * @brief ressource activity data structure
1140  *
1141  * @{
1142  */
1143 
1144 /** create a resource activity */
1145 SCIP_EXPORT
1147  SCIP_RESOURCEACTIVITY** activity, /**< pointer to store the resource activity */
1148  SCIP_VAR* var, /**< start time variable of the activity */
1149  int duration, /**< duration of the activity */
1150  int demand /**< demand of the activity */
1151  );
1152 
1153 /** frees a resource activity */
1154 SCIP_EXPORT
1155 void SCIPactivityFree(
1156  SCIP_RESOURCEACTIVITY** activity /**< pointer to the resource activity */
1157  );
1158 
1159 #ifndef NDEBUG
1160 
1161 /** returns the start time variable of the resource activity */
1162 SCIP_EXPORT
1164  SCIP_RESOURCEACTIVITY* activity /**< resource activity */
1165  );
1166 
1167 /** returns the duration of the resource activity */
1168 SCIP_EXPORT
1170  SCIP_RESOURCEACTIVITY* activity /**< resource activity */
1171  );
1172 
1173 /** returns the demand of the resource activity */
1174 SCIP_EXPORT
1176  SCIP_RESOURCEACTIVITY* activity /**< resource activity */
1177  );
1178 
1179 /** returns the energy of the resource activity */
1180 SCIP_EXPORT
1182  SCIP_RESOURCEACTIVITY* activity /**< resource activity */
1183  );
1184 
1185 #else
1186 
1187 #define SCIPactivityGetVar(activity) ((activity)->var)
1188 #define SCIPactivityGetDuration(activity) ((activity)->duration)
1189 #define SCIPactivityGetDemand(activity) ((activity)->demand)
1190 #define SCIPactivityGetEnergy(activity) ((activity)->duration * (activity)->demand)
1191 
1192 #endif
1193 
1194 /**@} */
1195 
1196 
1197 /*
1198  * Resource Profile
1199  */
1200 
1201 /**@defgroup ResourceProfile Resource Profile
1202  * @ingroup DataStructures
1203  * @brief ressource profile data structure
1204  *
1205  * @{
1206  */
1207 
1208 /** creates resource profile */
1209 SCIP_EXPORT
1211  SCIP_PROFILE** profile, /**< pointer to store the resource profile */
1212  int capacity /**< resource capacity */
1213  );
1214 
1215 /** frees given resource profile */
1216 SCIP_EXPORT
1217 void SCIPprofileFree(
1218  SCIP_PROFILE** profile /**< pointer to the resource profile */
1219  );
1220 
1221 /** output of the given resource profile */
1222 SCIP_EXPORT
1223 void SCIPprofilePrint(
1224  SCIP_PROFILE* profile, /**< resource profile to output */
1225  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1226  FILE* file /**< output file (or NULL for standard output) */
1227  );
1228 
1229 /** returns the capacity of the resource profile */
1230 SCIP_EXPORT
1232  SCIP_PROFILE* profile /**< resource profile to use */
1233  );
1234 
1235 /** returns the number time points of the resource profile */
1236 SCIP_EXPORT
1238  SCIP_PROFILE* profile /**< resource profile to use */
1239  );
1240 
1241 /** returns the time points of the resource profile */
1242 SCIP_EXPORT
1244  SCIP_PROFILE* profile /**< resource profile to use */
1245  );
1246 
1247 /** returns the loads of the resource profile */
1248 SCIP_EXPORT
1249 int* SCIPprofileGetLoads(
1250  SCIP_PROFILE* profile /**< resource profile to use */
1251  );
1252 
1253 /** returns the time point for given position of the resource profile */
1254 SCIP_EXPORT
1255 int SCIPprofileGetTime(
1256  SCIP_PROFILE* profile, /**< resource profile to use */
1257  int pos /**< position */
1258  );
1259 
1260 /** returns the loads of the resource profile at the given position */
1261 SCIP_EXPORT
1262 int SCIPprofileGetLoad(
1263  SCIP_PROFILE* profile, /**< resource profile */
1264  int pos /**< position */
1265  );
1266 
1267 /** returns if the given time point exists in the resource profile and stores the position of the given time point if it
1268  * exists; otherwise the position of the next smaller existing time point is stored
1269  */
1270 SCIP_EXPORT
1272  SCIP_PROFILE* profile, /**< resource profile to search */
1273  int timepoint, /**< time point to search for */
1274  int* pos /**< pointer to store the position */
1275  );
1276 
1277 /** insert a core into resource profile; if the core is non-empty the resource profile will be updated otherwise nothing
1278  * happens
1279  */
1280 SCIP_EXPORT
1282  SCIP_PROFILE* profile, /**< resource profile to use */
1283  int left, /**< left side of the core */
1284  int right, /**< right side of the core */
1285  int height, /**< height of the core */
1286  int* pos, /**< pointer to store the first position were it gets infeasible */
1287  SCIP_Bool* infeasible /**< pointer to store if the core does not fit due to capacity */
1288  );
1289 
1290 /** subtracts the height from the resource profile during core time */
1291 SCIP_EXPORT
1293  SCIP_PROFILE* profile, /**< resource profile to use */
1294  int left, /**< left side of the core */
1295  int right, /**< right side of the core */
1296  int height /**< height of the core */
1297  );
1298 
1299 /** return the earliest possible starting point within the time interval [lb,ub] for a given core (given by its height
1300  * and duration)
1301  */
1302 SCIP_EXPORT
1304  SCIP_PROFILE* profile, /**< resource profile to use */
1305  int est, /**< earliest starting time of the given core */
1306  int lst, /**< latest starting time of the given core */
1307  int duration, /**< duration of the core */
1308  int height, /**< height of the core */
1309  SCIP_Bool* infeasible /**< pointer store if the corer cannot be inserted */
1310  );
1311 
1312 /** return the latest possible starting point within the time interval [lb,ub] for a given core (given by its height and
1313  * duration)
1314  */
1315 SCIP_EXPORT
1317  SCIP_PROFILE* profile, /**< resource profile to use */
1318  int lb, /**< earliest possible start point */
1319  int ub, /**< latest possible start point */
1320  int duration, /**< duration of the core */
1321  int height, /**< height of the core */
1322  SCIP_Bool* infeasible /**< pointer store if the core cannot be inserted */
1323  );
1324 
1325 /**@} */
1326 
1327 /*
1328  * Directed graph
1329  */
1330 
1331 /**@addtogroup DirectedGraph
1332  *
1333  * @{
1334  */
1335 
1336 /** resize directed graph structure */
1337 SCIP_EXPORT
1339  SCIP_DIGRAPH* digraph, /**< directed graph */
1340  int nnodes /**< new number of nodes */
1341  );
1342 
1343 /** sets the sizes of the successor lists for the nodes in a directed graph and allocates memory for the lists */
1344 SCIP_EXPORT
1346  SCIP_DIGRAPH* digraph, /**< directed graph */
1347  int* sizes /**< sizes of the successor lists */
1348  );
1349 
1350 /** frees given directed graph structure */
1351 SCIP_EXPORT
1352 void SCIPdigraphFree(
1353  SCIP_DIGRAPH** digraph /**< pointer to the directed graph */
1354  );
1355 
1356 /** add (directed) arc and a related data to the directed graph structure
1357  *
1358  * @note if the arc is already contained, it is added a second time
1359  */
1360 SCIP_EXPORT
1362  SCIP_DIGRAPH* digraph, /**< directed graph */
1363  int startnode, /**< start node of the arc */
1364  int endnode, /**< start node of the arc */
1365  void* data /**< data that should be stored for the arc; or NULL */
1366  );
1367 
1368 /** add (directed) arc to the directed graph structure, if it is not contained, yet
1369  *
1370  * @note if there already exists an arc from startnode to endnode, the new arc is not added,
1371  * even if its data is different
1372  */
1373 SCIP_EXPORT
1375  SCIP_DIGRAPH* digraph, /**< directed graph */
1376  int startnode, /**< start node of the arc */
1377  int endnode, /**< start node of the arc */
1378  void* data /**< data that should be stored for the arc; or NULL */
1379  );
1380 
1381 /** sets the number of successors to a given value */
1382 SCIP_EXPORT
1384  SCIP_DIGRAPH* digraph, /**< directed graph */
1385  int node, /**< node for which the number of successors has to be changed */
1386  int nsuccessors /**< new number of successors */
1387  );
1388 
1389 /** returns the number of nodes of the given digraph */
1390 SCIP_EXPORT
1392  SCIP_DIGRAPH* digraph /**< directed graph */
1393  );
1394 
1395 /** returns the node data, or NULL if no data exist */
1396 SCIP_EXPORT
1398  SCIP_DIGRAPH* digraph, /**< directed graph */
1399  int node /**< node for which the node data is returned */
1400  );
1401 
1402 /** sets the node data */
1403 SCIP_EXPORT
1405  SCIP_DIGRAPH* digraph, /**< directed graph */
1406  void* dataptr, /**< user node data pointer, or NULL */
1407  int node /**< node for which the node data is returned */
1408  );
1409 
1410 /** returns the total number of arcs in the given digraph */
1411 SCIP_EXPORT
1413  SCIP_DIGRAPH* digraph /**< directed graph */
1414  );
1415 
1416 /** returns the number of successor nodes of the given node */
1417 SCIP_EXPORT
1419  SCIP_DIGRAPH* digraph, /**< directed graph */
1420  int node /**< node for which the number of outgoing arcs is returned */
1421  );
1422 
1423 /** returns the array of indices of the successor nodes; this array must not be changed from outside */
1424 SCIP_EXPORT
1426  SCIP_DIGRAPH* digraph, /**< directed graph */
1427  int node /**< node for which the array of outgoing arcs is returned */
1428  );
1429 
1430 /** returns the array of data corresponding to the arcs originating at the given node, or NULL if no data exist; this
1431  * array must not be changed from outside
1432  */
1433 SCIP_EXPORT
1435  SCIP_DIGRAPH* digraph, /**< directed graph */
1436  int node /**< node for which the data corresponding to the outgoing arcs is returned */
1437  );
1438 
1439 /** identifies the articulation points in a given directed graph
1440  * uses the helper recursive function findArticulationPointsUtil
1441  */
1442 SCIP_EXPORT
1444  SCIP_DIGRAPH* digraph, /**< directed graph */
1445  int** articulations, /**< array to store the sorted node indices of the computed articulation points, or NULL */
1446  int* narticulations /**< number of the computed articulation points, or NULL */
1447  );
1448 
1449 /** Compute undirected connected components on the given graph.
1450  *
1451  * @note For each arc, its reverse is added, so the graph does not need to be the directed representation of an
1452  * undirected graph.
1453  */
1454 SCIP_EXPORT
1456  SCIP_DIGRAPH* digraph, /**< directed graph */
1457  int minsize, /**< all components with less nodes are ignored */
1458  int* components, /**< array with as many slots as there are nodes in the directed graph
1459  * to store for each node the component to which it belongs
1460  * (components are numbered 0 to ncomponents - 1); or NULL, if components
1461  * are accessed one-by-one using SCIPdigraphGetComponent() */
1462  int* ncomponents /**< pointer to store the number of components; or NULL, if the
1463  * number of components is accessed by SCIPdigraphGetNComponents() */
1464  );
1465 
1466 /** Computes all strongly connected components of an undirected connected component with Tarjan's Algorithm.
1467  * The resulting strongly connected components are sorted topologically (starting from the end of the
1468  * strongcomponents array).
1469  *
1470  * @note In general a topological sort of the strongly connected components is not unique.
1471  */
1472 SCIP_EXPORT
1474  SCIP_DIGRAPH* digraph, /**< directed graph */
1475  int compidx, /**< number of the undirected connected component */
1476  int* strongcomponents, /**< array to store the strongly connected components
1477  * (length >= size of the component) */
1478  int* strongcompstartidx, /**< array to store the start indices of the strongly connected
1479  * components (length >= size of the component) */
1480  int* nstrongcomponents /**< pointer to store the number of strongly connected
1481  * components */
1482  );
1483 
1484 /** Performes an (almost) topological sort on the undirected components of the given directed graph. The undirected
1485  * components should be computed before using SCIPdigraphComputeUndirectedComponents().
1486  *
1487  * @note In general a topological sort is not unique. Note, that there might be directed cycles, that are randomly
1488  * broken, which is the reason for having only almost topologically sorted arrays.
1489  */
1490 SCIP_EXPORT
1492  SCIP_DIGRAPH* digraph /**< directed graph */
1493  );
1494 
1495 /** returns the number of previously computed undirected components for the given directed graph */
1496 SCIP_EXPORT
1498  SCIP_DIGRAPH* digraph /**< directed graph */
1499  );
1500 
1501 /** Returns the previously computed undirected component of the given number for the given directed graph.
1502  * If the components were sorted using SCIPdigraphTopoSortComponents(), the component is (almost) topologically sorted.
1503  */
1504 SCIP_EXPORT
1506  SCIP_DIGRAPH* digraph, /**< directed graph */
1507  int compidx, /**< number of the component to return */
1508  int** nodes, /**< pointer to store the nodes in the component; or NULL, if not needed */
1509  int* nnodes /**< pointer to store the number of nodes in the component;
1510  * or NULL, if not needed */
1511  );
1512 
1513 /** frees the component information for the given directed graph */
1514 SCIP_EXPORT
1516  SCIP_DIGRAPH* digraph /**< directed graph */
1517  );
1518 
1519 /** output of the given directed graph via the given message handler */
1520 SCIP_EXPORT
1521 void SCIPdigraphPrint(
1522  SCIP_DIGRAPH* digraph, /**< directed graph */
1523  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1524  FILE* file /**< output file (or NULL for standard output) */
1525  );
1526 
1527 /** prints the given directed graph structure in GML format into the given file */
1528 SCIP_EXPORT
1529 void SCIPdigraphPrintGml(
1530  SCIP_DIGRAPH* digraph, /**< directed graph */
1531  FILE* file /**< file to write to */
1532  );
1533 
1534 
1535 /** output of the given directed graph via the given message handler */
1536 SCIP_EXPORT
1538  SCIP_DIGRAPH* digraph, /**< directed graph */
1539  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1540  FILE* file /**< output file (or NULL for standard output) */
1541  );
1542 
1543 /**@} */
1544 
1545 /*
1546  * Binary search tree
1547  */
1548 
1549 /**@defgroup BinaryTree Binary Search Tree
1550  * @ingroup DataStructures
1551  * @brief binary search tree data structure
1552  *@{
1553  */
1554 
1555 /** creates a binary tree node with sorting value and user data */
1556 SCIP_EXPORT
1558  SCIP_BT* tree, /**< binary search tree */
1559  SCIP_BTNODE** node, /**< pointer to store the created search node */
1560  void* dataptr /**< user node data pointer, or NULL */
1561  );
1562 
1563 /** frees the binary node including the rooted subtree
1564  *
1565  * @note The user pointer (object) is not freed. If needed, it has to be done by the user.
1566  */
1567 SCIP_EXPORT
1568 void SCIPbtnodeFree(
1569  SCIP_BT* tree, /**< binary tree */
1570  SCIP_BTNODE** node /**< node to be freed */
1571  );
1572 
1573 /** returns the user data pointer stored in that node */
1574 SCIP_EXPORT
1575 void* SCIPbtnodeGetData(
1576  SCIP_BTNODE* node /**< node */
1577  );
1578 
1579 /** returns the parent which can be NULL if the given node is the root */
1580 SCIP_EXPORT
1582  SCIP_BTNODE* node /**< node */
1583  );
1584 
1585 /** returns left child which can be NULL if the given node is a leaf */
1586 SCIP_EXPORT
1588  SCIP_BTNODE* node /**< node */
1589  );
1590 
1591 /** returns right child which can be NULL if the given node is a leaf */
1592 SCIP_EXPORT
1594  SCIP_BTNODE* node /**< node */
1595  );
1596 
1597 /** returns the sibling of the node or NULL if does not exist */
1598 SCIP_EXPORT
1600  SCIP_BTNODE* node /**< node */
1601  );
1602 
1603 /** returns whether the node is a root node */
1604 SCIP_EXPORT
1606  SCIP_BTNODE* node /**< node */
1607  );
1608 
1609 /** returns whether the node is a leaf */
1610 SCIP_EXPORT
1612  SCIP_BTNODE* node /**< node */
1613  );
1614 
1615 /** returns TRUE if the given node is left child */
1616 SCIP_EXPORT
1618  SCIP_BTNODE* node /**< node */
1619  );
1620 
1621 /** returns TRUE if the given node is right child */
1622 SCIP_EXPORT
1624  SCIP_BTNODE* node /**< node */
1625  );
1626 
1627 #ifdef NDEBUG
1628 
1629 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
1630  * speed up the algorithms.
1631  */
1632 
1633 #define SCIPbtnodeGetData(node) ((node)->dataptr)
1634 #define SCIPbtnodeGetParent(node) ((node)->parent)
1635 #define SCIPbtnodeGetLeftchild(node) ((node)->left)
1636 #define SCIPbtnodeGetRightchild(node) ((node)->right)
1637 #define SCIPbtnodeGetSibling(node) ((node)->parent == NULL ? NULL : \
1638  (node)->parent->left == (node) ? (node)->parent->right : (node)->parent->left)
1639 #define SCIPbtnodeIsRoot(node) ((node)->parent == NULL)
1640 #define SCIPbtnodeIsLeaf(node) ((node)->left == NULL && (node)->right == NULL)
1641 #define SCIPbtnodeIsLeftchild(node) ((node)->parent == NULL ? FALSE : (node)->parent->left == (node) ? TRUE : FALSE)
1642 #define SCIPbtnodeIsRightchild(node) ((node)->parent == NULL ? FALSE : (node)->parent->right == (node) ? TRUE : FALSE)
1643 
1644 #endif
1645 
1646 /** sets the give node data
1647  *
1648  * @note The old user pointer is not freed.
1649  */
1650 SCIP_EXPORT
1651 void SCIPbtnodeSetData(
1652  SCIP_BTNODE* node, /**< node */
1653  void* dataptr /**< node user data pointer */
1654  );
1655 
1656 /** sets parent node
1657  *
1658  * @note The old parent including the rooted subtree is not delete.
1659  */
1660 SCIP_EXPORT
1661 void SCIPbtnodeSetParent(
1662  SCIP_BTNODE* node, /**< node */
1663  SCIP_BTNODE* parent /**< new parent node, or NULL */
1664  );
1665 
1666 /** sets left child
1667  *
1668  * @note The old left child including the rooted subtree is not delete.
1669  */
1670 SCIP_EXPORT
1672  SCIP_BTNODE* node, /**< node */
1673  SCIP_BTNODE* left /**< new left child, or NULL */
1674  );
1675 
1676 /** sets right child
1677  *
1678  * @note The old right child including the rooted subtree is not delete.
1679  */
1680 SCIP_EXPORT
1682  SCIP_BTNODE* node, /**< node */
1683  SCIP_BTNODE* right /**< new right child, or NULL */
1684  );
1685 
1686 /** creates an binary tree */
1687 SCIP_EXPORT
1689  SCIP_BT** tree, /**< pointer to store the created binary tree */
1690  BMS_BLKMEM* blkmem /**< block memory used to create nodes */
1691  );
1692 
1693 /** frees binary tree
1694  *
1695  * @note The user pointers (object) of the search nodes are not freed. If needed, it has to be done by the user.
1696  */
1697 SCIP_EXPORT
1698 void SCIPbtFree(
1699  SCIP_BT** tree /**< pointer to binary tree */
1700  );
1701 
1702 /** prints the binary tree in GML format into the given file */
1703 SCIP_EXPORT
1704 void SCIPbtPrintGml(
1705  SCIP_BT* tree, /**< binary tree */
1706  FILE* file /**< file to write to */
1707  );
1708 
1709 /** returns whether the binary tree is empty (has no nodes) */
1710 SCIP_EXPORT
1712  SCIP_BT * tree /**< binary tree */
1713  );
1714 
1715 /** returns the root node of the binary tree or NULL if the binary tree is empty */
1716 SCIP_EXPORT
1718  SCIP_BT* tree /**< tree to be evaluated */
1719  );
1720 
1721 #ifdef NDEBUG
1722 
1723 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
1724  * speed up the algorithms.
1725  */
1726 
1727 #define SCIPbtIsEmpty(tree) (tree->root == NULL)
1728 #define SCIPbtGetRoot(tree) (tree->root)
1729 
1730 #endif
1731 
1732 /** sets root node
1733  *
1734  * @note The old root including the rooted subtree is not delete.
1735  */
1736 SCIP_EXPORT
1737 void SCIPbtSetRoot(
1738  SCIP_BT* tree, /**< tree to be evaluated */
1739  SCIP_BTNODE* root /**< new root, or NULL */
1740  );
1741 
1742 /**@} */
1743 
1744 /**@addtogroup DisjointSet
1745  *
1746  * @{
1747  */
1748 
1749 /*
1750  * disjoint set data structure
1751  */
1752 
1753 /** clears the disjoint set (union find) structure \p djset */
1754 SCIP_EXPORT
1756  SCIP_DISJOINTSET* djset /**< disjoint set (union find) data structure */
1757  );
1758 
1759 /** finds and returns the component identifier of this \p element */
1760 SCIP_EXPORT
1762  SCIP_DISJOINTSET* djset, /**< disjoint set (union find) data structure */
1763  int element /**< element to be found */
1764  );
1765 
1766 /** merges the components containing the elements \p p and \p q */
1767 SCIP_EXPORT
1769  SCIP_DISJOINTSET* djset, /**< disjoint set (union find) data structure */
1770  int p, /**< first element */
1771  int q, /**< second element */
1772  SCIP_Bool forcerepofp /**< force representative of p to be new representative */
1773  );
1774 
1775 /** returns the number of independent components in this disjoint set (union find) data structure */
1776 SCIP_EXPORT
1778  SCIP_DISJOINTSET* djset /**< disjoint set (union find) data structure */
1779  );
1780 
1781 /** returns the size (number of nodes) of this disjoint set (union find) data structure */
1782 SCIP_EXPORT
1784  SCIP_DISJOINTSET* djset /**< disjoint set (union find) data structure */
1785  );
1786 
1787 /** @} */
1788 
1789 /*
1790  * Numerical methods
1791  */
1792 
1793 /**@defgroup NumericalMethods Numerical Methods
1794  * @ingroup MiscellaneousMethods
1795  * @brief commonly used numerical methods
1796  *
1797  * @{
1798  */
1799 
1800 /** returns the machine epsilon: the smallest number eps > 0, for which 1.0 + eps > 1.0 */
1801 SCIP_EXPORT
1803  void
1804  );
1805 
1806 /** returns the next representable value of from in the direction of to */
1807 SCIP_EXPORT
1809  SCIP_Real from, /**< value from which the next representable value should be returned */
1810  SCIP_Real to /**< direction in which the next representable value should be returned */
1811  );
1812 
1813 /** calculates the greatest common divisor of the two given values */
1814 SCIP_EXPORT
1816  SCIP_Longint val1, /**< first value of greatest common devisor calculation */
1817  SCIP_Longint val2 /**< second value of greatest common devisor calculation */
1818  );
1819 
1820 /** calculates the smallest common multiple of the two given values */
1821 SCIP_EXPORT
1823  SCIP_Longint val1, /**< first value of smallest common multiple calculation */
1824  SCIP_Longint val2 /**< second value of smallest common multiple calculation */
1825  );
1826 
1827 /** calculates a binomial coefficient n over m, choose m elements out of n, maximal value will be 33 over 16 (because
1828  * 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
1829  * big numbers or an negative value m (and m < n) and -1 will be returned
1830  */
1831 SCIP_EXPORT
1833  int n, /**< number of different elements */
1834  int m /**< number to choose out of the above */
1835  );
1836 
1837 /** calculates hash for floating-point number by using Fibonacci hashing */
1838 SCIP_EXPORT
1839 unsigned int SCIPcalcFibHash(
1840  SCIP_Real v /**< number to hash */
1841  );
1842 
1843 #ifdef NDEBUG
1844 
1845 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
1846  * speed up the algorithms.
1847  */
1848 
1849 #define SCIPcalcFibHash(v) ((v) >= 0 ? ((unsigned long long)((v) * 2654435769)) % UINT_MAX : ((unsigned long long)(-(v) * 683565275)) % UINT_MAX )
1850 
1851 #endif
1852 
1853 /** converts a real number into a (approximate) rational representation, and returns TRUE iff the conversion was
1854  * successful
1855  */
1856 SCIP_EXPORT
1858  SCIP_Real val, /**< real value r to convert into rational number */
1859  SCIP_Real mindelta, /**< minimal allowed difference r - q of real r and rational q = n/d */
1860  SCIP_Real maxdelta, /**< maximal allowed difference r - q of real r and rational q = n/d */
1861  SCIP_Longint maxdnom, /**< maximal denominator allowed */
1862  SCIP_Longint* nominator, /**< pointer to store the nominator n of the rational number */
1863  SCIP_Longint* denominator /**< pointer to store the denominator d of the rational number */
1864  );
1865 
1866 /** tries to find a value, such that all given values, if scaled with this value become integral in relative allowed
1867  * difference in between mindelta and maxdelta
1868  */
1869 SCIP_EXPORT
1871  SCIP_Real* vals, /**< values to scale */
1872  int nvals, /**< number of values to scale */
1873  SCIP_Real mindelta, /**< minimal relative allowed difference of scaled coefficient s*c and integral i */
1874  SCIP_Real maxdelta, /**< maximal relative allowed difference of scaled coefficient s*c and integral i */
1875  SCIP_Longint maxdnom, /**< maximal denominator allowed in rational numbers */
1876  SCIP_Real maxscale, /**< maximal allowed scalar */
1877  SCIP_Real* intscalar, /**< pointer to store scalar that would make the coefficients integral, or NULL */
1878  SCIP_Bool* success /**< stores whether returned value is valid */
1879  );
1880 
1881 /** given a (usually very small) interval, tries to find a rational number with simple denominator (i.e. a small
1882  * number, probably multiplied with powers of 10) out of this interval; returns TRUE iff a valid rational
1883  * number inside the interval was found
1884  */
1885 SCIP_EXPORT
1887  SCIP_Real lb, /**< lower bound of the interval */
1888  SCIP_Real ub, /**< upper bound of the interval */
1889  SCIP_Longint maxdnom, /**< maximal denominator allowed for resulting rational number */
1890  SCIP_Longint* nominator, /**< pointer to store the nominator n of the rational number */
1891  SCIP_Longint* denominator /**< pointer to store the denominator d of the rational number */
1892  );
1893 
1894 /** given a (usually very small) interval, selects a value inside this interval; it is tried to select a rational number
1895  * with simple denominator (i.e. a small number, probably multiplied with powers of 10);
1896  * if no valid rational number inside the interval was found, selects the central value of the interval
1897  */
1898 SCIP_EXPORT
1900  SCIP_Real lb, /**< lower bound of the interval */
1901  SCIP_Real ub, /**< upper bound of the interval */
1902  SCIP_Longint maxdnom /**< maximal denominator allowed for resulting rational number */
1903  );
1904 
1905 /** Performs the Newton Procedure from a given starting point to compute a root of the given function with
1906  * specified precision and maximum number of iterations. If the procedure fails, SCIP_INVALID is returned.
1907  */
1908 SCIP_EXPORT
1910  SCIP_DECL_NEWTONEVAL((*function)), /**< pointer to function for which roots are computed */
1911  SCIP_DECL_NEWTONEVAL((*derivative)), /**< pointer to derivative of above function */
1912  SCIP_Real* params, /**< parameters needed for function (can be NULL) */
1913  int nparams, /**< number of parameters (can be 0) */
1914  SCIP_Real x, /**< starting point */
1915  SCIP_Real eps, /**< tolerance */
1916  int k /**< iteration limit */
1917  );
1918 
1919 /* The C99 standard defines the function (or macro) isfinite.
1920  * On MacOS X, isfinite is also available.
1921  * From the BSD world, there comes a function finite.
1922  * On SunOS, finite is also available.
1923  * In the MS compiler world, there is a function _finite.
1924  * As last resort, we check whether x == x does not hold, but this works only for NaN's, not for infinities!
1925  */
1926 #if _XOPEN_SOURCE >= 600 || defined(_ISOC99_SOURCE) || _POSIX_C_SOURCE >= 200112L || defined(__APPLE__)
1927 #define SCIPisFinite isfinite
1928 #elif defined(_BSD_SOURCE) || defined(__sun)
1929 #define SCIPisFinite finite
1930 #elif defined(_MSC_VER)
1931 #define SCIPisFinite _finite
1932 #else
1933 #define SCIPisFinite(x) ((x) == (x))
1934 #endif
1935 
1936 /* In debug mode, the following methods are implemented as function calls to ensure
1937  * type validity.
1938  */
1939 
1940 /** returns the relative difference: (val1-val2)/max(|val1|,|val2|,1.0) */
1941 SCIP_EXPORT
1943  SCIP_Real val1, /**< first value to be compared */
1944  SCIP_Real val2 /**< second value to be compared */
1945  );
1946 
1947 #ifdef NDEBUG
1948 
1949 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
1950  * speed up the algorithms.
1951  */
1952 
1953 #define SCIPrelDiff(val1, val2) ( ((val1)-(val2))/(MAX3(1.0,REALABS(val1),REALABS(val2))) )
1954 
1955 #endif
1956 
1957 /** computes the gap from the primal and the dual bound */
1958 SCIP_EXPORT
1960  SCIP_Real eps, /**< the value treated as zero */
1961  SCIP_Real inf, /**< the value treated as infinity */
1962  SCIP_Real primalbound, /**< the primal bound */
1963  SCIP_Real dualbound /**< the dual bound */
1964  );
1965 
1966 /**@} */
1967 
1968 
1969 /*
1970  * Random Numbers
1971  */
1972 
1973 /**@defgroup RandomNumbers Random Numbers
1974  * @ingroup MiscellaneousMethods
1975  * @brief structures and methods for pseudo random number generation
1976  *
1977  *@{
1978  */
1979 
1980 /** returns a random integer between minrandval and maxrandval
1981  *
1982  * @deprecated Please use SCIPrandomGetInt() to request a random integer.
1983  */
1984 SCIP_EXPORT
1985 int SCIPgetRandomInt(
1986  int minrandval, /**< minimal value to return */
1987  int maxrandval, /**< maximal value to return */
1988  unsigned int* seedp /**< pointer to seed value */
1989  );
1990 
1991 
1992 /** returns a random integer between minrandval and maxrandval */
1993 SCIP_EXPORT
1994 int SCIPrandomGetInt(
1995  SCIP_RANDNUMGEN* randgen, /**< random number generator data */
1996  int minrandval, /**< minimal value to return */
1997  int maxrandval /**< maximal value to return */
1998  );
1999 
2000 /** draws a random subset of disjoint elements from a given set of disjoint elements;
2001  * this implementation is suited for the case that nsubelems is considerably smaller then nelems
2002  */
2003 SCIP_EXPORT
2005  SCIP_RANDNUMGEN* randgen, /**< random number generator */
2006  void** set, /**< original set, from which elements should be drawn */
2007  int nelems, /**< number of elements in original set */
2008  void** subset, /**< subset in which drawn elements should be stored */
2009  int nsubelems /**< number of elements that should be drawn and stored */
2010  );
2011 
2012 /** returns a random real between minrandval and maxrandval */
2013 SCIP_EXPORT
2015  SCIP_RANDNUMGEN* randgen, /**< random number generator data */
2016  SCIP_Real minrandval, /**< minimal value to return */
2017  SCIP_Real maxrandval /**< maximal value to return */
2018  );
2019 
2020 /** returns a random real between minrandval and maxrandval
2021  *
2022  * @deprecated Please use SCIPrandomGetReal() to request a random real.
2023  */
2024 SCIP_EXPORT
2026  SCIP_Real minrandval, /**< minimal value to return */
2027  SCIP_Real maxrandval, /**< maximal value to return */
2028  unsigned int* seedp /**< pointer to seed value */
2029  );
2030 
2031 /** draws a random subset of disjoint elements from a given set of disjoint elements;
2032  * this implementation is suited for the case that nsubelems is considerably smaller then nelems
2033  *
2034  * @deprecated Please use SCIPrandomGetSubset()
2035  */
2036 SCIP_EXPORT
2038  void** set, /**< original set, from which elements should be drawn */
2039  int nelems, /**< number of elements in original set */
2040  void** subset, /**< subset in which drawn elements should be stored */
2041  int nsubelems, /**< number of elements that should be drawn and stored */
2042  unsigned int randseed /**< seed value for random generator */
2043  );
2044 
2045 /**@} */
2046 
2047 /*
2048  * Permutations / Shuffling
2049  */
2050 
2051 /**@defgroup PermutationsShuffling Permutations Shuffling
2052  * @ingroup MiscellaneousMethods
2053  * @brief methods for shuffling arrays
2054  *
2055  * @{
2056  */
2057 
2058 /** swaps two ints */
2059 SCIP_EXPORT
2060 void SCIPswapInts(
2061  int* value1, /**< pointer to first integer */
2062  int* value2 /**< pointer to second integer */
2063  );
2064 
2065 /** swaps two real values */
2066 SCIP_EXPORT
2067 void SCIPswapReals(
2068  SCIP_Real* value1, /**< pointer to first real value */
2069  SCIP_Real* value2 /**< pointer to second real value */
2070 );
2071 
2072 /** swaps the addresses of two pointers */
2073 SCIP_EXPORT
2074 void SCIPswapPointers(
2075  void** pointer1, /**< first pointer */
2076  void** pointer2 /**< second pointer */
2077  );
2078 
2079 /** randomly shuffles parts of an integer array using the Fisher-Yates algorithm
2080  *
2081  * @deprecated Please use SCIPrandomPermuteIntArray()
2082  */
2083 SCIP_EXPORT
2084 void SCIPpermuteIntArray(
2085  int* array, /**< array to be shuffled */
2086  int begin, /**< first included index that should be subject to shuffling
2087  * (0 for first array entry)
2088  */
2089  int end, /**< first excluded index that should not be subject to shuffling
2090  * (array size for last array entry)
2091  */
2092  unsigned int* randseed /**< seed value for the random generator */
2093  );
2094 
2095 /** randomly shuffles parts of an integer array using the Fisher-Yates algorithm */
2096 SCIP_EXPORT
2098  SCIP_RANDNUMGEN* randgen, /**< random number generator */
2099  int* array, /**< array to be shuffled */
2100  int begin, /**< first included index that should be subject to shuffling
2101  * (0 for first array entry)
2102  */
2103  int end /**< first excluded index that should not be subject to shuffling
2104  * (array size for last array entry)
2105  */
2106  );
2107 
2108 /** randomly shuffles parts of an array using the Fisher-Yates algorithm */
2109 SCIP_EXPORT
2111  SCIP_RANDNUMGEN* randgen, /**< random number generator */
2112  void** array, /**< array to be shuffled */
2113  int begin, /**< first included index that should be subject to shuffling
2114  * (0 for first array entry)
2115  */
2116  int end /**< first excluded index that should not be subject to shuffling
2117  * (array size for last array entry)
2118  */
2119  );
2120 
2121 /** randomly shuffles parts of an array using the Fisher-Yates algorithm
2122  *
2123  * @deprecated Please use SCIPrandomPermuteArray()
2124  */
2125 SCIP_EXPORT
2126 void SCIPpermuteArray(
2127  void** array, /**< array to be shuffled */
2128  int begin, /**< first included index that should be subject to shuffling
2129  * (0 for first array entry)
2130  */
2131  int end, /**< first excluded index that should not be subject to shuffling
2132  * (array size for last array entry)
2133  */
2134  unsigned int* randseed /**< pointer to seed value for the random generator */
2135  );
2136 
2137 /**@} */
2138 
2139 
2140 /*
2141  * Arrays
2142  */
2143 
2144 /**@defgroup Arrays Arrays
2145  * @ingroup MiscellaneousMethods
2146  * @brief miscellaneous methods for arrays
2147  *
2148  * @{
2149  */
2150 
2151 
2152 /** computes set intersection (duplicates removed) of two integer arrays that are ordered ascendingly
2153  *
2154  * @deprecated Switch to SCIPcomputeArraysIntersectionInt().
2155  */
2156 SCIP_EXPORT
2158  int* array1, /**< first array (in ascending order) */
2159  int narray1, /**< number of entries of first array */
2160  int* array2, /**< second array (in ascending order) */
2161  int narray2, /**< number of entries of second array */
2162  int* intersectarray, /**< intersection of array1 and array2
2163  * (note: it is possible to use array1 for this input argument) */
2164  int* nintersectarray /**< pointer to store number of entries of intersection array
2165  * (note: it is possible to use narray1 for this input argument) */
2166  );
2167 
2168 /** computes set intersection (duplicates removed) of two integer arrays that are ordered ascendingly */
2169 SCIP_EXPORT
2171  int* array1, /**< first array (in ascending order) */
2172  int narray1, /**< number of entries of first array */
2173  int* array2, /**< second array (in ascending order) */
2174  int narray2, /**< number of entries of second array */
2175  int* intersectarray, /**< intersection of array1 and array2
2176  * (note: it is possible to use array1 for this input argument) */
2177  int* nintersectarray /**< pointer to store number of entries of intersection array
2178  * (note: it is possible to use narray1 for this input argument) */
2179  );
2180 
2181 /** computes set intersection (duplicates removed) of two void-pointer arrays that are ordered ascendingly */
2182 SCIP_EXPORT
2184  void** array1, /**< first array (in ascending order) */
2185  int narray1, /**< number of entries of first array */
2186  void** array2, /**< second array (in ascending order) */
2187  int narray2, /**< number of entries of second array */
2188  SCIP_DECL_SORTPTRCOMP((*ptrcomp)), /**< data element comparator */
2189  void** intersectarray, /**< intersection of array1 and array2
2190  * (note: it is possible to use array1 for this input argument) */
2191  int* nintersectarray /**< pointer to store number of entries of intersection array
2192  * (note: it is possible to use narray1 for this input argument) */
2193 );
2194 
2195 /** computes set difference (duplicates removed) of two integer arrays that are ordered ascendingly
2196  *
2197  * @deprecated Switch to SCIPcomputeArraysSetminusInt().
2198  */
2199 SCIP_EXPORT
2201  int* array1, /**< first array (in ascending order) */
2202  int narray1, /**< number of entries of first array */
2203  int* array2, /**< second array (in ascending order) */
2204  int narray2, /**< number of entries of second array */
2205  int* setminusarray, /**< array to store entries of array1 that are not an entry of array2
2206  * (note: it is possible to use array1 for this input argument) */
2207  int* nsetminusarray /**< pointer to store number of entries of setminus array
2208  * (note: it is possible to use narray1 for this input argument) */
2209  );
2210 
2211 /** computes set difference (duplicates removed) of two integer arrays that are ordered ascendingly */
2212 SCIP_EXPORT
2214  int* array1, /**< first array (in ascending order) */
2215  int narray1, /**< number of entries of first array */
2216  int* array2, /**< second array (in ascending order) */
2217  int narray2, /**< number of entries of second array */
2218  int* setminusarray, /**< array to store entries of array1 that are not an entry of array2
2219  * (note: it is possible to use array1 for this input argument) */
2220  int* nsetminusarray /**< pointer to store number of entries of setminus array
2221  * (note: it is possible to use narray1 for this input argument) */
2222  );
2223 
2224 /**@} */
2225 
2226 
2227 /*
2228  * Strings
2229  */
2230 
2231 /**@defgroup StringMethods String Methods
2232  * @ingroup MiscellaneousMethods
2233  * @brief commonly used methods for strings
2234  *
2235  *@{
2236  */
2237 
2238 /** copies characters from 'src' to 'dest', copying is stopped when either the 'stop' character is reached or after
2239  * 'cnt' characters have been copied, whichever comes first.
2240  *
2241  * @note undefined behaviuor on overlapping arrays
2242  */
2243 SCIP_EXPORT
2244 int SCIPmemccpy(
2245  char* dest, /**< destination pointer to copy to */
2246  const char* src, /**< source pointer to copy to */
2247  char stop, /**< character when found stop copying */
2248  unsigned int cnt /**< maximal number of characters to copy too */
2249  );
2250 
2251 /** prints an error message containing of the given string followed by a string describing the current system error;
2252  * prefers to use the strerror_r method, which is threadsafe; on systems where this method does not exist,
2253  * NO_STRERROR_R should be defined (see INSTALL), in this case, srerror is used which is not guaranteed to be
2254  * threadsafe (on SUN-systems, it actually is)
2255  */
2256 SCIP_EXPORT
2257 void SCIPprintSysError(
2258  const char* message /**< first part of the error message, e.g. the filename */
2259  );
2260 
2261 /** extracts tokens from strings - wrapper method for strtok_r() */
2262 SCIP_EXPORT
2263 char* SCIPstrtok(
2264  char* s, /**< string to parse */
2265  const char* delim, /**< delimiters for parsing */
2266  char** ptrptr /**< pointer to working char pointer - must stay the same while parsing */
2267  );
2268 
2269 /** translates the given string into a string where symbols ", ', and spaces are escaped with a \ prefix */
2270 SCIP_EXPORT
2271 void SCIPescapeString(
2272  char* t, /**< target buffer to store escaped string */
2273  int bufsize, /**< size of buffer t */
2274  const char* s /**< string to transform into escaped string */
2275  );
2276 
2277 /** increases string pointer as long as it refers to a space character or an explicit space control sequence */
2278 SCIP_EXPORT
2280  char** s /**< pointer to string pointer */
2281  );
2282 
2283 /** safe version of snprintf */
2284 SCIP_EXPORT
2285 int SCIPsnprintf(
2286  char* t, /**< target string */
2287  int len, /**< length of the string to copy */
2288  const char* s, /**< source string */
2289  ... /**< further parameters */
2290  );
2291 
2292 /** safe version of strncpy
2293  *
2294  * Copies string in s to t using at most @a size-1 nonzero characters (strncpy copies size characters). It always adds
2295  * a terminating zero char. Does not pad the remaining string with zero characters (unlike strncpy). Returns the number
2296  * of copied nonzero characters, if the length of s is at most size - 1, and returns size otherwise. Thus, the original
2297  * string was truncated if the return value is size.
2298  */
2299 SCIP_EXPORT
2300 int SCIPstrncpy(
2301  char* t, /**< target string */
2302  const char* s, /**< source string */
2303  int size /**< maximal size of t */
2304  );
2305 
2306 /** 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
2307  *
2308  * @return Returns TRUE if a value could be extracted, otherwise FALSE
2309  */
2310 SCIP_EXPORT
2312  const char* str, /**< string to search */
2313  int* value, /**< pointer to store the parsed value */
2314  char** endptr /**< pointer to store the final string position if successfully parsed, otherwise @p str */
2315  );
2316 
2317 /** 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
2318  *
2319  * @return Returns TRUE if a value could be extracted, otherwise FALSE
2320  */
2321 SCIP_EXPORT
2323  const char* str, /**< string to search */
2324  SCIP_Real* value, /**< pointer to store the parsed value */
2325  char** endptr /**< pointer to store the final string position if successfully parsed, otherwise @p str */
2326  );
2327 
2328 /** copies the first size characters between a start and end character of str into token, if no error occurred endptr
2329  * will point to the position after the read part, otherwise it will point to @p str
2330  */
2331 SCIP_EXPORT
2332 void SCIPstrCopySection(
2333  const char* str, /**< string to search */
2334  char startchar, /**< character which defines the beginning */
2335  char endchar, /**< character which defines the ending */
2336  char* token, /**< string to store the copy */
2337  int size, /**< size of the token char array */
2338  char** endptr /**< pointer to store the final string position if successfully parsed, otherwise @p str */
2339  );
2340 
2341 /** checks whether a given string t appears at the beginning of the string s (up to spaces at beginning) */
2342 SCIP_EXPORT
2344  const char* s, /**< string to search in */
2345  const char* t, /**< string to search for */
2346  size_t tlen /**< length of t */
2347 );
2348 
2349 /**@} */
2350 
2351 /*
2352  * File methods
2353  */
2354 
2355 /**@defgroup FileMethods File Methods
2356  * @ingroup MiscellaneousMethods
2357  * @brief commonly used file methods
2358  *
2359  * @{
2360  */
2361 
2362 /** returns, whether the given file exists */
2363 SCIP_EXPORT
2365  const char* filename /**< file name */
2366  );
2367 
2368 /** splits filename into path, name, and extension */
2369 SCIP_EXPORT
2370 void SCIPsplitFilename(
2371  char* filename, /**< filename to split; is destroyed (but not freed) during process */
2372  char** path, /**< pointer to store path, or NULL if not needed */
2373  char** name, /**< pointer to store name, or NULL if not needed */
2374  char** extension, /**< pointer to store extension, or NULL if not needed */
2375  char** compression /**< pointer to store compression extension, or NULL if not needed */
2376  );
2377 
2378 /**@} */
2379 
2380 #ifdef __cplusplus
2381 }
2382 #endif
2383 
2384 #endif
void SCIPmultihashFree(SCIP_MULTIHASH **multihash)
Definition: misc.c:1993
void SCIPpermuteArray(void **array, int begin, int end, unsigned int *randseed)
Definition: misc.c:10446
SCIP_RETCODE SCIPbtnodeCreate(SCIP_BT *tree, SCIP_BTNODE **node, void *dataptr)
Definition: misc.c:8677
void ** SCIPdigraphGetSuccessorsData(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7837
int SCIPpqueueNElems(SCIP_PQUEUE *pqueue)
Definition: misc.c:1527
void SCIPbtnodeFree(SCIP_BT *tree, SCIP_BTNODE **node)
Definition: misc.c:8741
void * SCIPhashmapEntryGetImage(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3570
SCIP_Real SCIPnormalGetCriticalValue(SCIP_CONFIDENCELEVEL clevel)
Definition: misc.c:183
void SCIPdotWriteOpening(FILE *file)
Definition: misc.c:711
int SCIPmemccpy(char *dest, const char *src, char stop, unsigned int cnt)
Definition: misc.c:10744
SCIP_RETCODE SCIPskipSpace(char **s)
Definition: misc.c:10866
SCIP_Real SCIPerf(SCIP_Real x)
Definition: misc.c:156
void SCIPhashmapEntrySetImageReal(SCIP_HASHMAPENTRY *entry, SCIP_Real image)
Definition: misc.c:3622
internal miscellaneous methods for linear constraints
SCIP_RETCODE SCIPhashsetRemove(SCIP_HASHSET *hashset, void *element)
Definition: misc.c:3858
void SCIPdisjointsetUnion(SCIP_DISJOINTSET *djset, int p, int q, SCIP_Bool forcerepofp)
Definition: misc.c:11296
void * SCIPhashtableGetEntry(SCIP_HASHTABLE *hashtable, int entryidx)
Definition: misc.c:2785
void SCIPsparseSolGetFirstSol(SCIP_SPARSESOL *sparsesol, SCIP_Longint *sol, int nvars)
Definition: misc.c:869
type definitions for miscellaneous datastructures
SCIP_BTNODE * SCIPbtnodeGetSibling(SCIP_BTNODE *node)
Definition: misc.c:8826
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3357
SCIP_RETCODE SCIPprofileDeleteCore(SCIP_PROFILE *profile, int left, int right, int height)
Definition: misc.c:7050
void * SCIPbtnodeGetData(SCIP_BTNODE *node)
Definition: misc.c:8786
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2547
SCIP_DECL_HASHKEYVAL(SCIPhashKeyValString)
Definition: misc.c:2851
void SCIPdigraphFreeComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8518
int SCIPhashsetGetNElements(SCIP_HASHSET *hashset)
Definition: misc.c:3992
void SCIPhashmapEntrySetImageInt(SCIP_HASHMAPENTRY *entry, int image)
Definition: misc.c:3611
void ** SCIPhashsetGetSlots(SCIP_HASHSET *hashset)
Definition: misc.c:4008
void SCIPgmlWriteArc(FILE *file, unsigned int source, unsigned int target, const char *label, const char *color)
Definition: misc.c:639
SCIP_RETCODE SCIPdigraphComputeUndirectedComponents(SCIP_DIGRAPH *digraph, int minsize, int *components, int *ncomponents)
Definition: misc.c:8089
void SCIPcomputeArraysSetminusInt(int *array1, int narray1, int *array2, int narray2, int *setminusarray, int *nsetminusarray)
Definition: misc.c:10689
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7819
SCIP_RETCODE SCIPqueueInsert(SCIP_QUEUE *queue, void *elem)
Definition: misc.c:1079
void SCIPgmlWriteNode(FILE *file, unsigned int id, const char *label, const char *nodetype, const char *fillcolor, const char *bordercolor)
Definition: misc.c:497
void SCIPsplitFilename(char *filename, char **path, char **name, char **extension, char **compression)
Definition: misc.c:11095
#define INLINE
Definition: def.h:129
void * SCIPhashmapEntryGetOrigin(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3560
SCIP_Bool SCIPsparseSolGetNextSol(SCIP_SPARSESOL *sparsesol, SCIP_Longint *sol, int nvars)
Definition: misc.c:892
int SCIPprofileGetTime(SCIP_PROFILE *profile, int pos)
Definition: misc.c:6847
SCIP_RETCODE SCIPmultihashCreate(SCIP_MULTIHASH **multihash, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:1960
void SCIPgmlWriteClosing(FILE *file)
Definition: misc.c:699
void SCIPswapPointers(void **pointer1, void **pointer2)
Definition: misc.c:10396
void SCIPbtnodeSetRightchild(SCIP_BTNODE *node, SCIP_BTNODE *right)
Definition: misc.c:8947
void SCIPdotWriteArc(FILE *file, int source, int target, const char *color)
Definition: misc.c:736
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:11184
int SCIPprofileGetEarliestFeasibleStart(SCIP_PROFILE *profile, int est, int lst, int duration, int height, SCIP_Bool *infeasible)
Definition: misc.c:7140
miscellaneous datastructures
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
void SCIPrandomPermuteArray(SCIP_RANDNUMGEN *randgen, void **array, int begin, int end)
Definition: misc.c:10179
SCIP_RETCODE SCIPhashsetCreate(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem, int size)
Definition: misc.c:3759
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_RETCODE SCIPdigraphSetSizes(SCIP_DIGRAPH *digraph, int *sizes)
Definition: misc.c:7544
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3192
void SCIPdigraphPrintComponents(SCIP_DIGRAPH *digraph, SCIP_MESSAGEHDLR *messagehdlr, FILE *file)
Definition: misc.c:8624
SCIP_VAR * SCIPactivityGetVar(SCIP_RESOURCEACTIVITY *activity)
Definition: misc.c:6686
void * SCIPpqueueFirst(SCIP_PQUEUE *pqueue)
Definition: misc.c:1513
SCIP_Bool SCIPhashsetExists(SCIP_HASHSET *hashset, void *element)
Definition: misc.c:3817
SCIP_Real SCIPregressionGetIntercept(SCIP_REGRESSION *regression)
Definition: misc.c:274
void SCIPhashtableClear(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2398
SCIP_RETCODE SCIPcomputeArraysIntersection(int *array1, int narray1, int *array2, int narray2, int *intersectarray, int *nintersectarray)
Definition: misc.c:10542
void SCIPregressionAddObservation(SCIP_REGRESSION *regression, SCIP_Real x, SCIP_Real y)
Definition: misc.c:381
void SCIPswapReals(SCIP_Real *value1, SCIP_Real *value2)
Definition: misc.c:10383
int SCIPdigraphGetNComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8285
SCIP_Bool SCIPstrToIntValue(const char *str, int *value, char **endptr)
Definition: misc.c:10946
void SCIPpqueueFree(SCIP_PQUEUE **pqueue)
Definition: misc.c:1322
SCIP_RETCODE SCIPprofileInsertCore(SCIP_PROFILE *profile, int left, int right, int height, int *pos, SCIP_Bool *infeasible)
Definition: misc.c:7020
type definitions for return codes for SCIP methods
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randgen, int minrandval, int maxrandval)
Definition: misc.c:10108
SCIP_Real SCIPselectSimpleValue(SCIP_Real lb, SCIP_Real ub, SCIP_Longint maxdnom)
Definition: misc.c:9824
void SCIPdigraphGetComponent(SCIP_DIGRAPH *digraph, int compidx, int **nodes, int *nnodes)
Definition: misc.c:8298
SCIP_Bool SCIPhashmapIsEmpty(SCIP_HASHMAP *hashmap)
Definition: misc.c:3523
int SCIPdisjointsetGetSize(SCIP_DISJOINTSET *djset)
Definition: misc.c:11376
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIP_Bool SCIPqueueIsEmpty(SCIP_QUEUE *queue)
Definition: misc.c:1234
void SCIPpqueueDelPos(SCIP_PQUEUE *pqueue, int pos)
Definition: misc.c:1433
int SCIPprofileGetLoad(SCIP_PROFILE *profile, int pos)
Definition: misc.c:6859
SCIP_Real SCIPhashmapGetImageReal(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3301
int SCIPstrncpy(char *t, const char *s, int size)
Definition: misc.c:10919
int SCIPhashsetGetNSlots(SCIP_HASHSET *hashset)
Definition: misc.c:4000
SCIP_VAR ** x
Definition: circlepacking.c:63
SCIP_RETCODE SCIPdigraphTopoSortComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8219
SCIP_Bool SCIPbtnodeIsRoot(SCIP_BTNODE *node)
Definition: misc.c:8846
real eps
void SCIPmultihashRemoveAll(SCIP_MULTIHASH *multihash)
Definition: misc.c:2210
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2296
SCIP_Real SCIPcalcRootNewton(SCIP_DECL_NEWTONEVAL((*function)), SCIP_DECL_NEWTONEVAL((*derivative)), SCIP_Real *params, int nparams, SCIP_Real x, SCIP_Real eps, int k)
Definition: misc.c:9865
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
SCIP_Longint SCIPmultihashGetNElements(SCIP_MULTIHASH *multihash)
Definition: misc.c:2231
SCIP_Bool SCIPhashsetIsEmpty(SCIP_HASHSET *hashset)
Definition: misc.c:3984
SCIP_Bool SCIPfileExists(const char *filename)
Definition: misc.c:11079
void SCIPqueueClear(SCIP_QUEUE *queue)
Definition: misc.c:1028
int SCIPdigraphGetNNodes(SCIP_DIGRAPH *digraph)
Definition: misc.c:7746
int SCIPprofileGetCapacity(SCIP_PROFILE *profile)
Definition: misc.c:6807
SCIP_Bool SCIPrealToRational(SCIP_Real val, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Longint *nominator, SCIP_Longint *denominator)
Definition: misc.c:9394
SCIP_RETCODE SCIPactivityCreate(SCIP_RESOURCEACTIVITY **activity, SCIP_VAR *var, int duration, int demand)
Definition: misc.c:6641
void SCIPregressionRemoveObservation(SCIP_REGRESSION *regression, SCIP_Real x, SCIP_Real y)
Definition: misc.c:349
SCIP_DECL_HASHKEYEQ(SCIPhashKeyEqString)
Definition: misc.c:2842
void SCIPhashsetRemoveAll(SCIP_HASHSET *hashset)
Definition: misc.c:4016
#define SCIP_DECL_NEWTONEVAL(x)
Definition: type_misc.h:205
void SCIPdisjointsetClear(SCIP_DISJOINTSET *djset)
Definition: misc.c:11252
void SCIPdotWriteClosing(FILE *file)
Definition: misc.c:749
enum SCIP_Confidencelevel SCIP_CONFIDENCELEVEL
Definition: type_misc.h:53
void SCIPdotWriteNode(FILE *file, int node, const char *label, const char *nodetype, const char *fillcolor, const char *bordercolor)
Definition: misc.c:721
SCIP_Bool SCIPstrAtStart(const char *s, const char *t, size_t tlen)
Definition: misc.c:11386
SCIP_Longint * SCIPsparseSolGetLbs(SCIP_SPARSESOL *sparsesol)
Definition: misc.c:849
int SCIPqueueNElems(SCIP_QUEUE *queue)
Definition: misc.c:1247
SCIP_Bool SCIPmultihashExists(SCIP_MULTIHASH *multihash, void *element)
Definition: misc.c:2149
SCIP_BTNODE * SCIPbtnodeGetParent(SCIP_BTNODE *node)
Definition: misc.c:8796
SCIP_RETCODE SCIPdigraphSetNSuccessors(SCIP_DIGRAPH *digraph, int node, int nsuccessors)
Definition: misc.c:7730
void SCIPhashmapPrintStatistics(SCIP_HASHMAP *hashmap, SCIP_MESSAGEHDLR *messagehdlr)
Definition: misc.c:3485
int SCIPactivityGetEnergy(SCIP_RESOURCEACTIVITY *activity)
Definition: misc.c:6716
int SCIPhashmapGetNEntries(SCIP_HASHMAP *hashmap)
Definition: misc.c:3541
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
Definition: misc.c:3549
void SCIPbtnodeSetLeftchild(SCIP_BTNODE *node, SCIP_BTNODE *left)
Definition: misc.c:8933
void * SCIPdigraphGetNodeData(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7756
void SCIPhashsetFree(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem)
Definition: misc.c:3790
static INLINE uint32_t SCIPrealHashCode(double x)
Definition: pub_misc.h:576
void SCIPdigraphSetNodeData(SCIP_DIGRAPH *digraph, void *dataptr, int node)
Definition: misc.c:7772
void SCIPescapeString(char *t, int bufsize, const char *s)
Definition: misc.c:10832
void SCIPhashmapEntrySetImage(SCIP_HASHMAPENTRY *entry, void *image)
Definition: misc.c:3600
void SCIPstrCopySection(const char *str, char startchar, char endchar, char *token, int size, char **endptr)
Definition: misc.c:11007
SCIP_RETCODE SCIPmultihashSafeInsert(SCIP_MULTIHASH *multihash, void *element)
Definition: misc.c:2065
void SCIPcomputeArraysIntersectionInt(int *array1, int narray1, int *array2, int narray2, int *intersectarray, int *nintersectarray)
Definition: misc.c:10559
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
void SCIPdigraphPrint(SCIP_DIGRAPH *digraph, SCIP_MESSAGEHDLR *messagehdlr, FILE *file)
Definition: misc.c:8550
void SCIPactivityFree(SCIP_RESOURCEACTIVITY **activity)
Definition: misc.c:6660
int SCIPdisjointsetFind(SCIP_DISJOINTSET *djset, int element)
Definition: misc.c:11269
void SCIPgmlWriteEdge(FILE *file, unsigned int source, unsigned int target, const char *label, const char *color)
Definition: misc.c:595
unsigned int SCIPqueueRemoveUInt(SCIP_QUEUE *queue)
Definition: misc.c:1164
void SCIPhashtableRemoveAll(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2755
type definitions for problem variables
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2677
SCIP_RETCODE SCIPprofileCreate(SCIP_PROFILE **profile, int capacity)
Definition: misc.c:6755
void SCIPqueueFree(SCIP_QUEUE **queue)
Definition: misc.c:1017
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
Definition: misc.c:7662
SCIP_Bool SCIPbtnodeIsRightchild(SCIP_BTNODE *node)
Definition: misc.c:8884
SCIP_Real SCIPmultihashGetLoad(SCIP_MULTIHASH *multihash)
Definition: misc.c:2241
void * SCIPpqueueRemove(SCIP_PQUEUE *pqueue)
Definition: misc.c:1493
int SCIPdisjointsetGetComponentCount(SCIP_DISJOINTSET *djset)
Definition: misc.c:11366
SCIP_RETCODE SCIPgetRandomSubset(void **set, int nelems, void **subset, int nsubelems, unsigned int randseed)
Definition: misc.c:10480
SCIP_BTNODE * SCIPbtGetRoot(SCIP_BT *tree)
Definition: misc.c:9069
SCIP_RETCODE SCIPhashmapInsertReal(SCIP_HASHMAP *hashmap, void *origin, SCIP_Real image)
Definition: misc.c:3228
void SCIPregressionFree(SCIP_REGRESSION **regression)
Definition: misc.c:432
SCIP_RETCODE SCIPcomputeArraysSetminus(int *array1, int narray1, int *array2, int narray2, int *setminusarray, int *nsetminusarray)
Definition: misc.c:10672
SCIP_DECL_HASHGETKEY(SCIPhashGetKeyStandard)
Definition: misc.c:2870
void SCIPhashtablePrintStatistics(SCIP_HASHTABLE *hashtable, SCIP_MESSAGEHDLR *messagehdlr)
Definition: misc.c:2804
SCIP_BTNODE * SCIPbtnodeGetRightchild(SCIP_BTNODE *node)
Definition: misc.c:8816
SCIP_RETCODE SCIPdigraphAddArcSafe(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
Definition: misc.c:7693
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7804
#define SCIP_Bool
Definition: def.h:91
SCIP_Longint * SCIPsparseSolGetUbs(SCIP_SPARSESOL *sparsesol)
Definition: misc.c:859
void SCIPprintSysError(const char *message)
Definition: misc.c:10769
SCIP_RETCODE SCIPsparseSolCreate(SCIP_SPARSESOL **sparsesol, SCIP_VAR **vars, int nvars, SCIP_Bool cleared)
Definition: misc.c:763
SCIP_RETCODE SCIPhashmapRemoveAll(SCIP_HASHMAP *hashmap)
Definition: misc.c:3633
SCIP_RETCODE SCIPmultihashInsert(SCIP_MULTIHASH *multihash, void *element)
Definition: misc.c:2024
SCIP_Bool SCIPprofileFindLeft(SCIP_PROFILE *profile, int timepoint, int *pos)
Definition: misc.c:6873
SCIP_RETCODE SCIPdigraphResize(SCIP_DIGRAPH *digraph, int nnodes)
Definition: misc.c:7414
unsigned int SCIPqueueFirstUInt(SCIP_QUEUE *queue)
Definition: misc.c:1216
void SCIPrandomPermuteIntArray(SCIP_RANDNUMGEN *randgen, int *array, int begin, int end)
Definition: misc.c:10149
SCIP_Bool SCIPstrToRealValue(const char *str, SCIP_Real *value, char **endptr)
Definition: misc.c:10977
int SCIPdigraphGetNArcs(SCIP_DIGRAPH *digraph)
Definition: misc.c:7786
void SCIPbtFree(SCIP_BT **tree)
Definition: misc.c:8977
SCIP_RETCODE SCIPhashtableSafeInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2579
SCIP_Bool SCIPbtnodeIsLeftchild(SCIP_BTNODE *node)
Definition: misc.c:8866
SCIP_Real SCIPnextafter(SCIP_Real from, SCIP_Real to)
Definition: misc.c:9364
SCIP_RETCODE SCIPdigraphComputeDirectedComponents(SCIP_DIGRAPH *digraph, int compidx, int *strongcomponents, int *strongcompstartidx, int *nstrongcomponents)
Definition: misc.c:8430
void * SCIPmultihashRetrieveNext(SCIP_MULTIHASH *multihash, SCIP_MULTIHASHLIST **multihashlist, void *key)
Definition: misc.c:2113
SCIP_Real SCIPcomputeTwoSampleTTestValue(SCIP_Real meanx, SCIP_Real meany, SCIP_Real variancex, SCIP_Real variancey, SCIP_Real countx, SCIP_Real county)
Definition: misc.c:123
void ** SCIPpqueueElems(SCIP_PQUEUE *pqueue)
Definition: misc.c:1538
#define SCIP_DECL_PQUEUEELEMCHGPOS(x)
Definition: type_misc.h:208
void SCIPprofilePrint(SCIP_PROFILE *profile, SCIP_MESSAGEHDLR *messagehdlr, FILE *file)
Definition: misc.c:6785
void SCIPgmlWriteNodeWeight(FILE *file, unsigned int id, const char *label, const char *nodetype, const char *fillcolor, const char *bordercolor, SCIP_Real weight)
Definition: misc.c:545
SCIP_Bool SCIPfindSimpleRational(SCIP_Real lb, SCIP_Real ub, SCIP_Longint maxdnom, SCIP_Longint *nominator, SCIP_Longint *denominator)
Definition: misc.c:9777
SCIP_RETCODE SCIPdigraphGetArticulationPoints(SCIP_DIGRAPH *digraph, int **articulations, int *narticulations)
Definition: misc.c:8000
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2608
int * SCIPprofileGetTimepoints(SCIP_PROFILE *profile)
Definition: misc.c:6827
SCIP_VAR ** SCIPsparseSolGetVars(SCIP_SPARSESOL *sparsesol)
Definition: misc.c:829
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10130
int * SCIPprofileGetLoads(SCIP_PROFILE *profile)
Definition: misc.c:6837
int SCIPgetRandomInt(int minrandval, int maxrandval, unsigned int *seedp)
Definition: misc.c:9991
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2346
SCIP_Bool SCIPbtIsEmpty(SCIP_BT *tree)
Definition: misc.c:9059
SCIP_Real SCIPgetRandomReal(SCIP_Real minrandval, SCIP_Real maxrandval, unsigned int *seedp)
Definition: misc.c:10004
SCIP_BTNODE * SCIPbtnodeGetLeftchild(SCIP_BTNODE *node)
Definition: misc.c:8806
SCIP_RETCODE SCIPpqueueCreate(SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)))
Definition: misc.c:1295
methods for sorting joint arrays of various types
int SCIPsparseSolGetNVars(SCIP_SPARSESOL *sparsesol)
Definition: misc.c:839
void SCIPbtSetRoot(SCIP_BT *tree, SCIP_BTNODE *root)
Definition: misc.c:9082
SCIP_RETCODE SCIPhashmapSetImageReal(SCIP_HASHMAP *hashmap, void *origin, SCIP_Real image)
Definition: misc.c:3391
SCIP_RETCODE SCIPhashmapRemove(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3439
int SCIPpqueueFind(SCIP_PQUEUE *pqueue, void *elem)
Definition: misc.c:1549
void SCIPbtnodeSetParent(SCIP_BTNODE *node, SCIP_BTNODE *parent)
Definition: misc.c:8919
int SCIPhashmapGetNElements(SCIP_HASHMAP *hashmap)
Definition: misc.c:3533
SCIP_Real SCIPstudentTGetCriticalValue(SCIP_CONFIDENCELEVEL clevel, int df)
Definition: misc.c:106
SCIP_RETCODE SCIPqueueCreate(SCIP_QUEUE **queue, int initsize, SCIP_Real sizefac)
Definition: misc.c:993
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
Definition: misc.c:1394
SCIP_Real SCIPcalcMachineEpsilon(void)
Definition: misc.c:9098
SCIP_Real SCIPhashmapEntryGetImageReal(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3590
#define SCIP_DECL_SORTPTRCOMP(x)
Definition: type_misc.h:188
void * SCIPmultihashRetrieve(SCIP_MULTIHASH *multihash, void *key)
Definition: misc.c:2084
SCIP_Real SCIPnormalCDF(SCIP_Real mean, SCIP_Real variance, SCIP_Real value)
Definition: misc.c:196
SCIP_Real SCIPregressionGetSlope(SCIP_REGRESSION *regression)
Definition: misc.c:264
int SCIPactivityGetDuration(SCIP_RESOURCEACTIVITY *activity)
Definition: misc.c:6696
SCIP_RETCODE SCIPqueueInsertUInt(SCIP_QUEUE *queue, unsigned int elem)
Definition: misc.c:1105
void SCIPhashsetPrintStatistics(SCIP_HASHSET *hashset, SCIP_MESSAGEHDLR *messagehdlr)
Definition: misc.c:3933
SCIP_RETCODE SCIPhashsetInsert(SCIP_HASHSET *hashset, BMS_BLKMEM *blkmem, void *element)
Definition: misc.c:3800
SCIP_RETCODE SCIPhashmapSetImage(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3323
#define SCIP_Real
Definition: def.h:173
void SCIPmultihashPrintStatistics(SCIP_MULTIHASH *multihash, SCIP_MESSAGEHDLR *messagehdlr)
Definition: misc.c:2251
void SCIPpermuteIntArray(int *array, int begin, int end, unsigned int *randseed)
Definition: misc.c:10412
SCIP_VAR ** y
Definition: circlepacking.c:64
SCIP_RETCODE SCIPrandomGetSubset(SCIP_RANDNUMGEN *randgen, void **set, int nelems, void **subset, int nsubelems)
Definition: misc.c:10211
SCIP_Longint SCIPcalcBinomCoef(int n, int m)
Definition: misc.c:10272
int SCIPhashmapEntryGetImageInt(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3580
int SCIPhashtableGetNEntries(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2777
#define SCIP_Longint
Definition: def.h:158
SCIP_RETCODE SCIPcalcIntegralScalar(SCIP_Real *vals, int nvals, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Real *intscalar, SCIP_Bool *success)
Definition: misc.c:9557
void SCIPregressionReset(SCIP_REGRESSION *regression)
Definition: misc.c:400
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2659
void * SCIPqueueRemove(SCIP_QUEUE *queue)
Definition: misc.c:1130
unsigned int SCIPcalcFibHash(SCIP_Real v)
Definition: misc.c:10347
type definitions for message output methods
SCIP_RETCODE SCIPmultihashRemove(SCIP_MULTIHASH *multihash, void *element)
Definition: misc.c:2176
#define nnodes
Definition: gastrans.c:74
int SCIPprofileGetLatestFeasibleStart(SCIP_PROFILE *profile, int lb, int ub, int duration, int height, SCIP_Bool *infeasible)
Definition: misc.c:7289
void SCIPgmlWriteOpening(FILE *file, SCIP_Bool directed)
Definition: misc.c:683
int SCIPcalcMultihashSize(int minsize)
Definition: misc.c:1637
SCIP_RETCODE SCIPregressionCreate(SCIP_REGRESSION **regression)
Definition: misc.c:416
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3156
SCIP_Real SCIPhashtableGetLoad(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2794
common defines and data types used in all packages of SCIP
void * SCIPqueueFirst(SCIP_QUEUE *queue)
Definition: misc.c:1198
void SCIPswapInts(int *value1, int *value2)
Definition: misc.c:10370
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:437
SCIP_RETCODE SCIPbtCreate(SCIP_BT **tree, BMS_BLKMEM *blkmem)
Definition: misc.c:8958
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3281
void SCIPcomputeArraysIntersectionPtr(void **array1, int narray1, void **array2, int narray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void **intersectarray, int *nintersectarray)
Definition: misc.c:10612
int SCIPactivityGetDemand(SCIP_RESOURCEACTIVITY *activity)
Definition: misc.c:6706
void SCIPbtnodeSetData(SCIP_BTNODE *node, void *dataptr)
Definition: misc.c:8905
void SCIPdigraphFree(SCIP_DIGRAPH **digraph)
Definition: misc.c:7568
int SCIPprofileGetNTimepoints(SCIP_PROFILE *profile)
Definition: misc.c:6817
void SCIPpqueueClear(SCIP_PQUEUE *pqueue)
Definition: misc.c:1333
int SCIPregressionGetNObservations(SCIP_REGRESSION *regression)
Definition: misc.c:254
char * SCIPstrtok(char *s, const char *delim, char **ptrptr)
Definition: misc.c:10818
SCIP_Longint SCIPcalcGreComDiv(SCIP_Longint val1, SCIP_Longint val2)
Definition: misc.c:9121
void SCIPdigraphPrintGml(SCIP_DIGRAPH *digraph, FILE *file)
Definition: misc.c:8585
void SCIPbtPrintGml(SCIP_BT *tree, FILE *file)
Definition: misc.c:9029
SCIP_Longint SCIPhashtableGetNElements(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2767
SCIP_Longint SCIPcalcSmaComMul(SCIP_Longint val1, SCIP_Longint val2)
Definition: misc.c:9373
SCIP_Bool SCIPbtnodeIsLeaf(SCIP_BTNODE *node)
Definition: misc.c:8856
preparation of a linear inequality to become a SCIP_ROW
void SCIPsparseSolFree(SCIP_SPARSESOL **sparsesol)
Definition: misc.c:815
SCIP_Real SCIPcomputeGap(SCIP_Real eps, SCIP_Real inf, SCIP_Real primalbound, SCIP_Real dualbound)
Definition: misc.c:11202
void SCIPprofileFree(SCIP_PROFILE **profile)
Definition: misc.c:6769
methods for selecting (weighted) k-medians
memory allocation routines