Scippy

SCIP

Solving Constraint Integer Programs

graphheaps.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-2022 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 graphheaps.h
17  * @brief includes (inline) graph heap methods used for Steiner tree problems
18  * @author Thorsten Koch
19  * @author Daniel Rehfeldt
20  *
21  *
22  */
23 
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
25 
26 
27 #ifndef APPLICATIONS_STP_SRC_GRAPHHEAPS_H_
28 #define APPLICATIONS_STP_SRC_GRAPHHEAPS_H_
29 
30 #include "scip/scip.h"
31 #include "graphdefs.h"
32 #include "portab.h"
33 
34 
35 #ifdef __cplusplus
36 extern "C" {
37 #endif
38 
39 
40 /** gets closest node from heap */
41 inline static int nearestX(
42  int* RESTRICT heap,
43  int* RESTRICT state,
44  int* RESTRICT count, /* pointer to store the number of elements on the heap */
45  const SCIP_Real* pathdist)
46 {
47  int k;
48  int t;
49  int c;
50  int j;
51  int dcount;
52 
53  /* Heap shift down
54  */
55  k = heap[1];
56  j = 1;
57  c = 2;
58  heap[1] = heap[(*count)--];
59  state[heap[1]] = 1;
60 
61  dcount = *count;
62 
63  if (dcount > 2)
64  if (LT(pathdist[heap[3]], pathdist[heap[2]]))
65  c++;
66 
67  while((c <= dcount) && GT(pathdist[heap[j]], pathdist[heap[c]]))
68  {
69  t = heap[c];
70  heap[c] = heap[j];
71  heap[j] = t;
72  state[heap[j]] = j;
73  state[heap[c]] = c;
74  j = c;
75  c += c;
76 
77  if ((c + 1) <= dcount)
78  if (LT(pathdist[heap[c + 1]], pathdist[heap[c]]))
79  c++;
80  }
81  return(k);
82 }
83 
84 /** corrects the heap */
85 inline static void correctX(
86  int* RESTRICT heap,
87  int* RESTRICT state,
88  int* RESTRICT count, /* pointer to store the number of elements on the heap */
89  SCIP_Real* RESTRICT pathdist,
90  int* RESTRICT pathedge,
91  int l,
92  int k,
93  int e,
94  SCIP_Real cost
95  )
96 {
97  int t;
98  int c;
99  int j;
100 
101  pathdist[l] = (pathdist[k] + cost);
102 
103  if( pathedge != NULL )
104  pathedge[l] = e;
105 
106  /* not yet in heap? */
107  if( state[l] == UNKNOWN )
108  {
109  heap[++(*count)] = l;
110  state[l] = (*count);
111  }
112 
113  /* Heap shift up
114  */
115  j = state[l];
116  c = j / 2;
117 
118  while( (j > 1) && pathdist[heap[c]] > pathdist[heap[j]] )
119  {
120  t = heap[c];
121  heap[c] = heap[j];
122  heap[j] = t;
123  state[heap[j]] = j;
124  state[heap[c]] = c;
125  j = c;
126  c = j / 2;
127  }
128 }
129 
130 
131 /** resets element from heap */
132 inline static void resetX(
133  SCIP_Real* RESTRICT pathdist,
134  int* RESTRICT heap,
135  int* RESTRICT state,
136  int* RESTRICT count,
137  int node,
138  SCIP_Real distnew
139  )
140 {
141  int c;
142  int j;
143 
144  pathdist[node] = distnew;
145 
146  heap[++(*count)] = node;
147  state[node] = (*count);
148 
149  /* heap shift up */
150  j = state[node];
151  c = j / 2;
152 
153  while( (j > 1) && pathdist[heap[c]] > pathdist[heap[j]] )
154  {
155  const int t = heap[c];
156  heap[c] = heap[j];
157  heap[j] = t;
158  state[heap[j]] = j;
159  state[heap[c]] = c;
160  j = c;
161  c = j / 2;
162  }
163 }
164 
165 
166 #ifdef __cplusplus
167 }
168 #endif
169 
170 
171 
172 #endif /* APPLICATIONS_STP_SRC_GRAPHHEAPS_H_ */
static int nearestX(int *RESTRICT heap, int *RESTRICT state, int *RESTRICT count, const SCIP_Real *pathdist)
Definition: graphheaps.h:41
static void correctX(int *RESTRICT heap, int *RESTRICT state, int *RESTRICT count, SCIP_Real *RESTRICT pathdist, int *RESTRICT pathedge, int l, int k, int e, SCIP_Real cost)
Definition: graphheaps.h:85
#define NULL
Definition: lpi_spx1.cpp:155
#define LT(a, b)
Definition: portab.h:81
#define GT(a, b)
Definition: portab.h:84
includes graph definitions used for Steiner tree problems
Portable definitions.
#define SCIP_Real
Definition: def.h:177
#define UNKNOWN
Definition: sepa_mcf.c:4095
static void resetX(SCIP_Real *RESTRICT pathdist, int *RESTRICT heap, int *RESTRICT state, int *RESTRICT count, int node, SCIP_Real distnew)
Definition: graphheaps.h:132
SCIP callable library.