Detailed Description
includes various files containing graph methods used for Steiner tree problems
Definition in file grph.h.
Go to the source code of this file.
Data Structures | |
struct | GRAPH |
struct | presolve_info |
struct | shortest_path |
Macros | |
#define | EAT_FREE -1 |
#define | EAT_LAST -2 |
#define | EAT_HIDE -3 |
#define | GRAPH_HAS_COORDINATES 1 |
#define | GRAPH_IS_GRIDGRAPH 2 |
#define | GRAPH_IS_DIRECTED 4 |
#define | STP_SPG 0 |
#define | STP_SAP 1 |
#define | STP_PCSPG 2 |
#define | STP_RPCSPG 3 |
#define | STP_NWSPG 4 |
#define | STP_DCSTP 5 |
#define | STP_REVENUES_BUDGET_HOPCONS 6 |
#define | STP_RSMT 7 |
#define | STP_OARSMT 8 |
#define | STP_MWCSP 9 |
#define | STP_DHCSTP 10 |
#define | STP_GSTP 11 |
#define | STP_RMWCSP 12 |
#define | flipedge(edge) ( ((edge) + 1) - 2 * ((edge) % 2) ) |
#define | flipedge_Uint(edge) ( (((unsigned int) edge) + 1) - 2 * (((unsigned int) edge) % 2) ) |
#define | PATH_NIL ((PATH*)0) |
#define | CONNECT 0 |
#define | UNKNOWN (-1) |
#define | FARAWAY 1e15 |
#define | BLOCKED 1e10 |
#define | EDGE_BLOCKED 0 |
#define | EDGE_MODIFIABLE 1 |
#define | MST_MODE 0 |
#define | FSP_MODE 1 |
#define | BSP_MODE 2 |
#define | NO_CHANGE -10 |
#define | Is_term(a) ((a) >= 0) |
#define | Is_pterm(a) ((a) == -2) |
#define | Is_gterm(a) ((a) == -2 || (a) >= 0 ) |
#define | Edge_anti(a) ((((a) % 2) > 0) ? (a) - 1 : (a) + 1) |
#define | VERSION_SCIPJACK "1.3" |
#define | STP_MAGIC 0x33d32945 |
#define | VERSION_MAJOR 1 |
#define | VERSION_MINOR 0 |
Typedefs | |
typedef unsigned char | STP_Bool |
typedef struct presolve_info | PRESOL |
typedef struct shortest_path | PATH |
Enumerations | |
enum | FILETYPE { FF_BEA, FF_STP, FF_PRB, FF_GRD } |
Macro Definition Documentation
◆ EAT_FREE
#define EAT_FREE -1 |
Definition at line 30 of file grph.h.
Referenced by adjterms(), bea_save(), buildsolgraph(), graph_edge_del(), graph_edge_hide(), graph_edge_redirect(), graph_pack(), graph_show(), graph_sol_unreduced(), graph_valid(), nchains(), redbasedVarfixing(), reduce_contractZeroEdges(), reduce_deleteConflictEdges(), reduce_extendedEdge(), reduce_nts(), reduce_sd(), reduce_sdPc(), reducePcMw(), SCIPprobdataPrintGraph2(), SCIPStpHeurLocalRun(), SCIPStpHeurRecExclude(), SCIPwriteStp(), sddeltable(), and stp_save().
◆ 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
◆ GRAPH_IS_GRIDGRAPH
◆ GRAPH_IS_DIRECTED
◆ STP_SPG
#define STP_SPG 0 |
Definition at line 38 of file grph.h.
Referenced by buildsolgraph(), graph_load(), graph_sol_reroot(), isProbCompatible(), probdataCreate(), reduce_ledge(), reduceWithEdgeFixingBounds(), reduceWithNodeFixingBounds(), SCIP_DECL_CONSSEPALP(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEURINIT(), SCIP_DECL_PROPEXEC(), SCIPintListNodeAppendCopy(), SCIPprobdataCreate(), SCIPprobdataWriteSolution(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurSlackPruneRun(), SCIPwriteStp(), updateEdgeFixingBounds(), updateNodeFixingBounds(), and updateNodeReplaceBounds().
◆ 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
◆ STP_RSMT
#define STP_RSMT 7 |
Definition at line 45 of file grph.h.
Referenced by buildsolgraph(), graph_copy_data(), graph_free(), graph_grid_create(), graph_load(), graph_pack(), isProbCompatible(), reduce_da(), reduceWithEdgeFixingBounds(), reduceWithNodeFixingBounds(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PROPEXEC(), SCIPprobdataCreate(), SCIPprobdataWriteSolution(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurSlackPruneRun(), SCIPwriteStp(), updateEdgeFixingBounds(), updateNodeFixingBounds(), and updateNodeReplaceBounds().
◆ 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
#define STP_RMWCSP 12 |
Definition at line 50 of file grph.h.
Referenced by buildsolgraph(), computeSteinerTreeDijkPcMw(), graph_copy_data(), graph_load(), graph_pack(), graph_pc_2org(), graph_pc_2rmw(), graph_pc_chgPrize(), graph_pc_contractEdge(), graph_pc_isPcMw(), graph_pc_knot2nonTerm(), graph_pc_mw2rmw(), graph_pc_subtractPrize(), graph_valid(), prune(), reduce(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PROBEXITSOL(), SCIPprobdataCreate(), SCIPprobdataWriteLogfileEnd(), SCIPprobdataWriteSolution(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurPruneRun(), SCIPStpHeurPruneUpdateSols(), SCIPStpHeurRecRun(), SCIPStpHeurTMPrunePc(), SCIPStpHeurTMRun(), and SCIPStpHeurTMRunLP().
◆ 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
◆ 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
◆ 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
◆ 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 |
Definition at line 163 of file grph.h.
Referenced by central_terminal(), createVariables(), getlecloseterms(), graph_get2next(), graph_get3next(), graph_get4next(), graph_path_exec(), graph_path_PcMwSd(), graph_path_st_pcmw_extend(), graph_sdPaths(), graph_voronoi(), graph_voronoiExtend(), graph_voronoiMw(), graph_voronoiRepair(), graph_voronoiRepairMult(), graph_voronoiTerms(), graph_voronoiWithDist(), graph_voronoiWithRadius(), graph_voronoiWithRadiusMw(), pricing(), and SCIPprobdataAddNewSol().
◆ BSP_MODE
◆ NO_CHANGE
◆ Is_term
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
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
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
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
◆ PRESOL
typedef struct presolve_info PRESOL |
◆ PATH
typedef struct shortest_path PATH |
Enumeration Type Documentation
◆ FILETYPE
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()
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 1992 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()
change prize of a terminal
- Parameters
-
scip SCIP data structure g the graph newprize prize to be subtracted i the terminal
Definition at line 2035 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 3916 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 2200 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 2222 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()
delete node
- Parameters
-
scip SCIP data structure g the graph k the node freeancestors free edge ancestors?
Definition at line 2246 of file grphbase.c.
References EAT_LAST, graph_edge_del(), NULL, and GRAPH::outbeg.
Referenced by graph_knot_delPseudo(), reduceSPG(), reduceWithNodeFixingBounds(), and STPStpBranchruleParseConsname().
◆ graph_knot_contract_dir()
void graph_knot_contract_dir | ( | GRAPH * | , |
int | , | ||
int | |||
) |
◆ graph_get_csr()
void graph_get_csr | ( | const GRAPH * | , |
int * | RESTRICT, | ||
int * | RESTRICT, | ||
int * | RESTRICT, | ||
int * | |||
) |
Referenced by SCIPStpDualAscent().
◆ graph_edge_add()
◆ graph_edge_del()
delete an edge
- Parameters
-
scip SCIP data structure g the graph e the edge freeancestors free edge ancestors?
Definition at line 2841 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 2891 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()
print edge info
- Parameters
-
scip SCIP data structure g the graph e the edge
Definition at line 2935 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 3941 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 4188 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()
free the graph
- Parameters
-
scip SCIP data structure graph graph to be freed final delete ancestor data structures?
Definition at line 3678 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()
free the history
- Parameters
-
scip SCIP data p graph data
Definition at line 3740 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()
free the deep history
- Parameters
-
scip SCIP data p graph data
Definition at line 3764 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 3386 of file grphbase.c.
References GRAPH::grad, Is_term, GRAPH::knots, NULL, and GRAPH::term.
Referenced by SCIPStpHeurPruneRun(), SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().
◆ graph_sol_setNodeList()
mark endpoints of edges in given list
- Parameters
-
g graph data structure solnode solution nodes array (TRUE/FALSE) listnode edge list
Definition at line 3174 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()
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()
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 1520 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 1601 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 1682 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 1741 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 1850 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 2079 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 2105 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 3635 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 2433 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 2666 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 2947 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 3218 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 3292 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 2757 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 2262 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 3809 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 3900 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 3988 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 4242 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 3452 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 3495 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 3573 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 4299 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()
Definition at line 2685 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()
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 1945 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()
is the given graph valid?
- Parameters
-
g the new graph
Definition at line 4328 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()
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()
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 3050 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()
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 3070 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()
is this graph a prize-collecting or maximum-weight variant?
- Parameters
-
g the graph
Definition at line 2188 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 3200 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()
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()
Definition at line 466 of file grphpath.c.
References NULL, GRAPH::path_heap, GRAPH::path_state, and SCIPfreeMemoryArray.
Referenced by graph_pack(), initReceivedSubproblem(), redbasedVarfixing(), reduce(), reduce_bd34(), reduce_bdr(), reduce_bound(), reduce_boundHop(), reduce_boundPrune(), reduce_daPcMw(), reduce_daSlackPruneMw(), reduce_ledge(), reduce_npv(), reduce_nts(), reduce_sd(), SCIP_DECL_PROBDELORIG(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().
◆ graph_path_exec()
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()
◆ 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 * | |||
) |
Definition at line 444 of file grphpath.c.
References GRAPH::knots, NULL, GRAPH::path_heap, GRAPH::path_state, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.
Referenced by initReceivedSubproblem(), redbasedVarfixing(), reduce(), reduce_bd34(), reduce_bdr(), reduce_bound(), reduce_boundHop(), reduce_boundPrune(), reduce_daPcMw(), reduce_daSlackPruneMw(), reduce_ledge(), reduce_npv(), reduce_nts(), reduce_sd(), SCIP_DECL_PROBCOPY(), SCIPprobdataCreate(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().
◆ 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()
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()
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()
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()
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()
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()
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()
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, 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 * | |||
) |
Definition at line 3710 of file reduce_alt.c.
References GRAPH::ancestors, GRAPH::cost, shortest_path::dist, EAT_LAST, FARAWAY, GRAPH::fixedges, 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, SCIPfreeBufferArrayNull, SCIPintListNodeAppendCopy(), SCIPisGE(), SCIPisLE(), GRAPH::source, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and UNKNOWN.
◆ 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, 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, 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, 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(), 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, 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, 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, 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().