Detailed Description

extended-reduction specific MST algorithms for Steiner tree problems

Author: Daniel Rehfeldt

This file implements MST algorithms for extended reduction techniques for Steiner problems. Allows to efficiently compute and store special distance (SD) MSTs between the leaves of extension tree. Furthermore, one can check for tree bottlenecks.

A 'level' of the extension tree consists of all possible extension edges from the leaf used for extension. For each level there are a number of 'components': all the subsets that were not already ruled-out. Once a level is initiated, all SDs to the other leaves of the tree are computed ('vertical'), as well as the SDs among the level ('horizontal'). These SDs are kept until the level has been removed again. Furthermore, for each level of the tree we store two SD MSTs, namely:

the MST corresponding to the extension tree without the level and without the tree node at which the level is rooted: 'msts_levelbase'
the MST corresponding to the component of this level in the current tree: "msts_comp'

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

Definition in file extreduce_extmst.c.

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "graph.h"
#include "portab.h"
#include "extreduce.h"
#include "extreducedefs.h"

Go to the source code of this file.

Data Structures
struct	mst_extension_tree_component

Macros
#define	EXT_PC_SDMAXVISITS 20

#define	EXT_DOUBLESD_ALWAYS

Typedefs
typedef struct mst_extension_tree_component	MSTXCOMP

Functions
static void	extGetSdPcUpdate (const GRAPH g, const PCDATA pcdata, int vertex1, int vertex2, SCIP_Real *sd)

static SCIP_Real	extGetSdDouble (SCIP scip, const GRAPH g, int vertex1, int vertex2, EXTDATA *extdata)

static SCIP_Real	extGetSdDoubleFromDistdata (SCIP scip, const GRAPH g, int vertex1, int vertex2, DISTDATA distdata, EXTDATA extdata)

static SCIP_Real	extGetSd (SCIP scip, const GRAPH g, int vertex1, int vertex2, EXTDATA *extdata)

static int	extStackGetLastMarked (const EXTDATA *extdata)

static int	extStackGetTopSize (const EXTDATA *extdata)

static int	extGetNancestorLeaves (const EXTDATA *extdata)

static void	mstExtend (SCIP scip, const SCIP_Real adjcosts[], DCMST dcmst, MSTXCOMP *mstextcomp)

static void	baseMstGetAdjcosts (const REDDATA reddata, MSTXCOMP mstextcomp, SCIP_Real adjcosts[])

static void	baseMstGetOrderedParentNodes (const GRAPH graph, const EXTDATA extdata, int *parentcomp_size, int parentcomp_nodes[])

static void	baseMstInitMsts (const EXTDATA extdata, REDDATA reddata, CSR mst_parent, CSR mst_new)

static void	baseMstInitExtComp (const REDDATA reddata, int extnode, const CSR mst_parent, CSR mst_new, MSTXCOMP mstextcomp)

static void	baseMstBuildNew (SCIP scip, const GRAPH graph, REDDATA reddata, EXTDATA extdata, MSTXCOMP *mstextcomp)

static void	baseMstFinalizeNew (SCIP scip, const GRAPH graph, const MSTXCOMP mstextcomp, REDDATA reddata, EXTDATA *extdata)

static void	compMstInitExtComp (const GRAPH graph, const EXTDATA extdata, const CSR mst_base, CSR mst_new, MSTXCOMP *mstextcomp)

static void	compMstInitMsts (EXTDATA extdata, CSR mst_base, CSR *mst_new)

static void	compMstFinalizeNew (const MSTXCOMP mstextcomp, SCIP_Bool deletemst, EXTDATA extdata)

static void	pcSdMarkSingle (const GRAPH graph, int entry, SCIP_Real value, SCIP_Real pcSdToNode, int pcSdCands, int nPcSdCands)

static void	pcSdToNodeMark (const GRAPH graph, int startvertex, EXTDATA extdata)

static void	pcSdToNodeUnmark (const GRAPH graph, int startvertex, EXTDATA extdata)

static SCIP_Bool	dbgBottleneckFromLeafIsDominated (SCIP scip, const GRAPH graph, int topleaf, SCIP_Bool with_sd_double, int edge_forbidden, EXTDATA *extdata)

static void	add1NodeMst (SCIP scip, CSRDEPO msts)

static void	mstAddRootLevelMsts (SCIP scip, EXTDATA extdata)

static void	mstAddRootLevelSDs (int root, EXTDATA *extdata)

static SCIP_Bool	mstEqComp3RuleOut (SCIP scip, const GRAPH graph, SCIP_Real tree_cost, EXTDATA *extdata)

static SCIP_Bool	mstCompLeafToSiblingsBiasedRuleOut (SCIP scip, const GRAPH graph, int edge2top, EXTDATA *extdata)

static SCIP_Bool	mstCompLeafToAncestorsBiasedRuleOut (SCIP scip, const GRAPH graph, int edge2leaf, int nleaves_ancestors, EXTDATA *extdata)

static void	mstCompLeafGetSDsToSiblings (SCIP scip, const GRAPH graph, int edge2top, EXTDATA extdata, SCIP_Real sds[], SCIP_Bool leafRuledOut)

static void	mstCompLeafGetSDsToAncestors (SCIP scip, const GRAPH graph, int edge2leaf, int nleaves_ancestors, EXTDATA extdata, SCIP_Real sds[], SCIP_Bool leafRuledOut)

static void	mstCompLeafGetSDs (SCIP scip, const GRAPH graph, int edge2leaf, EXTDATA extdata, SCIP_Real sds[], SCIP_Bool leafRuledOut)

static void	mstCompAddLeaf (SCIP scip, const GRAPH graph, int edge2leaf, MSTXCOMP mstextcomp, EXTDATA extdata, SCIP_Bool *leafRuledOut)

static SCIP_Bool	mstCompRuleOut (SCIP scip, const GRAPH graph, EXTDATA *extdata)

static void	mstCompBuildMst (SCIP scip, const GRAPH graph, EXTDATA extdata, SCIP_Bool ruledOut)

static void	mstLevelLeafSetVerticalSDsBoth (SCIP scip, const GRAPH graph, int edge2neighbor, EXTDATA extdata, SCIP_Bool ruledOut)

static void	mstLevelLeafAdjustVerticalSDs (int neighbor_base, MLDISTS sds_vertical, EXTDATA extdata)

static void	mstLevelLeafInit (const GRAPH graph, int neighbor_base, int neighbor, EXTDATA extdata)

static void	mstLevelLeafExit (const GRAPH graph, int neighbor_base, int neighbor, SCIP_Bool ruledOut, EXTDATA extdata)

static void	mstLevelLeafTryExtMst (SCIP scip, const GRAPH graph, int extneighbor, EXTDATA extdata, SCIP_Bool leafRuledOut)

static void	mstLevelBuildBaseMst (SCIP scip, const GRAPH graph, int extnode, REDDATA reddata, EXTDATA extdata)

static void	mstLevelBuildBaseMstRoot (SCIP scip, REDDATA reddata)

static void	mstLevelHorizontalAddSds (SCIP scip, const GRAPH graph, int nextedges, const int extedges, EXTDATA extdata, DISTDATA distdata, MLDISTS sds_horizontal)

SCIP_Bool	extreduce_mstRuleOutPeriph (SCIP scip, const GRAPH graph, EXTDATA *extdata)

void	extreduce_mstAddRootLevel (SCIP scip, int root, EXTDATA extdata)

void	extreduce_mstCompRemove (const GRAPH graph, EXTDATA extdata)

void	extreduce_mstLevelInitialInit (REDDATA reddata, EXTDATA extdata)

void	extreduce_mstLevelVerticalAddLeaf (SCIP scip, const GRAPH graph, int edge2neighbor, EXTDATA extdata, SCIP_Bool leafRuledOut)

void	extreduce_mstLevelVerticalAddLeafInitial (SCIP scip, const GRAPH graph, int edge2neighbor, EXTDATA extdata, SCIP_Bool leafRuledOut)

void	extreduce_mstLevelVerticalAddEmpty (const GRAPH graph, EXTDATA extdata)

void	extreduce_mstLevelVerticalReopen (EXTDATA *extdata)

void	extreduce_mstLevelVerticalClose (REDDATA *reddata)

void	extreduce_mstLevelHorizontalAdd (SCIP scip, const GRAPH graph, int nextedges, const int extedges, EXTDATA extdata)

