Detailed Description

tests for Steiner tree problem methods

Author: Daniel Rehfeldt

This file implements tests for Steiner problems.

A list of all interface methods can be found in stptest.h.

#include "scip/scip.h"
#include "stptest.h"
#include "graph.h"
#include "portab.h"

Functions
static SCIP_Bool	csrdepoCSRsAreEqual (const CSR csr1, const CSR csr2)

static void	csrdepoFillRandom (int seed, CSR *csrd)

static SCIP_RETCODE	csrdepoTest1 (SCIP *scip)

static SCIP_RETCODE	csrdepoTest2 (SCIP *scip)

void	stptest_graphTearDown (SCIP scip, GRAPH graph)

SCIP_RETCODE	stptest_graphSetUp (SCIP scip, GRAPH graph)

SCIP_RETCODE	stptest_graphSetUpPcOrg (SCIP scip, GRAPH graph, int nnodes_new, int nedges_new)

SCIP_RETCODE	stptest_graphSetUpRpcOrg (SCIP scip, GRAPH graph, int nnodes_new, int nedges_new)

SCIP_RETCODE	stptest_graphSetUpRmwOrg (SCIP scip, GRAPH graph, int nnodes_new, int nedges_new)

SCIP_RETCODE	stptest_graphSetUpRmwExtended (SCIP scip, GRAPH graph, int nnodes_new, int nedges_new)

SCIP_RETCODE	stptest_graphSetUpPcExtended (SCIP scip, GRAPH graph, int nnodes_new, int nedges_new)

SCIP_RETCODE	stptest_graphSetUpRpcExtended (SCIP scip, GRAPH graph, int nnodes_new, int nedges_new)

SCIP_RETCODE	stptest_csrdepo (SCIP *scip)

Function Documentation

◆ csrdepoCSRsAreEqual()

static SCIP_Bool csrdepoCSRsAreEqual	(	const CSR *	csr1,
		const CSR *	csr2
	)

static

are the CSRs equal?

Parameters

csr1	csr
csr2	csr

Definition at line 36 of file stptest_graph.c.

References csr_storage::cost, EQ, FALSE, csr_storage::head, csr_storage::nedges_max, csr_storage::nnodes, SCIPdebugMessage, csr_storage::start, and TRUE.

Referenced by csrdepoTest2().

◆ csrdepoFillRandom()

static void csrdepoFillRandom	(	int	seed,
		CSR *	csrd
	)

static

simple pseudo random fill of CSRs

Parameters

seed	seed
csrd	csr

Definition at line 83 of file stptest_graph.c.

References csr_storage::cost, csr_storage::head, csr_storage::nedges_max, nnodes, csr_storage::nnodes, SCIP_Real, and csr_storage::start.

Referenced by csrdepoTest1(), and csrdepoTest2().

◆ csrdepoTest1()

static SCIP_RETCODE csrdepoTest1 ( SCIP * scip )

static

first test: Simple additions and deletions

Parameters

scip	SCIP data structure

Definition at line 118 of file stptest_graph.c.

References csrdepoFillRandom(), graph_csrdepo_addEmptyTop(), graph_csrdepo_emptyTopSetMarked(), graph_csrdepo_free(), graph_csrdepo_getEmptyTop(), graph_csrdepo_init(), graph_csrdepo_isEmpty(), graph_csrdepo_removeTop(), csr_storage::nedges_max, csr_storage::nnodes, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, and SCIPdebugMessage.

Referenced by stptest_csrdepo().

◆ csrdepoTest2()

static SCIP_RETCODE csrdepoTest2 ( SCIP * scip )

static

second test: Make sure that the CSRs are stored correctly

Parameters

scip	SCIP data structure

Definition at line 173 of file stptest_graph.c.

References csrdepoCSRsAreEqual(), csrdepoFillRandom(), graph_csr_alloc(), graph_csr_free(), graph_csrdepo_addEmptyTop(), graph_csrdepo_emptyTopSetMarked(), graph_csrdepo_free(), graph_csrdepo_getCSR(), graph_csrdepo_getEmptyTop(), graph_csrdepo_init(), graph_csrdepo_isEmpty(), graph_csrdepo_removeTop(), SCIP_CALL, SCIP_ERROR, SCIP_OKAY, and SCIPdebugMessage.

Referenced by stptest_csrdepo().

◆ stptest_graphTearDown()

