dpborder_util.c File Reference

Detailed Description

Utility methods for dynamic programming solver for Steiner tree (sub-) problems with small border.

Author

Daniel Rehfeldt

Implements utility methods.

Definition in file dpborder_util.c.

#include "dpborder.h"
#include "dpborderinterns.h"

Go to the source code of this file.

Functions
static SCIP_Bool	partitionIsIncluded (const DPBORDER *dpborder, const DPB_Ptype *partition, int size)
static SCIP_Bool	partitionIsSorted (const DPB_Ptype *partition, DPB_Ptype delimiter, int size)
static void	partitionSortSubsets (DPB_Ptype *RESTRICT partition, DPB_Ptype delimiter, int size)
SCIP_Bool	dpborder_partIsValid (const DPBPART *borderpartition)
void	dpborder_partPrint (const DPBPART *borderpartition)
	STP_Vectype (int)
int	dpborder_partglobalGetCard (int globalindex, int delimiter, const DPBORDER *dpborder)
SCIP_Real	dpborder_partGetConnectionCost (const DPBORDER *dpborder, const DPBPART *borderpartition, const int *candstarts_sub, int ncandstarts_sub)
int	dpborder_partGetIdxNew (SCIP *scip, const DPBPART *borderpartition, const int *candstarts_sub, int ncandstarts_sub, DPBORDER *dpborder)
int	dpborder_partGetIdxNewExclusive (SCIP *scip, const DPBPART *borderpartition, DPBORDER *dpborder)
void	dpborder_markSolNodes (const DPBORDER *dpborder, STP_Bool *RESTRICT nodes_isSol)

Function Documentation

partitionIsIncluded()

static SCIP_Bool partitionIsIncluded ( const DPBORDER *  dpborder, const DPB_Ptype *  partition, int  size  )

static

Parameters

dpborder	border
partition	array of size 'size'
size	size

Definition at line 34 of file dpborder_util.c.

References dpborder_getTopLevel(), FALSE, dynamic_programming_border::global_npartitions, dynamic_programming_border::global_partitions, dynamic_programming_border_level::globalstartidx, SCIPdebugMessage, and TRUE.

Referenced by dpborder_partGetIdxNew(), and dpborder_partGetIdxNewExclusive().

partitionIsSorted()

static SCIP_Bool partitionIsSorted ( const DPB_Ptype *  partition, DPB_Ptype  delimiter, int  size  )

static

fully sorted?

Parameters

partition	array of size 'size' with delimiter at [size]
delimiter	delimiter
size	size

Definition at line 68 of file dpborder_util.c.

References BPBORDER_MAXBORDERSIZE, FALSE, SCIPdebugMessage, hashmap_s::size, and TRUE.

Referenced by partitionSortSubsets().

partitionSortSubsets()

static void partitionSortSubsets ( DPB_Ptype *RESTRICT  partition, DPB_Ptype  delimiter, int  size  )

inlinestatic

sorts all subsets NOTE: partition needs to have allocated entry [-1] and [size]

Parameters

partition	array of size 'size'
delimiter	delimiter
size	size

Definition at line 130 of file dpborder_util.c.

References BPBORDER_MAXBORDERSIZE, DPB_Ptype, partitionIsSorted(), and hashmap_s::size.

Referenced by dpborder_partGetIdxNew(), and dpborder_partGetIdxNewExclusive().

dpborder_partIsValid()

SCIP_Bool dpborder_partIsValid

(

const DPBPART *

borderpartition

)

is partition valid?

Parameters

borderpartition

partition

Definition at line 226 of file dpborder_util.c.

References dynamic_programming_border_partition::delimiter, DPB_Ptype, FALSE, dynamic_programming_border_partition::partchars, dynamic_programming_border_partition::partsize, SCIPdebugMessage, and TRUE.

Referenced by dpborder_getPredLevel(), dpborder_partGetConnectionCost(), dpborder_partGetIdxNew(), dpborder_partGetIdxNewExclusive(), dpborder_partPrint(), and STP_Vectype().

dpborder_partPrint()

void dpborder_partPrint

(

const DPBPART *

borderpartition

)

prints partition

Parameters

borderpartition

partition

Definition at line 286 of file dpborder_util.c.

References dynamic_programming_border_partition::delimiter, DPB_Ptype, dpborder_partIsValid(), dynamic_programming_border_partition::partchars, and dynamic_programming_border_partition::partsize.

Referenced by dpborder_getPredLevel(), dpborder_partGetIdxNew(), dpborder_partGetIdxNewExclusive(), and updateFromPartition().

STP_Vectype()

STP_Vectype

(

int

)

gets candidates start for given partition border

gets indices of intersections to insert to

Definition at line 314 of file dpborder_util.c.

