Scippy

SCIP

Solving Constraint Integer Programs

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