Scippy

SCIP

Solving Constraint Integer Programs

graph_node.c File Reference

Detailed Description

includes graph node methods for Steiner problems

Author
Daniel Rehfeldt

Graph node methods for Steiner problems

Definition in file graph_node.c.

#include "graph.h"
#include "portab.h"

Go to the source code of this file.

Functions

SCIP_Bool graph_knotIsNWLeaf (const GRAPH *g, int vertex)
 
SCIP_Bool graph_knot_isInRange (const GRAPH *g, int k)
 
void graph_knot_add (GRAPH *p, int term)
 
void graph_knot_chg (GRAPH *p, int node, int term)
 
void graph_knot_del (SCIP *scip, GRAPH *g, int k, SCIP_Bool freeancestors)
 
void graph_knot_delFull (SCIP *scip, GRAPH *g, int k, SCIP_Bool freeancestors)
 
SCIP_RETCODE graph_knot_replaceDeg2 (SCIP *scip, int vertex, SCIP_Real edgecost, int ancestornode, GRAPH *g, SCIP_Bool *edgeEliminated)
 
SCIP_RETCODE graph_knot_contract (SCIP *scip, GRAPH *g, int *solnode, int t, int s)
 
SCIP_RETCODE graph_knot_contractFixed (SCIP *scip, GRAPH *g, int *solnode, int edge, int t, int s)
 
SCIP_RETCODE graph_knot_contractLowdeg2High (SCIP *scip, GRAPH *g, int *solnode, int t, int s)
 

Function Documentation

◆ graph_knotIsNWLeaf()

SCIP_Bool graph_knotIsNWLeaf ( const GRAPH g,
int  vertex 
)
Parameters
gthe graph
vertexthe vertex

Definition at line 35 of file graph_node.c.

References GRAPH::cost, EAT_LAST, FARAWAY, LT, NULL, GRAPH::oeat, GRAPH::outbeg, STP_NWPTSPG, and GRAPH::stp_type.

Referenced by computeStarts(), graph_findCentralTerminal(), graph_knot_printInfo(), nwptstpSetRoot(), reduce_rpt(), and runTm().

◆ graph_knot_isInRange()

SCIP_Bool graph_knot_isInRange ( const GRAPH g,
int  k 
)

is node in range?

Parameters
gthe graph
kthe node

Definition at line 52 of file graph_node.c.

Referenced by addLevel(), bidecomposition_getMarkedSubRoot(), bidecomposition_markSub(), blctreeBuildMst(), blctreeComputeBottlenecks(), blctreeComputeEdgesState(), borderNodesCollect(), borderNodesContract(), bottleneckMarkEqualityPath(), closeNodesRunInit(), computeOrderingFromNode(), computeSteinerTree_execBiased(), cutNodesTreeBuildSteinerTree(), cutNodesTreeMakeTerms(), cutNodesTreeMakeTermsIsComplete(), dapathsRunShortestPaths(), dapathsUpdate(), decomposeCsrIsValid(), decomposeGetFirstMarked(), decomposeGetSubgraph(), dpborder_coreUpdateOrdering(), dpgraphInit(), dpsolverGetSolution(), dualascent_allTermsReachable(), dualascent_execDegCons(), extensionHasImplicationConflict(), extractSubgraphAddEdge(), extractSubgraphAddEdgesWithHistory(), extractSubgraphAddNodes(), extreduce_bottleneckCheckNonLeaves(), extreduce_bottleneckIsDominated(), extreduce_bottleneckIsDominatedBiased(), extreduce_distComputeRestrictedDist(), extreduce_distDataGetSp(), extreduce_mstbiasedCheck3NodeSimple(), extreduce_spgCheck3ComponentSimple(), extreduce_spgCheck3NodeSimple(), extStackTopProcessInitialEdges(), extTreeGetDirectedRedcost(), extTreeGetDirectedRedcostProper(), extTreeStackTopRootRemove(), getTreeRedcosts_dbg(), gmlWriteEdge(), graph_contractTrace(), graph_knot_contract(), graph_knot_del(), graph_knot_delFull(), graph_knot_hasContractTrace(), graph_path_st_dc(), graph_pathInLimitedExec(), graph_tpathsGetClosestTerm(), graph_tpathsGetProfitNodes(), graph_tpathsPrintForNode(), graph_transRpcGetSpg(), graphmarkIsClean(), impliedNodesRemoveTerm(), initSolve(), mincutFree(), redcostGraphBuild(), redcostGraphMark(), reduce_compbuilderPrintSeparators(), reduce_impliedNodesIsValid(), reduce_impliedNodesRepair(), reduce_nodesDeg1(), reduce_sdneighborGetCloseTerms(), reduce_termcompChangeSubgraphToBottleneck(), reduce_termsepaGetNextComp(), reinsertSubgraphAdaptSubToOrgMap(), reinsertSubgraphDeleteOldEdges(), reinsertSubgraphTransferEdges(), reinsertSubgraphTransferTerminals(), sdneighborUpdateExec(), sdqueryAttachBinaryTreeNode(), sdqueryBuildNodesToFullMap(), sdqueryBuildNodesToRmqMap(), subgraphBuild(), subgraphIdentify(), subtreesRemoveNonValids(), termcompMarkPseudoDelNodes(), termcompReduce(), termsepaCsrGetMaxNedges(), termsepaCutIsCorrect(), termsepaStoreCutTry(), termsepaTraverseSinkComp(), tpathsGetKCloseTerms(), tpathsPrintPath(), tpathsRepairExit(), tpathsRepairExitLevel(), tpathsRepairTraverse1st(), tpathsRepairTraverseLevelWithStack(), tpathsRepairTraverseStackAddBelow(), tpathsRepairUpdate1st(), tpathsRepairUpdateLevel(), tpathsScan2nd(), updateBorder(), updateTerminalSource(), and vnoiDataRepairPreprocess().

