Scippy

SCIP

Solving Constraint Integer Programs

grph.h File Reference

Detailed Description

includes various files containing graph methods used for Steiner tree problems

Author
Gerald Gamrath
Thorsten Koch
Daniel Rehfeldt

Definition in file grph.h.

#include "scip/scip.h"
#include "misc_stp.h"

Go to the source code of this file.

Data Structures

struct  GRAPH
 
struct  presolve_info
 
struct  shortest_path
 

Macros

#define EAT_FREE   -1
 
#define EAT_LAST   -2
 
#define EAT_HIDE   -3
 
#define GRAPH_HAS_COORDINATES   1
 
#define GRAPH_IS_GRIDGRAPH   2
 
#define GRAPH_IS_DIRECTED   4
 
#define STP_SPG   0
 
#define STP_SAP   1
 
#define STP_PCSPG   2
 
#define STP_RPCSPG   3
 
#define STP_NWSPG   4
 
#define STP_DCSTP   5
 
#define STP_REVENUES_BUDGET_HOPCONS   6
 
#define STP_RSMT   7
 
#define STP_OARSMT   8
 
#define STP_MWCSP   9
 
#define STP_DHCSTP   10
 
#define STP_GSTP   11
 
#define STP_RMWCSP   12
 
#define flipedge(edge)   ( ((edge) + 1) - 2 * ((edge) % 2) )
 
#define flipedge_Uint(edge)   ( (((unsigned int) edge) + 1) - 2 * (((unsigned int) edge) % 2) )
 
#define PATH_NIL   ((PATH*)0)
 
#define CONNECT   0
 
#define UNKNOWN   (-1)
 
#define FARAWAY   1e15
 
#define BLOCKED   1e10
 
#define EDGE_BLOCKED   0
 
#define EDGE_MODIFIABLE   1
 
#define MST_MODE   0
 
#define FSP_MODE   1
 
#define BSP_MODE   2
 
#define NO_CHANGE   -10
 
#define Is_term(a)   ((a) >= 0)
 
#define Is_pterm(a)   ((a) == -2)
 
#define Is_gterm(a)   ((a) == -2 || (a) >= 0 )
 
#define Edge_anti(a)   ((((a) % 2) > 0) ? (a) - 1 : (a) + 1)
 
#define VERSION_SCIPJACK   "1.3"
 
#define STP_MAGIC   0x33d32945
 
#define VERSION_MAJOR   1
 
#define VERSION_MINOR   0
 

Typedefs

typedef unsigned char STP_Bool
 
typedef struct presolve_info PRESOL
 
typedef struct shortest_path PATH
 

Enumerations

enum  FILETYPE {
  FF_BEA,
  FF_STP,
  FF_PRB,
  FF_GRD
}
 

Functions

void graph_pc_knot2nonTerm (GRAPH *, int)
 
void graph_pc_updateTerm2edge (GRAPH *, const GRAPH *, int, int, int, int)
 
void graph_pc_subtractPrize (SCIP *, GRAPH *, SCIP_Real, int)
 
void graph_pc_chgPrize (SCIP *, GRAPH *, SCIP_Real, int)
 
void graph_show (const GRAPH *)
 
void graph_knot_add (GRAPH *, int)
 
void graph_knot_chg (GRAPH *, int, int)
 
void graph_knot_del (SCIP *, GRAPH *, int, SCIP_Bool)
 
void graph_knot_contract_dir (GRAPH *, int, int)
 
void graph_get_csr (const GRAPH *, int *RESTRICT, int *RESTRICT, int *RESTRICT, int *)
 
void graph_edge_add (SCIP *, GRAPH *, int, int, double, double)
 
void graph_edge_del (SCIP *, GRAPH *, int, SCIP_Bool)
 
void graph_edge_hide (GRAPH *, int)
 
void graph_edge_printInfo (SCIP *, const GRAPH *, int)
 
void graph_uncover (GRAPH *)
 
void graph_trail (const GRAPH *, int)
 
void graph_free (SCIP *, GRAPH **, SCIP_Bool)
 
void graph_free_history (SCIP *, GRAPH *)
 
void graph_free_historyDeep (SCIP *, GRAPH *)
 
void graph_get_NVET (const GRAPH *, int *, int *, int *)
 
void graph_sol_setNodeList (const GRAPH *, STP_Bool *, IDX *)
 
void graph_pc_2org (GRAPH *)
 
void graph_pc_2trans (GRAPH *)
 
void graph_pc_2orgcheck (GRAPH *)
 
void graph_pc_2transcheck (GRAPH *)
 
void graph_pc_adaptSap (SCIP *, SCIP_Real, GRAPH *, SCIP_Real *)
 
void graph_pc_presolExit (SCIP *, GRAPH *)
 
SCIP_RETCODE graph_pc_init (SCIP *, GRAPH *, int, int)
 
SCIP_RETCODE graph_pc_2pc (SCIP *, GRAPH *)
 
SCIP_RETCODE graph_pc_2rpc (SCIP *, GRAPH *)
 
SCIP_RETCODE graph_pc_2mw (SCIP *, GRAPH *, SCIP_Real *)
 
SCIP_RETCODE graph_pc_2rmw (SCIP *, GRAPH *)
 
SCIP_RETCODE graph_pc_mw2rmw (SCIP *, GRAPH *, SCIP_Real)
 
SCIP_RETCODE graph_pc_getSap (SCIP *, GRAPH *, GRAPH **, SCIP_Real *)
 
SCIP_RETCODE graph_pc_getSapShift (SCIP *, GRAPH *, GRAPH **, SCIP_Real *)
 
SCIP_RETCODE graph_pc_getRsap (SCIP *, GRAPH *, GRAPH **, int *, int, int)
 
SCIP_RETCODE graph_pc_contractEdgeAncestors (SCIP *, GRAPH *, int, int, int)
 
SCIP_RETCODE graph_pc_contractEdge (SCIP *, GRAPH *, int *, int, int, int)
 
SCIP_RETCODE graph_resize (SCIP *, GRAPH *, int, int, int)
 
SCIP_RETCODE graph_knot_contract (SCIP *, GRAPH *, int *, int, int)
 
SCIP_RETCODE graph_knot_contractLowdeg2High (SCIP *, GRAPH *, int *, int, int)
 
SCIP_RETCODE graph_sol_reroot (SCIP *, GRAPH *, int *, int)
 
SCIP_RETCODE graph_sol_getOrg (SCIP *, const GRAPH *, const GRAPH *, const int *, int *)
 
SCIP_RETCODE graph_sol_markPcancestors (SCIP *, IDX **, const int *, const int *, int, STP_Bool *, STP_Bool *, int *, int *, int *)
 
SCIP_RETCODE graph_edge_reinsert (SCIP *, GRAPH *, int, int, int, SCIP_Real, IDX *, IDX *, IDX *, IDX *, SCIP_Bool)
 
SCIP_RETCODE graph_knot_delPseudo (SCIP *, GRAPH *, const SCIP_Real *, const SCIP_Real *, const SCIP_Real *, int, SCIP_Bool *)
 
SCIP_RETCODE graph_grid_create (SCIP *, GRAPH **, int **, int, int, int)
 
SCIP_RETCODE graph_obstgrid_create (SCIP *, GRAPH **, int **, int **, int, int, int, int)
 
SCIP_RETCODE graph_grid_coordinates (SCIP *, int **, int **, int *, int, int)
 
SCIP_RETCODE graph_copy_data (SCIP *, const GRAPH *, GRAPH *)
 
SCIP_RETCODE graph_copy (SCIP *, const GRAPH *, GRAPH **)
 
SCIP_RETCODE graph_pack (SCIP *, GRAPH *, GRAPH **, SCIP_Bool)
 
SCIP_RETCODE graph_trail_arr (SCIP *, const GRAPH *, int)
 
SCIP_RETCODE graph_get_edgeConflicts (SCIP *, const GRAPH *)
 
SCIP_RETCODE graph_init (SCIP *, GRAPH **, int, int, int)
 
SCIP_RETCODE graph_init_history (SCIP *, GRAPH *)
 
SCIP_RETCODE graph_termsReachable (SCIP *, const GRAPH *, SCIP_Bool *)
 
SCIP_RETCODE graph_pc_presolInit (SCIP *, GRAPH *)
 
int graph_edge_redirect (SCIP *, GRAPH *, int, int, int, SCIP_Real, SCIP_Bool)
 
int graph_pc_deleteTerm (SCIP *, GRAPH *, int)
 
SCIP_Bool graph_valid (const GRAPH *)
 
SCIP_Bool graph_pc_term2edgeConsistent (const GRAPH *)
 
SCIP_Bool graph_sol_unreduced (SCIP *, const GRAPH *, const int *)
 
SCIP_Bool graph_sol_valid (SCIP *, const GRAPH *, const int *)
 
SCIP_Bool graph_pc_isPcMw (const GRAPH *)
 
SCIP_Real graph_sol_getObj (const SCIP_Real *, const int *, SCIP_Real, int)
 
SCIP_Real graph_pc_getPosPrizeSum (SCIP *, const GRAPH *)
 
void graph_path_exit (SCIP *, GRAPH *)
 
void graph_path_exec (SCIP *, const GRAPH *, const int, int, const SCIP_Real *, PATH *)
 
void graph_path_execX (SCIP *, const GRAPH *, int, const SCIP_Real *, SCIP_Real *, int *)
 
void graph_path_invroot (SCIP *, const GRAPH *, int, const SCIP_Real *, SCIP_Real *, int *)
 
void graph_path_st (SCIP *, const GRAPH *, SCIP_Real *, SCIP_Real *, int *, int, SCIP_RANDNUMGEN *, STP_Bool *)
 
void graph_path_st_rmw (SCIP *, const GRAPH *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *)
 
void graph_path_st_pcmw (SCIP *, const GRAPH *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *)
 
void graph_path_st_pcmw_full (SCIP *, const GRAPH *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *)
 
void graph_path_st_pcmw_reduce (SCIP *, const GRAPH *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *)
 
void graph_path_st_pcmw_extend (SCIP *, const GRAPH *, const SCIP_Real *, PATH *, STP_Bool *, SCIP_Bool *)
 
void graph_path_st_rpc (SCIP *, const GRAPH *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *)
 
void graph_voronoi (SCIP *scip, const GRAPH *, SCIP_Real *, SCIP_Real *, STP_Bool *, int *, PATH *)
 
void graph_get2next (SCIP *, const GRAPH *, const SCIP_Real *, const SCIP_Real *, PATH *, int *, int *, int *)
 
void graph_get3next (SCIP *, const GRAPH *, const SCIP_Real *, const SCIP_Real *, PATH *, int *, int *, int *)
 
void graph_get4next (SCIP *, const GRAPH *, const SCIP_Real *, const SCIP_Real *, PATH *, int *, int *, int *)
 
void graph_get3nextTerms (SCIP *, const GRAPH *, SCIP_Real *, SCIP_Real *, PATH *, int *, int *, int *)
 
void graph_get4nextTerms (SCIP *, const GRAPH *, SCIP_Real *, SCIP_Real *, PATH *, int *, int *, int *)
 
void graph_voronoiMw (SCIP *, const GRAPH *, const SCIP_Real *, PATH *, int *, int *, int *)
 
void graph_voronoiTerms (SCIP *, const GRAPH *, const SCIP_Real *, PATH *, int *, int *, int *)
 
void voronoi_inout (const GRAPH *)
 
void voronoi_term (const GRAPH *, double *, double *, double *, PATH *, int *, int *, int *, int *, int)
 
void heap_add (int *, int *, int *, int, PATH *)
 
void graph_voronoiRepair (SCIP *, const GRAPH *, SCIP_Real *, int *, int *, PATH *, int *, int, UF *)
 
void graph_voronoiRepairMult (SCIP *, const GRAPH *, SCIP_Real *, int *, int *, int *, int *, STP_Bool *, UF *, PATH *)
 
void voronoiSteinerTreeExt (SCIP *, const GRAPH *, SCIP_Real *, int *, STP_Bool *, PATH *)
 
void graph_sdPaths (SCIP *, const GRAPH *, PATH *, SCIP_Real *, SCIP_Real, int *, int *, int *, int *, int, int, int)
 
void graph_path_PcMwSd (SCIP *, const GRAPH *, PATH *, SCIP_Real *, SCIP_Real, int *, int *, int *, int *, int *, int *, int, int, int)
 
void graph_voronoiWithRadiusMw (SCIP *scip, const GRAPH *, PATH *, const SCIP_Real *, SCIP_Real *, int *, int *, int *)
 
SCIP_RETCODE graph_voronoiExtend (SCIP *, const GRAPH *, SCIP_Real *, PATH *, SCIP_Real **, int **, int **, STP_Bool *, int *, int *, int *, int, int, int)
 
SCIP_RETCODE graph_path_init (SCIP *, GRAPH *)
 
SCIP_RETCODE graph_voronoiWithDist (SCIP *, const GRAPH *, SCIP_Real *, double *, int *, int *, int *, int *, int *, int *, PATH *)
 
SCIP_RETCODE graph_voronoiWithRadius (SCIP *scip, const GRAPH *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *)
 
SCIP_RETCODE graph_get4nextTTerms (SCIP *, const GRAPH *, SCIP_Real *, PATH *, int *, int *, int *)
 
void graph_mincut_exit (SCIP *, GRAPH *)
 
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)
 
SCIP_RETCODE graph_mincut_init (SCIP *, GRAPH *)
 
SCIP_RETCODE graph_load (SCIP *, GRAPH **, const char *, PRESOL *)
 
void graph_save (const GRAPH *, const char *, FILETYPE)
 
void SCIPwriteStp (SCIP *, const GRAPH *, FILE *, SCIP_Real)
 
SCIP_RETCODE level0 (SCIP *, GRAPH *)
 
SCIP_RETCODE level0save (SCIP *, GRAPH *)
 
SCIP_RETCODE reduceStp (SCIP *, GRAPH **, SCIP_Real *, int, SCIP_Bool, SCIP_Bool, SCIP_Bool)
 
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)
 
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)
 
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)
 
SCIP_RETCODE reduce (SCIP *, GRAPH **, SCIP_Real *, int, int, SCIP_Bool)
 
void reduce_ans (SCIP *, GRAPH *, int *, int *)
 
void reduce_ansAdv (SCIP *, GRAPH *, int *, int *, SCIP_Bool)
 
void reduce_ansAdv2 (SCIP *, GRAPH *, int *, int *)
 
void reduce_nnp (SCIP *, GRAPH *, int *, int *)
 
SCIP_RETCODE reduce_sdsp (SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int, int *)
 
SCIP_RETCODE reduce_sdspSap (SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
 
SCIP_RETCODE reduce_sd (SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *, int *, int *, SCIP_Bool, int *)
 
SCIP_RETCODE reduce_sdPc (SCIP *, GRAPH *, PATH *, int *, int *, int *, int *, int *, int *)
 
SCIP_RETCODE reduce_getSd (SCIP *, GRAPH *, PATH *, PATH *, SCIP_Real *, SCIP_Real, int *, int *, int *, int *, int *, int, int, int, SCIP_Bool, SCIP_Bool)
 
SCIP_RETCODE reduce_getSdPcMw (SCIP *, const GRAPH *, PATH *, PATH *, SCIP_Real *, SCIP_Real, int *, int *, int *, int *, int *, int *, int *, int, int, int)
 
SCIP_RETCODE reduce_nts (SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
 
SCIP_RETCODE reduce_bd34 (SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
 
SCIP_RETCODE reduce_bdr (SCIP *, GRAPH *, GRAPH *, PATH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *)
 
SCIP_RETCODE reduce_nv (SCIP *, GRAPH *, PATH *, double *, int *, int *, int *, int *, int *, int *)
 
SCIP_RETCODE reduce_nvAdv (SCIP *, GRAPH *, PATH *, SCIP_Real *, double *, int *, int *, int *, int *, int *, int *, int *, int *)
 
SCIP_RETCODE reduce_sl (SCIP *, GRAPH *, PATH *, double *, int *, int *, int *, int *, STP_Bool *, int *, int *)
 
SCIP_RETCODE reduce_ledge (SCIP *, GRAPH *, PATH *, int *, int *, int *, int *, int *)
 
SCIP_RETCODE reduce_cnsAdv (SCIP *, GRAPH *, int *, int *)
 
SCIP_RETCODE reduce_npv (SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
 
SCIP_RETCODE reduce_chain2 (SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
 
SCIP_RETCODE reduce_deleteConflictEdges (SCIP *, GRAPH *)
 
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 *)
 
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)
 
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)
 
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)
 
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)
 
