stptest_extreduce.c File Reference

Detailed Description

tests for Steiner tree extended reductions

Author

Daniel Rehfeldt

This file implements tests for Steiner problem extended reductions.

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

Definition in file stptest_extreduce.c.

#include <stdio.h>
#include <assert.h>
#include "stptest.h"
#include "portab.h"
#include "graph.h"
#include "reduce.h"
#include "extreduce.h"

Go to the source code of this file.

Macros
#define	STPTEST_EXT_MAXNCLOSENODES   64

Functions
static SCIP_RETCODE	extCheckArc (SCIP *scip, GRAPH *graph, REDCOST *redcostdata, STP_Bool *edgedeleted, int edge, int edgedelete, int nclosenodes, SCIP_Bool *deletable, SCIP_Bool equality)
static SCIP_RETCODE	extCheckEdge (SCIP *scip, GRAPH *graph, REDCOST *redcostdata, STP_Bool *edgedeleted, int edge, SCIP_Bool *deletable, SCIP_Bool allowEquality)
static SCIP_RETCODE	extCheckNode (SCIP *scip, GRAPH *graph, REDCOST *redcostdata, STP_Bool *edgedeleted, int node, SCIP_Bool *deletable, SCIP_Bool allowEquality)
static SCIP_RETCODE	extDeleteNodes (SCIP *scip, GRAPH *graph, REDCOST *redcostdata, SCIP_Bool allowEquality)
static void	extInitRedCostArrays (const GRAPH *graph, REDCOST *redcostdata)
static void	extInitRedCostArraysPc (const GRAPH *graph, REDCOST *redcostdata)
static SCIP_RETCODE	testEdgeDeletion5_deprecated (SCIP *scip, int variant)
static SCIP_RETCODE	testEdgeDeletion4_deprecated (SCIP *scip, int variant)
static SCIP_RETCODE	testEdgeDeletion3_deprecated (SCIP *scip, int variant)
static SCIP_RETCODE	testEdgeDeletion2_deprecated (SCIP *scip, int variant)
static SCIP_RETCODE	testEdgeDeletion1_deprecated (SCIP *scip)
static SCIP_RETCODE	testEdgeDeletedByCommonRedCostsTargets (SCIP *scip)
static SCIP_RETCODE	testEdgeDeletedByMultiRedCosts (SCIP *scip)
static SCIP_RETCODE	testEdgeDeletedByMst1 (SCIP *scip)
static SCIP_RETCODE	testEdgeDeletedByMst2 (SCIP *scip)
static SCIP_RETCODE	testEdgeDeletedByEqBottleneck (SCIP *scip)
static SCIP_RETCODE	testEdgeNotDeleted1 (SCIP *scip)
static SCIP_RETCODE	testEdgeDeletedByEqBottleneck2 (SCIP *scip)
static SCIP_RETCODE	testEdgeDeletedBy3LeafSpg (SCIP *scip)
static SCIP_RETCODE	testNode3PseudoDeletedByRedCosts1 (SCIP *scip)
static SCIP_RETCODE	testNode3PseudoDeletedByContraction (SCIP *scip)
static SCIP_RETCODE	testNode3PseudoDeletedBySdBiasedSimple (SCIP *scip)
static SCIP_RETCODE	testNode3PseudoDeletedBySdBiased (SCIP *scip)
static SCIP_RETCODE	testNode3PseudoDeletedBySd1 (SCIP *scip)
static SCIP_RETCODE	testNode3PseudoDeletedBySd2 (SCIP *scip)
static SCIP_RETCODE	testNode3PseudoDeletedBySd3 (SCIP *scip)
static SCIP_RETCODE	testNode4PseudoDeletedBySd1 (SCIP *scip)
static SCIP_RETCODE	testNode4PseudoNotDeletedBySd1 (SCIP *scip)
static SCIP_RETCODE	testGeneralStarDeletedEdge1 (SCIP *scip)
static SCIP_RETCODE	testGeneralStarDeletedEdge2 (SCIP *scip)
static SCIP_RETCODE	testGeneralStarDeletedEdge3 (SCIP *scip)
static SCIP_RETCODE	testPcEdgeDeletedByMst1 (SCIP *scip)
static SCIP_RETCODE	testPcEdgeNotDeleted (SCIP *scip)
static SCIP_RETCODE	testPcNode3PseudoDeletedBySd1 (SCIP *scip)
static SCIP_RETCODE	testPcNode4PseudoDeletedBySd1 (SCIP *scip)
static SCIP_RETCODE	testPathReplaceDeletesEdge (SCIP *scip)
static SCIP_RETCODE	testPathReplaceDeletesEdge2 (SCIP *scip)
void	stptest_extreduceTearDown (SCIP *scip, GRAPH *graph, REDCOST **redcostdata)
SCIP_RETCODE	stptest_extreduce (SCIP *scip)

