Detailed Description

utility methods for Steiner tree reductions

Author: Daniel Rehfeldt

This file implements utility methods for Steiner tree problem special distance reduction techniques.

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

#include "reduce.h"
#include "portab.h"

Data Structures
struct	special_distance_neighbors

Macros
#define	STP_SDN_NCLOSETERMS 4

#define	STP_SDN_MAXDEGREE 4

#define	STP_SDN_MAXNVISITS 4

Functions
static void	sdgraphInsertEdge (SCIP scip, int term1, int term2, SCIP_Real edgecost, SDGRAPH sdgraph)

static SCIP_RETCODE	sdprofitAlloc (SCIP scip, const GRAPH g, SCIP_Bool useSecond, SDPROFIT **sdprofit)

static void	sdprofitBuild (const GRAPH g, SDPROFIT sdprofit)

static void	sdprofitBuild1stOnly (const GRAPH g, const SCIP_Real edgecosts, SDPROFIT *sdprofit)

static void	sdprofitUpdateNode (const GRAPH g, int node, int sourceterm, SCIP_Real edgecost, SCIP_Real bdist, SCIP_Bool blctree_isUpdated, SDPROFIT sdprofit)

static SCIP_RETCODE	sdneighborMarkCloseNodes (SCIP scip, const GRAPH g, int sourcenode, SD *sddata)

static SCIP_RETCODE	sdneighborUpdateInit (SCIP scip, GRAPH g, SDN *sdn)

static void	sdneighborUpdateFree (SCIP scip, GRAPH g, SDN *sdn)

static void	sdneighborUpdateNode (SCIP scip, const GRAPH g, int node, int term, SDN sdn, SDGRAPH sdgraph, int *nupdates)

static SCIP_RETCODE	sdneighborUpdateExec (SCIP scip, GRAPH g, SD sddata, int nupdates)

static SCIP_RETCODE	sdneighborUpdate (SCIP scip, GRAPH g, SD sddata, int nupdates)

SCIP_RETCODE	reduce_sdInit (SCIP scip, GRAPH g, SD **sd)

SCIP_RETCODE	reduce_sdInitBiased (SCIP scip, GRAPH g, SD **sd)

SCIP_RETCODE	reduce_sdInitBiasedBottleneck (SCIP scip, GRAPH g, SD **sd)

SCIP_RETCODE	reduce_sdRepair (SCIP scip, int edge, SCIP_Bool withEdgeReplacement, GRAPH g, SD *sd)

SCIP_RETCODE	reduce_sdRepairSetUp (SCIP scip, const GRAPH g, SD *sd)

SCIP_RETCODE	reduce_sdAddNeighborSd (SCIP scip, const GRAPH g, SD *sd)

void	reduce_sdFree (SCIP scip, SD *sd)

const SCIP_Bool *	reduce_sdneighborGetBlocked (const SDN *sdneighbors)

void	reduce_sdneighborGetCloseTerms (const GRAPH g, const SDN sdneighbor, int node, SCIP_Real maxdist_strict, int RESTRICT closeterms, SCIP_Real RESTRICT closeterms_dist, int *RESTRICT ncloseterms)

SCIP_RETCODE	reduce_sdneighborInit (SCIP scip, const GRAPH g, SDN **sdn)

void	reduce_sdneighborFree (SCIP scip, SDN *sdn)

SCIP_RETCODE	reduce_sdUpdateWithSdNeighbors (SCIP scip, GRAPH g, SD sddata, int nupdates)

SCIP_RETCODE	reduce_sdprofitInit (SCIP scip, const GRAPH g, SDPROFIT **sdprofit)

SCIP_RETCODE	reduce_sdprofitInit1stOnly (SCIP scip, const GRAPH g, const SCIP_Real edgecosts, SDPROFIT *sdprofit)

void	reduce_sdprofitPrintStats (const GRAPH g, const SDPROFIT sdprofit)

void	reduce_sdprofitFree (SCIP scip, SDPROFIT *sdprofit)

