Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

tests for Steiner tree reductions

Author: Daniel Rehfeldt

This file implements unit tests for Steiner problem PC/MW reductions.

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

Definition in file stptest_pcreduce.c.

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

Go to the source code of this file.

Functions
static SCIP_RETCODE	checkSdWalk (SCIP scip, SCIP_Bool extended, GRAPH g, int nelims)

static SCIP_RETCODE	testRmwChain2DeletesNode (SCIP *scip)

static SCIP_RETCODE	testRmwNpv3DeletesNode (SCIP *scip)

static SCIP_RETCODE	testRmwAnsDeletesOneNode (SCIP *scip)

static SCIP_RETCODE	testRmwAnsDeletesOneEdge (SCIP *scip)

static SCIP_RETCODE	testRmwAnsDeletesTwoNodes (SCIP *scip)

static SCIP_RETCODE	testRmwTerminalContraction (SCIP *scip)

static SCIP_RETCODE	testRmwTerminalDeg1Contraction1 (SCIP *scip)

static SCIP_RETCODE	testRmwTerminalDeg1Contraction2 (SCIP *scip)

static SCIP_RETCODE	testRmwTerminalDeg1Contraction3 (SCIP *scip)

static SCIP_RETCODE	testSdPcKillsEdge1 (SCIP *scip)

static SCIP_RETCODE	testSdPcKillsEdge2 (SCIP *scip)

static SCIP_RETCODE	testSdPcKillsTwoEdges (SCIP *scip)

static SCIP_RETCODE	testSdStarPcKillsEdge (SCIP *scip)

SCIP_RETCODE	stptest_pcreduce (SCIP *scip)

Function Documentation

◆ checkSdWalk()

static SCIP_RETCODE checkSdWalk	(	SCIP *	scip,
		SCIP_Bool	extended,
		GRAPH **	g,
		int *	nelims
	)

static

Parameters

scip	SCIP data structure
extended	graph in extended state?
g	graph data structure
nelims	pointer to number of eliminations

Definition at line 40 of file stptest_pcreduce.c.