Macro Definition Documentation

STPTEST_EXT_MAXNCLOSENODES

#define STPTEST_EXT_MAXNCLOSENODES   64

Definition at line 38 of file stptest_extreduce.c.

Referenced by extCheckEdge(), extCheckNode(), extDeleteNodes(), and testNode3PseudoDeletedBySdBiasedSimple().

Function Documentation

extCheckArc()

static SCIP_RETCODE extCheckArc ( SCIP *  scip, GRAPH *  graph, REDCOST *  redcostdata, STP_Bool *  edgedeleted, int  edge, int  edgedelete, int  nclosenodes, SCIP_Bool *  deletable, SCIP_Bool  equality  )

static

base method for extended edge reduction tests

Parameters

scip	SCIP data structure
graph	the graph
redcostdata	reduced cost data
edgedeleted	marks for each edge whether deleted
edge	the edge/arc to check
edgedelete	delete the edge if possible?
nclosenodes	max. number of close nodes to each node
deletable	is the edge deletable?
equality	allow equality for checks

Definition at line 42 of file stptest_extreduce.c.

References extension_data_permanent::distdata_default, extred_full, extreduce_checkArc(), extreduce_distDataFree(), extreduce_distDataInit(), extreduce_edgeRemove(), extreduce_extPermaFree(), extreduce_extPermaInit(), FALSE, graph_free_dcsr(), graph_init_dcsr(), graph_isMarked(), extension_data_permanent::redcostEqualAllow, SCIP_CALL, and SCIP_OKAY.

Referenced by testEdgeDeletion1_deprecated(), testEdgeDeletion2_deprecated(), testEdgeDeletion3_deprecated(), testEdgeDeletion4_deprecated(), and testEdgeDeletion5_deprecated().

extCheckEdge()

static SCIP_RETCODE extCheckEdge ( SCIP *  scip, GRAPH *  graph, REDCOST *  redcostdata, STP_Bool *  edgedeleted, int  edge, SCIP_Bool *  deletable, SCIP_Bool  allowEquality  )

static

base method for extended edge reduction tests

Parameters

scip	SCIP data structure
graph	the graph
redcostdata	reduced cost data
edgedeleted	array to mark
edge	edge to check
deletable	can edge be deleted?
allowEquality	allow equality for rule-out

Definition at line 84 of file stptest_extreduce.c.

References extension_data_permanent::distdata_default, extred_full, extreduce_checkEdge(), extreduce_distDataFree(), extreduce_distDataInit(), extreduce_extPermaFree(), extreduce_extPermaInit(), FALSE, graph_free_dcsr(), graph_init_dcsr(), extension_data_permanent::redcostEqualAllow, SCIP_CALL, SCIP_OKAY, and STPTEST_EXT_MAXNCLOSENODES.

Referenced by testEdgeDeletedBy3LeafSpg(), testEdgeDeletedByCommonRedCostsTargets(), testEdgeDeletedByEqBottleneck(), testEdgeDeletedByEqBottleneck2(), testEdgeDeletedByMst1(), testEdgeDeletedByMst2(), testEdgeDeletedByMultiRedCosts(), testEdgeNotDeleted1(), testPcEdgeDeletedByMst1(), and testPcEdgeNotDeleted().

extCheckNode()

static SCIP_RETCODE extCheckNode ( SCIP *  scip, GRAPH *  graph, REDCOST *  redcostdata, STP_Bool *  edgedeleted, int  node, SCIP_Bool *  deletable, SCIP_Bool  allowEquality  )

static

base method for extended edge reduction tests

Parameters