SCIP_RETCODE	reduce_sdprofitUpdateFromBLC (SCIP scip, const GRAPH g, const BLCTREE blctree, SCIP_Bool blctree_isUpdated, SDPROFIT sdprofit)

SCIP_RETCODE	reduce_sdprofitBuildFromBLC (SCIP scip, const GRAPH g, const BLCTREE blctree, SCIP_Bool blctree_isUpdated, SDPROFIT sdprofit)

Macro Definition Documentation

◆ STP_SDN_NCLOSETERMS

#define STP_SDN_NCLOSETERMS 4

Definition at line 32 of file reduce_sdutil.c.

Referenced by reduce_sdneighborInit().

◆ STP_SDN_MAXDEGREE

#define STP_SDN_MAXDEGREE 4

Definition at line 33 of file reduce_sdutil.c.

Referenced by sdneighborUpdateExec().

◆ STP_SDN_MAXNVISITS

#define STP_SDN_MAXNVISITS 4

Definition at line 34 of file reduce_sdutil.c.

Referenced by sdneighborUpdateInit().

Function Documentation

◆ sdgraphInsertEdge()

static void sdgraphInsertEdge	(	SCIP *	scip,
		int	term1,
		int	term2,
		SCIP_Real	edgecost,
		SDGRAPH *	sdgraph
	)

inlinestatic

inserts new edge

Parameters

scip	SCIP data structure
term1	end node 1
term2	end node 2
edgecost	cost
sdgraph	the SD graph

Definition at line 62 of file reduce_sdutil.c.

References NULL, reduce_sdgraphGetOrgnodesToSdMap(), reduce_sdgraphInsertEdge(), and SCIP_Bool.

Referenced by sdneighborUpdateNode().

◆ sdprofitAlloc()

static SCIP_RETCODE sdprofitAlloc	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Bool	useSecond,
		SDPROFIT **	sdprofit
	)

static

allocates memory

Parameters

scip	SCIP
g	graph to initialize from
useSecond	use second profit?
sdprofit	SD profit

Definition at line 81 of file reduce_sdutil.c.

References graph_get_nNodes(), nnodes, special_distance_implied_profit::nodes_bias, special_distance_implied_profit::nodes_bias2, special_distance_implied_profit::nodes_biassource, special_distance_implied_profit::nodes_biassource2, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, and SCIPallocMemoryArray.

Referenced by reduce_sdprofitInit(), and reduce_sdprofitInit1stOnly().

◆ sdprofitBuild()

static void sdprofitBuild	(	const GRAPH *	g,
		SDPROFIT *	sdprofit
	)

static

gets SD node bias

Parameters

g	the graph
sdprofit	SD profit

Definition at line 114 of file reduce_sdutil.c.

References GRAPH::cost, EAT_LAST, GRAPH::extended, FARAWAY, GE, graph_get_nNodes(), graph_pc_isPcMw(), graph_pc_isUnrootedPcMw(), graph_pc_knotIsDummyTerm(), GT, GRAPH::ieat, GRAPH::inpbeg, Is_term, nnodes, special_distance_implied_profit::nodes_bias, special_distance_implied_profit::nodes_bias2, special_distance_implied_profit::nodes_biassource, special_distance_implied_profit::nodes_biassource2, GRAPH::prize, SCIP_Bool, SCIP_Real, GRAPH::source, GRAPH::tail, GRAPH::term, and GRAPH::terms.

Referenced by reduce_sdprofitBuildFromBLC(), and reduce_sdprofitInit().

◆ sdprofitBuild1stOnly()

static void sdprofitBuild1stOnly	(	const GRAPH *	g,
		const SCIP_Real *	edgecosts,
		SDPROFIT *	sdprofit
	)

static

gets SD node bias

Parameters

g	the graph
edgecosts	edge costs (w.r.t graph 'g')
sdprofit	SD profit

Definition at line 238 of file reduce_sdutil.c.