References GRAPH::edges, graph_free(), graph_getIsTermArray(), graph_heap_create(), graph_heap_free(), graph_initHistory(), graph_mark(), graph_path_exit(), graph_path_init(), graph_pc_2org(), graph_transPc(), GRAPH::knots, nnodes, NULL, reduce_sdWalkExt(), reduce_sdWalkTriangle(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and TRUE.

Referenced by testSdPcKillsEdge1(), testSdPcKillsEdge2(), and testSdPcKillsTwoEdges().

◆ testRmwChain2DeletesNode()

static SCIP_RETCODE testRmwChain2DeletesNode ( SCIP * scip )

static

tests chain2 RMW test

Parameters

scip	SCIP data structure

Definition at line 127 of file stptest_pcreduce.c.

References FARAWAY, GRAPH::grad, graph_edge_addBi(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_pc_initPrizes(), nnodes, NULL, GRAPH::prize, reduce_chain2(), SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, SCIPfreeMemoryArray, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT, stptest_graphSetUpRmwOrg(), and stptest_graphTearDown().

Referenced by stptest_pcreduce().

◆ testRmwNpv3DeletesNode()

static SCIP_RETCODE testRmwNpv3DeletesNode ( SCIP * scip )

static

tests NPV RMW test

Parameters

scip	SCIP data structure

Definition at line 193 of file stptest_pcreduce.c.

References FARAWAY, GRAPH::grad, graph_edge_addBi(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_pc_initPrizes(), nnodes, NULL, GRAPH::prize, reduce_npv(), SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, SCIPfreeMemoryArray, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT, stptest_graphSetUpRmwOrg(), and stptest_graphTearDown().

Referenced by stptest_pcreduce().

◆ testRmwAnsDeletesOneNode()

static SCIP_RETCODE testRmwAnsDeletesOneNode ( SCIP * scip )

static

tests ANS RMW test

Parameters

scip	SCIP data structure

Definition at line 263 of file stptest_pcreduce.c.

References FARAWAY, GRAPH::grad, graph_edge_addBi(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_pc_initPrizes(), NULL, GRAPH::prize, reduce_ans(), SCIP_CALL, SCIP_OKAY, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT, stptest_graphSetUpRmwOrg(), and stptest_graphTearDown().

Referenced by stptest_pcreduce().

◆ testRmwAnsDeletesOneEdge()

static SCIP_RETCODE testRmwAnsDeletesOneEdge ( SCIP * scip )

static

test ANS RMW test

Parameters

scip	SCIP data structure

Definition at line 316 of file stptest_pcreduce.c.

References EAT_FREE, FARAWAY, GRAPH::grad, graph_edge_addBi(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_pc_initPrizes(), NULL, GRAPH::oeat, GRAPH::prize, reduce_ans(), SCIP_CALL, SCIP_OKAY, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT, stptest_graphSetUpRmwOrg(), and stptest_graphTearDown().

Referenced by stptest_pcreduce().

◆ testRmwAnsDeletesTwoNodes()

static SCIP_RETCODE testRmwAnsDeletesTwoNodes ( SCIP * scip )

static

test ANS RMW test

Parameters

scip	SCIP data structure

Definition at line 373 of file stptest_pcreduce.c.

References FARAWAY, GRAPH::grad, graph_edge_addBi(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_pc_initPrizes(), NULL, GRAPH::prize, reduce_ans(), SCIP_CALL, SCIP_OKAY, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT, stptest_graphSetUpRmwOrg(), and stptest_graphTearDown().

Referenced by stptest_pcreduce().

◆ testRmwTerminalContraction()

static SCIP_RETCODE testRmwTerminalContraction ( SCIP * scip )

static

test simple RMW test

Parameters

scip	SCIP data structure

Definition at line 427 of file stptest_pcreduce.c.

References FARAWAY, GRAPH::grad, graph_edge_addBi(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_pc_initPrizes(), NULL, GRAPH::prize, reduce_simple_mw(), SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT, stptest_graphSetUpRmwOrg(), and stptest_graphTearDown().

Referenced by stptest_pcreduce().

◆ testRmwTerminalDeg1Contraction1()

static SCIP_RETCODE testRmwTerminalDeg1Contraction1 ( SCIP * scip )

static

test simple RMW test

Parameters

scip	SCIP data structure

Definition at line 472 of file stptest_pcreduce.c.

References FARAWAY, GRAPH::grad, graph_edge_addBi(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_pc_initPrizes(), NULL, GRAPH::prize, reduce_simple_mw(), SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT, stptest_graphSetUpRmwOrg(), and stptest_graphTearDown().

Referenced by stptest_pcreduce().

◆ testRmwTerminalDeg1Contraction2()

static SCIP_RETCODE testRmwTerminalDeg1Contraction2 ( SCIP * scip )

static

test simple RMW test

Parameters

scip	SCIP data structure

Definition at line 512 of file stptest_pcreduce.c.

References EQ, FARAWAY, GRAPH::grad, graph_edge_addBi(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_pc_initPrizes(), NULL, GRAPH::prize, reduce_simple_mw(), SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT, stptest_graphSetUpRmwOrg(), and stptest_graphTearDown().

Referenced by stptest_pcreduce().

◆ testRmwTerminalDeg1Contraction3()

static SCIP_RETCODE testRmwTerminalDeg1Contraction3 ( SCIP * scip )

static

test simple RMW test

Parameters

scip	SCIP data structure

Definition at line 554 of file stptest_pcreduce.c.

References EQ, FARAWAY, GRAPH::grad, graph_edge_addBi(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_pc_initPrizes(), NULL, GRAPH::prize, reduce_simple_mw(), SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT, stptest_graphSetUpRmwOrg(), and stptest_graphTearDown().

Referenced by stptest_pcreduce().

◆ testSdPcKillsEdge1()

static SCIP_RETCODE testSdPcKillsEdge1 ( SCIP * scip )

static

Parameters

scip	SCIP data structure

Definition at line 595 of file stptest_pcreduce.c.

References checkSdWalk(), FALSE, graph_edge_add(), graph_init(), graph_knot_add(), graph_pc_initPrizes(), nnodes, NULL, GRAPH::prize, SCIP_CALL, SCIP_OKAY, GRAPH::source, and STPTEST_ASSERT.

Referenced by stptest_pcreduce().

◆ testSdPcKillsEdge2()

static SCIP_RETCODE testSdPcKillsEdge2 ( SCIP * scip )

static

Parameters

scip	SCIP data structure

Definition at line 637 of file stptest_pcreduce.c.

References checkSdWalk(), FALSE, graph_edge_add(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_pc_initPrizes(), nnodes, NULL, GRAPH::prize, SCIP_CALL, SCIP_OKAY, GRAPH::source, and STPTEST_ASSERT.

Referenced by stptest_pcreduce().

◆ testSdPcKillsTwoEdges()

static SCIP_RETCODE testSdPcKillsTwoEdges ( SCIP * scip )

static

Parameters

scip	SCIP data structure

Definition at line 684 of file stptest_pcreduce.c.

References checkSdWalk(), FALSE, graph_edge_add(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_pc_initPrizes(), nnodes, NULL, GRAPH::prize, SCIP_CALL, SCIP_OKAY, GRAPH::source, and STPTEST_ASSERT.

Referenced by stptest_pcreduce().

◆ testSdStarPcKillsEdge()

static SCIP_RETCODE testSdStarPcKillsEdge ( SCIP * scip )

static

tests that SD star PC test kills an edge

Parameters

scip	SCIP data structure

Definition at line 740 of file stptest_pcreduce.c.

References dijkstra_data::dheap, EAT_FREE, graph_dijkLimited_free(), graph_dijkLimited_init(), graph_edge_addBi(), graph_init(), graph_knot_add(), graph_pc_initPrizes(), nnodes, dijkstra_data::node_distance, dijkstra_data::node_visited, GRAPH::oeat, GRAPH::prize, reduce_sdStarPc2(), SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, SCIPfreeMemoryArray, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT, stptest_graphSetUpPcOrg(), stptest_graphTearDown(), TRUE, and dijkstra_data::visitlist.

Referenced by stptest_pcreduce().

◆ stptest_pcreduce()

SCIP_RETCODE stptest_pcreduce ( SCIP * scip )

tests PCMW special distance methods

Parameters

scip	SCIP data structure

Definition at line 793 of file stptest_pcreduce.c.

References SCIP_CALL, SCIP_OKAY, testRmwAnsDeletesOneEdge(), testRmwAnsDeletesOneNode(), testRmwAnsDeletesTwoNodes(), testRmwChain2DeletesNode(), testRmwNpv3DeletesNode(), testRmwTerminalContraction(), testRmwTerminalDeg1Contraction1(), testRmwTerminalDeg1Contraction2(), testRmwTerminalDeg1Contraction3(), testSdPcKillsEdge1(), testSdPcKillsEdge2(), testSdPcKillsTwoEdges(), and testSdStarPcKillsEdge().

Referenced by stptest_testAll().