scip	SCIP data structure
graph	the graph
redcostdata	reduced cost data
edgedeleted	array
node	node to check
deletable	pointer to mark whether node can be deleted
allowEquality	allow equality?

Definition at line 118 of file stptest_extreduce.c.

References extension_data_permanent::distdata_default, extred_full, extreduce_checkNode(), extreduce_distDataFree(), extreduce_distDataInit(), extreduce_extPermaFree(), extreduce_extPermaInit(), FALSE, GRAPH::grad, graph_free_dcsr(), graph_init_dcsr(), extension_data_permanent::redcostEqualAllow, reduce_starFree(), reduce_starInit(), SCIP_CALL, SCIP_OKAY, and STPTEST_EXT_MAXNCLOSENODES.

Referenced by testNode3PseudoDeletedByContraction(), testNode3PseudoDeletedByRedCosts1(), testNode3PseudoDeletedBySd1(), testNode3PseudoDeletedBySd2(), testNode3PseudoDeletedBySd3(), testNode4PseudoDeletedBySd1(), testNode4PseudoNotDeletedBySd1(), testPcNode3PseudoDeletedBySd1(), and testPcNode4PseudoDeletedBySd1().

extDeleteNodes()

static SCIP_RETCODE extDeleteNodes ( SCIP *  scip, GRAPH *  graph, REDCOST *  redcostdata, SCIP_Bool  allowEquality  )

static

base method for extended edge reduction tests (with biased SDs)

Parameters

scip	SCIP data structure
graph	the graph
redcostdata	reduced cost data
allowEquality	allow equality?

Definition at line 156 of file stptest_extreduce.c.

References extension_data_permanent::distdata_biased, extension_data_permanent::distdata_default, extred_full, extreduce_distDataFree(), extreduce_distDataInit(), extreduce_extPermaFree(), extreduce_extPermaInit(), extreduce_pseudoDeleteNodes(), FALSE, graph_free_dcsr(), graph_init_dcsr(), NULL, extension_data_permanent::redcostdata, extension_data_permanent::redcostEqualAllow, SCIP_CALL, SCIP_OKAY, and STPTEST_EXT_MAXNCLOSENODES.

Referenced by testNode3PseudoDeletedBySdBiased().

extInitRedCostArrays()

static void extInitRedCostArrays ( const GRAPH *  graph, REDCOST *  redcostdata  )

static

initializes to default

Parameters

graph	the graph
redcostdata	reduced costs data

Definition at line 194 of file stptest_extreduce.c.

References shortest_path::dist, shortest_path::edge, GRAPH::edges, GRAPH::knots, nnodes, redcosts_getEdgeCostsTop(), redcosts_getNedges(), redcosts_getNnodes(), redcosts_getNodeToTermsBasesTop(), redcosts_getNodeToTermsPathsTop(), redcosts_getRootToNodeDistTop(), SCIP_Real, and GRAPH::source.

Referenced by extInitRedCostArraysPc(), testEdgeDeletedBy3LeafSpg(), testEdgeDeletedByCommonRedCostsTargets(), testEdgeDeletedByEqBottleneck(), testEdgeDeletedByEqBottleneck2(), testEdgeDeletedByMst1(), testEdgeDeletedByMst2(), testEdgeDeletion1_deprecated(), testEdgeDeletion2_deprecated(), testEdgeDeletion3_deprecated(), testEdgeDeletion4_deprecated(), testEdgeDeletion5_deprecated(), testEdgeNotDeleted1(), testGeneralStarDeletedEdge1(), testGeneralStarDeletedEdge2(), testGeneralStarDeletedEdge3(), testNode3PseudoDeletedByContraction(), testNode3PseudoDeletedByRedCosts1(), testNode3PseudoDeletedBySd1(), testNode3PseudoDeletedBySd2(), testNode3PseudoDeletedBySd3(), testNode3PseudoDeletedBySdBiased(), testNode3PseudoDeletedBySdBiasedSimple(), testNode4PseudoDeletedBySd1(), and testNode4PseudoNotDeletedBySd1().

extInitRedCostArraysPc()

static void extInitRedCostArraysPc ( const GRAPH *  graph, REDCOST *  redcostdata  )

static

initializes to default for PC

Parameters

graph	the graph
redcostdata	reduced costs data

Definition at line 226 of file stptest_extreduce.c.