References EAT_LAST, GRAPH::extended, FARAWAY, GE, graph_get_nNodes(), graph_pc_isPcMw(), graph_pc_isUnrootedPcMw(), graph_pc_knotIsDummyTerm(), GT, GRAPH::ieat, GRAPH::inpbeg, Is_term, nnodes, special_distance_implied_profit::nodes_bias, special_distance_implied_profit::nodes_biassource, GRAPH::prize, SCIP_Bool, SCIP_Real, GRAPH::source, GRAPH::tail, GRAPH::term, and GRAPH::terms.

Referenced by reduce_sdprofitInit1stOnly().

◆ sdprofitUpdateNode()

static void sdprofitUpdateNode	(	const GRAPH *	g,
		int	node,
		int	sourceterm,
		SCIP_Real	edgecost,
		SCIP_Real	bdist,
		SCIP_Bool	blctree_isUpdated,
		SDPROFIT *	sdprofit
	)

inlinestatic

updates implied profits by using exact bottleneck distances

Parameters

g	graph
node	the node to update
sourceterm	the source terminal
edgecost	edge cost
bdist	bottleneck distance
blctree_isUpdated	BLC tree fresh?
sdprofit	the SD profit

Definition at line 333 of file reduce_sdutil.c.

References FARAWAY, GE, graph_tpathsGet4CloseTerms(), GT, Is_term, LE, special_distance_implied_profit::nodes_bias, special_distance_implied_profit::nodes_bias2, special_distance_implied_profit::nodes_biassource, special_distance_implied_profit::nodes_biassource2, special_distance_neighbors::nodes_maxdist, special_distance_neighbors::nodes_nhits, NULL, SCIP_Real, GRAPH::term, and special_distance_storage::terminalpaths.

Referenced by reduce_sdprofitUpdateFromBLC().

◆ sdneighborMarkCloseNodes()

static SCIP_RETCODE sdneighborMarkCloseNodes	(	SCIP *	scip,
		const GRAPH *	g,
		int	sourcenode,
		SD *	sddata
	)

inlinestatic

marks nodes that can be reached from given source node

Parameters

scip	SCIP data structure
g	graph to initialize from
sourcenode	(neighbor) node to mark from
sddata	SD

Definition at line 419 of file reduce_sdutil.c.

References special_distance_neighbors::dijkdata, EQ, graph_dijkLimited_reset(), graph_sdCloseNodesBiased(), GT, special_distance_neighbors::hitlist, special_distance_neighbors::nnodesHit, special_distance_neighbors::nodes_maxdist, special_distance_neighbors::nodes_nhits, SCIP_CALL, SCIP_OKAY, SCIP_Real, special_distance_storage::sdneighbors, and special_distance_storage::sdprofit.

Referenced by sdneighborUpdateExec().

◆ sdneighborUpdateInit()

static SCIP_RETCODE sdneighborUpdateInit	(	SCIP *	scip,
		GRAPH *	g,
		SDN *	sdn
	)

static

helper

Parameters

scip	SCIP
g	graph
sdn	SD neighbors

Definition at line 474 of file reduce_sdutil.c.

References special_distance_neighbors::closeterms_distN, special_distance_neighbors::closetermsN, special_distance_neighbors::dijkdata, dijkstra_data::edgelimit, FALSE, FARAWAY, graph_dijkLimited_init(), graph_get_nNodes(), graph_init_dcsr(), special_distance_neighbors::hitlist, special_distance_neighbors::N, nnodes, special_distance_neighbors::nodes_isBlocked, special_distance_neighbors::nodes_maxdist, special_distance_neighbors::nodes_nhits, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, STP_SDN_MAXNVISITS, and UNKNOWN.

Referenced by sdneighborUpdate().

◆ sdneighborUpdateFree()

static void sdneighborUpdateFree	(	SCIP *	scip,
		GRAPH *	g,
		SDN *	sdn
	)

static

helper

Parameters

scip	SCIP
g	graph
sdn	SD neighbors

Definition at line 523 of file reduce_sdutil.c.

References special_distance_neighbors::dijkdata, graph_dijkLimited_free(), graph_free_dcsr(), special_distance_neighbors::hitlist, special_distance_neighbors::nodes_maxdist, special_distance_neighbors::nodes_nhits, and SCIPfreeBufferArray.

