Scippy

SCIP

Solving Constraint Integer Programs

misc_stp.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-2019 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 scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file misc_stp.h
17  * @brief miscellaneous methods used for solving Steiner problems
18  * @author Daniel Rehfeldt
19  *
20  * This file includes miscellaneous methods used for solving Steiner problems. For more details see \ref STP_MISC page.
21  */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #ifndef __SCIP_MISC_STP_H__
26 #define __SCIP_MISC_STP_H__
27 
28 #include "scip/scip.h"
29 
30 #ifdef __cplusplus
31 extern "C" {
32 #endif
33 
34 /** returns maximum of given SCIP_Real values */
35 extern
37  SCIP_Real* realarr, /**< array of reals */
38  unsigned nreals /**< size of array of reals */
39  );
40 
41 /** graph node structure storing number and distance */
42 typedef struct Graph_Node
43 {
44  int number; /**< node number */
45  SCIP_Real dist; /**< node distance */
46 }GNODE;
47 
48 /** voronoi list node structure storing distance, incoming edge,base and pointer to next list node */
49 typedef struct Vnoi_List_Node
50 {
51  double dist; /**< Distance to the end of the path */
52  signed int edge; /**< First edge to go */
53  signed int base; /**< Voronoi base */
55 }VLIST;
56 
57 /** node */
58 typedef struct ST_Node
59 {
60  int edge; /**< edge to the node */
61  struct ST_Node *parent; /**< pointer to parent node */
62 }NODE;
63 
64 
65 /** a weighted-quick-union-path-compression union find structure */
66 typedef struct UnionFind_Structure
67 {
68  int* parent; /**< parent[i] stores the parent of i */
69  int* size; /**< size[i] stores number of nodes in the tree rooted at i */
70  int count; /**< number of components */
71 }UF;
72 
73 /** integer list node */
74 typedef struct Int_List_Node
75 {
76  int index; /**< int value to store */
77  struct Int_List_Node *parent; /**< pointer to parent node */
78 }IDX;
79 
80 /** Pairing heap node */
81 typedef struct PHeap_Node
82 {
83  int element; /**< int data value */
84  SCIP_Real key; /**< key value */
85  struct PHeap_Node* child; /**< pointer to child node */
86  struct PHeap_Node* sibling; /**< pointer to right sibling */
87  struct PHeap_Node* prev; /**< pointer to to previous node */
88 }PHNODE;
89 
90 
91 /**
92  * Int List
93  */
94 
95 /** append copy of list pertaining to node2 to node1 */
96 extern
98  SCIP* scip, /**< SCIP data structure */
99  IDX** node1, /**< pointer to the last node of list to be enlarged */
100  IDX* node2, /**< pointer to the last node of source list */
101  SCIP_Bool* conflict /**< pointer to store whether a conflict has been detected by the method */
102  );
103 
104 /** insert a new node */
105 extern
107  SCIP* scip, /**< SCIP data structure */
108  IDX** node, /**< pointer to the last list node */
109  int nodeval /**< data of the new node */
110  );
111 
112 /** free list */
113 extern
115  SCIP* scip, /**< SCIP data structure */
116  IDX** node /**< pointer to the last list node */
117  );
118 
119 /** compares distances of two GNODE structures */
120 extern
121 int GNODECmpByDist(
122  void *first_arg, /**< first argument */
123  void *second_arg /**< second argument */
124  );
125 
126 /**
127  * Linear Link Cut Tree
128  */
129 
130 /** inits a node, setting 'parent' and 'edge' to its default values */
131 extern
133  NODE* v /**< pointer to node representing the tree */
134  );
135 
136 /** renders w a child of v; v has to be the root of its tree */
137 extern
139  NODE* v, /**< pointer to node representing the tree */
140  NODE* w, /**< pointer to the child */
141  int edge /**< link edge */
142  );
143 
144 /** cut tree at given node */
145 extern
146 void SCIPlinkcuttreeCut(
147  NODE* v /**< node to cut at */
148  );
149 
150 /** finds minimum weight chain between node 'start' and distinct root node **/
152  SCIP* scip, /**< SCIP data structure */
153  const SCIP_Real* nodeweight, /**< node weight array */
154  const int* head, /**< head of an arc */
155  const int* stdeg, /**< degree in Steiner tree */
156  const NODE* start, /**< the node to start at */
157  NODE** first, /**< first node of chain */
158  NODE** last /**< last node of chain */
159  );
160 
161 /** finds the max value between node 'v' and the root of the tree **/
162 extern
164  SCIP* scip, /**< SCIP data structure */
165  const SCIP_Real* cost, /**< edge cost array */
166  NODE* v /**< the node */
167  );
168 
169 /** makes vertex v the root of the link cut tree */
170 extern
172  NODE* v /**< the vertex to become the root */
173  );
174 
175 
176 /*
177  * Pairing Heap
178  */
179 
180 /** links nodes 'root1' and 'root2' together */
181 extern
183  SCIP* scip, /**< SCIP data structure */
184  PHNODE *root1, /**< pointer to root of first heap */
185  PHNODE *root2 /**< pointer to root of second heap */
186  );
187 
188 extern
190  SCIP* scip, /**< SCIP data structure */
191  PHNODE* root1, /**< pointer to root of first heap */
192  PHNODE* root2 /**< pointer to root of second heap */
193  );
194 
195 /** inserts a new node into the pairing heap */
196 extern
198  SCIP* scip, /**< SCIP data structure */
199  PHNODE** root,
200  int element,
201  SCIP_Real key,
202  int* size
203  );
204 
205 /** deletes the root of the paring heap, concomitantly storing its data and key in '*element' and '*key' respectively */
206 extern
208  SCIP* scip, /**< SCIP data structure */
209  int* element, /**< data of the root */
210  SCIP_Real* key, /**< key of the root */
211  PHNODE** root, /**< pointer to root of the heap */
212  int* size /**< pointer to size of the heap */
213  );
214 
215 /** links nodes 'root1' and 'root2' together, roots the resulting tree at root1 and sets root2 to NULL */
216 extern
218  SCIP* scip, /**< SCIP data structure */
219  PHNODE** root1, /**< pointer to root of first heap */
220  PHNODE** root2, /**< pointer to root of second heap */
221  int* sizeroot1, /**< pointer to size of first heap */
222  int* sizeroot2 /**< pointer to size of second heap */
223  );
224 
225 /** frees the paring heap with root 'p' */
226 extern
227 void SCIPpairheapFree(
228  SCIP* scip, /**< SCIP data structure */
229  PHNODE** root /**< root of heap to be freed */
230  );
231 
232 /** stores all elements of the pairing heap in an array */
233 extern
235  SCIP* scip, /**< SCIP data structure */
236  PHNODE* root, /**< root of the heap */
237  int size, /**< size of the array */
238  int** elements /**< pointer to array */
239  );
240 
241 /*
242  * Union-Find data structure
243  */
244 
245 /** initializes the union-find structure 'uf' with 'length' many components (of size one) */
246 extern
248  SCIP* scip, /**< SCIP data structure */
249  UF* uf, /**< union find data structure */
250  int length /**< number of components */
251  );
252 
253 /** clears the union-find structure 'uf'*/
254 extern
256  SCIP* scip, /**< SCIP data structure */
257  UF* uf, /**< union find data structure */
258  int length /**< number of components */
259  );
260 
261 /** finds and returns the component identifier */
262 extern
264  UF* uf, /**< union find data structure */
265  int element /**< element to be found */
266  );
267 
268 /** merges the components containing p and q respectively */
269 extern
271  UF* uf, /**< union find data structure */
272  int p, /**< first component */
273  int q, /**< second component*/
274  SCIP_Bool compress /**< compress union find structure? */
275  );
276 
277 /** frees the data fields of the union-find structure */
278 extern
280  SCIP* scip, /**< SCIP data structure */
281  UF* uf /**< union find data structure */
282  );
283 
284 
285 #ifdef __cplusplus
286 }
287 #endif
288 
289 #endif
SCIP_RETCODE SCIPStpunionfindInit(SCIP *scip, UF *uf, int length)
Definition: misc_stp.c:689
struct Graph_Node GNODE
struct UnionFind_Structure UF
SCIP_Real SCIPlinkcuttreeFindMinChain(SCIP *scip, const SCIP_Real *nodeweight, const int *head, const int *stdeg, const NODE *start, NODE **first, NODE **last)
Definition: misc_stp.c:258
struct ST_Node * parent
Definition: misc_stp.h:61
struct PHeap_Node * sibling
Definition: misc_stp.h:86
void SCIPpairheapMeldheaps(SCIP *scip, PHNODE **root1, PHNODE **root2, int *sizeroot1, int *sizeroot2)
Definition: misc_stp.c:599
struct Vnoi_List_Node VLIST
PHNODE * SCIPpairheapAddtoheap(SCIP *scip, PHNODE *root1, PHNODE *root2)
Definition: misc_stp.c:429
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
struct PHeap_Node * child
Definition: misc_stp.h:85
SCIP_RETCODE SCIPpairheapDeletemin(SCIP *scip, int *element, SCIP_Real *key, PHNODE **root, int *size)
Definition: misc_stp.c:562
int number
Definition: misc_stp.h:44
void SCIPintListNodeFree(SCIP *scip, IDX **node)
Definition: misc_stp.c:205
void SCIPpairheapFree(SCIP *scip, PHNODE **root)
Definition: misc_stp.c:627
SCIP_VAR * w
Definition: circlepacking.c:58
signed int edge
Definition: misc_stp.h:52
struct Vnoi_List_Node * next
Definition: misc_stp.h:54
int SCIPStpunionfindFind(UF *uf, int element)
Definition: misc_stp.c:728
SCIP_Real dist
Definition: misc_stp.h:45
int edge
Definition: misc_stp.h:60
SCIP_RETCODE SCIPintListNodeAppendCopy(SCIP *scip, IDX **node1, IDX *node2, SCIP_Bool *conflict)
Definition: misc_stp.c:94
NODE * SCIPlinkcuttreeFindMax(SCIP *scip, const SCIP_Real *cost, NODE *v)
Definition: misc_stp.c:327
signed int base
Definition: misc_stp.h:53
Definition: grphload.c:88
SCIP_RETCODE SCIPintListNodeInsert(SCIP *scip, IDX **node, int nodeval)
Definition: misc_stp.c:77
int GNODECmpByDist(void *first_arg, void *second_arg)
void SCIPlinkcuttreeLink(NODE *v, NODE *w, int edge)
Definition: misc_stp.c:236
void SCIPStpunionfindClear(SCIP *scip, UF *uf, int length)
Definition: misc_stp.c:708
struct Int_List_Node IDX
#define SCIP_Bool
Definition: def.h:69
PHNODE * SCIPpairheapMergeheaps(SCIP *scip, PHNODE *root1, PHNODE *root2)
Definition: misc_stp.c:386
void SCIPlinkcuttreeEvert(NODE *v)
Definition: misc_stp.c:352
void SCIPStpunionfindUnion(UF *uf, int p, int q, SCIP_Bool compress)
Definition: misc_stp.c:752
struct ST_Node NODE
SCIP_Real key
Definition: misc_stp.h:84
SCIP_RETCODE SCIPpairheapInsert(SCIP *scip, PHNODE **root, int element, SCIP_Real key, int *size)
Definition: misc_stp.c:528
void SCIPlinkcuttreeInit(NODE *v)
Definition: misc_stp.c:227
struct PHeap_Node * prev
Definition: misc_stp.h:87
int element
Definition: misc_stp.h:83
#define SCIP_Real
Definition: def.h:157
SCIP_RETCODE SCIPpairheapBuffarr(SCIP *scip, PHNODE *root, int size, int **elements)
Definition: misc_stp.c:670
void SCIPStpunionfindFree(SCIP *scip, UF *uf)
Definition: misc_stp.c:795
void SCIPlinkcuttreeCut(NODE *v)
Definition: misc_stp.c:249
double dist
Definition: misc_stp.h:51
SCIP_Real misc_stp_maxReal(SCIP_Real *realarr, unsigned nreals)
Definition: misc_stp.c:41
struct Int_List_Node * parent
Definition: misc_stp.h:77
SCIP callable library.
struct PHeap_Node PHNODE