Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

tests for Steiner tree methods

Author: Daniel Rehfeldt

This file implements tests for Steiner problem heuristics.

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

Definition in file stptest_misc.c.

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

Go to the source code of this file.

Functions
static SCIP_RETCODE	graphBuildV5E5 (SCIP scip, GRAPH *g, SCIP_Bool pc)

static SCIP_RETCODE	pseudoDelSingle (SCIP *scip)

static SCIP_RETCODE	pseudoDelDouble (SCIP *scip)

static SCIP_RETCODE	pseudoAncestorsCreation (SCIP *scip)

static SCIP_RETCODE	pseudoAncestorsMerge (SCIP *scip)

static SCIP_RETCODE	pseudoAncestorsMergePc (SCIP *scip)

static SCIP_RETCODE	pseudoAncestorsHash (SCIP *scip)

static SCIP_RETCODE	pseudoAncestorsHashPc (SCIP *scip)

static SCIP_RETCODE	completegraph (SCIP *scip)

static SCIP_RETCODE	completemst1 (SCIP *scip)

static SCIP_RETCODE	completemst2 (SCIP *scip)

static SCIP_RETCODE	completemst3 (SCIP *scip)

static SCIP_RETCODE	completemst4 (SCIP *scip)

static SCIP_RETCODE	completemst5 (SCIP *scip)

SCIP_RETCODE	stptest_pseudoAncestors (SCIP *scip)

SCIP_RETCODE	stptest_pseudoDel (SCIP *scip)

SCIP_RETCODE	stptest_dheap (SCIP *scip)

SCIP_RETCODE	stptest_completegraph (SCIP *scip)

Function Documentation

◆ graphBuildV5E5()

static SCIP_RETCODE graphBuildV5E5	(	SCIP *	scip,
		GRAPH **	g,
		SCIP_Bool	pc
	)

static

Parameters

scip	SCIP data structure
g	the graph
pc	create pc graph?

Definition at line 38 of file stptest_misc.c.

References graph_edge_add(), graph_init(), graph_initHistory(), graph_knot_add(), graph_path_init(), graph_pc_initPrizes(), graph_transPc(), nnodes, GRAPH::prize, SCIP_CALL, SCIP_OKAY, and GRAPH::source.

Referenced by pseudoAncestorsCreation(), pseudoAncestorsHash(), pseudoAncestorsHashPc(), pseudoAncestorsMerge(), and pseudoAncestorsMergePc().

◆ pseudoDelSingle()

static SCIP_RETCODE pseudoDelSingle ( SCIP * scip )

static

Parameters

scip	SCIP data structure

Definition at line 83 of file stptest_misc.c.

References FARAWAY, graph_edge_add(), graph_edge_getPseudoAncestors(), graph_edge_nPseudoAncestors(), graph_free(), graph_init(), graph_initHistory(), graph_knot_add(), graph_knot_delPseudo(), graph_path_exit(), graph_path_init(), nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, and TRUE.

Referenced by stptest_pseudoDel().

◆ pseudoDelDouble()

static SCIP_RETCODE pseudoDelDouble ( SCIP * scip )

static

Parameters

scip	SCIP data structure

Definition at line 132 of file stptest_misc.c.

References EAT_LAST, FARAWAY, GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_edge_nPseudoAncestors(), graph_free(), graph_init(), graph_initHistory(), graph_knot_add(), graph_knot_delPseudo(), graph_path_exit(), graph_path_init(), GRAPH::head, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, GRAPH::source, and TRUE.

Referenced by stptest_pseudoDel().

◆ pseudoAncestorsCreation()

static SCIP_RETCODE pseudoAncestorsCreation ( SCIP * scip )

static

Parameters

scip	SCIP data structure

Definition at line 190 of file stptest_misc.c.

References GRAPH::edges, FALSE, graph_addPseudoAncestor(), graph_edge_delPseudoAncestors(), graph_edge_nPseudoAncestors(), graph_free(), graph_path_exit(), graph_pseudoAncestors_addToEdge(), graphBuildV5E5(), GRAPH::knots, SCIP_CALL, SCIP_OKAY, STPTEST_ASSERT, and TRUE.

Referenced by stptest_pseudoAncestors().