void	extreduce_mstLevelHorizontalAddEmpty (const GRAPH graph, EXTDATA extdata)

void	extreduce_mstLevelHorizontalRemove (REDDATA *reddata)

void	extreduce_mstLevelVerticalRemove (REDDATA *reddata)

void	extreduce_mstLevelClose (SCIP scip, const GRAPH graph, int extnode, EXTDATA *extdata)

void	extreduce_mstLevelRemove (REDDATA *reddata)

SCIP_Real	extreduce_extGetSd (SCIP scip, const GRAPH g, int vertex1, int vertex2, EXTDATA *extdata)

SCIP_Real	extreduce_extGetSdDouble (SCIP scip, const GRAPH g, int vertex1, int vertex2, EXTDATA *extdata)

SCIP_Real	extreduce_extGetSdProper (SCIP scip, const GRAPH g, int vertex1, int vertex2, EXTDATA *extdata)

SCIP_Real	extreduce_extGetSdProperDouble (SCIP scip, const GRAPH g, int vertex1, int vertex2, EXTDATA *extdata)

Macro Definition Documentation

◆ EXT_PC_SDMAXVISITS

#define EXT_PC_SDMAXVISITS 20

maximum visits for PC specific SD computation

Definition at line 52 of file extreduce_extmst.c.

Referenced by pcSdToNodeMark().

◆ EXT_DOUBLESD_ALWAYS

#define EXT_DOUBLESD_ALWAYS

Definition at line 53 of file extreduce_extmst.c.

Typedef Documentation

◆ MSTXCOMP

typedef struct mst_extension_tree_component MSTXCOMP

Function Documentation

◆ extGetSdPcUpdate()

static void extGetSdPcUpdate	(	const GRAPH *	g,
		const PCDATA *	pcdata,
		int	vertex1,
		int	vertex2,
		SCIP_Real *	sd
	)

inlinestatic

returns special distance computed only for PC and for current leaf

Parameters

g	graph data structure
pcdata	PC data
vertex1	second vertex
vertex2	second vertex
sd	special distance

Definition at line 70 of file extreduce_extmst.c.

References EQ, GE, graph_pc_isPcMw(), pcmw_specific_data::pcSdStart, pcmw_specific_data::pcSdToNode, SCIP_Real, and SCIPdebugMessage.

Referenced by extGetSd(), extGetSdDouble(), and extGetSdDoubleFromDistdata().

◆ extGetSdDouble()

static SCIP_Real extGetSdDouble	(	SCIP *	scip,
		const GRAPH *	g,
		int	vertex1,
		int	vertex2,
		EXTDATA *	extdata
	)

inlinestatic

Returns special distance. Checks normal distance from vertex2 to vertex1 if no opposite distance is known.

Parameters

scip	SCIP
g	graph data structure
vertex1	first vertex
vertex2	second vertex
extdata	extension data

Definition at line 95 of file extreduce_extmst.c.

References extension_data::distdata, extGetSdPcUpdate(), extProbIsPc(), extreduce_distDataGetSdDouble(), extension_data::pcdata, SCIP_Real, SCIPisEQ(), and SCIPisGE().

Referenced by dbgBottleneckFromLeafIsDominated(), extGetSd(), extreduce_extGetSdDouble(), and extreduce_extGetSdProperDouble().

◆ extGetSdDoubleFromDistdata()

static SCIP_Real extGetSdDoubleFromDistdata	(	SCIP *	scip,
		const GRAPH *	g,
		int	vertex1,
		int	vertex2,
		DISTDATA *	distdata,
		EXTDATA *	extdata
	)

inlinestatic

As above, but with given distance data

Parameters

scip	SCIP
g	graph data structure
vertex1	first vertex
vertex2	second vertex
distdata	distance data
extdata	extension data

Definition at line 117 of file extreduce_extmst.c.

References extGetSdPcUpdate(), extProbIsPc(), extreduce_distDataGetSdDouble(), extension_data::pcdata, SCIP_Real, SCIPisEQ(), and SCIPisGE().

Referenced by mstCompLeafToAncestorsBiasedRuleOut(), mstLevelHorizontalAddSds(), and mstLevelLeafSetVerticalSDsBoth().

◆ extGetSd()

static SCIP_Real extGetSd	(	SCIP *	scip,
		const GRAPH *	g,
		int	vertex1,
		int	vertex2,
		EXTDATA *	extdata
	)

inlinestatic

Returns special distance. Only checks normal distance from vertex1 to vertex2.

Parameters

scip	SCIP
g	graph data structure
vertex1	first vertex
vertex2	second vertex
extdata	extension data

Definition at line 140 of file extreduce_extmst.c.

References extension_data::distdata, extGetSdDouble(), extGetSdPcUpdate(), extreduce_distDataGetSd(), graph_pc_isPcMw(), NULL, extension_data::pcdata, pcmw_specific_data::pcSdToNode, SCIP_Real, SCIPisEQ(), and SCIPisGE().

Referenced by dbgBottleneckFromLeafIsDominated(), extreduce_extGetSd(), extreduce_extGetSdProper(), mstCompLeafGetSDsToAncestors(), and mstLevelLeafSetVerticalSDsBoth().

◆ extStackGetLastMarked()

static int extStackGetLastMarked ( const EXTDATA * extdata )

inlinestatic

returns position of last marked component

Parameters

extdata extension data

Definition at line 170 of file extreduce_extmst.c.

References EXT_STATE_MARKED, extension_data::extstack_state, and extStackGetPosition().

Referenced by baseMstGetOrderedParentNodes(), and baseMstInitMsts().

◆ extStackGetTopSize()

static int extStackGetTopSize ( const EXTDATA * extdata )

inlinestatic

returns size of top component on the stack

Parameters

extdata extension data

Definition at line 189 of file extreduce_extmst.c.

References EXT_STATE_NONE, extension_data::extstack_start, extension_data::extstack_state, extStackGetPosition(), and STP_EXT_MAXGRAD.

Referenced by compMstInitExtComp(), compMstInitMsts(), extGetNancestorLeaves(), mstCompLeafGetSDsToAncestors(), mstCompLeafGetSDsToSiblings(), and mstCompLeafToAncestorsBiasedRuleOut().

◆ extGetNancestorLeaves()

static int extGetNancestorLeaves ( const EXTDATA * extdata )

inlinestatic

returns number of ancestor leaves (i.e. number of leaves below current level)

Parameters

extdata extension data

Definition at line 206 of file extreduce_extmst.c.

References extIsAtInitialComp(), extStackGetTopSize(), and extension_data::tree_nleaves.

Referenced by mstCompLeafGetSDs().

◆ mstExtend()

static void mstExtend	(	SCIP *	scip,
		const SCIP_Real	adjcosts[],
		DCMST *	dcmst,
		MSTXCOMP *	mstextcomp
	)

inlinestatic

Repeatedly extends MST 'new', starting from MST 'parent' (in 'mstextcomp'). In first call 'new' is extended from 'parent', afterwards from itself

Parameters

scip	SCIP
adjcosts	adjacency costs
dcmst	DCMST
mstextcomp	extension component (in/out)

Definition at line 232 of file extreduce_extmst.c.

References mst_extension_tree_component::isExtended, mst_extension_tree_component::mst_new, mst_extension_tree_component::mst_parent, csr_storage::nedges_max, csr_storage::nnodes, reduce_dcmstAddNode(), reduce_dcmstAddNodeInplace(), and TRUE.

Referenced by baseMstBuildNew(), and mstCompAddLeaf().

◆ baseMstGetAdjcosts()

static void baseMstGetAdjcosts	(	const REDDATA *	reddata,
		MSTXCOMP *	mstextcomp,
		SCIP_Real	adjcosts[]
	)

inlinestatic

fills MST adjacency costs for new vertex in

Parameters

reddata	reduction data
mstextcomp	extension component (in/out)
adjcosts	adjacency costs (out)

Definition at line 262 of file extreduce_extmst.c.

References mst_extension_tree_component::comp_extnode, mst_extension_tree_component::comp_level, mst_extension_tree_component::comp_nodes, mst_extension_tree_component::comp_size, mst_extension_tree_component::comp_vert, extreduce_mldistsTargetDist(), extreduce_mldistsTargetDists(), FARAWAY, mst_extension_tree_component::mst_parent, csr_storage::nnodes, SCIP_Real, reduction_data::sds_horizontal, and reduction_data::sds_vertical.

