SCIP
Solving Constraint Integer Programs
graph_pcbase.c File Reference
Detailed Description
includes several methods for prize-collecting Steiner problem graphs
This file contains several basic methods to process prize-collecting Steiner problem graphs and kinsmen such as the maximum-weight connected subgraph problem.
Definition in file graph_pcbase.c.
#include "scip/misc.h"#include <stdio.h>#include <stdlib.h>#include <string.h>#include <assert.h>#include "solstp.h"#include "portab.h"#include "graph.h"Go to the source code of this file.
Function Documentation
◆ markNonLeafTerms_2trans()
remove non-leaf terminals by edge weight shifting (call before graph transformation was performed)
- Parameters
-
scip SCIP g the graph
Definition at line 46 of file graph_pcbase.c.
References GRAPH::extended, graph_knot_chg(), graph_pc_termIsNonLeafTerm(), Is_term, GRAPH::knots, nnodes, STP_TERM_NONLEAF, and GRAPH::term.
Referenced by graph_pc_2trans().
◆ setCostToOrgPc()
gets original edge costs, when in extended mode
- Parameters
-
scip SCIP data structure graph the graph
Definition at line 70 of file graph_pcbase.c.
References BLOCKED, BLOCKED_MINOR, GRAPH::cost, GRAPH::cost_org_pc, GRAPH::edges, EQ, GRAPH::extended, graph_edge_isBlocked(), graph_pc_isPcMw(), graph_pc_transOrgAreConistent(), SCIP_Real, and TRUE.
Referenced by graph_pc_2org().
◆ setCostToOrgPcPreState()
gets original edge costs, when in extended mode and in presolving state
- Parameters
-
scip SCIP data structure graph the graph
Definition at line 96 of file graph_pcbase.c.
References BMScopyMemoryArray, GRAPH::cost, GRAPH::cost_org_pc, GRAPH::edges, GRAPH::extended, graph_edge_isBlocked(), graph_pc_isPcMw(), graph_pc_transOrgAreConistent(), SCIP_Real, and TRUE.
Referenced by graph_pc_2org().
◆ termDeleteExtension()
- Parameters
-
scip SCIP data structure g graph data structure i index of the terminal makeNonTerminal make i a non-terminal?
Definition at line 124 of file graph_pcbase.c.
References GRAPH::cost, EAT_LAST, GRAPH::extended, GRAPH::grad, graph_edge_del(), graph_knot_chg(), graph_pc_getRoot2PtermEdge(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), GRAPH::head, GRAPH::inpbeg, Is_pseudoTerm, Is_term, GRAPH::prize, SCIP_Bool, SCIPisEQ(), GRAPH::source, STP_TERM_NONE, GRAPH::tail, GRAPH::term, GRAPH::term2edge, TERM2EDGE_NOTERM, and TRUE.
Referenced by graph_pc_knotToFixedTerm(), graph_pc_termToNonLeafTerm(), and graph_pc_termToNonTerm().
◆ isLastTerm()
is given terminal the last terminal?
- Parameters
-
g the graph t terminal
Definition at line 190 of file graph_pcbase.c.
References GRAPH::extended, FALSE, GRAPH::grad, graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsNonLeafTerm(), Is_term, GRAPH::source, GRAPH::term, GRAPH::term2edge, and TRUE.
Referenced by graph_pc_termToNonLeafTerm().
◆ mwKnotUpdateIncEdges()
|
inlinestatic |
changes incident edges after prize of node was changed
- Parameters
-
g the graph node the node
Definition at line 213 of file graph_pcbase.c.
References GRAPH::cost, graph_pc_knotIsDummyTerm(), GRAPH::ieat, GRAPH::inpbeg, GRAPH::prize, SCIP_Real, and GRAPH::tail.
Referenced by graph_pc_contractEdge(), and graph_pc_knotChgPrize().
◆ contractEdgeWithFixedEnd()
|
static |
contract an edge of rooted prize-collecting Steiner tree problem or maximum-weight connected subgraph problem such that this edge is incident to least one fixed terminal
- 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 ets edge from t to s
Definition at line 237 of file graph_pcbase.c.
References GRAPH::extended, FARAWAY, graph_fixed_addEdge(), graph_fixed_moveNodePc(), graph_knot_contract(), graph_pc_fixedTermToNonTerm(), graph_pc_isMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_knotToFixedTerm(), graph_pc_termToNonTerm(), GRAPH::head, Is_term, NULL, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPisEQ(), GRAPH::source, GRAPH::tail, and GRAPH::term.
Referenced by graph_pc_contractEdge().
◆ contractEdgeNoFixedEnd()
|
static |
contract an edge of (rooted) prize-collecting Steiner tree problem or maximum-weight connected subgraph problem such that this edge is NOT incident to least one fixed terminal
- 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 ets edge from t to s term4offset terminal to add offset to
Definition at line 287 of file graph_pcbase.c.
References GRAPH::cost, FALSE, GRAPH::grad, graph_knot_contract(), graph_pc_contractNodeAncestors(), graph_pc_evalTermIsNonLeaf(), graph_pc_isMw(), graph_pc_knotIsFixedTerm(), graph_pc_subtractPrize(), graph_pc_termToNonLeafTerm(), graph_pc_termToNonTerm(), GRAPH::head, Is_term, LE, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::tail, GRAPH::term, GRAPH::term2edge, TERM2EDGE_NONLEAFTERM, and TERM2EDGE_NOTERM.
Referenced by graph_pc_contractEdge().
◆ getBiasedPc()
|
static |
initializes biased data
apply the minimum
- Parameters
-
graph graph data structure costbiased biased costs prizebiased biased prizes
Definition at line 371 of file graph_pcbase.c.
References BMScopyMemoryArray, GRAPH::cost, EAT_LAST, GRAPH::edges, FARAWAY, GE, GRAPH::grad, graph_get_nNodes(), graph_pc_isPc(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), GRAPH::ieat, GRAPH::inpbeg, Is_pseudoTerm, Is_term, nnodes, GRAPH::prize, SCIP_Bool, SCIP_Real, GRAPH::source, GRAPH::tail, and GRAPH::term.
Referenced by graph_pc_getBiased().
◆ getBiasedMw()
|
static |
initializes biased data
apply the minimum
- Parameters
-
graph graph data structure costbiased biased costs prizebiased biased prizes
Definition at line 448 of file graph_pcbase.c.
References BLOCKED, BMScopyMemoryArray, GRAPH::cost, EAT_LAST, GRAPH::edges, EQ, GRAPH::esize, GRAPH::extended, FARAWAY, GE, GRAPH::grad, graph_edge_add(), graph_get_nNodes(), graph_knot_add(), graph_knot_chg(), graph_pc_isMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), graph_resize(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pseudoTerm, Is_term, GRAPH::knots, GRAPH::ksize, LT, nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisGE(), SCIPisLT(), GRAPH::source, STP_MWCSP, STP_PCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.
Referenced by graph_pc_getBiased().
◆ graph_pc_shiftNonLeafCosts()
shift costs of non-leaf terminals (call right after transformation to extended has been performed)
- Parameters
-
scip SCIP g the graph
Definition at line 671 of file graph_pcbase.c.
References GRAPH::cost, GRAPH::cost_org_pc, EAT_LAST, GRAPH::edges, GRAPH::extended, FARAWAY, flipedge, graph_edge_isBlocked(), graph_pc_isPc(), GRAPH::ieat, GRAPH::inpbeg, Is_nonleafTerm, GRAPH::knots, nnodes, GRAPH::oeat, GRAPH::prize, SCIP_Real, SCIPisEQ(), SCIPisGE(), SCIPisLT(), and GRAPH::term.
Referenced by graph_pc_2trans(), graph_transPc(), and graph_transRpc().
◆ graph_pc_initTerm2Edge()
| SCIP_RETCODE graph_pc_initTerm2Edge | ( | SCIP * | scip, |
| GRAPH * | g, | ||
| int | size | ||
| ) |
initializes term2edge array
- Parameters
-
scip SCIP data structure g the graph size the size
Definition at line 721 of file graph_pcbase.c.
References SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, GRAPH::term2edge, and TERM2EDGE_NOTERM.
Referenced by graph_pc_initSubgraph(), graph_transPc(), graph_transPcGetRsap(), graph_transRmw(), and graph_transRpc().
◆ graph_pc_initPrizes()
| SCIP_RETCODE graph_pc_initPrizes | ( | SCIP * | scip, |
| GRAPH * | g, | ||
| int | sizeprize | ||
| ) |
allocates prizes array for PC and MW problems
- Parameters
-
scip SCIP data structure g the graph sizeprize size of prize array to allocate (or -1)
Definition at line 741 of file graph_pcbase.c.
References FARAWAY, NULL, GRAPH::prize, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.
Referenced by graph_load(), graph_pc_initSubgraph(), graph_transPcGetRsap(), graphBuildV5E5(), localExtendPc(), localInsertion2pc(), localKeyPathExchangeMw(), localKeyPathExchangePc(), localKeyPathExchangePc2(), localKeyVertexPc(), localKeyVertexPc2(), testDaPathsPcMw3EdgesWorks(), testDistCloseNodesPcAreValid1(), testDistCloseNodesPcAreValid2(), testDistCloseNodesPcAreValidAfterDeletion(), testPcEdgeDeletedByMst1(), testPcEdgeNotDeleted(), testPcNode3PseudoDeletedBySd1(), testPcNode4PseudoDeletedBySd1(), testPrunedSolIsImprovedPc1(), testPrunedSolIsImprovedPc2(), testRmwAnsDeletesOneEdge(), testRmwAnsDeletesOneNode(), testRmwAnsDeletesTwoNodes(), testRmwChain2DeletesNode(), testRmwNpv3DeletesNode(), testRmwTerminalContraction(), testRmwTerminalDeg1Contraction1(), testRmwTerminalDeg1Contraction2(), testRmwTerminalDeg1Contraction3(), testSdBiasedBottleneckDeletesEdge(), testSdPcKillsEdge1(), testSdPcKillsEdge2(), testSdPcKillsTwoEdges(), testSdStarPcKillsEdge(), testTmGivesExpectedTreePcFull1(), testTmGivesExpectedTreePcFull2(), and testTmGivesExpectedTreePcFull3().
◆ graph_pc_initSubgraph()
| SCIP_RETCODE graph_pc_initSubgraph | ( | SCIP * | scip, |
| GRAPH * | subgraph | ||
| ) |
allocates and initializes arrays for subgraph PC/MW
- Parameters
-
scip SCIP data structure subgraph the subgraph
Definition at line 763 of file graph_pcbase.c.
References GRAPH::cost_org_pc, GRAPH::edges, GRAPH::esize, graph_pc_initPrizes(), graph_pc_initTerm2Edge(), graph_pc_isPc(), graph_pc_isPcMw(), GRAPH::knots, GRAPH::ksize, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.
Referenced by buildsolgraph(), packPcMwInit(), redcostGraphBuild(), and SCIPStpHeurRecExclude().
◆ graph_pc_finalizeSubgraph()
| SCIP_RETCODE graph_pc_finalizeSubgraph | ( | SCIP * | scip, |
| GRAPH * | subgraph | ||
| ) |
allocates and initializes arrays for subgraph PC/MW
- Parameters
-
scip SCIP data structure subgraph the subgraph
Definition at line 795 of file graph_pcbase.c.
References GRAPH::cost_org_pc, GRAPH::extended, graph_pc_isPc(), graph_pc_isPcMw(), Is_term, NULL, GRAPH::prize, SCIP_OKAY, GRAPH::source, GRAPH::term, and GRAPH::term2edge.
Referenced by buildsolgraph(), graph_pack(), redcostGraphBuild(), and SCIPStpHeurRecExclude().
◆ 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 815 of file graph_pcbase.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_transPcGetRsap(), graph_transPcGetSap(), and reduce_redLoopPc().
◆ 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 858 of file graph_pcbase.c.
References NULL, GRAPH::rootedgeprevs, SCIPfreeMemoryArray, STP_RPCSPG, and GRAPH::stp_type.
Referenced by graph_transPcGetRsap(), graph_transPcGetSap(), graph_transPcmw2rooted(), and reduce_redLoopPc().
◆ graph_pc_term2edgeIsConsistent()
checks consistency of term2edge array
- Parameters
-
scip SCIP data structure g the graph
Definition at line 874 of file graph_pcbase.c.
References EAT_LAST, GRAPH::extended, FALSE, FARAWAY, flipedge, graph_knot_printInfo(), graph_pc_evalTermIsNonLeaf(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsNonLeafTerm(), graph_pc_realDegree(), GRAPH::head, Is_anyTerm, Is_nonleafTerm, Is_pseudoTerm, Is_term, GRAPH::knots, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIPdebugMessage, SCIPisEQ(), GRAPH::source, GRAPH::term, GRAPH::term2edge, TERM2EDGE_FIXEDTERM, TERM2EDGE_NONLEAFTERM, TERM2EDGE_NOTERM, and TRUE.
Referenced by graph_transPc(), graphisValidPcMw(), reduce_identifyNonLeafTerms(), reduce_redLoopMw(), and reduce_redLoopPc().
◆ graph_pc_transOrgAreConistent()
transformed problem consistent to original one? Call only for extended graph
- Parameters
-
scip SCIP data structure graph the graph verbose be verbose?
Definition at line 980 of file graph_pcbase.c.
References GRAPH::cost, GRAPH::cost_org_pc, EAT_FREE, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, graph_edge_isBlocked(), graph_edge_printInfo(), graph_pc_isPcMw(), GRAPH::head, Is_nonleafTerm, GRAPH::oeat, GRAPH::prize, SCIP_Real, SCIPisEQ(), SCIPisGE(), SCIPisLT(), GRAPH::term, and TRUE.
Referenced by graph_pc_getOrgCosts(), graph_pc_getOrgCostsCsr(), setCostToOrgPc(), and setCostToOrgPcPreState().
◆ graph_pc_knotToNonTermProperty()
| void graph_pc_knotToNonTermProperty | ( | GRAPH * | g, |
| int | node | ||
| ) |
change property of node to be a non-terminal; prize is not changed!
- Parameters
-
g the graph node node to be changed
Definition at line 1044 of file graph_pcbase.c.
References graph_knot_chg(), graph_pc_isPcMw(), STP_TERM_NONE, GRAPH::term2edge, and TERM2EDGE_NOTERM.
Referenced by graph_pc_deleteTerm(), graph_pc_termToNonTerm(), graph_transPcmw2rooted(), and pcmwReduceTerm0Prize().
◆ graph_pc_knotToFixedTermProperty()
| void graph_pc_knotToFixedTermProperty | ( | GRAPH * | g, |
| int | node | ||
| ) |
change property of node to be a terminal; prize is changed, but no edges are deleted!
- Parameters
-
g the graph node node to be changed
Definition at line 1062 of file graph_pcbase.c.
References FARAWAY, graph_knot_chg(), GRAPH::prize, STP_TERM, GRAPH::term2edge, and TERM2EDGE_FIXEDTERM.
Referenced by graph_pc_enforceNode(), graph_pc_enforceNonLeafTerm(), graph_transPcGetRsap(), graph_transPcmw2rooted(), graph_transRmw(), and graph_transRpc().
◆ graph_pc_knotToFixedTerm()
Makes a node a fixed terminal
- Parameters
-
scip SCIP data structure g graph data structure node node offset offset needed for RMW, or NULL
Definition at line 1079 of file graph_pcbase.c.
References GRAPH::extended, graph_knot_chg(), graph_pc_isMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_nonTermToFixedTerm(), graph_pc_termIsNonLeafTerm(), Is_pseudoTerm, Is_term, GRAPH::prize, SCIP_Bool, GRAPH::source, STP_TERM_NONE, GRAPH::term, GRAPH::term2edge, TERM2EDGE_NOTERM, termDeleteExtension(), and TRUE.
Referenced by contractEdgeWithFixedEnd(), dapathsFixPotTerms(), propgraphApplyImplicationsPcMw(), propgraphFixNode(), and reduce_sl().
◆ graph_pc_nonTermToFixedTerm()
makes a non-terminal node a fixed terminal
- Parameters
-
g graph data structure node node offset offset needed for RMW, or NULL
Definition at line 1115 of file graph_pcbase.c.
References GRAPH::cost, EAT_LAST, EQ, FARAWAY, GRAPH::grad, graph_knot_chg(), graph_pc_isMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), GRAPH::ieat, GRAPH::inpbeg, Is_pseudoTerm, Is_term, NULL, GRAPH::prize, SCIP_Bool, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, GRAPH::term, GRAPH::term2edge, TERM2EDGE_FIXEDTERM, and TERM2EDGE_NOTERM.
Referenced by applyBranchHistoryToGraph(), graph_pc_enforceNode(), and graph_pc_knotToFixedTerm().
◆ graph_pc_termToNonTerm()
Makes a non-fixed terminal a non-terminal. Also sets the prize to 0.0 for (R)PC!
- Parameters
-
scip SCIP data structure g graph data structure term terminal to be unfixed
Definition at line 1158 of file graph_pcbase.c.
References GRAPH::extended, FALSE, graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_knotToNonTermProperty(), graph_pc_termIsNonLeafTerm(), Is_anyTerm, GRAPH::prize, GRAPH::source, GRAPH::term, and termDeleteExtension().
Referenced by contractEdgeNoFixedEnd(), contractEdgeWithFixedEnd(), and delPseudoInit().
◆ graph_pc_fixedTermToNonTerm()
Makes a fixed terminal a non-terminal
- Parameters
-
scip SCIP data structure g graph data structure term terminal to be unfixed
Definition at line 1189 of file graph_pcbase.c.
References graph_knot_chg(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), Is_anyTerm, GRAPH::prize, GRAPH::source, STP_TERM_NONE, GRAPH::term, GRAPH::term2edge, and TERM2EDGE_NOTERM.
Referenced by contractEdgeWithFixedEnd().
◆ graph_pc_termToNonLeafTerm()
change property of (non-fixed) terminal to be a non-leaf terminal NOTE: if force == FALSE, then nothing is done if term is the last terminal
- Parameters
-
scip SCIP data structure g the graph term terminal to be changed force force the transformation? Should usually be FALSE
Definition at line 1210 of file graph_pcbase.c.
References GRAPH::extended, FALSE, graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsNonLeafTerm(), Is_term, isLastTerm(), GRAPH::term, GRAPH::term2edge, TERM2EDGE_NONLEAFTERM, and termDeleteExtension().
Referenced by contractEdgeNoFixedEnd(), and reduce_identifyNonLeafTerms().
◆ graph_pc_edgeIsExtended()
is the edge part of the extended graph?
- Parameters
-
g the graph edge edge to be checked
Definition at line 1232 of file graph_pcbase.c.
References GRAPH::cost, EQ, FALSE, FARAWAY, flipedge, graph_pc_isPcMw(), graph_pc_knotIsDummyTerm(), GRAPH::head, LT, GRAPH::tail, and TRUE.
Referenced by fixVarsExtendedRed(), getBoundchanges(), pathreplaceExec(), reduceFixedVars(), reduceLurk(), SCIPStpHeurSlackPruneRun(), and validateEdgestate().
◆ graph_pc_knotIsFixedTerm()
check whether node is fixed terminal
- Parameters
-
g the graph node node to be checked
Definition at line 1257 of file graph_pcbase.c.
References GRAPH::cost, EAT_LAST, EQ, FARAWAY, graph_pc_isMw(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::prize, GRAPH::source, GRAPH::term, GRAPH::term2edge, and TERM2EDGE_FIXEDTERM.
Referenced by addToCandidates(), applyBranchHistoryToGraph(), collectFixedTerminals(), collectRoots(), computeSteinerTree_allFixedTermsAreReached(), computeSteinerTree_execRpcMw(), contractEdgeNoFixedEnd(), contractEdgeWithFixedEnd(), createVariables(), daOrderRoots(), daPcFindRoots(), findRootsMark(), findSolRPcMw(), getBiasedMw(), getBiasedPc(), graph_copyData(), graph_knot_printInfo(), graph_path_st_pcmw_extendBiased(), graph_path_st_pcmw_full(), graph_path_st_rpcmw(), graph_pc_2org(), graph_pc_2trans(), graph_pc_contractEdge(), graph_pc_deleteTerm(), graph_pc_enforceNode(), graph_pc_evalTermIsNonLeaf(), graph_pc_fixedTermToNonTerm(), graph_pc_getBiased(), graph_pc_knotHasMaxPrize(), graph_pc_knotIsDummyTerm(), graph_pc_knotToFixedTerm(), graph_pc_nFixedTerms(), graph_pc_nonTermToFixedTerm(), graph_pc_realDegree(), graph_pc_subtractPrize(), graph_pc_term2edgeIsConsistent(), graph_pc_termIsNonLeafTerm(), graph_pc_termToNonLeafTerm(), graph_pc_termToNonTerm(), graph_transRpcGetSpg(), graph_valid(), graph_validInput(), graph_voronoiWithRadius(), graph_writeStp(), graphisValidPcMw(), insertionGetCandidateEdges(), isLastTerm(), mwContractTerminalsChainWise(), mwContractTerminalsSimple(), mwReduceTermDeg1(), pcmwGetStartNodes(), pcmwReduceTerm0Prize(), pcmwUpdate(), pcReduceTermDeg1(), pcReduceTermDeg2(), pcsolMarkGraphNodes(), pcsolMarkGraphNodes_csr(), propgraphApplyImplicationsPcMw(), propgraphDeleteNode(), propgraphFixNode(), pseudodeleteNodeIsPromising(), reduce_bd34(), reduce_bound(), reduce_identifyNonLeafTerms(), reduce_impliedProfitBasedRpc(), reduce_simple_mw(), reduce_simple_pc(), reduce_sl(), reduce_unconnectedRpcRmwInfeas(), reduceRootedProb(), reroot(), runTmPcMW_mode(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurLocalExtendPcMwImp(), SCIPStpHeurTMBuildTreePcMw(), sepaspecial_pcimplicationsInit(), solIsTrivialPcMw(), solstp_isValid(), solstp_pcConnectDummies(), stRpcmwInit(), and termDeleteExtension().
◆ graph_pc_knotIsPropPotTerm()
check whether node is proper potential terminal
- Parameters
-
g the graph node node to be checked
Definition at line 1288 of file graph_pcbase.c.
References GRAPH::extended, FALSE, graph_pc_isPcMw(), graph_pc_knotIsDummyTerm(), Is_pseudoTerm, Is_term, GRAPH::prize, GRAPH::term, GRAPH::term2edge, and TRUE.
Referenced by getBoundchangesPcMW(), graph_pc_enforceNode(), graph_pc_enforcePseudoTerm(), graph_pc_knotChgPrize(), propgraphApplyImplicationsPcMw(), propgraphDeleteNode(), propgraphMarkFixedTermsPcMw(), and reduce_impliedProfitBasedRpc().
◆ graph_pc_knotHasMaxPrize()
is there no vertex of higher prize?
- Parameters
-
g graph data structure i the node to be checked
Definition at line 1315 of file graph_pcbase.c.
References EQ, FARAWAY, graph_get_nNodes(), graph_pc_isPc(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), LT, nnodes, GRAPH::prize, SCIP_Real, STP_RPCSPG, and GRAPH::stp_type.
Referenced by delPseudoInit(), and delPseudoInitForCheck().
◆ graph_pc_knotIsDummyTerm()
check whether node is a dummy (pseudo) terminal
- Parameters
-
g the graph node node to be checked
Definition at line 1344 of file graph_pcbase.c.
References GRAPH::extended, FALSE, GRAPH::grad, graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), Is_pseudoTerm, Is_term, NULL, GRAPH::source, GRAPH::term, and TRUE.
Referenced by ansDeleteVertex(), ansProcessCandidate(), blctreeComputeBottlenecks(), blctreeComputeEdgesState(), buildsolgraph(), computeSteinerTree_execRpcMw(), createVariables(), cutNodesSetDfsRoot(), dapathsFixPotTerms(), extreduce_bottleneckMarkRootPath(), extreduce_edgeIsValid(), findSolPcMw1Term(), getBiasedMw(), getBiasedPc(), getBoundchanges(), getBoundchangesPcMW(), getOrgNodeToNodeMap(), graph_csr_build(), graph_csr_chgCosts(), graph_fixed_addNodePc(), graph_path_st_rpcmw(), graph_pc_edgeIsExtended(), graph_pc_enforceNode(), graph_pc_enforcePseudoTerm(), graph_pc_evalTermIsNonLeaf(), graph_pc_getNorgEdges(), graph_pc_getReductionRatios(), graph_pc_knotHasMaxPrize(), graph_pc_knotIsPropPotTerm(), graph_pc_markOrgGraph(), graph_pc_nonTermToFixedTerm(), graph_pseudoAncestors_addToNode(), graph_transPcGetSap(), graph_writeStp(), graphisValidPcMw(), impliedNodesAddTerm(), mwContractTerminalsChainWise(), mwKnotUpdateIncEdges(), mwReduceTermDeg1(), pathExendPrepare(), pcsolGetTrivialEdges(), pcsolMarkGraphNodes(), pcsolMarkGraphNodes_csr(), pcsubtreeDelete(), pcsubtreePruneForProfit(), propgraphApplyImplicationsPcMw(), propgraphDeleteEdge(), propgraphDeleteNode(), propgraphFixEdge(), propgraphFixNode(), pseudodeleteDeleteComputeCutoffs(), redcostGraphBuild(), redcostGraphMark(), redcosts_forLPget(), reduce_ans(), reduce_ansAdv(), reduce_ansAdv2(), reduce_applyPseudoDeletions(), reduce_daSlackPrune(), reduce_simple_mw(), SCIPStpHeurTMBuildTreePcMw(), sdprofitBuild(), sdprofitBuild1stOnly(), shortestpath_computeSteinerTreePcMw(), shortestpath_computeSteinerTreePcMwFull(), shortestpath_computeSteinerTreeRpcMw(), solgraphAdaptForPcMw(), solstp_pcConnectDummies(), strongPruneSteinerTreePc(), and strongPruneSteinerTreePc_csr().
◆ graph_pc_knotIsNonLeafTerm()
check whether node is a terminal AND is not a leaf (or not contained) in at least one optimal tree
- Parameters
-
g the graph node node to be checked
Definition at line 1383 of file graph_pcbase.c.
References FALSE, graph_pc_termIsNonLeafTerm(), Is_anyTerm, and GRAPH::term.
Referenced by computeSteinerTree_tryConnectNodePcMw(), daPcFindRoots(), extreduce_distDataInit(), getKeyPathsStar(), graph_knot_printInfo(), graph_path_st_pcmw(), graph_path_st_rpcmw(), graph_pc_enforceNode(), graph_pc_enforceNonLeafTerm(), graph_pc_getNonLeafTermOffset(), graph_pc_nNonLeafTerms(), graph_pc_nonLeafTermIsEnforced(), graph_pc_realDegree(), graph_pc_solGetObj(), graph_pc_term2edgeIsConsistent(), graph_pc_termToNonLeafTerm(), graph_transRpcGetSpg(), graph_writeStp(), graphisValidPcMw(), isLastTerm(), markPseudoDeletablesFromBounds(), packPcMwVanished(), propgraphApplyImplicationsPcMw(), propgraphDeleteNode(), pseudodeleteDeleteComputeCutoffs(), pseudodeleteDeleteNode(), reduce_applyPseudoDeletions(), reduce_daPcMw(), reduce_identifyNonLeafTerms(), reduce_nvAdv(), reduce_removeDeg0NonLeafTerms(), reduce_simple_pc(), reduce_sl(), and stpsol_pruningIsPossible().
◆ graph_pc_knotChgPrize()
changes prize of a node
- Parameters
-
g the graph newprize new prize node the node
Definition at line 1399 of file graph_pcbase.c.
References GRAPH::cost, EQ, GE, graph_pc_getRoot2PtermEdge(), graph_pc_getTwinTerm(), graph_pc_isPcMw(), graph_pc_knotIsPropPotTerm(), Is_term, mwKnotUpdateIncEdges(), GRAPH::prize, SCIP_Bool, STP_MWCSP, STP_RMWCSP, GRAPH::stp_type, and GRAPH::term.
Referenced by propgraphMarkFixedTermsPcMw().
◆ graph_pc_termIsNonLeafTerm()
check whether terminal is not a leaf (or not contained) in at least one optimal tree
- Parameters
-
g the graph term terminal to be checked
Definition at line 1431 of file graph_pcbase.c.
References GRAPH::extended, FALSE, graph_pc_knotIsFixedTerm(), Is_anyTerm, Is_nonleafTerm, Is_pseudoTerm, Is_term, SCIP_Bool, GRAPH::term, GRAPH::term2edge, and TERM2EDGE_NONLEAFTERM.
Referenced by bottleneckGetDist(), bottleneckMarkEqualityEdges(), cutNodesTreeBuildSteinerTree(), cutNodesTreeDeleteComponents(), extreduce_bottleneckMarkRootPath(), findRootsMark(), graph_getIsTermArray(), graph_pc_contractEdgeUnordered(), graph_pc_deleteTerm(), graph_pc_knotIsNonLeafTerm(), graph_pc_knotToFixedTerm(), graph_pc_subtractPrize(), graph_pc_termMarkProper(), graph_pc_termToNonTerm(), markNonLeafTerms_2trans(), packPcMwVanished(), pcmwReduceTerm0Prize(), pcReduceTermDeg1(), pcReduceTermDeg2(), pseudodeleteNodeIsPromising(), reduce_bd34(), reduce_identifyNonLeafTerms(), reduce_unconnected(), reduce_unconnectedRpcRmwInfeas(), reduceRootedProb(), SCIPStpHeurLocalExtendPcMwOut(), sepaspecial_pcimplicationsInit(), and solstp_isValid().
◆ graph_pc_evalTermIsNonLeaf()
is terminal a non-leaf? Checked by evaluation of the current graph
- Parameters
-
scip SCIP g the graph term terminal to be checked
Definition at line 1467 of file graph_pcbase.c.
References GRAPH::cost, EAT_LAST, GRAPH::extended, FALSE, graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), graph_pc_realDegree(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::prize, SCIP_Bool, SCIPisLT(), GRAPH::source, GRAPH::tail, GRAPH::term, and TRUE.
Referenced by contractEdgeNoFixedEnd(), graph_pc_term2edgeIsConsistent(), and reduce_identifyNonLeafTerms().
◆ graph_pc_termMarkProper()
| void graph_pc_termMarkProper | ( | const GRAPH * | g, |
| int * | termmark | ||
| ) |
check whether terminal is not a leaf in at least one optimal tree
- Parameters
-
g the graph termmark terminal mark (2 for proper terminal, 1 for non-proper terminal, 0 otherwise)
Definition at line 1500 of file graph_pcbase.c.
References GRAPH::extended, graph_pc_termIsNonLeafTerm(), Is_term, GRAPH::knots, nnodes, and GRAPH::term.
Referenced by daPcFindRoots(), reduce_sdWalk(), reduce_sdWalk_csr(), reduce_sdWalkExt2(), reduce_sdWalkTriangle(), and sepaspecial_pcimplicationsInit().
◆ graph_pc_enforcePseudoTerm()
Enforces given pseudo-terminal without deleting edges. I.e. the terminal is part of any optimal solution.
- Parameters
-
scip SCIP data graph graph pterm the pseudo-terminal
Definition at line 1530 of file graph_pcbase.c.
References BLOCKED_MINOR, GRAPH::cost, graph_pc_getRoot2PtermEdge(), graph_pc_getTwinTerm(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsPropPotTerm(), GRAPH::prize, SCIPisEQ(), and SCIPisLT().
Referenced by applyBranchHistoryToGraph(), and graph_pc_enforceNode().
◆ graph_pc_enforceNonLeafTerm()
Enforces non-leaf terminal without deleting edges. I.e. the terminal is part of any optimal solution.
- Parameters
-
scip SCIP data graph graph nonleafterm the terminal
Definition at line 1556 of file graph_pcbase.c.
References BLOCKED, GRAPH::cost, GRAPH::cost_org_pc, EAT_LAST, GRAPH::extended, graph_pc_isMw(), graph_pc_isPc(), graph_pc_isRootedPcMw(), graph_pc_knotIsNonLeafTerm(), graph_pc_knotToFixedTermProperty(), GRAPH::ieat, GRAPH::inpbeg, GRAPH::prize, and SCIPisLT().
Referenced by applyBranchHistoryToGraph().
◆ graph_pc_nonLeafTermIsEnforced()
is non-leaf term enforced?
- Parameters
-
scip SCIP data graph graph nonleafterm the terminal
Definition at line 1589 of file graph_pcbase.c.
References BLOCKED_MINOR, GRAPH::extended, graph_pc_isPcMw(), graph_pc_knotIsNonLeafTerm(), GRAPH::prize, and SCIPisEQ().
◆ graph_pc_enforceNode()
Tries to enforce node without deleting or adding edges. I.e. the terminal is part of any optimal solution. Is not always possible!
- Parameters
-
scip SCIP data graph graph term the terminal offset pointer to the offset, for RMW only
Definition at line 1606 of file graph_pcbase.c.
References GRAPH::extended, graph_pc_enforcePseudoTerm(), graph_pc_isMw(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsNonLeafTerm(), graph_pc_knotIsPropPotTerm(), graph_pc_knotToFixedTermProperty(), graph_pc_nonTermToFixedTerm(), Is_pseudoTerm, Is_term, and GRAPH::term.
Referenced by initReceivedSubproblem(), and propgraphFixNode().
◆ graph_pc_updateSubgraphEdge()
| void graph_pc_updateSubgraphEdge | ( | const GRAPH * | orggraph, |
| const int * | nodemapOrg2sub, | ||
| int | orgedge, | ||
| GRAPH * | subgraph | ||
| ) |
Updates prize-collecting data for an edge added to subgraph of given graph 'orggraph'. Needs to be called right before corresponding edge is added
- Parameters
-
orggraph original graph nodemapOrg2sub node mapping from original to subgraph orgedge original edge subgraph the subgraph
Definition at line 1661 of file graph_pcbase.c.
References GRAPH::cost_org_pc, GRAPH::edges, GRAPH::esize, GRAPH::extended, flipedge, graph_pc_isPc(), GRAPH::head, Is_anyTerm, GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::term2edge, and TERM2EDGE_NOTERM.
Referenced by graph_edge_addSubgraph().
◆ graph_pc_getNorgEdges()
| int graph_pc_getNorgEdges | ( | const GRAPH * | graph | ) |
gets number of undeleted, original edges (not going to dummy terminals)
- Parameters
-
graph the graph
Definition at line 1722 of file graph_pcbase.c.
References GRAPH::cost, EAT_FREE, FARAWAY, graph_get_nEdges(), graph_pc_knotIsDummyTerm(), GRAPH::head, LT, GRAPH::oeat, and GRAPH::tail.
◆ graph_pc_getReductionRatios()
| void graph_pc_getReductionRatios | ( | const GRAPH * | graph, |
| SCIP_Real * | ratio_nodes, | ||
| SCIP_Real * | ratio_edges | ||
| ) |
gets ratio of remaining nodes/edges
- Parameters
-
graph graph ratio_nodes nodes ratio ratio_edges edges ratio
Definition at line 1751 of file graph_pcbase.c.
References GRAPH::edges, GRAPH::extended, GRAPH::grad, graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_nNonFixedTerms(), Is_pseudoTerm, Is_term, GRAPH::knots, nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, SCIP_Bool, SCIP_Real, GRAPH::source, GRAPH::term, and GRAPH::terms.
Referenced by getEdgeReductionRatio(), and getReductionRatiosPcMw().
◆ graph_pc_getOrgCosts()
gets original edge costs, when in extended mode
- Parameters
-
scip SCIP data structure graph the graph edgecosts original costs to be filled
Definition at line 1829 of file graph_pcbase.c.
References BLOCKED, BLOCKED_MINOR, BMScopyMemoryArray, GRAPH::cost, GRAPH::cost_org_pc, EQ, GRAPH::extended, graph_edge_isBlocked(), graph_get_nEdges(), graph_pc_isPcMw(), graph_pc_transOrgAreConistent(), SCIP_Bool, SCIP_Real, SCIP_STAGE_INITSOLVE, SCIPgetStage(), and TRUE.
Referenced by graph_pc_costsEqualOrgCosts(), localKeyVertexHeuristics(), localVertexInsertion(), runTmPcMW_mode(), and solstp_prune().
◆ graph_pc_getOrgCostsCsr()
gets original edge costs for CSR, when in extended mode
- Parameters
-
scip SCIP data structure g the graph csr CSR
Definition at line 1871 of file graph_pcbase.c.
References BLOCKED, BLOCKED_MINOR, csr_storage::cost, GRAPH::cost, GRAPH::cost_org_pc, csr_storage::edge_id, EQ, GRAPH::extended, graph_edge_isBlocked(), graph_get_nEdges(), graph_get_nNodes(), graph_pc_isPc(), graph_pc_transOrgAreConistent(), nnodes, csr_storage::nnodes, SCIP_Bool, SCIP_Real, csr_storage::start, and TRUE.
Referenced by tmBaseInit().
◆ graph_pc_costsEqualOrgCosts()
| SCIP_Bool graph_pc_costsEqualOrgCosts | ( | SCIP * | scip, |
| const GRAPH * | graph, | ||
| const SCIP_Real * | edgecosts | ||
| ) |
are the given costs equal to the original edge costs?
- Parameters
-
scip SCIP data structure graph the graph edgecosts edge costs to be checked
Definition at line 1913 of file graph_pcbase.c.
References EQ, FALSE, graph_get_nEdges(), graph_pc_getOrgCosts(), SCIP_Bool, SCIP_CALL_ABORT, SCIP_Real, SCIPallocMemoryArray, SCIPfreeMemoryArray, and TRUE.
Referenced by solstp_pruneFromTmHeur(), and strongPruneSteinerTreePc().
◆ graph_pc_markOrgGraph()
| void graph_pc_markOrgGraph | ( | GRAPH * | g | ) |
mark original graph (without dummy terminals)
- Parameters
-
g the graph
Definition at line 1944 of file graph_pcbase.c.
References GRAPH::cost, EAT_LAST, GRAPH::extended, FALSE, GRAPH::grad, graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), GT, GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, and GRAPH::source.
Referenced by graph_path_st_brmwcs(), graph_path_st_pcmw_extendBiased(), pcmwGetStartNodes(), and stRpcmwInit().
◆ graph_pc_2org()
mark terminals and switch terminal property to original terminals
- Parameters
-
scip SCIP data structure graph the graph
Definition at line 1976 of file graph_pcbase.c.
References GRAPH::extended, FALSE, graph_get_nNodes(), graph_knot_chg(), graph_mark(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), Is_nonleafTerm, Is_pseudoTerm, Is_term, nnodes, SCIP_STAGE_INITSOLVE, SCIPgetStage(), setCostToOrgPc(), setCostToOrgPcPreState(), GRAPH::source, STP_TERM, STP_TERM_PSEUDO, and GRAPH::term.
Referenced by checkSdWalk(), computeSteinerTree(), daPcFindRoots(), daPcMarkRoots(), daRoundInit(), findSolPcMw2Term(), findSolRPcMw(), fixVarsExtendedRed(), graph_pc_2orgcheck(), propgraphApplyBoundchanges(), redcosts_initializeDistances(), reduce_dapaths(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_redLoopMw(), reduce_redLoopPc(), reduce_sollocalRebuildTry(), reduce_unconnectedRpcRmwInfeas(), SCIP_DECL_CONSSEPALP(), SCIPStpHeurLocalExtendPcMwOut(), SCIPStpHeurPruneRun(), stptest_graphSetUpPcOrg(), stptest_graphSetUpRmwOrg(), and stptest_graphSetUpRpcOrg().
◆ graph_pc_2trans()
mark transformed graph and adapt terminal properties to transformed graph
- Parameters
-
scip SCIP data structure graph the graph
Definition at line 2018 of file graph_pcbase.c.
References BMScopyMemoryArray, GRAPH::cost, GRAPH::cost_org_pc, GRAPH::edges, GRAPH::extended, graph_knot_chg(), graph_mark(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_shiftNonLeafCosts(), Is_pseudoTerm, Is_term, GRAPH::knots, markNonLeafTerms_2trans(), nnodes, GRAPH::source, STP_TERM, STP_TERM_PSEUDO, GRAPH::term, and TRUE.
Referenced by computeSteinerTree(), daPcFindRoots(), daPcMarkRoots(), daRoundExit(), extreduce_pseudoDeleteNodes(), findSolPcMw2Term(), findSolRPcMw(), fixVarsExtendedRed(), graph_pc_2transcheck(), propgraphApplyBoundchanges(), redcosts_initializeDistances(), reduce_applyPseudoDeletions(), reduce_da(), reduce_dapaths(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_redLoopMw(), reduce_redLoopPc(), reduce_sollocalRebuildTry(), reduce_unconnectedRpcRmwInfeas(), SCIP_DECL_CONSSEPALP(), SCIPStpHeurLocalExtendPcMwOut(), and SCIPStpHeurPruneRun().
◆ graph_pc_2orgcheck()
graph_pc_2org if extended
- Parameters
-
scip SCIP data structure graph the graph
Definition at line 2062 of file graph_pcbase.c.
References GRAPH::extended, and graph_pc_2org().
Referenced by extreduce_pseudoDeleteNodes(), graph_transRpc2SpgTrivial(), reduce_applyPseudoDeletions(), reduce_da(), reduce_daPcMw(), reducePcMw(), and SCIPStpHeurLocalExtendPcMwOut().
◆ graph_pc_2transcheck()
graph_pc_2trans if not extended
- Parameters
-
scip SCIP data structure graph the graph
Definition at line 2076 of file graph_pcbase.c.
References GRAPH::extended, and graph_pc_2trans().
Referenced by computePertubedSol(), dualascent_paths(), graph_transPcGetRsap(), SCIPStpHeurLocalExtendPcMw(), and SCIPStpHeurTMRun().
◆ graph_pc_getPosPrizeSum()
- Parameters
-
scip SCIP data structure graph the graph
Definition at line 2091 of file graph_pcbase.c.
References BLOCKED, GRAPH::extended, Is_term, GRAPH::knots, NULL, GRAPH::prize, SCIP_Real, SCIPisLT(), GRAPH::source, and GRAPH::term.
Referenced by reduce_redLoopMw(), and reduce_redLoopPc().
◆ graph_pc_realDegree()
- Parameters
-
g graph data structure i the vertex to be checked fixedterm fixed terminal?
Definition at line 2112 of file graph_pcbase.c.
References GRAPH::extended, GRAPH::grad, graph_pc_isMw(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsNonLeafTerm(), Is_pseudoTerm, Is_term, NULL, SCIP_Bool, GRAPH::source, and GRAPH::term.
Referenced by delPseudoInitForCheck(), graph_pc_evalTermIsNonLeaf(), graph_pc_term2edgeIsConsistent(), pseudodeleteNodeIsPromising(), reduce_bd34(), reduce_simple_mw(), and reduce_simple_pc().
◆ graph_pc_adaptSap()
adapts SAP deriving from PCST or MWCS problem with new big M
- Parameters
-
bigM new big M value graph the SAP graph offset the offset
Definition at line 2156 of file graph_pcbase.c.
References GRAPH::cost, EAT_LAST, EQ, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Real, SCIPdebugMessage, and GRAPH::source.
◆ graph_pc_getBiased()
| void graph_pc_getBiased | ( | const GRAPH * | graph, |
| SCIP_Real *RESTRICT | costbiased, | ||
| SCIP_Real *RESTRICT | prizebiased | ||
| ) |
initializes biased data structures
- Parameters
-
graph graph data structure costbiased biased costs prizebiased biased prizes
Definition at line 2185 of file graph_pcbase.c.
References GRAPH::extended, getBiasedMw(), getBiasedPc(), graph_pc_isMw(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), and GRAPH::source.
◆ graph_pc_getNonLeafTermOffset()
returns offset generated by non-leaf terminals
- Parameters
-
scip SCIP data structure graph graph data structure
Definition at line 2209 of file graph_pcbase.c.
References graph_get_nNodes(), graph_pc_knotIsNonLeafTerm(), nnodes, GRAPH::prize, SCIP_Real, SCIPisGT(), STP_PCSPG, STP_RPCSPG, and GRAPH::stp_type.
Referenced by computeDualSolution(), computeDualSolutionGuided(), computeSteinerTreeRedCosts(), computeSteinerTreeRedCostsPcMw(), graph_pack(), graph_pc_solGetObj(), graph_transPcGetSap(), pcmwUpdateBestSol_csrInSync(), reduce_sollocalRebuildTry(), testPrunedSolIsImprovedPc1(), testPrunedSolIsImprovedPc2(), testTmGivesExpectedTreePcFull1(), testTmGivesExpectedTreePcFull2(), and testTmGivesExpectedTreePcFull3().
◆ graph_pc_deleteTerm()
Deletes a terminal for a (rooted) prize-collecting problem. Note that the prize of the terminal is not changed!
- Parameters
-
scip SCIP data structure g graph data structure term terminal to be deleted offset pointer to the offset
Definition at line 2235 of file graph_pcbase.c.
References EAT_LAST, GRAPH::extended, FALSE, GRAPH::grad, graph_edge_del(), graph_knot_del(), graph_pc_getTwinTerm(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_knotToNonTermProperty(), graph_pc_termIsNonLeafTerm(), GRAPH::head, Is_pseudoTerm, Is_term, GRAPH::mark, GRAPH::outbeg, GRAPH::prize, SCIPisZero(), GRAPH::source, GRAPH::term, GRAPH::term2edge, TRUE, and UNKNOWN.
Referenced by cutNodesTreeDeleteComponents(), pcReduceTermDeg1(), pcReduceTermDeg2(), propgraphApplyImplicationsPcMw(), propgraphDeleteNode(), reduce_bound(), reduce_removeDeg0NonLeafTerms(), reduce_simple_mw(), reduce_simple_pc(), and reduce_unconnectedRpcRmwInfeas().
◆ 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 2315 of file graph_pcbase.c.
References GRAPH::cost, GRAPH::extended, graph_pc_getRoot2PtermEdge(), graph_pc_getTwinTerm(), graph_pc_isMw(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_termIsNonLeafTerm(), GRAPH::head, Is_term, GRAPH::mark, GRAPH::prize, SCIPisEQ(), SCIPisGE(), GRAPH::source, GRAPH::tail, and GRAPH::term.
Referenced by contractEdgeNoFixedEnd().
◆ graph_pc_contractNodeAncestors()
| SCIP_RETCODE graph_pc_contractNodeAncestors | ( | 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 2352 of file graph_pcbase.c.
References EAT_LAST, graph_edge_getAncestors(), GRAPH::head, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::pcancestors, SCIP_CALL, SCIP_OKAY, and SCIPintListNodeAppendCopy().
Referenced by contractEdgeNoFixedEnd(), and mwContract0WeightVertices().
◆ graph_pc_contractEdge()
| SCIP_RETCODE graph_pc_contractEdge | ( | SCIP * | scip, |
| GRAPH * | g, | ||
| int * | solnode, | ||
| int | t, | ||
| int | s, | ||
| int | term4offset | ||
| ) |
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 term4offset terminal to add offset to
Definition at line 2385 of file graph_pcbase.c.
References contractEdgeNoFixedEnd(), contractEdgeWithFixedEnd(), EAT_LAST, GRAPH::extended, GRAPH::grad, graph_pc_isMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), GRAPH::head, Is_anyTerm, Is_term, mwKnotUpdateIncEdges(), GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisEQ(), GRAPH::source, GRAPH::term, GRAPH::term2edge, and TERM2EDGE_NOTERM.
Referenced by graph_pc_contractEdgeUnordered(), mwContract0WeightVertices(), mwContractTerminalsChainWise(), mwContractTerminalsSimple(), mwReduceTermDeg1(), pcReduceTermDeg1(), pcReduceTermDeg2(), reduce_impliedProfitBasedRpc(), reduce_nv(), reduce_nvAdv(), and reduce_sl().
◆ graph_pc_contractEdgeUnordered()
| SCIP_RETCODE graph_pc_contractEdgeUnordered | ( | SCIP * | scip, |
| GRAPH * | g, | ||
| int * | solnode, | ||
| int | t, | ||
| int | s | ||
| ) |
contract an edge of (rooted) prize-collecting Steiner tree problem or maximum-weight connected subgraph problem; method decides whether to contract s into t or vice-versa. Offset is added to surviving node
- Parameters
-
scip SCIP data structure g the graph solnode solution nodes or NULL t tail node to be contracted s head node to be contracted
Definition at line 2439 of file graph_pcbase.c.
References GRAPH::grad, graph_pc_contractEdge(), graph_pc_termIsNonLeafTerm(), SCIP_CALL, SCIP_OKAY, and GRAPH::source.
Referenced by pcContractWithAdjacentTerm().
◆ graph_pc_isPc()
is this graph a prize-collecting variant?
- Parameters
-
g the graph
Definition at line 2463 of file graph_pcbase.c.
References NULL, STP_PCSPG, STP_RPCSPG, and GRAPH::stp_type.
Referenced by blctreeBuildNodeMap(), blctreeComputeBottlenecks(), blctreeComputeEdgesState(), blockEdgesWithGlobalFixings(), bottleneckGetDist(), bottleneckMarkEqualityEdges(), closeNodesRunCompute(), computeSteinerTree(), computeSteinerTree_tryConnectNodePcMw(), computeSteinerTreeRedCostsPcMw(), dbgBottleneckFromLeafIsDominated(), delPseudoDeleteVertex(), distCloseNodesCompute(), distGetRestricted(), extInitRedCostArraysPc(), extInnerNodeAdd(), extInnerNodeRemoveTop(), extProbIsPc(), extreduce_bottleneckMarkRootPath(), extreduce_checkComponent(), extreduce_deleteArcs(), extreduce_deleteEdges(), extreduce_deleteGeneralStars(), extreduce_distDataInit(), extreduce_mstLevelHorizontalAdd(), extreduce_mstLevelHorizontalAddEmpty(), extreduce_mstLevelVerticalAddEmpty(), extreduce_mstLevelVerticalAddLeaf(), extreduce_pcdataIsClean(), extreduce_pseudoDeleteNodes(), extreduce_sdshorizontalInSync(), extreduce_sdsTopInSync(), extreduce_sdsverticalInSync(), extreduce_spgCheck3ComponentSimple(), extreduce_treeRecompCosts(), extStackAddCompsExpanded(), extTreeRuleOutSingletonImplied(), fixVarsRedbased(), getBiasedPc(), getEdgeCostUnbiased(), getKeyPathsStar(), graph_copyData(), graph_dijkLimited_initPcShifts(), graph_pack(), graph_path_st_pcmw(), graph_pc_2org(), graph_pc_2trans(), graph_pc_enforceNonLeafTerm(), graph_pc_finalizeSubgraph(), graph_pc_getBiased(), graph_pc_getOrgCostsCsr(), graph_pc_initSubgraph(), graph_pc_knotHasMaxPrize(), graph_pc_shiftNonLeafCosts(), graph_pc_solGetObj(), graph_pc_subtractPrize(), graph_pc_termToNonTerm(), graph_pc_updateSubgraphEdge(), graph_printInfo(), graph_printInfoReduced(), graph_transPcGetSap(), graph_voronoiRepair(), graph_voronoiTerms(), graph_voronoiWithDist(), initCostOrgPc(), insertionInitInsert(), localKeyVertexHeuristics(), localVertexInsertion(), mstCompLeafGetSDs(), mstCompLeafGetSDsToAncestors(), mstCompLeafToAncestorsBiasedRuleOut(), mstCompRuleOut(), mstLevelHorizontalAddSds(), mstLevelLeafExit(), mstLevelLeafInit(), mstLevelLeafTryExtMst(), pcmwSetEdgeCosts(), pcmwUpdateBestSol_csrInSync(), pcsubtreePruneForProfit(), prInit(), pseudodeleteBiasedIsPromising(), pseudodeleteDeleteComputeCutoffs(), pseudodeleteDeleteNode(), pseudodeleteNodeIsPromising(), reduce_applyPseudoDeletions(), reduce_bd34(), reduce_bound(), reduce_da(), reduce_daPcMw(), reduce_getMinNreductions(), reduce_identifyNonLeafTerms(), reduce_removeDeg0NonLeafTerms(), reduce_simple_pc(), reduce_sl(), reduce_sollocalRebuildTry(), reduce_unconnected(), reduceExact(), runTmPcMW(), runTmPcMW_mode(), SCIP_DECL_HEUREXEC(), selectBranchingVertexBySol(), solstp_isValid(), solstp_pcGetObjCsr(), solstp_prune(), solstp_pruneFromTmHeur(), solstp_pruneFromTmHeur_csr(), spg3StarNeighborRuleOut(), spg4VerticesRuleOut(), stpsol_pruningIsPossible(), strongPruneSteinerTreePc_csr(), tmBaseInit(), and useRedcostdata().
◆ graph_pc_isMw()
is this graph a maximum-weight variant?
- Parameters
-
g the graph
Definition at line 2475 of file graph_pcbase.c.
References NULL, STP_BRMWCSP, STP_MWCSP, STP_RMWCSP, and GRAPH::stp_type.
Referenced by applyBranchHistoryToGraph(), blctreeBuildMst(), boundPruneHeur(), boundPruneHeurMw(), computeSteinerTree(), contractEdgeNoFixedEnd(), contractEdgeWithFixedEnd(), extreduce_deleteEdges(), fixVarsRedbased(), getBiasedMw(), graph_pc_contractEdge(), graph_pc_enforceNode(), graph_pc_enforceNonLeafTerm(), graph_pc_getBiased(), graph_pc_knotIsFixedTerm(), graph_pc_knotToFixedTerm(), graph_pc_nonTermToFixedTerm(), graph_pc_realDegree(), graph_pc_subtractPrize(), graph_sdPaths(), graphisValidPcMw(), initCostsAndPrioLP(), initReceivedSubproblem(), mwContract0WeightVertices(), mwContractNonPositiveChain(), mwContractTerminalsChainWise(), mwContractTerminalsSimple(), mwGetNchains(), mwTraverseChain(), pcsubtreePruneForProfit(), propgraphFixEdge(), reduce_ans(), reduce_ansAdv(), reduce_ansAdv2(), reduce_boundPruneHeur(), reduce_da(), reduce_getMinNreductions(), reduce_nnp(), reduceExact(), reduceWithEdgeFixingBounds(), strongPruneSteinerTreePc(), tpathsGetDistNew(), and updateNodeReplaceBounds().
◆ graph_pc_isPcMw()
is this graph a prize-collecting or maximum-weight variant?
- Parameters
-
g the graph
Definition at line 2487 of file graph_pcbase.c.
References NULL, STP_BRMWCSP, STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, and GRAPH::stp_type.
Referenced by addRedsol(), applyBranchHistoryToGraph(), applyEdgestateToProb(), blctreeBuildMst(), branchruleGetType(), buildsolgraph(), computeHistory(), computeHistoryPcMw(), computePertubedSol(), computeReducedProbSolution(), computeReducedProbSolutionBiased(), computeStarts(), computeSteinerTree(), computeSteinerTree_allFixedTermsAreReached(), computeSteinerTree_allPseudoTermsAreReached(), computeSteinerTree_execPcMw(), computeSteinerTree_execPcMwFull(), computeSteinerTreeDijk(), computeSteinerTreeDijkPcMw(), computeSteinerTreeRedCostsPcMw(), computeSteinerTreeSingleNode(), createVariables(), cutNodesSetDfsRoot(), cutNodesTreeBuildSteinerTree(), cutNodesTreeDeleteComponents(), daPcFindRoots(), delPseudoInit(), delPseudoInitForCheck(), dualascent_paths(), enumeration_findSolPcMw(), enumeration_isPossible(), extGetSd(), extGetSdPcUpdate(), extInit(), extreduce_checkArc(), extreduce_checkEdge(), extreduce_distDataInit(), extreduce_edgeIsValid(), extreduce_extPermaInit(), extreduce_init(), extreduce_mstbiasedCheck3NodeSimple(), extreduce_mstTopCompExtObjValid(), extreduce_mstTopCompInSync(), extreduce_mstTopCompObjValid(), extreduce_mstTopLevelBaseObjValid(), extTreeGetDirectedRedcostProper(), fixVarsExtendedRed(), fixVarsRedbased(), fixVarsRedbasedIsPromising(), getBoundaryPathCost(), getBoundaryPathCostPrized(), getBoundchanges(), getBoundchangesPcMW(), getEdgeCosts(), getEdgeReductionRatio(), getGraphStatesDirected(), getHighSolDegVertex(), getKeyPathReplaceCost(), getKeyPathsStar(), getKeyPathUpper(), getNewPrizeNode(), getOrgNodeToNodeMap(), getReductionRatios(), getReductionRatiosPcMw(), getSolObj(), getTmMode(), graph_copyData(), graph_csr_build(), graph_csr_chgCosts(), graph_edge_addSubgraph(), graph_edge_printInfo(), graph_edge_reinsert(), graph_fixed_addNodePc(), graph_fixed_moveNodePc(), graph_get4nextTTerms(), graph_getIsTermArray(), graph_init_dcsr(), graph_initHistory(), graph_initPseudoAncestorsSized(), graph_isMarked(), graph_knot_delPseudoAncestors(), graph_knot_printInfo(), graph_knot_replaceDeg2(), graph_mark(), graph_pack(), graph_path_st_pcmw(), graph_path_st_pcmw_extendOut(), graph_path_st_pcmw_full(), graph_pc_2org(), graph_pc_2trans(), graph_pc_deleteTerm(), graph_pc_edgeIsExtended(), graph_pc_enforceNode(), graph_pc_evalTermIsNonLeaf(), graph_pc_finalizeSubgraph(), graph_pc_fixedTermToNonTerm(), graph_pc_getBiased(), graph_pc_getOrgCosts(), graph_pc_getReductionRatios(), graph_pc_getTwinTerm(), graph_pc_initSubgraph(), graph_pc_knotChgPrize(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsPropPotTerm(), graph_pc_knotToNonTermProperty(), graph_pc_markOrgGraph(), graph_pc_nFixedTerms(), graph_pc_nNonFixedTerms(), graph_pc_nNonLeafTerms(), graph_pc_nonLeafTermIsEnforced(), graph_pc_nProperPotentialTerms(), graph_pc_realDegree(), graph_pc_solGetObj(), graph_pc_subtractPrize(), graph_pc_term2edgeIsConsistent(), graph_pc_termToNonLeafTerm(), graph_pc_termToNonTerm(), graph_pc_transOrgAreConistent(), graph_printEdgeConflicts(), graph_printInfo(), graph_printInfoReduced(), graph_pseudoAncestors_addToNode(), graph_sdStar(), graph_sdStarBiased(), graph_sdWalks(), graph_sdWalks_csr(), graph_sdWalksConnected(), graph_sdWalksExt(), graph_sdWalksExt2(), graph_sdWalksTriangle(), graph_subgraphExtract(), graph_subgraphReinsert(), graph_tpathsSetAll2(), graph_tpathsSetAll3(), graph_transPcGetRsap(), graph_valid(), graph_valid_ancestors(), graph_valid_pseudoAncestors(), graph_validInput(), graph_voronoiRepair(), graph_writeReductionRatioStats(), graph_writeReductionRatioStatsLive(), graph_writeStp(), graphisValidPcMw(), impliedNodesAddTerm(), initCostsAndPrioLP(), initPropAtFirstCall(), initReceivedSubproblem(), insertionGetCandidateEdges(), insertionInitInsert(), insertionRestoreTree(), isLastTerm(), localKeyVertexHeuristics(), localRun(), localVertexInsertion(), nodesolUpdate(), packNodes(), packPcMwInit(), pcBiasCostsDCSR(), pcmwGetNewEdgePrize(), pcmwGetSolRoot(), pcmwReduceTerm0Prize(), pcmwUpdate(), pcSdToNodeMark(), pcSdToNodeUnmark(), presolveStp(), probAllowsSolBranching(), propgraphApplyBoundchanges(), propgraphApplyImplicationsPcMw(), propgraphDeleteEdge(), propgraphDeleteNode(), propgraphFixEdge(), propgraphFixNode(), propgraphMarkFixedTermsPcMw(), prunegraphInit(), pruneSteinerTreePc(), pruneSteinerTreePc_csr(), pseudodeleteNodeIsPromising(), redcostGraphBuild(), redcostGraphMark(), redcosts_forLPget(), reduce_bd34(), reduce_bd34WithSd(), reduce_bdkWithSd(), reduce_bound(), reduce_contract0Edges(), reduce_dapaths(), reduce_daSlackPrune(), reduce_deleteConflictEdges(), reduce_extendedEdge(), reduce_impliedNodesGet(), reduce_impliedNodesRepair(), reduce_impliedProfitBased(), reduce_nonTerminalComponents(), reduce_sdStar(), reduce_sdStarPc(), reduce_sdStarPc2(), reduce_sdWalk(), reduce_sdWalk_csr(), reduce_sdWalkExt(), reduce_sdWalkExt2(), reduce_sdWalkTriangle(), reduce_solInit(), reduce_sollocalInit(), reduce_sollocalRebuildTry(), reduce_solPack(), reduceCheckEdge(), reduceFixedVars(), reduceLurk(), removeEdge(), replaceEdgeByPath(), reroot(), retransformReducedProbSolution(), ruleOutSubtree(), runTm(), runTmPcMW(), SCIP_DECL_CONSSEPALP(), SCIP_DECL_HEUREXEC(), SCIPprobdataCreateFromGraph(), SCIPprobdataProbIsAdversarial(), SCIPprobdataWriteSolution(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurLocalExtendPcMwImp(), SCIPStpHeurLocalExtendPcMwOut(), SCIPStpHeurLurkPruneRun(), SCIPStpHeurRecExclude(), SCIPStpHeurSlackPruneRun(), SCIPStpHeurTMBuildTree(), SCIPStpHeurTMRun(), SCIPStpHeurTMRunLP(), sdprofitBuild(), sdprofitBuild1stOnly(), sdStarInit(), selectBranchingVertexByDegree(), selectBranchingVertexBySol(), sepaspecial_pcimplicationsInit(), setCostToOrgPc(), setCostToOrgPcPreState(), setParams(), shortestpath_computeSteinerTreePcMw(), shortestpath_computeSteinerTreePcMwFull(), shortestpath_pcInit(), solgraphSelectSolsDiff(), solhistory_computeHistory(), solIsTrivialPcMw(), solstp_convertCsrToGraph(), solstp_getObjBounded(), solstp_getObjCsr(), solstp_getOrg(), solstp_getTrivialSol(), solstp_isValid(), solstp_pcConnectDummies(), solstp_pcGetObjCsr(), solstp_pcGetSolRoot(), solstp_prune(), solstp_pruneFromTmHeur(), solstp_pruneFromTmHeur_csr(), strongPruneSteinerTreePc(), strongPruneSteinerTreePc_csr(), supergraphComputeMst(), treeDistsAreFlawed(), updateEdgestateFromRed(), updateEdgestateFromRedPcmw(), and validateEdgestate().
◆ graph_pc_getRoot2PtermEdge()
| int graph_pc_getRoot2PtermEdge | ( | const GRAPH * | graph, |
| int | pseudoterm | ||
| ) |
get edge from root to (pseudo) terminal
- Parameters
-
graph the graph pseudoterm the pseudo terminal
Definition at line 2499 of file graph_pcbase.c.
References EAT_LAST, GRAPH::ieat, GRAPH::inpbeg, NULL, GRAPH::source, and GRAPH::tail.
Referenced by computeReducedProbSolutionBiased(), createVariables(), findRootsMark(), getBoundchangesPcMW(), graph_pc_enforcePseudoTerm(), graph_pc_knotChgPrize(), graph_pc_subtractPrize(), initCostsAndPrioLP(), initReceivedSubproblem(), propgraphApplyImplicationsPcMw(), sepaspecial_pcimplicationsSeparate(), solgraphAdaptForPcMw(), and termDeleteExtension().
◆ graph_pc_nFixedTerms()
| int graph_pc_nFixedTerms | ( | const GRAPH * | graph | ) |
get number of fixed terminals (not counting the aritificial root)
- Parameters
-
graph the graph
Definition at line 2526 of file graph_pcbase.c.
References graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), GRAPH::knots, nnodes, and NULL.
Referenced by buildsolgraph(), computeSteinerTree_execRpcMw(), graph_pc_nNonFixedTerms(), graph_printInfo(), graph_printInfoReduced(), rpcTryFullReduce(), solstp_getOrg(), solstp_isValid(), and updatePropgraph().
◆ graph_pc_nNonFixedTerms()
| int graph_pc_nNonFixedTerms | ( | const GRAPH * | graph | ) |
Returns number of non-fixed terminals. Note that it is equal to the number of the proper potential terminals if g->extended, because in this case the non-leaf terminals are not marked explicitly.
- Parameters
-
graph the graph
Definition at line 2549 of file graph_pcbase.c.
References graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_nFixedTerms(), NULL, and GRAPH::terms.
Referenced by computeSteinerTree_execPcMw(), graph_pc_getReductionRatios(), graph_pc_nProperPotentialTerms(), propgraphApplyImplicationsPcMw(), SCIPStpHeurLocalExtendPcMwImp(), and sepaspecial_pcimplicationsSeparate().
◆ graph_pc_nNonLeafTerms()
| int graph_pc_nNonLeafTerms | ( | const GRAPH * | graph | ) |
returns number of non-leaf terminals
- Parameters
-
graph the graph
Definition at line 2564 of file graph_pcbase.c.
References graph_get_nNodes(), graph_pc_isPcMw(), graph_pc_knotIsNonLeafTerm(), and nnodes.
Referenced by cutNodesTreeBuildSteinerTree(), graph_pc_nProperPotentialTerms(), graph_printInfo(), graph_printInfoReduced(), graph_transRpc2SpgTrivial(), graph_transRpcGetSpg(), reduce_pc(), and reduce_redLoopPc().
◆ graph_pc_nProperPotentialTerms()
| int graph_pc_nProperPotentialTerms | ( | const GRAPH * | graph | ) |
returns number of proper potential terminals (potential terminals excluding non-leaf terminals)
- Parameters
-
graph the graph
Definition at line 2582 of file graph_pcbase.c.
References GRAPH::extended, graph_pc_isPcMw(), graph_pc_nNonFixedTerms(), graph_pc_nNonLeafTerms(), and NULL.
Referenced by graph_printInfo(), graph_printInfoReduced(), graph_transRpc2SpgTrivial(), graph_transRpcGetSpg(), reduce_redLoopPc(), rpcTryFullReduce(), sepaspecial_pcimplicationsInit(), sepaspecial_pcimplicationsSeparate(), and solstp_isValid().
◆ graph_pc_solGetObj()
| SCIP_Real graph_pc_solGetObj | ( | SCIP * | scip, |
| const GRAPH * | g, | ||
| const int * | soledge, | ||
| SCIP_Real | offset | ||
| ) |
compute solution value for given edge-solution array (CONNECT/UNKNOWN) and offset, takes prizes into account!
- Parameters
-
scip SCIP data structure g the graph soledge solution offset offset
Definition at line 2603 of file graph_pcbase.c.
References CONNECT, GRAPH::cost, GRAPH::extended, graph_get_nEdges(), graph_get_nNodes(), graph_pc_getNonLeafTermOffset(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_knotIsNonLeafTerm(), nnodes, GRAPH::prize, SCIP_CALL_ABORT, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGT(), and solstp_setVertexFromEdge().
Referenced by computeSteinerTree(), and getSolObj().
◆ graph_pc_getTwinTerm()
| int graph_pc_getTwinTerm | ( | const GRAPH * | g, |
| int | vertex | ||
| ) |
get twin-terminal
- Parameters
-
g the graph vertex the vertex
Definition at line 2653 of file graph_pcbase.c.
References GRAPH::edges, graph_pc_isPcMw(), GRAPH::head, Is_anyTerm, GRAPH::tail, GRAPH::term, and GRAPH::term2edge.
Referenced by computeReducedProbSolutionBiased(), createVariables(), dapathsFixPotTerms(), daPcMarkRoots(), daRpcmwDeleteTermIncidents(), findRootsMark(), getBoundchangesPcMW(), graph_pc_deleteTerm(), graph_pc_enforcePseudoTerm(), graph_pc_knotChgPrize(), graph_pc_subtractPrize(), graph_transPcmw2rooted(), initCostsAndPrioLP(), initReceivedSubproblem(), propgraphApplyImplicationsPcMw(), reduce_unconnectedRpcRmwInfeas(), and sepaspecial_pcimplicationsSeparate().
◆ graph_pc_isUnrootedPcMw()
is this graph a un-rooted prize-collecting or rooted maximum-weight variant?
- Parameters
-
g the graph
Definition at line 2669 of file graph_pcbase.c.
References NULL, STP_MWCSP, STP_PCSPG, and GRAPH::stp_type.
Referenced by reduce_sl(), SCIP_DECL_RELAXEXEC(), SCIPStpHeurTMBuildTreePcMw(), sdprofitBuild(), and sdprofitBuild1stOnly().
◆ graph_pc_isRootedPcMw()
is this graph a rooted prize-collecting or rooted maximum-weight variant?
- Parameters
-
g the graph
Definition at line 2681 of file graph_pcbase.c.
References NULL, STP_BRMWCSP, STP_RMWCSP, STP_RPCSPG, and GRAPH::stp_type.
Referenced by applyBranchHistoryToGraph(), blctreeBuildMst(), buildsolgraph(), collectFixedTerminals(), collectRoots(), computeHistoryPcMw(), computeStarts(), computeSteinerTree_execPcMw(), computeSteinerTree_execPcMwFull(), computeSteinerTree_execRpcMw(), computeSteinerTreeSingleNode(), computeSteinerTreeTM(), contractEdgeWithFixedEnd(), createInitialCuts(), cutNodesSetDfsRoot(), daOrderRoots(), dapathsFixPotTerms(), daPcFindRoots(), daRoundExit(), daRoundInit(), daRpcmwDeleteTermIncidents(), dualascent_paths(), enumeration_findSolPcMw(), enumeration_isPossible(), findSolPcMw(), findSolRPcMw(), fixVarsExtendedRed(), getBiasedMw(), getBiasedPc(), graph_copyData(), graph_dijkLimited_initPcShifts(), graph_isMarked(), graph_mark(), graph_pack(), graph_path_st_pcmw(), graph_path_st_pcmw_full(), graph_path_st_rpcmw(), graph_pc_contractEdge(), graph_pc_enforceNode(), graph_pc_enforceNonLeafTerm(), graph_pc_evalTermIsNonLeaf(), graph_pc_getReductionRatios(), graph_pc_knotIsDummyTerm(), graph_pc_knotToFixedTerm(), graph_pc_markOrgGraph(), graph_pc_nFixedTerms(), graph_pc_nNonFixedTerms(), graph_pc_nonTermToFixedTerm(), graph_pc_realDegree(), graph_pc_term2edgeIsConsistent(), graph_transPcGetRsap(), graph_transPcmw2rooted(), graphisValidPcMw(), initReceivedSubproblem(), insertionGetCandidateEdges(), isLastTerm(), isMaxprizeTerm(), localKeyVertexHeuristics(), mwContractTerminalsChainWise(), mwContractTerminalsSimple(), packNodes(), packPcMwVanished(), pcmwFindMax2Terms(), pcmwGetSolRoot(), pcmwGetStartNodes(), pcmwUpdate(), pcsolMarkGraphNodes(), pcsolMarkGraphNodes_csr(), propgraphApplyBoundchanges(), propgraphFixNode(), propgraphMarkFixedTermsPcMw(), propgraphPruneUnconnected(), pruneSteinerTreePc(), pruneSteinerTreePc_csr(), redcostGraphBuild(), redcostGraphMark(), redcosts_initializeDistances(), redLoopInnerMw(), redLoopInnerPc(), reduce_boundMw(), reduce_da(), reduce_dapaths(), reduce_daSlackPrune(), reduce_redLoopMw(), reduce_simple_mw(), reduce_unconnectedRpcRmwInfeas(), reduceRootedProb(), runTmPcMW_mode(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurPruneRun(), SCIPStpHeurTMBuildTreePcMw(), shortestpath_computeSteinerTreePcMw(), shortestpath_computeSteinerTreeRpcMw(), solgraphAdaptForPcMw(), solIsTrivialPcMw(), solstp_getOrg(), solstp_isValid(), solstp_pcConnectDummies(), solstp_pcGetSolRoot(), stptest_graphSetUpRpcOrg(), strongPruneSteinerTreePc(), termDeleteExtension(), updateEdgestateFromRedPcmw(), updatePropgraph(), and updateSolution().