References extInitRedCostArrays(), graph_pc_isPc(), GRAPH::knots, nnodes, and redcosts_getNodeToTermsBasesTop().

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

testEdgeDeletion5_deprecated()

static SCIP_RETCODE testEdgeDeletion5_deprecated ( SCIP *  scip, int  variant  )

static

Parameters

scip	SCIP data structure
variant	1,2

Definition at line 269 of file stptest_extreduce.c.

References EAT_LAST, GRAPH::edges, extCheckArc(), extInitRedCostArrays(), graph_edge_addBi(), graph_init(), graph_knot_add(), graph_knot_chg(), GRAPH::head, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, redcosts_getEdgeCostsTop(), redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, stptest_extreduceTearDown(), stptest_graphSetUp(), and TRUE.

Referenced by stptest_extreduce().

testEdgeDeletion4_deprecated()

static SCIP_RETCODE testEdgeDeletion4_deprecated ( SCIP *  scip, int  variant  )

static

Parameters

scip	SCIP data structure
variant	1,2,3

Definition at line 359 of file stptest_extreduce.c.

References EAT_LAST, GRAPH::edges, extCheckArc(), extInitRedCostArrays(), graph_edge_addBi(), graph_init(), graph_initHistory(), graph_knot_add(), graph_knot_chg(), graph_mark(), graph_path_init(), GRAPH::head, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, redcosts_getEdgeCostsTop(), redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, stptest_extreduceTearDown(), and TRUE.

Referenced by stptest_extreduce().

testEdgeDeletion3_deprecated()

static SCIP_RETCODE testEdgeDeletion3_deprecated ( SCIP *  scip, int  variant  )

static

Parameters

scip	SCIP data structure
variant	1,2,3,4

Definition at line 459 of file stptest_extreduce.c.

References GRAPH::cost, shortest_path::dist, GRAPH::edges, extCheckArc(), extInitRedCostArrays(), FALSE, flipedge, graph_edge_addBi(), graph_init(), graph_initHistory(), graph_knot_add(), graph_knot_chg(), graph_mark(), graph_path_init(), GRAPH::head, GRAPH::knots, nnodes, NULL, redcosts_getEdgeCostsTop(), redcosts_getNodeToTermsBasesTop(), redcosts_getNodeToTermsPathsTop(), redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, stptest_extreduceTearDown(), GRAPH::tail, and TRUE.

Referenced by stptest_extreduce().

testEdgeDeletion2_deprecated()

static SCIP_RETCODE testEdgeDeletion2_deprecated ( SCIP *  scip, int  variant  )

static

Parameters

scip	SCIP data structure
variant	1,2,3,4,5

Definition at line 569 of file stptest_extreduce.c.

References EAT_LAST, GRAPH::edges, extCheckArc(), extInitRedCostArrays(), FALSE, graph_addPseudoAncestor(), graph_edge_addBi(), graph_init(), graph_initHistory(), graph_knot_add(), graph_mark(), graph_path_init(), graph_pseudoAncestors_addToEdge(), GRAPH::head, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STPTEST_ASSERT_MSG, and stptest_extreduceTearDown().

Referenced by stptest_extreduce().

testEdgeDeletion1_deprecated()

static SCIP_RETCODE testEdgeDeletion1_deprecated ( SCIP *  scip )

static

Parameters

scip	SCIP data structure

Definition at line 651 of file stptest_extreduce.c.

References GRAPH::edges, extCheckArc(), extInitRedCostArrays(), FALSE, graph_edge_addBi(), graph_init(), graph_initHistory(), graph_knot_add(), graph_mark(), graph_path_init(), GRAPH::knots, nnodes, NULL, redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STPTEST_ASSERT_MSG, and stptest_extreduceTearDown().

Referenced by stptest_extreduce().

testEdgeDeletedByCommonRedCostsTargets()

static SCIP_RETCODE testEdgeDeletedByCommonRedCostsTargets ( SCIP *  scip )

static

tests that edge can be deleted by exploiting that two vertices have the same reduced costs closest terminal

Parameters

scip	SCIP data structure

Definition at line 712 of file stptest_extreduce.c.

