Detailed Description

utility methods for Steiner tree reductions

Author: Daniel Rehfeldt

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

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

Definition in file reduce_util.c.

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

Data Structures
struct	complete_edge

struct	dynamic_complete_minimum_spanning_tree

struct	node_one_hop_star

struct	bottleneck_link_cut_node

struct	bottleneck_link_cut_tree

Typedefs
typedef struct complete_edge	CEDGE

typedef struct bottleneck_link_cut_node	BLCNODE

Functions
static SCIP_RETCODE	blctreeBuildNodeMap (SCIP scip, const GRAPH graph, BLCTREE *RESTRICT blctree)

static SCIP_RETCODE	blctreeInitPrimitives (SCIP scip, const GRAPH graph, BLCTREE **blctree)

static void	blctreeResetNode (int i, BLCTREE *RESTRICT blctree)

static void	blctreeEvert (const GRAPH graph, int newroot, BLCTREE blctree)

static SCIP_Real	blctreeGetRootPathCost (int startnode, const BLCTREE *blctree)

static void	blctreeUpdateRootPath (int startnode, SCIP_Real bottleneck, BLCTREE *blctree)

static void	blctreeComputeBottlenecks (const GRAPH graph, BLCTREE blctree)

static void	blctreeComputeEdgesState (const GRAPH graph, BLCTREE blctree)

static SCIP_RETCODE	blctreeBuildMst (SCIP scip, GRAPH graph, BLCTREE *blctree)

static SCIP_RETCODE	blctreeInitBottlenecks (SCIP scip, GRAPH graph, BLCTREE *blctree)

static void	dcmstInsert (const CSR org_mst, const SCIP_Real adjcosts[], int root, CEDGE new_mst[], SCIP_Bool new_nodemarked[], CEDGE max_path_edge, int *new_nedges)

static void	dcmstAddNode (const CSR mst_in, const SCIP_Real adjcosts, DCMST *dmst)

static void	dcmstGetCSRfromStore (const DCMST dmst, CSR mst_out)

static SCIP_Real	dcmstGetWeightFromStore (SCIP scip, int mst_nedges, const DCMST dmst)

static void	starSelectedPositionsReset (STAR *star)

static void	starSelectedEdgesUpdate (STAR *star)

static void	starSelectedPositionsCopy (const STAR star, int posStorage)

static void	starSelectedPositionsSetNext (STAR *star)

static SCIP_Bool	starIsDeg2 (const STAR *star)

static void	impliedNodesAddTerm (SCIP scip, const GRAPH graph, int term, STP_Vectype(int) *nodes_implications)

static void	impliedNodesRemoveTerm (const GRAPH graph, int neighbor, int term, STP_Vectype(int) nodes_implications, SCIP_Bool *removed)

void	reduce_impliedNodesGet (SCIP scip, const GRAPH graph, STP_Vectype(int) *nodes_implications)

void	reduce_impliedNodesRepair (SCIP scip, const GRAPH graph, int tail, int head, STP_Vectype(int) *nodes_implications)

SCIP_Bool	reduce_impliedNodesIsValid (const GRAPH graph, const STP_Vectype(int) nodes_implications)

SCIP_RETCODE	reduce_applyPseudoDeletions (SCIP scip, const SCIP_Bool pseudoDelNodes, REDCOST redcostdata, GRAPH graph, SCIP_Real offsetp, int nelims)

SCIP_RETCODE	reduce_blctreeInit (SCIP scip, GRAPH graph, BLCTREE **blctree)

SCIP_RETCODE	reduce_blctreeRebuild (SCIP scip, GRAPH graph, BLCTREE *blctree)

void	reduce_blctreeFree (SCIP scip, BLCTREE *blctree)

int	reduce_blctreeGetMstNedges (const BLCTREE *blctree)

void	reduce_blctreeGetMstEdges (const GRAPH graph, const BLCTREE blctree, int *edgelist)

void	reduce_blctreeGetMstEdgesToCutDist (const GRAPH graph, const BLCTREE blctree, SCIP_Real RESTRICT tails2CutDist, SCIP_Real RESTRICT heads2CutDist)

void	reduce_blctreeGetMstEdgesState (const GRAPH graph, const BLCTREE blctree, SCIP_Bool *statelist)

void	reduce_blctreeGetMstBottlenecks (const GRAPH graph, const BLCTREE blctree, SCIP_Real *costlist)

SCIP_RETCODE	reduce_dcmstInit (SCIP scip, int maxnnodes, DCMST *dcmst)

void	reduce_dcmstAddNode (SCIP scip, const CSR mst_in, const SCIP_Real adjcosts, DCMST dmst, CSR *mst_out)

void	reduce_dcmstAddNodeInplace (SCIP scip, const SCIP_Real adjcosts, DCMST dmst, CSR mst)

void	reduce_dcmstGet0NodeMst (SCIP scip, CSR mst)

void	reduce_dcmstGet1NodeMst (SCIP scip, CSR mst)

void	reduce_dcmstGet2NodeMst (SCIP scip, SCIP_Real edgecost, CSR mst)

void	reduce_dcmstGet3NodeMst (SCIP scip, SCIP_Real edgecost01, SCIP_Real edgecost02, SCIP_Real edgecost12, CSR mst)

SCIP_Real	reduce_dcmstGetExtWeight (SCIP scip, const CSR mst, const SCIP_Real adjcosts, DCMST dmst)

SCIP_Real	reduce_dcmstGetWeight (SCIP scip, const CSR mst_in)

int	reduce_dcmstGetMaxnnodes (const DCMST *dmst)

SCIP_Real *	reduce_dcmstGetAdjcostBuffer (const DCMST *dmst)

void	reduce_dcmstFree (SCIP scip, DCMST *dcmst)

SCIP_Bool	reduce_dcmstMstIsValid (SCIP scip, const CSR cmst)

SCIP_RETCODE	reduce_starInit (SCIP scip, int maxdegree, STAR *star)

void	reduce_starFree (SCIP scip, STAR *star)

void	reduce_starReset (const GRAPH g, int node, STAR star)

void	reduce_starResetWithEdges (const GRAPH g, const STP_Vectype(int) staredges, STAR star)