Referenced by baseMstBuildNew().

◆ baseMstGetOrderedParentNodes()

static void baseMstGetOrderedParentNodes	(	const GRAPH *	graph,
		const EXTDATA *	extdata,
		int *	parentcomp_size,
		int	parentcomp_nodes[]
	)

inlinestatic

Gets nodes of parent component ordered according to their position in the tree leaves array.

Parameters

graph	graph
extdata	extension data
parentcomp_size	size (number of nodes) of parent component
parentcomp_nodes	ordered nodes of parent component

Definition at line 307 of file extreduce_extmst.c.

References extLeafFindPos(), extreduce_extStackCompNOutedges(), extension_data::extstack_data, extStackGetLastMarked(), extStackGetOutEdgesEnd(), extStackGetOutEdgesStart(), GRAPH::head, SCIPsortIntInt(), and STP_EXT_MAXGRAD.

Referenced by baseMstBuildNew().

◆ baseMstInitMsts()

static void baseMstInitMsts	(	const EXTDATA *	extdata,
		REDDATA *	reddata,
		CSR *	mst_parent,
		CSR *	mst_new
	)

inlinestatic

initializes base MST data for old and new MSTs

Parameters

extdata	extension data
reddata	reduction data (in/out)
mst_parent	parent MST (out)
mst_new	new MST (out)

Definition at line 351 of file extreduce_extmst.c.

References extreduce_extStackCompNOutedges(), extreduce_mldistsLevelNTargets(), extreduce_mldistsTopLevel(), extStackGetLastMarked(), graph_csrdepo_addEmptyTopTree(), graph_csrdepo_getEmptyTop(), graph_csrdepo_getTopCSR(), reduction_data::msts_levelbase, csr_storage::nedges_max, csr_storage::nnodes, SCIPdebugMessage, reduction_data::sds_vertical, and extension_data::tree_nleaves.

Referenced by mstLevelBuildBaseMst().

◆ baseMstInitExtComp()

static void baseMstInitExtComp	(	const REDDATA *	reddata,
		int	extnode,
		const CSR *	mst_parent,
		CSR *	mst_new,
		MSTXCOMP *	mstextcomp
	)

inlinestatic

(partially) initializes base MST data

Parameters

reddata	reduction data
extnode	node from which we extended
mst_parent	parent MST
mst_new	new MST (in)
mstextcomp	extension component (out)

Definition at line 385 of file extreduce_extmst.c.

References mst_extension_tree_component::comp_extnode, mst_extension_tree_component::comp_level, mst_extension_tree_component::comp_nodes, mst_extension_tree_component::comp_size, mst_extension_tree_component::comp_vert, extReddataHasBiasedSds(), extreduce_mldistsTopLevel(), FALSE, mst_extension_tree_component::isExtended, mst_extension_tree_component::mst_new, mst_extension_tree_component::mst_parent, NULL, reduction_data::sds_vertical, and reduction_data::sdsbias_vertical.

Referenced by mstLevelBuildBaseMst().

◆ baseMstBuildNew()

static void baseMstBuildNew	(	SCIP *	scip,
		const GRAPH *	graph,
		REDDATA *	reddata,
		EXTDATA *	extdata,
		MSTXCOMP *	mstextcomp
	)

inlinestatic

extends parent base MST to obtain current one

Parameters

scip	SCIP
graph	graph
reddata	reduction data
extdata	extension data
mstextcomp	extension component (in/out)

Definition at line 412 of file extreduce_extmst.c.

References baseMstGetAdjcosts(), baseMstGetOrderedParentNodes(), mst_extension_tree_component::comp_extnode, mst_extension_tree_component::comp_nodes, mst_extension_tree_component::comp_size, mst_extension_tree_component::comp_vert, reduction_data::dcmst, graph_csr_copy(), mst_extension_tree_component::isExtended, mst_extension_tree_component::mst_new, mst_extension_tree_component::mst_parent, mstExtend(), csr_storage::nnodes, NULL, reduce_dcmstGetAdjcostBuffer(), SCIP_Real, STP_EXT_MAXGRAD, and extension_data::tree_nleaves.

Referenced by mstLevelBuildBaseMst().

◆ baseMstFinalizeNew()

static void baseMstFinalizeNew	(	SCIP *	scip,
		const GRAPH *	graph,
		const MSTXCOMP *	mstextcomp,
		REDDATA *	reddata,
		EXTDATA *	extdata
	)

inlinestatic

finalizes base MST built

Parameters

scip	SCIP
graph	graph
mstextcomp	extension component
reddata	reduction data
extdata	extension data

Definition at line 481 of file extreduce_extmst.c.

References mst_extension_tree_component::comp_extnode, extreduce_mstTopLevelBaseObjValid(), graph_csr_print(), graph_csrdepo_emptyTopSetMarked(), graph_csrdepo_print(), mst_extension_tree_component::mst_new, mst_extension_tree_component::mst_parent, reduction_data::msts_levelbase, csr_storage::nedges_max, csr_storage::nnodes, reduce_dcmstGetWeight(), and SCIPdebugMessage.

Referenced by mstLevelBuildBaseMst().

◆ compMstInitExtComp()

static void compMstInitExtComp	(	const GRAPH *	graph,
		const EXTDATA *	extdata,
		const CSR *	mst_base,
		CSR *	mst_new,
		MSTXCOMP *	mstextcomp
	)

inlinestatic

(partially) initializes component extension MST data

Parameters

graph	the graph
extdata	extension data
mst_base	levelbase MST
mst_new	new MST (in)
mstextcomp	extension component (out)

Definition at line 514 of file extreduce_extmst.c.

References mst_extension_tree_component::comp_extnode, mst_extension_tree_component::comp_level, mst_extension_tree_component::comp_nodes, mst_extension_tree_component::comp_size, mst_extension_tree_component::comp_vert, extreduce_mldistsTopLevel(), extStackGetTopSize(), FALSE, mst_extension_tree_component::isExtended, mst_extension_tree_component::mst_new, mst_extension_tree_component::mst_parent, NULL, extension_data::reddata, reduction_data::sds_vertical, and extension_data::tree_depth.

Referenced by mstCompBuildMst().

◆ compMstInitMsts()

static void compMstInitMsts	(	EXTDATA *	extdata,
		CSR *	mst_base,
		CSR *	mst_new
	)

inlinestatic

initializes component MSTs (current component MST and previous levelbase)

Parameters

extdata	extension data
mst_base	the base (out)
mst_new	new MST (out)

Definition at line 539 of file extreduce_extmst.c.

References extInitialCompIsEdge(), extIsAtInitialComp(), extreduce_mldistsLevelNTopTargets(), extStackGetTopSize(), graph_csrdepo_addEmptyTopTree(), graph_csrdepo_getEmptyTop(), graph_csrdepo_getNcsrs(), graph_csrdepo_getTopCSR(), reduction_data::msts_comp, reduction_data::msts_levelbase, csr_storage::nnodes, extension_data::reddata, reduction_data::sds_vertical, and extension_data::tree_nleaves.

Referenced by mstCompBuildMst().

◆ compMstFinalizeNew()

static void compMstFinalizeNew	(	const MSTXCOMP *	mstextcomp,
		SCIP_Bool	deletemst,
		EXTDATA *	extdata
	)

inlinestatic

finalizes component MST

Parameters

mstextcomp	extension component
deletemst	delete the MST?
extdata	extension data

Definition at line 574 of file extreduce_extmst.c.

References graph_csr_print(), graph_csrdepo_emptyTopSetMarked(), graph_csrdepo_print(), graph_csrdepo_removeTop(), mst_extension_tree_component::mst_new, mst_extension_tree_component::mst_parent, reduction_data::msts_comp, csr_storage::nedges_max, csr_storage::nnodes, extension_data::reddata, and SCIPdebugMessage.

Referenced by mstCompBuildMst().

◆ pcSdMarkSingle()

static void pcSdMarkSingle	(	const GRAPH *	graph,
		int	entry,
		SCIP_Real	value,
		SCIP_Real *	pcSdToNode,
		int *	pcSdCands,
		int *	nPcSdCands
	)

inlinestatic

marks single PcSd array entry

Parameters

graph	graph data structure
entry	entry to mark
value	value to mark with
pcSdToNode	node mark array
pcSdCands	marked candidates list
nPcSdCands	pointer to store number of candidates

Definition at line 613 of file extreduce_extmst.c.