◆ graph_knot_add()

void graph_knot_add ( GRAPH p,
int  term 
)

add a vertex

Parameters
pthe graph
termterminal property

Definition at line 64 of file graph_node.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(), computeHistory(), distgraphAddNodes(), extractSubgraphAddNodes(), getBiasedMw(), graph_buildCompleteGraph(), graph_grid_create(), graph_load(), graph_obstgrid_create(), graph_pack(), graph_transPc(), graph_transPc2Spg(), graph_transPcGetSap(), graph_transRmw(), graph_transRpc(), graph_transRpc2FixedProper(), graph_transRpcGetSpg(), graph_voronoiWithRadius(), graphBuildV5E5(), localExtendPc(), localInsertion(), localInsertion2(), localInsertion2pc(), localKeyPathExchange(), localKeyPathExchangeMw(), localKeyPathExchangePc(), localKeyPathExchangePc2(), localKeyVertex(), localKeyVertexPc(), localKeyVertexPc2(), packNodes(), pseudoDelDouble(), pseudoDelSingle(), redcostGraphBuild(), reduce_npv(), reduce_sd(), reduce_sdPc(), SCIPStpHeurRecExclude(), subgraphBuild(), supergraphComputeMst(), testBdkSdMstDeletesNodeDeg3(), testBdkSdMstDeletesNodeDeg4(), testBdkSdMstStarDeletesNodeDeg4(), testBdkTreeDistDeletesNodeDeg4(), testBiasedTerminalPathsTo4NextFound(), testBiconnectedComponentsAreFound(), testBiconnectedComponentsAreFound2(), testBiconnectedComponentsAreFound3(), testBiconnectedDecomposition(), testBiconnectedDecomposition2(), testBiconnectedDecomposition3(), testBLCworksFor3Star(), testBLCworksFor3StarAfterReduction(), testBLCworksFor5Tree(), testDaPathsPcMw3EdgesWorks(), testDistCloseNodesAreValid(), testDistCloseNodesPcAreValid1(), testDistCloseNodesPcAreValid2(), testDistCloseNodesPcAreValidAfterDeletion(), testDistDistancesAreValid(), testDistRootPathsAreValid(), testEdgeDeletedBy3LeafSpg(), testEdgeDeletedByCommonRedCostsTargets(), testEdgeDeletedByEqBottleneck(), testEdgeDeletedByEqBottleneck2(), testEdgeDeletedByMst1(), testEdgeDeletedByMst2(), testEdgeDeletedByMultiRedCosts(), testEdgeDeletion1_deprecated(), testEdgeDeletion2_deprecated(), testEdgeDeletion3_deprecated(), testEdgeDeletion4_deprecated(), testEdgeDeletion5_deprecated(), testEdgeNotDeleted1(), testGeneralStarDeletedEdge1(), testGeneralStarDeletedEdge2(), testGeneralStarDeletedEdge3(), testNode3PseudoDeletedByContraction(), testNode3PseudoDeletedByRedCosts1(), testNode3PseudoDeletedBySd1(), testNode3PseudoDeletedBySd2(), testNode3PseudoDeletedBySd3(), testNode3PseudoDeletedBySdBiased(), testNode3PseudoDeletedBySdBiasedSimple(), testNode4PseudoDeletedBySd1(), testNode4PseudoNotDeletedBySd1(), testNsvImpliedContractsCutDistEdge(), testNsvImpliedContractsCutDistMiddleEdge(), testNsvImpliedContractsEdge(), testNsvImpliedContractsEdge2(), testNsvImpliedContractsImpliedToTermEdge(), testPathReplaceDeletesEdge(), testPathReplaceDeletesEdge2(), testPcEdgeDeletedByMst1(), testPcEdgeNotDeleted(), testPcNode3PseudoDeletedBySd1(), testPcNode4PseudoDeletedBySd1(), testPrunedSolIsImprovedPc1(), testPrunedSolIsImprovedPc2(), testRmwAnsDeletesOneEdge(), testRmwAnsDeletesOneNode(), testRmwAnsDeletesTwoNodes(), testRmwChain2DeletesNode(), testRmwNpv3DeletesNode(), testRmwTerminalContraction(), testRmwTerminalDeg1Contraction1(), testRmwTerminalDeg1Contraction2(), testRmwTerminalDeg1Contraction3(), testSdBiasedBottleneckDeletesEdge(), testSdBiasedBottleneckTermPathDeletesEdge(), testSdBiasedDeletesEdge(), testSdCliqueStarDeg3AdjacencyIsCorrect(), testSdCliqueStarDeg3IsCorrect(), testSdCliqueStarDeg3IsCorrect2(), testSdCliqueStarDeg4IsCorrect(), testSdCliqueStarDeletesEdge(), testSdGetterReturnsCorrectSds(), testSdGraphDistsAreValid(), testSdGraphDistsAreValid2(), testSdGraphQueriesAreValid(), testSdGraphStrongBiasedDistsAreValid(), testSdPcKillsEdge1(), testSdPcKillsEdge2(), testSdPcKillsTwoEdges(), testSdRepair(), testSdStarBiasedDeletesEdge(), testSdStarBiasedDeletesEdge2(), testSdStarBiasedDeletesEdge3(), testSdStarPcKillsEdge(), testStar3IsCorrect(), testStar4EdgeIsCorrect(), testStar4IsCorrect(), testStar5IsCorrect(), testTerminalPathsRepair(), testTerminalPathsRepair2(), testTerminalPathsRepair3(), testTerminalPathsTo3NextFound(), testTerminalSeparatorsAreFound(), testTerminalSeparatorsAreFound2(), testTerminalSeparatorsAreFound3(), testTmGivesExpectedTreePcFull1(), testTmGivesExpectedTreePcFull2(), and testTmGivesExpectedTreePcFull3().