int	reduce_starGetCenter (const STAR *star)

const int *	reduce_starGetNext (STAR star, int nedges)

const int *	reduce_starGetNextAndPosition (STAR star, int position, int *nedges)

const int *	reduce_starGetRuledOutEdges (STAR star, int nedges)

void	reduce_starCurrentSetRuledOut (STAR *star)

void	reduce_starCurrentSetFailed (STAR *star)

SCIP_Bool	reduce_starHasPromisingEdges (const STAR *star)

SCIP_Bool	reduce_starAllAreChecked (const STAR *star)

Typedef Documentation

◆ CEDGE

typedef struct complete_edge CEDGE

storage for edge on complete graph

◆ BLCNODE

typedef struct bottleneck_link_cut_node BLCNODE

bottleneck link-cut tree node

Function Documentation

◆ blctreeBuildNodeMap()

static SCIP_RETCODE blctreeBuildNodeMap	(	SCIP *	scip,
		const GRAPH *	graph,
		BLCTREE *RESTRICT	blctree
	)

inlinestatic

builds mapping

Parameters

scip	SCIP
graph	the graph
blctree	the tree

Definition at line 103 of file reduce_util.c.

References GRAPH::grad, graph_pc_isPc(), GRAPH::knots, GRAPH::mark, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, and UNKNOWN.

Referenced by blctreeInitPrimitives().

◆ blctreeInitPrimitives()

static SCIP_RETCODE blctreeInitPrimitives	(	SCIP *	scip,
		const GRAPH *	graph,
		BLCTREE **	blctree
	)

static

allocates BLC tree memory and builds mapping

Parameters

scip	SCIP
graph	the graph
blctree	to be initialized

Definition at line 155 of file reduce_util.c.

References blctreeBuildNodeMap(), graph_get_nNodes(), graph_get_nVET(), bottleneck_link_cut_tree::mst, bottleneck_link_cut_tree::mstedges_isLink, nnodes, bottleneck_link_cut_tree::nnodes_curr, bottleneck_link_cut_tree::nnodes_org, NULL, bottleneck_link_cut_tree::root, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, and UNKNOWN.

Referenced by reduce_blctreeInit().

◆ blctreeResetNode()

static void blctreeResetNode	(	int	i,
		BLCTREE *RESTRICT	blctree
	)

inlinestatic

resets given node

Parameters

i	the node
blctree	the tree

Definition at line 183 of file reduce_util.c.

References FARAWAY, and UNKNOWN.

Referenced by blctreeBuildMst(), and blctreeEvert().

◆ blctreeEvert()

static void blctreeEvert	(	const GRAPH *	graph,
		int	newroot,
		BLCTREE *	blctree
	)

inlinestatic

sets new root

Parameters

graph	the graph
newroot	new root
blctree	tree

Definition at line 202 of file reduce_util.c.

References blctreeResetNode(), bottleneck_link_cut_node::dist_edgehead, bottleneck_link_cut_node::dist_edgetail, bottleneck_link_cut_node::edge, bottleneck_link_cut_node::edgebottleneck, bottleneck_link_cut_node::edgecost, flipedge_Uint, complete_edge::head, bottleneck_link_cut_node::head, bottleneck_link_cut_tree::mst, bottleneck_link_cut_tree::nodes_curr2org, bottleneck_link_cut_tree::root, SCIP_Real, GRAPH::tail, and UNKNOWN.

Referenced by blctreeComputeBottlenecks().

◆ blctreeGetRootPathCost()

static SCIP_Real blctreeGetRootPathCost	(	int	startnode,
		const BLCTREE *	blctree
	)

inlinestatic

gets cost of path

Parameters

startnode	node to start from
blctree	tree

Definition at line 253 of file reduce_util.c.

References bottleneck_link_cut_node::edgecost, complete_edge::head, bottleneck_link_cut_node::head, bottleneck_link_cut_tree::mst, bottleneck_link_cut_tree::root, SCIP_Real, SCIPdebugMessage, and UNKNOWN.

Referenced by blctreeUpdateRootPath().

◆ blctreeUpdateRootPath()

static void blctreeUpdateRootPath	(	int	startnode,
		SCIP_Real	bottleneck,
		BLCTREE *	blctree
	)

inlinestatic

updates path to root

Parameters

startnode	node to start from
bottleneck	bottleneck
blctree	tree

Definition at line 282 of file reduce_util.c.

References blctreeGetRootPathCost(), GE, complete_edge::head, bottleneck_link_cut_tree::mst, bottleneck_link_cut_tree::root, SCIP_Real, SCIPdebugMessage, and UNKNOWN.

Referenced by blctreeComputeBottlenecks().

◆ blctreeComputeBottlenecks()

static void blctreeComputeBottlenecks	(	const GRAPH *	graph,
		BLCTREE *	blctree
	)

static

computes bottlenecks

Parameters

graph	the graph
blctree	to be built

Definition at line 338 of file reduce_util.c.

References blctreeEvert(), blctreeUpdateRootPath(), GRAPH::cost, EAT_LAST, flipedge, GRAPH::grad, graph_isMarked(), graph_knot_isInRange(), graph_pc_isPc(), graph_pc_knotIsDummyTerm(), complete_edge::head, GRAPH::head, GRAPH::mark, bottleneck_link_cut_tree::mst, bottleneck_link_cut_tree::nnodes_curr, bottleneck_link_cut_tree::nodes_curr2org, bottleneck_link_cut_tree::nodes_org2curr, GRAPH::oeat, GRAPH::outbeg, bottleneck_link_cut_tree::root, SCIPdebugMessage, and GRAPH::source.

Referenced by blctreeInitBottlenecks().

◆ blctreeComputeEdgesState()

static void blctreeComputeEdgesState	(	const GRAPH *	graph,
		BLCTREE *	blctree
	)

static

sets stage of MST edges

Parameters

graph	the graph
blctree	to be built

Definition at line 400 of file reduce_util.c.

