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"

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

#define EAT_FREE -1

◆ 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

#define STP_SAP 1

Definition at line 39 of file grph.h.

Referenced by computeSteinerTree(), getlecloseterms(), graph_load(), graph_pc_getRsap(), graph_pc_getSap(), graph_pc_getSapShift(), reduce(), reduce_da(), reduce_daPcMw(), SCIPprobdataCreate(), SCIPprobdataWriteSolution(), SCIPStpHeurRecRun(), and SCIPStpHeurTMRun().

◆ STP_PCSPG

#define STP_PCSPG 2

Definition at line 40 of file grph.h.

Referenced by buildsolgraph(), compEdges(), createPrizeConstraints(), createVariables(), getlecloseterms(), graph_copy_data(), graph_get3nextTerms(), graph_get4nextTerms(), graph_get4nextTTerms(), graph_load(), graph_pack(), graph_pc_2pc(), graph_pc_getSapShift(), graph_pc_isPcMw(), graph_pc_knot2nonTerm(), graph_sol_valid(), graph_valid(), graph_voronoiWithRadius(), isProbCompatible(), nvreduce_sl(), probdataFree(), prune(), redbasedVarfixing(), reduce(), reduce_bd34(), reduce_bdr(), reduce_bound(), reduce_boundPrune(), reduce_getSdPcMw(), reduce_nts(), reduce_nv(), reduce_nvAdv(), reduce_sdsp(), reduce_simple_pc(), reduce_sl(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PROBCOPY(), SCIP_DECL_PROBTRANS(), SCIP_DECL_PROPEXEC(), SCIPprobdataAddNewSol(), SCIPprobdataCreate(), SCIPprobdataWriteSolution(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurPruneUpdateSols(), SCIPStpHeurRecRun(), SCIPStpHeurTMRun(), SCIPStpHeurTMRunLP(), SCIPwriteStp(), STPStpBranchruleParseConsname(), and updateFixingBounds().

◆ STP_RPCSPG

#define STP_RPCSPG 3

Definition at line 41 of file grph.h.

Referenced by adjust0term(), buildsolgraph(), computeSteinerTreeDijkPcMw(), createPrizeConstraints(), graph_copy_data(), graph_get3nextTerms(), graph_get4nextTerms(), graph_get4nextTTerms(), graph_load(), graph_pack(), graph_path_st_rpc(), graph_pc_2org(), graph_pc_2rpc(), graph_pc_chgPrize(), graph_pc_isPcMw(), graph_pc_knot2nonTerm(), graph_pc_presolExit(), graph_pc_presolInit(), graph_pc_subtractPrize(), graph_valid(), graph_voronoiWithRadius(), is_maxprize(), isProbCompatible(), nvreduce_sl(), probdataFree(), prune(), redbasedVarfixing(), redLoopPc(), reduce(), reduce_bd34(), reduce_bdr(), reduce_bound(), reduce_boundPrune(), reduce_da(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), reduce_extendedEdge(), reduce_getSdPcMw(), reduce_nts(), reduce_nv(), reduce_nvAdv(), reduce_sdsp(), reduce_simple_pc(), reduce_sl(), reducePc(), reduceSPG(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PROBCOPY(), SCIP_DECL_PROPEXEC(), SCIPprobdataCreate(), SCIPprobdataWriteSolution(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurPruneUpdateSols(), SCIPStpHeurRecRun(), SCIPStpHeurTMBuildTreePcMw(), SCIPStpHeurTMPrunePc(), SCIPStpHeurTMRun(), SCIPwriteStp(), STPStpBranchruleParseConsname(), and trydg1edgepc().

◆ STP_NWSPG

#define STP_NWSPG 4

Definition at line 42 of file grph.h.

Referenced by graph_load(), reduce(), reduce_da(), SCIPprobdataCreate(), SCIPprobdataWriteSolution(), SCIPStpHeurRecRun(), and SCIPwriteStp().

◆ STP_DCSTP

#define STP_DCSTP 5

Definition at line 43 of file grph.h.

Referenced by buildsolgraph(), createVariables(), graph_copy_data(), graph_free(), graph_load(), probdataFree(), reduce(), SCIP_DECL_CONSPROP(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PROBCOPY(), SCIP_DECL_PROBTRANS(), SCIP_DECL_PROPEXEC(), SCIPprobdataCreate(), SCIPprobdataWriteSolution(), SCIPStpHeurRecRun(), SCIPStpHeurTMRun(), SCIPStpHeurTMRunLP(), SCIPStpValidateSol(), and SCIPwriteStp().

◆ STP_REVENUES_BUDGET_HOPCONS

#define STP_REVENUES_BUDGET_HOPCONS 6

Definition at line 44 of file grph.h.

◆ STP_RSMT

◆ STP_OARSMT

#define STP_OARSMT 8

Definition at line 46 of file grph.h.

Referenced by buildsolgraph(), graph_load(), graph_obstgrid_create(), isProbCompatible(), SCIP_DECL_HEUREXEC(), SCIPprobdataCreate(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurSlackPruneRun(), and SCIPwriteStp().

◆ STP_MWCSP

#define STP_MWCSP 9

Definition at line 47 of file grph.h.

Referenced by buildsolgraph(), compEdges(), computeDaSolPcMw(), computePertubedSol(), createVariables(), getlecloseterms(), graph_copy_data(), graph_load(), graph_pack(), graph_path_PcMwSd(), graph_pc_2mw(), graph_pc_2pc(), graph_pc_chgPrize(), graph_pc_contractEdge(), graph_pc_getSapShift(), graph_pc_isPcMw(), graph_pc_knot2nonTerm(), graph_pc_subtractPrize(), graph_sdPaths(), graph_sol_valid(), graph_valid(), graph_voronoiWithRadius(), pertubateEdgeCosts(), probdataFree(), prune(), reduce(), reduce_ans(), reduce_ansAdv(), reduce_ansAdv2(), reduce_bound(), reduce_boundPrune(), reduce_cnsAdv(), reduce_daPcMw(), reduce_getSdPcMw(), reduce_nnp(), reduce_simple_mw(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PROBCOPY(), SCIP_DECL_PROBEXITSOL(), SCIP_DECL_PROBTRANS(), SCIPprobdataAddNewSol(), SCIPprobdataCreate(), SCIPprobdataWriteLogfileEnd(), SCIPprobdataWriteSolution(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurPruneUpdateSols(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurTMRun(), SCIPStpHeurTMRunLP(), SCIPwriteStp(), trydg1edgepc(), and updateFixingBounds().

◆ STP_DHCSTP

#define STP_DHCSTP 10

Definition at line 48 of file grph.h.

Referenced by computeSteinerTree(), createVariables(), getlecloseterms(), graph_load(), graph_voronoiWithRadius(), prune(), reduce(), reduce_bound(), reduce_boundPrune(), reduce_simple_hc(), SCIP_DECL_HEUREXEC(), SCIPprobdataCreate(), SCIPprobdataWriteSolution(), SCIPStpHeurPruneRun(), SCIPStpHeurRecRun(), SCIPStpHeurTMRun(), SCIPStpHeurTMRunLP(), and SCIPwriteStp().

◆ STP_GSTP

#define STP_GSTP 11

Definition at line 49 of file grph.h.

Referenced by buildsolgraph(), graph_load(), SCIP_DECL_HEUREXEC(), SCIPprobdataCreate(), SCIPprobdataWriteSolution(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), and SCIPStpHeurSlackPruneRun().

◆ STP_RMWCSP

◆ flipedge

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

Definition at line 150 of file grph.h.

Referenced by branchOnVertex(), buildsolgraph(), computeDegConsTree(), computeTransVoronoi(), createVariables(), dualcostVarfixing(), graph_knot_delPseudo(), graph_mincut_exec(), graph_pc_2pc(), graph_pc_2rmw(), graph_pc_2rpc(), graph_pc_getRsap(), graph_pc_getSap(), graph_pc_getSapShift(), graph_pc_mw2rmw(), graph_pc_term2edgeConsistent(), graph_pc_updateTerm2edge(), graph_sol_reroot(), initialise(), initReceivedSubproblem(), nodeIsCrucial(), pertubateEdgeCosts(), redbasedVarfixing(), reduce_bd34(), reduce_bdr(), reduce_bound(), reduce_boundHop(), reduce_boundHopR(), reduce_boundHopRc(), reduce_boundMw(), reduce_boundPrune(), reduce_check3Tree(), reduce_contractZeroEdges(), reduce_da(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), reduce_npv(), reduce_nts(), reduce_nvAdv(), reduce_sd(), reduce_sdPc(), reduce_sdspSap(), reduce_simple(), reduce_simple_hc(), reduce_simple_pc(), reduce_simple_sap(), reduceCheckEdge(), reducePcMw(), reduceSPG(), reduceWithEdgeFixingBounds(), reinitialise(), ruleOutSubtree(), SCIPlinkcuttreeEvert(), SCIPprobdataWriteSolution(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurRecRun(), SCIPStpHeurTMBuildTreeDc(), SCIPStpHeurTMRun(), SCIPStpHeurTMRunLP(), SCIPStpValidateSol(), sddeltable(), selectBranchingVertexBySol(), sep_2cut(), setVnoiDistances(), traverseChain(), trydg1edgepc(), updateEdgeFixingBounds(), and updateNodeReplaceBounds().

◆ 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

#define CONNECT 0

Definition at line 154 of file grph.h.

Referenced by buildsolgraph(), computeDegConsTree(), computePertubedSol(), computeSteinerTreeVnoi(), getlecloseterms(), graph_get2next(), graph_get3next(), graph_get4next(), graph_knot_contract(), graph_path_exec(), graph_path_execX(), graph_path_invroot(), graph_path_PcMwSd(), graph_path_st_pcmw_reduce(), graph_sdPaths(), graph_sol_getObj(), graph_sol_getOrg(), graph_sol_reroot(), graph_sol_unreduced(), graph_sol_valid(), graph_voronoi(), graph_voronoiExtend(), graph_voronoiMw(), graph_voronoiRepair(), graph_voronoiRepairMult(), graph_voronoiTerms(), graph_voronoiWithDist(), graph_voronoiWithRadius(), graph_voronoiWithRadiusMw(), pertubateEdgeCosts(), reduce_bound(), reduce_boundHop(), reduce_boundHopRc(), reduce_boundMw(), reduce_boundPrune(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), reduce_extendedEdge(), reduce_ledge(), reducePcMw(), reduceSPG(), reduceWithEdgeFixingBounds(), SCIP_DECL_HEUREXEC(), SCIPStpDualAscent(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurPruneUpdateSols(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), SCIPStpHeurSlackPruneRunPcMw(), SCIPStpHeurTMBuildTree(), SCIPStpHeurTMBuildTreeDc(), SCIPStpHeurTMBuildTreePcMw(), SCIPStpHeurTMPrunePc(), SCIPStpHeurTMRun(), selectBranchingVertexBySol(), selectdiffsols(), setNodeSolArray(), and updateSolNodeArray().

◆ 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

#define BLOCKED 1e10

Definition at line 157 of file grph.h.

Referenced by compEdges(), graph_pc_getPosPrizeSum(), initReceivedSubproblem(), reduce_bound(), reduce_boundHopRc(), reduce_boundPrune(), SCIP_DECL_PROPEXEC(), SCIPStpHeurRecRun(), SCIPStpHeurTMRun(), and SCIPStpHeurTMRunLP().

◆ 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

#define MST_MODE 0

Definition at line 162 of file grph.h.

Referenced by correct(), graph_path_exec(), reduce_bd34(), reduce_bdr(), reduce_bound(), reduce_boundHop(), reduce_boundPrune(), reduce_daSlackPrune(), reduce_ledge(), reduce_npv(), reduce_nts(), reduce_sd(), SCIPStpHeurLocalRun(), SCIPStpHeurTMBuildTree(), SCIPStpHeurTMBuildTreePcMw(), SCIPStpHeurTMPrune(), and SCIPStpHeurTMPrunePc().

◆ FSP_MODE

#define FSP_MODE 1

◆ 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

#define Is_pterm ( a ) ((a) == -2)

Definition at line 169 of file grph.h.

Referenced by adjust0term(), ansProcessCandidate(), buildsolgraph(), findDaRoots(), graph_path_st_pcmw(), graph_path_st_pcmw_extend(), graph_path_st_pcmw_full(), graph_path_st_rmw(), graph_path_st_rpc(), graph_pc_2org(), graph_pc_2trans(), graph_pc_chgPrize(), graph_pc_contractEdge(), graph_pc_deleteTerm(), graph_pc_getRsap(), graph_pc_getSap(), graph_pc_getSapShift(), graph_pc_mw2rmw(), graph_pc_subtractPrize(), graph_pc_term2edgeConsistent(), graph_sol_valid(), graph_valid(), markPcMwRoots(), pertubateEdgeCosts(), reduce_bound(), reduce_boundPrune(), reduce_daPcMw(), reduce_simple_mw(), reduce_simple_pc(), reduce_sl(), reducePcMw(), reduceSPG(), reduceWithEdgeFixingBounds(), reduceWithNodeFixingBounds(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurLocalRun(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurTMRun(), selectBranchingVertexByDegree(), STPStpBranchruleParseConsname(), trydg1edgepc(), updateEdgeFixingBounds(), updateNodeFixingBounds(), and updateNodeReplaceBounds().

◆ Is_gterm

#define Is_gterm ( a ) ((a) == -2 || (a) >= 0 )

Definition at line 170 of file grph.h.

Referenced by buildsolgraph(), graph_path_st_rmw(), graph_pc_term2edgeConsistent(), graph_pc_updateTerm2edge(), pertubateEdgeCosts(), reduce_boundPrune(), reduceWithNodeReplaceBounds(), and updateNodeReplaceBounds().

◆ Edge_anti

#define Edge_anti ( a ) ((((a) % 2) > 0) ? (a) - 1 : (a) + 1)

Definition at line 171 of file grph.h.

Referenced by getlecloseterms(), graph_edge_del(), graph_edge_redirect(), graph_edge_reinsert(), graph_knot_contract(), graph_mincut_exec(), graph_pack(), graph_voronoiWithDist(), graph_voronoiWithRadius(), reduce_ledge(), reduce_simple(), reduce_simple_mw(), reduce_simple_pc(), reduce_simple_sap(), and SCIPwriteStp().

◆ 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

g	the graph
node	node 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

newgraph	the new graph
oldgraph	the old graph
newtail	tail in new graph
newhead	head in new graph
oldtail	tail in old graph
oldhead	head 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

scip	SCIP data structure
g	the graph
cost	cost to be subtracted
i	the 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

scip	SCIP data structure
g	the graph
newprize	prize to be subtracted
i	the 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()

void graph_show ( const GRAPH * )

Definition at line 3912 of file grphbase.c.

References GRAPH::cost, EAT_FREE, GRAPH::edges, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::tail, and GRAPH::term.

◆ graph_knot_add()

void graph_knot_add	(	GRAPH *	p,
		int	term
	)

add a vertex

Parameters

p	the graph
term	terminal property

Definition at line 2196 of file grphbase.c.

References EAT_LAST, GRAPH::grad, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::ksize, GRAPH::mark, NULL, GRAPH::outbeg, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by buildsolgraph(), compEdges(), graph_grid_create(), graph_load(), graph_obstgrid_create(), graph_pack(), graph_pc_2pc(), graph_pc_2rmw(), graph_pc_2rpc(), graph_pc_getSap(), graph_pc_getSapShift(), graph_voronoiWithRadius(), reduce_bd34(), reduce_bdr(), reduce_ledge(), reduce_npv(), reduce_nts(), reduce_sd(), reduce_sdPc(), SCIPprobdataWriteSolution(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), and SCIPStpHeurRecExclude().

◆ graph_knot_chg()

void graph_knot_chg	(	GRAPH *	p,
		int	node,
		int	term
	)

change terminal property of a vertex

Parameters

p	the graph
node	node to be changed
term	terminal property

Definition at line 2218 of file grphbase.c.

References Is_term, NULL, GRAPH::term, and GRAPH::terms.

Referenced by compEdges(), graph_grid_create(), graph_knot_contract(), graph_load(), graph_obstgrid_create(), graph_pc_2mw(), graph_pc_2org(), graph_pc_2pc(), graph_pc_2rmw(), graph_pc_2rpc(), graph_pc_2trans(), graph_pc_contractEdge(), graph_pc_getRsap(), graph_pc_getSapShift(), graph_pc_mw2rmw(), initReceivedSubproblem(), redbasedVarfixing(), reduce_bound(), reduce_boundHop(), reduce_boundPrune(), reduce_sd(), reduce_sl(), SCIP_DECL_CONSSEPALP(), selectBranchingVertexBySol(), and STPStpBranchruleParseConsname().

◆ graph_knot_del()

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

delete node

Parameters

scip	SCIP data structure
g	the graph
k	the node
freeancestors	free 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()

void graph_edge_add	(	SCIP *	,
		GRAPH *	,
		int	,
		int	,
		double	,
		double
	)

Referenced by buildsolgraph(), graph_load(), graph_voronoiWithRadius(), reduce_bd34(), reduce_bdr(), reduce_ledge(), reduce_npv(), reduce_nts(), reduce_sd(), reduce_sdPc(), SCIPprobdataWriteSolution(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), and SCIPStpHeurRecExclude().

◆ graph_edge_del()

void graph_edge_del	(	SCIP *	scip,
		GRAPH *	g,
		int	e,
		SCIP_Bool	freeancestors
	)

delete an edge

Parameters

scip	SCIP data structure
g	the graph
e	the edge
freeancestors	free edge ancestors?

Definition at line 2837 of file grphbase.c.

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

Referenced by adjust0term(), ansProcessCandidate(), getlecloseterms(), graph_edge_redirect(), graph_knot_contract(), graph_knot_del(), graph_pc_contractEdge(), graph_pc_deleteTerm(), graph_pc_getRsap(), graph_pc_getSapShift(), graph_pc_mw2rmw(), level0(), level0save(), redbasedVarfixing(), reduce_bound(), reduce_boundHop(), reduce_boundHopR(), reduce_boundHopRc(), reduce_boundMw(), reduce_boundPrune(), reduce_chain2(), reduce_cnsAdv(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), reduce_deleteConflictEdges(), reduce_extendedEdge(), reduce_ledge(), reduce_nnp(), reduce_npv(), reduce_sd(), reduce_sdPc(), reduce_sdsp(), reduce_sdspSap(), reduce_simple(), reduce_simple_hc(), reduce_simple_mw(), reduce_simple_pc(), reduce_simple_sap(), reducePcMw(), reduceSPG(), reduceWithEdgeFixingBounds(), SCIPStpHeurPruneRun(), SCIPStpHeurSlackPruneRun(), SCIPStpHeurSlackPruneRunPcMw(), traverseChain(), and trydg1edgepc().

◆ graph_edge_hide()

void graph_edge_hide	(	GRAPH *	g,
		int	e
	)

hide edge

Parameters

g	the graph
e	the 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

scip	SCIP data structure
g	the graph
e	the 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

g the 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

g	the new graph
i	node 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()

void graph_free	(	SCIP *	scip,
		GRAPH **	graph,
		SCIP_Bool	final
	)

free the graph

Parameters

scip	SCIP data structure
graph	graph to be freed
final	delete ancestor data structures?

Definition at line 3674 of file grphbase.c.

References GRAPH::cost, GRAPH::grad, graph_free_history(), graph_free_historyDeep(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, GRAPH::mark, GRAPH::maxdeg, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, GRAPH::rootedgeprevs, SCIPfreeMemory, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, STP_DCSTP, STP_RSMT, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and GRAPH::term2edge.

Referenced by graph_pack(), initReceivedSubproblem(), reduce_bd34(), reduce_bdr(), reduce_bound(), reduce_boundHop(), reduce_boundPrune(), reduce_daPcMw(), reduce_daSlackPruneMw(), reduce_ledge(), reduce_npv(), reduce_nts(), reduce_sd(), reduce_sdPc(), SCIP_DECL_PROBDELORIG(), SCIP_DECL_PROPEXITSOL(), SCIPprobdataWriteSolution(), SCIPStpDualAscentPcMw(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

◆ graph_free_history()

void graph_free_history	(	SCIP *	scip,
		GRAPH *	p
	)

free the history

Parameters

scip	SCIP data
p	graph 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

scip	SCIP data
p	graph 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

graph	the graph
nnodes	number of nodes
nedges	number of edges
nterms	number 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

g	graph data structure
solnode	solution nodes array (TRUE/FALSE)
listnode	edge 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()

void graph_pc_2org ( GRAPH * graph )

mark terminals and switch terminal property to original terminals

Parameters

graph the graph

Definition at line 964 of file grphbase.c.

References GRAPH::extended, FALSE, GRAPH::grad, graph_knot_chg(), Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::source, STP_RMWCSP, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by findDaRoots(), graph_pc_2orgcheck(), markPcMwRoots(), redLoopMw(), redLoopPc(), reduce_bound(), reduce_da(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), reduceSPG(), SCIPStpHeurPruneRun(), and SCIPStpHeurRecRun().

◆ graph_pc_2trans()

void graph_pc_2trans ( GRAPH * graph )

unmark terminals and switch terminal property to transformed terminals

Parameters

graph the graph

Definition at line 1002 of file grphbase.c.

References GRAPH::extended, GRAPH::grad, graph_knot_chg(), Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::source, GRAPH::term, and TRUE.

Referenced by findDaRoots(), graph_pc_2transcheck(), markPcMwRoots(), redLoopMw(), redLoopPc(), reduce_bound(), reduce_da(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), SCIPStpHeurPruneRun(), and SCIPStpHeurRecRun().

◆ graph_pc_2orgcheck()

void graph_pc_2orgcheck ( GRAPH * graph )

graph_pc_2org if extended

Parameters

graph the 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

graph the 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

scip	SCIP data structure
bigM	new big M value
graph	the SAP graph
offset	the 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

scip	SCIP data structure
g	the 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

scip	SCIP data structure
g	the graph
sizeprize	size of prize array to allocate (or -1)
sizeterm2edge	size 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()

SCIP_RETCODE graph_pc_2pc	(	SCIP *	scip,
		GRAPH *	graph
	)

alters the graph for prize collecting problems

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 1516 of file grphbase.c.

References GRAPH::edges, GRAPH::esize, GRAPH::extended, FARAWAY, flipedge, graph_edge_add(), graph_knot_add(), graph_knot_chg(), graph_pc_init(), graph_resize(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::ksize, nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, nterms, NULL, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), GRAPH::source, STP_MWCSP, STP_PCSPG, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, GRAPH::terms, and TRUE.

Referenced by graph_load(), and graph_pc_2mw().

◆ graph_pc_2rpc()

SCIP_RETCODE graph_pc_2rpc	(	SCIP *	scip,
		GRAPH *	graph
	)

alters the graph for rooted prize collecting problems

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 1597 of file grphbase.c.

References GRAPH::edges, GRAPH::esize, GRAPH::extended, FARAWAY, flipedge, graph_edge_add(), graph_knot_add(), graph_knot_chg(), graph_pc_init(), graph_resize(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::ksize, nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, nterms, NULL, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), GRAPH::source, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, GRAPH::terms, and TRUE.

Referenced by graph_load().

◆ graph_pc_2mw()

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

alters the graph for MWCS problems

Parameters

scip	SCIP data structure
graph	the graph
maxweights	array 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()

SCIP_RETCODE graph_pc_2rmw	(	SCIP *	scip,
		GRAPH *	graph
	)

alters the graph for RMWCS problems

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 1737 of file grphbase.c.

References GRAPH::cost, EAT_LAST, GRAPH::edges, GRAPH::esize, GRAPH::extended, FARAWAY, flipedge, GRAPH::grad, graph_edge_add(), graph_knot_add(), graph_knot_chg(), graph_pc_init(), graph_resize(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::ksize, nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, NULL, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), SCIPisGT(), SCIPisLT(), GRAPH::source, STP_RMWCSP, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, GRAPH::terms, and TRUE.

Referenced by graph_load().

◆ graph_pc_mw2rmw()

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

transforms MWCSP to RMWCSP if possible

Parameters

scip	SCIP data structure
graph	the graph
prizesum	sum 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
	)

alters the graph for prize collecting problems

Parameters

scip	SCIP data structure
graph	the graph
newgraph	the new graph
offset	offset

Definition at line 1075 of file grphbase.c.

References GRAPH::cost, EAT_LAST, GRAPH::edges, GRAPH::esize, FARAWAY, flipedge, graph_copy(), graph_edge_add(), graph_edge_redirect(), graph_knot_add(), graph_pc_presolExit(), graph_pc_presolInit(), graph_resize(), Is_pterm, Is_term, GRAPH::knots, GRAPH::ksize, nnodes, nterms, NULL, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_SAP, GRAPH::stp_type, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by reduce_daPcMw(), reduce_daSlackPruneMw(), and SCIPStpDualAscentPcMw().

◆ graph_pc_getSapShift()

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

alters the graph for prize collecting problems and shifts weights to reduce number of terminal

Parameters

scip	SCIP data structure
graph	the graph
newgraph	the new graph
offset	offset

Definition at line 1204 of file grphbase.c.

References GRAPH::cost, EAT_LAST, GRAPH::edges, GRAPH::esize, GRAPH::extended, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_copy(), graph_edge_add(), graph_edge_del(), graph_edge_redirect(), graph_knot_add(), graph_knot_chg(), graph_resize(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pterm, Is_term, GRAPH::knots, GRAPH::ksize, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisGE(), SCIPisGT(), SCIPisLT(), GRAPH::source, STP_MWCSP, STP_PCSPG, STP_SAP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

◆ 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

scip	SCIP data structure
graph	the graph
newgraph	the new graph
rootcands	array containing all vertices that could be used as root
nrootcands	number of all vertices could be used as root
root	the 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

scip	SCIP data structure
g	the graph
t	tail node to be contracted (surviving node)
s	head node to be contracted
ets	edge 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

scip	SCIP data structure
g	the graph
solnode	solution nodes or NULL
t	tail node to be contracted (surviving node)
s	head node to be contracted
i	terminal 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

scip	SCIP data structure
g	graph to be resized
ksize	new node slots
esize	new edge slots
layers	layers (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

scip	SCIP data structure
p	graph data structure
solnode	node array to mark whether an node is part of a given solution (CONNECT), or NULL
t	tail node to be contracted
s	head 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

scip	SCIP data structure
g	graph data structure
solnode	node array to mark whether an node is part of a given solution (CONNECT), or NULL
t	tail node to be contracted
s	head 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

scip	SCIP data structure
g	the graph
result	solution array (CONNECT/UNKNOWN)
newroot	the 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

scip	SCIP data structure
transgraph	the transformed graph
orggraph	the original graph
transsoledge	solution for transformed problem
orgsoledge	new 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

scip	SCIP data structure
pcancestors	the ancestors
tails	tails array
heads	heads array
orgnnodes	original number of nodes
solnodemark	solution nodes mark array
soledgemark	solution edges mark array or NULL
solnodequeue	solution nodes queue or NULL
nsolnodes	number of solution nodes or NULL
nsoledges	number 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

scip	SCIP data structure
g	the graph
e1	edge to reinsert
k1	tail
k2	head
cost	edge cost
ancestors0	ancestors of first edge
ancestors1	ancestors of second edge
revancestors0	reverse ancestors of first edge
revancestors1	reverse ancestors of first edge
forcedelete	delete 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

scip	SCIP data structure
g	the graph
edgecosts	edge costs for cutoff
cutoffs	cutoff values for each incident edge
cutoffsrev	revere cutoff values (or NULL if undirected)
vertex	the vertex
success	has 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

scip	SCIP data structure
gridgraph	the grid graph to be constructed
coords	coordinates
nterms	number of terminals
grid_dim	problem dimension
scale_order	scale 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

scip	SCIP data structure
gridgraph	the (obstacle) grid graph to be constructed
coords	coordinates of all points
obst_coords	coordinates of obstacles
nterms	number of terminals
grid_dim	dimension of the problem
nobstacles	number of obstacles
scale_order	scale 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

scip	SCIP data structure
coords	coordinates
nodecoords	coordinates of the node (to be computed)
ncoords	array with number of coordinate
node	the node
grid_dim	problem dimension

Definition at line 730 of file grphbase.c.

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.

Referenced by SCIPprobdataWriteSolution().

◆ graph_copy_data()

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

copy the data of the graph

Parameters

scip	SCIP data structure
orgraph	original graph
copygraph	graph to be copied to

Definition at line 3805 of file grphbase.c.

References BMScopyMemoryArray, GRAPH::cost, GRAPH::edges, GRAPH::esize, GRAPH::extended, GRAPH::grad, graph_valid(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, GRAPH::head, GRAPH::hoplimit, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::ksize, GRAPH::mark, GRAPH::maxdeg, GRAPH::norgmodeledges, GRAPH::norgmodelknots, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::orgknots, GRAPH::orgsource, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, GRAPH::source, STP_DCSTP, STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_RSMT, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::term2edge, and GRAPH::terms.

Referenced by graph_copy(), and redbasedVarfixing().

◆ graph_copy()

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

copy the graph

Parameters

scip	SCIP data structure
orgraph	original graph
copygraph	graph to be created

Definition at line 3896 of file grphbase.c.

References GRAPH::esize, graph_copy_data(), graph_init(), GRAPH::ksize, GRAPH::layers, NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by graph_pc_getRsap(), graph_pc_getSap(), graph_pc_getSapShift(), initReceivedSubproblem(), SCIP_DECL_PROBCOPY(), SCIP_DECL_PROPEXEC(), SCIPprobdataCreate(), SCIPStpHeurPruneRun(), SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

◆ graph_pack()

SCIP_RETCODE graph_pack	(	SCIP *	scip,
		GRAPH *	graph,
		GRAPH **	newgraph,
		SCIP_Bool	verbose
	)

pack the graph, i.e. build a new graph that discards deleted edges and nodes

Parameters

scip	SCIP data structure
graph	the graph
newgraph	the new graph
verbose	verbose?

Definition at line 3984 of file grphbase.c.

References GRAPH::ancestors, GRAPH::cost, EAT_FREE, EAT_LAST, Edge_anti, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, GRAPH::fixedges, GRAPH::grad, graph_edge_add(), graph_free(), graph_init(), graph_knot_add(), graph_path_exit(), graph_pc_init(), graph_pc_updateTerm2edge(), graph_valid(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, GRAPH::head, GRAPH::hoplimit, GRAPH::ieat, Is_term, GRAPH::knots, GRAPH::layers, GRAPH::mark, GRAPH::maxdeg, nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::orghead, GRAPH::orgknots, GRAPH::orgsource, GRAPH::orgtail, GRAPH::outbeg, GRAPH::path_heap, GRAPH::pcancestors, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPfreeBufferArray, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), SCIPisGT(), GRAPH::source, STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_RSMT, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and UNKNOWN.

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

◆ 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

scip	scip struct
g	the new graph
i	node 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 *
	)

Definition at line 3448 of file grphbase.c.

References GRAPH::ancestors, GRAPH::edges, NULL, GRAPH::orgedges, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, and SCIPfreeBufferArray.

◆ graph_init()

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

initialize graph

Parameters

scip	SCIP data structure
g	new graph
ksize	slots for nodes
esize	slots for edges
layers	number 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()

SCIP_RETCODE graph_init_history	(	SCIP *	scip,
		GRAPH *	graph
	)

initialize data structures required to keep track of reductions

Parameters

scip	SCIP data structure
graph	graph

Definition at line 3569 of file grphbase.c.

References GRAPH::ancestors, GRAPH::edges, graph_pc_isPcMw(), GRAPH::head, GRAPH::knots, nnodes, NULL, GRAPH::orghead, GRAPH::orgtail, GRAPH::pcancestors, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocMemoryArray, and GRAPH::tail.

Referenced by initReceivedSubproblem(), redbasedVarfixing(), reduce(), reduce_daPcMw(), reduce_daSlackPruneMw(), SCIP_DECL_PROPEXEC(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurPruneRun(), SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

◆ graph_termsReachable()

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

checks whether all terminals are reachable from root

Parameters

scip	scip struct
g	the new graph
reachable	are 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

scip	SCIP data structure
g	the 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()

int graph_edge_redirect	(	SCIP *	,
		GRAPH *	,
		int	,
		int	,
		int	,
		SCIP_Real	,
		SCIP_Bool
	)

Definition at line 2681 of file grphbase.c.

References GRAPH::cost, EAT_FREE, EAT_LAST, Edge_anti, FALSE, GRAPH::grad, graph_edge_del(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, NULL, GRAPH::oeat, GRAPH::outbeg, SCIPisGT(), and GRAPH::tail.

Referenced by graph_edge_reinsert(), graph_pc_getRsap(), graph_pc_getSap(), graph_pc_getSapShift(), graph_pc_mw2rmw(), reduce_simple_pc(), and traverseChain().

◆ graph_pc_deleteTerm()

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

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

Parameters

scip	SCIP data structure
g	graph data structure
i	index 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()

SCIP_Bool graph_valid ( const GRAPH * g )

is the given graph valid?

Parameters

g	the new graph

Definition at line 4324 of file grphbase.c.

References GRAPH::cost, EAT_FREE, EAT_LAST, GRAPH::edges, GRAPH::extended, FALSE, GRAPH::grad, graph_trail(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIPdebugMessage, GRAPH::source, STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::term2edge, GRAPH::terms, and TRUE.

Referenced by buildsolgraph(), computeNewSols(), computePertubedSol(), computeSteinerTree(), getlecloseterms(), graph_copy_data(), graph_load(), graph_pack(), graph_save(), nvreduce_sl(), redbasedVarfixing(), redLoopStp(), reduce(), reduce_ans(), reduce_ansAdv(), reduce_ansAdv2(), reduce_bd34(), reduce_bound(), reduce_boundHop(), reduce_boundHopR(), reduce_boundHopRc(), reduce_boundPrune(), reduce_da(), reduce_daPcMw(), reduce_ledge(), reduce_nnp(), reduce_nts(), reduce_sdPc(), reduce_sdsp(), reduce_simple(), reduce_simple_mw(), reduce_simple_pc(), reduce_simple_sap(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

◆ graph_pc_term2edgeConsistent()

SCIP_Bool graph_pc_term2edgeConsistent ( const GRAPH * g )

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

Parameters

g the 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

scip	SCIP data structure
graph	graph data structure
result	solution 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()

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

verifies whether a given primal solution is feasible

Parameters

scip	SCIP data structure
graph	graph data structure
result	solution array, indicating whether an edge is in the solution

Definition at line 3066 of file grphbase.c.

References CONNECT, EAT_LAST, GRAPH::extended, FALSE, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pterm, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::source, STP_MWCSP, STP_PCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by computeDaSolPcMw(), computePertubedSol(), graph_sol_getOrg(), reduce_da(), reduce_daPcMw(), reduce_daSlackPruneMw(), reducePcMw(), reducePcMwTryBest(), reduceWithEdgeFixingBounds(), SCIP_DECL_HEUREXEC(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurPruneUpdateSols(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), SCIPStpHeurSlackPruneRunPcMw(), SCIPStpHeurTMPrunePc(), and selectBranchingVertexBySol().

◆ graph_pc_isPcMw()

SCIP_Bool graph_pc_isPcMw ( const GRAPH * g )

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

Parameters

g the 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
	)

compute solution value for given edge-solution array (CONNECT/UNKNOWN) and offset

Definition at line 3196 of file grphbase.c.

References CONNECT, and SCIP_Real.

Referenced by computeDaSolPcMw(), computePertubedSol(), reduce_da(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), SCIP_DECL_HEUREXEC(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurPruneUpdateSols(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

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

void graph_path_exit	(	SCIP *	,
		GRAPH *
	)

◆ graph_path_exec()

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

Definition at line 491 of file grphpath.c.

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

Referenced by central_terminal(), createVariables(), getlecloseterms(), pricing(), reduce_bd34(), reduce_bdr(), reduce_bound(), reduce_boundHop(), reduce_boundPrune(), reduce_daSlackPrune(), reduce_ledge(), reduce_npv(), reduce_nts(), reduce_sd(), SCIPprobdataAddNewSol(), SCIPStpHeurLocalRun(), SCIPStpHeurTMBuildTree(), SCIPStpHeurTMBuildTreePcMw(), SCIPStpHeurTMPrune(), and SCIPStpHeurTMPrunePc().

◆ 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

scip	SCIP data structure
g	graph data structure
start	start vertex
cost	edge costs
pathdist	distance array (on vertices)
pathedge	predecessor 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

scip	SCIP data structure
g	graph data structure
start	start vertex
cost	edge costs
pathdist	distance array (on vertices)
pathedge	predecessor 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

scip	SCIP data structure
g	graph data structure
cost	edgecosts
pathdist	distance array (on vertices)
pathedge	predecessor edge array (on vertices)
start	start vertex
randnumgen	random number generator
connected	array 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

scip	SCIP data structure
g	graph data structure
cost	edge costs
pathdist	distance array (on vertices)
pathedge	predecessor edge array (on vertices)
start	start vertex
connected	array 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

scip	SCIP data structure
g	graph data structure
cost	edge costs
pathdist	distance array (on vertices)
pathedge	predecessor edge array (on vertices)
start	start vertex
connected	array 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

scip	SCIP data structure
g	graph data structure
cost	edge costs
pathdist	distance array (on vertices)
pathedge	predecessor edge array (on vertices)
start	start vertex
connected	array 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

scip	SCIP data structure
g	graph data structure
cost	edge costs
tmpnodeweight	node weight array
result	incoming arc array
start	start vertex
connected	array 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

scip	SCIP data structure
g	graph data structure
cost	edge costs
path	shortest paths data structure
connected	array to mark whether a vertex is part of computed Steiner tree
extensions	extensions 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

scip	SCIP data structure
g	graph data structure
cost	edge costs
pathdist	distance array (on vertices)
pathedge	predecessor edge array (on vertices)
start	start vertex
connected	array 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

scip	SCIP data structure
g	graph data structure
cost	edge costs
costrev	reversed edge costs
base	array to indicate whether a vertex is a Voronoi base
vbase	voronoi base to each vertex
path	path 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

scip	SCIP data structure
g	graph data structure
cost	edge costs
costrev	reversed edge costs
path	path data structure (leading to first and second nearest terminal)
vbase	first and second nearest terminal to each non terminal
heap	array representing a heap
state	array 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 *
	)

Definition at line 1934 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(), and reduce_boundPrune().

◆ graph_get4next()

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

Definition at line 2041 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_get4nextTerms(), and reduce_bound().

◆ 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

scip	SCIP data structure
g	graph data structure
cost	edge costs
costrev	reversed edge costs
path3	path data struture (leading to first, second and third nearest terminal)
vbase	first, second and third nearest terminal to each non terminal
heap	array representing a heap
state	array 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

scip	SCIP data structure
g	graph data structure
cost	edge costs
costrev	reversed edge costs
path	path data struture (leading to first, second, third and fouth nearest terminal)
vbase	first, second and third nearest terminal to each non terminal
heap	array representing a heap
state	array 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

scip	SCIP data structure
g	graph data structure
costrev	reversed edge costs
path	path data structure (leading to respective Voronoi base)
vbase	Voronoi base to each vertex
heap	array representing a heap
state	array 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

scip	SCIP data structure
g	graph data structure
cost	edge costs
path	path data structure (leading to respective Voronoi base)
vbase	Voronoi base to each vertex
heap	array representing a heap
state	array 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

scip	SCIP data structure
g	graph data structure
cost	edge costs
count	pointer to number of heap elements
vbase	array containing Voronoi base of each node
path	Voronoi paths data struture
newedge	the new edge
crucnode	the current crucial node
uf	union 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

scip	SCIP data structure
g	graph data structure
cost	edge costs
count	pointer to number of heap elements
vbase	array containing Voronoi base of each node
boundedges	boundary edges
nboundedges	number of boundary edges
nodesmark	array to mark temporarily discarded nodes
uf	union find data structure
path	Voronoi 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

scip	SCIP data structure
g	graph data structure
path	shortest paths data structure
cost	edge costs
distlimit	distance limit of the search
heap	array representing a heap
state	array to indicate whether a node has been scanned during SP calculation
memlbl	array to save labelled nodes
nlbl	number of labelled nodes
tail	tail of the edge
head	head of the edge
limit	maximum 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

scip	SCIP data structure
g	graph data structure
path	shortest paths data structure
cost	edge costs
distlimit	distance limit of the search
pathmaxnode	maximum weight node on path
heap	array representing a heap
state	array to indicate whether a node has been scanned during SP calculation
stateblock	array to indicate whether a node has been scanned during previous SP calculation
memlbl	array to save labelled nodes
nlbl	number of labelled nodes
tail	tail of the edge
head	head of the edge
limit	maximum 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

scip	SCIP data structure
g	graph data structure
path	array containing graph decomposition data
cost	edge costs
radius	array storing shortest way from a positive vertex out of its region
vbase	array containing base of each node
heap	array representing a heap
state	array 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

scip	SCIP data structure
g	graph data structure
cost	edgecosts
path	shortest paths data structure
distarr	array to store distance from each node to its base
basearr	array to store the bases
edgearr	array to store the ancestor edge
termsmark	array to mark terminal
reachednodes	array to mark reached nodes
nreachednodes	pointer to number of reached nodes
nodenterms	array to store number of terimals to each node
nneighbterms	number of neighbouring terminals
base	voronoi base
countex	count 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()

SCIP_RETCODE graph_path_init	(	SCIP *	,
		GRAPH *
	)

◆ 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

scip	SCIP data structure
graph	graph data structure
adjgraph	graph data structure
path	array containing Voronoi paths data
rad	array storing shortest way from a terminal out of its Voronoi region
cost	edge costs
costrev	reversed edge costs
vbase	array containing Voronoi base of each node
heap	array representing a heap
state	array 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

scip	SCIP data structure
g	graph data structure
cost	edge costs
path	path data structure (leading to first, second, third and fourth nearest terminal)
vbase	first, second and third nearest terminal to each non terminal
heap	array representing a heap
state	array 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
	)

frees min cut arrays

Parameters

scip	SCIP data structure
p	graph data structure

Definition at line 305 of file grphmcut.c.

References GRAPH::knots, GRAPH::mincut_dist, GRAPH::mincut_e, GRAPH::mincut_head, GRAPH::mincut_head_inact, GRAPH::mincut_next, GRAPH::mincut_numb, GRAPH::mincut_prev, GRAPH::mincut_r, GRAPH::mincut_temp, nnodes, NULL, and SCIPfreeMemoryArray.

Referenced by graph_mincut_exec(), initReceivedSubproblem(), and SCIP_DECL_PROBDELORIG().

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

SCIP_RETCODE graph_mincut_init	(	SCIP *	scip,
		GRAPH *	p
	)

initialize min cut arrays

Parameters

scip	SCIP data structure
p	graph data structure

Definition at line 275 of file grphmcut.c.

References GRAPH::edges, GRAPH::knots, GRAPH::mincut_dist, GRAPH::mincut_e, GRAPH::mincut_head, GRAPH::mincut_head_inact, GRAPH::mincut_next, GRAPH::mincut_numb, GRAPH::mincut_prev, GRAPH::mincut_r, GRAPH::mincut_temp, GRAPH::mincut_x, NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.

Referenced by graph_mincut_exec(), initReceivedSubproblem(), SCIP_DECL_PROBCOPY(), and SCIPprobdataCreate().

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

void SCIPwriteStp	(	SCIP *	,
		const GRAPH *	,
		FILE *	,
		SCIP_Real
	)

Definition at line 38 of file grphsave.c.

References GRAPH::cost, EAT_FREE, EAT_LAST, Edge_anti, GRAPH::edges, GRAPH::head, GRAPH::hoplimit, GRAPH::ieat, Is_term, GRAPH::knots, NULL, GRAPH::oeat, GRAPH::outbeg, SCIPisEQ(), GRAPH::source, STP_DCSTP, STP_DHCSTP, STP_MAGIC, STP_MWCSP, STP_NWSPG, STP_OARSMT, STP_PCSPG, STP_RPCSPG, STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, VERSION_MAJOR, and VERSION_MINOR.

Referenced by SCIP_DECL_READERWRITE().

◆ level0()

SCIP_RETCODE level0	(	SCIP *	,
		GRAPH *
	)

Definition at line 153 of file reduce.c.

References EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), graph_trail_arr(), GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, SCIP_CALL, SCIP_OKAY, GRAPH::source, GRAPH::term, and TRUE.

Referenced by redbasedVarfixing(), redLoopMw(), redLoopStp(), reduce(), reduce_da(), reduce_ledge(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurPruneRun(), SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

◆ level0save()

SCIP_RETCODE level0save	(	SCIP *	,
		GRAPH *
	)

Definition at line 185 of file reduce.c.

References BMScopyMemoryArray, EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), graph_trail_arr(), GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::source, GRAPH::term, and TRUE.

Referenced by reduce_simple_mw(), and reduce_simple_pc().

◆ 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

scip	SCIP data structure
graph	graph data structure
fixed	pointer to store the offset value
minelims	minimal number of edges to be eliminated in order to reiterate reductions
dualascent	perform dual-ascent reductions?
nodereplacing	should node replacement (by edges) be performed?
userec	use 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

scip	SCIP data structure
g	graph data structure
vnoi	Voronoi data structure
path	path data structure
gnodearr	nodes-sized array
nodearrreal	nodes-sized array
edgearrreal	edges-sized array
edgearrreal2	edges-sized array
heap	heap array
state	shortest path array
vbase	Voronoi base array
nodearrint	edges-sized array
edgearrint	nodes-sized array
nodearrint2	nodes-sized array
solnode	solution nodes array (or NULL)
nodearrchar	nodes-sized array
fixed	pointer to store the offset value
upperbound	upper bound
dualascent	do dual-ascent reduction?
boundreduce	do bound-based reduction?
nodereplacing	should node replacement (by edges) be performed?
reductbound	minimal number of edges to be eliminated in order to reiterate reductions
userec	use recombination heuristic?
fullreduce	use full reductions? (including extended techniques)

Definition at line 1411 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

scip	SCIP data structure
g	graph data structure
vnoi	Voronoi data structure
path	path data structure
gnodearr	nodes-sized array
nodearrreal	nodes-sized array
exedgearrreal	edges-sized array
exedgearrreal2	edges-sized array
heap	shortest path array
state	voronoi base array
vbase	nodes-sized array
nodearrint	edges-sized array
edgearrint	nodes-sized array
nodearrint2	nodes-sized array
solnode	solution nodes array (or NULL)
nodearrchar	nodes-sized array
fixed	pointer to store the offset value
dualascent	do dual-ascent reduction?
bred	do bound-based reduction?
reductbound	minimal number of edges to be eliminated in order to reiterate reductions
userec	use recombination heuristic?

Definition at line 1160 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

scip	SCIP data structure
g	graph data structure
vnoi	Voronoi data structure
path	path data structure
gnodearr	nodes-sized array
nodearrreal	nodes-sized array
edgearrreal	edges-sized array
edgearrreal2	edges-sized array
state	shortest path array
vbase	voronoi base array
nodearrint	nodes-sized array
edgearrint	edges-sized array
nodearrint2	nodes-sized array
nodearrint3	nodes-sized array
solnode	array to indicate whether a node is part of the current solution (==CONNECT)
nodearrchar	nodes-sized array
fixed	pointer to store the offset value
advanced	do advanced reduction?
bred	do bound-based reduction?
tryrmw	try to convert problem to RMWCSP? Only possible if advanced = TRUE and userec = TRUE
redbound	minimal number of edges to be eliminated in order to reiterate reductions
userec	use recombination heuristic?

Definition at line 923 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

scip	SCIP data structure
graph	graph structure
offset	pointer to store offset generated by reductions
level	reduction level 0: none, 1: basic, 2: advanced
minelims	minimal amount of reductions to reiterate reduction methods
userec	use recombination heuristic?

Definition at line 1675 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

scip	SCIP data structure
g	graph data structure
marked	nodes array
count	pointer 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

scip	SCIP data structure
g	graph data structure
marked	nodes array
count	pointer to number of performed reductions
extneigbhood	use 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

scip	SCIP data structure
g	graph data structure
marked	nodes array
count	pointer 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

scip	SCIP data structure
g	graph data structure
marked	nodes array
count	pointer 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
	)

SD test using only limited dijkstra from both endpoints of an edge

Definition at line 2459 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, EDGE_BLOCKED, FALSE, FARAWAY, GRAPH::grad, graph_edge_del(), graph_path_PcMwSd(), graph_sdPaths(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArrayNull, SCIPisGE(), SCIPisGT(), SCIPisLT(), SCIPisNegative(), SCIPisPositive(), STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by redLoopPc(), and redLoopStp().

◆ 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

scip	SCIP data structure
g	graph data structure
vnoi	Voronoi data structure
edgepreds	array to store edge predecessors of auxiliary graph
mstsdist	array to store mst distances in auxiliary graph
heap	array representing a heap
state	array to indicate whether a node has been scanned during SP calculation
vbase	Voronoi base to each vertex
nodesid	array to map nodes in auxiliary graph to original ones
nodesorg	array to map terminals of original graph vertices of auxiliary graph
forbidden	array to mark whether an edge may be eliminated
nelims	point to store number of deleted edges
nodereplacing	should node replacement (by edges) be performed?
edgestate	array 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

scip	SCIP data structure
g	graph data structure
vnoi	Voronoi data structure
heap	heap array
state	array to store state of a node during Voronoi computation
vbase	Voronoi base to each node
nodesid	array
nodesorg	array
nelims	pointer 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
	)

get SD to a single edge

Definition at line 1970 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, graph_sdPaths(), GRAPH::head, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPisGT(), SCIPisLE(), SCIPisLT(), GRAPH::term, and UNKNOWN.

Referenced by reduce_bd34(), reduce_chain2(), reduce_npv(), and reduce_nts().

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

get SD to a single edge

Definition at line 2110 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, graph_path_PcMwSd(), GRAPH::head, Is_term, GRAPH::knots, misc_stp_maxReal(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGT(), SCIPisNegative(), SCIPisPositive(), STP_MWCSP, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, and UNKNOWN.

Referenced by reduce_bd34(), and reduce_nts().

◆ 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

scip	SCIP data structure
g	graph structure
pathtail	array for internal use
pathhead	array for internal use
heap	array for internal use
statetail	array for internal use
statehead	array for internal use
memlbltail	array for internal use
memlblhead	array for internal use
nelims	point to return number of eliminations
limit	limit 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()

SCIP_RETCODE reduce_bd34	(	SCIP *	,
		GRAPH *	,
		PATH *	,
		PATH *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int
	)

Definition at line 2964 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, FALSE, FARAWAY, flipedge, 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_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(), SCIPisLE(), SCIPisLT(), STP_BD_MAXDEGREE, STP_BD_MAXDNEDGES, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by redLoopPc(), and redLoopStp().

◆ 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

scip	SCIP data structure
g	graph structure
netgraph	auxiliary graph structure
netmst	MST structure
vnoi	path structure
mstsdist	MST distance in aux-graph
termdist1	dist array
termdist2	second dist array
vbase	bases for nearest terminals
nodesid	nodes identification array
neighbterms1	neighbour terminals array
neighbterms2	second neighbour terminals array
nelims	number 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()

SCIP_RETCODE reduce_nv	(	SCIP *	,
		GRAPH *	,
		PATH *	,
		double *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *
	)

◆ reduce_nvAdv()

SCIP_RETCODE reduce_nvAdv	(	SCIP *	,
		GRAPH *	,
		PATH *	,
		SCIP_Real *	,
		double *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *
	)

Definition at line 3903 of file reduce_alt.c.

References GRAPH::ancestors, GRAPH::cost, shortest_path::dist, EAT_LAST, FALSE, FARAWAY, GRAPH::fixedges, flipedge, GRAPH::grad, graph_knot_contract(), graph_pc_contractEdge(), graph_voronoiWithDist(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPintListNodeAppendCopy(), SCIPisGE(), SCIPisLE(), SCIPisLT(), GRAPH::source, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by nvreduce_sl().

◆ reduce_sl()

SCIP_RETCODE reduce_sl	(	SCIP *	,
		GRAPH *	,
		PATH *	,
		double *	,
		int *	,
		int *	,
		int *	,
		int *	,
		STP_Bool *	,
		int *	,
		int *
	)

Definition at line 3483 of file reduce_alt.c.

References GRAPH::ancestors, GRAPH::cost, shortest_path::dist, EAT_LAST, FALSE, FARAWAY, GRAPH::fixedges, GRAPH::grad, graph_knot_chg(), graph_knot_contract(), graph_pc_contractEdge(), graph_voronoiTerms(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPintListNodeAppendCopy(), SCIPisGE(), SCIPisLE(), SCIPisLT(), SCIPqueueCreate(), SCIPqueueFree(), SCIPqueueInsert(), SCIPqueueIsEmpty(), SCIPqueueRemove(), GRAPH::source, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by nvreduce_sl().

◆ reduce_ledge()

SCIP_RETCODE reduce_ledge	(	SCIP *	,
		GRAPH *	,
		PATH *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *
	)

Definition at line 4143 of file reduce_alt.c.

References BMSclearMemoryArray, CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, Edge_anti, EDGE_BLOCKED, GRAPH::edges, FALSE, GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_free(), graph_init(), graph_knot_add(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_valid(), graph_voronoiTerms(), GRAPH::head, Is_term, GRAPH::knots, level0(), GRAPH::mark, MST_MODE, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), GRAPH::source, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by redLoopStp().

◆ reduce_cnsAdv()

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

advanced connected neighborhood subset reduction test for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
marked	nodes array for internal use
count	pointer 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
	)

non-positive vertex reduction for the MWCSP

Definition at line 5024 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_free(), graph_init(), graph_knot_add(), 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, GRAPH::prize, reduce_getSd(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), SCIPisGT(), SCIPisLE(), GRAPH::source, GRAPH::term, TRUE, and UNKNOWN.

Referenced by redLoopMw().

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

chain reduction (NPV_2) for the MWCSP

Definition at line 5367 of file reduce_alt.c.

References shortest_path::dist, shortest_path::edge, FALSE, FARAWAY, GRAPH::grad, graph_edge_del(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, reduce_getSd(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), GRAPH::term, TRUE, and UNKNOWN.

Referenced by redLoopMw().

◆ 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

scip	SCIP data structure
g	the 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

scip	SCIP data structure
graph	graph data structure
root	graph root from dual ascent
redcost	reduced costs
pathdist	shortest path distances
vnoi	Voronoi paths
vbase	bases to Voronoi paths
cutoff	cutoff value
outedges	two outgoing edge
inedge	incoming edge
edgestack	array of size nodes for internal computations
treebound	to store a lower bound for the tree
ruleout	could tree be ruled out?
eqstack	stores edges that were used for equality comparison
eqstack_size	pointer to size of eqstack
eqmark	marks 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

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure
gnodearr	GNODE* terminals array for internal computations or NULL
cost	edge costs
costrev	reverse edge costs
pathdist	distance array for shortest path calculations
ub	pointer to provide upper bound and return upper bound found during ascent and prune (if better)
offset	pointer to store offset
edgearrint	int edges array for internal computations or NULL
vbase	array for Voronoi bases
state	int 4 * nnodes array for internal computations
pathedge	array for predecessor edge on a path
nodearrint	int nnodes array for internal computations
heursources	array to store starting points of TM heuristic
nodearrchar	STP_Bool node array for internal computations
nelims	pointer to store number of reduced edges
prevrounds	number of reduction rounds that have been performed already
randnumgen	random number generator
userec	use recombination heuristic?
extended	use 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

scip	SCIP data structure
vars	problem variables or NULL
graph	graph data structure
vnoi	Voronoi data structure
gnodearr	GNODE* terminals array for internal computations or NULL
cost	array to store reduced costs
costrev	reverse edge costs
pathdist	distance array for shortest path calculations
upperbound	pointer to store new upper bound
edgearrint	int edges array to store solution value
edgearrint2	int edges array for internal computations
vbase	array for Voronoi bases
pathedge	array for predecessor edge on a path
state	int 4 * nnodes array for internal computations
solnode	array of nodes of current solution that is not to be destroyed
nodearrchar	STP_Bool node array for internal computations
edgearrchar	STP_Bool edge array for internal computations
nelims	pointer to store number of reduced edges
minelims	minimum number of edges to eliminate
solgiven	solution 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

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure array
gnodearr	GNODE* terminals array for internal computations or NULL
cost	edge costs
costrev	reverse edge costs
pathdist	distance array for shortest path calculations
vbase	Voronoi base array
pathedge	shortest path incoming edge array for shortest path calculations
soledge	edge solution array (CONNECT/UNKNOWN) or NULL; needs to contain solution if solgiven == TRUE
state	int 4 * vertices array
solnode	array of nodes of current solution that is not to be destroyed
nodearrchar	STP_Bool node array for internal computations
nelims	pointer to store number of reduced edges
minelims	minimum number of edges to eliminate
solgiven	solution 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

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure array
gnodearr	GNODE* terminals array for internal computations or NULL
cost	reduced edge costs
costrev	reduced reverse edge costs
pathdist	distance array for shortest path calculations
vbase	Voronoi base array
pathedge	shortest path incoming edge array for shortest path calculations
edgearrint	int edges array for internal computations or NULL
state	int 4 * vertices array
nodearrchar	STP_Bool node array for internal computations
nelims	pointer to store number of reduced edges
solbasedda	rerun Da based on best primal solution
varyroot	vary root for DA if possible
markroots	should terminals proven to be part of an opt. sol. be marked as such?
userec	use recombination heuristic?
fastmode	run heuristic in fast mode?
randnumgen	random number generator
prizesum	sum 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

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure
cost	edge cost array
prize	prize (nodes) array
radius	radius array
costrev	reversed edge cost array
offset	pointer to the offset
upperbound	pointer to an upper bound
heap	heap array
state	array to store state of a node during Voronoi computation
vbase	Voronoi base to each node
nelims	pointer 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

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure (size 3 * nnodes)
path	shortest path data structure (size nnodes)
cost	edge cost array
radius	radius array
costrev	reversed edge cost array
offset	pointer to the offset
heap	heap array
state	array to store state of a node during Voronoi computation
vbase	Voronoi base to each node
result	solution array or NULL
nelims	pointer 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

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure
cost	edge cost array
radius	radius array
costrev	reversed edge cost array
offset	pointer to the offset
heap	heap array
state	array to store state of a node during Voronoi computation
vbase	Voronoi base to each node
solnode	array of nodes of current solution that is not to be destroyed
soledge	array of edges of current solution that is not to be destroyed
nelims	pointer to store number of eliminated edges
minelims	minimum 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()

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

bound-based reduction test for the HCDSTP

Definition at line 5904 of file reduce_bnd.c.

References bound, CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_free(), graph_get2next(), graph_init(), graph_knot_chg(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_valid(), graph_voronoiWithRadius(), GRAPH::head, GRAPH::hoplimit, Is_term, GRAPH::knots, GRAPH::mark, MIN, MST_MODE, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), SCIPisLT(), SCIPsortReal(), GRAPH::source, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reduceHc().

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

hop bound-based reduction test for the HCDSTP

Definition at line 6098 of file reduce_bnd.c.

References bound, GRAPH::cost, shortest_path::dist, EAT_LAST, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_path_execX(), graph_valid(), graph_voronoiTerms(), GRAPH::head, GRAPH::hoplimit, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGT(), SCIPisLT(), GRAPH::source, GRAPH::term, and TRUE.

Referenced by reduceHc().

◆ reduce_boundHopRc()

SCIP_RETCODE reduce_boundHopRc	(	SCIP *	,
		GRAPH *	,
		PATH *	,
		SCIP_Real *	,
		SCIP_Real *	,
		SCIP_Real *	,
		SCIP_Real	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *	,
		SCIP_Bool
	)

Definition at line 6226 of file reduce_bnd.c.

References BLOCKED, bound, CONNECT, GRAPH::cost, DEFAULT_HOPFACTOR, shortest_path::dist, EAT_LAST, GRAPH::edges, FALSE, FARAWAY, fixedgevar(), flipedge, GRAPH::grad, graph_edge_del(), graph_path_execX(), graph_valid(), graph_voronoiTerms(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfindHeur(), SCIPfreeBufferArray, SCIPgetCutoffbound(), SCIPheurGetData(), SCIPisGT(), SCIPisLT(), SCIPprobdataGetVars(), SCIPStpHeurTMRun(), SCIPvarGetUbLocal(), GRAPH::source, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduceHc().

◆ 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

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure
cost	dual ascent costs
pathdist	distance array from shortest path calculations
result	sol int array
minpathcost	the required reduced path cost to be surpassed
root	the root
nodearr	for internal stuff
marked	edge 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

scip	SCIP data structure
g	graph data structure
savehistory	save 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

scip	SCIP data structure
g	graph data structure
fixed	pointer to offset value
solnode	node array to mark whether an node is part of a given solution (CONNECT), or NULL
nelims	pointer to number of reductions
edgestate	array 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

scip	SCIP data structure
g	graph data structure
fixed	pointer to offfset value
count	pointer to number of reductions

Definition at line 1252 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

scip	SCIP data structure
g	graph data structure
solnode	array to indicate whether a node is part of the current solution (==CONNECT)
fixed	pointer to offset value
count	pointer to number of reductions

Definition at line 953 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
	)

basic reductions for RPCSTP and PCSPG

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offset value
count	pointer to number of reductions
solnode	solution nodes
contractroot	contract vertices into root (for rooted prize-collecting)

Definition at line 1330 of file reduce_simple.c.

References adjust0term(), GRAPH::ancestors, GRAPH::cost, EAT_LAST, Edge_anti, GRAPH::extended, FALSE, FARAWAY, GRAPH::fixedges, flipedge, GRAPH::grad, graph_edge_del(), graph_edge_redirect(), graph_knot_contract(), graph_pc_contractEdge(), graph_pc_deleteTerm(), graph_pc_knot2nonTerm(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, is_maxprize(), Is_pterm, Is_term, GRAPH::knots, level0save(), GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::pcancestors, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), SCIPisEQ(), SCIPisLE(), SCIPisLT(), SCIPisZero(), GRAPH::source, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, trydg1edgepc(), and UNKNOWN.

Referenced by nvreduce_sl(), and redLoopPc().

◆ reduce_simple_sap()

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

basic reduction tests for the SAP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offfset value
count	pointer to number of reductions

Definition at line 684 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, Edge_anti, FALSE, FARAWAY, GRAPH::fixedges, flipedge, GRAPH::grad, graph_edge_del(), graph_knot_contract(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPintListNodeAppendCopy(), SCIPisGT(), SCIPisLT(), SCIPqueueCreate(), SCIPqueueFree(), SCIPqueueInsert(), SCIPqueueIsEmpty(), SCIPqueueRemove(), GRAPH::source, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reduceSap().

◆ reduce_rpt()

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

root proximity terminal test (SAP)

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offset value
count	pointer to number of reductions

Definition at line 884 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()

SCIP_RETCODE SCIPStpValidateSol	(	SCIP *	scip,
		const GRAPH *	g,
		const double *	xval,
		SCIP_Bool *	feasible
	)

validates whether a (LP) solution is feasible

Definition at line 136 of file validate.c.

References EAT_LAST, GRAPH::edges, EPSILON, EQ, FALSE, flipedge, GRAPH::grad, GRAPH::knots, GRAPH::layers, GRAPH::maxdeg, nail(), NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocClearBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, GRAPH::source, STP_DCSTP, GRAPH::stp_type, GRAPH::term, trail(), and TRUE.

Referenced by SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFOPS(), and SCIP_DECL_HEUREXEC().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ EAT_FREE

◆ EAT_LAST

◆ EAT_HIDE

◆ GRAPH_HAS_COORDINATES

◆ GRAPH_IS_GRIDGRAPH

◆ GRAPH_IS_DIRECTED

◆ STP_SPG

◆ STP_SAP

◆ STP_PCSPG

◆ STP_RPCSPG

◆ STP_NWSPG

◆ STP_DCSTP

◆ STP_REVENUES_BUDGET_HOPCONS

◆ STP_RSMT

◆ STP_OARSMT

◆ STP_MWCSP

◆ STP_DHCSTP

◆ STP_GSTP

◆ STP_RMWCSP

◆ flipedge

◆ flipedge_Uint

◆ PATH_NIL

◆ CONNECT

◆ UNKNOWN

◆ FARAWAY

◆ BLOCKED

◆ EDGE_BLOCKED

◆ EDGE_MODIFIABLE

◆ MST_MODE

◆ FSP_MODE

◆ BSP_MODE

◆ NO_CHANGE

◆ Is_term

◆ Is_pterm

◆ Is_gterm

◆ Edge_anti

◆ VERSION_SCIPJACK

◆ STP_MAGIC

◆ VERSION_MAJOR

◆ VERSION_MINOR

Typedef Documentation

◆ STP_Bool

◆ PRESOL

◆ PATH

Enumeration Type Documentation

◆ FILETYPE

Function Documentation

◆ graph_pc_knot2nonTerm()

◆ graph_pc_updateTerm2edge()

◆ graph_pc_subtractPrize()

◆ graph_pc_chgPrize()

◆ graph_show()

◆ graph_knot_add()

◆ graph_knot_chg()

◆ graph_knot_del()

◆ graph_knot_contract_dir()

◆ graph_get_csr()

◆ graph_edge_add()

◆ graph_edge_del()

◆ graph_edge_hide()

◆ graph_edge_printInfo()

◆ graph_uncover()

◆ graph_trail()

◆ graph_free()

◆ graph_free_history()

◆ graph_free_historyDeep()

◆ graph_get_NVET()

◆ graph_sol_setNodeList()

◆ graph_pc_2org()

◆ graph_pc_2trans()

◆ graph_pc_2orgcheck()

◆ graph_pc_2transcheck()