void stptest_graphTearDown	(	SCIP *	scip,
		GRAPH *	graph
	)

frees, etc.

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 274 of file stptest_graph.c.

References graph_free(), graph_path_exit(), NULL, and TRUE.

Referenced by stptest_extreduceTearDown(), testBdkSdMstDeletesNodeDeg3(), testBdkSdMstDeletesNodeDeg4(), testBdkSdMstStarDeletesNodeDeg4(), testBdkTreeDistDeletesNodeDeg4(), testBiasedTerminalPathsTo4NextFound(), testBiconnectedComponentsAreFound(), testBiconnectedComponentsAreFound2(), testBiconnectedComponentsAreFound3(), testBiconnectedDecomposition(), testBiconnectedDecomposition2(), testBiconnectedDecomposition3(), testBLCworksFor3Star(), testBLCworksFor3StarAfterReduction(), testBLCworksFor5Tree(), testDaPathsPcMw3EdgesWorks(), testNsvImpliedContractsCutDistEdge(), testNsvImpliedContractsCutDistMiddleEdge(), testNsvImpliedContractsEdge(), testNsvImpliedContractsEdge2(), testNsvImpliedContractsImpliedToTermEdge(), testPathReplaceDeletesEdge(), testPathReplaceDeletesEdge2(), testPrunedSolIsImprovedPc1(), testPrunedSolIsImprovedPc2(), testRmwAnsDeletesOneEdge(), testRmwAnsDeletesOneNode(), testRmwAnsDeletesTwoNodes(), testRmwChain2DeletesNode(), testRmwNpv3DeletesNode(), testRmwTerminalContraction(), testRmwTerminalDeg1Contraction1(), testRmwTerminalDeg1Contraction2(), testRmwTerminalDeg1Contraction3(), testSdBiasedBottleneckDeletesEdge(), testSdBiasedBottleneckTermPathDeletesEdge(), testSdBiasedDeletesEdge(), testSdCliqueStarDeg3AdjacencyIsCorrect(), testSdCliqueStarDeg3IsCorrect(), testSdCliqueStarDeg3IsCorrect2(), testSdCliqueStarDeg4IsCorrect(), testSdCliqueStarDeletesEdge(), testSdGetterReturnsCorrectSds(), testSdGraphDistsAreValid(), testSdGraphDistsAreValid2(), testSdGraphQueriesAreValid(), testSdGraphStrongBiasedDistsAreValid(), testSdRepair(), testSdStarBiasedDeletesEdge(), testSdStarBiasedDeletesEdge2(), testSdStarBiasedDeletesEdge3(), testSdStarPcKillsEdge(), testStar3IsCorrect(), testStar4EdgeIsCorrect(), testStar4IsCorrect(), testStar5IsCorrect(), testTerminalPathsRepair(), testTerminalPathsRepair2(), testTerminalPathsRepair3(), testTerminalPathsTo3NextFound(), testTerminalSeparatorsAreFound(), testTerminalSeparatorsAreFound2(), testTerminalSeparatorsAreFound3(), testTmGivesExpectedTreePcFull1(), testTmGivesExpectedTreePcFull2(), and testTmGivesExpectedTreePcFull3().

◆ stptest_graphSetUp()

SCIP_RETCODE stptest_graphSetUp	(	SCIP *	scip,
		GRAPH *	graph
	)

sets up graph

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 286 of file stptest_graph.c.

References graph_initHistory(), graph_mark(), graph_path_init(), SCIP_CALL, and SCIP_OKAY.

