1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */ 7 /* fuer Informationstechnik Berlin */ 8 /* */ 9 /* SCIP is distributed under the terms of the ZIB Academic License. */ 10 /* */ 11 /* You should have received a copy of the ZIB Academic License */ 12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */ 13 /* */ 14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 15 16 /**@file 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 */ 37 struct SCIP_SparseSol 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 */ 48 } SCIP_QUEUEELEMENT; 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 */ 69 struct SCIP_PQueue 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 */ 80 struct SCIP_HashTable 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 */ 95 struct SCIP_MultiHashList 96 { 97 void* element; /**< this element */ 98 SCIP_MULTIHASHLIST* next; /**< rest of the hash table list */ 99 }; 100 101 /** multihash table data structure */ 102 struct SCIP_MultiHash 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 */ 118 } SCIP_HASHMAPIMAGE; 119 120 /** hash map entry */ 121 struct SCIP_HashMapEntry 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 */ 128 struct SCIP_HashMap 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 */ 140 struct SCIP_HashSet 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 */ 148 struct SCIP_RealArray 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 */ 159 struct SCIP_IntArray 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 */ 170 struct SCIP_BoolArray 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 */ 181 struct SCIP_PtrArray 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 */ 192 struct SCIP_ResourceActivity 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 */ 200 struct SCIP_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 */ 210 struct SCIP_Digraph 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 */ 229 struct SCIP_BtNode 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) */ 245 struct SCIP_Regression 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 */ 259 struct SCIP_RandNumGen 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 */ 268 struct SCIP_DisjointSet 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 281