References FALSE, GRAPH::grad, graph_isMarked(), graph_knot_isInRange(), graph_pc_isPc(), graph_pc_knotIsDummyTerm(), Is_term, bottleneck_link_cut_tree::mst, bottleneck_link_cut_tree::mstedges_isLink, bottleneck_link_cut_tree::nnodes_curr, bottleneck_link_cut_tree::nodes_curr2org, bottleneck_link_cut_tree::nodes_org2curr, bottleneck_link_cut_tree::root, SCIP_Bool, GRAPH::source, GRAPH::term, and TRUE.

Referenced by blctreeInitBottlenecks().

◆ blctreeBuildMst()

static SCIP_RETCODE blctreeBuildMst	(	SCIP *	scip,
		GRAPH *	graph,
		BLCTREE *	blctree
	)

static

builds MST and sets BLC tree accordingly

Parameters

scip	SCIP
graph	the graph
blctree	to be built

Definition at line 445 of file reduce_util.c.

References blctreeResetNode(), GRAPH::cost, shortest_path::edge, GRAPH::extended, FARAWAY, flipedge, GRAPH::grad, graph_get_nNodes(), graph_knot_isInRange(), graph_path_exec(), graph_pc_isMw(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), GRAPH::head, bottleneck_link_cut_tree::mst, MST_MODE, bottleneck_link_cut_tree::nnodes_curr, bottleneck_link_cut_tree::nnodes_org, bottleneck_link_cut_tree::nodes_curr2org, bottleneck_link_cut_tree::nodes_org2curr, bottleneck_link_cut_tree::root, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, GRAPH::source, and GRAPH::tail.

Referenced by blctreeInitBottlenecks().

◆ blctreeInitBottlenecks()

static SCIP_RETCODE blctreeInitBottlenecks	(	SCIP *	scip,
		GRAPH *	graph,
		BLCTREE *	blctree
	)

static

builds BLC tree

Parameters

scip	SCIP
graph	the graph
blctree	to be built

Definition at line 516 of file reduce_util.c.

References blctreeBuildMst(), blctreeComputeBottlenecks(), blctreeComputeEdgesState(), SCIP_CALL, and SCIP_OKAY.

Referenced by reduce_blctreeInit(), and reduce_blctreeRebuild().

◆ dcmstInsert()

static void dcmstInsert	(	const CSR *	org_mst,
		const SCIP_Real	adjcosts[],
		int	root,
		CEDGE	new_mst[],
		SCIP_Bool	new_nodemarked[],
		CEDGE *	max_path_edge,
		int *	new_nedges
	)

static

recursive method for adding node to MST

Parameters

org_mst	the base MST
adjcosts	(undirected) adjacency costs for new node
root	the current root
new_mst	new MST
new_nodemarked	array
max_path_edge	pointer to maximum edge on path to new node
new_nedges	pointer to current number of edges

Definition at line 532 of file reduce_util.c.

References complete_edge::cost, csr_storage::cost, complete_edge::head, csr_storage::head, nnodes, csr_storage::nnodes, SCIP_Real, csr_storage::start, complete_edge::tail, TRUE, and w.

Referenced by dcmstAddNode().

◆ dcmstAddNode()

static void dcmstAddNode	(	const CSR *	mst_in,
		const SCIP_Real *	adjcosts,
		DCMST *	dmst
	)

inlinestatic

add node to MST

Parameters

mst_in	source
adjcosts	(undirected) adjacency costs for new node
dmst	underlying structure

Definition at line 600 of file reduce_util.c.

References dcmstInsert(), dynamic_complete_minimum_spanning_tree::edgestore, FALSE, csr_storage::nnodes, dynamic_complete_minimum_spanning_tree::nodemark, SCIP_Bool, complete_edge::tail, and TRUE.

Referenced by reduce_dcmstAddNode(), reduce_dcmstAddNodeInplace(), and reduce_dcmstGetExtWeight().

◆ dcmstGetCSRfromStore()

static void dcmstGetCSRfromStore	(	const DCMST *	dmst,
		CSR *	mst_out
	)

inlinestatic

transforms edge-store to CSR

Parameters

dmst	underlying structure
mst_out	target

Definition at line 629 of file reduce_util.c.

References BMSclearMemoryArray, complete_edge::cost, csr_storage::cost, dynamic_complete_minimum_spanning_tree::edgestore, complete_edge::head, csr_storage::head, csr_storage::nedges_max, csr_storage::nnodes, SCIP_Real, csr_storage::start, and complete_edge::tail.

Referenced by reduce_dcmstAddNode(), and reduce_dcmstAddNodeInplace().

◆ dcmstGetWeightFromStore()

static SCIP_Real dcmstGetWeightFromStore	(	SCIP *	scip,
		int	mst_nedges,
		const DCMST *	dmst
	)

inlinestatic

gets weight of MST from DCMST store

Parameters

scip	SCIP
mst_nedges	number of edges
dmst	underlying structure

Definition at line 689 of file reduce_util.c.

References complete_edge::cost, dynamic_complete_minimum_spanning_tree::edgestore, FARAWAY, GE, complete_edge::head, LE, SCIP_Real, and complete_edge::tail.

Referenced by reduce_dcmstGetExtWeight().

◆ starSelectedPositionsReset()

static void starSelectedPositionsReset ( STAR * star )

inlinestatic

sets star position array to initial setting for current star degree

Parameters

star the star

Definition at line 721 of file reduce_util.c.

References node_one_hop_star::edgesSelectedPos, and node_one_hop_star::starDegree.

Referenced by reduce_starReset(), reduce_starResetWithEdges(), and starSelectedPositionsSetNext().

◆ starSelectedEdgesUpdate()

static void starSelectedEdgesUpdate ( STAR * star )

inlinestatic

fills array star->edgesSelected by using the current positions

Parameters

star	the star (in/out)

Definition at line 737 of file reduce_util.c.

References node_one_hop_star::edgeId, node_one_hop_star::edgesSelected, node_one_hop_star::edgesSelectedPos, and node_one_hop_star::starDegree.

Referenced by reduce_starGetNext(), and reduce_starGetNextAndPosition().

◆ starSelectedPositionsCopy()

static void starSelectedPositionsCopy	(	const STAR *	star,
		int *	posStorage
	)

inlinestatic

copies selected positions into given array

Parameters

star	the star (in/out)
posStorage	to copy into

Definition at line 757 of file reduce_util.c.