Referenced by sdneighborUpdate().

◆ sdneighborUpdateNode()

static void sdneighborUpdateNode	(	SCIP *	scip,
		const GRAPH *	g,
		int	node,
		int	term,
		SDN *	sdn,
		SDGRAPH *	sdgraph,
		int *	nupdates
	)

inlinestatic

updates single node

Parameters

scip	SCIP
g	graph to initialize from
node	node to update
term	terminal
sdn	SD neighbors
sdgraph	SD graph
nupdates	number of distance updates

Definition at line 540 of file reduce_sdutil.c.

References special_distance_neighbors::closeterms_distN, special_distance_neighbors::closetermsN, FARAWAY, GT, Is_term, GRAPH::knots, LT, special_distance_neighbors::N, nnodes, special_distance_neighbors::nodes_isBlocked, special_distance_neighbors::nodes_maxdist, reduce_sdgraphGetSd(), SCIP_Real, sdgraphInsertEdge(), GRAPH::term, and TRUE.

Referenced by sdneighborUpdateExec().

◆ sdneighborUpdateExec()

static SCIP_RETCODE sdneighborUpdateExec	(	SCIP *	scip,
		GRAPH *	g,
		SD *	sddata,
		int *	nupdates
	)

static

updates SDs by using neighbor argument

Parameters

scip	SCIP
g	graph to initialize from
sddata	SD
nupdates	number of distance updates

Definition at line 604 of file reduce_sdutil.c.

References EAT_LAST, EQ, GRAPH::grad, graph_get_nNodes(), graph_knot_isInRange(), GRAPH::head, special_distance_neighbors::hitlist, Is_term, nnodes, special_distance_neighbors::nnodesHit, special_distance_neighbors::nodes_maxdist, special_distance_neighbors::nodes_nhits, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIP_Real, special_distance_storage::sdgraph, sdneighborMarkCloseNodes(), special_distance_storage::sdneighbors, sdneighborUpdateNode(), STP_SDN_MAXDEGREE, and GRAPH::term.

Referenced by sdneighborUpdate().

◆ sdneighborUpdate()

static SCIP_RETCODE sdneighborUpdate	(	SCIP *	scip,
		GRAPH *	g,
		SD *	sddata,
		int *	nupdates
	)

static

updates SDs by using neighbor argument

Parameters

scip	SCIP
g	graph to initialize from
sddata	SD
nupdates	number of distance updates

Definition at line 670 of file reduce_sdutil.c.

References special_distance_graph::mstcosts, reduce_sdgraphMstBuild(), reduce_sdgraphMstSortCosts(), SCIP_CALL, SCIP_OKAY, special_distance_storage::sdgraph, special_distance_storage::sdneighbors, sdneighborUpdateExec(), sdneighborUpdateFree(), sdneighborUpdateInit(), and GRAPH::terms.

Referenced by reduce_sdUpdateWithSdNeighbors().

◆ reduce_sdInit()

SCIP_RETCODE reduce_sdInit	(	SCIP *	scip,
		GRAPH *	g,
		SD **	sd
	)

initializes SD structure

Parameters