References dynamic_programming_border::borderchardists, dynamic_programming_border_partition::delimiter, DPB_Ptype, dpborder_partIsValid(), FARAWAY, LT, NULL, dynamic_programming_border_partition::partchars, dynamic_programming_border_partition::partsize, SCIP_Real, and StpVecPushBack.

Referenced by dpborder_markSolNodes().

dpborder_partglobalGetCard()

int dpborder_partglobalGetCard	(	int	globalindex,
		int	delimiter,
		const DPBORDER *	dpborder
	)

gets cardinality from global index of new global partition.

Parameters

globalindex	global index
delimiter	delimiter
dpborder	border

Definition at line 363 of file dpborder_util.c.

References DPB_Ptype, and dynamic_programming_border::global_partitions.

Referenced by dpborder_getPredLevel(), and updateFromPartition().

dpborder_partGetConnectionCost()

SCIP_Real dpborder_partGetConnectionCost	(	const DPBORDER *	dpborder,
		const DPBPART *	borderpartition,
		const int *	candstarts_sub,
		int	ncandstarts_sub
	)

gets minimum connection cost of connection selected sets of partition to extension vertex

Parameters

dpborder	border
borderpartition	base partition
candstarts_sub	candidate starts from which to construct new partition
ncandstarts_sub	number of candidate starts

Definition at line 389 of file dpborder_util.c.

References dynamic_programming_border::borderchardists, dynamic_programming_border_partition::delimiter, DPB_Ptype, dpborder_partIsValid(), FARAWAY, GE, LT, dynamic_programming_border_partition::partchars, dynamic_programming_border_partition::partsize, and SCIP_Real.

Referenced by dpborder_getPredLevel(), and updateFromPartition().

dpborder_partGetIdxNew()

int dpborder_partGetIdxNew	(	SCIP *	scip,
		const DPBPART *	borderpartition,
		const int *	candstarts_sub,
		int	ncandstarts_sub,
		DPBORDER *	dpborder
	)

Gets global index of new global partition. Returns -1 if no valid partition could be built.

Parameters

scip	SCIP data structure
borderpartition	base partition
candstarts_sub	candidate starts from which to construct new partition
ncandstarts_sub	number of candidate starts
dpborder	border

Definition at line 435 of file dpborder_util.c.

References dynamic_programming_border::bordercharmap, dynamic_programming_border_partition::delimiter, doCopy(), DPB_Ptype, dpborder_getTopDelimiter(), dpborder_getTopLevel(), dpborder_partIsValid(), dpborder_partPrint(), dynamic_programming_border::extborderchar, FALSE, FARAWAY, dynamic_programming_border::global_npartitions, dynamic_programming_border::global_partcap, dynamic_programming_border::global_partitions, dynamic_programming_border::hashmap, hashmap_get(), hashmap_put(), LT, dynamic_programming_border_partition::partchars, partitionIsIncluded(), partitionSortSubsets(), dynamic_programming_border_partition::partsize, SCIP_Bool, SCIPdebugMessage, StpVecPushBack, and TRUE.

Referenced by dpborder_getPredLevel(), and updateFromPartition().

dpborder_partGetIdxNewExclusive()

int dpborder_partGetIdxNewExclusive	(	SCIP *	scip,
		const DPBPART *	borderpartition,
		DPBORDER *	dpborder
	)

Gets global index of new global partition, similar to above, but merely removes prev. border nodes. Returns -1 if no valid partition could be built.

Parameters

scip	SCIP data structure
borderpartition	base partition
dpborder	border

Definition at line 633 of file dpborder_util.c.

References dynamic_programming_border::bordercharmap, dynamic_programming_border_partition::delimiter, DPB_Ptype, dpborder_getTopDelimiter(), dpborder_getTopLevel(), dpborder_partIsValid(), dpborder_partPrint(), FALSE, FARAWAY, dynamic_programming_border::global_npartitions, dynamic_programming_border::global_partitions, dynamic_programming_border::hashmap, hashmap_get(), hashmap_put(), LT, dynamic_programming_border_partition::partchars, partitionIsIncluded(), partitionSortSubsets(), dynamic_programming_border_partition::partsize, SCIPdebugMessage, StpVecGetSize, and StpVecPushBack.

Referenced by dpborder_getPredLevel(), and updateFromPartition().

dpborder_markSolNodes()

void dpborder_markSolNodes	(	const DPBORDER *	dpborder,
		STP_Bool *RESTRICT	nodes_isSol
	)

marks optimal solution nodes

Parameters

dpborder	border
nodes_isSol	solution nodes

Definition at line 736 of file dpborder_util.c.

References BMSclearMemoryArray, DPB_Ptype, dpborder_getDelimiter(), dynamic_programming_border::global_optposition, dynamic_programming_border::global_partitions, nnodes, dynamic_programming_border::nnodes, SCIPdebugMessage, STP_Vectype(), StpVecGetSize, and TRUE.

Referenced by dpborder_solve().