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"

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

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

g	the graph
k	the 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(), cutNodesCompute(), 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

p	the graph
term	terminal 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

p	the graph
node	node to be changed
term	terminal 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()

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

deletes node

Parameters

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

Definition at line 111 of file graph_node.c.

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

Referenced by ansDeleteVertex(), cutNodesTreeDeleteComponents(), delPseudoDeleteVertex(), graph_knot_contract(), graph_knot_replaceDeg2(), graph_pc_deleteTerm(), graph_transPcGetRsap(), graph_transPcmw2rooted(), pcmwReduceTerm0Prize(), propgraphApplyImplicationsPcMw(), propgraphDeleteNode(), pseudodeleteExecute(), reduce_daSlackPrune(), reduce_nodesDeg1(), reduce_npv(), reduce_simple_sap(), reduce_unconnected(), reduce_unconnectedForDirected(), reduce_unconnectedRpcRmwInfeas(), reduceRootedProb(), reduceWithNodeFixingBounds(), and rpcTryFullReduce().

◆ graph_knot_delFull()

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

deletes node, and also adapts DCSR storage

Parameters

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

SCIP_RETCODE graph_knot_replaceDeg2	(	SCIP *	scip,
		int	vertex,
		SCIP_Real	edgecost,
		int	ancestornode,
		GRAPH *	g,
		SCIP_Bool *	edgeEliminated
	)

pseudo deletes non-terminal of degree 2

Parameters

scip	SCIP data structure
vertex	the vertex to replace
edgecost	new edge cost
ancestornode	node to copy ancestors from or -1
g	the graph
edgeEliminated	edge eliminated? (due to conflict)

Definition at line 158 of file graph_node.c.

References GRAPH::ancestors, BMScopyMemoryArray, GRAPH::cost, Edge_even, FALSE, flipedge, GRAPH::grad, graph_edge_del(), graph_edge_delHistory(), graph_edge_getAncestors(), graph_edge_getPseudoAncestors(), graph_edge_nPseudoAncestors(), graph_edge_redirect(), graph_knot_del(), graph_pc_isPcMw(), graph_pseudoAncestors_appendCopyArrayToEdge(), graph_pseudoAncestors_appendCopyNodeToEdge(), graph_typeIsUndirected(), graph_valid_pseudoAncestors(), GRAPH::head, Is_term, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::pcancestors, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPdebugMessage, SCIPfreeBlockMemoryArrayNull, SCIPintListNodeAppend(), SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), SCIPisEQ(), GRAPH::term, and TRUE.

Referenced by pcReduceKnotDeg2(), and reduce_simple().

◆ graph_knot_contract()

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

contracts node s into node t

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 (surviving node)
s	head node to be contracted

Definition at line 264 of file graph_node.c.

References singleton_ancestors_edge::ancestors, GRAPH::ancestors, CONNECT, GRAPH::contracttrace, GRAPH::cost, EAT_LAST, Edge_anti, Edge_even, FALSE, flipedge, flipedge_Uint, GRAPH::grad, graph_edge_del(), graph_edge_delPseudoAncestors(), graph_edge_nPseudoAncestors(), graph_knot_chg(), graph_knot_del(), graph_knot_isInRange(), graph_pseudoAncestors_appendCopySingToEdge(), graph_singletonAncestors_freeMembers(), graph_singletonAncestors_init(), graph_typeIsUndirected(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, section::mark, NULL, GRAPH::oeat, GRAPH::outbeg, singleton_ancestors_edge::revancestors, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPdebugMessage, SCIPfreeBlockMemoryArray, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), SCIPisGT(), SCIPisLE(), GRAPH::source, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by borderNodesContract(), contractEdgeNoFixedEnd(), contractEdgeWithFixedEnd(), graph_knot_contractFixed(), graph_knot_contractLowdeg2High(), mwContract0WeightVertices(), reduce_contract0Edges(), reduce_simple(), and reduce_simple_sap().

◆ 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

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
edge	the edge
t	tail node to be contracted (surviving node)
s	head 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

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 539 of file graph_node.c.

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

Referenced by reduce_simple().

SCIP

Detailed Description

Functions

Function Documentation

◆ graph_knotIsNWLeaf()

◆ graph_knot_isInRange()

◆ graph_knot_add()

◆ graph_knot_chg()

◆ graph_knot_del()

◆ graph_knot_delFull()

◆ graph_knot_replaceDeg2()

◆ graph_knot_contract()

◆ graph_knot_contractFixed()

◆ graph_knot_contractLowdeg2High()