Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

tests for Steiner tree reductions

Author: Daniel Rehfeldt

This file implements unit tests for Steiner problem reduction utility methods.

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

Definition in file stptest_reduceutils.c.

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

Go to the source code of this file.

Functions
static SCIP_RETCODE	dcmstTest1 (SCIP *scip)

static SCIP_RETCODE	dcmstTest2 (SCIP *scip)

static SCIP_RETCODE	dcmstTest2b (SCIP *scip)

static SCIP_RETCODE	dcmstTest3 (SCIP *scip)

static SCIP_RETCODE	testStar3IsCorrect (SCIP *scip)

static SCIP_RETCODE	testStar4IsCorrect (SCIP *scip)

static SCIP_RETCODE	testStar4EdgeIsCorrect (SCIP *scip)

static SCIP_RETCODE	testStar5IsCorrect (SCIP *scip)

static SCIP_RETCODE	testBLCworksFor3Star (SCIP *scip)

static SCIP_RETCODE	testBLCworksFor3StarAfterReduction (SCIP *scip)

static SCIP_RETCODE	testBLCworksFor5Tree (SCIP *scip)

SCIP_RETCODE	stptest_dcmst (SCIP *scip)

SCIP_RETCODE	stptest_reduceStar (SCIP *scip)

SCIP_RETCODE	stptest_reduceBLCtree (SCIP *scip)

Function Documentation

◆ dcmstTest1()

static SCIP_RETCODE dcmstTest1 ( SCIP * scip )

static

builds up 3x3 MST

Parameters

scip	SCIP data structure

Definition at line 39 of file stptest_reduceutils.c.

References EQ, graph_csr_alloc(), graph_csr_copy(), graph_csr_free(), csr_storage::nedges_max, csr_storage::nnodes, reduce_dcmstAddNode(), reduce_dcmstFree(), reduce_dcmstGet1NodeMst(), reduce_dcmstGetWeight(), reduce_dcmstInit(), SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, and SCIPdebugMessage.

Referenced by stptest_dcmst().

◆ dcmstTest2()

static SCIP_RETCODE dcmstTest2 ( SCIP * scip )

static

builds up 4x4 MST

Parameters

scip	SCIP data structure

Definition at line 113 of file stptest_reduceutils.c.

References EQ, graph_csr_alloc(), graph_csr_copy(), graph_csr_free(), csr_storage::nedges_max, csr_storage::nnodes, reduce_dcmstAddNode(), reduce_dcmstFree(), reduce_dcmstGet2NodeMst(), reduce_dcmstGetWeight(), reduce_dcmstInit(), SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, and SCIPdebugMessage.

Referenced by stptest_dcmst().

◆ dcmstTest2b()

static SCIP_RETCODE dcmstTest2b ( SCIP * scip )

static

builds up a 4x4 MST

Parameters

scip	SCIP data structure

Definition at line 179 of file stptest_reduceutils.c.

References EQ, FARAWAY, graph_csr_alloc(), graph_csr_copy(), graph_csr_free(), csr_storage::nedges_max, csr_storage::nnodes, reduce_dcmstAddNode(), reduce_dcmstFree(), reduce_dcmstGet2NodeMst(), reduce_dcmstGetWeight(), reduce_dcmstInit(), SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, and SCIPdebugMessage.

Referenced by stptest_dcmst().

◆ dcmstTest3()

static SCIP_RETCODE dcmstTest3 ( SCIP * scip )

static

builds up 6x6 MST

Parameters

scip	SCIP data structure

Definition at line 244 of file stptest_reduceutils.c.

References EQ, graph_csr_alloc(), graph_csr_copy(), graph_csr_free(), csr_storage::nedges_max, csr_storage::nnodes, reduce_dcmstAddNode(), reduce_dcmstFree(), reduce_dcmstGet2NodeMst(), reduce_dcmstGetWeight(), reduce_dcmstInit(), SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, and SCIPdebugMessage.

Referenced by stptest_dcmst().

◆ testStar3IsCorrect()

static SCIP_RETCODE testStar3IsCorrect ( SCIP * scip )

static

STAR of degree 3 should be correctly computed

Parameters

scip	SCIP data structure

Definition at line 357 of file stptest_reduceutils.c.

References graph_edge_addBi(), graph_init(), graph_knot_add(), nnodes, reduce_starAllAreChecked(), reduce_starFree(), reduce_starGetNext(), reduce_starInit(), reduce_starReset(), SCIP_CALL, SCIP_OKAY, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT, stptest_graphSetUp(), and stptest_graphTearDown().

Referenced by stptest_reduceStar().

◆ testStar4IsCorrect()

static SCIP_RETCODE testStar4IsCorrect ( SCIP * scip )

static

STAR of degree 4 should be correctly computed

Parameters

scip	SCIP data structure

Definition at line 401 of file stptest_reduceutils.c.