References shortest_path::dist, GRAPH::edges, extCheckEdge(), extInitRedCostArrays(), FALSE, graph_edge_addBi(), graph_init(), graph_knot_add(), GRAPH::knots, nnodes, NULL, redcosts_getNodeToTermsBasesTop(), redcosts_getNodeToTermsPathsTop(), redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), and stptest_graphSetUp().

Referenced by stptest_extreduce().

testEdgeDeletedByMultiRedCosts()

static SCIP_RETCODE testEdgeDeletedByMultiRedCosts ( SCIP *  scip )

static

tests that edge can be deleted by exploiting multi-level reduced costs

Parameters

scip	SCIP data structure

Definition at line 788 of file stptest_extreduce.c.

References GRAPH::cost, reduced_costs_parameters::cutoff, GRAPH::edges, extCheckEdge(), FALSE, graph_edge_addBi(), graph_init(), graph_knot_add(), GRAPH::knots, nnodes, NULL, redcosts_addLevel(), redcosts_getEdgeCostsTop(), redcosts_initFromParams(), redcosts_initializeDistancesTop(), redcosts_setCutoffTop(), redcosts_setRootTop(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), and stptest_graphSetUp().

Referenced by stptest_extreduce().

testEdgeDeletedByMst1()

static SCIP_RETCODE testEdgeDeletedByMst1 ( SCIP *  scip )

static

tests that edge can be deleted by using SD MST argument

Parameters

scip	SCIP data structure

Definition at line 880 of file stptest_extreduce.c.

References GRAPH::edges, extCheckEdge(), extInitRedCostArrays(), FALSE, graph_edge_addBi(), graph_init(), graph_knot_add(), GRAPH::knots, nnodes, NULL, redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), and stptest_graphSetUp().

Referenced by stptest_extreduce().

testEdgeDeletedByMst2()

static SCIP_RETCODE testEdgeDeletedByMst2 ( SCIP *  scip )

static

tests that edge can be deleted by using SD MST argument

Parameters

scip	SCIP data structure

Definition at line 934 of file stptest_extreduce.c.

References GRAPH::edges, extCheckEdge(), extInitRedCostArrays(), FALSE, graph_edge_addBi(), graph_init(), graph_knot_add(), GRAPH::knots, nnodes, NULL, redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), and stptest_graphSetUp().

Referenced by stptest_extreduce().

testEdgeDeletedByEqBottleneck()

static SCIP_RETCODE testEdgeDeletedByEqBottleneck ( SCIP *  scip )

static

tests that edge can be deleted by using equality bottlneck test

Parameters

scip	SCIP data structure

Definition at line 995 of file stptest_extreduce.c.

References GRAPH::edges, extCheckEdge(), extInitRedCostArrays(), FALSE, graph_edge_addBi(), graph_init(), graph_knot_add(), GRAPH::knots, nnodes, NULL, redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), and stptest_graphSetUp().

Referenced by stptest_extreduce().

testEdgeNotDeleted1()

static SCIP_RETCODE testEdgeNotDeleted1 ( SCIP *  scip )

static

tests that edge cannot be deleted

Parameters

scip	SCIP data structure

Definition at line 1046 of file stptest_extreduce.c.

References extCheckEdge(), extInitRedCostArrays(), FALSE, graph_edge_addBi(), graph_init(), graph_knot_add(), nnodes, NULL, redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), and stptest_graphSetUp().

Referenced by stptest_extreduce().

testEdgeDeletedByEqBottleneck2()

static SCIP_RETCODE testEdgeDeletedByEqBottleneck2 ( SCIP *  scip )

static

tests that edge can be deleted (with equality argument)

Parameters

scip	SCIP data structure

Definition at line 1106 of file stptest_extreduce.c.

References GRAPH::edges, extCheckEdge(), extInitRedCostArrays(), FALSE, graph_edge_addBi(), graph_init(), graph_knot_add(), GRAPH::knots, nnodes, NULL, redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), and stptest_graphSetUp().

Referenced by stptest_extreduce().

testEdgeDeletedBy3LeafSpg()

static SCIP_RETCODE testEdgeDeletedBy3LeafSpg ( SCIP *  scip )

static

tests that edge can be deleted by extended SPG rule-out

Parameters

scip	SCIP data structure

Definition at line 1159 of file stptest_extreduce.c.