References node_one_hop_star::edgesSelectedPos, and node_one_hop_star::starDegree.

Referenced by reduce_starGetNextAndPosition().

◆ starSelectedPositionsSetNext()

static void starSelectedPositionsSetNext ( STAR * star )

inlinestatic

moves to next star

Parameters

star	the star (in/out)

Definition at line 779 of file reduce_util.c.

References BMScopyMemoryArray, node_one_hop_star::edgesSelectedPos, node_one_hop_star::edgesSelectedPosPrev, node_one_hop_star::nodeDegree, SCIP_Bool, node_one_hop_star::starDegree, node_one_hop_star::starDegreePrev, and starSelectedPositionsReset().

Referenced by reduce_starGetNext(), and reduce_starGetNextAndPosition().

◆ starIsDeg2()

static SCIP_Bool starIsDeg2 ( const STAR * star )

inlinestatic

have we just move past the last star?

Parameters

star	the star (in/out)

Definition at line 834 of file reduce_util.c.

References FALSE, node_one_hop_star::starDegree, and TRUE.

Referenced by reduce_starGetNext(), and reduce_starGetNextAndPosition().

◆ impliedNodesAddTerm()

static void impliedNodesAddTerm	(	SCIP *	scip,
		const GRAPH *	graph,
		int	term,
		STP_Vectype(int) *	nodes_implications
	)

inlinestatic

adds implication for terminal

Parameters

scip	SCIP data structure
graph	graph data structure
term	term
nodes_implications	array of size \|V\|; returned with implications per node or NULL

Definition at line 850 of file reduce_util.c.

References GRAPH::cost, EAT_LAST, EQ, FARAWAY, graph_pc_isPcMw(), graph_pc_knotIsDummyTerm(), GRAPH::ieat, GRAPH::inpbeg, Is_term, LE, LT, GRAPH::prize, SCIP_Bool, SCIP_Real, SCIPdebugMessage, STP_RPCSPG, GRAPH::stp_type, StpVecPushBack, GRAPH::tail, and GRAPH::term.

Referenced by reduce_impliedNodesGet(), and reduce_impliedNodesRepair().

◆ impliedNodesRemoveTerm()

static void impliedNodesRemoveTerm	(	const GRAPH *	graph,
		int	neighbor,
		int	term,
		STP_Vectype(int) *	nodes_implications,
		SCIP_Bool *	removed
	)

inlinestatic

removes implication for terminal from neighbor (if implication exists)

Parameters

graph	graph data structure
neighbor	neighbor of term
term	term
nodes_implications	array of size \|V\|; returned with implications per node or NULL
removed	was removed?

Definition at line 902 of file reduce_util.c.

References FALSE, graph_knot_isInRange(), Is_term, STP_Vectype, StpVecGetSize, StpVecPopBack, GRAPH::term, and TRUE.

Referenced by reduce_impliedNodesRepair().

◆ reduce_impliedNodesGet()

void reduce_impliedNodesGet	(	SCIP *	scip,
		const GRAPH *	graph,
		STP_Vectype(int) *	nodes_implications
	)

gets implied nodes for each node

Parameters

scip	SCIP data structure
graph	graph data structure
nodes_implications	array of size \|V\|; returned with implications per node or NULL

Definition at line 937 of file reduce_util.c.

References GRAPH::extended, graph_get_nNodes(), graph_pc_isPcMw(), impliedNodesAddTerm(), Is_term, nnodes, NULL, and GRAPH::term.

Referenced by extreduce_extPermaInit().

◆ reduce_impliedNodesRepair()

void reduce_impliedNodesRepair	(	SCIP *	scip,
		const GRAPH *	graph,
		int	tail,
		int	head,
		STP_Vectype(int) *	nodes_implications
	)

repairs implied nodes list AFTER edge elimination

Parameters

scip	SCIP data structure
graph	graph data structure
tail	tail of eliminated edge
head	head of eliminated edge
nodes_implications	initialized array of size \|V\|

Definition at line 962 of file reduce_util.c.

References GRAPH::extended, graph_knot_isInRange(), graph_pc_isPcMw(), impliedNodesAddTerm(), impliedNodesRemoveTerm(), Is_term, SCIP_Bool, and GRAPH::term.

Referenced by removeEdge(), and replaceEdgeByPath().

◆ reduce_impliedNodesIsValid()

SCIP_Bool reduce_impliedNodesIsValid	(	const GRAPH *	graph,
		const STP_Vectype(int) *	nodes_implications
	)

implied nodes list is valid

Parameters

graph	graph data structure
nodes_implications	initialized array of size \|V\|

Definition at line 996 of file reduce_util.c.

References EAT_LAST, FALSE, GRAPH::grad, graph_get_nNodes(), graph_knot_isInRange(), GRAPH::head, nnodes, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, STP_Vectype, StpVecGetSize, and TRUE.

Referenced by removeEdge(), and replaceEdgeByPath().

◆ reduce_applyPseudoDeletions()

SCIP_RETCODE reduce_applyPseudoDeletions	(	SCIP *	scip,
		const SCIP_Bool *	pseudoDelNodes,
		REDCOST *	redcostdata,
		GRAPH *	graph,
		SCIP_Real *	offsetp,
		int *	nelims
	)

apply pseudo eliminations provided

Parameters

scip	SCIP data structure
pseudoDelNodes	node with pseudo deletable nodes
redcostdata	reduced cost data
graph	graph data structure
offsetp	offset pointer (for PC)
nelims	number of eliminations

Definition at line 1042 of file reduce_util.c.