scip	SCIP
g	graph NOTE: will mark the graph, thus not const :( terrible design
sd	to initialize

Definition at line 724 of file reduce_sdutil.c.

References special_distance_storage::blctree, FALSE, graph_tpathsInit(), special_distance_storage::hasNeigborUpdate, special_distance_storage::isBiased, NULL, reduce_sdgraphInit(), reduce_sdgraphInitOrderedMstCosts(), SCIP_CALL, SCIP_OKAY, SCIPallocMemory, special_distance_storage::sdgraph, special_distance_storage::sdneighbors, special_distance_storage::sdprofit, and special_distance_storage::terminalpaths.

Referenced by extreduce_distDataInit(), reduce_bdk(), testSdGetterReturnsCorrectSds(), testSdGraphQueriesAreValid(), and testSdRepair().

◆ reduce_sdInitBiased()

SCIP_RETCODE reduce_sdInitBiased	(	SCIP *	scip,
		GRAPH *	g,
		SD **	sd
	)

initializes biased SD structure

Parameters

scip	SCIP
g	graph NOTE: will mark the graph, thus not const :( terrible design
sd	to initialize

Definition at line 751 of file reduce_sdutil.c.

References special_distance_storage::blctree, FALSE, graph_tpathsInitBiased(), special_distance_storage::hasNeigborUpdate, special_distance_storage::isBiased, NULL, reduce_sdgraphInitBiased(), reduce_sdgraphInitOrderedMstCosts(), reduce_sdprofitInit(), SCIP_CALL, SCIP_OKAY, SCIPallocMemory, special_distance_storage::sdgraph, special_distance_storage::sdneighbors, special_distance_storage::sdprofit, special_distance_storage::terminalpaths, and TRUE.

Referenced by reduce_bdkBiased(), testSdBiasedDeletesEdge(), testSdCliqueStarDeg3IsCorrect(), testSdCliqueStarDeg3IsCorrect2(), testSdGraphDistsAreValid(), and testSdGraphDistsAreValid2().

◆ reduce_sdInitBiasedBottleneck()

SCIP_RETCODE reduce_sdInitBiasedBottleneck	(	SCIP *	scip,
		GRAPH *	g,
		SD **	sd
	)

initializes fully biased SD structure

Parameters

scip	SCIP
g	graph NOTE: will mark the graph, thus not const :( terrible design
sd	to initialize

Definition at line 779 of file reduce_sdutil.c.

References special_distance_storage::blctree, FALSE, graph_tpathsInitBiased(), special_distance_storage::hasNeigborUpdate, special_distance_storage::isBiased, NULL, reduce_blctreeInit(), reduce_sdgraphInitBiasedFromTpaths(), reduce_sdgraphInitOrderedMstCosts(), reduce_sdprofitInit(), reduce_sdprofitUpdateFromBLC(), SCIP_CALL, SCIP_OKAY, SCIPallocMemory, special_distance_storage::sdgraph, special_distance_storage::sdneighbors, special_distance_storage::sdprofit, special_distance_storage::terminalpaths, and TRUE.

Referenced by extreduce_distDataInit(), reduce_impliedProfitBased(), reduce_impliedProfitBasedRpc(), testNsvImpliedContractsCutDistEdge(), testNsvImpliedContractsCutDistMiddleEdge(), testNsvImpliedContractsEdge(), testNsvImpliedContractsEdge2(), testNsvImpliedContractsImpliedToTermEdge(), testSdBiasedBottleneckDeletesEdge(), testSdBiasedBottleneckTermPathDeletesEdge(), and testSdBiasedDeletesEdge().

◆ reduce_sdRepair()

SCIP_RETCODE reduce_sdRepair	(	SCIP *	scip,
		int	edge,
		SCIP_Bool	withEdgeReplacement,
		GRAPH *	g,
		SD *	sd
	)

repairs SD structure for imminent edge elimination

Parameters

scip	SCIP
edge	edge to be deleted soon
withEdgeReplacement	with edge replacement?
g	graph NOTE: will mark the graph, thus not const :( terrible design
sd	to be repaired

Definition at line 811 of file reduce_sdutil.c.

References GRAPH::cost, EQ, FARAWAY, flipedge, graph_edge_isInRange(), graph_tpathsRepair(), special_distance_storage::hasNeigborUpdate, special_distance_storage::isBiased, reduce_sdgraphEdgeIsInMst(), reduce_sdgraphFree(), reduce_sdgraphInit(), reduce_sdgraphInitOrderedMstCosts(), SCIP_CALL, SCIP_OKAY, SCIP_Real, special_distance_storage::sdgraph, special_distance_storage::sdneighbors, special_distance_storage::sdprofit, and special_distance_storage::terminalpaths.

Referenced by removeEdge(), replaceEdgeByPath(), and testSdRepair().

◆ reduce_sdRepairSetUp()

SCIP_RETCODE reduce_sdRepairSetUp	(	SCIP *	scip,
		const GRAPH *	g,
		SD *	sd
	)

sets up SD repairing mechanism

Parameters

scip	SCIP
g	graph
sd	to be repaired

Definition at line 853 of file reduce_sdutil.c.

References graph_tpathsRepairSetUp(), SCIP_CALL, SCIP_OKAY, and special_distance_storage::terminalpaths.

Referenced by extreduce_deleteArcs(), extreduce_deleteEdges(), extreduce_deleteGeneralStars(), reduce_termsepaDa(), and testSdRepair().

◆ reduce_sdAddNeighborSd()

SCIP_RETCODE reduce_sdAddNeighborSd	(	SCIP *	scip,
		const GRAPH *	g,
		SD *	sd
	)

adds biased neighbor SD structure

Parameters

scip	SCIP
g	graph
sd	to add to

Definition at line 868 of file reduce_sdutil.c.

References special_distance_storage::hasNeigborUpdate, reduce_sdneighborInit(), SCIP_CALL, SCIP_OKAY, special_distance_storage::sdneighbors, and TRUE.

Referenced by testSdBiasedDeletesEdge().

◆ reduce_sdFree()

void reduce_sdFree	(	SCIP *	scip,
		SD **	sd
	)

frees SD structure

Parameters

scip	SCIP
sd	to free

Definition at line 886 of file reduce_sdutil.c.

References special_distance_storage::blctree, graph_tpathsFree(), reduce_blctreeFree(), reduce_sdgraphFree(), reduce_sdneighborFree(), reduce_sdprofitFree(), SCIPfreeMemory, special_distance_storage::sdgraph, special_distance_storage::sdneighbors, special_distance_storage::sdprofit, and special_distance_storage::terminalpaths.

Referenced by extreduce_distDataFree(), reduce_bdk(), reduce_bdkBiased(), reduce_impliedProfitBased(), reduce_impliedProfitBasedRpc(), testNsvImpliedContractsCutDistEdge(), testNsvImpliedContractsCutDistMiddleEdge(), testNsvImpliedContractsEdge(), testNsvImpliedContractsEdge2(), testNsvImpliedContractsImpliedToTermEdge(), testSdBiasedBottleneckDeletesEdge(), testSdBiasedBottleneckTermPathDeletesEdge(), testSdBiasedDeletesEdge(), testSdCliqueStarDeg3IsCorrect(), testSdCliqueStarDeg3IsCorrect2(), testSdGetterReturnsCorrectSds(), testSdGraphDistsAreValid(), testSdGraphDistsAreValid2(), testSdGraphQueriesAreValid(), and testSdRepair().

◆ reduce_sdneighborGetBlocked()

const SCIP_Bool* reduce_sdneighborGetBlocked ( const SDN * sdneighbors )

get blocked nodes

Definition at line 915 of file reduce_sdutil.c.

References special_distance_neighbors::nodes_isBlocked.

Referenced by reduce_sdBiasedNeighbor(), and reduce_sdImpLongEdge().

◆ reduce_sdneighborGetCloseTerms()

void reduce_sdneighborGetCloseTerms	(	const GRAPH *	g,
		const SDN *	sdneighbor,
		int	node,
		SCIP_Real	maxdist_strict,
		int *RESTRICT	closeterms,
		SCIP_Real *RESTRICT	closeterms_dist,
		int *RESTRICT	ncloseterms
	)

gets (up to) four close terminals to given node i; with strict upper bound on allowed distances

Parameters

g	graph data structure
sdneighbor	SD neighbor data structure
node	node
maxdist_strict	maximum valid distance (strict)
closeterms	four close terminals
closeterms_dist	four close terminal distance
ncloseterms	number of close terminals found

Definition at line 926 of file reduce_sdutil.c.

References special_distance_neighbors::closeterms_distN, special_distance_neighbors::closetermsN, GE, graph_get_nNodes(), graph_knot_isInRange(), LT, special_distance_neighbors::N, nnodes, nterms, and SCIP_Real.

◆ reduce_sdneighborInit()

SCIP_RETCODE reduce_sdneighborInit	(	SCIP *	scip,
		const GRAPH *	g,
		SDN **	sdn
	)

initializes SDN

Parameters

scip	SCIP
g	graph to initialize from
sdn	SD neighbors

Definition at line 970 of file reduce_sdutil.c.

References special_distance_neighbors::closeterms_distN, special_distance_neighbors::closetermsN, special_distance_neighbors::dijkdata, graph_get_nNodes(), special_distance_neighbors::hitlist, special_distance_neighbors::N, nnodes, special_distance_neighbors::nnodesHit, special_distance_neighbors::nodes_isBlocked, special_distance_neighbors::nodes_maxdist, special_distance_neighbors::nodes_nhits, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, and STP_SDN_NCLOSETERMS.

Referenced by reduce_sdAddNeighborSd().

◆ reduce_sdneighborFree()

void reduce_sdneighborFree	(	SCIP *	scip,
		SDN **	sdn
	)

frees SDN

Parameters

scip	SCIP
sdn	SD neighbors

Definition at line 1000 of file reduce_sdutil.c.

References SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by reduce_sdFree().

◆ reduce_sdUpdateWithSdNeighbors()

SCIP_RETCODE reduce_sdUpdateWithSdNeighbors	(	SCIP *	scip,
		GRAPH *	g,
		SD *	sddata,
		int *	nupdates
	)

updates SDs by using neighbor argument NOTE: invalidates certain SD routines!

Parameters

scip	SCIP
g	graph to initialize from
sddata	SD
nupdates	number of distance updates

Definition at line 1015 of file reduce_sdutil.c.

References SCIP_OKAY, special_distance_storage::sdneighbors, and sdneighborUpdate().

Referenced by reduce_sdBiasedNeighbor().

◆ reduce_sdprofitInit()

SCIP_RETCODE reduce_sdprofitInit	(	SCIP *	scip,
		const GRAPH *	g,
		SDPROFIT **	sdprofit
	)

initializes SD profit

Parameters

scip	SCIP
g	graph to initialize from
sdprofit	the SD profit

Definition at line 1032 of file reduce_sdutil.c.

References SCIP_CALL, SCIP_OKAY, sdprofitAlloc(), sdprofitBuild(), and TRUE.

Referenced by prInit(), reduce_sdEdgeCliqueStar(), reduce_sdInitBiased(), reduce_sdInitBiasedBottleneck(), reduce_sdStarBiased(), testBiasedTerminalPathsTo4NextFound(), and testSdGraphStrongBiasedDistsAreValid().

◆ reduce_sdprofitInit1stOnly()

SCIP_RETCODE reduce_sdprofitInit1stOnly	(	SCIP *	scip,
		const GRAPH *	g,
		const SCIP_Real *	edgecosts,
		SDPROFIT **	sdprofit
	)

initializes SD profit

Parameters

scip	SCIP
g	graph to initialize from
edgecosts	edge costs (w.r.t graph 'g')
sdprofit	the SD profit

Definition at line 1048 of file reduce_sdutil.c.

References FALSE, SCIP_CALL, SCIP_OKAY, sdprofitAlloc(), and sdprofitBuild1stOnly().

Referenced by pseudodeleteBiasedIsPromising(), and tmBaseInit().

◆ reduce_sdprofitPrintStats()

void reduce_sdprofitPrintStats	(	const GRAPH *	g,
		const SDPROFIT *	sdprofit
	)

prints SD profit statistics

Parameters

g	graph to initialize from
sdprofit	the SD profit

Definition at line 1065 of file reduce_sdutil.c.

References graph_get_nNodes(), GT, Is_term, nnodes, special_distance_implied_profit::nodes_bias, SCIP_Real, and GRAPH::term.

◆ reduce_sdprofitFree()

void reduce_sdprofitFree	(	SCIP *	scip,
		SDPROFIT **	sdprofit
	)

frees SD profit

Parameters

scip	SCIP
sdprofit	the SD profit

Definition at line 1102 of file reduce_sdutil.c.

References special_distance_implied_profit::nodes_bias, special_distance_implied_profit::nodes_bias2, special_distance_implied_profit::nodes_biassource, special_distance_implied_profit::nodes_biassource2, SCIPfreeMemory, SCIPfreeMemoryArray, and SCIPfreeMemoryArrayNull.

Referenced by prFree(), pseudodeleteBiasedIsPromising(), reduce_sdEdgeCliqueStar(), reduce_sdFree(), reduce_sdStarBiased(), testBiasedTerminalPathsTo4NextFound(), testSdGraphStrongBiasedDistsAreValid(), and tmBaseFree().

◆ reduce_sdprofitUpdateFromBLC()

SCIP_RETCODE reduce_sdprofitUpdateFromBLC	(	SCIP *	scip,
		const GRAPH *	g,
		const BLCTREE *	blctree,
		SCIP_Bool	blctree_isUpdated,
		SDPROFIT *	sdprofit
	)

updates implied profits by using exact bottleneck distances

Parameters

scip	SCIP
g	graph
blctree	BLC tree
blctree_isUpdated	BLC tree fresh?
sdprofit	the SD profit

Definition at line 1123 of file reduce_sdutil.c.

References GRAPH::cost, graph_edge_isInRange(), GRAPH::head, Is_term, LE, LT, reduce_blctreeGetMstBottlenecks(), reduce_blctreeGetMstEdges(), reduce_blctreeGetMstNedges(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, sdprofitUpdateNode(), GRAPH::tail, and GRAPH::term.

Referenced by reduce_sdInitBiasedBottleneck(), and reduce_sdprofitBuildFromBLC().

◆ reduce_sdprofitBuildFromBLC()

SCIP_RETCODE reduce_sdprofitBuildFromBLC	(	SCIP *	scip,
		const GRAPH *	g,
		const BLCTREE *	blctree,
		SCIP_Bool	blctree_isUpdated,
		SDPROFIT *	sdprofit
	)

builds implied profits by using exact bottleneck distances

Parameters

scip	SCIP
g	graph
blctree	BLC tree
blctree_isUpdated	BLC tree fresh?
sdprofit	the SD profit

Definition at line 1179 of file reduce_sdutil.c.

References reduce_sdprofitUpdateFromBLC(), SCIP_CALL, SCIP_OKAY, and sdprofitBuild().

Referenced by reduce_impliedProfitBased(), and reduce_impliedProfitBasedRpc().

SCIP

Detailed Description

Data Structures

Macros

Functions

Macro Definition Documentation

◆ STP_SDN_NCLOSETERMS

◆ STP_SDN_MAXDEGREE

◆ STP_SDN_MAXNVISITS

Function Documentation

◆ sdgraphInsertEdge()

◆ sdprofitAlloc()

◆ sdprofitBuild()

◆ sdprofitBuild1stOnly()

◆ sdprofitUpdateNode()

◆ sdneighborMarkCloseNodes()

◆ sdneighborUpdateInit()

◆ sdneighborUpdateFree()

◆ sdneighborUpdateNode()

◆ sdneighborUpdateExec()

◆ sdneighborUpdate()

◆ reduce_sdInit()

◆ reduce_sdInitBiased()

◆ reduce_sdInitBiasedBottleneck()

◆ reduce_sdRepair()

◆ reduce_sdRepairSetUp()

◆ reduce_sdAddNeighborSd()

◆ reduce_sdFree()

◆ reduce_sdneighborGetBlocked()

◆ reduce_sdneighborGetCloseTerms()

◆ reduce_sdneighborInit()

◆ reduce_sdneighborFree()

◆ reduce_sdUpdateWithSdNeighbors()

◆ reduce_sdprofitInit()

◆ reduce_sdprofitInit1stOnly()

◆ reduce_sdprofitPrintStats()

◆ reduce_sdprofitFree()

◆ reduce_sdprofitUpdateFromBLC()

◆ reduce_sdprofitBuildFromBLC()