References graph_edge_addBi(), graph_init(), graph_knot_add(), nnodes, reduce_starAllAreChecked(), reduce_starFree(), reduce_starGetNext(), reduce_starInit(), reduce_starReset(), SCIP_CALL, SCIP_OKAY, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT, stptest_graphSetUp(), and stptest_graphTearDown().

Referenced by stptest_reduceStar().

◆ testStar4EdgeIsCorrect()

static SCIP_RETCODE testStar4EdgeIsCorrect ( SCIP * scip )

static

STAR of degree 4 edge rule-out should be correctly computed

Parameters

scip	SCIP data structure

Definition at line 480 of file stptest_reduceutils.c.

References graph_edge_addBi(), graph_init(), graph_knot_add(), nnodes, reduce_starAllAreChecked(), reduce_starCurrentSetFailed(), reduce_starFree(), reduce_starGetNext(), reduce_starGetRuledOutEdges(), reduce_starHasPromisingEdges(), reduce_starInit(), reduce_starReset(), SCIP_CALL, SCIP_OKAY, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT, stptest_graphSetUp(), and stptest_graphTearDown().

Referenced by stptest_reduceStar().

◆ testStar5IsCorrect()

static SCIP_RETCODE testStar5IsCorrect ( SCIP * scip )

static

STAR of degree 5 should be correctly computed

Parameters

scip	SCIP data structure

Definition at line 570 of file stptest_reduceutils.c.

References graph_edge_addBi(), graph_init(), graph_knot_add(), nnodes, reduce_starAllAreChecked(), reduce_starFree(), reduce_starGetNext(), reduce_starInit(), reduce_starReset(), SCIP_CALL, SCIP_OKAY, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT, stptest_graphSetUp(), and stptest_graphTearDown().

Referenced by stptest_reduceStar().

◆ testBLCworksFor3Star()

static SCIP_RETCODE testBLCworksFor3Star ( SCIP * scip )

static

tests that BLC works for a degree 3 star

Parameters

scip	SCIP data structure

Definition at line 731 of file stptest_reduceutils.c.

References EQ, graph_edge_addBi(), graph_init(), graph_knot_add(), nnodes, reduce_blctreeFree(), reduce_blctreeGetMstBottlenecks(), reduce_blctreeGetMstEdges(), reduce_blctreeInit(), SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT, stptest_graphSetUp(), and stptest_graphTearDown().

Referenced by stptest_reduceBLCtree().

◆ testBLCworksFor3StarAfterReduction()

static SCIP_RETCODE testBLCworksFor3StarAfterReduction ( SCIP * scip )

static

tests that BLC works for a degree 3 star even after edges have been deleted

Parameters

scip	SCIP data structure

Definition at line 792 of file stptest_reduceutils.c.

References EQ, FARAWAY, graph_edge_addBi(), graph_edge_del(), graph_init(), graph_knot_add(), nnodes, reduce_blctreeFree(), reduce_blctreeGetMstBottlenecks(), reduce_blctreeGetMstEdges(), reduce_blctreeInit(), SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT, stptest_graphSetUp(), stptest_graphTearDown(), and TRUE.

Referenced by stptest_reduceBLCtree().

◆ testBLCworksFor5Tree()

static SCIP_RETCODE testBLCworksFor5Tree ( SCIP * scip )

static

tests that BLC works for a tree with five nodes

Parameters

scip	SCIP data structure

Definition at line 855 of file stptest_reduceutils.c.

References EQ, graph_edge_addBi(), graph_init(), graph_knot_add(), graph_knot_chg(), nnodes, reduce_blctreeFree(), reduce_blctreeGetMstBottlenecks(), reduce_blctreeGetMstEdges(), reduce_blctreeInit(), SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, STPTEST_ASSERT, stptest_graphSetUp(), and stptest_graphTearDown().

Referenced by stptest_reduceBLCtree().

◆ stptest_dcmst()

SCIP_RETCODE stptest_dcmst ( SCIP * scip )

tests DCMST

Parameters

scip	SCIP data structure

Definition at line 925 of file stptest_reduceutils.c.

References dcmstTest1(), dcmstTest2(), dcmstTest2b(), dcmstTest3(), SCIP_CALL, and SCIP_OKAY.

Referenced by stptest_testAll().

◆ stptest_reduceStar()

SCIP_RETCODE stptest_reduceStar ( SCIP * scip )

tests STAR methods

Parameters

scip	SCIP data structure

Definition at line 941 of file stptest_reduceutils.c.

References SCIP_CALL, SCIP_OKAY, testStar3IsCorrect(), testStar4EdgeIsCorrect(), testStar4IsCorrect(), and testStar5IsCorrect().

Referenced by stptest_testAll().

◆ stptest_reduceBLCtree()

SCIP_RETCODE stptest_reduceBLCtree ( SCIP * scip )

tests bottleneck tree methods

Parameters

scip	SCIP data structure

Definition at line 957 of file stptest_reduceutils.c.

References SCIP_CALL, SCIP_OKAY, testBLCworksFor3Star(), testBLCworksFor3StarAfterReduction(), and testBLCworksFor5Tree().

Referenced by stptest_testAll().