References GRAPH::edges, extCheckEdge(), extInitRedCostArrays(), FALSE, graph_edge_addBi(), graph_init(), graph_knot_add(), GRAPH::knots, nnodes, NULL, redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), and stptest_graphSetUp().

Referenced by stptest_extreduce().

testNode3PseudoDeletedByRedCosts1()

static SCIP_RETCODE testNode3PseudoDeletedByRedCosts1 ( SCIP *  scip )

static

tests that edge can be deleted by reduced costs argument

Parameters

scip	SCIP data structure

Definition at line 1211 of file stptest_extreduce.c.

References GRAPH::edges, extCheckNode(), extInitRedCostArrays(), FALSE, graph_edge_addBi(), graph_init(), graph_knot_add(), GRAPH::knots, nnodes, NULL, redcosts_getEdgeCostsTop(), redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), and stptest_graphSetUp().

Referenced by stptest_extreduce().

testNode3PseudoDeletedByContraction()

static SCIP_RETCODE testNode3PseudoDeletedByContraction ( SCIP *  scip )

static

tests that node can be deleted

Parameters

scip	SCIP data structure

Definition at line 1272 of file stptest_extreduce.c.

References GRAPH::edges, extCheckNode(), extInitRedCostArrays(), FALSE, graph_edge_addBi(), graph_init(), graph_knot_add(), GRAPH::knots, nnodes, NULL, redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), and stptest_graphSetUp().

Referenced by stptest_extreduce().

testNode3PseudoDeletedBySdBiasedSimple()

static SCIP_RETCODE testNode3PseudoDeletedBySdBiasedSimple ( SCIP *  scip )

static

tests that node can be pseudo-deleted

Parameters

scip	SCIP data structure

Definition at line 1334 of file stptest_extreduce.c.

References GRAPH::edges, extInitRedCostArrays(), extreduce_distDataFree(), extreduce_distDataInit(), extreduce_mstbiasedCheck3NodeSimple(), FALSE, graph_edge_addBi(), graph_free_dcsr(), graph_init(), graph_init_dcsr(), graph_knot_add(), GRAPH::knots, nnodes, redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, STPTEST_EXT_MAXNCLOSENODES, stptest_extreduceTearDown(), stptest_graphSetUp(), and TRUE.

Referenced by stptest_extreduce().

testNode3PseudoDeletedBySdBiased()

static SCIP_RETCODE testNode3PseudoDeletedBySdBiased ( SCIP *  scip )

static

tests that node can be pseudo-deleted

Parameters

scip	SCIP data structure

Definition at line 1400 of file stptest_extreduce.c.

References GRAPH::edges, extDeleteNodes(), extInitRedCostArrays(), GRAPH::grad, graph_edge_addBi(), graph_init(), graph_knot_add(), GRAPH::knots, nnodes, redcosts_init(), SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), stptest_graphSetUp(), and TRUE.

Referenced by stptest_extreduce().

testNode3PseudoDeletedBySd1()

static SCIP_RETCODE testNode3PseudoDeletedBySd1 ( SCIP *  scip )

static

tests that node can be deleted

Parameters

scip	SCIP data structure

Definition at line 1461 of file stptest_extreduce.c.

References GRAPH::edges, extCheckNode(), extInitRedCostArrays(), FALSE, graph_edge_addBi(), graph_init(), graph_knot_add(), GRAPH::knots, nnodes, NULL, redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), and stptest_graphSetUp().

Referenced by stptest_extreduce().

testNode3PseudoDeletedBySd2()

static SCIP_RETCODE testNode3PseudoDeletedBySd2 ( SCIP *  scip )

static

tests that node can be deleted

Parameters

scip	SCIP data structure

Definition at line 1514 of file stptest_extreduce.c.

References GRAPH::edges, extCheckNode(), extInitRedCostArrays(), FALSE, graph_edge_addBi(), graph_init(), graph_knot_add(), GRAPH::knots, nnodes, NULL, redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), and stptest_graphSetUp().

Referenced by stptest_extreduce().

testNode3PseudoDeletedBySd3()

static SCIP_RETCODE testNode3PseudoDeletedBySd3 ( SCIP *  scip )

static

tests that node can be deleted

Parameters

scip	SCIP data structure

Definition at line 1565 of file stptest_extreduce.c.

