Scippy

SCIP

Solving Constraint Integer Programs

struct_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-2020 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file struct_misc.h
17  * @ingroup INTERNALAPI
18  * @brief miscellaneous datastructures
19  * @author Tobias Achterberg
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #ifndef __SCIP_STRUCT_MISC_H__
25 #define __SCIP_STRUCT_MISC_H__
26 
27 
28 #include "scip/def.h"
29 #include "blockmemshell/memory.h"
30 #include "scip/type_misc.h"
31 
32 #ifdef __cplusplus
33 extern "C" {
34 #endif
35 
36 /** data structure for sparse solutions */
38 {
39  SCIP_VAR** vars; /**< variables */
40  SCIP_Longint* lbvalues; /**< array of lower bounds */
41  SCIP_Longint* ubvalues; /**< array of upper bounds */
42  int nvars; /**< number of variables */
43 };
44 
45 typedef union {
46  void* ptr; /**< pointer element */
47  unsigned int uinteger; /**< unsigned integer element */
49 
50 /** (circular) Queue data structure */
51 struct SCIP_Queue
52 {
53  SCIP_Real sizefac; /**< memory growing factor */
54  SCIP_QUEUEELEMENT* slots; /**< array of element slots */
55  int firstfree; /**< first free slot */
56  int firstused; /**< first used slot */
57  int size; /**< total number of available element slots */
58 };
59 
60 /** priority queue data structure
61  * Elements are stored in an array, which grows dynamically in size as new elements are added to the queue.
62  * The ordering is done through a pointer comparison function.
63  * The array is organized as follows. The root element (that is the "best" element \f$ r \f$ with \f$ r \leq x \f$ for all \f$ x \f$ )
64  * is stored in position 0. The children of an element at position \f$ p \f$ are stored at positions \f$ q_1 = 2*p+1 \f$ and
65  * \f$ q_2 = 2*p+2 \f$ . That means, the parent of the element at position \f$ q \f$ is at position \f$ p = (q-1)/2 \f$ .
66  * At any time, the condition holds that \f$ p \leq q \f$ for each parent \f$ p \f$ and its children \f$ q \f$ .
67  * Insertion and removal of single elements needs time \f$ O(log n) \f$ .
68  */
70 {
71  SCIP_Real sizefac; /**< memory growing factor */
72  SCIP_DECL_SORTPTRCOMP((*ptrcomp)); /**< compares two data elements */
73  SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos));/**< callback to act on position change of elem in priority queue, or NULL */
74  void** slots; /**< array of element slots */
75  int len; /**< number of used element slots */
76  int size; /**< total number of available element slots */
77 };
78 
79 /** hash table data structure */
81 {
82  SCIP_DECL_HASHGETKEY((*hashgetkey)); /**< gets the key of the given element */
83  SCIP_DECL_HASHKEYEQ ((*hashkeyeq)); /**< returns TRUE iff both keys are equal */
84  SCIP_DECL_HASHKEYVAL((*hashkeyval)); /**< returns the hash value of the key */
85  BMS_BLKMEM* blkmem; /**< block memory used to store hash map entries */
86  void* userptr; /**< user pointer */
87  void** slots; /**< slots of the hash table */
88  uint32_t* hashes; /**< hash values of elements stored in slots */
89  uint32_t shift; /**< power such that 2^(32-shift) == nslots */
90  uint32_t mask; /**< mask used for fast modulo, i.e. nslots - 1 */
91  uint32_t nelements; /**< number of elements in the hashtable */
92 };
93 
94 /** element list to store single elements of a hash table */
96 {
97  void* element; /**< this element */
98  SCIP_MULTIHASHLIST* next; /**< rest of the hash table list */
99 };
100 
101 /** multihash table data structure */
103 {
104  SCIP_DECL_HASHGETKEY((*hashgetkey)); /**< gets the key of the given element */
105  SCIP_DECL_HASHKEYEQ ((*hashkeyeq)); /**< returns TRUE iff both keys are equal */
106  SCIP_DECL_HASHKEYVAL((*hashkeyval)); /**< returns the hash value of the key */
107  BMS_BLKMEM* blkmem; /**< block memory used to store hash map entries */
108  SCIP_MULTIHASHLIST** lists; /**< multihash table lists of the hash table */
109  int nlists; /**< number of lists stored in the hash table */
110  void* userptr; /**< user pointer */
111  SCIP_Longint nelements; /**< number of elements in the hashtable */
112 };
113 
114 typedef union {
115  void* ptr; /**< pointer image */
116  int integer; /**< integer image */
117  SCIP_Real real; /**< real image */
119 
120 /** hash map entry */
122 {
123  void* origin; /**< origin of element */
124  SCIP_HASHMAPIMAGE image; /**< image of element */
125 };
126 
127 /** hash map data structure to map pointers on pointers */
129 {
130  BMS_BLKMEM* blkmem; /**< block memory used to store hash map entries */
131  SCIP_HASHMAPENTRY* slots; /**< buffer for hashmap entries */
132  uint32_t* hashes; /**< hashes of elements */
133  uint32_t shift; /**< power such that 2^(32-shift) == nslots */
134  uint32_t mask; /**< mask used for fast modulo, i.e. nslots - 1 */
135  uint32_t nelements; /**< number of elements in the hashtable */
136  SCIP_HASHMAPTYPE hashmaptype; /**< type of entries */
137 };
138 
139 /** lightweight hash set data structure to map pointers on pointers */
141 {
142  void** slots; /**< buffer for hashmap entries */
143  uint32_t shift; /**< power such that 2^(64-shift) == nslots */
144  uint32_t nelements; /**< number of elements in the hashtable */
145 };
146 
147 /** dynamic array for storing real values */
149 {
150  BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */
151  SCIP_Real* vals; /**< array values */
152  int valssize; /**< size of vals array */
153  int firstidx; /**< index of first element in vals array */
154  int minusedidx; /**< index of first non zero element in vals array */
155  int maxusedidx; /**< index of last non zero element in vals array */
156 };
157 
158 /** dynamic array for storing int values */
160 {
161  BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */
162  int* vals; /**< array values */
163  int valssize; /**< size of vals array */
164  int firstidx; /**< index of first element in vals array */
165  int minusedidx; /**< index of first non zero element in vals array */
166  int maxusedidx; /**< index of last non zero element in vals array */
167 };
168 
169 /** dynamic array for storing bool values */
171 {
172  BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */
173  SCIP_Bool* vals; /**< array values */
174  int valssize; /**< size of vals array */
175  int firstidx; /**< index of first element in vals array */
176  int minusedidx; /**< index of first non zero element in vals array */
177  int maxusedidx; /**< index of last non zero element in vals array */
178 };
179 
180 /** dynamic array for storing pointers */
182 {
183  BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */
184  void** vals; /**< array values */
185  int valssize; /**< size of vals array */
186  int firstidx; /**< index of first element in vals array */
187  int minusedidx; /**< index of first non zero element in vals array */
188  int maxusedidx; /**< index of last non zero element in vals array */
189 };
190 
191 /** resource activity */
193 {
194  SCIP_VAR* var; /**< start time variable of the activity */
195  int duration; /**< duration of the activity */
196  int demand; /**< demand of the activity */
197 };
198 
199 /** resource profile */
201 {
202  int* timepoints; /**< time point array */
203  int* loads; /**< array holding the load for each time point */
204  int capacity; /**< capacity of the resource profile */
205  int ntimepoints; /**< current number of entries */
206  int arraysize; /**< current array size */
207 };
208 
209 /** digraph structure to store and handle graphs */
211 {
212  BMS_BLKMEM* blkmem; /**< block memory pointer to store the data */
213  int** successors; /**< adjacency list: for each node (first dimension) list of all successors */
214  void*** arcdata; /**< arc data corresponding to the arcs to successors given by the successors array */
215  void** nodedata; /**< data for each node of graph */
216  int* successorssize; /**< sizes of the successor lists for the nodes */
217  int* nsuccessors; /**< number of successors stored in the adjacency lists of the nodes */
218  int* components; /**< array to store the node indices of the components, one component after the other */
219  int* componentstarts; /**< array to store the start indices of the components in the components array */
220  int* articulations; /**< array of size narticulations to store the node indices of the articulation points */
221  int ncomponents; /**< number of undirected components stored */
222  int componentstartsize; /**< size of array componentstarts */
223  int nnodes; /**< number of nodes, nodes should be numbered from 0 to nnodes-1 */
224  int narticulations; /**< number of articulation points among the graph nodes */
225  SCIP_Bool articulationscheck; /**< TRUE if the (computed) articulation nodes are up-to-date and FALSE otherwise */
226 };
227 
228 /** binary node data structure for binary tree */
230 {
231  SCIP_BTNODE* parent; /**< pointer to the parent node */
232  SCIP_BTNODE* left; /**< pointer to the left child node */
233  SCIP_BTNODE* right; /**< pointer to the right child node */
234  void* dataptr; /**< user pointer */
235 };
236 
237 /** binary search tree data structure */
238 struct SCIP_Bt
239 {
240  SCIP_BTNODE* root; /**< pointer to the dummy root node; root is left child */
241  BMS_BLKMEM* blkmem; /**< block memory used to store tree nodes */
242 };
243 
244 /** data structure for incremental linear regression of data points (X_i, Y_i) */
246 {
247  SCIP_Real intercept; /**< the current axis intercept of the regression */
248  SCIP_Real slope; /**< the current slope of the regression */
249  SCIP_Real meanx; /**< mean of all X observations */
250  SCIP_Real meany; /**< mean of all Y observations */
251  SCIP_Real sumxy; /**< accumulated sum of all products X * Y */
252  SCIP_Real variancesumx; /**< incremental variance term for X observations */
253  SCIP_Real variancesumy; /**< incremental variance term for Y observations */
254  SCIP_Real corrcoef; /**< correlation coefficient of X and Y */
255  int nobservations; /**< number of observations so far */
256 };
257 
258 /** random number generator data */
260 {
261  uint32_t seed; /**< start seed */
262  uint32_t xor_seed; /**< Xorshift seed */
263  uint32_t mwc_seed; /**< Multiply-with-carry seed */
264  uint32_t cst_seed; /**< constant seed */
265 };
266 
267 /** disjoint set (disjoint set (union find)) data structure for querying and updating connectedness in a graph with integer vertices 0,...,n - 1 */
269 {
270  int* parents; /**< array to store the parent node index for every vertex */
271  int* sizes; /**< array to store the size of the subtree rooted at each vertex */
272  int size; /**< the number of vertices in the graph */
273  int componentcount; /**< counter for the number of connected components of the graph */
274 };
275 
276 #ifdef __cplusplus
277 }
278 #endif
279 
280 #endif
uint32_t * hashes
Definition: struct_misc.h:132
SCIP_BTNODE * parent
Definition: struct_misc.h:231
void ** slots
Definition: struct_misc.h:87
SCIP_Real * vals
Definition: struct_misc.h:151
BMS_BLKMEM * blkmem
Definition: struct_misc.h:85
SCIP_QUEUEELEMENT * slots
Definition: struct_misc.h:54
void *** arcdata
Definition: struct_misc.h:214
BMS_BLKMEM * blkmem
Definition: struct_misc.h:212
#define SCIP_DECL_HASHKEYVAL(x)
Definition: type_misc.h:181
type definitions for miscellaneous datastructures
uint32_t shift
Definition: struct_misc.h:133
BMS_BLKMEM * blkmem
Definition: struct_misc.h:241
SCIP_Real intercept
Definition: struct_misc.h:247
void ** nodedata
Definition: struct_misc.h:215
int firstfree
Definition: struct_misc.h:55
#define SCIP_DECL_HASHGETKEY(x)
Definition: type_misc.h:175
int * componentstarts
Definition: struct_misc.h:219
uint32_t * hashes
Definition: struct_misc.h:88
uint32_t shift
Definition: struct_misc.h:143
uint32_t mwc_seed
Definition: struct_misc.h:263
uint32_t mask
Definition: struct_misc.h:90
void ** slots
Definition: struct_misc.h:142
uint32_t cst_seed
Definition: struct_misc.h:264
uint32_t nelements
Definition: struct_misc.h:91
SCIP_VAR ** vars
Definition: struct_misc.h:39
SCIP_MULTIHASHLIST ** lists
Definition: struct_misc.h:108
void * dataptr
Definition: struct_misc.h:234
unsigned int uinteger
Definition: struct_misc.h:47
SCIP_Real corrcoef
Definition: struct_misc.h:254
BMS_BLKMEM * blkmem
Definition: struct_misc.h:130
void * userptr
Definition: struct_misc.h:86
SCIP_BTNODE * root
Definition: struct_misc.h:240
int ** successors
Definition: struct_misc.h:213
void ** slots
Definition: struct_misc.h:74
SCIP_Real meany
Definition: struct_misc.h:250
BMS_BLKMEM * blkmem
Definition: struct_misc.h:150
BMS_BLKMEM * blkmem
Definition: struct_misc.h:161
SCIP_BTNODE * left
Definition: struct_misc.h:232
int * timepoints
Definition: struct_misc.h:202
uint32_t mask
Definition: struct_misc.h:134
SCIP_Real variancesumx
Definition: struct_misc.h:252
SCIP_Real sizefac
Definition: struct_misc.h:71
SCIP_Longint * lbvalues
Definition: struct_misc.h:40
uint32_t shift
Definition: struct_misc.h:89
int narticulations
Definition: struct_misc.h:224
SCIP_Real slope
Definition: struct_misc.h:248
enum SCIP_Hashmaptype SCIP_HASHMAPTYPE
Definition: type_misc.h:54
uint32_t xor_seed
Definition: struct_misc.h:262
SCIP_Bool * vals
Definition: struct_misc.h:173
int * components
Definition: struct_misc.h:218
#define SCIP_Bool
Definition: def.h:70
SCIP_Real variancesumy
Definition: struct_misc.h:253
int * successorssize
Definition: struct_misc.h:216
#define SCIP_DECL_PQUEUEELEMCHGPOS(x)
Definition: type_misc.h:184
int * articulations
Definition: struct_misc.h:220
SCIP_Longint * ubvalues
Definition: struct_misc.h:41
SCIP_Real sumxy
Definition: struct_misc.h:251
uint32_t nelements
Definition: struct_misc.h:144
SCIP_Bool articulationscheck
Definition: struct_misc.h:225
SCIP_Real meanx
Definition: struct_misc.h:249
#define SCIP_DECL_SORTPTRCOMP(x)
Definition: type_misc.h:172
SCIP_HASHMAPTYPE hashmaptype
Definition: struct_misc.h:136
SCIP_HASHMAPENTRY * slots
Definition: struct_misc.h:131
SCIP_BTNODE * right
Definition: struct_misc.h:233
#define SCIP_Real
Definition: def.h:163
int componentstartsize
Definition: struct_misc.h:222
uint32_t nelements
Definition: struct_misc.h:135
BMS_BLKMEM * blkmem
Definition: struct_misc.h:107
BMS_BLKMEM * blkmem
Definition: struct_misc.h:172
#define SCIP_Longint
Definition: def.h:148
#define SCIP_DECL_HASHKEYEQ(x)
Definition: type_misc.h:178
void ** vals
Definition: struct_misc.h:184
SCIP_MULTIHASHLIST * next
Definition: struct_misc.h:98
BMS_BLKMEM * blkmem
Definition: struct_misc.h:183
int * nsuccessors
Definition: struct_misc.h:217
SCIP_Longint nelements
Definition: struct_misc.h:111
SCIP_Real sizefac
Definition: struct_misc.h:53
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:429
SCIP_HASHMAPIMAGE image
Definition: struct_misc.h:124
int firstused
Definition: struct_misc.h:56
memory allocation routines