Referenced by stptest_graphSetUpPcExtended(), stptest_graphSetUpRmwExtended(), stptest_graphSetUpRpcExtended(), testBdkSdMstDeletesNodeDeg3(), testBdkSdMstDeletesNodeDeg4(), testBdkSdMstStarDeletesNodeDeg4(), testBdkTreeDistDeletesNodeDeg4(), testBiasedTerminalPathsTo4NextFound(), testBiconnectedComponentsAreFound(), testBiconnectedComponentsAreFound2(), testBiconnectedComponentsAreFound3(), testBiconnectedDecomposition(), testBiconnectedDecomposition2(), testBiconnectedDecomposition3(), testBLCworksFor3Star(), testBLCworksFor3StarAfterReduction(), testBLCworksFor5Tree(), testEdgeDeletedBy3LeafSpg(), testEdgeDeletedByCommonRedCostsTargets(), testEdgeDeletedByEqBottleneck(), testEdgeDeletedByEqBottleneck2(), testEdgeDeletedByMst1(), testEdgeDeletedByMst2(), testEdgeDeletedByMultiRedCosts(), testEdgeDeletion5_deprecated(), testEdgeNotDeleted1(), testGeneralStarDeletedEdge1(), testGeneralStarDeletedEdge2(), testGeneralStarDeletedEdge3(), testNode3PseudoDeletedByContraction(), testNode3PseudoDeletedByRedCosts1(), testNode3PseudoDeletedBySd1(), testNode3PseudoDeletedBySd2(), testNode3PseudoDeletedBySd3(), testNode3PseudoDeletedBySdBiased(), testNode3PseudoDeletedBySdBiasedSimple(), testNode4PseudoDeletedBySd1(), testNode4PseudoNotDeletedBySd1(), testNsvImpliedContractsCutDistEdge(), testNsvImpliedContractsCutDistMiddleEdge(), testNsvImpliedContractsEdge(), testNsvImpliedContractsEdge2(), testNsvImpliedContractsImpliedToTermEdge(), testPathReplaceDeletesEdge(), testPathReplaceDeletesEdge2(), testSdBiasedBottleneckDeletesEdge(), testSdBiasedBottleneckTermPathDeletesEdge(), testSdBiasedDeletesEdge(), testSdCliqueStarDeg3AdjacencyIsCorrect(), testSdCliqueStarDeg3IsCorrect(), testSdCliqueStarDeg3IsCorrect2(), testSdCliqueStarDeg4IsCorrect(), testSdCliqueStarDeletesEdge(), testSdGetterReturnsCorrectSds(), testSdGraphDistsAreValid(), testSdGraphDistsAreValid2(), testSdGraphQueriesAreValid(), testSdGraphStrongBiasedDistsAreValid(), testSdRepair(), testSdStarBiasedDeletesEdge(), testSdStarBiasedDeletesEdge2(), testSdStarBiasedDeletesEdge3(), testStar3IsCorrect(), testStar4EdgeIsCorrect(), testStar4IsCorrect(), testStar5IsCorrect(), testTerminalPathsRepair(), testTerminalPathsRepair2(), testTerminalPathsRepair3(), testTerminalPathsTo3NextFound(), testTerminalSeparatorsAreFound(), testTerminalSeparatorsAreFound2(), and testTerminalSeparatorsAreFound3().

◆ stptest_graphSetUpPcOrg()

SCIP_RETCODE stptest_graphSetUpPcOrg	(	SCIP *	scip,
		GRAPH *	graph,
		int *	nnodes_new,
		int *	nedges_new
	)

sets up graph for (undirected) PC

Parameters

scip	SCIP data structure
graph	the graph
nnodes_new	to store new number of nodes (if != NULL)
nedges_new	to store new number of edge (if != NULL)

Definition at line 301 of file stptest_graph.c.

References graph_pc_2org(), SCIP_CALL, SCIP_OKAY, and stptest_graphSetUpPcExtended().

Referenced by testDistCloseNodesPcAreValid1(), testDistCloseNodesPcAreValid2(), testDistCloseNodesPcAreValidAfterDeletion(), and testSdStarPcKillsEdge().

◆ stptest_graphSetUpRpcOrg()

SCIP_RETCODE stptest_graphSetUpRpcOrg	(	SCIP *	scip,
		GRAPH *	graph,
		int *	nnodes_new,
		int *	nedges_new
	)

sets up graph for rooted PC

Parameters

scip	SCIP data structure
graph	the graph
nnodes_new	to store new number of nodes (if != NULL)
nedges_new	to store new number of edge (if != NULL)

Definition at line 317 of file stptest_graph.c.

References graph_pc_2org(), graph_pc_isRootedPcMw(), SCIP_CALL, SCIP_OKAY, and stptest_graphSetUpRpcExtended().

Referenced by testPcEdgeDeletedByMst1(), testPcEdgeNotDeleted(), testPcNode3PseudoDeletedBySd1(), testPcNode4PseudoDeletedBySd1(), and testSdBiasedBottleneckDeletesEdge().

◆ stptest_graphSetUpRmwOrg()

SCIP_RETCODE stptest_graphSetUpRmwOrg	(	SCIP *	scip,
		GRAPH *	graph,
		int *	nnodes_new,
		int *	nedges_new
	)