References GRAPH::edges, extCheckNode(), extInitRedCostArrays(), FALSE, graph_edge_addBi(), graph_init(), graph_knot_add(), GRAPH::knots, nnodes, NULL, redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), and stptest_graphSetUp().

Referenced by stptest_extreduce().

testNode4PseudoDeletedBySd1()

static SCIP_RETCODE testNode4PseudoDeletedBySd1 ( SCIP *  scip )

static

tests that node can be deleted

Parameters

scip	SCIP data structure

Definition at line 1623 of file stptest_extreduce.c.

References GRAPH::edges, extCheckNode(), extInitRedCostArrays(), FALSE, graph_edge_addBi(), graph_init(), graph_knot_add(), GRAPH::knots, nnodes, NULL, redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), and stptest_graphSetUp().

Referenced by stptest_extreduce().

testNode4PseudoNotDeletedBySd1()

static SCIP_RETCODE testNode4PseudoNotDeletedBySd1 ( SCIP *  scip )

static

tests that node cannot be deleted

Parameters

scip	SCIP data structure

Definition at line 1680 of file stptest_extreduce.c.

References GRAPH::edges, extCheckNode(), extInitRedCostArrays(), FALSE, graph_edge_addBi(), graph_init(), graph_knot_add(), GRAPH::knots, nnodes, NULL, redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), and stptest_graphSetUp().

Referenced by stptest_extreduce().

testGeneralStarDeletedEdge1()

static SCIP_RETCODE testGeneralStarDeletedEdge1 ( SCIP *  scip )

static

tests that edge can be deleted by general star test

Parameters

scip	SCIP data structure

Definition at line 1734 of file stptest_extreduce.c.

References GRAPH::edges, extInitRedCostArrays(), extreduce_deleteGeneralStars(), graph_edge_addBi(), graph_edge_isDeleted(), graph_init(), graph_knot_add(), GRAPH::knots, nnodes, NULL, redcosts_init(), SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), and stptest_graphSetUp().

Referenced by stptest_extreduce().

testGeneralStarDeletedEdge2()

static SCIP_RETCODE testGeneralStarDeletedEdge2 ( SCIP *  scip )

static

tests that edge can be deleted by general star test

Parameters

scip	SCIP data structure

Definition at line 1793 of file stptest_extreduce.c.

References GRAPH::edges, extInitRedCostArrays(), extreduce_deleteGeneralStars(), graph_edge_addBi(), graph_edge_isDeleted(), graph_init(), graph_knot_add(), GRAPH::knots, nnodes, NULL, redcosts_init(), SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), and stptest_graphSetUp().

Referenced by stptest_extreduce().

testGeneralStarDeletedEdge3()

static SCIP_RETCODE testGeneralStarDeletedEdge3 ( SCIP *  scip )

static

tests that edge can be deleted by general star test

Parameters

scip	SCIP data structure

Definition at line 1852 of file stptest_extreduce.c.

References extInitRedCostArrays(), extreduce_deleteGeneralStars(), graph_edge_addBi(), graph_edge_isDeleted(), graph_init(), graph_knot_add(), nnodes, NULL, redcosts_init(), SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), and stptest_graphSetUp().

Referenced by stptest_extreduce().

testPcEdgeDeletedByMst1()

static SCIP_RETCODE testPcEdgeDeletedByMst1 ( SCIP *  scip )

static

tests that edge can be deleted by using SD MST argument

Parameters

scip	SCIP data structure

Definition at line 1916 of file stptest_extreduce.c.

References GRAPH::edges, extCheckEdge(), extInitRedCostArraysPc(), FALSE, FARAWAY, graph_edge_addBi(), graph_init(), graph_knot_add(), graph_pc_initPrizes(), GRAPH::knots, nnodes, NULL, GRAPH::prize, redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), and stptest_graphSetUpRpcOrg().

Referenced by stptest_extreduce().

testPcEdgeNotDeleted()

static SCIP_RETCODE testPcEdgeNotDeleted ( SCIP *  scip )

static

tests that edge cannot be deleted (by using SD MST argument)

Parameters

scip	SCIP data structure

Definition at line 1979 of file stptest_extreduce.c.

