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-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 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 */
36  SCIP_Real* realarr, /**< array of reals */
37  unsigned nreals /**< size of array of reals */
38  );
39 
40 /** graph node structure storing number and distance */
41 typedef struct Graph_Node
42 {
43  int number; /**< node number */
44  SCIP_Real dist; /**< node distance */
45 }GNODE;
46 
47 /** voronoi list node structure storing distance, incoming edge,base and pointer to next list node */
48 typedef struct Vnoi_List_Node
49 {
50  double dist; /**< Distance to the end of the path */
51  signed int edge; /**< First edge to go */
52  signed int base; /**< Voronoi base */
54 }VLIST;
55 
56 /** node */
57 typedef struct ST_Node
58 {
59  int edge; /**< edge to the node */
60  struct ST_Node *parent; /**< pointer to parent node */
61 }NODE;
62 
63 
64 /** a weighted-quick-union-path-compression union find structure */
65 typedef struct UnionFind_Structure
66 {
67  int* parent; /**< parent[i] stores the parent of i */
68  int* size; /**< size[i] stores number of nodes in the tree rooted at i */
69  int count; /**< number of components */
70 }UF;
71 
72 /** integer list node */
73 typedef struct Int_List_Node
74 {
75  int index; /**< int value to store */
76  struct Int_List_Node *parent; /**< pointer to parent node */
77 }IDX;
78 
79 /** Pairing heap node */
80 typedef struct PHeap_Node
81 {
82  int element; /**< int data value */
83  SCIP_Real key; /**< key value */
84  struct PHeap_Node* child; /**< pointer to child node */
85  struct PHeap_Node* sibling; /**< pointer to right sibling */
86  struct PHeap_Node* prev; /**< pointer to to previous node */
87 }PHNODE;
88 
89 
90 /**
91  * Int List
92  */
93 
94 /** append copy of list pertaining to node2 to node1 */
96  SCIP* scip, /**< SCIP data structure */
97  IDX** node1, /**< pointer to the last node of list to be enlarged */
98  IDX* node2, /**< pointer to the last node of source list */
99  SCIP_Bool* conflict /**< pointer to store whether a conflict has been detected by the method */
100  );
101 
102 /** insert a new node */
104  SCIP* scip, /**< SCIP data structure */
105  IDX** node, /**< pointer to the last list node */
106  int nodeval /**< data of the new node */
107  );
108 
109 /** free list */
111  SCIP* scip, /**< SCIP data structure */
112  IDX** node /**< pointer to the last list node */
113  );
114 
115 /** compares distances of two GNODE structures */
116 int GNODECmpByDist(
117  void *first_arg, /**< first argument */
118  void *second_arg /**< second argument */
119  );
120 
121 /**
122  * Linear Link Cut Tree
123  */
124 
125 /** inits a node, setting 'parent' and 'edge' to its default values */
127  NODE* v /**< pointer to node representing the tree */
128  );
129 
130 /** renders w a child of v; v has to be the root of its tree */
132  NODE* v, /**< pointer to node representing the tree */
133  NODE* w, /**< pointer to the child */
134  int edge /**< link edge */
135  );
136 
137 /** cut tree at given node */
138 void SCIPlinkcuttreeCut(
139  NODE* v /**< node to cut at */
140  );
141 
142 /** finds minimum weight chain between node 'start' and distinct root node **/
144  SCIP* scip, /**< SCIP data structure */
145  const SCIP_Real* nodeweight, /**< node weight array */
146  const int* head, /**< head of an arc */
147  const int* stdeg, /**< degree in Steiner tree */
148  const NODE* start, /**< the node to start at */
149  NODE** first, /**< first node of chain */
150  NODE** last /**< last node of chain */
151  );
152 
153 /** finds the max value between node 'v' and the root of the tree **/
155  SCIP* scip, /**< SCIP data structure */
156  const SCIP_Real* cost, /**< edge cost array */
157  NODE* v /**< the node */
158  );
159 
160 /** makes vertex v the root of the link cut tree */
162  NODE* v /**< the vertex to become the root */
163  );
164 
165 
166 /*
167  * Pairing Heap
168  */
169 
170 /** links nodes 'root1' and 'root2' together */
172  SCIP* scip, /**< SCIP data structure */
173  PHNODE *root1, /**< pointer to root of first heap */
174  PHNODE *root2 /**< pointer to root of second heap */
175  );
176 
178  SCIP* scip, /**< SCIP data structure */
179  PHNODE* root1, /**< pointer to root of first heap */
180  PHNODE* root2 /**< pointer to root of second heap */
181  );
182 
183 /** inserts a new node into the pairing heap */
185  SCIP* scip, /**< SCIP data structure */
186  PHNODE** root,
187  int element,
188  SCIP_Real key,
189  int* size
190  );
191 
192 /** deletes the root of the paring heap, concomitantly storing its data and key in '*element' and '*key' respectively */
194  SCIP* scip, /**< SCIP data structure */
195  int* element, /**< data of the root */
196  SCIP_Real* key, /**< key of the root */
197  PHNODE** root, /**< pointer to root of the heap */
198  int* size /**< pointer to size of the heap */
199  );
200 
201 /** links nodes 'root1' and 'root2' together, roots the resulting tree at root1 and sets root2 to NULL */
203  SCIP* scip, /**< SCIP data structure */
204  PHNODE** root1, /**< pointer to root of first heap */
205  PHNODE** root2, /**< pointer to root of second heap */
206  int* sizeroot1, /**< pointer to size of first heap */
207  int* sizeroot2 /**< pointer to size of second heap */
208  );
209 
210 /** frees the paring heap with root 'p' */
211 void SCIPpairheapFree(
212  SCIP* scip, /**< SCIP data structure */
213  PHNODE** root /**< root of heap to be freed */
214  );
215 
216 /** stores all elements of the pairing heap in an array */
218  SCIP* scip, /**< SCIP data structure */
219  PHNODE* root, /**< root of the heap */
220  int size, /**< size of the array */
221  int** elements /**< pointer to array */
222  );
223 
224 /*
225  * Union-Find data structure
226  */
227 
228 /** initializes the union-find structure 'uf' with 'length' many components (of size one) */
230  SCIP* scip, /**< SCIP data structure */
231  UF* uf, /**< union find data structure */
232  int length /**< number of components */
233  );
234 
235 /** clears the union-find structure 'uf'*/
237  SCIP* scip, /**< SCIP data structure */
238  UF* uf, /**< union find data structure */
239  int length /**< number of components */
240  );
241 
242 /** finds and returns the component identifier */
244  UF* uf, /**< union find data structure */
245  int element /**< element to be found */
246  );
247 
248 /** merges the components containing p and q respectively */
250  UF* uf, /**< union find data structure */
251  int p, /**< first component */
252  int q, /**< second component*/
253  SCIP_Bool compress /**< compress union find structure? */
254  );
255 
256 /** frees the data fields of the union-find structure */
258  SCIP* scip, /**< SCIP data structure */
259  UF* uf /**< union find data structure */
260  );
261 
262 
263 #ifdef __cplusplus
264 }
265 #endif
266 
267 #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:60
struct PHeap_Node * sibling
Definition: misc_stp.h:85
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:54
struct PHeap_Node * child
Definition: misc_stp.h:84
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:43
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:51
struct Vnoi_List_Node * next
Definition: misc_stp.h:53
int SCIPStpunionfindFind(UF *uf, int element)
Definition: misc_stp.c:728
SCIP_Real dist
Definition: misc_stp.h:44
int edge
Definition: misc_stp.h:59
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:52
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:70
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:83
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:86
int element
Definition: misc_stp.h:82
#define SCIP_Real
Definition: def.h:163
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:50
SCIP_Real misc_stp_maxReal(SCIP_Real *realarr, unsigned nreals)
Definition: misc_stp.c:41
struct Int_List_Node * parent
Definition: misc_stp.h:76
SCIP callable library.
struct PHeap_Node PHNODE