dpborder_core.c File Reference

Detailed Description

Core of dynamic programming solver for Steiner tree (sub-) problems with small border.

Author

Daniel Rehfeldt

Contains core methods.

Definition in file dpborder_core.c.

#include "dpborder.h"
#include "dpborderinterns.h"
#include "stpvector.h"
#include "misc_stp.h"

Go to the source code of this file.

Macros
#define	DPB_ORDERMULT_PREVS   2
#define	DPB_ORDERMULT_TERM   5
#define	DPB_ORDERMULT_OUTDEG   1
#define	DPB_ORDERMULT_OUTDELTA   1
#define	DPB_ORDER_MAXNROOTS   100

Functions
static SCIP_RETCODE	partitionTryRealloc (SCIP *scip, int newadds, DPBORDER *dpborder)
static void	partitionGetRangeGlobal (const DPBORDER *dpborder, int globalposition, int *start, int *end)
static void	borderBuildCharMap (int iteration, DPBORDER *dpborder)
static void	borderBuildCharDists (const GRAPH *graph, DPBORDER *dpborder)
static void	updateBorder (SCIP *scip, const GRAPH *graph, int iteration, DPBORDER *dpborder)
static SCIP_RETCODE	updateFromPartition (SCIP *scip, int globalposition, const GRAPH *graph, DPBORDER *dpborder)
static SCIP_RETCODE	addPartitions (SCIP *scip, const GRAPH *graph, int iteration, DPBORDER *dpborder)
static SCIP_RETCODE	addLevel (SCIP *scip, const GRAPH *graph, int iteration, DPBORDER *dpborder)
static SCIP_RETCODE	addLevelFirst (SCIP *scip, const GRAPH *graph, DPBORDER *dpborder)
static SCIP_RETCODE	initSolve (SCIP *scip, const GRAPH *graph, DPBORDER *dpborder)
static SCIP_RETCODE	computeOrderingFromNode (SCIP *scip, const GRAPH *graph, int root, DPBSEQUENCE *dpbsequence)
SCIP_RETCODE	dpborder_coreComputeOrderingSimple (SCIP *scip, const GRAPH *graph, DPBORDER *dpborder)
SCIP_RETCODE	dpborder_coreUpdateOrdering (SCIP *scip, const GRAPH *graph, DPBORDER *dpborder)
SCIP_RETCODE	dpborder_coreSolve (SCIP *scip, const GRAPH *graph, DPBORDER *dpborder, SCIP_Bool *wasSolved)

Macro Definition Documentation

DPB_ORDERMULT_PREVS

#define DPB_ORDERMULT_PREVS   2

Definition at line 32 of file dpborder_core.c.

Referenced by computeOrderingFromNode().

DPB_ORDERMULT_TERM

#define DPB_ORDERMULT_TERM   5

Definition at line 33 of file dpborder_core.c.

Referenced by computeOrderingFromNode().

DPB_ORDERMULT_OUTDEG

#define DPB_ORDERMULT_OUTDEG   1

Definition at line 34 of file dpborder_core.c.

Referenced by computeOrderingFromNode().

DPB_ORDERMULT_OUTDELTA

#define DPB_ORDERMULT_OUTDELTA   1

Definition at line 35 of file dpborder_core.c.

Referenced by computeOrderingFromNode().

DPB_ORDER_MAXNROOTS

#define DPB_ORDER_MAXNROOTS   100

Definition at line 37 of file dpborder_core.c.

Referenced by dpborder_coreUpdateOrdering().

Function Documentation

partitionTryRealloc()

static SCIP_RETCODE partitionTryRealloc ( SCIP *  scip, int  newadds, DPBORDER *  dpborder  )

inlinestatic

does reallocation of global array if necessary

Parameters

scip	SCIP data structure
newadds	number of additions
dpborder	border

Definition at line 85 of file dpborder_core.c.

