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