SCIP_RETCODE reduce_bound (SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *)
 
SCIP_RETCODE reduce_boundMw (SCIP *, GRAPH *, PATH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *)
 
SCIP_RETCODE reduce_boundPrune (SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, const int *, const int *, int *, int)
 
SCIP_RETCODE reduce_boundHop (SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *)
 
SCIP_RETCODE reduce_boundHopR (SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *)
 
SCIP_RETCODE reduce_boundHopRc (SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real, int *, int *, int *, int *, int *, SCIP_Bool)
 
int reduce_extendedEdge (SCIP *, GRAPH *, const PATH *, const SCIP_Real *, const SCIP_Real *, const int *, SCIP_Real, int, int *, STP_Bool *)
 
SCIP_RETCODE reduce_contractZeroEdges (SCIP *, GRAPH *, SCIP_Bool)
 
SCIP_RETCODE reduce_simple (SCIP *, GRAPH *, SCIP_Real *, int *, int *, int *)
 
SCIP_RETCODE reduce_simple_hc (SCIP *, GRAPH *, SCIP_Real *, int *)
 
SCIP_RETCODE reduce_simple_mw (SCIP *, GRAPH *, int *, SCIP_Real *, int *)
 
SCIP_RETCODE reduce_simple_pc (SCIP *, GRAPH *, SCIP_Real *, int *, int *, SCIP_Bool)
 
SCIP_RETCODE reduce_simple_sap (SCIP *, GRAPH *, SCIP_Real *, int *)
 
SCIP_RETCODE reduce_rpt (SCIP *, GRAPH *, SCIP_Real *, int *)
 
SCIP_RETCODE SCIPStpValidateSol (SCIP *, const GRAPH *, const double *, SCIP_Bool *)
 

Macro Definition Documentation

◆ EAT_FREE

◆ EAT_LAST

#define EAT_LAST   -2

Definition at line 31 of file grph.h.