References shortest_path::dist, EAT_LAST, GRAPH::extended, FALSE, GE, GRAPH::grad, graph_get_nNodes(), graph_knot_delPseudo(), graph_knot_printInfo(), graph_pc_2orgcheck(), graph_pc_2trans(), graph_pc_isPc(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsNonLeafTerm(), graph_valid(), complete_edge::head, GRAPH::head, Is_anyTerm, GRAPH::mark, nnodes, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, redcosts_getCutoffTop(), redcosts_getEdgeCostsTop(), redcosts_getNodeToTermsPathsTop(), redcosts_getRootToNodeDistTop(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, STP_DELPSEUDO_MAXGRAD, STP_DELPSEUDO_MAXNEDGES, GRAPH::term, and TRUE.

Referenced by dapathsReplaceNodes(), and reduce_da().

◆ reduce_blctreeInit()

SCIP_RETCODE reduce_blctreeInit	(	SCIP *	scip,
		GRAPH *	graph,
		BLCTREE **	blctree
	)

initializes BLC tree

Parameters

scip	SCIP
graph	the graph
blctree	to be initialized

Definition at line 1168 of file reduce_util.c.

References blctreeInitBottlenecks(), blctreeInitPrimitives(), graph_mark(), SCIP_CALL, and SCIP_OKAY.

Referenced by reduce_sdInitBiasedBottleneck(), testBLCworksFor3Star(), testBLCworksFor3StarAfterReduction(), and testBLCworksFor5Tree().

◆ reduce_blctreeRebuild()

SCIP_RETCODE reduce_blctreeRebuild	(	SCIP *	scip,
		GRAPH *	graph,
		BLCTREE *	blctree
	)

rebuilds BLC tree (needs to be initializes)

Parameters

scip	SCIP
graph	the graph
blctree	to be initialized

Definition at line 1186 of file reduce_util.c.

References blctreeInitBottlenecks(), SCIP_CALL, and SCIP_OKAY.

◆ reduce_blctreeFree()

void reduce_blctreeFree	(	SCIP *	scip,
		BLCTREE **	blctree
	)

frees BLC tree

Parameters

scip	SCIP
blctree	to be freed

Definition at line 1201 of file reduce_util.c.

References SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by reduce_sdFree(), testBLCworksFor3Star(), testBLCworksFor3StarAfterReduction(), and testBLCworksFor5Tree().

◆ reduce_blctreeGetMstNedges()

int reduce_blctreeGetMstNedges ( const BLCTREE * blctree )

gets number of BLC MST edges

Parameters

blctree BLC tree

Definition at line 1218 of file reduce_util.c.

References bottleneck_link_cut_tree::nnodes_curr.

Referenced by nsvInitData(), and reduce_sdprofitUpdateFromBLC().

◆ reduce_blctreeGetMstEdges()

void reduce_blctreeGetMstEdges	(	const GRAPH *	graph,
		const BLCTREE *	blctree,
		int *	edgelist
	)

gets BLC MST edges

Parameters

graph	graph
blctree	BLC tree
edgelist	of size nodes - 1

Definition at line 1230 of file reduce_util.c.

References bottleneck_link_cut_node::edge, graph_get_nNodes(), bottleneck_link_cut_tree::mst, bottleneck_link_cut_tree::nnodes_curr, bottleneck_link_cut_tree::nnodes_org, bottleneck_link_cut_tree::root, and UNKNOWN.

Referenced by nsvInitData(), reduce_sdprofitUpdateFromBLC(), testBLCworksFor3Star(), testBLCworksFor3StarAfterReduction(), and testBLCworksFor5Tree().

◆ reduce_blctreeGetMstEdgesToCutDist()

void reduce_blctreeGetMstEdgesToCutDist	(	const GRAPH *	graph,
		const BLCTREE *	blctree,
		SCIP_Real *RESTRICT	tails2CutDist,
		SCIP_Real *RESTRICT	heads2CutDist
	)

gets BLC MST edges (maximum) distances from tail to cut

Parameters

graph	graph
blctree	BLC tree
tails2CutDist	of size nodes - 1
heads2CutDist	of size nodes - 1

Definition at line 1266 of file reduce_util.c.

References bottleneck_link_cut_node::dist_edgehead, bottleneck_link_cut_node::dist_edgetail, bottleneck_link_cut_node::edge, GE, graph_edge_printInfo(), graph_get_nNodes(), bottleneck_link_cut_tree::mst, bottleneck_link_cut_tree::nnodes_curr, bottleneck_link_cut_tree::nnodes_org, bottleneck_link_cut_tree::root, SCIP_Real, and UNKNOWN.

◆ reduce_blctreeGetMstEdgesState()

void reduce_blctreeGetMstEdgesState	(	const GRAPH *	graph,
		const BLCTREE *	blctree,
		SCIP_Bool *	statelist
	)

returns BLC MST edges state. I.e. whether the ede is between two terminal or not

Parameters

graph	graph
blctree	BLC tree
statelist	of size nodes - 1

Definition at line 1315 of file reduce_util.c.

References bottleneck_link_cut_node::edge, graph_get_nNodes(), bottleneck_link_cut_tree::mst, bottleneck_link_cut_tree::mstedges_isLink, bottleneck_link_cut_tree::nnodes_curr, bottleneck_link_cut_tree::nnodes_org, bottleneck_link_cut_tree::root, and UNKNOWN.

Referenced by nsvInitData().

◆ reduce_blctreeGetMstBottlenecks()

void reduce_blctreeGetMstBottlenecks	(	const GRAPH *	graph,
		const BLCTREE *	blctree,
		SCIP_Real *	costlist
	)

gets BLC MST bottleneck costs

Parameters

graph	graph
blctree	BLC tree
costlist	of size nodes - 1

Definition at line 1349 of file reduce_util.c.

References bottleneck_link_cut_node::edge, bottleneck_link_cut_node::edgebottleneck, graph_get_nNodes(), bottleneck_link_cut_tree::mst, bottleneck_link_cut_tree::nnodes_curr, bottleneck_link_cut_tree::nnodes_org, bottleneck_link_cut_tree::root, and UNKNOWN.

Referenced by nsvInitData(), reduce_sdprofitUpdateFromBLC(), testBLCworksFor3Star(), testBLCworksFor3StarAfterReduction(), and testBLCworksFor5Tree().

◆ reduce_dcmstInit()

SCIP_RETCODE reduce_dcmstInit	(	SCIP *	scip,
		int	maxnnodes,
		DCMST **	dcmst
	)

initializes dynamic MST structure

Parameters

scip	SCIP
maxnnodes	maximum number of nodes that can be handled
dcmst	to be initialized

Definition at line 1385 of file reduce_util.c.

References dynamic_complete_minimum_spanning_tree::adjcost_buffer, dynamic_complete_minimum_spanning_tree::edgestore, dynamic_complete_minimum_spanning_tree::maxnnodes, dynamic_complete_minimum_spanning_tree::nodemark, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, and SCIPallocMemoryArray.

Referenced by dcmstTest1(), dcmstTest2(), dcmstTest2b(), dcmstTest3(), and extreduce_extPermaInit().

◆ reduce_dcmstAddNode()

void reduce_dcmstAddNode	(	SCIP *	scip,
		const CSR *	mst_in,
		const SCIP_Real *	adjcosts,
		DCMST *	dmst,
		CSR *	mst_out
	)

adds node to CSR "mst_in" and saves result in "mst_out"

Parameters

scip	SCIP
mst_in	source
adjcosts	(undirected) adjacency costs for new node
dmst	underlying structure
mst_out	target

Definition at line 1411 of file reduce_util.c.

References dcmstAddNode(), dcmstGetCSRfromStore(), dynamic_complete_minimum_spanning_tree::maxnnodes, csr_storage::nedges_max, csr_storage::nnodes, and reduce_dcmstMstIsValid().

Referenced by dcmstTest1(), dcmstTest2(), dcmstTest2b(), dcmstTest3(), mstExtend(), and ruledOut().

◆ reduce_dcmstAddNodeInplace()

void reduce_dcmstAddNodeInplace	(	SCIP *	scip,
		const SCIP_Real *	adjcosts,
		DCMST *	dmst,
		CSR *	mst
	)

Adds node to CSR "mst". NOTE: There needs to be enough space in CSR arrays for one more node!

Parameters

scip	SCIP
adjcosts	(undirected) adjacency costs for new node
dmst	underlying structure
mst	source/target

Definition at line 1438 of file reduce_util.c.

References dcmstAddNode(), dcmstGetCSRfromStore(), dynamic_complete_minimum_spanning_tree::maxnnodes, csr_storage::nedges_max, csr_storage::nnodes, and reduce_dcmstMstIsValid().

Referenced by mstExtend().

◆ reduce_dcmstGet0NodeMst()

void reduce_dcmstGet0NodeMst	(	SCIP *	scip,
		CSR *	mst
	)

computes MST on 0 node

Parameters

scip	SCIP
mst	MST

Definition at line 1461 of file reduce_util.c.

References EQ, csr_storage::nedges_max, csr_storage::nnodes, reduce_dcmstGetWeight(), reduce_dcmstMstIsValid(), and csr_storage::start.

◆ reduce_dcmstGet1NodeMst()

void reduce_dcmstGet1NodeMst	(	SCIP *	scip,
		CSR *	mst
	)

computes MST on 1 node

Parameters

scip	SCIP
mst	MST

Definition at line 1479 of file reduce_util.c.

References EQ, csr_storage::nedges_max, csr_storage::nnodes, reduce_dcmstGetWeight(), reduce_dcmstMstIsValid(), and csr_storage::start.

Referenced by add1NodeMst(), and dcmstTest1().

◆ reduce_dcmstGet2NodeMst()

void reduce_dcmstGet2NodeMst	(	SCIP *	scip,
		SCIP_Real	edgecost,
		CSR *	mst
	)

computes MST on 2 nodes

Parameters

scip	SCIP
edgecost	edge cost
mst	MST

Definition at line 1498 of file reduce_util.c.

References complete_edge::cost, csr_storage::cost, EQ, csr_storage::head, csr_storage::nedges_max, csr_storage::nnodes, reduce_dcmstGetWeight(), reduce_dcmstMstIsValid(), SCIP_Real, and csr_storage::start.

Referenced by dcmstTest2(), dcmstTest2b(), and dcmstTest3().

◆ reduce_dcmstGet3NodeMst()

void reduce_dcmstGet3NodeMst	(	SCIP *	scip,
		SCIP_Real	edgecost01,
		SCIP_Real	edgecost02,
		SCIP_Real	edgecost12,
		CSR *	mst
	)

computes MST on 3 nodes

Parameters

scip	SCIP
edgecost01	edge cost
edgecost02	edge cost
edgecost12	edge cost
mst	MST

Definition at line 1528 of file reduce_util.c.

◆ reduce_dcmstGetExtWeight()

SCIP_Real reduce_dcmstGetExtWeight	(	SCIP *	scip,
		const CSR *	mst,
		const SCIP_Real *	adjcosts,
		DCMST *	dmst
	)

gets weight of MST extended along given vertex

Parameters

scip	SCIP
mst	MST for which to compute extended weight
adjcosts	(undirected) adjacency costs for new node
dmst	underlying structure

Definition at line 1541 of file reduce_util.c.

References dcmstAddNode(), dcmstGetWeightFromStore(), FARAWAY, GE, GT, csr_storage::nedges_max, csr_storage::nnodes, reduce_dcmstMstIsValid(), and SCIP_Real.

Referenced by mstLevelLeafTryExtMst().

◆ reduce_dcmstGetWeight()

SCIP_Real reduce_dcmstGetWeight	(	SCIP *	scip,
		const CSR *	mst_in
	)

gets weight of MST

Parameters

scip	SCIP
mst_in	source

Definition at line 1573 of file reduce_util.c.

References complete_edge::cost, csr_storage::cost, FARAWAY, GE, GT, csr_storage::nedges_max, reduce_dcmstMstIsValid(), and SCIP_Real.

Referenced by baseMstFinalizeNew(), dcmstTest1(), dcmstTest2(), dcmstTest2b(), dcmstTest3(), mstCompRuleOut(), mstTopLevelBaseValidWeight(), reduce_dcmstGet0NodeMst(), reduce_dcmstGet1NodeMst(), reduce_dcmstGet2NodeMst(), and ruledOut().

◆ reduce_dcmstGetMaxnnodes()

int reduce_dcmstGetMaxnnodes ( const DCMST * dmst )

returns maximum number of nodes

Parameters

dmst	underlying structure

Definition at line 1604 of file reduce_util.c.

References dynamic_complete_minimum_spanning_tree::maxnnodes.

Referenced by mstCompAddLeaf().

◆ reduce_dcmstGetAdjcostBuffer()

SCIP_Real* reduce_dcmstGetAdjcostBuffer ( const DCMST * dmst )

Returns buffer of size 'reduce_dcmstGetMaxnnodes'. NOTE: buffer is never used within any other function, apart from allocation and freeing. NOTE: in debug mode the array is initialized to -1.0

Parameters

dmst	underlying structure

Definition at line 1617 of file reduce_util.c.

References dynamic_complete_minimum_spanning_tree::adjcost_buffer, and dynamic_complete_minimum_spanning_tree::maxnnodes.

Referenced by baseMstBuildNew(), and mstCompAddLeaf().

◆ reduce_dcmstFree()

void reduce_dcmstFree	(	SCIP *	scip,
		DCMST **	dcmst
	)

frees dynamic MST structure

Parameters

scip	SCIP
dcmst	to be initialized

Definition at line 1634 of file reduce_util.c.

References SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by dcmstTest1(), dcmstTest2(), dcmstTest2b(), dcmstTest3(), and extreduce_extPermaFree().

◆ reduce_dcmstMstIsValid()

SCIP_Bool reduce_dcmstMstIsValid	(	SCIP *	scip,
		const CSR *	cmst
	)

is the CSR a valid MST on any underlying graph (with number of nodes and edges of the CSR)?

Parameters

scip	SCIP
cmst	the MST candidate

Definition at line 1650 of file reduce_util.c.

References FALSE, graph_csr_isValid(), complete_edge::head, csr_storage::head, csr_storage::nedges_max, nnodes, csr_storage::nnodes, SCIP_Bool, SCIP_CALL_ABORT, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeMemoryArray, csr_storage::start, and TRUE.

Referenced by extreduce_mstTopLevelBaseObjValid(), reduce_dcmstAddNode(), reduce_dcmstAddNodeInplace(), reduce_dcmstGet0NodeMst(), reduce_dcmstGet1NodeMst(), reduce_dcmstGet2NodeMst(), reduce_dcmstGetExtWeight(), and reduce_dcmstGetWeight().

◆ reduce_starInit()

SCIP_RETCODE reduce_starInit	(	SCIP *	scip,
		int	maxdegree,
		STAR **	star
	)

initializes STAR structure

Parameters

scip	SCIP
maxdegree	maximum node degree that can be handled
star	the star

Definition at line 1725 of file reduce_util.c.

References node_one_hop_star::allStarsChecked, node_one_hop_star::edgeId, node_one_hop_star::edgeIsFailed, node_one_hop_star::edgesPromising, node_one_hop_star::edgesSelected, node_one_hop_star::edgesSelectedPos, node_one_hop_star::edgesSelectedPosPrev, FALSE, node_one_hop_star::maxNodeDegree, node_one_hop_star::nedgesPromising, node_one_hop_star::nodeDegree, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, node_one_hop_star::starcenter, and node_one_hop_star::starDegree.

Referenced by bdkInit(), extCheckNode(), generalStarInit(), pseudodeleteExecute(), testStar3IsCorrect(), testStar4EdgeIsCorrect(), testStar4IsCorrect(), and testStar5IsCorrect().

◆ reduce_starFree()

void reduce_starFree	(	SCIP *	scip,
		STAR **	star
	)

frees STAR structure

Parameters

scip	SCIP
star	the star

Definition at line 1758 of file reduce_util.c.

References node_one_hop_star::edgeId, node_one_hop_star::edgeIsFailed, node_one_hop_star::edgesPromising, node_one_hop_star::edgesSelected, node_one_hop_star::edgesSelectedPos, node_one_hop_star::edgesSelectedPosPrev, SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by bdkFree(), extCheckNode(), generalStarExit(), pseudodeleteExecute(), testStar3IsCorrect(), testStar4EdgeIsCorrect(), testStar4IsCorrect(), and testStar5IsCorrect().

◆ reduce_starReset()

void reduce_starReset	(	const GRAPH *	g,
		int	node,
		STAR *	star
	)

resets star data structure with new node data

Parameters

g	graph
node	the node (degree <= STP_DELPSEUDO_MAXGRAD)
star	the star

Definition at line 1781 of file reduce_util.c.

References node_one_hop_star::allStarsChecked, EAT_LAST, node_one_hop_star::edgeId, node_one_hop_star::edgeIsFailed, node_one_hop_star::edgesSelectedPosPrev, FALSE, GRAPH::grad, node_one_hop_star::maxNodeDegree, node_one_hop_star::nedgesPromising, node_one_hop_star::nodeDegree, GRAPH::oeat, GRAPH::outbeg, node_one_hop_star::starcenter, node_one_hop_star::starDegree, node_one_hop_star::starDegreePrev, and starSelectedPositionsReset().

Referenced by bdkTryDegGe4(), pseudodeleteInitStar(), testStar3IsCorrect(), testStar4EdgeIsCorrect(), testStar4IsCorrect(), and testStar5IsCorrect().

◆ reduce_starResetWithEdges()

void reduce_starResetWithEdges	(	const GRAPH *	g,
		const STP_Vectype(int)	staredges,
		STAR *	star
	)

resets star data structure with explicitely given edges

Parameters

g	graph
staredges	the edges
star	the star

Definition at line 1816 of file reduce_util.c.

References node_one_hop_star::allStarsChecked, node_one_hop_star::edgeId, node_one_hop_star::edgeIsFailed, node_one_hop_star::edgesSelectedPosPrev, FALSE, graph_edge_isInRange(), node_one_hop_star::nedgesPromising, node_one_hop_star::nodeDegree, node_one_hop_star::starcenter, node_one_hop_star::starDegree, node_one_hop_star::starDegreePrev, starSelectedPositionsReset(), and StpVecGetSize.

◆ reduce_starGetCenter()

int reduce_starGetCenter ( const STAR * star )

gets center

Parameters

star	the star (in/out)

Definition at line 1853 of file reduce_util.c.

References node_one_hop_star::starcenter.

◆ reduce_starGetNext()

const int* reduce_starGetNext	(	STAR *	star,
		int *	nedges
	)

gets next star

Parameters

star	the star (in/out)
nedges	number of edges of next star (out)

Definition at line 1863 of file reduce_util.c.

References node_one_hop_star::allStarsChecked, node_one_hop_star::edgesSelected, reduce_starAllAreChecked(), node_one_hop_star::starDegree, starIsDeg2(), starSelectedEdgesUpdate(), starSelectedPositionsSetNext(), and TRUE.

Referenced by generalStarCheckGetNextStar(), pseudodeleteGetNextStar(), testStar3IsCorrect(), testStar4EdgeIsCorrect(), testStar4IsCorrect(), and testStar5IsCorrect().

◆ reduce_starGetNextAndPosition()

const int* reduce_starGetNextAndPosition	(	STAR *	star,
		int *	position,
		int *	nedges
	)

gets next star

Parameters

star	the star (in/out)
position	array to store the positions
nedges	number of edges of next star (out)

Definition at line 1886 of file reduce_util.c.

References node_one_hop_star::allStarsChecked, node_one_hop_star::edgesSelected, reduce_starAllAreChecked(), node_one_hop_star::starDegree, starIsDeg2(), starSelectedEdgesUpdate(), starSelectedPositionsCopy(), starSelectedPositionsSetNext(), and TRUE.

Referenced by bdkStarLoadNext().

◆ reduce_starGetRuledOutEdges()

const int* reduce_starGetRuledOutEdges	(	STAR *	star,
		int *	nedges
	)

gets ruled out edges after termination

Parameters

star	the star
nedges	number of ruled-out edges

Definition at line 1918 of file reduce_util.c.

References node_one_hop_star::edgeId, node_one_hop_star::edgeIsFailed, node_one_hop_star::edgesPromising, node_one_hop_star::nedgesPromising, node_one_hop_star::nodeDegree, and reduce_starAllAreChecked().

Referenced by bdkTryDegGe4(), and testStar4EdgeIsCorrect().

◆ reduce_starCurrentSetRuledOut()

void reduce_starCurrentSetRuledOut ( STAR * star )

sets current star to ruled-out

Parameters

star the star

Definition at line 1948 of file reduce_util.c.

References reduce_starAllAreChecked().

◆ reduce_starCurrentSetFailed()

void reduce_starCurrentSetFailed ( STAR * star )

sets current star to failed

Parameters

star the star

Definition at line 1960 of file reduce_util.c.

References node_one_hop_star::edgeIsFailed, node_one_hop_star::edgesSelectedPosPrev, node_one_hop_star::nedgesPromising, node_one_hop_star::starDegreePrev, and TRUE.

Referenced by bdkTryDegGe4(), and testStar4EdgeIsCorrect().

◆ reduce_starHasPromisingEdges()

SCIP_Bool reduce_starHasPromisingEdges ( const STAR * star )

are there edge that might still be ruled out?

Parameters

star the star

Definition at line 1990 of file reduce_util.c.

References node_one_hop_star::nedgesPromising.

Referenced by bdkTryDegGe4(), and testStar4EdgeIsCorrect().

◆ reduce_starAllAreChecked()

SCIP_Bool reduce_starAllAreChecked ( const STAR * star )

have all stars been checked?

Parameters

star the star

Definition at line 2002 of file reduce_util.c.

References node_one_hop_star::allStarsChecked.

Referenced by bdkTryDegGe4(), generalStarCheck(), generalStarCheckGetNextStar(), pseudodeleteAllStarsChecked(), reduce_starCurrentSetRuledOut(), reduce_starGetNext(), reduce_starGetNextAndPosition(), reduce_starGetRuledOutEdges(), testStar3IsCorrect(), testStar4EdgeIsCorrect(), testStar4IsCorrect(), and testStar5IsCorrect().

SCIP

Detailed Description

Data Structures

Typedefs

Functions

Typedef Documentation

◆ CEDGE

◆ BLCNODE

Function Documentation

◆ blctreeBuildNodeMap()

◆ blctreeInitPrimitives()

◆ blctreeResetNode()

◆ blctreeEvert()

◆ blctreeGetRootPathCost()

◆ blctreeUpdateRootPath()

◆ blctreeComputeBottlenecks()

◆ blctreeComputeEdgesState()

◆ blctreeBuildMst()

◆ blctreeInitBottlenecks()

◆ dcmstInsert()

◆ dcmstAddNode()

◆ dcmstGetCSRfromStore()

◆ dcmstGetWeightFromStore()

◆ starSelectedPositionsReset()

◆ starSelectedEdgesUpdate()

◆ starSelectedPositionsCopy()

◆ starSelectedPositionsSetNext()

◆ starIsDeg2()

◆ impliedNodesAddTerm()

◆ impliedNodesRemoveTerm()

◆ reduce_impliedNodesGet()

◆ reduce_impliedNodesRepair()

◆ reduce_impliedNodesIsValid()

◆ reduce_applyPseudoDeletions()

◆ reduce_blctreeInit()

◆ reduce_blctreeRebuild()

◆ reduce_blctreeFree()

◆ reduce_blctreeGetMstNedges()

◆ reduce_blctreeGetMstEdges()

◆ reduce_blctreeGetMstEdgesToCutDist()

◆ reduce_blctreeGetMstEdgesState()

◆ reduce_blctreeGetMstBottlenecks()

◆ reduce_dcmstInit()

◆ reduce_dcmstAddNode()

◆ reduce_dcmstAddNodeInplace()

◆ reduce_dcmstGet0NodeMst()

◆ reduce_dcmstGet1NodeMst()

◆ reduce_dcmstGet2NodeMst()

◆ reduce_dcmstGet3NodeMst()

◆ reduce_dcmstGetExtWeight()

◆ reduce_dcmstGetWeight()

◆ reduce_dcmstGetMaxnnodes()

◆ reduce_dcmstGetAdjcostBuffer()

◆ reduce_dcmstFree()

◆ reduce_dcmstMstIsValid()

◆ reduce_starInit()

◆ reduce_starFree()

◆ reduce_starReset()

◆ reduce_starResetWithEdges()

◆ reduce_starGetCenter()

◆ reduce_starGetNext()

◆ reduce_starGetNextAndPosition()

◆ reduce_starGetRuledOutEdges()

◆ reduce_starCurrentSetRuledOut()

◆ reduce_starCurrentSetFailed()

◆ reduce_starHasPromisingEdges()

◆ reduce_starAllAreChecked()