References EQ, and GE.

Referenced by pcSdToNodeMark().

◆ pcSdToNodeMark()

static void pcSdToNodeMark	(	const GRAPH *	graph,
		int	startvertex,
		EXTDATA *	extdata
	)

static

marks PcSd array

Parameters

graph	graph data structure
startvertex	vertex to start from
extdata	extension data

Definition at line 642 of file extreduce_extmst.c.

References dynamic_csr_storage::cost, GRAPH::dcsr_storage, csr_range::end, EXT_PC_SDMAXVISITS, graph_pc_isPcMw(), dynamic_csr_storage::head, Is_term, MAX, pcmw_specific_data::nPcSdCands, extension_data::pcdata, pcmw_specific_data::pcSdCands, pcSdMarkSingle(), pcmw_specific_data::pcSdStart, pcmw_specific_data::pcSdToNode, GRAPH::prize, dynamic_csr_storage::range, SCIP_Real, csr_range::start, GRAPH::term, and extension_data::tree_deg.

Referenced by dbgBottleneckFromLeafIsDominated(), mstCompLeafGetSDsToAncestors(), mstLevelHorizontalAddSds(), and mstLevelLeafInit().

◆ pcSdToNodeUnmark()

static void pcSdToNodeUnmark	(	const GRAPH *	graph,
		int	startvertex,
		EXTDATA *	extdata
	)

inlinestatic

unmarks PcSd array

Parameters

graph	graph data structure
startvertex	vertex to start from
extdata	extension data

Definition at line 720 of file extreduce_extmst.c.

References graph_pc_isPcMw(), GRAPH::knots, pcmw_specific_data::nPcSdCands, extension_data::pcdata, pcmw_specific_data::pcSdCands, pcmw_specific_data::pcSdStart, pcmw_specific_data::pcSdToNode, and SCIP_Real.

Referenced by dbgBottleneckFromLeafIsDominated(), mstCompLeafGetSDsToAncestors(), mstLevelHorizontalAddSds(), and mstLevelLeafExit().

◆ dbgBottleneckFromLeafIsDominated()

static SCIP_Bool dbgBottleneckFromLeafIsDominated	(	SCIP *	scip,
		const GRAPH *	graph,
		int	topleaf,
		SCIP_Bool	with_sd_double,
		int	edge_forbidden,
		EXTDATA *	extdata
	)

static

has the leaf a dominated bottleneck with other leaves?

Parameters

scip	SCIP
graph	graph data structure
topleaf	component leaf to check for
with_sd_double	use SD double method?
edge_forbidden	forbidden edge
extdata	extension data

Definition at line 755 of file extreduce_extmst.c.

References extGetSd(), extGetSdDouble(), extreduce_bottleneckIsDominated(), extreduce_bottleneckMarkRootPath(), extreduce_bottleneckUnmarkRootPath(), FALSE, graph_pc_isPc(), pcSdToNodeMark(), pcSdToNodeUnmark(), SCIP_Bool, SCIP_Real, SCIPdebugMessage, extension_data::tree_leaves, extension_data::tree_nleaves, and TRUE.

Referenced by mstCompLeafGetSDs().

◆ add1NodeMst()

static void add1NodeMst	(	SCIP *	scip,
		CSRDEPO *	msts
	)

inlinestatic

helper; adds single node MST

Parameters

scip	SCIP
msts	MSTs

Definition at line 806 of file extreduce_extmst.c.

References graph_csrdepo_addEmptyTop(), graph_csrdepo_emptyTopSetMarked(), graph_csrdepo_getEmptyTop(), and reduce_dcmstGet1NodeMst().

Referenced by mstAddRootLevelMsts(), and mstLevelBuildBaseMstRoot().

◆ mstAddRootLevelMsts()

static void mstAddRootLevelMsts	(	SCIP *	scip,
		EXTDATA *	extdata
	)

static

helper; adds MSTs

Parameters

scip	SCIP
extdata	extension data

Definition at line 826 of file extreduce_extmst.c.

References add1NodeMst(), graph_csrdepo_isEmpty(), reduction_data::msts_comp, reduction_data::msts_levelbase, extension_data::reddata, and extension_data::tree_depth.

Referenced by extreduce_mstAddRootLevel().

◆ mstAddRootLevelSDs()

static void mstAddRootLevelSDs	(	int	root,
		EXTDATA *	extdata
	)

static

helper; adds SDs

Parameters

root	the root of the extension tree
extdata	extension data

Definition at line 847 of file extreduce_extmst.c.

References extReddataHasBiasedSds(), extreduce_mldistsLevelAddAndCloseRoot(), extreduce_mldistsTopLevel(), extension_data::reddata, SCIPdebugMessage, reduction_data::sds_horizontal, reduction_data::sds_vertical, reduction_data::sdsbias_horizontal, and reduction_data::sdsbias_vertical.

Referenced by extreduce_mstAddRootLevel().

◆ mstEqComp3RuleOut()

static SCIP_Bool mstEqComp3RuleOut	(	SCIP *	scip,
		const GRAPH *	graph,
		SCIP_Real	tree_cost,
		EXTDATA *	extdata
	)

inlinestatic

can current 3-leaf tree be rule-out in case of equality?

Parameters

scip	SCIP
graph	graph data structure
tree_cost	tree cost
extdata	extension data

Definition at line 871 of file extreduce_extmst.c.

References extInitialCompIsStar(), extreduce_distDataGetSdDoubleForbidden(), FALSE, LE, SCIP_Real, extension_data::sdeq_hasForbiddenEdges, extension_data::tree_leaves, extension_data::tree_nleaves, and TRUE.

Referenced by mstCompRuleOut().

◆ mstCompLeafToSiblingsBiasedRuleOut()

static SCIP_Bool mstCompLeafToSiblingsBiasedRuleOut	(	SCIP *	scip,
		const GRAPH *	graph,
		int	edge2top,
		EXTDATA *	extdata
	)

inlinestatic

Is bottleneck rule out with biased SDs from leaf of top tree component to siblings possible? NOTE: Only restricted bottleneck tests are performed!

Parameters

scip	SCIP
graph	graph data structure
edge2top	edge to the top component leaf
extdata	extension data

Definition at line 915 of file extreduce_extmst.c.

References extIsAtInitialGenStar(), extReddataHasBiasedSds(), extreduce_bottleneckToSiblingIsDominatedBiased(), extreduce_mldistsTopTargetDist(), extreduce_nodeIsInStackTop(), extreduce_sdshorizontalInSync(), extension_data::extstack_data, extStackGetPosition(), extStackGetTopOutEdgesEnd(), extStackGetTopOutEdgesStart(), FALSE, GRAPH::head, extension_data::reddata, SCIP_Bool, SCIP_Real, SCIPdebugMessage, reduction_data::sdsbias_horizontal, GRAPH::tail, extension_data::tree_deg, and TRUE.

Referenced by mstCompLeafGetSDs().

◆ mstCompLeafToAncestorsBiasedRuleOut()

static SCIP_Bool mstCompLeafToAncestorsBiasedRuleOut	(	SCIP *	scip,
		const GRAPH *	graph,
		int	edge2leaf,
		int	nleaves_ancestors,
		EXTDATA *	extdata
	)

inlinestatic

Is bottleneck rule out with biased SDs from leaf of top tree component to ancestors possible? NOTE: Only restricted bottleneck tests are performed!

Parameters

scip	SCIP
graph	graph data structure
edge2leaf	edge to the top component leaf
nleaves_ancestors	number of leaves to ancestors
extdata	extension data

Definition at line 977 of file extreduce_extmst.c.

References extension_data::distdata_biased, EQ, extGetSdDoubleFromDistdata(), extIsAtInitialGenStar(), extreduce_bottleneckIsDominatedBiased(), extreduce_bottleneckMarkRootPath(), extreduce_bottleneckUnmarkRootPath(), extreduce_mldistsLevelNTopTargets(), extreduce_mldistsTopTargetDists(), extStackGetTopSize(), FALSE, FARAWAY, graph_pc_isPc(), GRAPH::head, extension_data::reddata, SCIP_Bool, SCIP_Real, SCIPdebugMessage, reduction_data::sdsbias_vertical, extension_data::tree_leaves, and TRUE.

Referenced by mstCompLeafGetSDs().

◆ mstCompLeafGetSDsToSiblings()