Referenced by adjust0term(), ansProcessCandidate(), branchOnVertex(), buildsolgraph(), compEdges(), computeDegConsTree(), computePertubedSol(), computeSteinerTreeVnoi(), computeTransVoronoi(), createVariables(), dualascent_init(), dualCostIsValid(), dualcostVarfixing(), extendSubtreeHead(), extendSubtreeTail(), findDaRoots(), getcloseterms2term(), getlecloseterms(), getRSD(), graph_edge_redirect(), graph_get2next(), graph_get3next(), graph_get4next(), graph_get4nextTTerms(), graph_get_csr(), graph_knot_add(), graph_knot_contract(), graph_knot_del(), graph_knot_delPseudo(), graph_load(), graph_mincut_exec(), graph_pack(), graph_path_exec(), graph_path_execX(), graph_path_invroot(), graph_path_PcMwSd(), graph_path_st(), graph_path_st_pcmw(), graph_path_st_pcmw_extend(), graph_path_st_pcmw_full(), graph_path_st_pcmw_reduce(), graph_path_st_rmw(), graph_path_st_rpc(), graph_pc_2mw(), graph_pc_2rmw(), graph_pc_adaptSap(), graph_pc_chgPrize(), graph_pc_contractEdge(), graph_pc_contractEdgeAncestors(), graph_pc_deleteTerm(), graph_pc_getRsap(), graph_pc_getSap(), graph_pc_getSapShift(), graph_pc_mw2rmw(), graph_pc_presolInit(), graph_pc_subtractPrize(), graph_pc_term2edgeConsistent(), graph_sdPaths(), graph_sol_reroot(), graph_sol_valid(), graph_trail(), graph_trail_arr(), graph_valid(), graph_voronoi(), graph_voronoiExtend(), graph_voronoiMw(), graph_voronoiRepair(), graph_voronoiRepairMult(), graph_voronoiTerms(), graph_voronoiWithDist(), graph_voronoiWithRadius(), graph_voronoiWithRadiusMw(), initReceivedSubproblem(), lca(), level0(), level0save(), markPcMwRoots(), pertubateEdgeCosts(), reduce_ans(), reduce_ansAdv(), reduce_ansAdv2(), reduce_bd34(), reduce_bdr(), reduce_bound(), reduce_boundHop(), reduce_boundHopR(), reduce_boundHopRc(), reduce_boundMw(), reduce_boundPrune(), reduce_check3Tree(), reduce_cnsAdv(), reduce_da(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), reduce_getSd(), reduce_getSdPcMw(), reduce_ledge(), reduce_nnp(), reduce_npv(), reduce_nts(), reduce_nv(), reduce_nvAdv(), reduce_rpt(), reduce_sd(), reduce_sdPc(), reduce_sdsp(), reduce_sdspSap(), reduce_simple(), reduce_simple_hc(), reduce_simple_mw(), reduce_simple_pc(), reduce_simple_sap(), reduce_sl(), reduceCheckEdge(), reducePcMw(), reduceSPG(), reduceWithEdgeFixingBounds(), reduceWithNodeReplaceBounds(), ruleOutSubtree(), SCIP_DECL_HEUREXEC(), SCIPprobdataAddNewSol(), SCIPprobdataWriteSolution(), SCIPStpDualAscentPcMw(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurLocalRun(), SCIPStpHeurRecRun(), SCIPStpHeurTMBuildTree(), SCIPStpHeurTMBuildTreeDc(), SCIPStpHeurTMBuildTreePcMw(), SCIPStpHeurTMPrune(), SCIPStpHeurTMPrunePc(), SCIPStpHeurTMRun(), SCIPStpValidateSol(), SCIPwriteStp(), sddeltable(), selectBranchingVertexByLp(), selectBranchingVertexByLp2Flow(), selectBranchingVertexBySol(), sep_2cut(), sep_flow(), setVnoiDistances(), trail(), traverseChain(), truncateSubtree(), trydg1edgepc(), updateEdgeFixingBounds(), updateFixingBounds(), and updateNodeReplaceBounds().

◆ EAT_HIDE

#define EAT_HIDE   -3

Definition at line 32 of file grph.h.

Referenced by graph_edge_del(), graph_edge_hide(), and graph_uncover().

◆ GRAPH_HAS_COORDINATES

#define GRAPH_HAS_COORDINATES   1

Definition at line 34 of file grph.h.

◆ GRAPH_IS_GRIDGRAPH

#define GRAPH_IS_GRIDGRAPH   2

Definition at line 35 of file grph.h.

◆ GRAPH_IS_DIRECTED

#define GRAPH_IS_DIRECTED   4

Definition at line 36 of file grph.h.

◆ STP_SPG

◆ STP_SAP

◆ STP_PCSPG

◆ STP_RPCSPG

◆ STP_NWSPG

#define STP_NWSPG   4

◆ STP_DCSTP

◆ STP_REVENUES_BUDGET_HOPCONS

#define STP_REVENUES_BUDGET_HOPCONS   6

Definition at line 44 of file grph.h.

◆ STP_RSMT

◆ STP_OARSMT

◆ STP_MWCSP

◆ STP_DHCSTP

◆ STP_GSTP

◆ STP_RMWCSP

◆ flipedge

#define flipedge (   edge)    ( ((edge) + 1) - 2 * ((edge) % 2) )

◆ flipedge_Uint

#define flipedge_Uint (   edge)    ( (((unsigned int) edge) + 1) - 2 * (((unsigned int) edge) % 2) )

Definition at line 151 of file grph.h.

Referenced by reduce_simple_mw().

◆ PATH_NIL

#define PATH_NIL   ((PATH*)0)

Definition at line 153 of file grph.h.

◆ CONNECT

◆ UNKNOWN

#define UNKNOWN   (-1)

Definition at line 155 of file grph.h.

◆ FARAWAY

#define FARAWAY   1e15

Definition at line 156 of file grph.h.

Referenced by buildsolgraph(), central_terminal(), compEdges(), computeDegConsTree(), computeSteinerTree(), computeSteinerTreeVnoi(), computeTransVoronoi(), dualcostVarfixing(), findDaRoots(), getlecloseterms(), getRSD(), graph_get2next(), graph_get3next(), graph_get4next(), graph_get4nextTTerms(), graph_load(), graph_pack(), graph_path_exec(), graph_path_execX(), graph_path_invroot(), graph_path_st(), graph_path_st_pcmw(), graph_path_st_pcmw_extend(), graph_path_st_pcmw_full(), graph_path_st_rmw(), graph_path_st_rpc(), graph_pc_2pc(), graph_pc_2rmw(), graph_pc_2rpc(), graph_pc_getRsap(), graph_pc_getSap(), graph_pc_getSapShift(), graph_pc_mw2rmw(), graph_voronoi(), graph_voronoiMw(), graph_voronoiTerms(), graph_voronoiWithDist(), graph_voronoiWithRadius(), graph_voronoiWithRadiusMw(), redbasedVarfixing(), redLoopPc(), reduce_bd34(), reduce_bound(), reduce_boundHop(), reduce_boundHopR(), reduce_boundHopRc(), reduce_boundMw(), reduce_boundPrune(), reduce_chain2(), reduce_check3Tree(), reduce_da(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), reduce_getSd(), reduce_getSdPcMw(), reduce_npv(), reduce_nts(), reduce_nv(), reduce_nvAdv(), reduce_sdPc(), reduce_sdsp(), reduce_sdspSap(), reduce_simple(), reduce_simple_hc(), reduce_simple_pc(), reduce_simple_sap(), reduce_sl(), reduceCheckEdge(), reduceNw(), reduceSap(), SCIP_DECL_HEUREXEC(), SCIPStpDualAscent(), SCIPStpDualAscentPcMw(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurPruneUpdateSols(), SCIPStpHeurTMBuildTree(), SCIPStpHeurTMRun(), SCIPStpHeurTMRunLP(), setRedcosts(), setVnoiDistances(), STPStpBranchruleParseConsname(), updateEdgeFixingBounds(), updateNodeFixingBounds(), and updateNodeReplaceBounds().

◆ BLOCKED

◆ EDGE_BLOCKED

#define EDGE_BLOCKED   0

Definition at line 159 of file grph.h.

Referenced by reduce_ledge(), reduce_sd(), reduce_sdsp(), and reduce_simple().

◆ EDGE_MODIFIABLE

#define EDGE_MODIFIABLE   1

Definition at line 160 of file grph.h.

◆ MST_MODE

◆ FSP_MODE

◆ BSP_MODE

#define BSP_MODE   2

Definition at line 164 of file grph.h.

◆ NO_CHANGE

#define NO_CHANGE   -10

Definition at line 166 of file grph.h.

◆ Is_term

#define Is_term (   a)    ((a) >= 0)

Definition at line 168 of file grph.h.

Referenced by adjterms(), adjust0term(), bea_save(), branchOnVertex(), buildsolgraph(), central_terminal(), compEdges(), computeDegConsTree(), computePertubedSol(), computeSteinerTree(), computeSteinerTreeVnoi(), computeTransVoronoi(), createVariables(), dualascent_init(), dualCostIsValid(), dualcostVarfixing(), findDaRoots(), getcloseterms2term(), getlecloseterms(), getRSD(), graph_copy_data(), graph_get2next(), graph_get3next(), graph_get4next(), graph_get4nextTTerms(), graph_get_NVET(), graph_knot_add(), graph_knot_chg(), graph_knot_contract(), graph_load(), graph_pack(), graph_path_PcMwSd(), graph_path_st(), graph_path_st_pcmw(), graph_path_st_pcmw_extend(), graph_path_st_pcmw_full(), graph_path_st_pcmw_reduce(), graph_path_st_rmw(), graph_path_st_rpc(), graph_pc_2mw(), graph_pc_2org(), graph_pc_2pc(), graph_pc_2rmw(), graph_pc_2rpc(), graph_pc_2trans(), graph_pc_contractEdge(), graph_pc_deleteTerm(), graph_pc_getPosPrizeSum(), graph_pc_getRsap(), graph_pc_getSap(), graph_pc_getSapShift(), graph_pc_knot2nonTerm(), graph_pc_mw2rmw(), graph_pc_term2edgeConsistent(), graph_sdPaths(), graph_sol_reroot(), graph_sol_valid(), graph_termsReachable(), graph_valid(), graph_voronoiExtend(), graph_voronoiMw(), graph_voronoiTerms(), graph_voronoiWithDist(), graph_voronoiWithRadius(), graph_voronoiWithRadiusMw(), initReceivedSubproblem(), is_maxprize(), level0(), level0save(), markPcMwRoots(), nchains(), pertubateEdgeCosts(), reduce_ans(), reduce_ansAdv(), reduce_ansAdv2(), reduce_bd34(), reduce_bdr(), reduce_bound(), reduce_boundHop(), reduce_boundHopR(), reduce_boundHopRc(), reduce_boundMw(), reduce_boundPrune(), reduce_chain2(), reduce_check3Tree(), reduce_cnsAdv(), reduce_da(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), reduce_getSd(), reduce_getSdPcMw(), reduce_ledge(), reduce_npv(), reduce_nts(), reduce_nv(), reduce_nvAdv(), reduce_rpt(), reduce_sd(), reduce_sdPc(), reduce_sdsp(), reduce_simple(), reduce_simple_hc(), reduce_simple_mw(), reduce_simple_pc(), reduce_simple_sap(), reduce_sl(), reduceCheckEdge(), reducePcMw(), reduceSPG(), reduceWithNodeFixingBounds(), ruleOutSubtree(), SCIP_DECL_CONSPROP(), SCIP_DECL_CONSSEPALP(), SCIP_DECL_HEUREXEC(), SCIPprobdataAddNewSol(), SCIPprobdataCreate(), SCIPprobdataWriteSolution(), SCIPprobdataWriteStp(), SCIPStpBranchruleInitNodeState(), SCIPStpDualAscent(), SCIPStpDualAscentPcMw(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRunPcMw(), SCIPStpHeurTMBuildTree(), SCIPStpHeurTMBuildTreeDc(), SCIPStpHeurTMBuildTreePcMw(), SCIPStpHeurTMCompStarts(), SCIPStpHeurTMPrunePc(), SCIPStpHeurTMRun(), SCIPStpHeurTMRunLP(), SCIPwriteStp(), sddeltable(), selectBranchingVertexByDegree(), selectBranchingVertexByLp(), selectBranchingVertexByLp2Flow(), selectBranchingVertexBySol(), selectdiffsols(), sep_2cut(), stp_save(), STPStpBranchruleParseConsname(), traverseChain(), truncateSubtree(), trydg1edgepc(), updateFixingBounds(), and utdist().

◆ Is_pterm

◆ Is_gterm

◆ Edge_anti

◆ VERSION_SCIPJACK

#define VERSION_SCIPJACK   "1.3"

Definition at line 173 of file grph.h.

Referenced by SCIPprobdataCreate().

◆ STP_MAGIC

#define STP_MAGIC   0x33d32945

Definition at line 174 of file grph.h.

Referenced by open_file(), SCIPwriteStp(), and stp_save().

◆ VERSION_MAJOR

#define VERSION_MAJOR   1

Definition at line 175 of file grph.h.

Referenced by open_file(), SCIPwriteStp(), and stp_save().

◆ VERSION_MINOR

#define VERSION_MINOR   0

Definition at line 176 of file grph.h.

Referenced by open_file(), SCIPwriteStp(), and stp_save().

Typedef Documentation

◆ STP_Bool

typedef unsigned char STP_Bool

Definition at line 52 of file grph.h.

◆ PRESOL

typedef struct presolve_info PRESOL

◆ PATH

typedef struct shortest_path PATH

Enumeration Type Documentation

◆ FILETYPE

enum FILETYPE
Enumerator
FF_BEA 
FF_STP 
FF_PRB 
FF_GRD 

Definition at line 178 of file grph.h.

Function Documentation

◆ graph_pc_knot2nonTerm()

void graph_pc_knot2nonTerm ( GRAPH g,
int  node 
)

change property of node to non-terminal

Parameters
gthe graph
nodenode to be changed

Definition at line 909 of file grphbase.c.

References Is_term, NULL, STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, and GRAPH::terms.

Referenced by adjust0term(), graph_pc_deleteTerm(), reduce_simple_pc(), and trydg1edgepc().

◆ graph_pc_updateTerm2edge()

void graph_pc_updateTerm2edge ( GRAPH newgraph,
const GRAPH oldgraph,
int  newtail,
int  newhead,
int  oldtail,
int  oldhead 
)

updates term2edge array for new graph

Parameters
newgraphthe new graph
oldgraphthe old graph
newtailtail in new graph
newheadhead in new graph
oldtailtail in old graph
oldheadhead in old graph

Definition at line 928 of file grphbase.c.

References GRAPH::edges, GRAPH::extended, flipedge, Is_gterm, NULL, GRAPH::source, GRAPH::term, and GRAPH::term2edge.

Referenced by buildsolgraph(), graph_pack(), SCIPStpHeurAscendPruneRun(), and SCIPStpHeurRecExclude().

◆ graph_pc_subtractPrize()

void graph_pc_subtractPrize ( SCIP scip,
GRAPH g,
SCIP_Real  cost,
int  i 
)

subtract a given sum from the prize of a terminal

Parameters
scipSCIP data structure
gthe graph
costcost to be subtracted
ithe terminal

Definition at line 1988 of file grphbase.c.

References GRAPH::cost, EAT_LAST, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pterm, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPisEQ(), SCIPisGE(), GRAPH::source, STP_MWCSP, STP_RMWCSP, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, and GRAPH::term.

Referenced by graph_pc_contractEdge().

◆ graph_pc_chgPrize()

void graph_pc_chgPrize ( SCIP scip,
GRAPH g,
SCIP_Real  newprize,
int  i 
)

change prize of a terminal

Parameters
scipSCIP data structure
gthe graph
newprizeprize to be subtracted
ithe terminal

Definition at line 2031 of file grphbase.c.

References GRAPH::cost, EAT_LAST, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pterm, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPisEQ(), SCIPisGE(), GRAPH::source, STP_MWCSP, STP_RMWCSP, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, and GRAPH::term.

Referenced by STPStpBranchruleParseConsname().

◆ graph_show()

◆ graph_knot_add()

◆ graph_knot_chg()

◆ graph_knot_del()

void graph_knot_del ( SCIP scip,
GRAPH g,
int  k,
SCIP_Bool  freeancestors 
)

delete node

Parameters
scipSCIP data structure
gthe graph
kthe node
freeancestorsfree edge ancestors?

Definition at line 2242 of file grphbase.c.

References EAT_LAST, graph_edge_del(), NULL, and GRAPH::outbeg.

Referenced by graph_knot_delPseudo(), reduceSPG(), reduceWithNodeFixingBounds(), and STPStpBranchruleParseConsname().

◆ graph_knot_contract_dir()

void graph_knot_contract_dir ( GRAPH ,
int  ,
int   
)

◆ graph_get_csr()

void graph_get_csr ( const GRAPH ,
int *  RESTRICT,
int *  RESTRICT,
int *  RESTRICT,
int *   
)

Referenced by SCIPStpDualAscent().

◆ graph_edge_add()

◆ graph_edge_del()

◆ graph_edge_hide()

void graph_edge_hide ( GRAPH g,
int  e 
)

hide edge

Parameters
gthe graph
ethe edge

Definition at line 2887 of file grphbase.c.

References EAT_FREE, EAT_HIDE, GRAPH::grad, GRAPH::head, GRAPH::ieat, NULL, GRAPH::oeat, removeEdge(), and GRAPH::tail.

◆ graph_edge_printInfo()

void graph_edge_printInfo ( SCIP scip,
const GRAPH g,
int  e 
)

print edge info

Parameters
scipSCIP data structure
gthe graph
ethe edge

Definition at line 2931 of file grphbase.c.

References h, GRAPH::head, GRAPH::tail, and GRAPH::term.

◆ graph_uncover()

void graph_uncover ( GRAPH g)

reinsert all hidden edges

Parameters
gthe graph

Definition at line 3937 of file grphbase.c.

References EAT_HIDE, GRAPH::edges, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, NULL, GRAPH::oeat, GRAPH::outbeg, and GRAPH::tail.

◆ graph_trail()

void graph_trail ( const GRAPH g,
int  i 
)

traverse the graph and mark all reached nodes (g->mark[i] has to be FALSE for all i)

Parameters
gthe new graph
inode to start from

Definition at line 4184 of file grphbase.c.

References a, EAT_LAST, GRAPH::grad, GRAPH::head, GRAPH::knots, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL_ABORT, SCIPqueueCreate(), SCIPqueueFree(), SCIPqueueInsert(), SCIPqueueIsEmpty(), SCIPqueueRemove(), and TRUE.

Referenced by graph_valid().

◆ graph_free()

◆ graph_free_history()

void graph_free_history ( SCIP scip,
GRAPH p 
)

free the history

Parameters
scipSCIP data
pgraph data

Definition at line 3736 of file grphbase.c.

References GRAPH::ancestors, GRAPH::edges, NULL, Int_List_Node::parent, SCIPfreeBlockMemory, and SCIPfreeMemoryArray.

Referenced by graph_free(), and redbasedVarfixing().

◆ graph_free_historyDeep()

void graph_free_historyDeep ( SCIP scip,
GRAPH p 
)

free the deep history

Parameters
scipSCIP data
pgraph data

Definition at line 3760 of file grphbase.c.

References GRAPH::fixedges, GRAPH::norgmodelknots, NULL, GRAPH::orghead, GRAPH::orgtail, Int_List_Node::parent, GRAPH::path_heap, GRAPH::path_state, GRAPH::pcancestors, SCIPfreeBlockMemory, and SCIPfreeMemoryArray.

Referenced by graph_free(), and redbasedVarfixing().

◆ graph_get_NVET()

void graph_get_NVET ( const GRAPH graph,
int *  nnodes,
int *  nedges,
int *  nterms 
)

get (real) number of nodes , edges, terminals

Parameters
graphthe graph
nnodesnumber of nodes
nedgesnumber of edges
ntermsnumber of terminals

Definition at line 3382 of file grphbase.c.

References GRAPH::grad, Is_term, GRAPH::knots, NULL, and GRAPH::term.

Referenced by SCIPStpHeurPruneRun(), SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

◆ graph_sol_setNodeList()

void graph_sol_setNodeList ( const GRAPH g,
STP_Bool solnode,
IDX listnode 
)

mark endpoints of edges in given list

Parameters
ggraph data structure
solnodesolution nodes array (TRUE/FALSE)
listnodeedge list

Definition at line 3170 of file grphbase.c.

References GRAPH::head, Int_List_Node::index, NULL, Int_List_Node::parent, GRAPH::tail, and TRUE.

Referenced by graph_sol_getOrg(), and SCIPStpHeurSlackPruneRunPcMw().

◆ graph_pc_2org()

◆ graph_pc_2trans()

void graph_pc_2trans ( GRAPH graph)

◆ graph_pc_2orgcheck()

void graph_pc_2orgcheck ( GRAPH graph)

graph_pc_2org if extended

Parameters
graphthe graph

Definition at line 1028 of file grphbase.c.

References GRAPH::extended, graph_pc_2org(), and NULL.

Referenced by reduce_daPcMw(), reduce_extendedEdge(), and reducePcMw().

◆ graph_pc_2transcheck()

void graph_pc_2transcheck ( GRAPH graph)

graph_pc_2trans if not extended

Parameters
graphthe graph

Definition at line 1041 of file grphbase.c.

References GRAPH::extended, graph_pc_2trans(), and NULL.

Referenced by computePertubedSol(), graph_pc_getRsap(), reduce_da(), SCIPStpHeurLocalExtendPcMw(), and SCIPStpHeurTMRun().

◆ graph_pc_adaptSap()

void graph_pc_adaptSap ( SCIP scip,
SCIP_Real  bigM,
GRAPH graph,
SCIP_Real offset 
)

adapts SAP deriving from PCST or MWCS problem with new big M

Parameters
scipSCIP data structure
bigMnew big M value
graphthe SAP graph
offsetthe offset

Definition at line 1174 of file grphbase.c.

References GRAPH::cost, EAT_LAST, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Real, and GRAPH::source.

◆ graph_pc_presolExit()

void graph_pc_presolExit ( SCIP scip,
GRAPH g 
)

changes graph of PC and MW problems needed after exiting presolving routines

Parameters
scipSCIP data structure
gthe graph

Definition at line 837 of file grphbase.c.

References NULL, GRAPH::rootedgeprevs, SCIPfreeMemoryArray, STP_RPCSPG, and GRAPH::stp_type.

Referenced by graph_pc_getRsap(), graph_pc_getSap(), and redLoopPc().

◆ graph_pc_init()

SCIP_RETCODE graph_pc_init ( SCIP scip,
GRAPH g,
int  sizeprize,
int  sizeterm2edge 
)

allocates (first and second) and initializes (only second) arrays for PC and MW problems

Parameters
scipSCIP data structure
gthe graph
sizeprizesize of prize array to allocate (or -1)
sizeterm2edgesize of term2edge array to allocate and initialize to -1 (or -1)

Definition at line 766 of file grphbase.c.

References NULL, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, and GRAPH::term2edge.

Referenced by buildsolgraph(), graph_load(), graph_pack(), graph_pc_2pc(), graph_pc_2rmw(), graph_pc_2rpc(), graph_pc_getRsap(), SCIPStpHeurAscendPruneRun(), and SCIPStpHeurRecExclude().

◆ graph_pc_2pc()

◆ graph_pc_2rpc()

◆ graph_pc_2mw()

SCIP_RETCODE graph_pc_2mw ( SCIP scip,
GRAPH graph,
SCIP_Real maxweights 
)

alters the graph for MWCS problems

Parameters
scipSCIP data structure
graphthe graph
maxweightsarray containing the weight of each node

Definition at line 1678 of file grphbase.c.

References GRAPH::cost, EAT_LAST, graph_knot_chg(), graph_pc_2pc(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, nterms, NULL, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), STP_MWCSP, GRAPH::stp_type, GRAPH::term, and GRAPH::terms.

Referenced by graph_load().

◆ graph_pc_2rmw()

◆ graph_pc_mw2rmw()

SCIP_RETCODE graph_pc_mw2rmw ( SCIP scip,
GRAPH graph,
SCIP_Real  prizesum 
)

transforms MWCSP to RMWCSP if possible

Parameters
scipSCIP data structure
graphthe graph
prizesumsum of positive prizes

Definition at line 1846 of file grphbase.c.

References GRAPH::cost, EAT_LAST, GRAPH::extended, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_edge_redirect(), graph_knot_chg(), GRAPH::head, Is_pterm, Is_term, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_OKAY, SCIPdebugMessage, SCIPisGE(), SCIPisZero(), GRAPH::source, STP_RMWCSP, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, and TRUE.

Referenced by redLoopMw().

◆ graph_pc_getSap()

SCIP_RETCODE graph_pc_getSap ( SCIP scip,
GRAPH graph,
GRAPH **  newgraph,
SCIP_Real offset 
)

◆ graph_pc_getSapShift()

SCIP_RETCODE graph_pc_getSapShift ( SCIP scip,
GRAPH graph,
GRAPH **  newgraph,
SCIP_Real offset 
)

◆ graph_pc_getRsap()

SCIP_RETCODE graph_pc_getRsap ( SCIP scip,
GRAPH graph,
GRAPH **  newgraph,
int *  rootcands,
int  nrootcands,
int  root 
)

alters the graph for prize-collecting problems with given root

Parameters
scipSCIP data structure
graphthe graph
newgraphthe new graph
rootcandsarray containing all vertices that could be used as root
nrootcandsnumber of all vertices could be used as root
rootthe root of the new SAP

Definition at line 1365 of file grphbase.c.

References GRAPH::cost, EAT_LAST, GRAPH::edges, GRAPH::esize, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_copy(), graph_edge_del(), graph_edge_redirect(), graph_knot_chg(), graph_pc_2transcheck(), graph_pc_init(), graph_pc_presolExit(), graph_pc_presolInit(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::ksize, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, GRAPH::source, STP_SAP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::term2edge, and TRUE.

Referenced by reduce_daPcMw().

◆ graph_pc_contractEdgeAncestors()

SCIP_RETCODE graph_pc_contractEdgeAncestors ( SCIP scip,
GRAPH g,
int  t,
int  s,
int  ets 
)

contract ancestors of an edge of (rooted) prize-collecting Steiner tree problem or maximum-weight connected subgraph problem

Parameters
scipSCIP data structure
gthe graph
ttail node to be contracted (surviving node)
shead node to be contracted
etsedge from t to s or -1

Definition at line 2075 of file grphbase.c.

References GRAPH::ancestors, EAT_LAST, GRAPH::head, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::pcancestors, SCIP_CALL, SCIP_OKAY, and SCIPintListNodeAppendCopy().

Referenced by graph_pc_contractEdge(), and reduce_simple_mw().

◆ graph_pc_contractEdge()

SCIP_RETCODE graph_pc_contractEdge ( SCIP scip,
GRAPH g,
int *  solnode,
int  t,
int  s,
int  i 
)

contract an edge of (rooted) prize-collecting Steiner tree problem or maximum-weight connected subgraph problem

Parameters
scipSCIP data structure
gthe graph
solnodesolution nodes or NULL
ttail node to be contracted (surviving node)
shead node to be contracted
iterminal to add offset to

Definition at line 2101 of file grphbase.c.

References GRAPH::cost, EAT_LAST, GRAPH::grad, graph_edge_del(), graph_knot_chg(), graph_knot_contract(), graph_pc_contractEdgeAncestors(), graph_pc_subtractPrize(), GRAPH::head, GRAPH::inpbeg, Is_pterm, Is_term, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::pcancestors, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisEQ(), GRAPH::source, STP_MWCSP, STP_RMWCSP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::term2edge, and TRUE.

Referenced by reduce_nv(), reduce_nvAdv(), reduce_simple_mw(), reduce_simple_pc(), reduce_sl(), and trydg1edgepc().

◆ graph_resize()

SCIP_RETCODE graph_resize ( SCIP scip,
GRAPH g,
int  ksize,
int  esize,
int  layers 
)

enlarge given graph

Parameters
scipSCIP data structure
ggraph to be resized
ksizenew node slots
esizenew edge slots
layerslayers (set to -1 by default)

Definition at line 3631 of file grphbase.c.

References GRAPH::cost, GRAPH::edges, GRAPH::esize, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, GRAPH::ksize, GRAPH::layers, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPreallocMemoryArray, GRAPH::tail, and GRAPH::term.

Referenced by compEdges(), graph_pc_2pc(), graph_pc_2rmw(), graph_pc_2rpc(), graph_pc_getSap(), and graph_pc_getSapShift().

◆ graph_knot_contract()

SCIP_RETCODE graph_knot_contract ( SCIP scip,
GRAPH p,
int *  solnode,
int  t,
int  s 
)

contract an edge, given by its endpoints

Parameters
scipSCIP data structure
pgraph data structure
solnodenode array to mark whether an node is part of a given solution (CONNECT), or NULL
ttail node to be contracted
shead node to be contracted

Definition at line 2429 of file grphbase.c.

References GRAPH::ancestors, CONNECT, GRAPH::cost, EAT_LAST, Edge_anti, FALSE, GRAPH::grad, graph_edge_del(), graph_knot_chg(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::layers, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPfreeBlockMemoryArray, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), GRAPH::source, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by getlecloseterms(), graph_knot_contractLowdeg2High(), graph_pc_contractEdge(), reduce_contractZeroEdges(), reduce_nv(), reduce_nvAdv(), reduce_rpt(), reduce_simple(), reduce_simple_mw(), reduce_simple_pc(), reduce_simple_sap(), and reduce_sl().

◆ graph_knot_contractLowdeg2High()

SCIP_RETCODE graph_knot_contractLowdeg2High ( SCIP scip,
GRAPH g,
int *  solnode,
int  t,
int  s 
)

contract endpoint of lower degree into endpoint of higher degree

Parameters
scipSCIP data structure
ggraph data structure
solnodenode array to mark whether an node is part of a given solution (CONNECT), or NULL
ttail node to be contracted
shead node to be contracted

Definition at line 2662 of file grphbase.c.

References GRAPH::grad, graph_knot_contract(), NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by reduce_simple().

◆ graph_sol_reroot()

SCIP_RETCODE graph_sol_reroot ( SCIP scip,
GRAPH g,
int *  result,
int  newroot 
)

changes solution according to given root

Parameters
scipSCIP data structure
gthe graph
resultsolution array (CONNECT/UNKNOWN)
newrootthe new root

Definition at line 2943 of file grphbase.c.

References a, CONNECT, EAT_LAST, FALSE, flipedge, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduce_da(), and reduce_daPcMw().

◆ graph_sol_getOrg()

SCIP_RETCODE graph_sol_getOrg ( SCIP scip,
const GRAPH transgraph,
const GRAPH orggraph,
const int *  transsoledge,
int *  orgsoledge 
)

get original solution

Parameters
scipSCIP data structure
transgraphthe transformed graph
orggraphthe original graph
transsoledgesolution for transformed problem
orgsoledgenew retransformed solution

Definition at line 3214 of file grphbase.c.

References GRAPH::ancestors, CONNECT, GRAPH::cost, GRAPH::edges, FALSE, GRAPH::fixedges, graph_pc_isPcMw(), graph_sol_markPcancestors(), graph_sol_setNodeList(), graph_sol_valid(), GRAPH::head, GRAPH::knots, NULL, GRAPH::pcancestors, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPStpHeurTMPrune(), SCIPStpHeurTMPrunePc(), GRAPH::stp_type, GRAPH::tail, TRUE, and UNKNOWN.

Referenced by SCIPStpHeurPruneUpdateSols().

◆ graph_sol_markPcancestors()

SCIP_RETCODE graph_sol_markPcancestors ( SCIP scip,
IDX **  pcancestors,
const int *  tails,
const int *  heads,
int  orgnnodes,
STP_Bool solnodemark,
STP_Bool soledgemark,
int *  solnodequeue,
int *  nsolnodes,
int *  nsoledges 
)

mark original solution

Parameters
scipSCIP data structure
pcancestorsthe ancestors
tailstails array
headsheads array
orgnnodesoriginal number of nodes
solnodemarksolution nodes mark array
soledgemarksolution edges mark array or NULL
solnodequeuesolution nodes queue or NULL
nsolnodesnumber of solution nodes or NULL
nsoledgesnumber of solution edges or NULL

Definition at line 3288 of file grphbase.c.

References nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and TRUE.

Referenced by graph_sol_getOrg(), SCIPprobdataWriteSolution(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), and SCIPStpHeurSlackPruneRunPcMw().

◆ graph_edge_reinsert()

SCIP_RETCODE graph_edge_reinsert ( SCIP scip,
GRAPH g,
int  e1,
int  k1,
int  k2,
SCIP_Real  cost,
IDX ancestors0,
IDX ancestors1,
IDX revancestors0,
IDX revancestors1,
SCIP_Bool  forcedelete 
)

reinsert an edge to replace two other edges

Parameters
scipSCIP data structure
gthe graph
e1edge to reinsert
k1tail
k2head
costedge cost
ancestors0ancestors of first edge
ancestors1ancestors of second edge
revancestors0reverse ancestors of first edge
revancestors1reverse ancestors of first edge
forcedeletedelete edge e1 if it is not used?

Definition at line 2753 of file grphbase.c.

References GRAPH::ancestors, Edge_anti, graph_edge_redirect(), NULL, SCIP_CALL, SCIP_OKAY, SCIPintListNodeAppendCopy(), and SCIPintListNodeFree().

Referenced by graph_knot_delPseudo().

◆ graph_knot_delPseudo()

SCIP_RETCODE graph_knot_delPseudo ( SCIP scip,
GRAPH g,
const SCIP_Real edgecosts,
const SCIP_Real cutoffs,
const SCIP_Real cutoffsrev,
int  vertex,
SCIP_Bool success 
)

pseudo delete node, i.e. reconnect neighbors; maximum degree of 4!

Parameters
scipSCIP data structure
gthe graph
edgecostsedge costs for cutoff
cutoffscutoff values for each incident edge
cutoffsrevrevere cutoff values (or NULL if undirected)
vertexthe vertex
successhas node been pseudo-eliminated?

Definition at line 2258 of file grphbase.c.

References GRAPH::ancestors, GRAPH::cost, cutoffEdge(), EAT_LAST, FALSE, flipedge, GRAPH::grad, graph_edge_reinsert(), graph_knot_del(), GRAPH::head, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), STP_DELPSEUDO_MAXGRAD, STP_DELPSEUDO_MAXNEDGES, GRAPH::tail, and TRUE.

Referenced by reduce_bd34(), reduce_bdr(), reduce_bound(), reduce_boundPrune(), and reduceWithNodeReplaceBounds().

◆ graph_grid_create()

SCIP_RETCODE graph_grid_create ( SCIP scip,
GRAPH **  gridgraph,
int **  coords,
int  nterms,
int  grid_dim,
int  scale_order 
)

creates a graph out of a given grid

Parameters
scipSCIP data structure
gridgraphthe grid graph to be constructed
coordscoordinates
ntermsnumber of terminals
grid_dimproblem dimension
scale_orderscale order

Definition at line 582 of file grphbase.c.

References compEdges(), getNodeNumber(), graph_edge_add(), graph_init(), graph_knot_add(), graph_knot_chg(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, nnodes, nterms, NULL, pow(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPfreeBufferArray, SCIPsortInt(), STP_RSMT, and GRAPH::stp_type.

Referenced by graph_load().

◆ graph_obstgrid_create()

SCIP_RETCODE graph_obstgrid_create ( SCIP scip,
GRAPH **  gridgraph,
int **  coords,
int **  obst_coords,
int  nterms,
int  grid_dim,
int  nobstacles,
int  scale_order 
)

creates a graph out of a given grid

Parameters
scipSCIP data structure
gridgraphthe (obstacle) grid graph to be constructed
coordscoordinates of all points
obst_coordscoordinates of obstacles
ntermsnumber of terminals
grid_dimdimension of the problem
nobstaclesnumber of obstacles
scale_orderscale factor

Definition at line 419 of file grphbase.c.

References compEdgesObst(), FALSE, getNodeNumber(), graph_edge_add(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_pack(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, nnodes, nterms, NULL, pow(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPfreeBufferArray, SCIPsortInt(), GRAPH::source, STP_OARSMT, GRAPH::stp_type, and TRUE.

Referenced by graph_load().

◆ graph_grid_coordinates()

SCIP_RETCODE graph_grid_coordinates ( SCIP scip,
int **  coords,
int **  nodecoords,
int *  ncoords,
int  node,
int  grid_dim 
)

computes coordinates of node 'node'

Parameters
scipSCIP data structure
coordscoordinates
nodecoordscoordinates of the node (to be computed)
ncoordsarray with number of coordinate
nodethe node
grid_dimproblem dimension

Definition at line 730 of file grphbase.c.

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.

Referenced by SCIPprobdataWriteSolution().

◆ graph_copy_data()

◆ graph_copy()

SCIP_RETCODE graph_copy ( SCIP scip,
const GRAPH orgraph,
GRAPH **  copygraph 
)

◆ graph_pack()

◆ graph_trail_arr()

SCIP_RETCODE graph_trail_arr ( SCIP scip,
const GRAPH g,
int  i 
)

traverse the graph and mark all reached nodes (g->mark[i] has to be FALSE for all i) .... uses an array and should be faster than graph_trail, but needs a scip

Parameters
scipscip struct
gthe new graph
inode to start from

Definition at line 4238 of file grphbase.c.

References a, EAT_LAST, GRAPH::grad, GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and TRUE.

Referenced by graph_termsReachable(), level0(), and level0save().

◆ graph_get_edgeConflicts()

SCIP_RETCODE graph_get_edgeConflicts ( SCIP ,
const GRAPH  
)

◆ graph_init()

SCIP_RETCODE graph_init ( SCIP scip,
GRAPH **  g,
int  ksize,
int  esize,
int  layers 
)

initialize graph

Parameters
scipSCIP data structure
gnew graph
ksizeslots for nodes
esizeslots for edges
layersnumber of layers (only needed for packing, otherwise 1)

Definition at line 3491 of file grphbase.c.

References GRAPH::ancestors, GRAPH::cost, GRAPH::edges, GRAPH::esize, GRAPH::extended, FALSE, GRAPH::fixedges, GRAPH::grad, GRAPH::grid_coordinates, GRAPH::grid_ncoords, GRAPH::head, GRAPH::hoplimit, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, GRAPH::ksize, GRAPH::layers, GRAPH::mark, GRAPH::maxdeg, GRAPH::mincut_dist, GRAPH::mincut_e, GRAPH::mincut_head, GRAPH::mincut_next, GRAPH::mincut_numb, GRAPH::mincut_prev, GRAPH::mincut_r, GRAPH::mincut_temp, GRAPH::mincut_x, GRAPH::norgmodeledges, GRAPH::norgmodelknots, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::orghead, GRAPH::orgknots, GRAPH::orgsource, GRAPH::orgtail, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::pcancestors, GRAPH::prize, GRAPH::rootedgeprevs, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, SCIPdebugMessage, GRAPH::source, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::term2edge, GRAPH::terms, and UNKNOWN.

Referenced by buildsolgraph(), graph_copy(), graph_grid_create(), graph_load(), graph_obstgrid_create(), graph_pack(), reduce_bd34(), reduce_bdr(), reduce_bound(), reduce_boundHop(), reduce_boundPrune(), reduce_ledge(), reduce_npv(), reduce_nts(), reduce_sd(), reduce_sdPc(), SCIPprobdataWriteSolution(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), and SCIPStpHeurRecExclude().

◆ graph_init_history()

◆ graph_termsReachable()

SCIP_RETCODE graph_termsReachable ( SCIP scip,
const GRAPH g,
SCIP_Bool reachable 
)

checks whether all terminals are reachable from root

Parameters
scipscip struct
gthe new graph
reachableare they reachable?

Definition at line 4295 of file grphbase.c.

References FALSE, graph_trail_arr(), Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, SCIP_OKAY, GRAPH::source, GRAPH::term, and TRUE.

◆ graph_pc_presolInit()

SCIP_RETCODE graph_pc_presolInit ( SCIP scip,
GRAPH g 
)

changes graph of PC and MW problems needed for presolving routines

Parameters
scipSCIP data structure
gthe graph

Definition at line 794 of file grphbase.c.

References EAT_LAST, GRAPH::edges, GRAPH::grad, GRAPH::ieat, GRAPH::inpbeg, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::rootedgeprevs, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, GRAPH::source, STP_RPCSPG, and GRAPH::stp_type.

Referenced by graph_pc_getRsap(), graph_pc_getSap(), and redLoopPc().

◆ graph_edge_redirect()

◆ graph_pc_deleteTerm()

int graph_pc_deleteTerm ( SCIP scip,
GRAPH g,
int  i 
)

delete a terminal for a (rooted) prize-collecting problem

Parameters
scipSCIP data structure
ggraph data structure
iindex of the terminal

Definition at line 1941 of file grphbase.c.

References EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), graph_pc_knot2nonTerm(), GRAPH::head, Is_pterm, Is_term, GRAPH::mark, NULL, GRAPH::outbeg, GRAPH::source, GRAPH::term, GRAPH::term2edge, TRUE, and UNKNOWN.

Referenced by reduce_bound(), reduce_simple_mw(), reduce_simple_pc(), reduceSPG(), STPStpBranchruleParseConsname(), and trydg1edgepc().

◆ graph_valid()

◆ graph_pc_term2edgeConsistent()

SCIP_Bool graph_pc_term2edgeConsistent ( const GRAPH g)

checks consistency of term2edge array ONLY for non-extended graphs!

Parameters
gthe graph

Definition at line 853 of file grphbase.c.

References EAT_LAST, GRAPH::extended, FALSE, flipedge, GRAPH::head, Is_gterm, Is_pterm, Is_term, GRAPH::knots, NULL, GRAPH::oeat, GRAPH::outbeg, SCIPdebugMessage, GRAPH::source, GRAPH::term, GRAPH::term2edge, and TRUE.

Referenced by redLoopMw(), redLoopPc(), and SCIPStpHeurRecRun().

◆ graph_sol_unreduced()

SCIP_Bool graph_sol_unreduced ( SCIP scip,
const GRAPH graph,
const int *  result 
)

checks whether edge(s) of given primal solution have been deleted

Parameters
scipSCIP data structure
graphgraph data structure
resultsolution array, indicating whether an edge is in the solution

Definition at line 3046 of file grphbase.c.

References CONNECT, EAT_FREE, GRAPH::edges, FALSE, NULL, GRAPH::oeat, and TRUE.

Referenced by reduce_daPcMw(), and reducePcMwTryBest().

◆ graph_sol_valid()

◆ graph_pc_isPcMw()

SCIP_Bool graph_pc_isPcMw ( const GRAPH g)

is this graph a prize-collecting or maximum-weight variant?

Parameters
gthe graph

Definition at line 2184 of file grphbase.c.

References NULL, STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, and GRAPH::stp_type.

Referenced by graph_init_history(), graph_sol_getOrg(), selectBranchingVertexByDegree(), and selectBranchingVertexBySol().

◆ graph_sol_getObj()

SCIP_Real graph_sol_getObj ( const SCIP_Real edgecost,
const int *  soledge,
SCIP_Real  offset,
int  nedges 
)

◆ graph_pc_getPosPrizeSum()

SCIP_Real graph_pc_getPosPrizeSum ( SCIP ,
const GRAPH  
)

Definition at line 1054 of file grphbase.c.

References BLOCKED, GRAPH::extended, Is_term, GRAPH::knots, NULL, GRAPH::prize, SCIP_Real, GRAPH::source, and GRAPH::term.

Referenced by redLoopMw(), and redLoopPc().

◆ graph_path_exit()

◆ graph_path_exec()

◆ graph_path_execX()

void graph_path_execX ( SCIP scip,
const GRAPH g,
int  start,
const SCIP_Real cost,
SCIP_Real pathdist,
int *  pathedge 
)

Dijkstra's algorithm starting from node 'start'

Parameters
scipSCIP data structure
ggraph data structure
startstart vertex
costedge costs
pathdistdistance array (on vertices)
pathedgepredecessor edge array (on vertices)

Definition at line 781 of file grphpath.c.

References CONNECT, correctX(), EAT_LAST, FARAWAY, GRAPH::head, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIPisGT(), and UNKNOWN.

Referenced by computeTransVoronoi(), reduce_boundHopR(), reduce_boundHopRc(), reduce_da(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), reduce_rpt(), SCIPStpHeurTMRun(), and setVnoiDistances().

◆ graph_path_invroot()

void graph_path_invroot ( SCIP scip,
const GRAPH g,
int  start,
const SCIP_Real cost,
SCIP_Real pathdist,
int *  pathedge 
)

Dijkstra on incoming edges until root is reached

Parameters
scipSCIP data structure
ggraph data structure
startstart vertex
costedge costs
pathdistdistance array (on vertices)
pathedgepredecessor edge array (on vertices)

Definition at line 849 of file grphpath.c.

References CONNECT, correctX(), EAT_LAST, FARAWAY, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, NULL, GRAPH::path_heap, GRAPH::path_state, SCIP_Real, SCIPisGT(), GRAPH::source, GRAPH::tail, and UNKNOWN.

◆ graph_path_st()

void graph_path_st ( SCIP scip,
const GRAPH g,
SCIP_Real cost,
SCIP_Real pathdist,
int *  pathedge,
int  start,
SCIP_RANDNUMGEN randnumgen,
STP_Bool connected 
)

Find a directed tree rooted in node 'start' and spanning all terminals

Parameters
scipSCIP data structure
ggraph data structure
costedgecosts
pathdistdistance array (on vertices)
pathedgepredecessor edge array (on vertices)
startstart vertex
randnumgenrandom number generator
connectedarray to mark whether a vertex is part of computed Steiner tree

Definition at line 926 of file grphpath.c.

References correctX(), EAT_LAST, FALSE, FARAWAY, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, resetX(), GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by computeSteinerTreeDijk().

◆ graph_path_st_rmw()

void graph_path_st_rmw ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
SCIP_Real pathdist,
int *  pathedge,
int  start,
STP_Bool connected 
)

Shortest path heuristic for the RMWCSP Find a directed tree rooted in node 'start' and connecting all terminals as well as all positive vertices (as long as this is profitable).

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
pathdistdistance array (on vertices)
pathedgepredecessor edge array (on vertices)
startstart vertex
connectedarray to mark whether a vertex is part of computed Steiner tree

Definition at line 1536 of file grphpath.c.

References correctX(), GRAPH::cost, EAT_LAST, FALSE, FARAWAY, GRAPH::grad, GRAPH::head, Is_gterm, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::prize, resetX(), SCIP_Real, SCIPisGE(), SCIPisGT(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by computeSteinerTreeDijkPcMw().

◆ graph_path_st_pcmw()

void graph_path_st_pcmw ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
SCIP_Real pathdist,
int *  pathedge,
int  start,
STP_Bool connected 
)

Find a tree rooted in node 'start' and connecting positive vertices as long as this is profitable. Note that this function overwrites g->mark.

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
pathdistdistance array (on vertices)
pathedgepredecessor edge array (on vertices)
startstart vertex
connectedarray to mark whether a vertex is part of computed Steiner tree

Definition at line 1154 of file grphpath.c.

References correctX(), EAT_LAST, FALSE, FARAWAY, GRAPH::grad, GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::prize, resetX(), SCIP_Real, SCIPisGT(), GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by computeSteinerTreeDijkPcMw().

◆ graph_path_st_pcmw_full()

void graph_path_st_pcmw_full ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
SCIP_Real pathdist,
int *  pathedge,
int  start,
STP_Bool connected 
)

Find a tree rooted in node 'start' and connecting all positive vertices. Note that this function overwrites g->mark.

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
pathdistdistance array (on vertices)
pathedgepredecessor edge array (on vertices)
startstart vertex
connectedarray to mark whether a vertex is part of computed Steiner tree

Definition at line 1316 of file grphpath.c.

References correctX(), EAT_LAST, FALSE, FARAWAY, GRAPH::grad, GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, resetX(), SCIPisGT(), GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by computeSteinerTreeDijkPcMwFull().

◆ graph_path_st_pcmw_reduce()

void graph_path_st_pcmw_reduce ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
SCIP_Real tmpnodeweight,
int *  result,
int  start,
STP_Bool connected 
)

Reduce given solution Note that this function overwrites g->mark.

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
tmpnodeweightnode weight array
resultincoming arc array
startstart vertex
connectedarray to mark whether a vertex is part of computed Steiner tree

Definition at line 1264 of file grphpath.c.

References CONNECT, EAT_LAST, FALSE, GRAPH::head, Is_term, NULL, GRAPH::oeat, GRAPH::outbeg, SCIPfreeBufferArray, SCIPisGE(), GRAPH::term, and UNKNOWN.

◆ graph_path_st_pcmw_extend()

void graph_path_st_pcmw_extend ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
PATH path,
STP_Bool connected,
SCIP_Bool extensions 
)

greedy extension of a given tree for PC or MW problems

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
pathshortest paths data structure
connectedarray to mark whether a vertex is part of computed Steiner tree
extensionsextensions performed?

Definition at line 1410 of file grphpath.c.

References correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FALSE, FARAWAY, FSP_MODE, GRAPH::grad, GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nearest(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::prize, reset(), SCIP_Real, SCIPisGE(), SCIPisGT(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by SCIPStpHeurLocalExtendPcMw().

◆ graph_path_st_rpc()

void graph_path_st_rpc ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
SCIP_Real pathdist,
int *  pathedge,
int  start,
STP_Bool connected 
)

For rooted prize-collecting problem find a tree rooted in node 'start' and connecting positive vertices as long as this is profitable. Note that this function overwrites g->mark.

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
pathdistdistance array (on vertices)
pathedgepredecessor edge array (on vertices)
startstart vertex
connectedarray to mark whether a vertex is part of computed Steiner tree

Definition at line 1033 of file grphpath.c.

References correctX(), EAT_LAST, FALSE, FARAWAY, GRAPH::grad, GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::prize, resetX(), SCIP_Real, SCIPisGE(), SCIPisGT(), GRAPH::source, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by computeSteinerTreeDijkPcMw().

◆ graph_voronoi()

void graph_voronoi ( SCIP scip,
const GRAPH g,
SCIP_Real cost,
SCIP_Real costrev,
STP_Bool base,
int *  vbase,
PATH path 
)

build a voronoi region, w.r.t. shortest paths, for a given set of bases

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
costrevreversed edge costs
basearray to indicate whether a vertex is a Voronoi base
vbasevoronoi base to each vertex
pathpath data struture (leading to respective Voronoi base)

Definition at line 1751 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, GRAPH::knots, nearest(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIPisGT(), GRAPH::source, and UNKNOWN.

Referenced by computeSteinerTreeVnoi(), and SCIPStpHeurLocalRun().

◆ graph_get2next()

void graph_get2next ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
const SCIP_Real costrev,
PATH path,
int *  vbase,
int *  heap,
int *  state 
)

2th next terminal to all non terminal nodes

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
costrevreversed edge costs
pathpath data structure (leading to first and second nearest terminal)
vbasefirst and second nearest terminal to each non terminal
heaparray representing a heap
statearray to mark the state of each node during calculation

Definition at line 1838 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIPisGT(), GRAPH::source, GRAPH::term, and UNKNOWN.

Referenced by graph_get3nextTerms(), graph_get4nextTerms(), reduce_bound(), reduce_boundHop(), reduce_boundMw(), reduce_boundPrune(), and reduce_daPcMw().

◆ graph_get3next()

void graph_get3next ( SCIP ,
const GRAPH ,
const SCIP_Real ,
const SCIP_Real ,
PATH ,
int *  ,
int *  ,
int *   
)

◆ graph_get4next()

void graph_get4next ( SCIP ,
const GRAPH ,
const SCIP_Real ,
const SCIP_Real ,
PATH ,
int *  ,
int *  ,
int *   
)

◆ graph_get3nextTerms()

void graph_get3nextTerms ( SCIP scip,
const GRAPH g,
SCIP_Real cost,
SCIP_Real costrev,
PATH path3,
int *  vbase,
int *  heap,
int *  state 
)

build a voronoi region in presolving, w.r.t. shortest paths, for all terminals

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
costrevreversed edge costs
path3path data struture (leading to first, second and third nearest terminal)
vbasefirst, second and third nearest terminal to each non terminal
heaparray representing a heap
statearray to mark the state of each node during calculation

Definition at line 2150 of file grphpath.c.

References GRAPH::grad, graph_get2next(), graph_get3next(), graph_voronoiTerms(), GRAPH::knots, GRAPH::mark, NULL, STP_PCSPG, STP_RPCSPG, and GRAPH::stp_type.

◆ graph_get4nextTerms()

void graph_get4nextTerms ( SCIP scip,
const GRAPH g,
SCIP_Real cost,
SCIP_Real costrev,
PATH path,
int *  vbase,
int *  heap,
int *  state 
)

build a voronoi region in presolving, w.r.t. shortest paths, for all terminals

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
costrevreversed edge costs
pathpath data struture (leading to first, second, third and fouth nearest terminal)
vbasefirst, second and third nearest terminal to each non terminal
heaparray representing a heap
statearray to mark the state of each node during calculation

Definition at line 2186 of file grphpath.c.

References GRAPH::grad, graph_get2next(), graph_get3next(), graph_get4next(), graph_voronoiTerms(), GRAPH::knots, GRAPH::mark, NULL, STP_PCSPG, STP_RPCSPG, and GRAPH::stp_type.

Referenced by reduce_da(), reduce_daSlackPrune(), reduce_sd(), and reduce_sdPc().

◆ graph_voronoiMw()

void graph_voronoiMw ( SCIP scip,
const GRAPH g,
const SCIP_Real costrev,
PATH path,
int *  vbase,
int *  heap,
int *  state 
)

build a Voronoi region, w.r.t. shortest paths, for all positive vertices

Parameters
scipSCIP data structure
ggraph data structure
costrevreversed edge costs
pathpath data structure (leading to respective Voronoi base)
vbaseVoronoi base to each vertex
heaparray representing a heap
statearray to mark the state of each node during calculation

Definition at line 2383 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPisGT(), GRAPH::term, and UNKNOWN.

Referenced by reduce_boundMw(), and reduce_boundPrune().

◆ graph_voronoiTerms()

void graph_voronoiTerms ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
PATH path,
int *  vbase,
int *  heap,
int *  state 
)

build a Voronoi region in presolving, w.r.t. shortest paths, for all terminals

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
pathpath data structure (leading to respective Voronoi base)
vbaseVoronoi base to each vertex
heaparray representing a heap
statearray to mark the state of each node during calculation

Definition at line 2307 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), NULL, GRAPH::oeat, GRAPH::outbeg, SCIPisGT(), GRAPH::term, and UNKNOWN.

Referenced by computeTransVoronoi(), graph_get3nextTerms(), graph_get4nextTerms(), reduce_boundHopR(), reduce_boundHopRc(), reduce_da(), reduce_daPcMw(), reduce_daSlackPruneMw(), reduce_ledge(), reduce_sl(), and setVnoiDistances().

◆ voronoi_inout()

void voronoi_inout ( const GRAPH )

◆ voronoi_term()

void voronoi_term ( const GRAPH ,
double *  ,
double *  ,
double *  ,
PATH ,
int *  ,
int *  ,
int *  ,
int *  ,
int   
)

Referenced by getlecloseterms().

◆ heap_add()

void heap_add ( int *  ,
int *  ,
int *  ,
int  ,
PATH  
)

Definition at line 244 of file grphpath.c.

References GT.

Referenced by computeSteinerTreeVnoi(), and SCIPStpHeurLocalRun().

◆ graph_voronoiRepair()

void graph_voronoiRepair ( SCIP scip,
const GRAPH g,
SCIP_Real cost,
int *  count,
int *  vbase,
PATH path,
int *  newedge,
int  crucnode,
UF uf 
)

repair a Voronoi diagram for a given set of base nodes

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
countpointer to number of heap elements
vbasearray containing Voronoi base of each node
pathVoronoi paths data struture
newedgethe new edge
crucnodethe current crucial node
ufunion find data structure

Definition at line 2979 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, FSP_MODE, GRAPH::head, GRAPH::knots, GRAPH::mark, nearest(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIPisGT(), SCIPStpunionfindFind(), GRAPH::tail, and UNKNOWN.

Referenced by SCIPStpHeurLocalRun().

◆ graph_voronoiRepairMult()

void graph_voronoiRepairMult ( SCIP scip,
const GRAPH g,
SCIP_Real cost,
int *  count,
int *  vbase,
int *  boundedges,
int *  nboundedges,
STP_Bool nodesmark,
UF uf,
PATH path 
)

repair the Voronoi diagram for a given set nodes

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
countpointer to number of heap elements
vbasearray containing Voronoi base of each node
boundedgesboundary edges
nboundedgesnumber of boundary edges
nodesmarkarray to mark temporarily discarded nodes
ufunion find data structure
pathVoronoi paths data structure

Definition at line 3057 of file grphpath.c.

References CONNECT, correct(), EAT_LAST, FSP_MODE, GRAPH::head, GRAPH::knots, GRAPH::mark, nearest(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIPisGT(), and SCIPStpunionfindFind().

Referenced by SCIPStpHeurLocalRun().

◆ voronoiSteinerTreeExt()

void voronoiSteinerTreeExt ( SCIP ,
const GRAPH ,
SCIP_Real ,
int *  ,
STP_Bool ,
PATH  
)

◆ graph_sdPaths()

void graph_sdPaths ( SCIP scip,
const GRAPH g,
PATH path,
SCIP_Real cost,
SCIP_Real  distlimit,
int *  heap,
int *  state,
int *  memlbl,
int *  nlbl,
int  tail,
int  head,
int  limit 
)

limited Dijkstra, stopping at terminals

Parameters
scipSCIP data structure
ggraph data structure
pathshortest paths data structure
costedge costs
distlimitdistance limit of the search
heaparray representing a heap
statearray to indicate whether a node has been scanned during SP calculation
memlblarray to save labelled nodes
nlblnumber of labelled nodes
tailtail of the edge
headhead of the edge
limitmaximum number of edges to consider during execution

Definition at line 567 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, FALSE, FSP_MODE, GRAPH::grad, GRAPH::head, Is_term, GRAPH::mark, nearest(), NULL, GRAPH::oeat, GRAPH::outbeg, SCIPisGT(), STP_MWCSP, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by findDaRoots(), reduce_getSd(), reduce_sdsp(), and reduce_sdspSap().

◆ graph_path_PcMwSd()

void graph_path_PcMwSd ( SCIP scip,
const GRAPH g,
PATH path,
SCIP_Real cost,
SCIP_Real  distlimit,
int *  pathmaxnode,
int *  heap,
int *  state,
int *  stateblock,
int *  memlbl,
int *  nlbl,
int  tail,
int  head,
int  limit 
)

limited Dijkstra for PCSTP, taking terminals into account

Parameters
scipSCIP data structure
ggraph data structure
pathshortest paths data structure
costedge costs
distlimitdistance limit of the search
pathmaxnodemaximum weight node on path
heaparray representing a heap
statearray to indicate whether a node has been scanned during SP calculation
stateblockarray to indicate whether a node has been scanned during previous SP calculation
memlblarray to save labelled nodes
nlblnumber of labelled nodes
tailtail of the edge
headhead of the edge
limitmaximum number of edges to consider during execution

Definition at line 664 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, FALSE, FSP_MODE, GRAPH::grad, GRAPH::head, Is_term, GRAPH::mark, nearest(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_Real, SCIPisGT(), SCIPisLE(), STP_MWCSP, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduce_getSdPcMw(), and reduce_sdsp().

◆ graph_voronoiWithRadiusMw()

void graph_voronoiWithRadiusMw ( SCIP scip,
const GRAPH g,
PATH path,
const SCIP_Real cost,
SCIP_Real radius,
int *  vbase,
int *  heap,
int *  state 
)

Build partition of graph for MWCSP into regions around the positive vertices. Store the weight of a minimum weight center-boundary path for each region in the radius array (has to be reverted to obtain the final r() value).

Parameters
scipSCIP data structure
ggraph data structure
patharray containing graph decomposition data
costedge costs
radiusarray storing shortest way from a positive vertex out of its region
vbasearray containing base of each node
heaparray representing a heap
statearray to mark state of each node during calculation

Definition at line 2852 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Real, SCIPisGE(), SCIPisGT(), SCIPisLT(), GRAPH::source, GRAPH::term, GRAPH::terms, and UNKNOWN.

Referenced by reduce_boundMw().

◆ graph_voronoiExtend()

SCIP_RETCODE graph_voronoiExtend ( SCIP scip,
const GRAPH g,
SCIP_Real cost,
PATH path,
SCIP_Real **  distarr,
int **  basearr,
int **  edgearr,
STP_Bool termsmark,
int *  reachednodes,
int *  nreachednodes,
int *  nodenterms,
int  nneighbterms,
int  base,
int  countex 
)

extend a voronoi region until all neighbouring terminals are spanned

Parameters
scipSCIP data structure
ggraph data structure
costedgecosts
pathshortest paths data structure
distarrarray to store distance from each node to its base
basearrarray to store the bases
edgearrarray to store the ancestor edge
termsmarkarray to mark terminal
reachednodesarray to mark reached nodes
nreachednodespointer to number of reached nodes
nodentermsarray to store number of terimals to each node
nneighbtermsnumber of neighbouring terminals
basevoronoi base
countexcount of heap elements

Definition at line 1671 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FALSE, FSP_MODE, GT, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIP_OKAY, GRAPH::term, and TRUE.

Referenced by computeSteinerTreeVnoi().

◆ graph_path_init()

◆ graph_voronoiWithDist()

SCIP_RETCODE graph_voronoiWithDist ( SCIP ,
const GRAPH ,
SCIP_Real ,
double *  ,
int *  ,
int *  ,
int *  ,
int *  ,
int *  ,
int *  ,
PATH  
)

Referenced by reduce_nv(), and reduce_nvAdv().

◆ graph_voronoiWithRadius()

SCIP_RETCODE graph_voronoiWithRadius ( SCIP scip,
const GRAPH graph,
GRAPH adjgraph,
PATH path,
SCIP_Real rad,
SCIP_Real cost,
SCIP_Real costrev,
int *  vbase,
int *  heap,
int *  state 
)

build voronoi regions, w.r.t. shortest paths, for all terminals and compute the radii

Parameters
scipSCIP data structure
graphgraph data structure
adjgraphgraph data structure
patharray containing Voronoi paths data
radarray storing shortest way from a terminal out of its Voronoi region
costedge costs
costrevreversed edge costs
vbasearray containing Voronoi base of each node
heaparray representing a heap
statearray to mark state of each node during calculation

Definition at line 2614 of file grphpath.c.

References CONNECT, correct(), GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, Edge_anti, FARAWAY, FSP_MODE, graph_edge_add(), graph_knot_add(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), SCIPisLT(), GRAPH::source, STP_DHCSTP, STP_MWCSP, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by reduce_bound(), reduce_boundHop(), and reduce_boundPrune().

◆ graph_get4nextTTerms()

SCIP_RETCODE graph_get4nextTTerms ( SCIP scip,
const GRAPH g,
SCIP_Real cost,
PATH path,
int *  vbase,
int *  heap,
int *  state 
)

get 4 close terminals to each terminal

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
pathpath data structure (leading to first, second, third and fourth nearest terminal)
vbasefirst, second and third nearest terminal to each non terminal
heaparray representing a heap
statearray to mark the state of each node during calculation

Definition at line 2227 of file grphpath.c.

References shortest_path::dist, EAT_LAST, GRAPH::edges, FARAWAY, GRAPH::grad, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, UNKNOWN, and utdist().

Referenced by reduce_bound(), and reduce_sdPc().

◆ graph_mincut_exit()

void graph_mincut_exit ( SCIP scip,
GRAPH p 
)

◆ 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   
)

Referenced by sep_2cut().

◆ graph_mincut_init()

◆ graph_load()

SCIP_RETCODE graph_load ( SCIP ,
GRAPH **  ,
const char *  ,
PRESOL  
)

Definition at line 821 of file grphload.c.

References GRAPH::cost, DIRSEP, EAT_LAST, GRAPH::edges, EXTSEP, FAILURE, FALSE, FARAWAY, current_file::filename, presolve_info::fixed, section::flag, FLAG_REQUIRED, key::format, current_file::fp, get_arguments(), GRAPH::grad, graph_edge_add(), graph_grid_create(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_obstgrid_create(), graph_pc_2mw(), graph_pc_2pc(), graph_pc_2rmw(), graph_pc_2rpc(), graph_pc_init(), graph_valid(), GRAPH::hoplimit, GRAPH::ieat, init_coordinates(), GRAPH::inpbeg, Is_term, KEY_COMMENT_CREATOR, KEY_COMMENT_DATE, KEY_COMMENT_NAME, KEY_COMMENT_PROBLEM, KEY_COMMENT_REMARK, KEY_COORDINATES_DD, KEY_COORDINATES_DDD, KEY_COORDINATES_DDDD, KEY_COORDINATES_DDDDD, KEY_COORDINATES_DDDDDD, KEY_COORDINATES_DDDDDDD, KEY_COORDINATES_DDDDDDDD, KEY_COORDINATES_END, KEY_COORDINATES_GRID, KEY_END, KEY_EOF, KEY_GRAPH_A, KEY_GRAPH_AA, KEY_GRAPH_E, KEY_GRAPH_EDGES, KEY_GRAPH_HOPLIMIT, KEY_GRAPH_NODES, KEY_GRAPH_OBSTACLES, KEY_MAXDEGS_MD, KEY_NODEWEIGHTS_END, KEY_NODEWEIGHTS_NW, KEY_OBSTACLES_END, KEY_OBSTACLES_RR, KEY_PRESOLVE_DATE, KEY_PRESOLVE_EA, KEY_PRESOLVE_EC, KEY_PRESOLVE_ED, KEY_PRESOLVE_ES, KEY_PRESOLVE_FIXED, KEY_PRESOLVE_LOWER, KEY_PRESOLVE_TIME, KEY_PRESOLVE_UPPER, KEY_SECTION, KEY_TERMINALS_END, KEY_TERMINALS_GROUPS, KEY_TERMINALS_ROOT, KEY_TERMINALS_ROOTP, KEY_TERMINALS_T, KEY_TERMINALS_TERMINALS, KEY_TERMINALS_TG, KEY_TERMINALS_TP, KEY_TERMINALS_TR, KEY_TREE_S, key::keyword, GRAPH::knots, current_file::line, presolve_info::lower, section::mark, MAX_ARGUMENTS, MAX_KEYWORD_LEN, MAX_LINE_LEN, MAX_PATH_LEN, GRAPH::maxdeg, message(), MSG_DEBUG, MSG_ERROR, MSG_FATAL, MSG_INFO, parameter::n, section::name, NULL, open_file(), GRAPH::prize, scale_coords(), SCIP_CALL, SCIP_OKAY, SCIP_READERROR, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPfreeBufferArrayNull, SCIPfreeMemoryArrayNull, SCIPisGT(), current_file::section, SECTION_EXISTEND, SECTION_MISSING, GRAPH::source, start_section(), STP_DCSTP, STP_DHCSTP, STP_GSTP, STP_MWCSP, STP_NWSPG, STP_OARSMT, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_RSMT, STP_SAP, STP_SPG, GRAPH::stp_type, SUCCESS, key::sw_code, GRAPH::tail, GRAPH::term, GRAPH::terms, presolve_info::time, TRUE, UNKNOWN, and presolve_info::upper.

Referenced by SCIPprobdataCreate().

◆ graph_save()

void graph_save ( const GRAPH ,
const char *  ,
FILETYPE   
)

Definition at line 309 of file grphsave.c.

References bea_save(), FALSE, FF_BEA, FF_GRD, FF_PRB, FF_STP, graph_valid(), NULL, and stp_save().

◆ SCIPwriteStp()

◆ level0()

◆ level0save()

◆ reduceStp()

SCIP_RETCODE reduceStp ( SCIP scip,
GRAPH **  graph,
SCIP_Real fixed,
int  minelims,
SCIP_Bool  dualascent,
SCIP_Bool  nodereplacing,
SCIP_Bool  userec 
)

basic reduction package for the STP

Parameters
scipSCIP data structure
graphgraph data structure
fixedpointer to store the offset value
minelimsminimal number of edges to be eliminated in order to reiterate reductions
dualascentperform dual-ascent reductions?
nodereplacingshould node replacement (by edges) be performed?
userecuse recombination heuristic?

Definition at line 223 of file reduce.c.

References GRAPH::edges, FALSE, GRAPH::knots, MAX, nnodes, nterms, NULL, redLoopStp(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBlockMemory, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisLE(), GRAPH::terms, and TRUE.

Referenced by redbasedVarfixing(), and reduce().

◆ redLoopStp()

SCIP_RETCODE redLoopStp ( SCIP scip,
GRAPH g,
PATH vnoi,
PATH path,
GNODE **  gnodearr,
SCIP_Real nodearrreal,
SCIP_Real edgearrreal,
SCIP_Real edgearrreal2,
int *  heap,
int *  state,
int *  vbase,
int *  nodearrint,
int *  edgearrint,
int *  nodearrint2,
int *  solnode,
STP_Bool nodearrchar,
SCIP_Real fixed,
SCIP_Real  upperbound,
SCIP_Bool  dualascent,
SCIP_Bool  boundreduce,
SCIP_Bool  nodereplacing,
int  reductbound,
SCIP_Bool  userec,
SCIP_Bool  fullreduce 
)

STP loop

Parameters
scipSCIP data structure
ggraph data structure
vnoiVoronoi data structure
pathpath data structure
gnodearrnodes-sized array
nodearrrealnodes-sized array
edgearrrealedges-sized array
edgearrreal2edges-sized array
heapheap array
stateshortest path array
vbaseVoronoi base array
nodearrintedges-sized array
edgearrintnodes-sized array
nodearrint2nodes-sized array
solnodesolution nodes array (or NULL)
nodearrcharnodes-sized array
fixedpointer to store the offset value
upperboundupper bound
dualascentdo dual-ascent reduction?
boundreducedo bound-based reduction?
nodereplacingshould node replacement (by edges) be performed?
reductboundminimal number of edges to be eliminated in order to reiterate reductions
userecuse recombination heuristic?
fullreduceuse full reductions? (including extended techniques)

Definition at line 1409 of file reduce.c.

References FALSE, graph_valid(), level0(), NULL, nvreduce_sl(), reduce_bd34(), reduce_bound(), reduce_contractZeroEdges(), reduce_da(), reduce_deleteConflictEdges(), reduce_ledge(), reduce_sd(), reduce_sdsp(), reduce_simple(), reduceStatsPrint(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcreateRandom(), SCIPdebugMessage, SCIPfreeRandom(), SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisStopped(), STP_RED_BD3BOUND, STP_RED_EXFACTOR, STP_RED_EXTENSIVE, STP_RED_SDSPBOUND, STP_RED_SDSPBOUND2, and TRUE.

Referenced by reduceStp(), SCIPStpHeurPruneRun(), and SCIPStpHeurSlackPruneRun().

◆ redLoopPc()

SCIP_RETCODE redLoopPc ( SCIP scip,
GRAPH g,
PATH vnoi,
PATH path,
GNODE **  gnodearr,
SCIP_Real nodearrreal,
SCIP_Real exedgearrreal,
SCIP_Real exedgearrreal2,
int *  heap,
int *  state,
int *  vbase,
int *  nodearrint,
int *  edgearrint,
int *  nodearrint2,
int *  solnode,
STP_Bool nodearrchar,
SCIP_Real fixed,
SCIP_Bool  dualascent,
SCIP_Bool  bred,
int  reductbound,
SCIP_Bool  userec 
)

(R)PC loop

Parameters
scipSCIP data structure
ggraph data structure
vnoiVoronoi data structure
pathpath data structure
gnodearrnodes-sized array
nodearrrealnodes-sized array
exedgearrrealedges-sized array
exedgearrreal2edges-sized array
heapshortest path array
statevoronoi base array
vbasenodes-sized array
nodearrintedges-sized array
edgearrintnodes-sized array
nodearrint2nodes-sized array
solnodesolution nodes array (or NULL)
nodearrcharnodes-sized array
fixedpointer to store the offset value
dualascentdo dual-ascent reduction?
breddo bound-based reduction?
reductboundminimal number of edges to be eliminated in order to reiterate reductions
userecuse recombination heuristic?

Definition at line 1158 of file reduce.c.

References FALSE, FARAWAY, GRAPH::grad, graph_pc_2org(), graph_pc_2trans(), graph_pc_getPosPrizeSum(), graph_pc_presolExit(), graph_pc_presolInit(), graph_pc_term2edgeConsistent(), NULL, nvreduce_sl(), GRAPH::prize, reduce_bd34(), reduce_bound(), reduce_da(), reduce_daPcMw(), reduce_sdPc(), reduce_sdsp(), reduce_simple_pc(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcreateRandom(), SCIPdebugMessage, SCIPfreeRandom(), SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisStopped(), GRAPH::source, STP_RED_BD3BOUND, STP_RED_EXTENSIVE, STP_RED_MAXNROUNDS, STP_RED_SDSPBOUND, STP_RED_SDSPBOUND2, STP_RPCSPG, GRAPH::stp_type, GRAPH::terms, and TRUE.

Referenced by reducePc(), and SCIPStpHeurPruneRun().

◆ redLoopMw()

SCIP_RETCODE redLoopMw ( SCIP scip,
GRAPH g,
PATH vnoi,
PATH path,
GNODE **  gnodearr,
SCIP_Real nodearrreal,
SCIP_Real edgearrreal,
SCIP_Real edgearrreal2,
int *  state,
int *  vbase,
int *  nodearrint,
int *  edgearrint,
int *  nodearrint2,
int *  nodearrint3,
int *  solnode,
STP_Bool nodearrchar,
SCIP_Real fixed,
STP_Bool  advanced,
STP_Bool  bred,
STP_Bool  tryrmw,
int  redbound,
SCIP_Bool  userec 
)

MWCS loop

Parameters
scipSCIP data structure
ggraph data structure
vnoiVoronoi data structure
pathpath data structure
gnodearrnodes-sized array
nodearrrealnodes-sized array
edgearrrealedges-sized array
edgearrreal2edges-sized array
stateshortest path array
vbasevoronoi base array
nodearrintnodes-sized array
edgearrintedges-sized array
nodearrint2nodes-sized array
nodearrint3nodes-sized array
solnodearray to indicate whether a node is part of the current solution (==CONNECT)
nodearrcharnodes-sized array
fixedpointer to store the offset value
advanceddo advanced reduction?
breddo bound-based reduction?
tryrmwtry to convert problem to RMWCSP? Only possible if advanced = TRUE and userec = TRUE
redboundminimal number of edges to be eliminated in order to reiterate reductions
userecuse recombination heuristic?

Definition at line 921 of file reduce.c.

References FALSE, graph_pc_2org(), graph_pc_2trans(), graph_pc_getPosPrizeSum(), graph_pc_mw2rmw(), graph_pc_term2edgeConsistent(), level0(), NULL, reduce_ans(), reduce_ansAdv(), reduce_ansAdv2(), reduce_boundMw(), reduce_chain2(), reduce_daPcMw(), reduce_nnp(), reduce_npv(), reduce_simple_mw(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcreateRandom(), SCIPdebugMessage, SCIPfreeRandom(), SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisStopped(), STP_RED_EXTENSIVE, STP_RED_MAXNROUNDS, STP_RED_MWTERMBOUND, GRAPH::terms, and TRUE.

Referenced by reduceMw(), SCIPStpHeurPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

◆ reduce()

SCIP_RETCODE reduce ( SCIP scip,
GRAPH **  graph,
SCIP_Real offset,
int  level,
int  minelims,
SCIP_Bool  userec 
)

reduces the graph

Parameters
scipSCIP data structure
graphgraph structure
offsetpointer to store offset generated by reductions
levelreduction level 0: none, 1: basic, 2: advanced
minelimsminimal amount of reductions to reiterate reduction methods
userecuse recombination heuristic?

Definition at line 1673 of file reduce.c.

References FALSE, graph_init_history(), graph_path_exit(), graph_path_init(), graph_valid(), level0(), NULL, reduceHc(), reduceMw(), reduceNw(), reducePc(), reduceSap(), reduceStp(), SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, STP_DCSTP, STP_DHCSTP, STP_MWCSP, STP_NWSPG, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_SAP, and TRUE.

Referenced by SCIPprobdataCreate(), SCIPStpHeurRecExclude(), and SCIPStpHeurRecRun().

◆ reduce_ans()

void reduce_ans ( SCIP scip,
GRAPH g,
int *  marked,
int *  count 
)

adjacent neighbourhood reduction for the MWCSP

Parameters
scipSCIP data structure
ggraph data structure
markednodes array
countpointer to number of reductions

Definition at line 4447 of file reduce_alt.c.

References ansProcessCandidate(), EAT_LAST, FALSE, GRAPH::grad, graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Real, SCIPisLT(), STP_MWCSP, STP_RED_ANSMAXNEIGHBORS, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by redLoopMw().

◆ reduce_ansAdv()

void reduce_ansAdv ( SCIP scip,
GRAPH g,
int *  marked,
int *  count,
SCIP_Bool  extneigbhood 
)

advanced adjacent neighbourhood reduction for the MWCSP

Parameters
scipSCIP data structure
ggraph data structure
markednodes array
countpointer to number of performed reductions
extneigbhooduse extended neighbour hood

Definition at line 4515 of file reduce_alt.c.

References ansProcessCandidate(), EAT_LAST, FALSE, GRAPH::grad, graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MAX, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Real, SCIPdebugMessage, SCIPisGT(), SCIPisLE(), STP_MWCSP, STP_RED_ANSEXMAXCANDS, STP_RED_ANSMAXCANDS, STP_RED_CNSNN, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by redLoopMw().

◆ reduce_ansAdv2()

void reduce_ansAdv2 ( SCIP scip,
GRAPH g,
int *  marked,
int *  count 
)

alternative advanced adjacent neighbourhood reduction for the MWCSP

Parameters
scipSCIP data structure
ggraph data structure
markednodes array
countpointer to number of reductions

Definition at line 4621 of file reduce_alt.c.

References ansProcessCandidate(), EAT_LAST, FALSE, GRAPH::grad, graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Real, SCIPisGE(), SCIPisGT(), SCIPisLE(), STP_MWCSP, STP_RED_CNSNN, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by redLoopMw().

◆ reduce_nnp()

void reduce_nnp ( SCIP scip,
GRAPH g,
int *  marked,
int *  count 
)

non-negative path reduction for the MWCSP

Parameters
scipSCIP data structure
ggraph data structure
markednodes array
countpointer to number of reductions

Definition at line 5450 of file reduce_alt.c.

References EAT_LAST, FALSE, graph_edge_del(), graph_valid(), GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, STP_MWCSP, GRAPH::stp_type, and TRUE.

Referenced by redLoopMw().

◆ reduce_sdsp()

SCIP_RETCODE reduce_sdsp ( SCIP scip,
GRAPH g,
PATH pathtail,
PATH pathhead,
int *  heap,
int *  statetail,
int *  statehead,
int *  memlbltail,
int *  memlblhead,
int *  nelims,
int  limit,
int *  edgestate 
)

◆ reduce_sdspSap()

SCIP_RETCODE reduce_sdspSap ( SCIP scip,
GRAPH g,
PATH pathtail,
PATH pathhead,
int *  heap,
int *  statetail,
int *  statehead,
int *  memlbltail,
int *  memlblhead,
int *  nelims,
int  limit 
)

SDC test for the SAP using a limited version of Dijkstra's algorithm from both endpoints of an arc

Definition at line 2308 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_sdPaths(), GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), TRUE, and UNKNOWN.

Referenced by reduceSap().

◆ reduce_sd()

SCIP_RETCODE reduce_sd ( SCIP scip,
GRAPH g,
PATH vnoi,
SCIP_Real edgepreds,
SCIP_Real mstsdist,
int *  heap,
int *  state,
int *  vbase,
int *  nodesid,
int *  nodesorg,
int *  forbidden,
int *  nelims,
SCIP_Bool  nodereplacing,
int *  edgestate 
)

Special distance test

Parameters
scipSCIP data structure
ggraph data structure
vnoiVoronoi data structure
edgepredsarray to store edge predecessors of auxiliary graph
mstsdistarray to store mst distances in auxiliary graph
heaparray representing a heap
statearray to indicate whether a node has been scanned during SP calculation
vbaseVoronoi base to each vertex
nodesidarray to map nodes in auxiliary graph to original ones
nodesorgarray to map terminals of original graph vertices of auxiliary graph
forbiddenarray to mark whether an edge may be eliminated
nelimspoint to store number of deleted edges
nodereplacingshould node replacement (by edges) be performed?
edgestatearray to store status of (directed) edge (for propagation, can otherwise be set to NULL)

Definition at line 1105 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_FREE, EAT_LAST, shortest_path::edge, EDGE_BLOCKED, GRAPH::edges, FALSE, flipedge, getlecloseterms(), GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_free(), graph_get4nextTerms(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_path_exec(), graph_path_exit(), graph_path_init(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MIN, MST_MODE, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_bdr(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisLT(), sddeltable(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by redLoopStp().

◆ reduce_sdPc()

SCIP_RETCODE reduce_sdPc ( SCIP scip,
GRAPH g,
PATH vnoi,
int *  heap,
int *  state,
int *  vbase,
int *  nodesid,
int *  nodesorg,
int *  nelims 
)

SD test for PC

Parameters
scipSCIP data structure
ggraph data structure
vnoiVoronoi data structure
heapheap array
statearray to store state of a node during Voronoi computation
vbaseVoronoi base to each node
nodesidarray
nodesorgarray
nelimspointer to store number of eliminated edges

Definition at line 1499 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_FREE, EAT_LAST, GRAPH::edges, FARAWAY, flipedge, getcloseterms(), getcloseterms2term(), GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_free(), graph_get4nextTerms(), graph_get4nextTTerms(), graph_init(), graph_knot_add(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGT(), SCIPisLT(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by redLoopPc().

◆ reduce_getSd()

SCIP_RETCODE reduce_getSd ( SCIP scip,
GRAPH g,
PATH pathtail,
PATH pathhead,
SCIP_Real sdist,
SCIP_Real  distlimit,
int *  heap,
int *  statetail,
int *  statehead,
int *  memlbltail,
int *  memlblhead,
int  i,
int  i2,
int  limit,
SCIP_Bool  pc,
SCIP_Bool  mw 
)

◆ reduce_getSdPcMw()

SCIP_RETCODE reduce_getSdPcMw ( SCIP scip,
const GRAPH g,
PATH pathtail,
PATH pathhead,
SCIP_Real sdist,
SCIP_Real  distlimit,
int *  heap,
int *  statetail,
int *  statehead,
int *  memlbltail,
int *  memlblhead,
int *  pathmaxnodetail,
int *  pathmaxnodehead,
int  i,
int  i2,
int  limit 
)

◆ reduce_nts()

SCIP_RETCODE reduce_nts ( SCIP scip,
GRAPH g,
PATH pathtail,
PATH pathhead,
int *  heap,
int *  statetail,
int *  statehead,
int *  memlbltail,
int *  memlblhead,
int *  nelims,
int  limit 
)

Non-Terminal-Set test

Parameters
scipSCIP data structure
ggraph structure
pathtailarray for internal use
pathheadarray for internal use
heaparray for internal use
statetailarray for internal use
stateheadarray for internal use
memlbltailarray for internal use
memlblheadarray for internal use
nelimspoint to return number of eliminations
limitlimit for edges to consider for each vertex

Definition at line 3217 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_FREE, EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_add(), graph_free(), graph_init(), graph_knot_add(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_getSd(), reduce_getSdPcMw(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArrayNull, SCIPisGE(), SCIPisGT(), SCIPisLT(), STP_BD_MAXDEGREE, STP_BD_MAXDNEDGES, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

◆ reduce_bd34()

◆ reduce_bdr()

SCIP_RETCODE reduce_bdr ( SCIP scip,
GRAPH g,
GRAPH netgraph,
PATH netmst,
PATH vnoi,
SCIP_Real mstsdist,
SCIP_Real termdist1,
SCIP_Real termdist2,
int *  vbase,
int *  nodesid,
int *  neighbterms1,
int *  neighbterms2,
int *  nelims 
)

bd_k test for given Steiner bottleneck distances todo bd5

Parameters
scipSCIP data structure
ggraph structure
netgraphauxiliary graph structure
netmstMST structure
vnoipath structure
mstsdistMST distance in aux-graph
termdist1dist array
termdist2second dist array
vbasebases for nearest terminals
nodesidnodes identification array
neighbterms1neighbour terminals array
neighbterms2second neighbour terminals array
nelimsnumber of eliminations

Definition at line 2747 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, GRAPH::edges, FALSE, flipedge, getRSD(), GRAPH::grad, graph_edge_add(), graph_free(), graph_init(), graph_knot_add(), graph_knot_delPseudo(), graph_path_exec(), graph_path_exit(), graph_path_init(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, STP_BDR_MAXDEGREE, STP_BDR_MAXDNEDGES, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduce_sd().

◆ reduce_nv()

◆ reduce_nvAdv()

◆ reduce_sl()

◆ reduce_ledge()

◆ reduce_cnsAdv()

SCIP_RETCODE reduce_cnsAdv ( SCIP scip,
GRAPH g,
int *  marked,
int *  count 
)

advanced connected neighborhood subset reduction test for the MWCSP

Parameters
scipSCIP data structure
ggraph data structure
markednodes array for internal use
countpointer to number of reductions

Definition at line 4748 of file reduce_alt.c.

References EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_OKAY, SCIP_Real, SCIPisGE(), SCIPisGT(), SCIPisLE(), STP_MWCSP, STP_RED_CNSNN, GRAPH::stp_type, GRAPH::term, TRUE, UNKNOWN, VERTEX_CONNECT, VERTEX_NEIGHBOR, VERTEX_OTHER, and VERTEX_TEMPNEIGHBOR.

◆ reduce_npv()

SCIP_RETCODE reduce_npv ( SCIP scip,
GRAPH g,
PATH pathtail,
PATH pathhead,
int *  heap,
int *  statetail,
int *  statehead,
int *  memlbltail,
int *  memlblhead,
int *  nelims,
int  limit 
)

◆ reduce_chain2()

SCIP_RETCODE reduce_chain2 ( SCIP scip,
GRAPH g,
PATH pathtail,
PATH pathhead,
int *  heap,
int *  statetail,
int *  statehead,
int *  memlbltail,
int *  memlblhead,
int *  nelims,
int  limit 
)

◆ reduce_deleteConflictEdges()

SCIP_RETCODE reduce_deleteConflictEdges ( SCIP scip,
GRAPH g 
)

todo don't use this function, but check for conflicts in misc_stp.c and handle them

Parameters
scipSCIP data structure
gthe graph

Definition at line 2421 of file reduce_bnd.c.

References GRAPH::ancestors, EAT_FREE, GRAPH::edges, FALSE, graph_edge_del(), markAncestorsConflict(), MAX, NULL, GRAPH::oeat, GRAPH::orgedges, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, TRUE, and unmarkAncestorsConflict().

Referenced by redLoopStp(), and reduce_da().

◆ reduce_check3Tree()

SCIP_RETCODE reduce_check3Tree ( SCIP scip,
const GRAPH graph,
int  root,
const SCIP_Real redcost,
const SCIP_Real pathdist,
const PATH vnoi,
const int *  vbase,
SCIP_Real  cutoff,
const int *  outedges,
int  inedge,
int *  edgestack,
SCIP_Real treebound,
SCIP_Bool ruleout,
unsigned int *  eqstack,
int *  eqstack_size,
SCIP_Bool eqmark 
)

check 3-tree

Parameters
scipSCIP data structure
graphgraph data structure
rootgraph root from dual ascent
redcostreduced costs
pathdistshortest path distances
vnoiVoronoi paths
vbasebases to Voronoi paths
cutoffcutoff value
outedgestwo outgoing edge
inedgeincoming edge
edgestackarray of size nodes for internal computations
treeboundto store a lower bound for the tree
ruleoutcould tree be ruled out?
eqstackstores edges that were used for equality comparison
eqstack_sizepointer to size of eqstack
eqmarkmarks edges that were used for equality comparison

Definition at line 2464 of file reduce_bnd.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, GRAPH::edges, extendSubtreeHead(), extendSubtreeTail(), FALSE, FARAWAY, finalizeSubtree(), flipedge, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, markAncestorsConflict(), MAX, MIN, nnodes, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::outbeg, ruleOutSubtree(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocCleanBufferArray, SCIPfreeCleanBufferArray, SCIPisGE(), SCIPisGT(), shortenSubtree(), STP_DAEX_EDGELIMIT, STP_DAEX_MAXDFSDEPTH, STP_DAEX_MAXGRAD, STP_DAEX_MINDFSDEPTH, STP_DAEX_MINGRAD, GRAPH::tail, GRAPH::term, TRUE, truncateSubtree(), and unmarkAncestorsConflict().

Referenced by updateNodeReplaceBounds().

◆ reduce_da()

SCIP_RETCODE reduce_da ( SCIP scip,
GRAPH graph,
PATH vnoi,
GNODE **  gnodearr,
SCIP_Real cost,
SCIP_Real costrev,
SCIP_Real pathdist,
SCIP_Real ub,
SCIP_Real offset,
int *  edgearrint,
int *  vbase,
int *  state,
int *  pathedge,
int *  nodearrint,
int *  heursources,
STP_Bool nodearrchar,
int *  nelims,
int  prevrounds,
SCIP_RANDNUMGEN randnumgen,
SCIP_Bool  userec,
SCIP_Bool  extended 
)

dual ascent based reductions

Parameters
scipSCIP data structure
graphgraph data structure
vnoiVoronoi data structure
gnodearrGNODE* terminals array for internal computations or NULL
costedge costs
costrevreverse edge costs
pathdistdistance array for shortest path calculations
ubpointer to provide upper bound and return upper bound found during ascent and prune (if better)
offsetpointer to store offset
edgearrintint edges array for internal computations or NULL
vbasearray for Voronoi bases
stateint 4 * nnodes array for internal computations
pathedgearray for predecessor edge on a path
nodearrintint nnodes array for internal computations
heursourcesarray to store starting points of TM heuristic
nodearrcharSTP_Bool node array for internal computations
nelimspointer to store number of reduced edges
prevroundsnumber of reduction rounds that have been performed already
randnumgenrandom number generator
userecuse recombination heuristic?
extendeduse extended tests?

Definition at line 2861 of file reduce_bnd.c.

References BMScopyMemoryArray, GRAPH::cost, DAMAXDEVIATION_RANDOM_LOWER, DAMAXDEVIATION_RANDOM_UPPER, DEFAULT_DARUNS, DEFAULT_HEURRUNS, EAT_LAST, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_get4nextTerms(), graph_path_execX(), graph_pc_2org(), graph_pc_2trans(), graph_pc_2transcheck(), graph_sol_getObj(), graph_sol_reroot(), graph_sol_valid(), graph_valid(), graph_voronoiTerms(), Is_term, GRAPH::knots, level0(), GRAPH::mark, stp_solution_pool::maxindex, MIN, nnodes, nterms, NULL, stp_solution::obj, GRAPH::oeat, orderDaRoots(), GRAPH::outbeg, GRAPH::path_heap, reduce_deleteConflictEdges(), reduce_extendedEdge(), reduceSPG(), reduceWithEdgeFixingBounds(), reduceWithNodeFixingBounds(), reduceWithNodeReplaceBounds(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisGE(), SCIPisLE(), SCIPisLT(), SCIPisZero(), SCIPrandomGetInt(), SCIPrandomGetReal(), SCIPStpDualAscent(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurRecAddToPool(), SCIPStpHeurRecFreePool(), SCIPStpHeurRecInitPool(), SCIPStpHeurRecRun(), SCIPStpHeurRecSolfromIdx(), SCIPStpHeurTMCompStarts(), SCIPStpHeurTMRun(), stp_solution_pool::size, stp_solution::soledges, SOLPOOL_SIZE, GRAPH::source, STP_NWSPG, STP_RPCSPG, STP_RSMT, STP_SAP, GRAPH::stp_type, GRAPH::term, GRAPH::terms, TRUE, UNKNOWN, updateEdgeFixingBounds(), updateNodeFixingBounds(), and updateNodeReplaceBounds().

Referenced by redLoopPc(), redLoopStp(), reduceNw(), and reduceSap().

◆ reduce_daSlackPrune()

SCIP_RETCODE reduce_daSlackPrune ( SCIP scip,
SCIP_VAR **  vars,
GRAPH graph,
PATH vnoi,
GNODE **  gnodearr,
SCIP_Real cost,
SCIP_Real costrev,
SCIP_Real pathdist,
SCIP_Real upperbound,
int *  edgearrint,
int *  edgearrint2,
int *  vbase,
int *  pathedge,
int *  state,
int *  solnode,
STP_Bool nodearrchar,
STP_Bool edgearrchar,
int *  nelims,
int  minelims,
SCIP_Bool  solgiven 
)

dual ascent reduction for slack-and-prune heuristic

Parameters
scipSCIP data structure
varsproblem variables or NULL
graphgraph data structure
vnoiVoronoi data structure
gnodearrGNODE* terminals array for internal computations or NULL
costarray to store reduced costs
costrevreverse edge costs
pathdistdistance array for shortest path calculations
upperboundpointer to store new upper bound
edgearrintint edges array to store solution value
edgearrint2int edges array for internal computations
vbasearray for Voronoi bases
pathedgearray for predecessor edge on a path
stateint 4 * nnodes array for internal computations
solnodearray of nodes of current solution that is not to be destroyed
nodearrcharSTP_Bool node array for internal computations
edgearrcharSTP_Bool edge array for internal computations
nelimspointer to store number of reduced edges
minelimsminimum number of edges to eliminate
solgivensolution provided?

Definition at line 3279 of file reduce_bnd.c.

References a, CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_get4nextTerms(), graph_path_exec(), graph_path_execX(), graph_pc_2org(), graph_pc_2trans(), graph_sol_getObj(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPepsilon(), SCIPfreeBufferArray, SCIPintListNodeFree(), SCIPisEQ(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPqueueCreate(), SCIPqueueFree(), SCIPqueueInsert(), SCIPqueueIsEmpty(), SCIPqueueRemove(), SCIPsortReal(), SCIPStpDualAscent(), SCIPStpHeurAscendPruneRun(), GRAPH::source, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by SCIPStpHeurSlackPruneRun().

◆ reduce_daSlackPruneMw()

SCIP_RETCODE reduce_daSlackPruneMw ( SCIP scip,
GRAPH graph,
PATH vnoi,
GNODE **  gnodearr,
SCIP_Real cost,
SCIP_Real costrev,
SCIP_Real pathdist,
int *  vbase,
int *  pathedge,
int *  soledge,
int *  state,
int *  solnode,
STP_Bool nodearrchar,
int *  nelims,
int  minelims,
SCIP_Bool  solgiven 
)

dual ascent based heuristic reductions for MWCSP

Parameters
scipSCIP data structure
graphgraph data structure
vnoiVoronoi data structure array
gnodearrGNODE* terminals array for internal computations or NULL
costedge costs
costrevreverse edge costs
pathdistdistance array for shortest path calculations
vbaseVoronoi base array
pathedgeshortest path incoming edge array for shortest path calculations
soledgeedge solution array (CONNECT/UNKNOWN) or NULL; needs to contain solution if solgiven == TRUE
stateint 4 * vertices array
solnodearray of nodes of current solution that is not to be destroyed
nodearrcharSTP_Bool node array for internal computations
nelimspointer to store number of reduced edges
minelimsminimum number of edges to eliminate
solgivensolution provided?

Definition at line 4237 of file reduce_bnd.c.

References CONNECT, GRAPH::cost, DEFAULT_HEURRUNS, DEFAULT_HOPFACTOR, shortest_path::dist, EAT_LAST, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_free(), graph_init_history(), graph_path_execX(), graph_path_exit(), graph_path_init(), graph_pc_2org(), graph_pc_2trans(), graph_pc_getSap(), graph_sol_getObj(), graph_sol_valid(), graph_voronoiTerms(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MIN, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPepsilon(), SCIPfindHeur(), SCIPfreeBufferArray, SCIPheurGetData(), SCIPintListNodeFree(), SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPprobdataGetOffset(), SCIPsortReal(), SCIPStpDualAscent(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurTMPrunePc(), SCIPStpHeurTMRun(), GRAPH::source, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by SCIPStpHeurSlackPruneRunPcMw().

◆ reduce_daPcMw()

SCIP_RETCODE reduce_daPcMw ( SCIP scip,
GRAPH graph,
PATH vnoi,
GNODE **  gnodearr,
SCIP_Real cost,
SCIP_Real costrev,
SCIP_Real pathdist,
int *  vbase,
int *  pathedge,
int *  edgearrint,
int *  state,
STP_Bool nodearrchar,
int *  nelims,
SCIP_Bool  solbasedda,
SCIP_Bool  varyroot,
SCIP_Bool  markroots,
SCIP_Bool  userec,
SCIP_Bool  fastmode,
SCIP_RANDNUMGEN randnumgen,
SCIP_Real  prizesum 
)

dual ascent based reductions for PCSPG and MWCSP

Parameters
scipSCIP data structure
graphgraph data structure
vnoiVoronoi data structure array
gnodearrGNODE* terminals array for internal computations or NULL
costreduced edge costs
costrevreduced reverse edge costs
pathdistdistance array for shortest path calculations
vbaseVoronoi base array
pathedgeshortest path incoming edge array for shortest path calculations
edgearrintint edges array for internal computations or NULL
stateint 4 * vertices array
nodearrcharSTP_Bool node array for internal computations
nelimspointer to store number of reduced edges
solbaseddarerun Da based on best primal solution
varyrootvary root for DA if possible
markrootsshould terminals proven to be part of an opt. sol. be marked as such?
userecuse recombination heuristic?
fastmoderun heuristic in fast mode?
randnumgenrandom number generator
prizesumsum of positive prizes

Definition at line 3801 of file reduce_bnd.c.

References BMScopyMemoryArray, computeDaSolPcMw(), computePertubedSol(), computeTransVoronoi(), GRAPH::cost, DAMAXDEVIATION_FAST, DEFAULT_HEURRUNS, DEFAULT_NMAXROOTS, dualCostIsValid(), EAT_LAST, GRAPH::edges, FALSE, FARAWAY, findDaRoots(), flipedge, GRAPH::grad, graph_free(), graph_get2next(), graph_init_history(), graph_path_execX(), graph_path_exit(), graph_path_init(), graph_pc_2org(), graph_pc_2orgcheck(), graph_pc_2trans(), graph_pc_getRsap(), graph_pc_getSap(), graph_sol_getObj(), graph_sol_reroot(), graph_sol_unreduced(), graph_sol_valid(), graph_valid(), graph_voronoiTerms(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, markPcMwRoots(), MIN, nnodes, nterms, NULL, stp_solution::obj, GRAPH::oeat, orderDaRoots(), GRAPH::outbeg, GRAPH::path_heap, GRAPH::prize, reducePcMw(), reducePcMwTryBest(), reduceWithEdgeFixingBounds(), reduceWithNodeFixingBounds(), roots, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisEQ(), SCIPisGT(), SCIPStpDualAscent(), SCIPStpHeurLocalRun(), SCIPStpHeurRecAddToPool(), SCIPStpHeurRecFreePool(), SCIPStpHeurRecInitPool(), SCIPStpHeurTMRun(), SOLPOOL_SIZE, stp_solution_pool::sols, GRAPH::source, STP_MWCSP, STP_RED_MINBNDTERMS, STP_RPCSPG, STP_SAP, GRAPH::stp_type, GRAPH::term, GRAPH::terms, TRUE, updateEdgeFixingBounds(), and updateNodeFixingBounds().

Referenced by redLoopMw(), and redLoopPc().

◆ reduce_bound()

SCIP_RETCODE reduce_bound ( SCIP scip,
GRAPH graph,
PATH vnoi,
SCIP_Real cost,
SCIP_Real prize,
SCIP_Real radius,
SCIP_Real costrev,
SCIP_Real offset,
SCIP_Real upperbound,
int *  heap,
int *  state,
int *  vbase,
int *  nelims 
)

bound-based reductions for the (R)PCSTP, the MWCSP and the STP

Parameters
scipSCIP data structure
graphgraph data structure
vnoiVoronoi data structure
costedge cost array
prizeprize (nodes) array
radiusradius array
costrevreversed edge cost array
offsetpointer to the offset
upperboundpointer to an upper bound
heapheap array
statearray to store state of a node during Voronoi computation
vbaseVoronoi base to each node
nelimspointer to store number of eliminated edges

Definition at line 4653 of file reduce_bnd.c.

References BLOCKED, bound, CONNECT, GRAPH::cost, DEFAULT_HEURRUNS, DEFAULT_HOPFACTOR, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_free(), graph_get2next(), graph_get3next(), graph_get4next(), graph_get4nextTTerms(), graph_init(), graph_knot_chg(), graph_knot_delPseudo(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_pc_2org(), graph_pc_2trans(), graph_pc_deleteTerm(), graph_valid(), graph_voronoiWithRadius(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, MIN, MST_MODE, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, GRAPH::prize, r, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfindHeur(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPheurGetData(), SCIPisGE(), SCIPisGT(), SCIPisLT(), SCIPsortReal(), SCIPsortRealInt(), SCIPStpHeurTMCompStarts(), SCIPStpHeurTMRun(), GRAPH::source, STP_DHCSTP, STP_MWCSP, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by redLoopPc(), redLoopStp(), and reduceHc().

◆ reduce_boundMw()

SCIP_RETCODE reduce_boundMw ( SCIP scip,
GRAPH graph,
PATH vnoi,
PATH path,
SCIP_Real cost,
SCIP_Real radius,
SCIP_Real costrev,
SCIP_Real offset,
int *  heap,
int *  state,
int *  vbase,
int *  result,
int *  nelims 
)

Bound-based reduction method for the MWCSP . The reduction method tries to eliminate nodes and vertices by checking whether an upper bound for each solution that contains them is smaller than the best known solution value. The essence of the approach is a decomposition of the graph such that this upper bound is minimized.

Parameters
scipSCIP data structure
graphgraph data structure
vnoiVoronoi data structure (size 3 * nnodes)
pathshortest path data structure (size nnodes)
costedge cost array
radiusradius array
costrevreversed edge cost array
offsetpointer to the offset
heapheap array
statearray to store state of a node during Voronoi computation
vbaseVoronoi base to each node
resultsolution array or NULL
nelimspointer to store number of eliminated edges

Definition at line 5243 of file reduce_bnd.c.

References bound, CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_get2next(), graph_voronoiMw(), graph_voronoiWithRadiusMw(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::outbeg, GRAPH::prize, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPfreeBufferArrayNull, SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPsortReal(), GRAPH::source, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by redLoopMw().

◆ reduce_boundPrune()

SCIP_RETCODE reduce_boundPrune ( SCIP scip,
GRAPH graph,
PATH vnoi,
SCIP_Real cost,
SCIP_Real radius,
SCIP_Real costrev,
SCIP_Real offset,
int *  heap,
int *  state,
int *  vbase,
const int *  solnode,
const int *  soledge,
int *  nelims,
int  minelims 
)

bound-based reductions for the (R)PCSTP, the MWCSP and the STP; used by prune heuristic

Parameters
scipSCIP data structure
graphgraph data structure
vnoiVoronoi data structure
costedge cost array
radiusradius array
costrevreversed edge cost array
offsetpointer to the offset
heapheap array
statearray to store state of a node during Voronoi computation
vbaseVoronoi base to each node
solnodearray of nodes of current solution that is not to be destroyed
soledgearray of edges of current solution that is not to be destroyed
nelimspointer to store number of eliminated edges
minelimsminimum number of edges to be eliminated

Definition at line 5415 of file reduce_bnd.c.

References BLOCKED, bound, CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_free(), graph_get2next(), graph_get3next(), graph_init(), graph_knot_chg(), graph_knot_delPseudo(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_valid(), graph_voronoiMw(), graph_voronoiWithRadius(), GRAPH::head, Is_gterm, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, MIN, MST_MODE, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPepsilon(), SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), SCIPisLT(), SCIPsortReal(), GRAPH::source, STP_DHCSTP, STP_MWCSP, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by SCIPStpHeurPruneRun().

◆ reduce_boundHop()

◆ reduce_boundHopR()

SCIP_RETCODE reduce_boundHopR ( SCIP scip,
GRAPH graph,
PATH vnoi,
SCIP_Real cost,
SCIP_Real costrev,
SCIP_Real pathdist,
int *  heap,
int *  state,
int *  vbase,
int *  nelims,
int *  pathedge 
)

◆ reduce_boundHopRc()

◆ reduce_extendedEdge()

int reduce_extendedEdge ( SCIP scip,
GRAPH graph,
const PATH vnoi,
const SCIP_Real cost,
const SCIP_Real pathdist,
const int *  result,
SCIP_Real  minpathcost,
int  root,
int *  nodearr,
STP_Bool marked 
)

reduce SPG graph based on reduced cost information and given upper bound

Parameters
scipSCIP data structure
graphgraph data structure
vnoiVoronoi data structure
costdual ascent costs
pathdistdistance array from shortest path calculations
resultsol int array
minpathcostthe required reduced path cost to be surpassed
rootthe root
nodearrfor internal stuff
markededge array to mark which (directed) edge can be removed

Definition at line 2774 of file reduce_bnd.c.

References CONNECT, EAT_FREE, GRAPH::edges, FALSE, GRAPH::grad, graph_edge_del(), graph_pc_2orgcheck(), GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, reduceCheckEdge(), SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPisZero(), STP_RPCSPG, GRAPH::stp_type, and TRUE.

Referenced by reduce_da(), and reduceRedcostExtended().

◆ reduce_contractZeroEdges()

SCIP_RETCODE reduce_contractZeroEdges ( SCIP scip,
GRAPH g,
SCIP_Bool  savehistory 
)

contract edges of weight zero

Parameters
scipSCIP data structure
ggraph data structure
savehistorysave the history?

Definition at line 453 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_FREE, GRAPH::edges, GRAPH::fixedges, flipedge, graph_knot_contract(), GRAPH::head, NULL, GRAPH::oeat, SCIP_CALL, SCIP_OKAY, SCIPintListNodeAppendCopy(), SCIPisZero(), and GRAPH::tail.

Referenced by redbasedVarfixing(), and redLoopStp().

◆ reduce_simple()

SCIP_RETCODE reduce_simple ( SCIP scip,
GRAPH g,
SCIP_Real fixed,
int *  solnode,
int *  nelims,
int *  edgestate 
)

basic reduction tests for the STP

Parameters
scipSCIP data structure
ggraph data structure
fixedpointer to offset value
solnodenode array to mark whether an node is part of a given solution (CONNECT), or NULL
nelimspointer to number of reductions
edgestatearray to store status of (directed) edge (for propagation, can otherwise be set to NULL)

Definition at line 489 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, Edge_anti, EDGE_BLOCKED, EQ, FALSE, FARAWAY, GRAPH::fixedges, flipedge, GRAPH::grad, graph_edge_del(), graph_knot_contract(), graph_knot_contractLowdeg2High(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPintListNodeAppendCopy(), SCIPisLE(), SCIPisLT(), GRAPH::term, TRUE, and UNKNOWN.

Referenced by nvreduce_sl(), and redLoopStp().

◆ reduce_simple_hc()

SCIP_RETCODE reduce_simple_hc ( SCIP scip,
GRAPH g,
SCIP_Real fixed,
int *  count 
)

basic reduction tests for the HCDSTP

Parameters
scipSCIP data structure
ggraph data structure
fixedpointer to offfset value
countpointer to number of reductions

Definition at line 1247 of file reduce_simple.c.

References GRAPH::cost, EAT_LAST, FALSE, FARAWAY, flipedge, graph_edge_del(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_OKAY, SCIPdebugMessage, SCIPisGE(), SCIPisLT(), GRAPH::source, STP_DHCSTP, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by reduceHc().

◆ reduce_simple_mw()

SCIP_RETCODE reduce_simple_mw ( SCIP scip,
GRAPH g,
int *  solnode,
SCIP_Real fixed,
int *  count 
)

basic reduction tests for the MWCS problem

Parameters
scipSCIP data structure
ggraph data structure
solnodearray to indicate whether a node is part of the current solution (==CONNECT)
fixedpointer to offset value
countpointer to number of reductions

Definition at line 947 of file reduce_simple.c.

References adjterms(), adjust0term(), GRAPH::cost, EAT_LAST, Edge_anti, FALSE, flipedge_Uint, GRAPH::grad, graph_edge_del(), graph_knot_contract(), graph_pc_contractEdge(), graph_pc_contractEdgeAncestors(), graph_pc_deleteTerm(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, is_maxprize(), Is_pterm, Is_term, GRAPH::knots, level0save(), GRAPH::mark, nchains(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), SCIPisLE(), SCIPisZero(), GRAPH::source, STP_MWCSP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, traverseChain(), TRUE, and trydg1edgepc().

Referenced by redLoopMw().

◆ reduce_simple_pc()

SCIP_RETCODE reduce_simple_pc ( SCIP scip,
GRAPH g,
SCIP_Real fixed,
int *  count,
int *  solnode,
SCIP_Bool  contractroot 
)

◆ reduce_simple_sap()

SCIP_RETCODE reduce_simple_sap ( SCIP scip,
GRAPH g,
SCIP_Real fixed,
int *  count 
)

◆ reduce_rpt()

SCIP_RETCODE reduce_rpt ( SCIP scip,
GRAPH g,
SCIP_Real fixed,
int *  count 
)

root proximity terminal test (SAP)

Parameters
scipSCIP data structure
ggraph data structure
fixedpointer to offset value
countpointer to number of reductions

Definition at line 876 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, GRAPH::fixedges, GRAPH::grad, graph_knot_contract(), graph_path_execX(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPintListNodeAppendCopy(), SCIPisGT(), GRAPH::source, GRAPH::tail, and GRAPH::term.

Referenced by reduceSap().

◆ SCIPStpValidateSol()