References DPBORDER_GROWTH_FACTOR, dynamic_programming_border::global_npartitions, dynamic_programming_border::global_partcap, dynamic_programming_border::global_partitions, dynamic_programming_border::hashmap, hashmap_updateKeyarr(), SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, and SCIPreallocMemoryArray.

Referenced by updateFromPartition().

partitionGetRangeGlobal()

static void partitionGetRangeGlobal ( const DPBORDER *  dpborder, int  globalposition, int *  start, int *  end  )

inlinestatic

gets partition range

Parameters

dpborder	border
globalposition	position of partition
start	pointer to range start (OUT)
end	pointer to range end (OUT)

Definition at line 112 of file dpborder_core.c.

References dynamic_programming_border::global_npartitions.

Referenced by updateFromPartition().

borderBuildCharMap()

static void borderBuildCharMap ( int  iteration, DPBORDER *  dpborder  )

static

builds map between old and new border char representation

Parameters

iteration	iteration number
dpborder	border

Definition at line 133 of file dpborder_core.c.

References dynamic_programming_border::bordercharmap, dpborder_getTopLevel(), dynamic_programming_border_level::extnode, dynamic_programming_border::nnodes, dynamic_programming_border::nodes_isBorder, dynamic_programming_border::nodes_outdeg, SCIP_Bool, SCIPdebugMessage, and StpVecGetSize.

Referenced by updateBorder().

borderBuildCharDists()

static void borderBuildCharDists ( const GRAPH *  graph, DPBORDER *  dpborder  )

static

builds distances to extension node

Parameters

graph	graph
dpborder	border

Definition at line 175 of file dpborder_core.c.

References BLOCKED, dynamic_programming_border::borderchardists, BPBORDER_MAXBORDERSIZE, csr_storage::cost, GRAPH::csr_storage, dpborder_getTopLevel(), EQ, dynamic_programming_border_level::extnode, FARAWAY, csr_storage::head, dynamic_programming_border::nodes_isBorder, SCIP_Bool, SCIP_Real, SCIPdebugMessage, csr_storage::start, and StpVecGetSize.

Referenced by updateBorder().

updateBorder()

static void updateBorder ( SCIP *  scip, const GRAPH *  graph, int  iteration, DPBORDER *  dpborder  )

static

adapts border

Parameters

scip	SCIP data structure
graph	graph
iteration	iteration number
dpborder	border

Definition at line 224 of file dpborder_core.c.

References borderBuildCharDists(), borderBuildCharMap(), GRAPH::csr_storage, dynamic_programming_border::extborderchar, dynamic_programming_border_level::extnode, FALSE, dynamic_programming_border::global_npartitions, graph_knot_isInRange(), csr_storage::head, dynamic_programming_border_level::nbordernodes, dynamic_programming_border::nnodes, dynamic_programming_border::nodes_isBorder, dynamic_programming_border::nodes_outdeg, SCIP_Bool, csr_storage::start, StpVecClear, StpVecGetSize, StpVecPopBack, StpVecPushBack, and TRUE.

Referenced by addLevel().

updateFromPartition()

static SCIP_RETCODE updateFromPartition ( SCIP *  scip, int  globalposition, const GRAPH *  graph, DPBORDER *  dpborder  )

static

updates partition from given partition

Parameters

scip	SCIP data structure
globalposition	position of partition
graph	graph
dpborder	border

Definition at line 325 of file dpborder_core.c.

References allTermsAreVisited(), BPBORDER_MAXBORDERSIZE, dynamic_programming_border_partition::delimiter, DPB_Ptype, dpborder_getDelimiter(), dpborder_getTopDelimiter(), dpborder_getTopLevel(), dpborder_partGetConnectionCost(), dpborder_partGetIdxNew(), dpborder_partGetIdxNewExclusive(), dpborder_partglobalGetCard(), dpborder_partPrint(), dynamic_programming_border_level::exnodeIsTerm, FALSE, FARAWAY, dynamic_programming_border::global_obj, dynamic_programming_border::global_optposition, dynamic_programming_border::global_partitions, GT, LT, dynamic_programming_border::nterms, dynamic_programming_border::ntermsvisited, dynamic_programming_border_partition::partchars, partitionGetRangeGlobal(), partitionTryRealloc(), dynamic_programming_border_partition::partsize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, STP_Vectype, StpVecFree, StpVecGetSize, and TRUE.

