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-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 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;
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 {
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);
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**);
234 extern SCIP_RETCODE graph_trail_arr(SCIP*, const GRAPH*, int);
236 extern SCIP_RETCODE graph_init(SCIP*, GRAPH**, int, int, int);
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*);
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);
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);
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);
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);
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*);
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  */
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);
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  */
359 extern SCIP_RETCODE reduce_simple(SCIP*, GRAPH*, SCIP_Real*, int*, int*, 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);
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_ */
SCIP_RETCODE graph_path_init(SCIP *, GRAPH *)
Definition: grphpath.c:444
SCIP_RETCODE level0save(SCIP *, GRAPH *)
Definition: reduce.c:185
void SCIPwriteStp(SCIP *, const GRAPH *, FILE *, SCIP_Real)
Definition: grphsave.c:38
void graph_pc_subtractPrize(SCIP *, GRAPH *, SCIP_Real, int)
Definition: grphbase.c:1992
void reduce_nnp(SCIP *, GRAPH *, int *, int *)
Definition: reduce_alt.c:5450
void graph_get_NVET(const GRAPH *, int *, int *, int *)
Definition: grphbase.c:3386
int *RESTRICT mincut_e
Definition: grph.h:113
void graph_voronoi(SCIP *scip, const GRAPH *, SCIP_Real *, SCIP_Real *, STP_Bool *, int *, PATH *)
Definition: grphpath.c:1751
struct presolve_info PRESOL
SCIP_RETCODE graph_pc_2mw(SCIP *, GRAPH *, SCIP_Real *)
Definition: grphbase.c:1682
void graph_path_st_rpc(SCIP *, const GRAPH *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *)
Definition: grphpath.c:1033
SCIP_RETCODE graph_pc_init(SCIP *, GRAPH *, int, int)
Definition: grphbase.c:766
SCIP_Bool graph_sol_unreduced(SCIP *, const GRAPH *, const int *)
Definition: grphbase.c:3050
void graph_get4next(SCIP *, const GRAPH *, const SCIP_Real *, const SCIP_Real *, PATH *, int *, int *, int *)
Definition: grphpath.c:2041
SCIP_RETCODE graph_pc_getSapShift(SCIP *, GRAPH *, GRAPH **, SCIP_Real *)
Definition: grphbase.c:1204
void graph_path_st(SCIP *, const GRAPH *, SCIP_Real *, SCIP_Real *, int *, int, SCIP_RANDNUMGEN *, STP_Bool *)
Definition: grphpath.c:926
int *RESTRICT head
Definition: grph.h:96
int *RESTRICT mincut_x
Definition: grph.h:114
int *RESTRICT orgtail
Definition: grph.h:97
Definition: grph.h:57
Definition: grph.h:178
int source
Definition: grph.h:67
SCIP_RETCODE graph_voronoiWithDist(SCIP *, const GRAPH *, SCIP_Real *, double *, int *, int *, int *, int *, int *, int *, PATH *)
SCIP_RETCODE graph_pc_getRsap(SCIP *, GRAPH *, GRAPH **, int *, int, int)
Definition: grphbase.c:1365
void graph_edge_hide(GRAPH *, int)
Definition: grphbase.c:2891
signed int edge
Definition: grph.h:146
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
SCIP_RETCODE graph_trail_arr(SCIP *, const GRAPH *, int)
Definition: grphbase.c:4242
void reduce_ans(SCIP *, GRAPH *, int *, int *)
Definition: reduce_alt.c:4447
Definition: grph.h:178
SCIP_Bool graph_valid(const GRAPH *)
Definition: grphbase.c:4328
int terms
Definition: grph.h:64
SCIP_Real upper
Definition: grph.h:136
SCIP_RETCODE reduce_rpt(SCIP *, GRAPH *, SCIP_Real *, int *)
void graph_knot_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: grphbase.c:2246
int graph_pc_deleteTerm(SCIP *, GRAPH *, int)
Definition: grphbase.c:1945
SCIP_RETCODE graph_copy(SCIP *, const GRAPH *, GRAPH **)
Definition: grphbase.c:3900
SCIP_RETCODE graph_init_history(SCIP *, GRAPH *)
Definition: grphbase.c:3573
SCIP_RETCODE graph_obstgrid_create(SCIP *, GRAPH **, int **, int **, int, int, int, int)
Definition: grphbase.c:419
int norgmodeledges
Definition: grph.h:88
int *RESTRICT maxdeg
Definition: grph.h:78
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
void graph_path_st_rmw(SCIP *, const GRAPH *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *)
Definition: grphpath.c:1536
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
Definition: grph.h:178
int *RESTRICT mincut_temp
Definition: grph.h:112
SCIP_RETCODE graph_pc_presolInit(SCIP *, GRAPH *)
Definition: grphbase.c:794
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)
Definition: grph.h:178
SCIP_RETCODE graph_mincut_init(SCIP *, GRAPH *)
Definition: grphmcut.c:275
struct shortest_path PATH
SCIP_RETCODE reduce_nv(SCIP *, GRAPH *, PATH *, double *, int *, int *, int *, int *, int *, int *)
Definition: reduce_alt.c:3710
SCIP_RETCODE reduce_contractZeroEdges(SCIP *, GRAPH *, SCIP_Bool)
int *RESTRICT inpbeg
Definition: grph.h:74
SCIP_RETCODE graph_pc_mw2rmw(SCIP *, GRAPH *, SCIP_Real)
Definition: grphbase.c:1850
int *RESTRICT path_state
Definition: grph.h:119
void graph_free(SCIP *, GRAPH **, SCIP_Bool)
Definition: grphbase.c:3678
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
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
void graph_path_exit(SCIP *, GRAPH *)
Definition: grphpath.c:466
SCIP_RETCODE graph_knot_delPseudo(SCIP *, GRAPH *, const SCIP_Real *, const SCIP_Real *, const SCIP_Real *, int, SCIP_Bool *)
Definition: grphbase.c:2262
SCIP_Real lower
Definition: grph.h:137
SCIP_RETCODE graph_pc_contractEdgeAncestors(SCIP *, GRAPH *, int, int, int)
Definition: grphbase.c:2079
void graph_voronoiRepair(SCIP *, const GRAPH *, SCIP_Real *, int *, int *, PATH *, int *, int, UF *)
Definition: grphpath.c:2979
SCIP_RETCODE graph_resize(SCIP *, GRAPH *, int, int, int)
Definition: grphbase.c:3635
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
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
int *RESTRICT orghead
Definition: grph.h:98
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
SCIP_RETCODE reduce_simple(SCIP *, GRAPH *, SCIP_Real *, int *, int *, int *)
void graph_knot_chg(GRAPH *, int, int)
Definition: grphbase.c:2222
void graph_pc_updateTerm2edge(GRAPH *, const GRAPH *, int, int, int, int)
Definition: grphbase.c:928
SCIP_RETCODE graph_pc_2rmw(SCIP *, GRAPH *)
Definition: grphbase.c:1741
int *RESTRICT mark
Definition: grph.h:70
SCIP_Bool graph_pc_term2edgeConsistent(const GRAPH *)
Definition: grphbase.c:853
IDX * fixedges
Definition: grph.h:85
SCIP_RETCODE graph_pc_contractEdge(SCIP *, GRAPH *, int *, int, int, int)
Definition: grphbase.c:2105
void graph_voronoiRepairMult(SCIP *, const GRAPH *, SCIP_Real *, int *, int *, int *, int *, STP_Bool *, UF *, PATH *)
Definition: grphpath.c:3057
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
void graph_sdPaths(SCIP *, const GRAPH *, PATH *, SCIP_Real *, SCIP_Real, int *, int *, int *, int *, int, int, int)
Definition: grphpath.c:567
SCIP_RETCODE graph_pack(SCIP *, GRAPH *, GRAPH **, SCIP_Bool)
Definition: grphbase.c:3988
void graph_path_execX(SCIP *, const GRAPH *, int, const SCIP_Real *, SCIP_Real *, int *)
Definition: grphpath.c:781
SCIP_RETCODE reduce_cnsAdv(SCIP *, GRAPH *, int *, int *)
Definition: reduce_alt.c:4748
void graph_path_st_pcmw(SCIP *, const GRAPH *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *)
Definition: grphpath.c:1154
SCIP_RETCODE reduce_boundHopR(SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *)
Definition: reduce_bnd.c:6098
int *RESTRICT oeat
Definition: grph.h:103
void graph_pc_2org(GRAPH *)
Definition: grphbase.c:964
int *RESTRICT mincut_dist
Definition: grph.h:106
SCIP_RETCODE reduce_simple_mw(SCIP *, GRAPH *, int *, SCIP_Real *, int *)
void graph_knot_contract_dir(GRAPH *, int, int)
SCIP_RETCODE graph_termsReachable(SCIP *, const GRAPH *, SCIP_Bool *)
Definition: grphbase.c:4299
miscellaneous methods used for solving Steiner problems
SCIP_RETCODE graph_knot_contractLowdeg2High(SCIP *, GRAPH *, int *, int, int)
Definition: grphbase.c:2666
SCIP_Bool extended
Definition: grph.h:128
int stp_type
Definition: grph.h:127
void graph_path_st_pcmw_extend(SCIP *, const GRAPH *, const SCIP_Real *, PATH *, STP_Bool *, SCIP_Bool *)
Definition: grphpath.c:1410
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
IDX ** ancestors
Definition: grph.h:86
SCIP_RETCODE level0(SCIP *, GRAPH *)
Definition: reduce.c:153
int orgedges
Definition: grph.h:93
SCIP_RETCODE reduce_deleteConflictEdges(SCIP *, GRAPH *)
Definition: reduce_bnd.c:2421
void heap_add(int *, int *, int *, int, PATH *)
Definition: grphpath.c:244
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
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
void graph_pc_2trans(GRAPH *)
Definition: grphbase.c:1002
unsigned char STP_Bool
Definition: grph.h:52
SCIP_RETCODE graph_sol_reroot(SCIP *, GRAPH *, int *, int)
Definition: grphbase.c:2947
SCIP_RETCODE graph_pc_2rpc(SCIP *, GRAPH *)
Definition: grphbase.c:1601
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
SCIP_Real * prize
Definition: grph.h:82
SCIP_RETCODE reduce_simple_sap(SCIP *, GRAPH *, SCIP_Real *, int *)
SCIP_Real dist
Definition: grph.h:145
int *RESTRICT grad
Definition: grph.h:73
void graph_pc_presolExit(SCIP *, GRAPH *)
Definition: grphbase.c:837
int *RESTRICT mincut_head_inact
Definition: grph.h:108
SCIP_Bool graph_sol_valid(SCIP *, const GRAPH *, const int *)
Definition: grphbase.c:3070
SCIP_RETCODE graph_grid_coordinates(SCIP *, int **, int **, int *, int, int)
Definition: grphbase.c:730
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
void graph_path_exec(SCIP *, const GRAPH *, const int, int, const SCIP_Real *, PATH *)
Definition: grphpath.c:491
void graph_path_st_pcmw_full(SCIP *, const GRAPH *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *)
Definition: grphpath.c:1316
int knots
Definition: grph.h:62
SCIP_RETCODE reduce_bd34(SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
Definition: reduce_alt.c:2964
SCIP_RETCODE reduce_nvAdv(SCIP *, GRAPH *, PATH *, SCIP_Real *, double *, int *, int *, int *, int *, int *, int *, int *, int *)
Definition: reduce_alt.c:3903
void voronoiSteinerTreeExt(SCIP *, const GRAPH *, SCIP_Real *, int *, STP_Bool *, PATH *)
int * term2edge
Definition: grph.h:80
IDX ** pcancestors
Definition: grph.h:87
SCIP_RETCODE graph_copy_data(SCIP *, const GRAPH *, GRAPH *)
Definition: grphbase.c:3809
void graph_get2next(SCIP *, const GRAPH *, const SCIP_Real *, const SCIP_Real *, PATH *, int *, int *, int *)
Definition: grphpath.c:1838
void graph_free_history(SCIP *, GRAPH *)
Definition: grphbase.c:3740
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
int orgknots
Definition: grph.h:63
SCIP_Real graph_pc_getPosPrizeSum(SCIP *, const GRAPH *)
Definition: grphbase.c:1054
SCIP_RETCODE graph_get_edgeConflicts(SCIP *, const GRAPH *)
Definition: grphbase.c:3452
SCIP_RETCODE reduce_simple_hc(SCIP *, GRAPH *, SCIP_Real *, int *)
void graph_path_st_pcmw_reduce(SCIP *, const GRAPH *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *)
Definition: grphpath.c:1264
int *RESTRICT mincut_head
Definition: grph.h:107
void graph_voronoiWithRadiusMw(SCIP *scip, const GRAPH *, PATH *, const SCIP_Real *, SCIP_Real *, int *, int *, int *)
Definition: grphpath.c:2852
void voronoi_term(const GRAPH *, double *, double *, double *, PATH *, int *, int *, int *, int *, int)
void reduce_ansAdv2(SCIP *, GRAPH *, int *, int *)
Definition: reduce_alt.c:4621
void reduce_ansAdv(SCIP *, GRAPH *, int *, int *, SCIP_Bool)
Definition: reduce_alt.c:4515
SCIP_RETCODE reduce_simple_pc(SCIP *, GRAPH *, SCIP_Real *, int *, int *, SCIP_Bool)
#define SCIP_Bool
Definition: def.h:70
int *RESTRICT ieat
Definition: grph.h:102
int *RESTRICT path_heap
Definition: grph.h:118
SCIP_RETCODE graph_sol_getOrg(SCIP *, const GRAPH *, const GRAPH *, const int *, int *)
Definition: grphbase.c:3218
SCIP_RETCODE reduce_boundHop(SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *)
Definition: reduce_bnd.c:5904
void graph_save(const GRAPH *, const char *, FILETYPE)
Definition: grphsave.c:309
int *RESTRICT tail
Definition: grph.h:95
int time
Definition: grph.h:138
void graph_show(const GRAPH *)
Definition: grphbase.c:3916
void graph_uncover(GRAPH *)
Definition: grphbase.c:3941
void graph_pc_chgPrize(SCIP *, GRAPH *, SCIP_Real, int)
Definition: grphbase.c:2035
void graph_voronoiMw(SCIP *, const GRAPH *, const SCIP_Real *, PATH *, int *, int *, int *)
Definition: grphpath.c:2383
void graph_mincut_exit(SCIP *, GRAPH *)
Definition: grphmcut.c:305
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
Definition: grphbase.c:2188
SCIP_RETCODE reduce_sl(SCIP *, GRAPH *, PATH *, double *, int *, int *, int *, int *, STP_Bool *, int *, int *)
Definition: reduce_alt.c:3483
SCIP_RETCODE graph_sol_markPcancestors(SCIP *, IDX **, const int *, const int *, int, STP_Bool *, STP_Bool *, int *, int *, int *)
Definition: grphbase.c:3292
SCIP_RETCODE reduce_nts(SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
Definition: reduce_alt.c:3217
SCIP_RETCODE SCIPStpValidateSol(SCIP *, const GRAPH *, const double *, SCIP_Bool *)
Definition: validate.c:136
int *RESTRICT term
Definition: grph.h:68
void graph_edge_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: grphbase.c:2841
SCIP_Real graph_sol_getObj(const SCIP_Real *, const int *, SCIP_Real, int)
Definition: grphbase.c:3200
SCIP_RETCODE reduce_ledge(SCIP *, GRAPH *, PATH *, int *, int *, int *, int *, int *)
Definition: reduce_alt.c:4143
SCIP_RETCODE reduce_sdPc(SCIP *, GRAPH *, PATH *, int *, int *, int *, int *, int *, int *)
Definition: reduce_alt.c:1499
int *RESTRICT mincut_prev
Definition: grph.h:110
int grid_dim
Definition: grph.h:122
int ** grid_coordinates
Definition: grph.h:124
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
int *RESTRICT mincut_numb
Definition: grph.h:109
int layers
Definition: grph.h:65
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
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
void graph_path_invroot(SCIP *, const GRAPH *, int, const SCIP_Real *, SCIP_Real *, int *)
Definition: grphpath.c:849
void graph_get4nextTerms(SCIP *, const GRAPH *, SCIP_Real *, SCIP_Real *, PATH *, int *, int *, int *)
Definition: grphpath.c:2186
void graph_get_csr(const GRAPH *, int *RESTRICT, int *RESTRICT, int *RESTRICT, int *)
struct Graph GRAPH
SCIP_RETCODE reduceStp(SCIP *, GRAPH **, SCIP_Real *, int, SCIP_Bool, SCIP_Bool, SCIP_Bool)
Definition: reduce.c:223
SCIP_Real * cost
Definition: grph.h:94
SCIP_RETCODE reduce_sdspSap(SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
Definition: reduce_alt.c:2308
void graph_edge_printInfo(SCIP *, const GRAPH *, int)
Definition: grphbase.c:2935
int *RESTRICT rootedgeprevs
Definition: grph.h:99
SCIP_RETCODE graph_load(SCIP *, GRAPH **, const char *, PRESOL *)
Definition: grphload.c:821
#define SCIP_Real
Definition: def.h:163
int esize
Definition: grph.h:91
int *RESTRICT outbeg
Definition: grph.h:76
void graph_pc_2orgcheck(GRAPH *)
Definition: grphbase.c:1028
void graph_get3next(SCIP *, const GRAPH *, const SCIP_Real *, const SCIP_Real *, PATH *, int *, int *, int *)
Definition: grphpath.c:1934
int edges
Definition: grph.h:92
SCIP_RETCODE graph_pc_getSap(SCIP *, GRAPH *, GRAPH **, SCIP_Real *)
Definition: grphbase.c:1075
int * grid_ncoords
Definition: grph.h:123
void graph_knot_add(GRAPH *, int)
Definition: grphbase.c:2200
void voronoi_inout(const GRAPH *)
SCIP_RETCODE graph_get4nextTTerms(SCIP *, const GRAPH *, SCIP_Real *, PATH *, int *, int *, int *)
Definition: grphpath.c:2227
SCIP_RETCODE graph_knot_contract(SCIP *, GRAPH *, int *, int, int)
Definition: grphbase.c:2433
SCIP_RETCODE reduce(SCIP *, GRAPH **, SCIP_Real *, int, int, SCIP_Bool)
Definition: reduce.c:1675
SCIP_Real fixed
Definition: grph.h:135
int ksize
Definition: grph.h:61
int *RESTRICT mincut_r
Definition: grph.h:115
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
SCIP_RETCODE graph_pc_2pc(SCIP *, GRAPH *)
Definition: grphbase.c:1520
Definition: grph.h:178
void graph_pc_knot2nonTerm(GRAPH *, int)
Definition: grphbase.c:909
void graph_pc_adaptSap(SCIP *, SCIP_Real, GRAPH *, SCIP_Real *)
Definition: grphbase.c:1174
SCIP_RETCODE reduce_npv(SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
Definition: reduce_alt.c:5024
int hoplimit
Definition: grph.h:89
int graph_edge_redirect(SCIP *, GRAPH *, int, int, int, SCIP_Real, SCIP_Bool)
Definition: grphbase.c:2685
void graph_edge_add(SCIP *, GRAPH *, int, int, double, double)
void graph_get3nextTerms(SCIP *, const GRAPH *, SCIP_Real *, SCIP_Real *, PATH *, int *, int *, int *)
Definition: grphpath.c:2150
SCIP_RETCODE graph_edge_reinsert(SCIP *, GRAPH *, int, int, int, SCIP_Real, IDX *, IDX *, IDX *, IDX *, SCIP_Bool)
Definition: grphbase.c:2757
SCIP_RETCODE graph_grid_create(SCIP *, GRAPH **, int **, int, int, int)
Definition: grphbase.c:582
void graph_free_historyDeep(SCIP *, GRAPH *)
Definition: grphbase.c:3764
void graph_trail(const GRAPH *, int)
Definition: grphbase.c:4188
void graph_voronoiTerms(SCIP *, const GRAPH *, const SCIP_Real *, PATH *, int *, int *, int *)
Definition: grphpath.c:2307
SCIP_RETCODE graph_voronoiWithRadius(SCIP *scip, const GRAPH *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *)
Definition: grphpath.c:2614
SCIP_RETCODE reduce_sdsp(SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int, int *)
Definition: reduce_alt.c:2459
SCIP callable library.
int *RESTRICT mincut_next
Definition: grph.h:111
SCIP_RETCODE graph_init(SCIP *, GRAPH **, int, int, int)
Definition: grphbase.c:3495
void graph_sol_setNodeList(const GRAPH *, STP_Bool *, IDX *)
Definition: grphbase.c:3174
void graph_pc_2transcheck(GRAPH *)
Definition: grphbase.c:1041
int norgmodelknots
Definition: grph.h:60
int orgsource
Definition: grph.h:66
SCIP_RETCODE reduce_chain2(SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
Definition: reduce_alt.c:5367
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