◆ pseudoAncestorsMerge()

static SCIP_RETCODE pseudoAncestorsMerge ( SCIP * scip )

static

Parameters

scip	SCIP data structure

Definition at line 241 of file stptest_misc.c.

References GRAPH::edges, FALSE, graph_addPseudoAncestor(), graph_edge_nPseudoAncestors(), graph_free(), graph_path_exit(), graph_pseudoAncestors_addToEdge(), graph_pseudoAncestors_appendMoveEdge(), graphBuildV5E5(), GRAPH::knots, SCIP_Bool, SCIP_CALL, SCIP_OKAY, STPTEST_ASSERT, and TRUE.

Referenced by stptest_pseudoAncestors().

◆ pseudoAncestorsMergePc()

static SCIP_RETCODE pseudoAncestorsMergePc ( SCIP * scip )

static

Parameters

scip	SCIP data structure

Definition at line 282 of file stptest_misc.c.

References GRAPH::edges, FALSE, graph_free(), graph_knot_nPseudoAncestors(), graph_path_exit(), graph_pseudoAncestors_addToNode(), graph_pseudoAncestors_appendMoveNode(), graphBuildV5E5(), GRAPH::knots, SCIP_Bool, SCIP_CALL, SCIP_OKAY, and TRUE.

Referenced by stptest_pseudoAncestors().

◆ pseudoAncestorsHash()

static SCIP_RETCODE pseudoAncestorsHash ( SCIP * scip )

static

Parameters

scip	SCIP data structure

Definition at line 319 of file stptest_misc.c.

References GRAPH::edges, FALSE, graph_addPseudoAncestor(), graph_free(), graph_path_exit(), graph_pseudoAncestors_addToEdge(), graph_pseudoAncestors_hashEdge(), graph_pseudoAncestors_hashEdgeDirty(), graph_pseudoAncestors_unhashEdge(), graph_pseudoAncestorsGetHashArraySize(), graphBuildV5E5(), GRAPH::knots, GRAPH::pseudoancestors, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocCleanBufferArray, SCIPfreeCleanBufferArray, STPTEST_ASSERT, and TRUE.

Referenced by stptest_pseudoAncestors().

◆ pseudoAncestorsHashPc()

static SCIP_RETCODE pseudoAncestorsHashPc ( SCIP * scip )

static

Parameters

scip	SCIP data structure

Definition at line 367 of file stptest_misc.c.

References GRAPH::edges, graph_free(), graph_path_exit(), graph_pseudoAncestors_addToNode(), graph_pseudoAncestors_hashNode(), graph_pseudoAncestors_hashNodeDirty(), graph_pseudoAncestors_unhashNode(), graph_pseudoAncestorsGetHashArraySize(), graphBuildV5E5(), GRAPH::knots, GRAPH::pseudoancestors, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocCleanBufferArray, SCIPfreeCleanBufferArray, and TRUE.

Referenced by stptest_pseudoAncestors().

◆ completegraph()

static SCIP_RETCODE completegraph ( SCIP * scip )

static

extension test

Parameters

scip	SCIP data structure

Definition at line 414 of file stptest_misc.c.

References cgraph_free(), cgraph_init(), cgraph_node_append(), cgraph_node_deleteTop(), cgraph_valid(), complete_graph::nnodes_curr, complete_graph::nnodes_max, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, and SCIPdebugMessage.

Referenced by stptest_completegraph().

◆ completemst1()

static SCIP_RETCODE completemst1 ( SCIP * scip )

static

mst test

Parameters

scip	SCIP data structure

Definition at line 482 of file stptest_misc.c.

References complete_graph::adjedgecosts, BMScopyMemoryArray, CGRAPH_EDGECOST_UNDEFINED_VALUE, cgraph_free(), cgraph_init(), cgraph_node_append(), cgraph_node_applyMinAdjCosts(), cgraph_node_repositionTop(), cmst_computeMst(), cmst_free(), cmst_init(), FARAWAY, complete_mst::mstobj, complete_mst::predecessors, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, and SCIPisEQ().

Referenced by stptest_completegraph().

◆ completemst2()

static SCIP_RETCODE completemst2 ( SCIP * scip )

static

mst test

Parameters

scip	SCIP data structure

