Scippy

SCIP

Solving Constraint Integer Programs

grph.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 grph.h
17  * @brief includes various files containing graph methods used for Steiner tree problems
18  * @author Gerald Gamrath
19  * @author Thorsten Koch
20  * @author Daniel Rehfeldt
21  *
22  *
23  */
24 
25 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
26 
27 #ifndef _GRAPH_H_
28 #define _GRAPH_H_
29 
30 #define EAT_FREE -1
31 #define EAT_LAST -2
32 #define EAT_HIDE -3
33 
34 #define GRAPH_HAS_COORDINATES 1
35 #define GRAPH_IS_GRIDGRAPH 2
36 #define GRAPH_IS_DIRECTED 4
37 
38 #define STP_SPG 0
39 #define STP_SAP 1
40 #define STP_PCSPG 2
41 #define STP_RPCSPG 3
42 #define STP_NWSPG 4
43 #define STP_DCSTP 5
44 #define STP_REVENUES_BUDGET_HOPCONS 6
45 #define STP_RSMT 7
46 #define STP_OARSMT 8
47 #define STP_MWCSP 9
48 #define STP_DHCSTP 10
49 #define STP_GSTP 11
50 #define STP_RMWCSP 12
51 
52 typedef unsigned char STP_Bool;
53 
54 #include "scip/scip.h"
55 #include "misc_stp.h"
56 
57 typedef struct
58 {
59  /* Nodes */
60  int norgmodelknots; /**< Number of nodes in the original model */
61  int ksize; /**< Count of allocated knot slots */
62  int knots; /**< Count of nodes in graph */
63  int orgknots; /**< Count of nodes prior to graph reduction */
64  int terms; /**< Count of terminals */
65  int layers; /**< Count of different networks */
66  int orgsource; /**< root of unreduced graph */
67  int source; /**< The root */
68  int* RESTRICT term; /**< Array [0..nodes-1] of networknumber for */
69  /**< knot [i], -1 if [i] is never a terminal */
70  int* RESTRICT mark; /**< Array [0..nodes-1], normally TRUE or FALSE */
71  /**< to mark nodes for inclusion in the shortest */
72  /**< path / minimum spanning tree routine */
73  int* RESTRICT grad; /**< Array [0..nodes-1] with degree of knot [i] */
74  int* RESTRICT inpbeg; /**< Array [0..nodes-1] with starting slot index */
75  /**< for the ieat array, -1 if not used */
76  int* RESTRICT outbeg; /**< Array [0..nodes-1] with starting slot index */
77  /**< for the oeat array, -1 if not used */
78  int* RESTRICT maxdeg; /**< For HCDSTP: Array [0..nodes-1] containing the maximal degrees
79  of all nodes */
80  int* term2edge; /**< (R)PCSTP and (R)MWCSP: Array [0..nodes-1] of edge to twin terminal or -1 */
81 
82  SCIP_Real* prize; /**< For (R)PCSTP and (R)MWCSP: Array [0..nodes-1] of node costs */
83 
84  /* Edges */
85  IDX* fixedges; /**< list of fixed edges*/
86  IDX** ancestors; /**< list of ancestor edges to each edge (to keep track of reductions) */
87  IDX** pcancestors; /**< list of ancestor edges to each node (to keep track of PC/MW reductions ) */
88  int norgmodeledges; /**< Count of edges prior to graph transformation */
89  int hoplimit; /**< maximal number of edges allowed for a solution to be feasible
90  (only used for HCDSTPs) */
91  int esize; /**< Count of allocated edge slots */
92  int edges; /**< Count of edges in the graph */
93  int orgedges;
94  SCIP_Real* cost; /**< Array [0..edges-1] of positive edge costs */
95  int* RESTRICT tail; /**< Array [0..edges-1] of node-number of tail of edge [i] */
96  int* RESTRICT head; /**< Array [0..edges-1] of node-number of head of edge [i] */
97  int* RESTRICT orgtail; /**< Array [0..edges-1] of node-number of tail of edge [i] prior to reduction */
98  int* RESTRICT orghead; /**< Array [0..edges-1] of node-number of head of edge [i] prior to reduction */
99  int* RESTRICT rootedgeprevs; /**< Array [0..edges-1] for PC and MW problems */
100 
101  /* Nodes/Edges */
102  int* RESTRICT ieat; /**< Array [0..edges-1], incoming edge allocation table */
103  int* RESTRICT oeat; /**< Array [0..edges-1], outgoing edge allocation table */
104 
105  /* Data for min cut computation */
106  int* RESTRICT mincut_dist; /**< dist[i] : Distance-label of node i */
107  int* RESTRICT mincut_head; /**< head[i] : Head of active queue with label i */
108  int* RESTRICT mincut_head_inact; /**< head[i] : Head of inactive queue with label i */
109  int* RESTRICT mincut_numb; /**< numb[i] : numb[i] nodes with label i */
110  int* RESTRICT mincut_prev;
111  int* RESTRICT mincut_next;
112  int* RESTRICT mincut_temp;
113  int* RESTRICT mincut_e; /**< e[i] : Excess of node i */
114  int* RESTRICT mincut_x; /**< x[k] : Actual flow on arc k */
115  int* RESTRICT mincut_r; /**< r[k] : residual capacity of arc k */
116 
117  /* Data for sp and mst computation */
118  int* RESTRICT path_heap;
119  int* RESTRICT path_state;
120 
121  /* Data for grid problems */
122  int grid_dim;
123  int* grid_ncoords;
124  int** grid_coordinates;
125 
126  /* Global information */
127  int stp_type; /**< Steiner problem variant */
128  SCIP_Bool extended; /**< For (R)PCSTP and (R)MWCSP: signifies whether problem is in extended
129  form (TRUE) or not (FALSE) */
130 
131 } GRAPH;
132 
133 typedef struct presolve_info
134 {
135  SCIP_Real fixed;
136  SCIP_Real upper;
137  SCIP_Real lower;
138  int time;
139 } PRESOL;
140 
141 /* ONE segment of a path
142  */
143 typedef struct shortest_path
144 {
145  SCIP_Real dist; /* Distance to the end of the path */
146  signed int edge; /* Incoming edge to go along */
147 } PATH;
148 
149 /* ((((edge) % 2) == 0) ? ((edge) + 1) : ((edge) - 1)) without branch */
150 #define flipedge(edge) ( ((edge) + 1) - 2 * ((edge) % 2) )
151 #define flipedge_Uint(edge) ( (((unsigned int) edge) + 1) - 2 * (((unsigned int) edge) % 2) )
152 
153 #define PATH_NIL ((PATH*)0)
154 #define CONNECT 0
155 #define UNKNOWN (-1)
156 #define FARAWAY 1e15
157 #define BLOCKED 1e10
158 
159 #define EDGE_BLOCKED 0
160 #define EDGE_MODIFIABLE 1
161 
162 #define MST_MODE 0
163 #define FSP_MODE 1
164 #define BSP_MODE 2
165 
166 #define NO_CHANGE -10
167 
168 #define Is_term(a) ((a) >= 0)
169 #define Is_pterm(a) ((a) == -2)
170 #define Is_gterm(a) ((a) == -2 || (a) >= 0 )
171 #define Edge_anti(a) ((((a) % 2) > 0) ? (a) - 1 : (a) + 1)
172 
173 #define VERSION_SCIPJACK "1.3"
174 #define STP_MAGIC 0x33d32945
175 #define VERSION_MAJOR 1
176 #define VERSION_MINOR 0
177 
178 typedef enum { FF_BEA, FF_STP, FF_PRB, FF_GRD } FILETYPE;
179 
180 /* grphbase.c
181  */
182 extern void graph_pc_knot2nonTerm(GRAPH*, int);
183 extern void graph_pc_updateTerm2edge(GRAPH*, const GRAPH*, int, int, int, int);
184 extern void graph_pc_subtractPrize(SCIP*, GRAPH*, SCIP_Real, int);
185 extern void graph_pc_chgPrize(SCIP*, GRAPH*, SCIP_Real, int);
186 extern void graph_show(const GRAPH*);
187 extern void graph_knot_add(GRAPH*, int);
188 extern void graph_knot_chg(GRAPH*, int, int);
189 extern void graph_knot_del(SCIP*, GRAPH*, int, SCIP_Bool);
190 extern void graph_knot_contract_dir(GRAPH*, int, int);
191 extern void graph_get_csr(const GRAPH*, int* RESTRICT, int* RESTRICT, int* RESTRICT, int*);
192 extern void graph_edge_add(SCIP*, GRAPH*, int, int, double, double);
193 extern void graph_edge_del(SCIP*, GRAPH*, int, SCIP_Bool);
194 extern void graph_edge_hide(GRAPH*, int);
195 extern void graph_edge_printInfo(SCIP*, const GRAPH*, int);
196 extern void graph_uncover(GRAPH*);
197 extern void graph_trail(const GRAPH*, int);
198 extern void graph_free(SCIP*, GRAPH**, SCIP_Bool);
199 extern void graph_free_history(SCIP*, GRAPH*);
200 extern void graph_free_historyDeep(SCIP*, GRAPH*);
201 extern void graph_get_NVET(const GRAPH*, int*, int*, int*);
202 extern void graph_sol_setNodeList(const GRAPH*, STP_Bool*, IDX*);
203 extern void graph_pc_2org(GRAPH*);
204 extern void graph_pc_2trans(GRAPH*);
205 extern void graph_pc_2orgcheck(GRAPH*);
206 extern void graph_pc_2transcheck(GRAPH*);
207 extern void graph_pc_adaptSap(SCIP*, SCIP_Real, GRAPH*, SCIP_Real*);
208 extern void graph_pc_presolExit(SCIP*, GRAPH*);
209 extern SCIP_RETCODE graph_pc_init(SCIP*, GRAPH*, int, int);
210 extern SCIP_RETCODE graph_pc_2pc(SCIP*, GRAPH*);
211 extern SCIP_RETCODE graph_pc_2rpc(SCIP*, GRAPH*);
212 extern SCIP_RETCODE graph_pc_2mw(SCIP*, GRAPH*, SCIP_Real*);
213 extern SCIP_RETCODE graph_pc_2rmw(SCIP*, GRAPH*);
214 extern SCIP_RETCODE graph_pc_mw2rmw(SCIP*, GRAPH*, SCIP_Real);
215 extern SCIP_RETCODE graph_pc_getSap(SCIP*, GRAPH*, GRAPH**, SCIP_Real*);
216 extern SCIP_RETCODE graph_pc_getSapShift(SCIP*, GRAPH*, GRAPH**, SCIP_Real*);
217 extern SCIP_RETCODE graph_pc_getRsap(SCIP*, GRAPH*, GRAPH**, int*, int, int);
218 extern SCIP_RETCODE graph_pc_contractEdgeAncestors(SCIP*, GRAPH*, int, int, int);
219 extern SCIP_RETCODE graph_pc_contractEdge(SCIP*, GRAPH*, int*, int, int, int);
220 extern SCIP_RETCODE graph_resize(SCIP*, GRAPH*, int, int, int);
221 extern SCIP_RETCODE graph_knot_contract(SCIP*, GRAPH*, int*, int, int);
222 extern SCIP_RETCODE graph_knot_contractLowdeg2High(SCIP*, GRAPH*, int*, int, int);
223 extern SCIP_RETCODE graph_sol_reroot(SCIP*, GRAPH*, int*, int);
224 extern SCIP_RETCODE graph_sol_getOrg(SCIP*, const GRAPH*, const GRAPH*, const int*, int*);
225 extern SCIP_RETCODE graph_sol_markPcancestors(SCIP*, IDX**, const int*, const int*, int, STP_Bool*, STP_Bool*, int*, int*, int*);
226 extern SCIP_RETCODE graph_edge_reinsert(SCIP*, GRAPH*, int, int, int, SCIP_Real, IDX*, IDX*, IDX*, IDX*, SCIP_Bool);
227 extern SCIP_RETCODE graph_knot_delPseudo(SCIP*, GRAPH*, const SCIP_Real*, const SCIP_Real*, const SCIP_Real*, int, SCIP_Bool*);
228 extern SCIP_RETCODE graph_grid_create(SCIP*, GRAPH**, int**, int, int, int);
229 extern SCIP_RETCODE graph_obstgrid_create(SCIP*, GRAPH**, int**, int**, int, int, int, int);
230 extern SCIP_RETCODE graph_grid_coordinates(SCIP*, int**, int**, int*, int, int);
231 extern SCIP_RETCODE graph_copy_data(SCIP*, const GRAPH*, GRAPH*);
232 extern SCIP_RETCODE graph_copy(SCIP*, const GRAPH*, GRAPH**);
233 extern SCIP_RETCODE graph_pack(SCIP*, GRAPH*, GRAPH**, SCIP_Bool);
234 extern SCIP_RETCODE graph_trail_arr(SCIP*, const GRAPH*, int);
235 extern SCIP_RETCODE graph_get_edgeConflicts(SCIP*, const GRAPH*);
236 extern SCIP_RETCODE graph_init(SCIP*, GRAPH**, int, int, int);
237 extern SCIP_RETCODE graph_init_history(SCIP*, GRAPH*);
238 extern SCIP_RETCODE graph_termsReachable(SCIP*, const GRAPH*, SCIP_Bool*);
239 extern SCIP_RETCODE graph_pc_presolInit(SCIP*, GRAPH*);
240 extern int graph_edge_redirect(SCIP*, GRAPH*, int, int, int, SCIP_Real, SCIP_Bool);
241 extern int graph_pc_deleteTerm(SCIP*, GRAPH*, int);
242 extern SCIP_Bool graph_valid(const GRAPH*);
243 extern SCIP_Bool graph_pc_term2edgeConsistent(const GRAPH*);
244 extern SCIP_Bool graph_sol_unreduced(SCIP*, const GRAPH*, const int*);
245 extern SCIP_Bool graph_sol_valid(SCIP*, const GRAPH*, const int*);
246 extern SCIP_Bool graph_pc_isPcMw(const GRAPH*);
247 extern SCIP_Real graph_sol_getObj(const SCIP_Real*, const int*, SCIP_Real, int);
248 extern SCIP_Real graph_pc_getPosPrizeSum(SCIP*, const GRAPH*);
249 
250 /* grphpath.c
251  */
252 extern void graph_path_exit(SCIP*, GRAPH*);
253 extern void graph_path_exec(SCIP*, const GRAPH*, const int, int, const SCIP_Real*, PATH*);
254 extern void graph_path_execX(SCIP*, const GRAPH*, int, const SCIP_Real*, SCIP_Real*, int*);
255 extern void graph_path_invroot(SCIP*, const GRAPH*, int, const SCIP_Real*, SCIP_Real*, int*);
256 extern void graph_path_st(SCIP*, const GRAPH*, SCIP_Real*, SCIP_Real*, int*, int, SCIP_RANDNUMGEN*, STP_Bool*);
257 extern void graph_path_st_rmw(SCIP*, const GRAPH*, const SCIP_Real*, SCIP_Real*, int*, int, STP_Bool*);
258 extern void graph_path_st_pcmw(SCIP*, const GRAPH*, const SCIP_Real*, SCIP_Real*, int*, int, STP_Bool*);
259 extern void graph_path_st_pcmw_full(SCIP*, const GRAPH*, const SCIP_Real*, SCIP_Real*, int*, int, STP_Bool*);
260 extern void graph_path_st_pcmw_reduce(SCIP*, const GRAPH*, const SCIP_Real*, SCIP_Real*, int*, int, STP_Bool*);
261 extern void graph_path_st_pcmw_extend(SCIP*, const GRAPH*, const SCIP_Real*, PATH*, STP_Bool*, SCIP_Bool*);
262 extern void graph_path_st_rpc(SCIP*, const GRAPH*, const SCIP_Real*, SCIP_Real*, int*, int, STP_Bool*);
263 extern void graph_voronoi(SCIP* scip, const GRAPH*, SCIP_Real*, SCIP_Real*, STP_Bool*, int*, PATH*);
264 extern void graph_get2next(SCIP*, const GRAPH*, const SCIP_Real*, const SCIP_Real*, PATH*, int*, int*, int*);
265 extern void graph_get3next(SCIP*, const GRAPH*, const SCIP_Real*, const SCIP_Real*, PATH*, int*, int*, int*);
266 extern void graph_get4next(SCIP*, const GRAPH*, const SCIP_Real*, const SCIP_Real*, PATH*, int*, int*, int*);
267 extern void graph_get3nextTerms(SCIP*, const GRAPH*, SCIP_Real*, SCIP_Real*, PATH*, int*, int*, int*);
268 extern void graph_get4nextTerms(SCIP*, const GRAPH*, SCIP_Real*, SCIP_Real*, PATH*, int*, int*, int*);
269 extern void graph_voronoiMw(SCIP*, const GRAPH*, const SCIP_Real*, PATH*, int*, int*, int*);
270 extern void graph_voronoiTerms(SCIP*, const GRAPH*, const SCIP_Real*, PATH*, int*, int*, int*);
271 extern void voronoi_inout(const GRAPH*);
272 extern void voronoi_term(const GRAPH*, double*, double*, double*, PATH*, int*, int*, int*, int*, int);
273 extern void heap_add(int*, int*, int*, int, PATH*);
274 extern void graph_voronoiRepair(SCIP*, const GRAPH*, SCIP_Real*, int*, int*, PATH*, int*, int, UF*);
275 extern void graph_voronoiRepairMult(SCIP*, const GRAPH*, SCIP_Real*, int*, int*, int*, int*, STP_Bool*, UF*, PATH*);
276 extern void voronoiSteinerTreeExt(SCIP*, const GRAPH*, SCIP_Real*, int*, STP_Bool*, PATH*);
277 extern void graph_sdPaths(SCIP*, const GRAPH*, PATH*, SCIP_Real*, SCIP_Real, int*, int*, int*, int*, int, int, int);
278 extern void graph_path_PcMwSd(SCIP*, const GRAPH*, PATH*, SCIP_Real*, SCIP_Real, int*, int*, int*, int*, int*, int*, int, int, int);
279 extern void graph_voronoiWithRadiusMw(SCIP* scip, const GRAPH*, PATH*, const SCIP_Real*, SCIP_Real*, int*, int*, int*);
280 extern SCIP_RETCODE graph_voronoiExtend(SCIP*, const GRAPH*, SCIP_Real*, PATH*, SCIP_Real**, int**, int**, STP_Bool*, int*, int*, int*, int, int, int);
281 extern SCIP_RETCODE graph_path_init(SCIP*, GRAPH*);
282 extern SCIP_RETCODE graph_voronoiWithDist(SCIP*, const GRAPH*, SCIP_Real*, double*, int*, int*, int*, int*, int*, int*, PATH*);
283 extern SCIP_RETCODE graph_voronoiWithRadius(SCIP* scip, const GRAPH*, GRAPH*, PATH*, SCIP_Real*, SCIP_Real*, SCIP_Real*, int*, int*, int*);
284 extern SCIP_RETCODE graph_get4nextTTerms(SCIP*, const GRAPH*, SCIP_Real*, PATH*, int*, int*, int*);
285 
286 /* grphmcut.c
287  */
288 #if 0
289 extern void graph_mincut_exit(SCIP*, GRAPH*);
290 extern void graph_mincut_exec(GRAPH*, int, int, int, const int*, int*, const int*, const int*, const int*, int);
291 extern SCIP_RETCODE graph_mincut_init(SCIP*, GRAPH*);
292 #else
293 extern void graph_mincut_exit(SCIP*, GRAPH*);
294 extern void graph_mincut_exec(const GRAPH*, const int, const int, const int, const int, const int, const int*, const int*, int* RESTRICT, const int*, const int*, const int*, const SCIP_Bool);
295 extern SCIP_RETCODE graph_mincut_init(SCIP*, GRAPH*);
296 #endif
297 
298 /* grphload.c
299  */
300 extern SCIP_RETCODE graph_load(SCIP*, GRAPH**, const char*, PRESOL*);
301 
302 /* grphsave.c
303  */
304 extern void graph_save(const GRAPH*, const char*, FILETYPE);
305 extern void SCIPwriteStp(SCIP*, const GRAPH*, FILE*, SCIP_Real);
306 
307 /* reduce.c
308  */
309 extern SCIP_RETCODE level0(SCIP*, GRAPH*);
310 extern SCIP_RETCODE level0save(SCIP*, GRAPH*);
311 extern SCIP_RETCODE reduceStp(SCIP*, GRAPH**, SCIP_Real*, int, SCIP_Bool, SCIP_Bool, SCIP_Bool);
312 extern SCIP_RETCODE redLoopStp(SCIP*, GRAPH*, PATH*, PATH*, GNODE**, SCIP_Real*, SCIP_Real*, SCIP_Real*, int*, int*, int*, int*, int*, int*, int*, STP_Bool*, SCIP_Real*, SCIP_Real, SCIP_Bool, SCIP_Bool, SCIP_Bool, int, SCIP_Bool, SCIP_Bool);
313 extern SCIP_RETCODE redLoopPc(SCIP*, GRAPH*, PATH*, PATH*, GNODE**, SCIP_Real*, SCIP_Real*, SCIP_Real*, int*, int*, int*, int*, int*, int*, int*, STP_Bool*, SCIP_Real*, SCIP_Bool, SCIP_Bool, int, SCIP_Bool);
314 extern SCIP_RETCODE redLoopMw(SCIP*, GRAPH*, PATH*, PATH*, GNODE**, SCIP_Real*, SCIP_Real*, SCIP_Real*, int*, int*, int*, int*, int*, int*, int*, STP_Bool*, SCIP_Real*, STP_Bool, STP_Bool, STP_Bool, int, SCIP_Bool);
315 extern SCIP_RETCODE reduce(SCIP*, GRAPH**, SCIP_Real*, int, int, SCIP_Bool);
316 
317 /* reduce_alt.c
318  */
319 extern void reduce_ans(SCIP*, GRAPH*, int*, int*);
320 extern void reduce_ansAdv(SCIP*, GRAPH*, int*, int*, SCIP_Bool);
321 extern void reduce_ansAdv2(SCIP*, GRAPH*, int*, int*);
322 extern void reduce_nnp(SCIP*, GRAPH*, int*, int*);
323 extern SCIP_RETCODE reduce_sdsp(SCIP*, GRAPH*, PATH*, PATH*, int*, int*, int*, int*, int*, int*, int, int*);
324 extern SCIP_RETCODE reduce_sdspSap(SCIP*, GRAPH*, PATH*, PATH*, int*, int*, int*, int*, int*, int*, int);
325 extern SCIP_RETCODE reduce_sd(SCIP*, GRAPH*, PATH*, SCIP_Real*, SCIP_Real*, int*, int*, int*, int*, int*, int*, int*, SCIP_Bool, int*);
326 extern SCIP_RETCODE reduce_sdPc(SCIP*, GRAPH*, PATH*, int*, int*, int*, int*, int*, int*);
327 extern SCIP_RETCODE reduce_getSd(SCIP*, GRAPH*, PATH*, PATH*, SCIP_Real*, SCIP_Real, int*, int*, int*, int*, int*, int, int, int, SCIP_Bool, SCIP_Bool);
328 extern SCIP_RETCODE reduce_getSdPcMw(SCIP*, const GRAPH*, PATH*, PATH*, SCIP_Real*, SCIP_Real, int*, int*, int*, int*, int*, int*, int*, int, int, int);
329 extern SCIP_RETCODE reduce_nts(SCIP*, GRAPH*, PATH*, PATH*, int*, int*, int*, int*, int*, int*, int);
330 extern SCIP_RETCODE reduce_bd34(SCIP*, GRAPH*, PATH*, PATH*, int*, int*, int*, int*, int*, int*, int);
331 extern SCIP_RETCODE reduce_bdr(SCIP*, GRAPH*, GRAPH*, PATH*, PATH*, SCIP_Real*, SCIP_Real*, SCIP_Real*, int*, int*, int*, int*, int*);
332 extern SCIP_RETCODE reduce_nv(SCIP*, GRAPH*, PATH*, double*, int*, int*, int*, int*, int*, int*);
333 extern SCIP_RETCODE reduce_nvAdv(SCIP*, GRAPH*, PATH*, SCIP_Real*, double*, int*, int*, int*, int*, int*, int*, int*, int*);
334 extern SCIP_RETCODE reduce_sl(SCIP*, GRAPH*, PATH*, double*, int*, int*, int*, int*, STP_Bool*, int*, int*);
335 extern SCIP_RETCODE reduce_ledge(SCIP*, GRAPH*, PATH*, int*, int*, int*, int*, int*);
336 extern SCIP_RETCODE reduce_cnsAdv(SCIP*, GRAPH*, int*, int*);
337 extern SCIP_RETCODE reduce_npv(SCIP*, GRAPH*, PATH*, PATH*, int*, int*, int*, int*, int*, int*, int);
338 extern SCIP_RETCODE reduce_chain2(SCIP*, GRAPH*, PATH*, PATH*, int*, int*, int*, int*, int*, int*, int);
339 
340 /* reduce_bnd.c
341  */
342 extern SCIP_RETCODE reduce_deleteConflictEdges(SCIP*, GRAPH*);
343 extern SCIP_RETCODE reduce_check3Tree(SCIP*, const GRAPH*, int, const SCIP_Real*, const SCIP_Real*, const PATH*, const int*, SCIP_Real, const int*, int, int*, SCIP_Real*, SCIP_Bool*, unsigned int*, int*, SCIP_Bool*);
344 extern SCIP_RETCODE reduce_da(SCIP*, GRAPH*, PATH*, GNODE**, SCIP_Real*, SCIP_Real*, SCIP_Real*, SCIP_Real*, SCIP_Real*, int*, int*, int*, int*, int*, int*, STP_Bool*, int*, int, SCIP_RANDNUMGEN*, SCIP_Bool, SCIP_Bool);
345 extern SCIP_RETCODE reduce_daSlackPrune(SCIP*, SCIP_VAR**, GRAPH*, PATH*, GNODE**, SCIP_Real*, SCIP_Real*, SCIP_Real*, SCIP_Real*, int*, int*, int*, int*, int*, int*, STP_Bool*, STP_Bool*, int*, int, SCIP_Bool);
346 extern SCIP_RETCODE reduce_daSlackPruneMw(SCIP*, GRAPH*, PATH*, GNODE**, SCIP_Real*, SCIP_Real*, SCIP_Real*, int*, int*, int*, int*, int*, STP_Bool*, int*, int, SCIP_Bool);
347 extern SCIP_RETCODE reduce_daPcMw(SCIP*, GRAPH*, PATH*, GNODE**, SCIP_Real*, SCIP_Real*, SCIP_Real*, int*, int*, int*, int*, STP_Bool*, int*, SCIP_Bool, SCIP_Bool, SCIP_Bool, SCIP_Bool, SCIP_Bool, SCIP_RANDNUMGEN*, SCIP_Real);
348 extern SCIP_RETCODE reduce_bound(SCIP*, GRAPH*, PATH*, SCIP_Real*, SCIP_Real*, SCIP_Real*, SCIP_Real*, SCIP_Real*, SCIP_Real*, int*, int*, int*, int*);
349 extern SCIP_RETCODE reduce_boundMw(SCIP*, GRAPH*, PATH*, PATH*, SCIP_Real*, SCIP_Real*, SCIP_Real*, SCIP_Real*, int*, int*, int*, int*, int*);
350 extern SCIP_RETCODE reduce_boundPrune(SCIP*, GRAPH*, PATH*, SCIP_Real*, SCIP_Real*, SCIP_Real*, SCIP_Real*, int*, int*, int*, const int*, const int*, int*, int);
351 extern SCIP_RETCODE reduce_boundHop(SCIP*, GRAPH*, PATH*, SCIP_Real*, SCIP_Real*, SCIP_Real*, int*, int*, int*, int*);
352 extern SCIP_RETCODE reduce_boundHopR(SCIP*, GRAPH*, PATH*, SCIP_Real*, SCIP_Real*, SCIP_Real*, int*, int*, int*, int*, int*);
353 extern SCIP_RETCODE reduce_boundHopRc(SCIP*, GRAPH*, PATH*, SCIP_Real*, SCIP_Real*, SCIP_Real*, SCIP_Real, int*, int*, int*, int*, int*, SCIP_Bool);
354 extern int reduce_extendedEdge(SCIP*, GRAPH*, const PATH*, const SCIP_Real*, const SCIP_Real*, const int*, SCIP_Real, int, int*, STP_Bool*);
355 
356 /* reduce_simple.c
357  */
358 extern SCIP_RETCODE reduce_contractZeroEdges(SCIP*, GRAPH*, SCIP_Bool);
359 extern SCIP_RETCODE reduce_simple(SCIP*, GRAPH*, SCIP_Real*, int*, int*, int*);
360 extern SCIP_RETCODE reduce_simple_hc(SCIP*, GRAPH*, SCIP_Real*, int*);
361 extern SCIP_RETCODE reduce_simple_mw(SCIP*, GRAPH*, int*, SCIP_Real*, int*);
362 extern SCIP_RETCODE reduce_simple_pc(SCIP*, GRAPH*, SCIP_Real*, int*, int*, SCIP_Bool);
363 extern SCIP_RETCODE reduce_simple_sap(SCIP*, GRAPH*, SCIP_Real*, int*);
364 extern SCIP_RETCODE reduce_rpt(SCIP*, GRAPH*, SCIP_Real*, int*);
365 
366 /* validate.c
367  */
368 extern SCIP_RETCODE SCIPStpValidateSol(SCIP*, const GRAPH*, const double*, SCIP_Bool*);
369 
370 #endif /* !_GRAPH_H_ */
graph_path_init
SCIP_RETCODE graph_path_init(SCIP *, GRAPH *)
Definition: grphpath.c:444
presolve_info
Definition: grph.h:133
level0save
SCIP_RETCODE level0save(SCIP *, GRAPH *)
Definition: reduce.c:185
Int_List_Node
Definition: misc_stp.h:73
SCIPwriteStp
void SCIPwriteStp(SCIP *, const GRAPH *, FILE *, SCIP_Real)
Definition: grphsave.c:38
graph_pc_subtractPrize
void graph_pc_subtractPrize(SCIP *, GRAPH *, SCIP_Real, int)
Definition: grphbase.c:1992
reduce_nnp
void reduce_nnp(SCIP *, GRAPH *, int *, int *)
Definition: reduce_alt.c:5450
graph_get_NVET
void graph_get_NVET(const GRAPH *, int *, int *, int *)
Definition: grphbase.c:3386
GRAPH::mincut_e
int *RESTRICT mincut_e
Definition: grph.h:113
graph_voronoi
void graph_voronoi(SCIP *scip, const GRAPH *, SCIP_Real *, SCIP_Real *, STP_Bool *, int *, PATH *)
Definition: grphpath.c:1751
PRESOL
struct presolve_info PRESOL
graph_pc_2mw
SCIP_RETCODE graph_pc_2mw(SCIP *, GRAPH *, SCIP_Real *)
Definition: grphbase.c:1682
graph_path_st_rpc
void graph_path_st_rpc(SCIP *, const GRAPH *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *)
Definition: grphpath.c:1033
graph_pc_init
SCIP_RETCODE graph_pc_init(SCIP *, GRAPH *, int, int)
Definition: grphbase.c:766
graph_sol_unreduced
SCIP_Bool graph_sol_unreduced(SCIP *, const GRAPH *, const int *)
Definition: grphbase.c:3050
graph_get4next
void graph_get4next(SCIP *, const GRAPH *, const SCIP_Real *, const SCIP_Real *, PATH *, int *, int *, int *)
Definition: grphpath.c:2041
graph_pc_getSapShift
SCIP_RETCODE graph_pc_getSapShift(SCIP *, GRAPH *, GRAPH **, SCIP_Real *)
Definition: grphbase.c:1204
graph_path_st
void graph_path_st(SCIP *, const GRAPH *, SCIP_Real *, SCIP_Real *, int *, int, SCIP_RANDNUMGEN *, STP_Bool *)
Definition: grphpath.c:926
GRAPH::head
int *RESTRICT head
Definition: grph.h:96
GRAPH::mincut_x
int *RESTRICT mincut_x
Definition: grph.h:114
GRAPH::orgtail
int *RESTRICT orgtail
Definition: grph.h:97
GRAPH
Definition: grph.h:57
FF_STP
Definition: grph.h:178
GRAPH::source
int source
Definition: grph.h:67
graph_voronoiWithDist
SCIP_RETCODE graph_voronoiWithDist(SCIP *, const GRAPH *, SCIP_Real *, double *, int *, int *, int *, int *, int *, int *, PATH *)
graph_pc_getRsap
SCIP_RETCODE graph_pc_getRsap(SCIP *, GRAPH *, GRAPH **, int *, int, int)
Definition: grphbase.c:1365
graph_edge_hide
void graph_edge_hide(GRAPH *, int)
Definition: grphbase.c:2891
shortest_path::edge
signed int edge
Definition: grph.h:146
reduce_boundPrune
SCIP_RETCODE reduce_boundPrune(SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, const int *, const int *, int *, int)
Definition: reduce_bnd.c:5415
graph_trail_arr
SCIP_RETCODE graph_trail_arr(SCIP *, const GRAPH *, int)
Definition: grphbase.c:4242
reduce_ans
void reduce_ans(SCIP *, GRAPH *, int *, int *)
Definition: reduce_alt.c:4447
FF_BEA
Definition: grph.h:178
graph_valid
SCIP_Bool graph_valid(const GRAPH *)
Definition: grphbase.c:4328
GRAPH::terms
int terms
Definition: grph.h:64
presolve_info::upper
SCIP_Real upper
Definition: grph.h:136
reduce_rpt
SCIP_RETCODE reduce_rpt(SCIP *, GRAPH *, SCIP_Real *, int *)
Definition: reduce_simple.c:884
graph_knot_del
void graph_knot_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: grphbase.c:2246
graph_pc_deleteTerm
int graph_pc_deleteTerm(SCIP *, GRAPH *, int)
Definition: grphbase.c:1945
graph_copy
SCIP_RETCODE graph_copy(SCIP *, const GRAPH *, GRAPH **)
Definition: grphbase.c:3900
graph_init_history
SCIP_RETCODE graph_init_history(SCIP *, GRAPH *)
Definition: grphbase.c:3573
graph_obstgrid_create
SCIP_RETCODE graph_obstgrid_create(SCIP *, GRAPH **, int **, int **, int, int, int, int)
Definition: grphbase.c:419
GRAPH::norgmodeledges
int norgmodeledges
Definition: grph.h:88
SCIP_Var
Definition: struct_var.h:198
UnionFind_Structure
Definition: misc_stp.h:65
GRAPH::maxdeg
int *RESTRICT maxdeg
Definition: grph.h:78
reduce_boundMw
SCIP_RETCODE reduce_boundMw(SCIP *, GRAPH *, PATH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *)
Definition: reduce_bnd.c:5243
graph_path_st_rmw
void graph_path_st_rmw(SCIP *, const GRAPH *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *)
Definition: grphpath.c:1536
reduce_daSlackPrune
SCIP_RETCODE reduce_daSlackPrune(SCIP *, SCIP_VAR **, GRAPH *, PATH *, GNODE **, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *, int *, STP_Bool *, STP_Bool *, int *, int, SCIP_Bool)
Definition: reduce_bnd.c:3279
FILETYPE
FILETYPE
Definition: grph.h:178
GRAPH::mincut_temp
int *RESTRICT mincut_temp
Definition: grph.h:112
graph_pc_presolInit
SCIP_RETCODE graph_pc_presolInit(SCIP *, GRAPH *)
Definition: grphbase.c:794
graph_mincut_exec
void graph_mincut_exec(const GRAPH *, const int, const int, const int, const int, const int, const int *, const int *, int *RESTRICT, const int *, const int *, const int *, const SCIP_Bool)
FF_GRD
Definition: grph.h:178
graph_mincut_init
SCIP_RETCODE graph_mincut_init(SCIP *, GRAPH *)
Definition: grphmcut.c:275
PATH
struct shortest_path PATH
reduce_nv
SCIP_RETCODE reduce_nv(SCIP *, GRAPH *, PATH *, double *, int *, int *, int *, int *, int *, int *)
Definition: reduce_alt.c:3710
reduce_contractZeroEdges
SCIP_RETCODE reduce_contractZeroEdges(SCIP *, GRAPH *, SCIP_Bool)
Definition: reduce_simple.c:453
GRAPH::inpbeg
int *RESTRICT inpbeg
Definition: grph.h:74
graph_pc_mw2rmw
SCIP_RETCODE graph_pc_mw2rmw(SCIP *, GRAPH *, SCIP_Real)
Definition: grphbase.c:1850
GRAPH::path_state
int *RESTRICT path_state
Definition: grph.h:119
graph_free
void graph_free(SCIP *, GRAPH **, SCIP_Bool)
Definition: grphbase.c:3678
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
reduce_boundHopRc
SCIP_RETCODE reduce_boundHopRc(SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real, int *, int *, int *, int *, int *, SCIP_Bool)
Definition: reduce_bnd.c:6226
graph_path_exit
void graph_path_exit(SCIP *, GRAPH *)
Definition: grphpath.c:466
SCIP_RandNumGen
Definition: struct_misc.h:259
shortest_path
Definition: grph.h:143
graph_knot_delPseudo
SCIP_RETCODE graph_knot_delPseudo(SCIP *, GRAPH *, const SCIP_Real *, const SCIP_Real *, const SCIP_Real *, int, SCIP_Bool *)
Definition: grphbase.c:2262
presolve_info::lower
SCIP_Real lower
Definition: grph.h:137
graph_pc_contractEdgeAncestors
SCIP_RETCODE graph_pc_contractEdgeAncestors(SCIP *, GRAPH *, int, int, int)
Definition: grphbase.c:2079
graph_voronoiRepair
void graph_voronoiRepair(SCIP *, const GRAPH *, SCIP_Real *, int *, int *, PATH *, int *, int, UF *)
Definition: grphpath.c:2979
graph_resize
SCIP_RETCODE graph_resize(SCIP *, GRAPH *, int, int, int)
Definition: grphbase.c:3635
redLoopPc
SCIP_RETCODE redLoopPc(SCIP *, GRAPH *, PATH *, PATH *, GNODE **, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *, int *, int *, STP_Bool *, SCIP_Real *, SCIP_Bool, SCIP_Bool, int, SCIP_Bool)
Definition: reduce.c:1160
reduce_extendedEdge
int reduce_extendedEdge(SCIP *, GRAPH *, const PATH *, const SCIP_Real *, const SCIP_Real *, const int *, SCIP_Real, int, int *, STP_Bool *)
Definition: reduce_bnd.c:2774
GRAPH::orghead
int *RESTRICT orghead
Definition: grph.h:98
reduce_daPcMw
SCIP_RETCODE reduce_daPcMw(SCIP *, GRAPH *, PATH *, GNODE **, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, STP_Bool *, int *, SCIP_Bool, SCIP_Bool, SCIP_Bool, SCIP_Bool, SCIP_Bool, SCIP_RANDNUMGEN *, SCIP_Real)
Definition: reduce_bnd.c:3801
reduce_simple
SCIP_RETCODE reduce_simple(SCIP *, GRAPH *, SCIP_Real *, int *, int *, int *)
Definition: reduce_simple.c:489
graph_knot_chg
void graph_knot_chg(GRAPH *, int, int)
Definition: grphbase.c:2222
graph_pc_updateTerm2edge
void graph_pc_updateTerm2edge(GRAPH *, const GRAPH *, int, int, int, int)
Definition: grphbase.c:928
graph_pc_2rmw
SCIP_RETCODE graph_pc_2rmw(SCIP *, GRAPH *)
Definition: grphbase.c:1741
GRAPH::mark
int *RESTRICT mark
Definition: grph.h:70
graph_pc_term2edgeConsistent
SCIP_Bool graph_pc_term2edgeConsistent(const GRAPH *)
Definition: grphbase.c:853
GRAPH::fixedges
IDX * fixedges
Definition: grph.h:85
graph_pc_contractEdge
SCIP_RETCODE graph_pc_contractEdge(SCIP *, GRAPH *, int *, int, int, int)
Definition: grphbase.c:2105
graph_voronoiRepairMult
void graph_voronoiRepairMult(SCIP *, const GRAPH *, SCIP_Real *, int *, int *, int *, int *, STP_Bool *, UF *, PATH *)
Definition: grphpath.c:3057
redLoopStp
SCIP_RETCODE redLoopStp(SCIP *, GRAPH *, PATH *, PATH *, GNODE **, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *, int *, int *, STP_Bool *, SCIP_Real *, SCIP_Real, SCIP_Bool, SCIP_Bool, SCIP_Bool, int, SCIP_Bool, SCIP_Bool)
Definition: reduce.c:1411
graph_sdPaths
void graph_sdPaths(SCIP *, const GRAPH *, PATH *, SCIP_Real *, SCIP_Real, int *, int *, int *, int *, int, int, int)
Definition: grphpath.c:567
graph_pack
SCIP_RETCODE graph_pack(SCIP *, GRAPH *, GRAPH **, SCIP_Bool)
Definition: grphbase.c:3988
graph_path_execX
void graph_path_execX(SCIP *, const GRAPH *, int, const SCIP_Real *, SCIP_Real *, int *)
Definition: grphpath.c:781
reduce_cnsAdv
SCIP_RETCODE reduce_cnsAdv(SCIP *, GRAPH *, int *, int *)
Definition: reduce_alt.c:4748
graph_path_st_pcmw
void graph_path_st_pcmw(SCIP *, const GRAPH *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *)
Definition: grphpath.c:1154
reduce_boundHopR
SCIP_RETCODE reduce_boundHopR(SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *)
Definition: reduce_bnd.c:6098
GRAPH::oeat
int *RESTRICT oeat
Definition: grph.h:103
graph_pc_2org
void graph_pc_2org(GRAPH *)
Definition: grphbase.c:964
GRAPH::mincut_dist
int *RESTRICT mincut_dist
Definition: grph.h:106
reduce_simple_mw
SCIP_RETCODE reduce_simple_mw(SCIP *, GRAPH *, int *, SCIP_Real *, int *)
Definition: reduce_simple.c:953
graph_knot_contract_dir
void graph_knot_contract_dir(GRAPH *, int, int)
graph_termsReachable
SCIP_RETCODE graph_termsReachable(SCIP *, const GRAPH *, SCIP_Bool *)
Definition: grphbase.c:4299
misc_stp.h
miscellaneous methods used for solving Steiner problems
graph_knot_contractLowdeg2High
SCIP_RETCODE graph_knot_contractLowdeg2High(SCIP *, GRAPH *, int *, int, int)
Definition: grphbase.c:2666
GRAPH::extended
SCIP_Bool extended
Definition: grph.h:128
GRAPH::stp_type
int stp_type
Definition: grph.h:127
graph_path_st_pcmw_extend
void graph_path_st_pcmw_extend(SCIP *, const GRAPH *, const SCIP_Real *, PATH *, STP_Bool *, SCIP_Bool *)
Definition: grphpath.c:1410
reduce_bdr
SCIP_RETCODE reduce_bdr(SCIP *, GRAPH *, GRAPH *, PATH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *)
Definition: reduce_alt.c:2747
GRAPH::ancestors
IDX ** ancestors
Definition: grph.h:86
level0
SCIP_RETCODE level0(SCIP *, GRAPH *)
Definition: reduce.c:153
GRAPH::orgedges
int orgedges
Definition: grph.h:93
reduce_deleteConflictEdges
SCIP_RETCODE reduce_deleteConflictEdges(SCIP *, GRAPH *)
Definition: reduce_bnd.c:2421
heap_add
void heap_add(int *, int *, int *, int, PATH *)
Definition: grphpath.c:244
reduce_sd
SCIP_RETCODE reduce_sd(SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *, int *, int *, SCIP_Bool, int *)
Definition: reduce_alt.c:1105
reduce_da
SCIP_RETCODE reduce_da(SCIP *, GRAPH *, PATH *, GNODE **, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *, int *, STP_Bool *, int *, int, SCIP_RANDNUMGEN *, SCIP_Bool, SCIP_Bool)
Definition: reduce_bnd.c:2861
graph_pc_2trans
void graph_pc_2trans(GRAPH *)
Definition: grphbase.c:1002
STP_Bool
unsigned char STP_Bool
Definition: grph.h:52
graph_sol_reroot
SCIP_RETCODE graph_sol_reroot(SCIP *, GRAPH *, int *, int)
Definition: grphbase.c:2947
graph_pc_2rpc
SCIP_RETCODE graph_pc_2rpc(SCIP *, GRAPH *)
Definition: grphbase.c:1601
reduce_check3Tree
SCIP_RETCODE reduce_check3Tree(SCIP *, const GRAPH *, int, const SCIP_Real *, const SCIP_Real *, const PATH *, const int *, SCIP_Real, const int *, int, int *, SCIP_Real *, SCIP_Bool *, unsigned int *, int *, SCIP_Bool *)
Definition: reduce_bnd.c:2464
GRAPH::prize
SCIP_Real * prize
Definition: grph.h:82
reduce_simple_sap
SCIP_RETCODE reduce_simple_sap(SCIP *, GRAPH *, SCIP_Real *, int *)
Definition: reduce_simple.c:684
shortest_path::dist
SCIP_Real dist
Definition: grph.h:145
GRAPH::grad
int *RESTRICT grad
Definition: grph.h:73
graph_pc_presolExit
void graph_pc_presolExit(SCIP *, GRAPH *)
Definition: grphbase.c:837
GRAPH::mincut_head_inact
int *RESTRICT mincut_head_inact
Definition: grph.h:108
graph_sol_valid
SCIP_Bool graph_sol_valid(SCIP *, const GRAPH *, const int *)
Definition: grphbase.c:3070
graph_grid_coordinates
SCIP_RETCODE graph_grid_coordinates(SCIP *, int **, int **, int *, int, int)
Definition: grphbase.c:730
reduce_getSd
SCIP_RETCODE reduce_getSd(SCIP *, GRAPH *, PATH *, PATH *, SCIP_Real *, SCIP_Real, int *, int *, int *, int *, int *, int, int, int, SCIP_Bool, SCIP_Bool)
Definition: reduce_alt.c:1970
graph_path_exec
void graph_path_exec(SCIP *, const GRAPH *, const int, int, const SCIP_Real *, PATH *)
Definition: grphpath.c:491
graph_path_st_pcmw_full
void graph_path_st_pcmw_full(SCIP *, const GRAPH *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *)
Definition: grphpath.c:1316
GRAPH::knots
int knots
Definition: grph.h:62
reduce_bd34
SCIP_RETCODE reduce_bd34(SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
Definition: reduce_alt.c:2964
reduce_nvAdv
SCIP_RETCODE reduce_nvAdv(SCIP *, GRAPH *, PATH *, SCIP_Real *, double *, int *, int *, int *, int *, int *, int *, int *, int *)
Definition: reduce_alt.c:3903
voronoiSteinerTreeExt
void voronoiSteinerTreeExt(SCIP *, const GRAPH *, SCIP_Real *, int *, STP_Bool *, PATH *)
GRAPH::term2edge
int * term2edge
Definition: grph.h:80
GRAPH::pcancestors
IDX ** pcancestors
Definition: grph.h:87
graph_copy_data
SCIP_RETCODE graph_copy_data(SCIP *, const GRAPH *, GRAPH *)
Definition: grphbase.c:3809
graph_get2next
void graph_get2next(SCIP *, const GRAPH *, const SCIP_Real *, const SCIP_Real *, PATH *, int *, int *, int *)
Definition: grphpath.c:1838
graph_free_history
void graph_free_history(SCIP *, GRAPH *)
Definition: grphbase.c:3740
graph_path_PcMwSd
void graph_path_PcMwSd(SCIP *, const GRAPH *, PATH *, SCIP_Real *, SCIP_Real, int *, int *, int *, int *, int *, int *, int, int, int)
Definition: grphpath.c:664
GRAPH::orgknots
int orgknots
Definition: grph.h:63
graph_pc_getPosPrizeSum
SCIP_Real graph_pc_getPosPrizeSum(SCIP *, const GRAPH *)
Definition: grphbase.c:1054
graph_get_edgeConflicts
SCIP_RETCODE graph_get_edgeConflicts(SCIP *, const GRAPH *)
Definition: grphbase.c:3452
reduce_simple_hc
SCIP_RETCODE reduce_simple_hc(SCIP *, GRAPH *, SCIP_Real *, int *)
Definition: reduce_simple.c:1252
graph_path_st_pcmw_reduce
void graph_path_st_pcmw_reduce(SCIP *, const GRAPH *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *)
Definition: grphpath.c:1264
GRAPH::mincut_head
int *RESTRICT mincut_head
Definition: grph.h:107
graph_voronoiWithRadiusMw
void graph_voronoiWithRadiusMw(SCIP *scip, const GRAPH *, PATH *, const SCIP_Real *, SCIP_Real *, int *, int *, int *)
Definition: grphpath.c:2852
voronoi_term
void voronoi_term(const GRAPH *, double *, double *, double *, PATH *, int *, int *, int *, int *, int)
reduce_ansAdv2
void reduce_ansAdv2(SCIP *, GRAPH *, int *, int *)
Definition: reduce_alt.c:4621
reduce_ansAdv
void reduce_ansAdv(SCIP *, GRAPH *, int *, int *, SCIP_Bool)
Definition: reduce_alt.c:4515
reduce_simple_pc
SCIP_RETCODE reduce_simple_pc(SCIP *, GRAPH *, SCIP_Real *, int *, int *, SCIP_Bool)
Definition: reduce_simple.c:1330
SCIP_Bool
#define SCIP_Bool
Definition: def.h:70
GRAPH::ieat
int *RESTRICT ieat
Definition: grph.h:102
GRAPH::path_heap
int *RESTRICT path_heap
Definition: grph.h:118
graph_sol_getOrg
SCIP_RETCODE graph_sol_getOrg(SCIP *, const GRAPH *, const GRAPH *, const int *, int *)
Definition: grphbase.c:3218
reduce_boundHop
SCIP_RETCODE reduce_boundHop(SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *)
Definition: reduce_bnd.c:5904
graph_save
void graph_save(const GRAPH *, const char *, FILETYPE)
Definition: grphsave.c:309
GRAPH::tail
int *RESTRICT tail
Definition: grph.h:95
presolve_info::time
int time
Definition: grph.h:138
graph_show
void graph_show(const GRAPH *)
Definition: grphbase.c:3916
graph_uncover
void graph_uncover(GRAPH *)
Definition: grphbase.c:3941
graph_pc_chgPrize
void graph_pc_chgPrize(SCIP *, GRAPH *, SCIP_Real, int)
Definition: grphbase.c:2035
graph_voronoiMw
void graph_voronoiMw(SCIP *, const GRAPH *, const SCIP_Real *, PATH *, int *, int *, int *)
Definition: grphpath.c:2383
graph_mincut_exit
void graph_mincut_exit(SCIP *, GRAPH *)
Definition: grphmcut.c:305
graph_pc_isPcMw
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
Definition: grphbase.c:2188
reduce_sl
SCIP_RETCODE reduce_sl(SCIP *, GRAPH *, PATH *, double *, int *, int *, int *, int *, STP_Bool *, int *, int *)
Definition: reduce_alt.c:3483
graph_sol_markPcancestors
SCIP_RETCODE graph_sol_markPcancestors(SCIP *, IDX **, const int *, const int *, int, STP_Bool *, STP_Bool *, int *, int *, int *)
Definition: grphbase.c:3292
reduce_nts
SCIP_RETCODE reduce_nts(SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
Definition: reduce_alt.c:3217
SCIPStpValidateSol
SCIP_RETCODE SCIPStpValidateSol(SCIP *, const GRAPH *, const double *, SCIP_Bool *)
Definition: validate.c:136
GRAPH::term
int *RESTRICT term
Definition: grph.h:68
graph_edge_del
void graph_edge_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: grphbase.c:2841
graph_sol_getObj
SCIP_Real graph_sol_getObj(const SCIP_Real *, const int *, SCIP_Real, int)
Definition: grphbase.c:3200
reduce_ledge
SCIP_RETCODE reduce_ledge(SCIP *, GRAPH *, PATH *, int *, int *, int *, int *, int *)
Definition: reduce_alt.c:4143
reduce_sdPc
SCIP_RETCODE reduce_sdPc(SCIP *, GRAPH *, PATH *, int *, int *, int *, int *, int *, int *)
Definition: reduce_alt.c:1499
GRAPH::mincut_prev
int *RESTRICT mincut_prev
Definition: grph.h:110
GRAPH::grid_dim
int grid_dim
Definition: grph.h:122
GRAPH::grid_coordinates
int ** grid_coordinates
Definition: grph.h:124
graph_voronoiExtend
SCIP_RETCODE graph_voronoiExtend(SCIP *, const GRAPH *, SCIP_Real *, PATH *, SCIP_Real **, int **, int **, STP_Bool *, int *, int *, int *, int, int, int)
Definition: grphpath.c:1671
GRAPH::mincut_numb
int *RESTRICT mincut_numb
Definition: grph.h:109
GRAPH::layers
int layers
Definition: grph.h:65
reduce_bound
SCIP_RETCODE reduce_bound(SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *)
Definition: reduce_bnd.c:4653
reduce_getSdPcMw
SCIP_RETCODE reduce_getSdPcMw(SCIP *, const GRAPH *, PATH *, PATH *, SCIP_Real *, SCIP_Real, int *, int *, int *, int *, int *, int *, int *, int, int, int)
Definition: reduce_alt.c:2110
graph_path_invroot
void graph_path_invroot(SCIP *, const GRAPH *, int, const SCIP_Real *, SCIP_Real *, int *)
Definition: grphpath.c:849
graph_get4nextTerms
void graph_get4nextTerms(SCIP *, const GRAPH *, SCIP_Real *, SCIP_Real *, PATH *, int *, int *, int *)
Definition: grphpath.c:2186
graph_get_csr
void graph_get_csr(const GRAPH *, int *RESTRICT, int *RESTRICT, int *RESTRICT, int *)
GRAPH
struct Graph GRAPH
reduceStp
SCIP_RETCODE reduceStp(SCIP *, GRAPH **, SCIP_Real *, int, SCIP_Bool, SCIP_Bool, SCIP_Bool)
Definition: reduce.c:223
GRAPH::cost
SCIP_Real * cost
Definition: grph.h:94
Graph_Node
Definition: misc_stp.h:41
reduce_sdspSap
SCIP_RETCODE reduce_sdspSap(SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
Definition: reduce_alt.c:2308
graph_edge_printInfo
void graph_edge_printInfo(SCIP *, const GRAPH *, int)
Definition: grphbase.c:2935
GRAPH::rootedgeprevs
int *RESTRICT rootedgeprevs
Definition: grph.h:99
graph_load
SCIP_RETCODE graph_load(SCIP *, GRAPH **, const char *, PRESOL *)
Definition: grphload.c:821
SCIP_Real
#define SCIP_Real
Definition: def.h:163
GRAPH::esize
int esize
Definition: grph.h:91
GRAPH::outbeg
int *RESTRICT outbeg
Definition: grph.h:76
graph_pc_2orgcheck
void graph_pc_2orgcheck(GRAPH *)
Definition: grphbase.c:1028
graph_get3next
void graph_get3next(SCIP *, const GRAPH *, const SCIP_Real *, const SCIP_Real *, PATH *, int *, int *, int *)
Definition: grphpath.c:1934
GRAPH::edges
int edges
Definition: grph.h:92
graph_pc_getSap
SCIP_RETCODE graph_pc_getSap(SCIP *, GRAPH *, GRAPH **, SCIP_Real *)
Definition: grphbase.c:1075
GRAPH::grid_ncoords
int * grid_ncoords
Definition: grph.h:123
graph_knot_add
void graph_knot_add(GRAPH *, int)
Definition: grphbase.c:2200
voronoi_inout
void voronoi_inout(const GRAPH *)
graph_get4nextTTerms
SCIP_RETCODE graph_get4nextTTerms(SCIP *, const GRAPH *, SCIP_Real *, PATH *, int *, int *, int *)
Definition: grphpath.c:2227
graph_knot_contract
SCIP_RETCODE graph_knot_contract(SCIP *, GRAPH *, int *, int, int)
Definition: grphbase.c:2433
reduce
SCIP_RETCODE reduce(SCIP *, GRAPH **, SCIP_Real *, int, int, SCIP_Bool)
Definition: reduce.c:1675
presolve_info::fixed
SCIP_Real fixed
Definition: grph.h:135
GRAPH::ksize
int ksize
Definition: grph.h:61
GRAPH::mincut_r
int *RESTRICT mincut_r
Definition: grph.h:115
reduce_daSlackPruneMw
SCIP_RETCODE reduce_daSlackPruneMw(SCIP *, GRAPH *, PATH *, GNODE **, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *, STP_Bool *, int *, int, SCIP_Bool)
Definition: reduce_bnd.c:4237
graph_pc_2pc
SCIP_RETCODE graph_pc_2pc(SCIP *, GRAPH *)
Definition: grphbase.c:1520
FF_PRB
Definition: grph.h:178
graph_pc_knot2nonTerm
void graph_pc_knot2nonTerm(GRAPH *, int)
Definition: grphbase.c:909
graph_pc_adaptSap
void graph_pc_adaptSap(SCIP *, SCIP_Real, GRAPH *, SCIP_Real *)
Definition: grphbase.c:1174
reduce_npv
SCIP_RETCODE reduce_npv(SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
Definition: reduce_alt.c:5024
GRAPH::hoplimit
int hoplimit
Definition: grph.h:89
graph_edge_redirect
int graph_edge_redirect(SCIP *, GRAPH *, int, int, int, SCIP_Real, SCIP_Bool)
Definition: grphbase.c:2685
graph_edge_add
void graph_edge_add(SCIP *, GRAPH *, int, int, double, double)
graph_get3nextTerms
void graph_get3nextTerms(SCIP *, const GRAPH *, SCIP_Real *, SCIP_Real *, PATH *, int *, int *, int *)
Definition: grphpath.c:2150
graph_edge_reinsert
SCIP_RETCODE graph_edge_reinsert(SCIP *, GRAPH *, int, int, int, SCIP_Real, IDX *, IDX *, IDX *, IDX *, SCIP_Bool)
Definition: grphbase.c:2757
graph_grid_create
SCIP_RETCODE graph_grid_create(SCIP *, GRAPH **, int **, int, int, int)
Definition: grphbase.c:582
graph_free_historyDeep
void graph_free_historyDeep(SCIP *, GRAPH *)
Definition: grphbase.c:3764
graph_trail
void graph_trail(const GRAPH *, int)
Definition: grphbase.c:4188
graph_voronoiTerms
void graph_voronoiTerms(SCIP *, const GRAPH *, const SCIP_Real *, PATH *, int *, int *, int *)
Definition: grphpath.c:2307
graph_voronoiWithRadius
SCIP_RETCODE graph_voronoiWithRadius(SCIP *scip, const GRAPH *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *)
Definition: grphpath.c:2614
reduce_sdsp
SCIP_RETCODE reduce_sdsp(SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int, int *)
Definition: reduce_alt.c:2459
scip.h
SCIP callable library.
GRAPH::mincut_next
int *RESTRICT mincut_next
Definition: grph.h:111
graph_init
SCIP_RETCODE graph_init(SCIP *, GRAPH **, int, int, int)
Definition: grphbase.c:3495
graph_sol_setNodeList
void graph_sol_setNodeList(const GRAPH *, STP_Bool *, IDX *)
Definition: grphbase.c:3174
graph_pc_2transcheck
void graph_pc_2transcheck(GRAPH *)
Definition: grphbase.c:1041
GRAPH::norgmodelknots
int norgmodelknots
Definition: grph.h:60
GRAPH::orgsource
int orgsource
Definition: grph.h:66
reduce_chain2
SCIP_RETCODE reduce_chain2(SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
Definition: reduce_alt.c:5367
redLoopMw
SCIP_RETCODE redLoopMw(SCIP *, GRAPH *, PATH *, PATH *, GNODE **, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *, int *, int *, STP_Bool *, SCIP_Real *, STP_Bool, STP_Bool, STP_Bool, int, SCIP_Bool)
Definition: reduce.c:923