static void mstCompLeafGetSDsToSiblings	(	SCIP *	scip,
		const GRAPH *	graph,
		int	edge2top,
		EXTDATA *	extdata,
		SCIP_Real	sds[],
		SCIP_Bool *	leafRuledOut
	)

inlinestatic

Gets SDs from leaf of top tree component to siblings for MST calculation. Returns early (with leafRuledOut == TRUE) if extension via 'edge2leaf' can be ruled out already. NOTE: Only restricted bottleneck tests are performed!

Parameters

scip	SCIP
graph	graph data structure
edge2top	edge to the top component leaf
extdata	extension data
sds	array to store the SDs
leafRuledOut	could the extension already by ruled out

Definition at line 1033 of file extreduce_extmst.c.

References EQ, extIsAtInitialGenStar(), extIsAtInitialStar(), extreduce_bottleneckIsDominated(), extreduce_bottleneckMarkRootPath(), extreduce_bottleneckToSiblingIsDominated(), extreduce_bottleneckUnmarkRootPath(), extreduce_mldistsLevelNTopTargets(), extreduce_mldistsTopTargetDist(), extreduce_nodeIsInStackTop(), extreduce_sdshorizontalInSync(), extension_data::extstack_data, extStackGetPosition(), extStackGetTopOutEdgesEnd(), extStackGetTopOutEdgesStart(), extStackGetTopSize(), FALSE, FARAWAY, GRAPH::head, extension_data::reddata, SCIP_Bool, SCIPdebugMessage, reduction_data::sds_horizontal, GRAPH::tail, extension_data::tree_deg, and TRUE.

Referenced by mstCompLeafGetSDs().

◆ mstCompLeafGetSDsToAncestors()

static void mstCompLeafGetSDsToAncestors	(	SCIP *	scip,
		const GRAPH *	graph,
		int	edge2leaf,
		int	nleaves_ancestors,
		EXTDATA *	extdata,
		SCIP_Real	sds[],
		SCIP_Bool *	leafRuledOut
	)

inlinestatic

Gets SDs from leaf of top tree component to ancestors for MST calculation. Returns early (with leafRuledOut == TRUE) if extension via 'edge2leaf' can be ruled out already. NOTE: Only restricted bottleneck tests are performed, UNLESS the leaf has no siblings!

Parameters

scip	SCIP
graph	graph data structure
edge2leaf	edge to the top component leaf
nleaves_ancestors	number of leaves to ancestors
extdata	extension data
sds	array to store the SDs
leafRuledOut	could the extension already by ruled out

Definition at line 1129 of file extreduce_extmst.c.

References EQ, extGetSd(), extIsAtInitialGenStar(), extreduce_bottleneckIsDominated(), extreduce_bottleneckMarkRootPath(), extreduce_bottleneckUnmarkRootPath(), extreduce_mldistsLevelNTopTargets(), extreduce_mldistsTopTargetDists(), extreduce_sdsverticalInSync(), extStackGetTopSize(), FARAWAY, graph_pc_isPc(), GRAPH::head, pcSdToNodeMark(), pcSdToNodeUnmark(), extension_data::reddata, SCIP_Bool, SCIP_Real, SCIPdebugMessage, reduction_data::sds_vertical, extension_data::tree_leaves, and TRUE.

Referenced by mstCompLeafGetSDs().

◆ mstCompLeafGetSDs()

static void mstCompLeafGetSDs	(	SCIP *	scip,
		const GRAPH *	graph,
		int	edge2leaf,
		EXTDATA *	extdata,
		SCIP_Real	sds[],
		SCIP_Bool *	leafRuledOut
	)

inlinestatic

Gets SDs from leaf (head of 'edge2leaf') to all other leaves of the tree. Returns early (with leafRuledOut == TRUE) if extension via 'edge2leaf' can be ruled out already. NOTE: Only restricted bottleneck tests are performed!

Parameters

scip	SCIP
graph	graph data structure
edge2leaf	edge to the top component leaf
extdata	extension data
sds	array to store the SDs
leafRuledOut	could the extension already by ruled out

Definition at line 1206 of file extreduce_extmst.c.

References dbgBottleneckFromLeafIsDominated(), extGetNancestorLeaves(), extInitialCompIsStar(), extReddataHasBiasedSds(), extreduce_sdsTopInSync(), FALSE, graph_pc_isPc(), GRAPH::head, mstCompLeafGetSDsToAncestors(), mstCompLeafGetSDsToSiblings(), mstCompLeafToAncestorsBiasedRuleOut(), mstCompLeafToSiblingsBiasedRuleOut(), extension_data::reddata, SCIP_Bool, extension_data::tree_starcenter, and TRUE.

Referenced by mstCompAddLeaf().

◆ mstCompAddLeaf()

static void mstCompAddLeaf	(	SCIP *	scip,
		const GRAPH *	graph,
		int	edge2leaf,
		MSTXCOMP *	mstextcomp,
		EXTDATA *	extdata,
		SCIP_Bool *	leafRuledOut
	)

inlinestatic

Adds leaf from top component of current tree to MST. I.e., adds SD adjacency costs updates MST. 'edge2leaf' must be in top component of the stack. Returns early (with leafRuledOut == TRUE) if extension via 'edge2leaf' can be ruled out already. NOTE: SDs are not computed but taken from storage!

Parameters

scip	SCIP
graph	graph data structure
edge2leaf	edge to the top component leaf
mstextcomp	MST extension component
extdata	extension data
leafRuledOut	could the extension already by ruled out

Definition at line 1266 of file extreduce_extmst.c.

References mst_extension_tree_component::comp_extnode, mst_extension_tree_component::comp_vert, reduction_data::dcmst, FALSE, mstCompLeafGetSDs(), mstExtend(), extension_data::reddata, reduce_dcmstGetAdjcostBuffer(), reduce_dcmstGetMaxnnodes(), SCIP_Real, and extension_data::tree_nleaves.

Referenced by mstCompBuildMst().

◆ mstCompRuleOut()

static SCIP_Bool mstCompRuleOut	(	SCIP *	scip,
		const GRAPH *	graph,
		EXTDATA *	extdata
	)

inlinestatic

is a rule-out by using the top component possible?

Parameters

scip	SCIP
graph	graph data structure
extdata	extension data

Definition at line 1301 of file extreduce_extmst.c.

References EQ, extInitialCompIsEdge(), extReddataHasBiasedSds(), extreduce_mstbiased3LeafTreeRuleOut(), extreduce_mstTopCompObjValid(), extreduce_spg3LeafTreeRuleOut(), FALSE, GE, graph_csrdepo_getTopCSR(), graph_pc_isPc(), LE, LT, mstEqComp3RuleOut(), reduction_data::msts_comp, csr_storage::nedges_max, NULL, extension_data::pcdata, GRAPH::prize, extension_data::reddata, reduce_dcmstGetWeight(), ruledOut(), SCIP_Bool, SCIP_Real, SCIPdebugMessage, extension_data::tree_cost, pcmw_specific_data::tree_innerPrize, and extension_data::tree_nleaves.

Referenced by extreduce_mstRuleOutPeriph().

◆ mstCompBuildMst()

static void mstCompBuildMst	(	SCIP *	scip,
		const GRAPH *	graph,
		EXTDATA *	extdata,
		SCIP_Bool *	ruledOut
	)

inlinestatic

builds (top) component MST

Parameters

scip	SCIP
graph	graph data structure
extdata	extension data
ruledOut	already ruled out?

Definition at line 1365 of file extreduce_extmst.c.

References compMstFinalizeNew(), compMstInitExtComp(), compMstInitMsts(), EXT_STATE_EXPANDED, extreduce_mstTopCompInSync(), extension_data::extstack_data, extension_data::extstack_state, extStackGetPosition(), extStackGetTopOutEdgesEnd(), extStackGetTopOutEdgesStart(), FALSE, mst_extension_tree_component::mst_new, and mstCompAddLeaf().

Referenced by extreduce_mstRuleOutPeriph().

◆ mstLevelLeafSetVerticalSDsBoth()

static void mstLevelLeafSetVerticalSDsBoth	(	SCIP *	scip,
		const GRAPH *	graph,
		int	edge2neighbor,
		EXTDATA *	extdata,
		SCIP_Bool *	ruledOut
	)

inlinestatic

Computes and stores SDs from head of extension edge to all leaves of the tree. Also computes biased special distances if existing NOTE: ugly, but should be more efficient, because bottleneck distances can be reused!