Referenced by addPartitions().

addPartitions()

static SCIP_RETCODE addPartitions ( SCIP *  scip, const GRAPH *  graph, int  iteration, DPBORDER *  dpborder  )

static

adds partitions for new border

Parameters

scip	SCIP data structure
graph	graph
iteration	iteration number
dpborder	border

Definition at line 447 of file dpborder_core.c.

References dynamic_programming_border_level::globalstartidx, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, and updateFromPartition().

Referenced by dpborder_coreSolve().

addLevel()

static SCIP_RETCODE addLevel ( SCIP *  scip, const GRAPH *  graph, int  iteration, DPBORDER *  dpborder  )

static

adds border level

Parameters

scip	SCIP data structure
graph	graph
iteration	iteration number
dpborder	border

Definition at line 476 of file dpborder_core.c.

References dpborder_dpblevelInit(), dpborder_getTopLevel(), dynamic_programming_border::dpbsequence, dynamic_programming_border_level::exnodeIsTerm, dynamic_programming_border_level::extnode, dynamic_programming_border::global_npartitions, dynamic_programming_border_level::globalstartidx, graph_knot_isInRange(), dynamic_programming_border::hashmap, hashmap_isEmpty(), hashmap_remove(), Is_term, dynamic_programming_border_nodes_sequence::nodessquence, dynamic_programming_border::ntermsvisited, SCIP_CALL, SCIP_OKAY, STP_Vectype, StpVecPushBack, GRAPH::term, and updateBorder().

Referenced by dpborder_coreSolve().

addLevelFirst()

static SCIP_RETCODE addLevelFirst ( SCIP *  scip, const GRAPH *  graph, DPBORDER *  dpborder  )

static

adds first border level

Parameters

scip	SCIP data structure
graph	graph
dpborder	border

Definition at line 547 of file dpborder_core.c.

References dpborder_dpblevelInit(), dynamic_programming_border::dpbsequence, dynamic_programming_border_level::exnodeIsTerm, dynamic_programming_border_level::extnode, dynamic_programming_border::global_npartitions, dynamic_programming_border::global_partitions, dynamic_programming_border_level::globalstartidx, Is_term, dynamic_programming_border_level::nbordernodes, dynamic_programming_border::nodes_isBorder, dynamic_programming_border_nodes_sequence::nodessquence, dynamic_programming_border::ntermsvisited, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, StpVecGetSize, StpVecPushBack, GRAPH::term, and TRUE.

Referenced by initSolve().

initSolve()

static SCIP_RETCODE initSolve ( SCIP *  scip, const GRAPH *  graph, DPBORDER *  dpborder  )

static

initializes for solve

Parameters

scip	SCIP data structure
graph	graph
dpborder	border

Definition at line 592 of file dpborder_core.c.

References addLevelFirst(), BPBORDER_MAXBORDERSIZE, BPBORDER_MAXNPARTITIONS, computeOrderingFromNode(), GRAPH::csr_storage, DPBORDER_GROWTH_FACTOR, dynamic_programming_border::dpbsequence, dynamic_programming_border::global_partcap, dynamic_programming_border::global_partitions, graph_get_nNodes(), graph_knot_isInRange(), dynamic_programming_border::hashmap, hashmap_updateKeyarr(), csr_storage::head, Is_term, MAX, dynamic_programming_border_nodes_sequence::maxnpartitions, nnodes, dynamic_programming_border_nodes_sequence::nodessquence, dynamic_programming_border::nterms, dynamic_programming_border::ntermsvisited, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIPallocClearBufferArray, SCIPallocMemoryArray, SCIPerrorMessage, SCIPfreeBufferArray, csr_storage::start, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by dpborder_coreSolve().

computeOrderingFromNode()

