Detailed Description

Dynamic programming internals for Steiner tree (sub-) problems with small number of terminals.

Author: Daniel Rehfeldt

Internal methods and data structures for DP.

#include "scip/scip.h"
#include "graph.h"
#include "stpvector.h"
#include "dpborder_hashmap.h"

Data Structures
struct	dynamic_programming_border_nodes_sequence

struct	dynamic_programming_border_level

struct	dynamic_programming_border_partition

struct	dynamic_programming_border

Macros
#define	BPBORDER_MAXNPARTITIONS 50000000

#define	BPBORDER_MAXBORDERSIZE 16

#define	DPB_Ptype char

#define	DPBORDER_GROWTH_FACTOR 4

Typedefs
typedef struct dynamic_programming_border_nodes_sequence	DPBSEQUENCE

typedef struct dynamic_programming_border_level	DPBLEVEL

typedef struct dynamic_programming_border_partition	DPBPART

Functions
static int	dpborder_getDelimiter (const DPBORDER *dpborder, int iteration)

static int	dpborder_getTopDelimiter (const DPBORDER *dpborder)

static DPBLEVEL *	dpborder_getTopLevel (const DPBORDER *dpborder)

static DPBLEVEL *	dpborder_getPredLevel (const DPBORDER *dpborder)

SCIP_Real	dpborder_partGetConnectionCost (const DPBORDER , const DPBPART , const int *, int)

int	dpborder_partglobalGetCard (int, int, const DPBORDER *)

int	dpborder_partGetIdxNew (SCIP , const DPBPART , const int , int, DPBORDER )