Parameters

scip	SCIP
graph	graph data structure
edge2neighbor	the edge from the tree to the neighbor
extdata	extension data
ruledOut	early rule out?

Definition at line 1414 of file extreduce_extmst.c.

References extension_data::distdata_biased, extGetSd(), extGetSdDoubleFromDistdata(), extReddataHasBiasedSds(), extreduce_bottleneckWithExtedgeIsDominated(), extreduce_bottleneckWithExtedgeIsDominatedBiased(), extreduce_mldistsEmptySlotTargetDists(), extreduce_mldistsEmptySlotTargetIds(), extSdGetProper(), FALSE, GRAPH::head, NULL, extension_data::reddata, SCIP_Bool, SCIP_Real, SCIPdebugMessage, reduction_data::sds_vertical, reduction_data::sdsbias_vertical, GRAPH::tail, extension_data::tree_deg, extension_data::tree_leaves, extension_data::tree_nleaves, and TRUE.

Referenced by extreduce_mstLevelVerticalAddLeaf(), and extreduce_mstLevelVerticalAddLeafInitial().

◆ mstLevelLeafAdjustVerticalSDs()

static void mstLevelLeafAdjustVerticalSDs	(	int	neighbor_base,
		MLDISTS *	sds_vertical,
		EXTDATA *	extdata
	)

inlinestatic

adjusts vertical SDs by removing the neighbor base entry

Parameters

neighbor_base	the edge from the tree to the neighbor
sds_vertical	SD storage, possibly biased!
extdata	extension data

Definition at line 1488 of file extreduce_extmst.c.

References extInitialCompIsEdge(), extInitialCompIsStar(), extIsAtInitialComp(), extLeafFindPos(), extreduce_mldistsEmptySlotTargetDistsDirty(), extreduce_mldistsEmptySlotTargetIdsDirty(), SCIP_Real, STP_MLDISTS_DIST_UNSET, STP_MLDISTS_ID_UNSET, extension_data::tree_nleaves, extension_data::tree_root, and extension_data::tree_starcenter.

Referenced by mstLevelLeafExit().

◆ mstLevelLeafInit()

static void mstLevelLeafInit	(	const GRAPH *	graph,
		int	neighbor_base,
		int	neighbor,
		EXTDATA *	extdata
	)

inlinestatic

initialization for adding a leaf to a level

Parameters

graph	graph data structure
neighbor_base	neighbor base
neighbor	neighbor
extdata	extension data

Definition at line 1539 of file extreduce_extmst.c.

References extReddataHasBiasedSds(), extreduce_bottleneckMarkRootPath(), extreduce_mldistsEmptySlotSetBase(), graph_pc_isPc(), NULL, extension_data::pcdata, pcmw_specific_data::pcSdToNode, pcSdToNodeMark(), extension_data::reddata, SCIP_Bool, reduction_data::sds_vertical, and reduction_data::sdsbias_vertical.

Referenced by extreduce_mstLevelVerticalAddLeaf(), and extreduce_mstLevelVerticalAddLeafInitial().

◆ mstLevelLeafExit()

static void mstLevelLeafExit	(	const GRAPH *	graph,
		int	neighbor_base,
		int	neighbor,
		SCIP_Bool	ruledOut,
		EXTDATA *	extdata
	)

inlinestatic

finalization for adding a neighbor leaf to a level

Parameters

graph	graph data structure
neighbor_base	neighbor base
neighbor	neighbor
ruledOut	extension along neighbor already ruled out?
extdata	extension data

Definition at line 1569 of file extreduce_extmst.c.

References extReddataHasBiasedSds(), extreduce_bottleneckUnmarkRootPath(), extreduce_mldistsEmptySlotReset(), extreduce_mldistsEmptySlotSetFilled(), graph_pc_isPc(), mstLevelLeafAdjustVerticalSDs(), pcSdToNodeUnmark(), extension_data::reddata, SCIP_Bool, reduction_data::sds_vertical, and reduction_data::sdsbias_vertical.

Referenced by extreduce_mstLevelVerticalAddLeaf(), and extreduce_mstLevelVerticalAddLeafInitial().

◆ mstLevelLeafTryExtMst()

static void mstLevelLeafTryExtMst	(	SCIP *	scip,
		const GRAPH *	graph,
		int	extneighbor,
		EXTDATA *	extdata,
		SCIP_Bool *	leafRuledOut
	)

inlinestatic

checks whether the MST extended at the given neighbor allows to rule-out any extension along this neighbor

Parameters

scip	SCIP
graph	graph data structure
extneighbor	neighbor leaf to extend to
extdata	extension data
leafRuledOut	rule out possible?

Definition at line 1612 of file extreduce_extmst.c.

References reduction_data::dcmst, extreduce_mldistsEmptySlotTargetDistsDirty(), extreduce_mstTopCompExtObjValid(), FALSE, GE, graph_csrdepo_getTopCSR(), graph_pc_isPc(), LT, reduction_data::msts_comp, csr_storage::nnodes, NULL, extension_data::pcdata, GRAPH::prize, extension_data::reddata, reduce_dcmstGetExtWeight(), SCIP_Bool, SCIP_Real, SCIPdebugMessage, reduction_data::sds_vertical, extension_data::tree_cost, pcmw_specific_data::tree_innerPrize, extension_data::tree_nleaves, and TRUE.

Referenced by extreduce_mstLevelVerticalAddLeaf().

◆ mstLevelBuildBaseMst()

static void mstLevelBuildBaseMst	(	SCIP *	scip,
		const GRAPH *	graph,
		int	extnode,
		REDDATA *	reddata,
		EXTDATA *	extdata
	)

inlinestatic

builds base MST

Parameters

scip	SCIP
graph	graph
extnode	node from which to extend
reddata	reduction data
extdata	extension data

Definition at line 1665 of file extreduce_extmst.c.

References baseMstBuildNew(), baseMstFinalizeNew(), baseMstInitExtComp(), baseMstInitMsts(), mst_extension_tree_component::mst_new, mst_extension_tree_component::mst_parent, and extension_data::tree_root.

Referenced by extreduce_mstLevelClose().

◆ mstLevelBuildBaseMstRoot()

static void mstLevelBuildBaseMstRoot	(	SCIP *	scip,
		REDDATA *	reddata
	)

inlinestatic

Builds base MST if the previous level is the root. I.e., just a 1-node MST.

Parameters

scip	SCIP
reddata	reduction data

Definition at line 1695 of file extreduce_extmst.c.

References add1NodeMst(), graph_csrdepo_getNcsrs(), graph_csrdepo_isEmpty(), and reduction_data::msts_levelbase.

Referenced by extreduce_mstLevelClose().

◆ mstLevelHorizontalAddSds()

static void mstLevelHorizontalAddSds	(	SCIP *	scip,
		const GRAPH *	graph,
		int	nextedges,
		const int *	extedges,
		EXTDATA *	extdata,
		DISTDATA *	distdata,
		MLDISTS *	sds_horizontal
	)

static

Compute and store horizontal SDs in given ML storage

Parameters

scip	SCIP
graph	graph data structure
nextedges	number of edges for extension
extedges	array of edges for extension
extdata	extension data
distdata	distance data (possibly biased!)
sds_horizontal	horizontal multi-level distances (possibly biased!)

Definition at line 1711 of file extreduce_extmst.c.

References EQ, extGetSdDoubleFromDistdata(), extProbIsPc(), extreduce_mldistsEmptySlotExists(), extreduce_mldistsEmptySlotSetBase(), extreduce_mldistsEmptySlotSetFilled(), extreduce_mldistsEmptySlotTargetDists(), extreduce_mldistsEmptySlotTargetIds(), extreduce_mldistsLevelAddTop(), extreduce_mldistsTopLevel(), extreduce_mldistsTopTargetDist(), FARAWAY, graph_pc_isPc(), GRAPH::head, pcSdToNodeMark(), pcSdToNodeUnmark(), SCIP_Bool, SCIP_Real, and extension_data::tree_depth.

Referenced by extreduce_mstLevelHorizontalAdd().

◆ extreduce_mstRuleOutPeriph()

SCIP_Bool extreduce_mstRuleOutPeriph	(	SCIP *	scip,
		const GRAPH *	graph,
		EXTDATA *	extdata
	)

Can current tree be peripherally ruled out by using MST based arguments?

Parameters

scip	SCIP
graph	graph data structure
extdata	extension data