◆ graph_knot_chg()

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

change terminal property of a vertex

Parameters
pthe graph
nodenode to be changed
termterminal property

Definition at line 86 of file graph_node.c.

References Is_term, NULL, STP_TERM, STP_TERM_NONE, STP_TERM_NONLEAF, STP_TERM_PSEUDO, GRAPH::term, and GRAPH::terms.

Referenced by applyBranchHistoryToGraph(), boundPruneHeur(), cutNodesTreeMakeTerms(), decomposeExactFixSol(), distgraphAddNodes(), fixVarsDualcost(), getBiasedMw(), graph_grid_create(), graph_knot_contract(), graph_load(), graph_obstgrid_create(), graph_pc_2org(), graph_pc_2trans(), graph_pc_fixedTermToNonTerm(), graph_pc_knotToFixedTerm(), graph_pc_knotToFixedTermProperty(), graph_pc_knotToNonTermProperty(), graph_pc_nonTermToFixedTerm(), graph_transMw(), graph_transNw2pc(), graph_transPc(), graph_transPc2Spg(), graph_transPcGetRsap(), graph_transPcmw2rooted(), graph_transRmw(), graph_transRpc(), graph_transRpc2FixedProper(), initReceivedSubproblem(), keyNodesResetTerms(), keyNodesSetTerms(), localExtendPc(), localInsertion(), localInsertion2(), localInsertion2pc(), localKeyPathExchange(), localKeyPathExchangePc(), localKeyPathExchangePc2(), localKeyVertex(), localKeyVertexPc(), localKeyVertexPc2(), markNonLeafTerms_2trans(), markNonLeafTerms_pretransPc(), nsvEdgeContract(), propgraphFixNode(), reduce_bound(), reduce_boundHop(), reduce_sd(), reduce_sl(), reinsertSubgraphTransferTerminals(), SCIP_DECL_CONSSEPALP(), SCIPStpHeurTMRunLP(), selectBranchingVertexBySol(), sepafullReduceFromSols(), termDeleteExtension(), testBdkSdMstDeletesNodeDeg3(), testBdkSdMstDeletesNodeDeg4(), testBdkSdMstStarDeletesNodeDeg4(), testBdkTreeDistDeletesNodeDeg4(), testBiasedTerminalPathsTo4NextFound(), testBiconnectedComponentsAreFound(), testBiconnectedComponentsAreFound2(), testBiconnectedComponentsAreFound3(), testBiconnectedDecomposition(), testBiconnectedDecomposition2(), testBiconnectedDecomposition3(), testBLCworksFor5Tree(), testDaPathsPcMw3EdgesWorks(), testEdgeDeletion3_deprecated(), testEdgeDeletion4_deprecated(), testEdgeDeletion5_deprecated(), testNsvImpliedContractsCutDistEdge(), testNsvImpliedContractsCutDistMiddleEdge(), testNsvImpliedContractsEdge(), testNsvImpliedContractsEdge2(), testNsvImpliedContractsImpliedToTermEdge(), testRmwAnsDeletesOneEdge(), testRmwAnsDeletesOneNode(), testRmwAnsDeletesTwoNodes(), testRmwChain2DeletesNode(), testRmwNpv3DeletesNode(), testRmwTerminalContraction(), testRmwTerminalDeg1Contraction1(), testRmwTerminalDeg1Contraction2(), testRmwTerminalDeg1Contraction3(), testSdBiasedBottleneckDeletesEdge(), testSdBiasedBottleneckTermPathDeletesEdge(), testSdBiasedDeletesEdge(), testSdCliqueStarDeg3AdjacencyIsCorrect(), testSdCliqueStarDeg3IsCorrect(), testSdCliqueStarDeg3IsCorrect2(), testSdCliqueStarDeg4IsCorrect(), testSdCliqueStarDeletesEdge(), testSdGetterReturnsCorrectSds(), testSdGraphDistsAreValid(), testSdGraphDistsAreValid2(), testSdGraphStrongBiasedDistsAreValid(), testSdPcKillsEdge2(), testSdPcKillsTwoEdges(), testSdRepair(), testSdStarBiasedDeletesEdge(), testSdStarBiasedDeletesEdge2(), testSdStarBiasedDeletesEdge3(), testTerminalPathsRepair(), testTerminalPathsRepair2(), testTerminalPathsRepair3(), testTerminalPathsTo3NextFound(), testTerminalSeparatorsAreFound(), testTerminalSeparatorsAreFound2(), testTerminalSeparatorsAreFound3(), testTmGivesExpectedTreePcFull2(), and testTmGivesExpectedTreePcFull3().

◆ graph_knot_del()

◆ graph_knot_delFull()

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

deletes node, and also adapts DCSR storage

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

Definition at line 131 of file graph_node.c.

References GRAPH::dcsr_storage, EAT_LAST, GRAPH::grad, graph_edge_del(), graph_edge_delFull(), graph_knot_isInRange(), GRAPH::inpbeg, and GRAPH::outbeg.

◆ graph_knot_replaceDeg2()

◆ graph_knot_contract()

◆ graph_knot_contractFixed()

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

contract an edge, given index and by its endpoints, which is to be fixed

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

Definition at line 521 of file graph_node.c.

References graph_fixed_addEdge(), graph_knot_contract(), SCIP_CALL, and SCIP_OKAY.

Referenced by nsvEdgeContract(), reduce_nv(), reduce_nvAdv(), reduce_rpt(), reduce_simple_sap(), and reduce_sl().

◆ graph_knot_contractLowdeg2High()

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

contract endpoint of lower degree into endpoint of higher degree

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

Definition at line 539 of file graph_node.c.

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

Referenced by reduce_simple().