sets up graph for RMW

Parameters

scip	SCIP data structure
graph	the graph
nnodes_new	to store new number of nodes (if != NULL)
nedges_new	to store new number of edge (if != NULL)

Definition at line 335 of file stptest_graph.c.

References graph_pc_2org(), SCIP_CALL, SCIP_OKAY, and stptest_graphSetUpRmwExtended().

Referenced by testRmwAnsDeletesOneEdge(), testRmwAnsDeletesOneNode(), testRmwAnsDeletesTwoNodes(), testRmwChain2DeletesNode(), testRmwNpv3DeletesNode(), testRmwTerminalContraction(), testRmwTerminalDeg1Contraction1(), testRmwTerminalDeg1Contraction2(), and testRmwTerminalDeg1Contraction3().

◆ stptest_graphSetUpRmwExtended()

SCIP_RETCODE stptest_graphSetUpRmwExtended	(	SCIP *	scip,
		GRAPH *	graph,
		int *	nnodes_new,
		int *	nedges_new
	)

sets up graph for RMW

Parameters

scip	SCIP data structure
graph	the graph
nnodes_new	to store new number of nodes (if != NULL)
nedges_new	to store new number of edge (if != NULL)

Definition at line 351 of file stptest_graph.c.

References GRAPH::edges, graph_transRmw(), GRAPH::knots, SCIP_CALL, SCIP_OKAY, STP_RMWCSP, GRAPH::stp_type, and stptest_graphSetUp().

Referenced by stptest_graphSetUpRmwOrg(), and testPrunedSolIsImprovedPc2().

◆ stptest_graphSetUpPcExtended()

SCIP_RETCODE stptest_graphSetUpPcExtended	(	SCIP *	scip,
		GRAPH *	graph,
		int *	nnodes_new,
		int *	nedges_new
	)

sets up graph for (undirected) PC

Parameters

scip	SCIP data structure
graph	the graph
nnodes_new	to store new number of nodes (if != NULL)
nedges_new	to store new number of edge (if != NULL)

Definition at line 375 of file stptest_graph.c.

References GRAPH::edges, graph_transPc(), GRAPH::knots, SCIP_CALL, SCIP_OKAY, STP_PCSPG, GRAPH::stp_type, and stptest_graphSetUp().

Referenced by stptest_graphSetUpPcOrg(), testDaPathsPcMw3EdgesWorks(), testPrunedSolIsImprovedPc1(), testPrunedSolIsImprovedPc2(), testTmGivesExpectedTreePcFull1(), testTmGivesExpectedTreePcFull2(), and testTmGivesExpectedTreePcFull3().

◆ stptest_graphSetUpRpcExtended()

SCIP_RETCODE stptest_graphSetUpRpcExtended	(	SCIP *	scip,
		GRAPH *	graph,
		int *	nnodes_new,
		int *	nedges_new
	)

sets up graph for RPC

Parameters

scip	SCIP data structure
graph	the graph
nnodes_new	to store new number of nodes (if != NULL)
nedges_new	to store new number of edge (if != NULL)

Definition at line 400 of file stptest_graph.c.

References GRAPH::edges, graph_transRpc(), GRAPH::knots, SCIP_CALL, SCIP_OKAY, STP_RPCSPG, GRAPH::stp_type, and stptest_graphSetUp().

Referenced by stptest_graphSetUpRpcOrg().

◆ stptest_csrdepo()

SCIP_RETCODE stptest_csrdepo ( SCIP * scip )

tests CSR depository

Parameters

scip	SCIP data structure

Definition at line 423 of file stptest_graph.c.

References csrdepoTest1(), csrdepoTest2(), SCIP_CALL, and SCIP_OKAY.

Referenced by stptest_testAll().

SCIP

Detailed Description

Functions

Function Documentation

◆ csrdepoCSRsAreEqual()

◆ csrdepoFillRandom()

◆ csrdepoTest1()

◆ csrdepoTest2()

◆ stptest_graphTearDown()

◆ stptest_graphSetUp()

◆ stptest_graphSetUpPcOrg()

◆ stptest_graphSetUpRpcOrg()

◆ stptest_graphSetUpRmwOrg()

◆ stptest_graphSetUpRmwExtended()

◆ stptest_graphSetUpPcExtended()

◆ stptest_graphSetUpRpcExtended()

◆ stptest_csrdepo()