Definition at line 1783 of file extreduce_extmst.c.

References extreduce_stackTopIsHashed(), FALSE, mstCompBuildMst(), mstCompRuleOut(), ruledOut(), SCIP_Bool, SCIPdebugMessage, and TRUE.

Referenced by extTreeRuleOutPeriph().

◆ extreduce_mstAddRootLevel()

void extreduce_mstAddRootLevel	(	SCIP *	scip,
		int	root,
		EXTDATA *	extdata
	)

adds the initial level corresponding to the root of the extension tree

Parameters

scip	SCIP
root	the root of the extension tree
extdata	extension data

Definition at line 1814 of file extreduce_extmst.c.

References mstAddRootLevelMsts(), and mstAddRootLevelSDs().

Referenced by extPreprocessInitialComponent().

◆ extreduce_mstCompRemove()

void extreduce_mstCompRemove	(	const GRAPH *	graph,
		EXTDATA *	extdata
	)

Removes current component (subset of the top level) from MST storages

Parameters

graph	graph data structure
extdata	extension data

Definition at line 1829 of file extreduce_extmst.c.

References graph_csrdepo_getNcsrs(), graph_csrdepo_removeTop(), reduction_data::msts_comp, extension_data::reddata, and extension_data::tree_depth.

Referenced by extTreeStackTopRemove().

◆ extreduce_mstLevelInitialInit()

void extreduce_mstLevelInitialInit	(	REDDATA *	reddata,
		EXTDATA *	extdata
	)

Adds a full initial new level at the top. NOTE: for now only the horizontal distances are initialized

Parameters

reddata	reduction data
extdata	extension data

Definition at line 1849 of file extreduce_extmst.c.

References extIsAtInitialComp(), extReddataHasBiasedSds(), extreduce_mldistsLevelAddTop(), extreduce_mldistsTopLevel(), SCIP_Bool, SCIPdebugMessage, reduction_data::sds_vertical, reduction_data::sdsbias_vertical, STP_EXT_MAXGRAD, extension_data::tree_depth, and extension_data::tree_nleaves.

Referenced by extStackTopExpandInitial().

◆ extreduce_mstLevelVerticalAddLeaf()

void extreduce_mstLevelVerticalAddLeaf	(	SCIP *	scip,
		const GRAPH *	graph,
		int	edge2neighbor,
		EXTDATA *	extdata,
		SCIP_Bool *	leafRuledOut
	)

Adds neighbor of tree for MST calculation. Basically, SDs to all leafs are computed and stored in 'reddata->sds_vertical'. Neighbor is given by head of edge 'edge2neighbor'. Returns early (with leafRuledOut == TRUE, and without adding the neighbor) if extension via this edge can be ruled out already by using a bottleneck argument or MST.

Parameters

scip	SCIP
graph	graph data structure
edge2neighbor	the edge from the tree to the neighbor
extdata	extension data
leafRuledOut	could the extension already by ruled out

Definition at line 1882 of file extreduce_extmst.c.

References extInitialCompIsGenStar(), extIsAtInitialComp(), extred_full, extreduce_bottleneckCheckNonLeaves(), extreduce_bottleneckCheckNonLeaves_pc(), FALSE, graph_pc_isPc(), GRAPH::head, extension_data::mode, mstLevelLeafExit(), mstLevelLeafInit(), mstLevelLeafSetVerticalSDsBoth(), mstLevelLeafTryExtMst(), SCIP_Bool, GRAPH::tail, and extension_data::tree_deg.

Referenced by extTreeRuleOutSingletonFull().

◆ extreduce_mstLevelVerticalAddLeafInitial()

void extreduce_mstLevelVerticalAddLeafInitial	(	SCIP *	scip,
		const GRAPH *	graph,
		int	edge2neighbor,
		EXTDATA *	extdata,
		SCIP_Bool *	leafRuledOut
	)

similar to above, but only for initial component!

Parameters

scip	SCIP
graph	graph data structure
edge2neighbor	edge to the neighbor
extdata	extension data
leafRuledOut	could the extension already by ruled out?

Definition at line 1929 of file extreduce_extmst.c.

References extInitialCompIsEdge(), extInitialCompIsStar(), extIsAtInitialComp(), extension_data::extstack_data, FALSE, GRAPH::head, mstLevelLeafExit(), mstLevelLeafInit(), mstLevelLeafSetVerticalSDsBoth(), GRAPH::tail, extension_data::tree_deg, and extension_data::tree_root.

Referenced by extStackTopProcessInitialEdges().

◆ extreduce_mstLevelVerticalAddEmpty()

void extreduce_mstLevelVerticalAddEmpty	(	const GRAPH *	graph,
		EXTDATA *	extdata
	)

Adds empty level for vertical SDs

Parameters

graph	graph data structure
extdata	extension data

Definition at line 1959 of file extreduce_extmst.c.

References extReddataHasBiasedSds(), extreduce_mldistsLevelAddAndCloseEmpty(), extreduce_mldistsTopLevel(), graph_pc_isPc(), extension_data::reddata, SCIPdebugMessage, reduction_data::sds_vertical, reduction_data::sdsbias_vertical, and extension_data::tree_nleaves.

Referenced by extStackTopExpandSingletons().

◆ extreduce_mstLevelVerticalReopen()

void extreduce_mstLevelVerticalReopen ( EXTDATA * extdata )

reopens top level and allows one more slot

Parameters

extdata extension data

Definition at line 1985 of file extreduce_extmst.c.

References extReddataHasBiasedSds(), extreduce_mldistsLevelNTopTargets(), extreduce_mldistsLevelReopenTop(), extreduce_mldistsTopLevel(), extension_data::reddata, reduction_data::sds_vertical, reduction_data::sdsbias_vertical, and extension_data::tree_nleaves.

Referenced by extTreeRuleOutSingletonFull().

◆ extreduce_mstLevelVerticalClose()

void extreduce_mstLevelVerticalClose ( REDDATA * reddata )

closes vertical part of top MST level for further additions

Parameters

reddata reduction data

Definition at line 2008 of file extreduce_extmst.c.

References extReddataHasBiasedSds(), extreduce_mldistsLevelCloseTop(), extreduce_mldistsLevelNSlots(), extreduce_mldistsTopLevel(), SCIPdebugMessage, reduction_data::sds_vertical, and reduction_data::sdsbias_vertical.

Referenced by extStackTopExpandInitial(), and extTreeRuleOutSingletonFull().

◆ extreduce_mstLevelHorizontalAdd()

void extreduce_mstLevelHorizontalAdd	(	SCIP *	scip,
		const GRAPH *	graph,
		int	nextedges,
		const int *	extedges,
		EXTDATA *	extdata
	)

Compute and store horizontal SDs

Parameters

scip	SCIP
graph	graph data structure
nextedges	number of edges for extension
extedges	array of edges for extension
extdata	extension data

Definition at line 2037 of file extreduce_extmst.c.

References extension_data::distdata, extension_data::distdata_biased, extReddataHasBiasedSds(), extreduce_mldistsTopLevel(), graph_pc_isPc(), mstLevelHorizontalAddSds(), extension_data::reddata, SCIPdebugMessage, reduction_data::sds_horizontal, and reduction_data::sdsbias_horizontal.

Referenced by extStackAddCompInitialExpanded(), and extStackAddCompsExpanded().

◆ extreduce_mstLevelHorizontalAddEmpty()

void extreduce_mstLevelHorizontalAddEmpty	(	const GRAPH *	graph,
		EXTDATA *	extdata
	)

Reserve space for horizontal SDs

Parameters

graph	graph data structure
extdata	extension data

Definition at line 2065 of file extreduce_extmst.c.

References extReddataHasBiasedSds(), extreduce_mldistsLevelAddAndCloseEmpty(), extreduce_mldistsTopLevel(), graph_pc_isPc(), extension_data::reddata, SCIPdebugMessage, reduction_data::sds_horizontal, and reduction_data::sdsbias_horizontal.

Referenced by extStackAddCompsExpandedSing().

◆ extreduce_mstLevelHorizontalRemove()

void extreduce_mstLevelHorizontalRemove ( REDDATA * reddata )

Removes top horizontal MST level. NOTE: SDs from level vertices to all leafs will be discarded!

Parameters

reddata reduction data

Definition at line 2090 of file extreduce_extmst.c.