static SCIP_RETCODE computeOrderingFromNode ( SCIP *  scip, const GRAPH *  graph, int  root, DPBSEQUENCE *  dpbsequence  )

static

computes node ordering and updates if better

Parameters

scip	SCIP data structure
graph	graph
root	node to start from
dpbsequence	sequence

Definition at line 674 of file dpborder_core.c.

References BMScopyMemoryArray, BPBORDER_MAXBORDERSIZE, BPBORDER_MAXNPARTITIONS, GRAPH::csr_storage, DPB_ORDERMULT_OUTDEG, DPB_ORDERMULT_OUTDELTA, DPB_ORDERMULT_PREVS, DPB_ORDERMULT_TERM, FALSE, GRAPH::grad, graph_get_nNodes(), graph_knot_isInRange(), csr_storage::head, Is_term, dynamic_programming_border_nodes_sequence::maxbordersize, dynamic_programming_border_nodes_sequence::maxnpartitions, nnodes, dynamic_programming_border_nodes_sequence::nodessquence, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, csr_storage::start, STP_Vectype, StpVecFree, StpVecGetSize, StpVecPopBack, StpVecPushBack, StpVecReserve, SWAP_INTS, GRAPH::term, and TRUE.

Referenced by dpborder_coreComputeOrderingSimple(), dpborder_coreUpdateOrdering(), and initSolve().

dpborder_coreComputeOrderingSimple()

SCIP_RETCODE dpborder_coreComputeOrderingSimple	(	SCIP *	scip,
		const GRAPH *	graph,
		DPBORDER *	dpborder
	)

computes node ordering

Parameters

scip	SCIP data structure
graph	graph
dpborder	border

Definition at line 863 of file dpborder_core.c.

References computeOrderingFromNode(), dynamic_programming_border::dpbsequence, SCIP_CALL, SCIP_OKAY, and GRAPH::source.

Referenced by dpborder_getPredLevel(), and dpborder_probePotential().

dpborder_coreUpdateOrdering()

SCIP_RETCODE dpborder_coreUpdateOrdering	(	SCIP *	scip,
		const GRAPH *	graph,
		DPBORDER *	dpborder
	)

updates given ordering

Parameters

scip	SCIP data structure
graph	graph
dpborder	border

Definition at line 876 of file dpborder_core.c.

References BPBORDER_MAXBORDERSIZE, BPBORDER_MAXNPARTITIONS, computeOrderingFromNode(), DPB_ORDER_MAXNROOTS, dpborder_dpbsequenceCopy(), dpborder_dpbsequenceFree(), dpborder_dpbsequenceInit(), dynamic_programming_border::dpbsequence, graph_getTermsRandom(), graph_knot_isInRange(), Is_term, MAX, dynamic_programming_border_nodes_sequence::maxbordersize, dynamic_programming_border_nodes_sequence::maxnpartitions, dynamic_programming_border_nodes_sequence::nodessquence, nterms, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeMemory, GRAPH::term, and GRAPH::terms.

Referenced by dpborder_getPredLevel(), and dpborder_solve().

dpborder_coreSolve()

SCIP_RETCODE dpborder_coreSolve	(	SCIP *	scip,
		const GRAPH *	graph,
		DPBORDER *	dpborder,
		SCIP_Bool *	wasSolved
	)

solves problem

Parameters

scip	SCIP data structure
graph	graph
dpborder	border
wasSolved	was problem solved to optimality?

Definition at line 943 of file dpborder_core.c.

References addLevel(), addPartitions(), dynamic_programming_border::dpbsequence, FALSE, dynamic_programming_border::global_npartitions, dynamic_programming_border::global_obj, dynamic_programming_border::global_optposition, graph_get_nNodes(), initSolve(), dynamic_programming_border_nodes_sequence::maxbordersize, nnodes, dynamic_programming_border::ntermsvisited, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisStopped(), GRAPH::terms, and TRUE.

Referenced by dpborder_getPredLevel(), and dpborder_solve().