References GRAPH::edges, extCheckEdge(), extInitRedCostArraysPc(), FALSE, FARAWAY, graph_edge_addBi(), graph_init(), graph_knot_add(), graph_pc_initPrizes(), GRAPH::knots, nnodes, NULL, GRAPH::prize, redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), and stptest_graphSetUpRpcOrg().

Referenced by stptest_extreduce().

testPcNode3PseudoDeletedBySd1()

static SCIP_RETCODE testPcNode3PseudoDeletedBySd1 ( SCIP *  scip )

static

tests that node can be deleted

Parameters

scip	SCIP data structure

Definition at line 2041 of file stptest_extreduce.c.

References GRAPH::edges, extCheckNode(), extInitRedCostArraysPc(), FALSE, FARAWAY, graph_edge_addBi(), graph_init(), graph_knot_add(), graph_pc_initPrizes(), GRAPH::knots, nnodes, NULL, GRAPH::prize, redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), and stptest_graphSetUpRpcOrg().

Referenced by stptest_extreduce().

testPcNode4PseudoDeletedBySd1()

static SCIP_RETCODE testPcNode4PseudoDeletedBySd1 ( SCIP *  scip )

static

tests that node can be deleted

Parameters

scip	SCIP data structure

Definition at line 2102 of file stptest_extreduce.c.

References GRAPH::edges, extCheckNode(), extInitRedCostArraysPc(), extreduce_pseudoDeleteNodes(), FALSE, FARAWAY, GRAPH::grad, graph_edge_addBi(), graph_init(), graph_knot_add(), graph_pc_initPrizes(), GRAPH::knots, nnodes, NULL, GRAPH::prize, redcosts_init(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, stptest_extreduceTearDown(), and stptest_graphSetUpRpcOrg().

Referenced by stptest_extreduce().

testPathReplaceDeletesEdge()

static SCIP_RETCODE testPathReplaceDeletesEdge ( SCIP *  scip )

static

tests that path replacement deletes an edge

Parameters

scip	SCIP data structure

Definition at line 2232 of file stptest_extreduce.c.

References graph_edge_addBi(), graph_edge_isDeleted(), graph_init(), graph_knot_add(), nnodes, reduce_pathreplace(), SCIP_CALL, SCIP_OKAY, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, stptest_graphSetUp(), and stptest_graphTearDown().

Referenced by stptest_extreduce().

testPathReplaceDeletesEdge2()

static SCIP_RETCODE testPathReplaceDeletesEdge2 ( SCIP *  scip )

static

tests that path replacement deletes an edge

Parameters

scip	SCIP data structure

Definition at line 2287 of file stptest_extreduce.c.

References graph_edge_addBi(), graph_edge_isDeleted(), graph_init(), graph_knot_add(), nnodes, reduce_pathreplace(), SCIP_CALL, SCIP_OKAY, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT_MSG, stptest_graphSetUp(), and stptest_graphTearDown().

Referenced by stptest_extreduce().

stptest_extreduceTearDown()

void stptest_extreduceTearDown	(	SCIP *	scip,
		GRAPH *	graph,
		REDCOST **	redcostdata
	)

frees, etc.

Parameters

scip	SCIP data structure
graph	the graph
redcostdata	reduced cost data

Definition at line 2346 of file stptest_extreduce.c.

References redcosts_free(), and stptest_graphTearDown().

Referenced by testDistCloseNodesPcAreValid1(), testDistCloseNodesPcAreValid2(), testDistCloseNodesPcAreValidAfterDeletion(), 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(), testPcEdgeDeletedByMst1(), testPcEdgeNotDeleted(), testPcNode3PseudoDeletedBySd1(), and testPcNode4PseudoDeletedBySd1().

stptest_extreduce()

SCIP_RETCODE stptest_extreduce

(

SCIP *

scip

)

tests extended reduction techniques

Parameters

scip	SCIP data structure

Definition at line 2362 of file stptest_extreduce.c.

References SCIP_CALL, SCIP_OKAY, 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(), testPathReplaceDeletesEdge(), testPathReplaceDeletesEdge2(), testPcEdgeDeletedByMst1(), testPcEdgeNotDeleted(), testPcNode3PseudoDeletedBySd1(), and testPcNode4PseudoDeletedBySd1().

Referenced by stptest_testAll().