int	dpborder_partGetIdxNewExclusive (SCIP , const DPBPART , DPBORDER *)

	STP_Vectype (int) dpborder_partGetCandstarts(SCIP *

const DPBPART const DPBORDER *SCIP_Bool	dpborder_partIsValid (const DPBPART *)

void	dpborder_partPrint (const DPBPART *)

void	dpborder_markSolNodes (const DPBORDER , STP_Bool RESTRICT)

SCIP_RETCODE	dpborder_dpbsequenceInit (SCIP , const GRAPH , DPBSEQUENCE **)

void	dpborder_dpbsequenceFree (SCIP , DPBSEQUENCE *)

void	dpborder_dpbsequenceCopy (const DPBSEQUENCE , DPBSEQUENCE )

SCIP_RETCODE	dpborder_dpblevelInit (SCIP , DPBLEVEL *)

void	dpborder_dpblevelFree (SCIP , DPBLEVEL *)

SCIP_RETCODE	dpborder_coreComputeOrderingSimple (SCIP , const GRAPH , DPBORDER *)

SCIP_RETCODE	dpborder_coreUpdateOrdering (SCIP , const GRAPH , DPBORDER *)

SCIP_RETCODE	dpborder_coreSolve (SCIP , const GRAPH , DPBORDER , SCIP_Bool )

Macro Definition Documentation

◆ BPBORDER_MAXNPARTITIONS

#define BPBORDER_MAXNPARTITIONS 50000000

Definition at line 35 of file dpborderinterns.h.

Referenced by computeOrderingFromNode(), dpborder_coreUpdateOrdering(), dpborder_probePotential(), and initSolve().

◆ BPBORDER_MAXBORDERSIZE

#define BPBORDER_MAXBORDERSIZE 16

Definition at line 36 of file dpborderinterns.h.

Referenced by borderBuildCharDists(), computeOrderingFromNode(), dpborder_coreUpdateOrdering(), dpborder_getDelimiter(), dpborder_getTopDelimiter(), dpborder_probePotential(), dpborderInitHelper(), initSolve(), partitionIsSorted(), partitionSortSubsets(), and updateFromPartition().

◆ DPB_Ptype

#define DPB_Ptype char

Definition at line 37 of file dpborderinterns.h.

Referenced by dpborder_markSolNodes(), dpborder_partGetConnectionCost(), dpborder_partGetIdxNew(), dpborder_partGetIdxNewExclusive(), dpborder_partglobalGetCard(), dpborder_partIsValid(), dpborder_partPrint(), partitionSortSubsets(), STP_Vectype(), and updateFromPartition().

◆ DPBORDER_GROWTH_FACTOR

#define DPBORDER_GROWTH_FACTOR 4

Definition at line 38 of file dpborderinterns.h.

Referenced by dpborder_solve(), initSolve(), and partitionTryRealloc().

Typedef Documentation

◆ DPBSEQUENCE

typedef struct dynamic_programming_border_nodes_sequence DPBSEQUENCE

nodes sequence structure

◆ DPBLEVEL

typedef struct dynamic_programming_border_level DPBLEVEL

nodes sequence structure

◆ DPBPART

typedef struct dynamic_programming_border_partition DPBPART

single partition

Function Documentation

◆ dpborder_getDelimiter()

static int dpborder_getDelimiter	(	const DPBORDER *	dpborder,
		int	iteration
	)

inlinestatic

gets border delimiter for given iteration

Parameters

dpborder	border
iteration	iteration number

Definition at line 106 of file dpborderinterns.h.

References BPBORDER_MAXBORDERSIZE.

Referenced by dpborder_markSolNodes(), and updateFromPartition().

◆ dpborder_getTopDelimiter()

static int dpborder_getTopDelimiter ( const DPBORDER * dpborder )

inlinestatic

gets border delimiter

Parameters

dpborder border

Definition at line 121 of file dpborderinterns.h.

References BPBORDER_MAXBORDERSIZE, and StpVecGetSize.

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

◆ dpborder_getTopLevel()

static DPBLEVEL* dpborder_getTopLevel ( const DPBORDER * dpborder )

inlinestatic

gets top level

Parameters

dpborder border

Definition at line 137 of file dpborderinterns.h.

References StpVecGetSize.

Referenced by addLevel(), borderBuildCharDists(), borderBuildCharMap(), dpborder_partGetIdxNew(), dpborder_partGetIdxNewExclusive(), partitionIsIncluded(), and updateFromPartition().

◆ dpborder_getPredLevel()

static DPBLEVEL* dpborder_getPredLevel ( const DPBORDER * dpborder )

inlinestatic

gets previous level

Parameters

dpborder border

Definition at line 151 of file dpborderinterns.h.

References dpborder_coreComputeOrderingSimple(), dpborder_coreSolve(), dpborder_coreUpdateOrdering(), dpborder_dpblevelFree(), dpborder_dpblevelInit(), dpborder_dpbsequenceCopy(), dpborder_dpbsequenceFree(), dpborder_dpbsequenceInit(), dpborder_markSolNodes(), dpborder_partGetConnectionCost(), dpborder_partGetIdxNew(), dpborder_partGetIdxNewExclusive(), dpborder_partglobalGetCard(), dpborder_partIsValid(), dpborder_partPrint(), SCIP_Bool, SCIP_Real, STP_Vectype(), and StpVecGetSize.

◆ 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_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_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.

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().

◆ STP_Vectype()

STP_Vectype ( int )

Referenced by dpborder_getPredLevel().

◆ dpborder_partIsValid()

const DPBPART const DPBORDER* 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().

◆ dpborder_markSolNodes()

void dpborder_markSolNodes	(	const DPBORDER *	,
		STP_Bool *	RESTRICT
	)

Referenced by dpborder_getPredLevel().

◆ dpborder_dpbsequenceInit()

SCIP_RETCODE dpborder_dpbsequenceInit	(	SCIP *	scip,
		const GRAPH *	graph,
		DPBSEQUENCE **	dpbsequence
	)

initializes

Parameters

scip	SCIP data structure
graph	original graph
dpbsequence	to initialize

Definition at line 97 of file dpborder_base.c.

References dynamic_programming_border::dpbsequence, graph_get_nNodes(), dynamic_programming_border_nodes_sequence::maxbordersize, dynamic_programming_border_nodes_sequence::maxnpartitions, dynamic_programming_border_nodes_sequence::nnodes, nnodes, dynamic_programming_border_nodes_sequence::nodessquence, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, and SCIPallocMemoryArray.

Referenced by dpborder_coreUpdateOrdering(), dpborder_getPredLevel(), and dpborderInitHelper().

◆ dpborder_dpbsequenceFree()

void dpborder_dpbsequenceFree	(	SCIP *	scip,
		DPBSEQUENCE **	dpbsequence
	)

frees

Parameters

scip	SCIP data structure
dpbsequence	to free

Definition at line 134 of file dpborder_base.c.

References dynamic_programming_border::dpbsequence, dynamic_programming_border_nodes_sequence::nodessquence, SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by dpborder_coreUpdateOrdering(), dpborder_free(), and dpborder_getPredLevel().

◆ dpborder_dpbsequenceCopy()

void dpborder_dpbsequenceCopy	(	const DPBSEQUENCE *	dpbsequence_source,
		DPBSEQUENCE *	dpbsequence_target
	)

copies

Parameters

dpbsequence_source	to copy
dpbsequence_target	to copy to

Definition at line 119 of file dpborder_base.c.

References BMScopyMemoryArray, dynamic_programming_border_nodes_sequence::maxbordersize, dynamic_programming_border_nodes_sequence::maxnpartitions, dynamic_programming_border_nodes_sequence::nnodes, nnodes, and dynamic_programming_border_nodes_sequence::nodessquence.

Referenced by dpborder_coreUpdateOrdering(), and dpborder_getPredLevel().

◆ dpborder_dpblevelInit()

SCIP_RETCODE dpborder_dpblevelInit	(	SCIP *	scip,
		DPBLEVEL **	dpblevel
	)

initializes

Parameters

scip	SCIP data structure
dpblevel	to initialize

Definition at line 149 of file dpborder_base.c.

References dynamic_programming_border_level::exnodeIsTerm, dynamic_programming_border_level::extnode, FALSE, dynamic_programming_border_level::globalstartidx, dynamic_programming_border_level::nbordernodes, NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemory.

Referenced by addLevel(), addLevelFirst(), and dpborder_getPredLevel().

◆ dpborder_dpblevelFree()

void dpborder_dpblevelFree	(	SCIP *	scip,
		DPBLEVEL **	dpblevel
	)

frees

Parameters

scip	SCIP data structure
dpblevel	to be freed

Definition at line 170 of file dpborder_base.c.

References SCIPfreeMemory, and StpVecFree.

Referenced by dpborder_free(), and dpborder_getPredLevel().

◆ 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().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ BPBORDER_MAXNPARTITIONS

◆ BPBORDER_MAXBORDERSIZE

◆ DPB_Ptype

◆ DPBORDER_GROWTH_FACTOR

Typedef Documentation

◆ DPBSEQUENCE

◆ DPBLEVEL

◆ DPBPART

Function Documentation

◆ dpborder_getDelimiter()

◆ dpborder_getTopDelimiter()

◆ dpborder_getTopLevel()

◆ dpborder_getPredLevel()

◆ dpborder_partGetConnectionCost()

◆ dpborder_partglobalGetCard()

◆ dpborder_partGetIdxNew()

◆ dpborder_partGetIdxNewExclusive()

◆ STP_Vectype()

◆ dpborder_partIsValid()

◆ dpborder_partPrint()

◆ dpborder_markSolNodes()

◆ dpborder_dpbsequenceInit()

◆ dpborder_dpbsequenceFree()

◆ dpborder_dpbsequenceCopy()

◆ dpborder_dpblevelInit()

◆ dpborder_dpblevelFree()

◆ dpborder_coreComputeOrderingSimple()

◆ dpborder_coreUpdateOrdering()

◆ dpborder_coreSolve()