References extReddataHasBiasedSds(), extreduce_mldistsLevelRemoveTop(), extreduce_mldistsNlevels(), SCIPdebugMessage, reduction_data::sds_horizontal, and reduction_data::sdsbias_horizontal.

Referenced by extStackAddCompsExpanded().

◆ extreduce_mstLevelVerticalRemove()

void extreduce_mstLevelVerticalRemove ( REDDATA * reddata )

Removes top vertical MST level. NOTE: SDs from level vertices to all leafs will be discarded!

Parameters

reddata reduction data

Definition at line 2105 of file extreduce_extmst.c.

References extReddataHasBiasedSds(), extreduce_mldistsLevelRemoveTop(), extreduce_mldistsNlevels(), SCIPdebugMessage, reduction_data::sds_vertical, and reduction_data::sdsbias_vertical.

Referenced by extStackTopExpandInitial().

◆ extreduce_mstLevelClose()

void extreduce_mstLevelClose	(	SCIP *	scip,
		const GRAPH *	graph,
		int	extnode,
		EXTDATA *	extdata
	)

Closes top MST level for further additions. Will initialize the 'mst_levelbase' MST.

Parameters

scip	SCIP
graph	graph
extnode	node from which to extend
extdata	extension data

Definition at line 2126 of file extreduce_extmst.c.

References extIsAtInitialComp(), extreduce_mldistsTopLevel(), extreduce_mldistsTopLevelNSlots(), extreduce_mstInternalsInSync(), extreduce_printTopLevel(), mstLevelBuildBaseMst(), mstLevelBuildBaseMstRoot(), extension_data::reddata, SCIPdebugMessage, reduction_data::sds_horizontal, and extension_data::tree_root.

Referenced by extStackAddCompInitialExpanded(), and extStackAddCompsExpandedSing().

◆ extreduce_mstLevelRemove()

void extreduce_mstLevelRemove ( REDDATA * reddata )

Removes top MST level (both vertical and horizontal). NOTE: SDs from level vertices to all leafs will be discarded!

Parameters

reddata reduction data

Definition at line 2160 of file extreduce_extmst.c.

References extReddataHasBiasedSds(), extreduce_mldistsLevelRemoveTop(), extreduce_mldistsNlevels(), graph_csrdepo_getNcsrs(), graph_csrdepo_removeTop(), reduction_data::msts_levelbase, SCIPdebugMessage, reduction_data::sds_horizontal, reduction_data::sds_vertical, reduction_data::sdsbias_horizontal, and reduction_data::sdsbias_vertical.

Referenced by extBacktrack().

◆ extreduce_extGetSd()

SCIP_Real extreduce_extGetSd	(	SCIP *	scip,
		const GRAPH *	g,
		int	vertex1,
		int	vertex2,
		EXTDATA *	extdata
	)

Returns special distance. NOTE: Only checks normal distance from vertex1 to vertex2. I.e., might lead different result if 'vertex1' and 'vertex2' are swapped. SHOULD MOSTLY BE USED FOR DEBUG CHECKS!

Parameters

scip	SCIP
g	graph data structure
vertex1	first vertex
vertex2	second vertex
extdata	extension data

Definition at line 2200 of file extreduce_extmst.c.

References extGetSd().

Referenced by extreduce_bottleneckCheckNonLeaves(), extreduce_bottleneckCheckNonLeaves_pc(), extreduce_sdsverticalInSync(), and sdmstGetWeight().

◆ extreduce_extGetSdDouble()

SCIP_Real extreduce_extGetSdDouble	(	SCIP *	scip,
		const GRAPH *	g,
		int	vertex1,
		int	vertex2,
		EXTDATA *	extdata
	)

Returns special distance. NOTE: Checks normal distance from vertex2 to vertex1 if no opposite distance is known. SHOULD MOSTLY BE USED FOR DEBUG CHECKS!

Parameters

scip	SCIP
g	graph data structure
vertex1	first vertex
vertex2	second vertex
extdata	extension data

Definition at line 2214 of file extreduce_extmst.c.

References extGetSdDouble().

Referenced by extreduce_bottleneckIsDominated(), extreduce_bottleneckWithExtedgeIsDominated(), and sdmstGetWeight().

◆ extreduce_extGetSdProper()

SCIP_Real extreduce_extGetSdProper	(	SCIP *	scip,
		const GRAPH *	g,
		int	vertex1,
		int	vertex2,
		EXTDATA *	extdata
	)

Proper SD version of above method. I.e. SD is non-negative, but possibly FARAWAY FOR DEBUG CHECKS ONLY!

Parameters

scip	SCIP
g	graph data structure
vertex1	first vertex
vertex2	second vertex
extdata	extension data

Definition at line 2228 of file extreduce_extmst.c.

References extGetSd(), and extSdGetProper().

Referenced by extreduce_mstTopCompInSync(), and extreduce_sdsTopInSync().

◆ extreduce_extGetSdProperDouble()

SCIP_Real extreduce_extGetSdProperDouble	(	SCIP *	scip,
		const GRAPH *	g,
		int	vertex1,
		int	vertex2,
		EXTDATA *	extdata
	)

Proper SD version of above method. I.e. SD is non-negative, but possibly FARAWAY FOR DEBUG CHECKS ONLY!

Parameters

scip	SCIP
g	graph data structure
vertex1	first vertex
vertex2	second vertex
extdata	extension data

Definition at line 2242 of file extreduce_extmst.c.

References extGetSdDouble(), and extSdGetProper().

Referenced by extreduce_mstTopCompInSync(), extreduce_sdshorizontalInSync(), and extreduce_sdsTopInSync().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ EXT_PC_SDMAXVISITS

◆ EXT_DOUBLESD_ALWAYS

Typedef Documentation

◆ MSTXCOMP

Function Documentation

◆ extGetSdPcUpdate()

◆ extGetSdDouble()

◆ extGetSdDoubleFromDistdata()

◆ extGetSd()

◆ extStackGetLastMarked()

◆ extStackGetTopSize()

◆ extGetNancestorLeaves()

◆ mstExtend()

◆ baseMstGetAdjcosts()

◆ baseMstGetOrderedParentNodes()

◆ baseMstInitMsts()

◆ baseMstInitExtComp()

◆ baseMstBuildNew()

◆ baseMstFinalizeNew()

◆ compMstInitExtComp()

◆ compMstInitMsts()

◆ compMstFinalizeNew()

◆ pcSdMarkSingle()

◆ pcSdToNodeMark()

◆ pcSdToNodeUnmark()

◆ dbgBottleneckFromLeafIsDominated()

◆ add1NodeMst()

◆ mstAddRootLevelMsts()

◆ mstAddRootLevelSDs()

◆ mstEqComp3RuleOut()

◆ mstCompLeafToSiblingsBiasedRuleOut()

◆ mstCompLeafToAncestorsBiasedRuleOut()

◆ mstCompLeafGetSDsToSiblings()

◆ mstCompLeafGetSDsToAncestors()

◆ mstCompLeafGetSDs()

◆ mstCompAddLeaf()

◆ mstCompRuleOut()

◆ mstCompBuildMst()

◆ mstLevelLeafSetVerticalSDsBoth()

◆ mstLevelLeafAdjustVerticalSDs()

◆ mstLevelLeafInit()

◆ mstLevelLeafExit()

◆ mstLevelLeafTryExtMst()

◆ mstLevelBuildBaseMst()

◆ mstLevelBuildBaseMstRoot()

◆ mstLevelHorizontalAddSds()

◆ extreduce_mstRuleOutPeriph()

◆ extreduce_mstAddRootLevel()

◆ extreduce_mstCompRemove()

◆ extreduce_mstLevelInitialInit()

◆ extreduce_mstLevelVerticalAddLeaf()

◆ extreduce_mstLevelVerticalAddLeafInitial()

◆ extreduce_mstLevelVerticalAddEmpty()

◆ extreduce_mstLevelVerticalReopen()

◆ extreduce_mstLevelVerticalClose()

◆ extreduce_mstLevelHorizontalAdd()

◆ extreduce_mstLevelHorizontalAddEmpty()

◆ extreduce_mstLevelHorizontalRemove()

◆ extreduce_mstLevelVerticalRemove()

◆ extreduce_mstLevelClose()

◆ extreduce_mstLevelRemove()

◆ extreduce_extGetSd()

◆ extreduce_extGetSdDouble()

◆ extreduce_extGetSdProper()

◆ extreduce_extGetSdProperDouble()