Definition at line 532 of file stptest_misc.c.

References complete_graph::adjedgecosts, BMScopyMemoryArray, CGRAPH_EDGECOST_UNDEFINED_VALUE, cgraph_free(), cgraph_init(), cgraph_node_append(), cgraph_node_applyMinAdjCosts(), cmst_computeMst(), cmst_free(), cmst_init(), FARAWAY, complete_mst::mstobj, complete_mst::predecessors, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, and SCIPisEQ().

Referenced by stptest_completegraph().

◆ completemst3()

static SCIP_RETCODE completemst3 ( SCIP * scip )

static

mst test

Parameters

scip	SCIP data structure

Definition at line 581 of file stptest_misc.c.

References complete_graph::adjedgecosts, BMScopyMemoryArray, CGRAPH_EDGECOST_UNDEFINED_VALUE, cgraph_free(), cgraph_init(), cgraph_node_append(), cgraph_node_applyMinAdjCosts(), cmst_computeMst(), cmst_free(), cmst_init(), FARAWAY, complete_mst::mstobj, complete_mst::predecessors, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, and SCIPisEQ().

Referenced by stptest_completegraph().

◆ completemst4()

static SCIP_RETCODE completemst4 ( SCIP * scip )

static

mst test

Parameters

scip	SCIP data structure

Definition at line 629 of file stptest_misc.c.

References complete_graph::adjedgecosts, BMScopyMemoryArray, CGRAPH_EDGECOST_UNDEFINED_VALUE, cgraph_free(), cgraph_init(), cgraph_node_append(), cgraph_node_applyMinAdjCosts(), cgraph_node_deleteTop(), cmst_computeMst(), cmst_free(), cmst_init(), FARAWAY, complete_mst::mstobj, complete_mst::predecessors, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, and SCIPisEQ().

Referenced by stptest_completegraph().

◆ completemst5()

static SCIP_RETCODE completemst5 ( SCIP * scip )

static

mst test

Parameters

scip	SCIP data structure

Definition at line 691 of file stptest_misc.c.

References complete_graph::adjedgecosts, BMScopyMemoryArray, CGRAPH_EDGECOST_UNDEFINED_VALUE, cgraph_free(), cgraph_init(), cgraph_node_append(), cgraph_node_applyMinAdjCosts(), cgraph_node_deleteTop(), cmst_computeMst(), cmst_free(), cmst_init(), FARAWAY, complete_mst::mstobj, complete_mst::predecessors, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, and SCIPisEQ().

Referenced by stptest_completegraph().

◆ stptest_pseudoAncestors()

SCIP_RETCODE stptest_pseudoAncestors ( SCIP * scip )

test pseudo ancestors

Parameters

scip	SCIP data structure

Definition at line 757 of file stptest_misc.c.

References pseudoAncestorsCreation(), pseudoAncestorsHash(), pseudoAncestorsHashPc(), pseudoAncestorsMerge(), pseudoAncestorsMergePc(), SCIP_CALL, and SCIP_OKAY.

◆ stptest_pseudoDel()

SCIP_RETCODE stptest_pseudoDel ( SCIP * scip )

test pseudo deletion

Parameters

scip	SCIP data structure

Definition at line 775 of file stptest_misc.c.

References pseudoDelDouble(), pseudoDelSingle(), SCIP_CALL, and SCIP_OKAY.

Referenced by stptest_testAll().

◆ stptest_dheap()

SCIP_RETCODE stptest_dheap ( SCIP * scip )

Parameters

scip	SCIP data structure

Definition at line 791 of file stptest_misc.c.

References graph_heap_clean(), graph_heap_correct(), graph_heap_create(), graph_heap_deleteMinGetNode(), graph_heap_free(), NULL, SCIP_OKAY, dijkstra_heap::size, and TRUE.

Referenced by stptest_testAll().

◆ stptest_completegraph()

SCIP_RETCODE stptest_completegraph ( SCIP * scip )

Parameters

scip	SCIP data structure

Definition at line 893 of file stptest_misc.c.

References completegraph(), completemst1(), completemst2(), completemst3(), completemst4(), completemst5(), SCIP_CALL, and SCIP_OKAY.

Referenced by stptest_testAll().