extreduce.h File Reference

Detailed Description

This file implements extended reduction techniques for several Steiner problems.

Author

Daniel Rehfeldt

Definition in file extreduce.h.

#include "scip/scip.h"
#include "graph.h"
#include "reduce.h"
#include "completegraph.h"
#include "portab.h"
#include "extreducedefs.h"

Go to the source code of this file.

Functions
SCIP_RETCODE	extreduce_init (SCIP *, SCIP_Bool, enum EXTRED_MODE, GRAPH *, REDCOST *, EXTPERMA **)
void	extreduce_exit (SCIP *, GRAPH *, EXTPERMA **)
SCIP_RETCODE	extreduce_deleteArcs (SCIP *, REDCOST *, const int *, GRAPH *, STP_Bool *, int *)
SCIP_RETCODE	extreduce_deleteEdges (SCIP *, EXTPERMA *, GRAPH *, int *)
SCIP_RETCODE	extreduce_pseudoDeleteNodes (SCIP *, const SCIP_Bool *, EXTPERMA *, GRAPH *, SCIP_Real *, int *)
SCIP_RETCODE	extreduce_deleteGeneralStars (SCIP *, REDCOST *, const int *, GRAPH *, STP_Bool *, int *)
int	extreduce_getMaxTreeDepth (const GRAPH *, const EXTPERMA *)
int	extreduce_getMaxStackSize (void)
int	extreduce_getMaxStackNcomponents (const GRAPH *)
int	extreduce_getMaxStackNedges (const GRAPH *)
void	extreduce_edgeRemove (SCIP *, int, GRAPH *, DISTDATA *, EXTPERMA *)
SCIP_Bool	extreduce_edgeIsValid (const GRAPH *, const REDCOST *, int)
void	extreduce_treeRecompCosts (SCIP *, const GRAPH *, EXTDATA *)
SCIP_RETCODE	extreduce_checkComponent (SCIP *, const GRAPH *, const REDCOST *, EXTCOMP *, EXTPERMA *, SCIP_Bool *)
SCIP_RETCODE	extreduce_checkArc (SCIP *, const GRAPH *, REDCOST *, int, EXTPERMA *, SCIP_Bool *)
SCIP_RETCODE	extreduce_checkEdge (SCIP *, const GRAPH *, const REDCOST *, int, EXTPERMA *, SCIP_Bool *)
SCIP_RETCODE	extreduce_checkNode (SCIP *, const GRAPH *, const REDCOST *, int, STAR *, EXTPERMA *, SCIP_Bool *)
void	extreduce_extCompRevert (const GRAPH *, const EXTPERMA *, EXTCOMP *)
SCIP_Bool	extreduce_extCompIsPromising (const GRAPH *, const EXTPERMA *, const EXTCOMP *)
SCIP_Bool	extreduce_extCompFullIsPromising (const GRAPH *, const EXTPERMA *, const EXTCOMP *)
SCIP_RETCODE	extreduce_distDataInit (SCIP *, GRAPH *, int, SCIP_Bool, SCIP_Bool, DISTDATA **)
SCIP_Real	extreduce_distDataGetSp (SCIP *, const GRAPH *, int, int, int *, int *, DISTDATA *)
void	extreduce_distDataRecomputeDirtyPaths (SCIP *, const GRAPH *, DISTDATA *)
SCIP_Real	extreduce_distDataGetSd (SCIP *, const GRAPH *, int, int, DISTDATA *)
SCIP_Real	extreduce_distDataGetSdDouble (SCIP *, const GRAPH *, int, int, DISTDATA *)
SCIP_Real	extreduce_distDataGetSdDoubleEq (SCIP *, const GRAPH *, SCIP_Real, int, int, DISTDATA *)
SCIP_Real	extreduce_distDataGetSdDoubleForbiddenSingle (SCIP *, const GRAPH *, int, int, int, DISTDATA *)
SCIP_Real	extreduce_distDataGetSdDoubleForbiddenLast (SCIP *, const GRAPH *, int, int, int, int, DISTDATA *)
SCIP_Real	extreduce_distDataGetSdDoubleForbiddenEq (SCIP *, const GRAPH *, SCIP_Real, int, int, int, EXTDATA *)
SCIP_Real	extreduce_distDataGetSdDoubleForbidden (SCIP *, const GRAPH *, int, int, EXTDATA *)
void	extreduce_distDataFree (SCIP *, const GRAPH *, DISTDATA **)
void	extreduce_distDataDeleteEdge (SCIP *, const GRAPH *, int, DISTDATA *)
SCIP_RETCODE	extreduce_contractionInit (SCIP *, int, int, CONTRACT **)
void	extreduce_contractionFree (SCIP *, CONTRACT **)
SCIP_Bool	extreduce_contractionRuleOutPeriph (SCIP *, const GRAPH *, EXTDATA *)
SCIP_RETCODE	extreduce_mldistsInit (SCIP *, int, int, int, int, SCIP_Bool, MLDISTS **)
void	extreduce_mldistsFree (SCIP *, MLDISTS **)
SCIP_Bool	extreduce_mldistsIsEmpty (const MLDISTS *)
SCIP_Bool	extreduce_mldistsEmptySlotExists (const MLDISTS *)
int *	extreduce_mldistsEmptySlotTargetIds (const MLDISTS *)
int *	extreduce_mldistsEmptySlotTargetIdsDirty (const MLDISTS *)
SCIP_Real *	extreduce_mldistsEmptySlotTargetDists (const MLDISTS *)
SCIP_Real *	extreduce_mldistsEmptySlotTargetDistsDirty (const MLDISTS *)
int	extreduce_mldistsEmptySlotLevel (const MLDISTS *)
void	extreduce_mldistsEmptySlotSetBase (int, MLDISTS *)
void	extreduce_mldistsEmptySlotReset (MLDISTS *)
void	extreduce_mldistsEmptySlotSetFilled (MLDISTS *)
void	extreduce_mldistsLevelAddTop (int, int, MLDISTS *)
void	extreduce_mldistsLevelCloseTop (MLDISTS *)
void	extreduce_mldistsLevelAddAndCloseEmpty (int, MLDISTS *)
void	extreduce_mldistsLevelAddAndCloseRoot (int, MLDISTS *)
void	extreduce_mldistsLevelReopenTop (MLDISTS *)
void	extreduce_mldistsLevelRemoveTop (MLDISTS *)
void	extreduce_mldistsLevelRemoveTopNonClosed (MLDISTS *)
int	extreduce_mldistsLevelNTargets (const MLDISTS *, int)
int	extreduce_mldistsLevelNTopTargets (const MLDISTS *)
int	extreduce_mldistsLevelNSlots (const MLDISTS *, int)
int	extreduce_mldistsNlevels (const MLDISTS *)
int	extreduce_mldistsTopLevel (const MLDISTS *)
const int *	extreduce_mldistsTopLevelBases (const MLDISTS *)
int	extreduce_mldistsTopLevelNSlots (const MLDISTS *)
SCIP_Bool	extreduce_mldistsLevelContainsBase (const MLDISTS *, int, int)
const int *	extreduce_mldistsTargetIds (const MLDISTS *, int, int)
const SCIP_Real *	extreduce_mldistsTargetDists (const MLDISTS *, int, int)
SCIP_Real	extreduce_mldistsTargetDist (const MLDISTS *, int, int, int)
const int *	extreduce_mldistsTopTargetIds (const MLDISTS *, int)
const SCIP_Real *	extreduce_mldistsTopTargetDists (const MLDISTS *, int)
SCIP_Real	extreduce_mldistsTopTargetDist (const MLDISTS *, int, int)
void	extreduce_mstAddRootLevel (SCIP *, int, EXTDATA *)
void	extreduce_mstCompRemove (const GRAPH *, EXTDATA *)
void	extreduce_mstLevelRemove (REDDATA *)
void	extreduce_mstLevelClose (SCIP *, const GRAPH *, int, EXTDATA *)
void	extreduce_mstLevelInitialInit (REDDATA *, EXTDATA *)
void	extreduce_mstLevelVerticalAddLeaf (SCIP *, const GRAPH *, int, EXTDATA *, SCIP_Bool *)
void	extreduce_mstLevelVerticalAddLeafInitial (SCIP *, const GRAPH *, int, EXTDATA *, SCIP_Bool *)
void	extreduce_mstLevelVerticalAddEmpty (const GRAPH *, EXTDATA *)
void	extreduce_mstLevelVerticalClose (REDDATA *)
void	extreduce_mstLevelVerticalReopen (EXTDATA *)
void	extreduce_mstLevelVerticalRemove (REDDATA *)
void	extreduce_mstLevelHorizontalRemove (REDDATA *)
void	extreduce_mstLevelHorizontalAdd (SCIP *, const GRAPH *, int, const int *, EXTDATA *)
void	extreduce_mstLevelHorizontalAddEmpty (const GRAPH *, EXTDATA *)
SCIP_Real	extreduce_extGetSd (SCIP *, const GRAPH *, int, int, EXTDATA *)
SCIP_Real	extreduce_extGetSdDouble (SCIP *, const GRAPH *, int, int, EXTDATA *)
SCIP_Real	extreduce_extGetSdProper (SCIP *, const GRAPH *, int, int, EXTDATA *)
SCIP_Real	extreduce_extGetSdProperDouble (SCIP *, const GRAPH *, int, int, EXTDATA *)
SCIP_Bool	extreduce_mstRuleOutPeriph (SCIP *, const GRAPH *, EXTDATA *)
SCIP_RETCODE	extreduce_spgCheck3ComponentSimple (SCIP *, const GRAPH *, int, const EXTCOMP *, SCIP_Bool, DISTDATA *, SCIP_Bool *)
SCIP_RETCODE	extreduce_spgCheck3NodeSimple (SCIP *, const GRAPH *, int, DISTDATA *, SCIP_Bool *)
SCIP_Bool	extreduce_spg3LeafTreeRuleOut (SCIP *, const GRAPH *, SCIP_Real, EXTDATA *)
SCIP_RETCODE	extreduce_mstbiasedCheck3NodeSimple (SCIP *, const GRAPH *, int, DISTDATA *, DISTDATA *, SCIP_Bool *)
SCIP_Bool	extreduce_mstbiased3LeafTreeRuleOut (SCIP *, const GRAPH *, SCIP_Real, EXTDATA *)
void	extreduce_bottleneckMarkRootPath (const GRAPH *, int, EXTDATA *)
void	extreduce_bottleneckUnmarkRootPath (const GRAPH *, int, EXTDATA *)
SCIP_Bool	extreduce_bottleneckIsDominated (SCIP *, const GRAPH *, int, int, SCIP_Real, int, EXTDATA *)
SCIP_Bool	extreduce_bottleneckIsDominatedBiased (SCIP *, const GRAPH *, int, int, SCIP_Real, EXTDATA *)
SCIP_Bool	extreduce_bottleneckWithExtedgeIsDominated (SCIP *, const GRAPH *, int, int, int, SCIP_Real, EXTDATA *)
SCIP_Bool	extreduce_bottleneckWithExtedgeIsDominatedBiased (SCIP *, const GRAPH *, int, int, int, SCIP_Real, EXTDATA *)
SCIP_Bool	extreduce_bottleneckToSiblingIsDominated (SCIP *, const GRAPH *, int, int, SCIP_Real, EXTDATA *)
SCIP_Bool	extreduce_bottleneckToSiblingIsDominatedBiased (SCIP *, const GRAPH *, int, int, SCIP_Real, EXTDATA *)
void	extreduce_bottleneckCheckNonLeaves_pc (SCIP *, const GRAPH *, int, EXTDATA *, SCIP_Bool *)
void	extreduce_bottleneckCheckNonLeaves (SCIP *, const GRAPH *, int, EXTDATA *, SCIP_Bool *)
void	extreduce_redcostAddEdge (const GRAPH *, int, REDDATA *, EXTDATA *)
void	extreduce_redcostRemoveEdge (int, const REDDATA *, EXTDATA *)
void	extreduce_redcostTreeRecompute (SCIP *, const GRAPH *, EXTDATA *)
void	extreduce_redcostInitExpansion (const GRAPH *, EXTDATA *)
SCIP_Bool	extreduce_redcostRuleOutPeriph (const GRAPH *, EXTDATA *)
void	extreduce_extCompClean (SCIP *, const GRAPH *, const EXTCOMP *, SCIP_Bool, EXTDATA *)
SCIP_RETCODE	extreduce_extPermaInit (SCIP *, enum EXTRED_MODE, const GRAPH *, STP_Bool *, EXTPERMA **)
void	extreduce_extPermaAddRandnumgen (SCIP_RANDNUMGEN *, EXTPERMA *)
SCIP_RETCODE	extreduce_extPermaAddMLdistsbiased (SCIP *, EXTPERMA *)
SCIP_Bool	extreduce_extPermaIsClean (const GRAPH *, const EXTPERMA *)
void	extreduce_extPermaFree (SCIP *, EXTPERMA **)
void	extreduce_extdataClean (EXTDATA *)
SCIP_Bool	extreduce_extdataIsClean (const GRAPH *, const EXTDATA *)
void	extreduce_reddataClean (REDDATA *)
SCIP_Bool	extreduce_reddataIsClean (const GRAPH *, const REDDATA *)
void	extreduce_pcdataClean (PCDATA *)
SCIP_Bool	extreduce_pcdataIsClean (const GRAPH *, const PCDATA *)
int	extreduce_extStackCompNOutedges (const EXTDATA *, int)
SCIP_Bool	extreduce_stackTopIsHashed (const GRAPH *, const EXTDATA *)
void	extreduce_extdataCleanArraysDbg (const GRAPH *, EXTDATA *)
SCIP_Bool	extreduce_treeIsFlawed (SCIP *, const GRAPH *, const EXTDATA *)
SCIP_Bool	extreduce_treeIsHashed (const GRAPH *, const EXTDATA *)
SCIP_Bool	extreduce_nodeIsInStackTop (const GRAPH *, const EXTDATA *, int)
SCIP_Bool	extreduce_distCloseNodesAreValid (SCIP *, const GRAPH *, const DISTDATA *)
SCIP_Real	extreduce_distComputeRestrictedDist (SCIP *, const GRAPH *, int, const DISTDATA *, int, int)
void	extreduce_printStack (const GRAPH *, const EXTDATA *)
void	extreduce_printLeaves (const EXTDATA *)
void	extreduce_printTopLevel (const EXTDATA *)
void	extreduce_extendInitDebug (int *, int *)
SCIP_Bool	extreduce_sdsverticalInSync (SCIP *, const GRAPH *, int, int, int, EXTDATA *)
SCIP_Bool	extreduce_sdshorizontalInSync (SCIP *, const GRAPH *, int, EXTDATA *)
SCIP_Bool	extreduce_sdsTopInSync (SCIP *, const GRAPH *, const SCIP_Real[], int, EXTDATA *)
SCIP_Bool	extreduce_mstTopCompInSync (SCIP *, const GRAPH *, EXTDATA *)
SCIP_Bool	extreduce_mstTopCompExtObjValid (SCIP *, const GRAPH *, int, SCIP_Real, EXTDATA *)
SCIP_Bool	extreduce_mstTopCompObjValid (SCIP *, const GRAPH *, SCIP_Real, EXTDATA *)
SCIP_Bool	extreduce_mstInternalsInSync (const EXTDATA *)
SCIP_Bool	extreduce_mstTopLevelBaseObjValid (SCIP *, const GRAPH *, int, EXTDATA *)

Function Documentation

extreduce_init()

SCIP_RETCODE extreduce_init	(	SCIP *	scip,
		SCIP_Bool	useSd,
		enum EXTRED_MODE	mode,
		GRAPH *	graph,
		REDCOST *	redcostdata,
		EXTPERMA **	extpermanent
	)

initializes

Parameters

scip	SCIP data structure
useSd	use special distance?
mode	mode
graph	graph data structure
redcostdata	reduced costs data
extpermanent	permanent extension data (out)

Definition at line 1425 of file extreduce_base.c.

References extension_data_permanent::distdata_default, GRAPH::extended, extreduce_distDataInit(), extreduce_extPermaInit(), FALSE, graph_init_dcsr(), graph_mark(), graph_pc_isPcMw(), NULL, extension_data_permanent::redcostdata, SCIP_CALL, SCIP_OKAY, and STP_EXT_CLOSENODES_MAXN.

Referenced by reduce_da().

extreduce_exit()

void extreduce_exit	(	SCIP *	scip,
		GRAPH *	graph,
		EXTPERMA **	extpermanent
	)

frees

Parameters

scip	SCIP data structure
graph	graph data structure
extpermanent	permanent extension data

Definition at line 1452 of file extreduce_base.c.

References extension_data_permanent::distdata_biased, extension_data_permanent::distdata_default, extreduce_distDataFree(), extreduce_extPermaFree(), and graph_free_dcsr().

Referenced by reduce_da(), and reduce_termsepaDa().

extreduce_deleteArcs()

SCIP_RETCODE extreduce_deleteArcs	(	SCIP *	scip,
		REDCOST *	redcostdata,
		const int *	result,
		GRAPH *	graph,
		STP_Bool *	edgedeletable,
		int *	nelims
	)

Extended reduction test for arcs. This method will also set edgedeletable[a] to TRUE if arc 'a' can be deleted, but its anti-parallel arc not.

Parameters

scip	SCIP data structure
redcostdata	reduced cost data
result	solution array or NULL
graph	graph data structure
edgedeletable	edge array to mark which (directed) edge can be removed
nelims	number of eliminations

Definition at line 1476 of file extreduce_base.c.

References CONNECT, GRAPH::cost, extension_data_permanent::distdata_default, extFree(), extInit(), extreduce_checkArc(), extreduce_edgeIsValid(), FALSE, flipedge, graph_get_nEdges(), graph_pc_isPc(), graphmarkIsClean(), NULL, extension_data_permanent::redcostEqualAllow, redcosts_getCutoffTop(), reduce_sdRepairSetUp(), removeEdge(), extension_data_permanent::result, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPisEQ(), SCIPisZero(), distance_data::sdistdata, and TRUE.

Referenced by fixVarsExtendedRed().

extreduce_deleteEdges()

SCIP_RETCODE extreduce_deleteEdges	(	SCIP *	scip,
		EXTPERMA *	extperma,
		GRAPH *	graph,
		int *	nelims
	)

extended reduction test for edges

Parameters

scip	SCIP data structure
extperma	extension data
graph	graph data structure (in/out)
nelims	number of eliminations (out)

Definition at line 1569 of file extreduce_base.c.

References CONNECT, GRAPH::cost, extension_data_permanent::distdata_default, extred_fast, extred_full, extreduce_checkEdge(), extreduce_edgeIsValid(), FALSE, flipedge, generalStarDeleteEdges(), graph_get_nEdges(), graph_isMarked(), graph_mark(), graph_pc_isMw(), graph_pc_isPc(), graph_typeIsSpgLike(), graphmarkIsClean(), GRAPH::knots, extension_data_permanent::mode, NULL, extension_data_permanent::redcostdata, extension_data_permanent::redcostEqualAllow, redcosts_getCutoffTop(), redcosts_getRootTop(), reduce_pathreplaceExt(), reduce_sdgraphEdgeIsInMst(), reduce_sdRepairSetUp(), reduce_termsepaDaWithExperma(), removeEdge(), extension_data_permanent::result, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisEQ(), SCIPisZero(), special_distance_storage::sdgraph, distance_data::sdistdata, extension_data_permanent::solIsValid, solstp_isUnreduced(), solstp_isValid(), extension_data_permanent::tree_maxdepth, and TRUE.

Referenced by reduceWithEdgeExtReds().

extreduce_pseudoDeleteNodes()

SCIP_RETCODE extreduce_pseudoDeleteNodes	(	SCIP *	scip,
		const SCIP_Bool *	pseudoDelNodes,
		EXTPERMA *	extperma,
		GRAPH *	graph,
		SCIP_Real *	offsetp,
		int *	nelims
	)

extended reduction test for pseudo-eliminating nodes

Parameters

scip	SCIP data structure
pseudoDelNodes	nodes to pseudo-eliminate already
extperma	extension data
graph	graph data structure (in/out)
offsetp	pointer to store offset
nelims	number of eliminations (out)

Definition at line 1668 of file extreduce_base.c.

References delete_all, delete_nonprofits, delete_profits, extension_pseudo_deletion::deletionMode, extension_data_permanent::distdata_biased, extension_data_permanent::distdata_default, GRAPH::extended, extreduce_distDataInit(), extreduce_extPermaAddMLdistsbiased(), FALSE, graph_mark(), graph_pc_2orgcheck(), graph_pc_2trans(), graph_pc_isPc(), distance_data::hasPathReplacement, extension_pseudo_deletion::nelims_extended, NULL, pseudodeleteBiasedIsPromising(), pseudodeleteExecute(), pseudodeleteExit(), pseudodeleteInit(), extension_data_permanent::redcostdata, redcosts_getCutoffTop(), reduce_removeDeg0NonLeafTerms(), reduce_unconnected(), extension_data_permanent::result, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisZero(), extension_data_permanent::solIsValid, solstp_isValid(), STP_EXT_CLOSENODES_MAXN, extension_data_permanent::tree_maxdepth, TRUE, extension_data_permanent::useSdBias, and extension_pseudo_deletion::useSolForEq.

Referenced by extDeleteNodes(), fixVarsRedbased(), reduce_da(), and testPcNode4PseudoDeletedBySd1().

extreduce_deleteGeneralStars()

SCIP_RETCODE extreduce_deleteGeneralStars	(	SCIP *	scip,
		REDCOST *	redcostdata,
		const int *	result,
		GRAPH *	graph,
		STP_Bool *	edgedeletable,
		int *	nelims
	)

deletes center edges of general stars

Parameters

scip	SCIP data structure
redcostdata	reduced cost data
result	solution array or NULL
graph	graph data structure (in/out)
edgedeletable	edge array to mark which (directed) edge can be removed (in/out)
nelims	number of eliminations (out)

Definition at line 1750 of file extreduce_base.c.

References extension_data_permanent::distdata_default, extFree(), extInit(), generalStarDeleteEdges(), graph_pc_isPc(), graphmarkIsClean(), GRAPH::knots, redcosts_getCutoffTop(), redcosts_getRootTop(), reduce_sdRepairSetUp(), extension_data_permanent::result, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPisZero(), and distance_data::sdistdata.

Referenced by testGeneralStarDeletedEdge1(), testGeneralStarDeletedEdge2(), and testGeneralStarDeletedEdge3().

extreduce_getMaxTreeDepth()

int extreduce_getMaxTreeDepth	(	const GRAPH *	graph,
		const EXTPERMA *	extpermanent
	)

get maximum allowed depth for extended tree in given graph

Parameters

graph	graph data structure
extpermanent	extension data

Definition at line 2080 of file extreduce_base.c.

References extred_fast, graph_get_nVET(), extension_data_permanent::mode, NULL, STP_EXT_DEPTH_MAXNEDGES, STP_EXT_DEPTH_MIDNEDGES, STP_EXT_MAXDFSDEPTH, STP_EXT_MIDDFSDEPTH, and STP_EXT_MINDFSDEPTH.

Referenced by extreduce_extPermaInit().

extreduce_getMaxStackSize()

int extreduce_getMaxStackSize

(

void

)

get maximum allowed stack size

Definition at line 2062 of file extreduce_base.c.

References STP_EXT_MAXSTACKSIZE.

Referenced by extreduce_checkComponent(), and extreduce_extdataCleanArraysDbg().

extreduce_getMaxStackNcomponents()

int extreduce_getMaxStackNcomponents

(

const GRAPH *

graph

)

get maximum allowed number of components

Parameters

graph

graph data structure

Definition at line 2069 of file extreduce_base.c.

References STP_EXT_MAXNCOMPS.

Referenced by extreduce_checkComponent(), and extreduce_extdataCleanArraysDbg().

extreduce_getMaxStackNedges()

int extreduce_getMaxStackNedges

(

const GRAPH *

)

extreduce_edgeRemove()

void extreduce_edgeRemove	(	SCIP *	scip,
		int	edge,
		GRAPH *	graph,
		DISTDATA *	distdata,
		EXTPERMA *	extpermanent
	)

deletes an edge and makes corresponding adaptations

Parameters

scip	SCIP
edge	edge to delete
graph	graph data structure (in/out)
distdata	distance data (in/out)
extpermanent	(in/out) can be NULL

Definition at line 1946 of file extreduce_base.c.

References removeEdge().

Referenced by deleteEdge(), deletenodesDeg1(), extCheckArc(), termcompDeleteEdges(), and testDistCloseNodesPcAreValidAfterDeletion().

extreduce_edgeIsValid()

SCIP_Bool extreduce_edgeIsValid	(	const GRAPH *	graph,
		const REDCOST *	redcostdata,
		int	e
	)

is the edge valid?

Parameters

graph	graph data structure
redcostdata	reduced cost data
e	edge to be checked

Definition at line 1959 of file extreduce_base.c.

References EAT_FREE, EQ, FALSE, flipedge, graph_edge_isInRange(), graph_pc_isPcMw(), graph_pc_knotIsDummyTerm(), GRAPH::head, GRAPH::mark, GRAPH::oeat, redcosts_getEdgeCostsTop(), GRAPH::tail, and TRUE.

Referenced by extreduce_deleteArcs(), and extreduce_deleteEdges().

extreduce_treeRecompCosts()

void extreduce_treeRecompCosts	(	SCIP *	scip,
		const GRAPH *	graph,
		EXTDATA *	extdata
	)

recompute costs and reduced costs for current tree

Parameters

scip	SCIP
graph	graph data structure
extdata	extension data

Definition at line 1998 of file extreduce_base.c.

References GRAPH::cost, reduction_data::edgedeleted, EQ, extreduce_redcostTreeRecompute(), extreduce_treeIsFlawed(), graph_pc_isPc(), NULL, extension_data::pcdata, GRAPH::prize, extension_data::reddata, SCIP_Bool, SCIP_Real, SCIPisEQ(), extension_data::tree_cost, extension_data::tree_edges, extension_data::tree_innerNodes, pcmw_specific_data::tree_innerPrize, extension_data::tree_nDelUpArcs, extension_data::tree_nedges, and extension_data::tree_ninnerNodes.

Referenced by extTreeSyncWithStack().

extreduce_checkComponent()

SCIP_RETCODE extreduce_checkComponent	(	SCIP *	scip,
		const GRAPH *	graph,
		const REDCOST *	redcostdata,
		EXTCOMP *	extcomp,
		EXTPERMA *	extpermanent,
		SCIP_Bool *	compIsDeletable
	)

check component for possible elimination

Parameters

scip	SCIP data structure
graph	graph data structure
redcostdata	reduced cost data structures
extcomp	component to be checked (might be reverted)
extpermanent	extension data
compIsDeletable	is component deletable?

Definition at line 2081 of file extreduce_core.c.

References extension_data_permanent::bottleneckDistNode, extension_data_permanent::contration, reduction_data::contration, extension_data_permanent::dcmst, extension_data_permanent::distdata_biased, extension_data_permanent::distdata_default, extension_data_permanent::edgedeleted, GRAPH::edges, extProcessComponent(), extreduce_extCompFullIsPromising(), extreduce_extCompIsPromising(), extreduce_extCompRevert(), extreduce_extdataCleanArraysDbg(), extreduce_extPermaIsClean(), extreduce_getMaxStackNcomponents(), extreduce_getMaxStackSize(), extreduce_reddataClean(), extension_data::extstack_data, FALSE, initial_extension_component::genstar_centeredge, graph_pc_isPc(), graph_pseudoAncestorsGetHashArraySize(), extension_data_permanent::isterm, GRAPH::knots, extension_data_permanent::mode, extension_data_permanent::msts_comp, extension_data_permanent::msts_levelbase, initial_extension_component::ncompedges, nnodes, NULL, extension_data_permanent::pcSdToNode, pcmw_specific_data::pcSdToNode, GRAPH::pseudoancestors, extension_data_permanent::redcostEqualAllow, redcosts_getNlevels(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPfreeCleanBufferArray, extension_data_permanent::sds_horizontal, extension_data_permanent::sds_vertical, extension_data_permanent::sdsbias_horizontal, extension_data_permanent::sdsbias_vertical, extension_data_permanent::tree_deg, extension_data_permanent::tree_maxdepth, extension_data_permanent::tree_maxnedges, extension_data_permanent::tree_maxnleaves, and extension_data_permanent::useSdBias.

Referenced by extreduce_checkArc(), extreduce_checkEdge(), extreduce_checkNode(), and generalStarCheck().

extreduce_checkArc()

SCIP_RETCODE extreduce_checkArc	(	SCIP *	scip,
		const GRAPH *	graph,
		REDCOST *	redcostdata,
		int	edge,
		EXTPERMA *	extpermanent,
		SCIP_Bool *	edgeIsDeletable
	)

check (directed) arc

Parameters

scip	SCIP data structure
graph	graph data structure
redcostdata	reduced cost data structures
edge	edge to be checked
extpermanent	extension data
edgeIsDeletable	is edge deletable?

Definition at line 1794 of file extreduce_base.c.

References initial_extension_component::compedges, shortest_path::dist, GRAPH::extended, extLeafIsExtendable(), extreduce_checkComponent(), extreduce_extPermaIsClean(), FALSE, flipedge, graph_isMarked(), graph_pc_isPcMw(), GRAPH::head, extension_data_permanent::isterm, GRAPH::mark, extension_data_permanent::redcostEqualAllow, redcosts_getCutoffTop(), redcosts_getEdgeCostsTop(), redcosts_getNodeToTermsPathsTop(), redcosts_getRootToNodeDistTop(), redcosts_getRootTop(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisEQ(), SCIPisGT(), GRAPH::tail, and TRUE.

Referenced by extCheckArc(), and extreduce_deleteArcs().

extreduce_checkEdge()

SCIP_RETCODE extreduce_checkEdge	(	SCIP *	scip,
		const GRAPH *	graph,
		const REDCOST *	redcostdata,
		int	edge,
		EXTPERMA *	extpermanent,
		SCIP_Bool *	edgeIsDeletable
	)

check edge

Parameters

scip	SCIP data structure
graph	graph data structure
redcostdata	reduced cost data structures
edge	edge to be checked
extpermanent	extension data
edgeIsDeletable	is edge deletable?

Definition at line 1854 of file extreduce_base.c.

References initial_extension_component::compedges, GRAPH::extended, extLeafIsExtendable(), extreduce_checkComponent(), extreduce_extPermaIsClean(), FALSE, graph_isMarked(), graph_pc_isPcMw(), GRAPH::head, extension_data_permanent::isterm, SCIP_Bool, SCIP_CALL, SCIP_OKAY, GRAPH::tail, and TRUE.

Referenced by extCheckEdge(), and extreduce_deleteEdges().

extreduce_checkNode()

SCIP_RETCODE extreduce_checkNode	(	SCIP *	scip,
		const GRAPH *	graph,
		const REDCOST *	redcostdata,
		int	node,
		STAR *	stardata,
		EXTPERMA *	extpermanent,
		SCIP_Bool *	isPseudoDeletable
	)

check node for possible

Parameters

scip	SCIP data structure
graph	graph data structure
redcostdata	reduced cost data structures
node	the node
stardata	star
extpermanent	extension data
isPseudoDeletable	is node pseudo-deletable?

Definition at line 1890 of file extreduce_base.c.

References initial_extension_component::compedges, extension_data_permanent::distdata_default, extreduce_checkComponent(), extreduce_spgCheck3ComponentSimple(), FALSE, GRAPH::grad, initial_extension_component::ncompedges, pseudodeleteAllStarsChecked(), pseudodeleteFreeStar(), pseudodeleteGetNextStar(), pseudodeleteInitStar(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, extension_data_permanent::tree_maxdepth, and TRUE.

Referenced by extCheckNode(), and pseudodeleteExecute().

extreduce_extCompRevert()

void extreduce_extCompRevert	(	const GRAPH *	graph,
		const EXTPERMA *	extperma,
		EXTCOMP *	extcomp
	)

reverts extension component (makes root the only extension leaf)

Parameters

graph	graph data structure
extperma	extension data
extcomp	component to be cleaned for

Definition at line 52 of file extreduce_util.c.

References initial_extension_component::compedges, initial_extension_component::comproot, initial_extension_component::extleaves, flipedge, GRAPH::head, initial_extension_component::ncompedges, initial_extension_component::nextleaves, SCIP_Bool, and GRAPH::tail.

Referenced by extreduce_checkComponent().

extreduce_extCompIsPromising()

SCIP_Bool extreduce_extCompIsPromising	(	const GRAPH *	graph,
		const EXTPERMA *	extperma,
		const EXTCOMP *	extcomp
	)

is extension component promising candidate for extension?

Parameters

graph	graph data structure
extperma	extension data
extcomp	component to be cleaned for

Definition at line 93 of file extreduce_util.c.

References extLeafIsExtendable(), initial_extension_component::extleaves, FALSE, extension_data_permanent::isterm, initial_extension_component::ncompedges, initial_extension_component::nextleaves, SCIP_Bool, and TRUE.

Referenced by extreduce_checkComponent(), and extreduce_extCompFullIsPromising().

extreduce_extCompFullIsPromising()

SCIP_Bool extreduce_extCompFullIsPromising	(	const GRAPH *	graph,
		const EXTPERMA *	extperma,
		const EXTCOMP *	extcomp
	)

is extension component or its reversed version promising candidate for extension?

Parameters

graph	graph data structure
extperma	extension data
extcomp	component to be cleaned for

Definition at line 124 of file extreduce_util.c.

References initial_extension_component::comproot, extLeafIsExtendable(), extreduce_extCompIsPromising(), FALSE, extension_data_permanent::isterm, and TRUE.

Referenced by extreduce_checkComponent().

extreduce_distDataInit()

SCIP_RETCODE extreduce_distDataInit	(	SCIP *	scip,
		GRAPH *	g,
		int	maxnclosenodes,
		SCIP_Bool	computeSD,
		SCIP_Bool	useBias,
		DISTDATA **	distdata
	)

initializes distance data

Parameters

scip	SCIP
g	graph data structure
maxnclosenodes	maximum number of close nodes to each node
computeSD	also compute special distances?
useBias	use bias?
distdata	to be initialized

Definition at line 1218 of file extreduce_dist.c.

References distance_data::closenodes_prededges, distance_data::closenodes_range, GRAPH::dcsr_storage, distance_data::dheap, distance_data::dijkdata, distDataAllocateNodesArrays(), distDataComputeCloseNodes(), distDataInitSizes(), distDataPathRootsInitialize(), csr_range::end, GRAPH::extended, extreduce_distCloseNodesAreValid(), FALSE, GRAPH::grad, graph_dijkLimited_init(), graph_dijkLimited_initPcShifts(), graph_dijkLimited_reset(), graph_heap_create(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_knotIsNonLeafTerm(), graph_valid_dcsr(), distance_data::hasPathReplacement, close_nodes_run::is_buildphase, GRAPH::knots, GRAPH::mark, nnodes, NULL, reduce_sdInit(), reduce_sdInitBiasedBottleneck(), SCIP_CALL, SCIP_OKAY, SCIPallocMemory, distance_data::sdistdata, csr_range::start, close_nodes_run::startvertex, and TRUE.

Referenced by extCheckArc(), extCheckEdge(), extCheckNode(), extDeleteNodes(), extInit(), extreduce_init(), extreduce_pseudoDeleteNodes(), fixVarsRedbased(), reduce_termsepaDa(), sepafullInitDistdata(), testDistCloseNodesAreValid(), testDistCloseNodesPcAreValid1(), testDistCloseNodesPcAreValid2(), testDistCloseNodesPcAreValidAfterDeletion(), testDistDistancesAreValid(), testDistRootPathsAreValid(), and testNode3PseudoDeletedBySdBiasedSimple().

extreduce_distDataGetSp()

SCIP_Real extreduce_distDataGetSp	(	SCIP *	scip,
		const GRAPH *	g,
		int	vertex1,
		int	vertex2,
		int *	pathnodes,
		int *	npathnodes,
		DISTDATA *	distdata
	)

returns (normal) shortest path distance between vertex1 and vertex2 and provides inner shortest path vertices. Returns -1.0 if no shortest path was found

Parameters

scip	SCIP
g	graph data structure
vertex1	first vertex
vertex2	second vertex
pathnodes	inner nodes
npathnodes	number of inner nodes
distdata	distance data

Definition at line 1400 of file extreduce_dist.c.

References distDataGetSp(), EQ, graph_knot_isInRange(), and SCIP_Real.

Referenced by spg4VerticesRuleOut().

extreduce_distDataRecomputeDirtyPaths()

void extreduce_distDataRecomputeDirtyPaths	(	SCIP *	scip,
		const GRAPH *	g,
		DISTDATA *	distdata
	)

recomputes shortest paths for dirty nodes

Parameters

scip	SCIP
g	graph data structure
distdata	distance data

Definition at line 1370 of file extreduce_dist.c.

References distDataRecomputeNormalDist(), FALSE, GRAPH::grad, graph_get_nNodes(), graph_isMarked(), GRAPH::mark, nnodes, distance_data::pathroot_isdirty, and SCIP_Bool.

Referenced by pseudodeleteExecute().

extreduce_distDataGetSd()

SCIP_Real extreduce_distDataGetSd	(	SCIP *	scip,
		const GRAPH *	g,
		int	vertex1,
		int	vertex2,
		DISTDATA *	distdata
	)

Gets bottleneck (or special) distance between v1 and v2. Will check shortest known v1->v2 path, but NOT shortest known v2->v1 path. Returns -1.0 if no distance is known. (might only happen for RPC or PC)

Parameters

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

Definition at line 1426 of file extreduce_dist.c.

References distDataGetNormalDist(), distDataGetSpecialDist(), EQ, GE, SCIP_Real, and distance_data::sdistdata.

Referenced by extGetSd(), and testDistDistancesAreValid().

extreduce_distDataGetSdDouble()

SCIP_Real extreduce_distDataGetSdDouble	(	SCIP *	scip,
		const GRAPH *	g,
		int	vertex1,
		int	vertex2,
		DISTDATA *	distdata
	)

Gets bottleneck (or special) distance between v1 and v2. Will check shortest known v1->v2 path, and also shortest known v2->v1 path if no v1-v2 path is known. Returns -1.0 if no distance is known. (might only happen for RPC or PC)

Parameters

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

Definition at line 1463 of file extreduce_dist.c.

References distDataGetNormalDist(), distDataGetSpecialDist(), EQ, GE, SCIP_Real, and distance_data::sdistdata.

Referenced by extGetSdDouble(), extGetSdDoubleFromDistdata(), extreduce_mstbiased3LeafTreeRuleOut(), extreduce_mstbiasedCheck3NodeSimple(), mst3LeafTreeGetSds(), pseudodeleteDeleteComputeCutoffs(), sepafullAddSingleSolcandEdges(), spg3StarNeighborRuleOut(), spg4VerticesRuleOut(), and subgraphBuild().

extreduce_distDataGetSdDoubleEq()

SCIP_Real extreduce_distDataGetSdDoubleEq	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Real	dist_eq,
		int	vertex1,
		int	vertex2,
		DISTDATA *	distdata
	)

As 'extreduce_distDataGetSdDouble', but with critial value for early abort

Parameters

scip	SCIP
g	graph data structure
dist_eq	critical distance
vertex1	first vertex
vertex2	second vertex
distdata	distance data

Definition at line 1506 of file extreduce_dist.c.

References distDataGetNormalDist(), distDataGetSpecialDist(), EQ, GE, LT, SCIP_Real, and distance_data::sdistdata.

Referenced by ruleOutFromHead(), ruleOutFromTailCombs(), and ruleOutFromTailSingle().

extreduce_distDataGetSdDoubleForbiddenSingle()

SCIP_Real extreduce_distDataGetSdDoubleForbiddenSingle	(	SCIP *	scip,
		const GRAPH *	g,
		int	edge_forbidden,
		int	vertex1,
		int	vertex2,
		DISTDATA *	distdata
	)

Same as extreduce_distDataGetSdDouble, but only takes paths that do not contain given edge

Parameters

scip	SCIP
g	graph data structure
edge_forbidden	edge
vertex1	first vertex
vertex2	second vertex
distdata	distance data

Definition at line 1669 of file extreduce_dist.c.

References distDataGetNormalDistForbidden(), distDataGetSpecialDistIntermedTerms(), EQ, GE, graph_edge_isInRange(), Is_term, LT, NULL, SCIP_Real, distance_data::sdistdata, and GRAPH::term.

Referenced by generalStarSetUp(), ruleOutFromHead(), ruleOutFromTailCombs(), and ruleOutFromTailSingle().

extreduce_distDataGetSdDoubleForbiddenLast()

SCIP_Real extreduce_distDataGetSdDoubleForbiddenLast	(	SCIP *	scip,
		const GRAPH *	g,
		int	vertex1,
		int	vertex2,
		int	lastedge12,
		int	lastedge21,
		DISTDATA *	distdata
	)

Same as extreduce_distDataGetSdDouble, but only takes paths that do not contain given last edges. NOTE: Behaves peculiarly for terminal-paths!

Parameters

scip	SCIP
g	graph data structure
vertex1	first vertex
vertex2	second vertex
lastedge12	forbidden last edge on v1->v2 path; needs to be in-edge of v2
lastedge21	forbidden last edge on v2->v1 path; needs to be in-edge of v1
distdata	distance data

Definition at line 1727 of file extreduce_dist.c.

References distDataGetNormalDistForbiddenLast(), distDataGetSpecialDistIntermedTerms(), EQ, GE, graph_edge_isInRange(), Is_term, LT, SCIP_Real, distance_data::sdistdata, and GRAPH::term.

Referenced by pseudodeleteDeleteComputeCutoffs().

extreduce_distDataGetSdDoubleForbiddenEq()

SCIP_Real extreduce_distDataGetSdDoubleForbiddenEq	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Real	dist_eq,
		int	edge_forbidden,
		int	vertex1,
		int	vertex2,
		EXTDATA *	extdata
	)

Same as extreduce_distDataGetSdDouble, but only takes paths that do not include given edge or any edges marked as blocked. User needs to provide (known) equality value

Parameters

scip	SCIP
g	graph data structure
dist_eq	critical distance
edge_forbidden	forbidden edge
vertex1	first vertex
vertex2	second vertex
extdata	extension data

Definition at line 1609 of file extreduce_dist.c.

References extension_data::distdata, distDataGetNormalDistForbiddenEq(), distDataGetSpecialDistIntermedTerms(), EQ, extInitialCompIsEdge(), extInitialCompIsGenStar(), GE, graph_edge_isInRange(), Is_term, SCIP_Bool, SCIP_Real, extension_data::sdeq_edgesIsForbidden, distance_data::sdistdata, and GRAPH::term.

Referenced by bottleneckIsEqualityDominated().

extreduce_distDataGetSdDoubleForbidden()

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

Same as extreduce_distDataGetSdDouble, but only takes paths that do not include any edges marked as blocked.

Parameters

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

Definition at line 1557 of file extreduce_dist.c.

References extension_data::distdata, distDataGetNormalDistForbidden(), distDataGetSpecialDistIntermedTerms(), EDGE_FORBIDDEN_NONE, EQ, extInitialCompIsEdge(), extInitialCompIsGenStar(), GE, Is_term, SCIP_Bool, SCIP_Real, extension_data::sdeq_edgesIsForbidden, distance_data::sdistdata, and GRAPH::term.

Referenced by mstEqComp3RuleOut().

extreduce_distDataFree()

void extreduce_distDataFree	(	SCIP *	scip,
		const GRAPH *	graph,
		DISTDATA **	distdata
	)

frees distance data

Parameters

scip	SCIP
graph	graph data structure
distdata	to be freed

Definition at line 1784 of file extreduce_dist.c.

References distance_data::closenodes_distances, distance_data::closenodes_indices, distance_data::closenodes_prededges, distance_data::closenodes_range, distance_data::dheap, distance_data::dijkdata, distDataPathRootsFree(), graph_dijkLimited_free(), graph_heap_free(), reduce_sdFree(), SCIPfreeMemory, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, distance_data::sdistdata, and TRUE.

Referenced by extCheckArc(), extCheckEdge(), extCheckNode(), extDeleteNodes(), extFree(), extreduce_exit(), fixVarsRedbased(), sepafullFree(), testDistCloseNodesAreValid(), testDistCloseNodesPcAreValid1(), testDistCloseNodesPcAreValid2(), testDistCloseNodesPcAreValidAfterDeletion(), testDistDistancesAreValid(), testDistRootPathsAreValid(), and testNode3PseudoDeletedBySdBiasedSimple().

extreduce_distDataDeleteEdge()

void extreduce_distDataDeleteEdge	(	SCIP *	scip,
		const GRAPH *	g,
		int	edge,
		DISTDATA *	distdata
	)

updates data for edge deletion

Parameters

scip	SCIP
g	graph data structure
edge	edge to be deleted
distdata	distance data

Definition at line 1315 of file extreduce_dist.c.

References distance_data::closenodes_distances, distance_data::closenodes_indices, distance_data::closenodes_range, csr_range::end, FARAWAY, NULL, distance_data::pathroot_blocks, distance_data::pathroot_blocksizes, distance_data::pathroot_blocksizesmax, pathroot_state::pathroot_id, distance_data::pathroot_isdirty, pathroot_state::pathroot_nrecomps, distance_data::pathroot_nrecomps, SCIP_Bool, SCIPfreeBlockMemoryArray, csr_range::start, and TRUE.

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

extreduce_contractionInit()

SCIP_RETCODE extreduce_contractionInit	(	SCIP *	scip,
		int	maxnlevels,
		int	maxnleaves,
		CONTRACT **	contraction
	)

initializes

Parameters

scip	SCIP
maxnlevels	maximum number of levels that can be handled
maxnleaves	maximum number of leaves that can be handled
contraction	to be initialized

Definition at line 538 of file extreduce_contract.c.

References FARAWAY, graph_csr_alloc(), extension_tree_contraction::leafToCompLeaves, extension_tree_contraction::leafToCompRootDists, extension_tree_contraction::leafToCompUpDists, extension_tree_contraction::leaves_maxn, extension_tree_contraction::leaves_mindists, extension_tree_contraction::leaves_start, extension_tree_contraction::level_maxn, extension_tree_contraction::level_treecost, extension_tree_contraction::mst_buffer, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, and SCIPallocMemoryArray.

Referenced by extreduce_extPermaInit().

extreduce_contractionFree()

void extreduce_contractionFree	(	SCIP *	scip,
		CONTRACT **	contraction
	)

frees

Parameters

scip	SCIP
contraction	to be initialized

Definition at line 581 of file extreduce_contract.c.

References graph_csr_free(), extension_tree_contraction::leafToCompLeaves, extension_tree_contraction::leafToCompRootDists, extension_tree_contraction::leafToCompUpDists, extension_tree_contraction::leaves_mindists, extension_tree_contraction::leaves_start, extension_tree_contraction::level_treecost, extension_tree_contraction::mst_buffer, SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by extreduce_extPermaFree().

extreduce_contractionRuleOutPeriph()

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

can current tree be peripherally ruled out by using contraction based arguments?

Parameters

scip	SCIP
graph	graph data structure
extdata	extension data

Definition at line 609 of file extreduce_contract.c.

References addComponent(), reduction_data::contration, FALSE, extension_data::reddata, ruledOut(), SCIPdebugMessage, extension_data::tree_nleaves, and TRUE.

Referenced by extTreeRuleOutPeriph().

extreduce_mldistsInit()

SCIP_RETCODE extreduce_mldistsInit	(	SCIP *	scip,
		int	maxnlevels,
		int	maxnslots,
		int	maxntargets,
		int	emptyslot_nbuffers,
		SCIP_Bool	use_targetids,
		MLDISTS **	mldistances
	)

initializes multi-level distances structure

Parameters

scip	SCIP
maxnlevels	maximum number of levels that can be handled
maxnslots	maximum number of of slots (per level) that can be handled
maxntargets	maximum number of of targets (per slot) that can be handled
emptyslot_nbuffers	buffer entries for empty slot (dists and IDs array is that much longer)
use_targetids	use target IDs?
mldistances	to be initialized

Definition at line 291 of file extreduce_mldists.c.

References multi_level_distances_storage::base_ids, multi_level_distances_storage::emptyslot_number, multi_level_distances_storage::level_basestart, multi_level_distances_storage::level_maxnslots, multi_level_distances_storage::level_maxntargets, multi_level_distances_storage::level_ntargets, multi_level_distances_storage::level_targetstart, multi_level_distances_storage::maxnlevels, multi_level_distances_storage::maxnslots, multi_level_distances_storage::maxntargets, MLDISTS_EMPTYSLOT_NONE, multi_level_distances_storage::nlevels, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, multi_level_distances_storage::target_dists, multi_level_distances_storage::target_ids, and multi_level_distances_storage::target_withids.

Referenced by extreduce_extPermaAddMLdistsbiased(), extreduce_extPermaInit(), and testMldistsBuilding().

extreduce_mldistsFree()

void extreduce_mldistsFree	(	SCIP *	scip,
		MLDISTS **	mldistances
	)

frees multi-level distances structure

Parameters

scip	SCIP
mldistances	to be freed

Definition at line 344 of file extreduce_mldists.c.

References multi_level_distances_storage::base_ids, multi_level_distances_storage::level_basestart, multi_level_distances_storage::level_ntargets, multi_level_distances_storage::level_targetstart, SCIPfreeMemory, SCIPfreeMemoryArray, multi_level_distances_storage::target_dists, multi_level_distances_storage::target_ids, and multi_level_distances_storage::target_withids.

Referenced by extreduce_extPermaFree(), and testMldistsBuilding().

extreduce_mldistsIsEmpty()

SCIP_Bool extreduce_mldistsIsEmpty

(

const MLDISTS *

mldists

)

empty?

Parameters

mldists

multi-level distances

Definition at line 372 of file extreduce_mldists.c.

References multi_level_distances_storage::nlevels.

Referenced by extreduce_extPermaIsClean(), extreduce_mldistsLevelCloseTop(), extreduce_mldistsLevelReopenTop(), and testMldistsBuilding().

extreduce_mldistsEmptySlotExists()

SCIP_Bool extreduce_mldistsEmptySlotExists

(

const MLDISTS *

mldists

)

does an empty slot exits? (on current level)

Parameters

mldists

multi-level distances

Definition at line 383 of file extreduce_mldists.c.

References multi_level_distances_storage::emptyslot_number, and MLDISTS_EMPTYSLOT_NONE.

Referenced by extreduce_mldistsEmptySlotLevel(), extreduce_mldistsEmptySlotReset(), extreduce_mldistsEmptySlotSetBase(), extreduce_mldistsEmptySlotSetFilled(), extreduce_mldistsLevelAddTop(), extreduce_mldistsLevelCloseTop(), extreduce_mldistsLevelRemoveTop(), extreduce_mldistsLevelRemoveTopNonClosed(), extreduce_mldistsLevelReopenTop(), extreduce_mstInternalsInSync(), mldistsGetPosBase(), mldistsGetPosEmptyTargetsStart(), and mstLevelHorizontalAddSds().

extreduce_mldistsEmptySlotTargetIds()

int* extreduce_mldistsEmptySlotTargetIds

(

const MLDISTS *

mldists

)

gets targets IDs memory from clean slot (to be filled in)

Parameters

mldists

multi-level distances

Definition at line 395 of file extreduce_mldists.c.

References multi_level_distances_storage::level_ntargets, mldistsGetPosEmptyTargetsStart(), mldistsGetTopLevel(), STP_MLDISTS_ID_UNSET, multi_level_distances_storage::target_ids, and multi_level_distances_storage::target_withids.

Referenced by mstLevelHorizontalAddSds(), and mstLevelLeafSetVerticalSDsBoth().

extreduce_mldistsEmptySlotTargetIdsDirty()

int* extreduce_mldistsEmptySlotTargetIdsDirty

(

const MLDISTS *

mldists

)

gets targets IDs memory from clean slot (to be filled in)

Parameters

mldists

multi-level distances

Definition at line 418 of file extreduce_mldists.c.

References mldistsGetPosEmptyTargetsStart(), and multi_level_distances_storage::target_ids.

Referenced by mstLevelLeafAdjustVerticalSDs().

extreduce_mldistsEmptySlotTargetDists()

SCIP_Real* extreduce_mldistsEmptySlotTargetDists

(

const MLDISTS *

mldists

)

Gets targets distances memory from clean slot (to be filled in). NOTE: Can only be called as long as this empty slots' distances have not not modified!

Parameters

mldists

multi-level distances

Definition at line 432 of file extreduce_mldists.c.

References EQ, multi_level_distances_storage::level_ntargets, mldistsGetPosEmptyTargetsStart(), mldistsGetTopLevel(), STP_MLDISTS_DIST_UNSET, and multi_level_distances_storage::target_dists.

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

extreduce_mldistsEmptySlotTargetDistsDirty()

SCIP_Real* extreduce_mldistsEmptySlotTargetDistsDirty

(

const MLDISTS *

mldists

)

Gets targets distances memory from empty slot. NOTE: This method does not make sure that the distances are clean! (i.e. not already set)

Parameters

mldists

multi-level distances

Definition at line 454 of file extreduce_mldists.c.

References mldistsGetPosEmptyTargetsStart(), and multi_level_distances_storage::target_dists.

Referenced by mstLevelLeafAdjustVerticalSDs(), and mstLevelLeafTryExtMst().

extreduce_mldistsEmptySlotLevel()

int extreduce_mldistsEmptySlotLevel

(

const MLDISTS *

mldists

)

gets level of current empty slot

Parameters

mldists

multi-level distances

Definition at line 466 of file extreduce_mldists.c.

References extreduce_mldistsEmptySlotExists(), and mldistsGetTopLevel().

extreduce_mldistsEmptySlotSetBase()

void extreduce_mldistsEmptySlotSetBase	(	int	baseid,
		MLDISTS *	mldists
	)

sets base of empty slot

Parameters

baseid	base
mldists	multi-level distances

Definition at line 477 of file extreduce_mldists.c.

References multi_level_distances_storage::base_ids, multi_level_distances_storage::emptyslot_number, extreduce_mldistsEmptySlotExists(), multi_level_distances_storage::level_basestart, multi_level_distances_storage::maxnslots, mldistsGetTopLevel(), STP_MLDISTS_ID_EMPTY, and STP_MLDISTS_ID_UNSET.

Referenced by extreduce_mldistsLevelAddAndCloseEmpty(), extreduce_mldistsLevelAddAndCloseRoot(), mstLevelHorizontalAddSds(), mstLevelLeafInit(), and testMldistsBuilding().

extreduce_mldistsEmptySlotReset()

void extreduce_mldistsEmptySlotReset

(

MLDISTS *

mldists

)

Resets all changes (especially bases) of empty slot. NOTE: Assumes that at least the basis of the slot has been set

Parameters

mldists

multi-level distances

Definition at line 496 of file extreduce_mldists.c.

References multi_level_distances_storage::base_ids, multi_level_distances_storage::emptyslot_number, extreduce_mldistsEmptySlotExists(), multi_level_distances_storage::level_basestart, multi_level_distances_storage::level_ntargets, multi_level_distances_storage::maxnslots, mldistsGetPosEmptyTargetsStart(), mldistsGetTopLevel(), STP_MLDISTS_DIST_UNSET, STP_MLDISTS_ID_UNSET, multi_level_distances_storage::target_dists, multi_level_distances_storage::target_ids, and multi_level_distances_storage::target_withids.

Referenced by mstLevelLeafExit().

extreduce_mldistsEmptySlotSetFilled()

void extreduce_mldistsEmptySlotSetFilled

(

MLDISTS *

mldists

)

marks current empty slot as filled

Parameters

mldists

multi-level distances

Definition at line 534 of file extreduce_mldists.c.

References multi_level_distances_storage::base_ids, multi_level_distances_storage::emptyslot_number, extreduce_mldistsEmptySlotExists(), extreduce_mldistsLevelNSlots(), multi_level_distances_storage::level_basestart, MLDISTS_EMPTYSLOT_NONE, mldistsGetTopLevel(), and STP_MLDISTS_ID_UNSET.

Referenced by extreduce_mldistsLevelAddAndCloseEmpty(), extreduce_mldistsLevelAddAndCloseRoot(), mstLevelHorizontalAddSds(), mstLevelLeafExit(), and testMldistsBuilding().

extreduce_mldistsLevelAddTop()

void extreduce_mldistsLevelAddTop	(	int	nslots,
		int	nslottargets,
		MLDISTS *	mldists
	)

adds another level of slots at top

Parameters

nslots	number of slots per this level
nslottargets	number of targets per slot
mldists	multi-level distances

Definition at line 562 of file extreduce_mldists.c.

References multi_level_distances_storage::emptyslot_number, extreduce_mldistsEmptySlotExists(), multi_level_distances_storage::level_basestart, multi_level_distances_storage::level_maxnslots, multi_level_distances_storage::level_maxntargets, multi_level_distances_storage::level_ntargets, multi_level_distances_storage::level_targetstart, multi_level_distances_storage::maxnlevels, mldistsTopLevelUnset(), and multi_level_distances_storage::nlevels.

Referenced by extreduce_mldistsLevelAddAndCloseEmpty(), extreduce_mldistsLevelAddAndCloseRoot(), extreduce_mstLevelInitialInit(), mstLevelHorizontalAddSds(), and testMldistsBuilding().

extreduce_mldistsLevelCloseTop()

void extreduce_mldistsLevelCloseTop

(

MLDISTS *

mldists

)

closes the top level for further extensions

Parameters

mldists

multi-level distances

Definition at line 625 of file extreduce_mldists.c.

References multi_level_distances_storage::emptyslot_number, extreduce_mldistsEmptySlotExists(), extreduce_mldistsIsEmpty(), multi_level_distances_storage::level_basestart, multi_level_distances_storage::level_ntargets, multi_level_distances_storage::level_targetstart, MLDISTS_EMPTYSLOT_NONE, and multi_level_distances_storage::nlevels.

Referenced by extreduce_mldistsLevelAddAndCloseEmpty(), extreduce_mldistsLevelAddAndCloseRoot(), and extreduce_mstLevelVerticalClose().

extreduce_mldistsLevelAddAndCloseEmpty()

void extreduce_mldistsLevelAddAndCloseEmpty	(	int	nslottargets,
		MLDISTS *	mldists
	)

adds dummy level

Parameters

nslottargets	number of targets per slot
mldists	multi-level distances

Definition at line 594 of file extreduce_mldists.c.

References extreduce_mldistsEmptySlotSetBase(), extreduce_mldistsEmptySlotSetFilled(), extreduce_mldistsLevelAddTop(), extreduce_mldistsLevelCloseTop(), and STP_MLDISTS_ID_EMPTY.

Referenced by extreduce_mstLevelHorizontalAddEmpty(), and extreduce_mstLevelVerticalAddEmpty().

extreduce_mldistsLevelAddAndCloseRoot()

void extreduce_mldistsLevelAddAndCloseRoot	(	int	base,
		MLDISTS *	mldists
	)

adds root level of slots

Parameters

base	the base
mldists	multi-level distances

Definition at line 609 of file extreduce_mldists.c.

References extreduce_mldistsEmptySlotSetBase(), extreduce_mldistsEmptySlotSetFilled(), extreduce_mldistsLevelAddTop(), and extreduce_mldistsLevelCloseTop().

Referenced by mstAddRootLevelSDs().

extreduce_mldistsLevelReopenTop()

void extreduce_mldistsLevelReopenTop

(

MLDISTS *

mldists

)

reopens top level for one further extensions

Parameters

mldists

multi-level distances

Definition at line 656 of file extreduce_mldists.c.

References multi_level_distances_storage::base_ids, multi_level_distances_storage::emptyslot_number, extreduce_mldistsEmptySlotExists(), extreduce_mldistsIsEmpty(), multi_level_distances_storage::level_basestart, multi_level_distances_storage::level_ntargets, multi_level_distances_storage::level_targetstart, multi_level_distances_storage::maxnlevels, multi_level_distances_storage::nlevels, STP_MLDISTS_DIST_UNSET, STP_MLDISTS_ID_UNSET, multi_level_distances_storage::target_dists, multi_level_distances_storage::target_ids, and multi_level_distances_storage::target_withids.

Referenced by extreduce_mstLevelVerticalReopen().

extreduce_mldistsLevelRemoveTop()

void extreduce_mldistsLevelRemoveTop

(

MLDISTS *

mldists

)

removes top level of slots

Parameters

mldists

multi-level distances

Definition at line 695 of file extreduce_mldists.c.

References extreduce_mldistsEmptySlotExists(), mldistsTopLevelUnset(), and multi_level_distances_storage::nlevels.

Referenced by extreduce_mstLevelHorizontalRemove(), extreduce_mstLevelRemove(), extreduce_mstLevelVerticalRemove(), postCleanSDs(), and testMldistsBuilding().

extreduce_mldistsLevelRemoveTopNonClosed()

void extreduce_mldistsLevelRemoveTopNonClosed

(

MLDISTS *

mldists

)

removes top level of slots, which is not yet closed

Parameters

mldists

multi-level distances

Definition at line 712 of file extreduce_mldists.c.

References multi_level_distances_storage::emptyslot_number, extreduce_mldistsEmptySlotExists(), MLDISTS_EMPTYSLOT_NONE, mldistsTopLevelUnset(), and multi_level_distances_storage::nlevels.

extreduce_mldistsLevelNTargets()

int extreduce_mldistsLevelNTargets	(	const MLDISTS *	mldists,
		int	level
	)

gets number of targets (per slots) for given level

Parameters

mldists	multi-level distances
level	level

Definition at line 730 of file extreduce_mldists.c.

References multi_level_distances_storage::level_maxntargets, multi_level_distances_storage::level_ntargets, and mldistsGetTopLevel().

Referenced by baseMstInitMsts(), compRootDistsUpdateLeavesDists(), and extreduce_mldistsLevelNTopTargets().

extreduce_mldistsLevelNTopTargets()

int extreduce_mldistsLevelNTopTargets

(

const MLDISTS *

mldists

)

gets number of targets (per slots) for top level

Parameters

mldists

multi-level distances

Definition at line 743 of file extreduce_mldists.c.

References extreduce_mldistsLevelNTargets(), and mldistsGetTopLevel().

Referenced by compMstInitMsts(), compUpDistUpdateLeavesDists(), extreduce_mstLevelVerticalReopen(), mstCompLeafGetSDsToAncestors(), mstCompLeafGetSDsToSiblings(), and mstCompLeafToAncestorsBiasedRuleOut().

extreduce_mldistsLevelNSlots()

int extreduce_mldistsLevelNSlots	(	const MLDISTS *	mldists,
		int	level
	)

gets number of slots for given level

Parameters

mldists	multi-level distances
level	level

Definition at line 754 of file extreduce_mldists.c.

References multi_level_distances_storage::level_basestart, multi_level_distances_storage::level_maxnslots, and mldistsGetTopLevel().

Referenced by extreduce_mldistsEmptySlotSetFilled(), extreduce_mldistsTopLevelNSlots(), and extreduce_mstLevelVerticalClose().

extreduce_mldistsNlevels()

int extreduce_mldistsNlevels

(

const MLDISTS *

mldists

)

gets number of levels

Parameters

mldists

multi-level distances

Definition at line 778 of file extreduce_mldists.c.

References multi_level_distances_storage::nlevels.

Referenced by extreduce_extPermaIsClean(), extreduce_mstInternalsInSync(), extreduce_mstLevelHorizontalRemove(), extreduce_mstLevelRemove(), extreduce_mstLevelVerticalRemove(), and postCleanSDs().

extreduce_mldistsTopLevel()

int extreduce_mldistsTopLevel

(

const MLDISTS *

mldists

)

gets top level

Parameters

mldists

multi-level distances

Definition at line 790 of file extreduce_mldists.c.

References multi_level_distances_storage::nlevels.

Referenced by baseMstInitExtComp(), baseMstInitMsts(), compMstInitExtComp(), extreduce_mldistsTopLevelNSlots(), extreduce_mstLevelClose(), extreduce_mstLevelHorizontalAdd(), extreduce_mstLevelHorizontalAddEmpty(), extreduce_mstLevelInitialInit(), extreduce_mstLevelVerticalAddEmpty(), extreduce_mstLevelVerticalClose(), extreduce_mstLevelVerticalReopen(), extStackTopCollectExtEdges(), mstAddRootLevelSDs(), and mstLevelHorizontalAddSds().

extreduce_mldistsTopLevelBases()

const int* extreduce_mldistsTopLevelBases

(

const MLDISTS *

mldists

)

gets top level bases

Parameters

mldists

multi-level distances

Definition at line 802 of file extreduce_mldists.c.

References multi_level_distances_storage::base_ids, mldistsGetPosBasesStart(), and mldistsGetTopLevel().

Referenced by extreduce_printTopLevel().

extreduce_mldistsTopLevelNSlots()

int extreduce_mldistsTopLevelNSlots

(

const MLDISTS *

mldists

)

gets number of slots for top level

Parameters

mldists

multi-level distances

Definition at line 769 of file extreduce_mldists.c.

References extreduce_mldistsLevelNSlots(), and extreduce_mldistsTopLevel().

Referenced by extreduce_mstInternalsInSync(), extreduce_mstLevelClose(), and extreduce_printTopLevel().

extreduce_mldistsLevelContainsBase()

SCIP_Bool extreduce_mldistsLevelContainsBase	(	const MLDISTS *	mldists,
		int	level,
		int	baseid
	)

is the base contained in a slot of the given level?

Parameters

mldists	multi-level distances
level	level
baseid	the base id

Definition at line 814 of file extreduce_mldists.c.

References mldistsGetPosBase(), and mldistsGetTopLevel().

Referenced by extStackTopCollectExtEdges(), and mldistsGetPosTargetsStart().

extreduce_mldistsTargetIds()

const int* extreduce_mldistsTargetIds	(	const MLDISTS *	mldists,
		int	level,
		int	baseid
	)

gets targets ids

Parameters

mldists	multi-level distances
level	level
baseid	the base

Definition at line 829 of file extreduce_mldists.c.

References mldistsGetPosTargetsStart(), multi_level_distances_storage::target_ids, and multi_level_distances_storage::target_withids.

Referenced by compRootDistsUpdateLeavesDists(), and extreduce_mldistsTopTargetIds().

extreduce_mldistsTargetDists()

const SCIP_Real* extreduce_mldistsTargetDists	(	const MLDISTS *	mldists,
		int	level,
		int	baseid
	)

gets targets distances

Parameters

mldists	multi-level distances
level	level
baseid	the base

Definition at line 845 of file extreduce_mldists.c.

References mldistsGetPosTargetsStart(), and multi_level_distances_storage::target_dists.

Referenced by baseMstGetAdjcosts(), and compRootDistsUpdateLeavesDists().

extreduce_mldistsTargetDist()

SCIP_Real extreduce_mldistsTargetDist	(	const MLDISTS *	mldists,
		int	level,
		int	baseid,
		int	targetid
	)

gets (one!) target distance for given level, target ID and base ID

Parameters

mldists	multi-level distances
level	level
baseid	the base
targetid	the identifier

Definition at line 904 of file extreduce_mldists.c.

References GE, mldistsGetPosTargets(), mldistsGetTopLevel(), and multi_level_distances_storage::target_dists.

Referenced by baseMstGetAdjcosts().

extreduce_mldistsTopTargetIds()

const int* extreduce_mldistsTopTargetIds	(	const MLDISTS *	mldists,
		int	baseid
	)

Gets targets ids

Parameters

mldists	multi-level distances
baseid	the base

Definition at line 863 of file extreduce_mldists.c.

References extreduce_mldistsTargetIds(), and mldistsGetTopLevel().

Referenced by compUpDistUpdateLeavesDists(), and extreduce_sdsverticalInSync().

extreduce_mldistsTopTargetDists()

const SCIP_Real* extreduce_mldistsTopTargetDists	(	const MLDISTS *	mldists,
		int	baseid
	)

gets targets distances

Parameters

mldists	multi-level distances
baseid	the base

Definition at line 873 of file extreduce_mldists.c.

References mldistsGetPosTargetsStart(), mldistsGetTopLevel(), and multi_level_distances_storage::target_dists.

Referenced by compUpDistUpdateLeavesDists(), extreduce_sdsverticalInSync(), mst3LeafTreeGetSds(), mstCompLeafGetSDsToAncestors(), and mstCompLeafToAncestorsBiasedRuleOut().

extreduce_mldistsTopTargetDist()

SCIP_Real extreduce_mldistsTopTargetDist	(	const MLDISTS *	mldists,
		int	baseid,
		int	targetid
	)

gets (one!) target distance for given target ID and base ID

Parameters

mldists	multi-level distances
baseid	the base
targetid	the identifier

Definition at line 885 of file extreduce_mldists.c.

References GE, mldistsGetPosTargets(), mldistsGetTopLevel(), and multi_level_distances_storage::target_dists.

Referenced by extreduce_sdshorizontalInSync(), mst3LeafTreeGetSds(), mstCompLeafGetSDsToSiblings(), mstCompLeafToSiblingsBiasedRuleOut(), and mstLevelHorizontalAddSds().

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

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

SCIP_RETCODE extreduce_spgCheck3ComponentSimple	(	SCIP *	scip,
		const GRAPH *	graph,
		int	node,
		const EXTCOMP *	extcomp,
		SCIP_Bool	allowEquality,
		DISTDATA *	distdata,
		SCIP_Bool *	isPseudoDeletable
	)

checks component for possible pseudo-elimination by using simple Steiner tree

Parameters

scip	SCIP data structure
graph	graph data structure
node	the node
extcomp	component to be checked
allowEquality	allow equality?
distdata	data for distance computations
isPseudoDeletable	is component pseudo-deletable?

Definition at line 252 of file extreduce_extspg.c.

References initial_extension_component::compedges, initial_extension_component::comproot, GRAPH::cost, EQ, initial_extension_component::extleaves, FALSE, flipedge, GE, graph_edge_isInRange(), graph_knot_isInRange(), graph_pc_isPc(), GRAPH::head, Is_term, initial_extension_component::ncompedges, initial_extension_component::nextleaves, GRAPH::prize, SCIP_OKAY, SCIP_Real, spg3StarNeighborRuleOut(), GRAPH::tail, and GRAPH::term.

Referenced by extreduce_checkNode().

extreduce_spgCheck3NodeSimple()

SCIP_RETCODE extreduce_spgCheck3NodeSimple	(	SCIP *	scip,
		const GRAPH *	graph,
		int	node,
		DISTDATA *	distdata,
		SCIP_Bool *	isPseudoDeletable
	)

checks node of degree 3 for possible pseudo-elimination by using simple Steiner tree

Parameters

scip	SCIP data structure
graph	graph data structure
node	the node
distdata	data for distance computations
isPseudoDeletable	is node pseudo-deletable?

Definition at line 310 of file extreduce_extspg.c.

References GRAPH::cost, EAT_LAST, EQ, FALSE, flipedge, GRAPH::grad, graph_knot_isInRange(), GRAPH::head, Is_term, GRAPH::oeat, GRAPH::outbeg, SCIP_OKAY, SCIP_Real, spg3StarNeighborRuleOut(), GRAPH::term, and TRUE.

extreduce_spg3LeafTreeRuleOut()

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

can current 3-leaf tree be ruled-out?

Parameters

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

Definition at line 207 of file extreduce_extspg.c.

References extInitialCompIsEdge(), FALSE, GE, GRAPH::knots, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, spg4VerticesRuleOut(), extension_data::tree_leaves, extension_data::tree_nleaves, and TRUE.

Referenced by mstCompRuleOut().

extreduce_mstbiasedCheck3NodeSimple()

SCIP_RETCODE extreduce_mstbiasedCheck3NodeSimple	(	SCIP *	scip,
		const GRAPH *	graph,
		int	node,
		DISTDATA *	distdata_default,
		DISTDATA *	distdata_biased,
		SCIP_Bool *	isPseudoDeletable
	)

checks node of degree 3 for possible pseudo-elimination by using bias bottleneck Steiner distance

Parameters

scip	SCIP data structure
graph	graph data structure
node	the node
distdata_default	data for distance computations
distdata_biased	data for distance computations
isPseudoDeletable	is node pseudo-deletable?

Definition at line 226 of file extreduce_extmstbiased.c.

References GRAPH::cost, EAT_LAST, EQ, extreduce_distDataGetSdDouble(), FALSE, flipedge, GRAPH::grad, graph_knot_isInRange(), graph_pc_isPcMw(), GRAPH::head, Is_term, mst3StarNeighborRuleOut(), GRAPH::oeat, GRAPH::outbeg, reduce_sdprofitGetProfit(), SCIP_OKAY, SCIP_Real, distance_data::sdistdata, special_distance_storage::sdprofit, GRAPH::term, and TRUE.

Referenced by pseudodeleteExecute(), and testNode3PseudoDeletedBySdBiasedSimple().

extreduce_mstbiased3LeafTreeRuleOut()

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

can current 3-leaf tree be ruled-out?

Parameters

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

Definition at line 182 of file extreduce_extmstbiased.c.

References extension_data::distdata, extension_data::distdata_biased, EQ, extreduce_distDataGetSdDouble(), FALSE, GE, mst3LeafTreeGetSds(), mst3StarNeighborRuleOut(), ruledOut(), SCIP_Bool, SCIP_Real, SCIPdebugMessage, extension_data::tree_leaves, extension_data::tree_nleaves, and TRUE.

Referenced by mstCompRuleOut().

extreduce_bottleneckMarkRootPath()

void extreduce_bottleneckMarkRootPath	(	const GRAPH *	graph,
		int	vertex,
		EXTDATA *	extdata
	)

marks bottleneck array on path to tree root

Parameters

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

Definition at line 354 of file extreduce_bottleneck.c.

References extInitialCompIsEdge(), extInitialCompIsGenStar(), graph_pc_isPc(), graph_pc_knotIsDummyTerm(), graph_pc_termIsNonLeafTerm(), Is_term, GRAPH::prize, SCIP_Bool, SCIP_Real, GRAPH::term, extension_data::tree_bottleneckDistNode, extension_data::tree_deg, extension_data::tree_parentEdgeCost, extension_data::tree_parentNode, extension_data::tree_root, and extension_data::tree_starcenter.

Referenced by dbgBottleneckFromLeafIsDominated(), mstCompLeafGetSDsToAncestors(), mstCompLeafGetSDsToSiblings(), mstCompLeafToAncestorsBiasedRuleOut(), and mstLevelLeafInit().

extreduce_bottleneckUnmarkRootPath()

void extreduce_bottleneckUnmarkRootPath	(	const GRAPH *	graph,
		int	vertex,
		EXTDATA *	extdata
	)

unmarks bottleneck array on path to tree root

Parameters

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

Definition at line 422 of file extreduce_bottleneck.c.

References SCIP_Real, extension_data::tree_bottleneckDistNode, extension_data::tree_deg, extension_data::tree_parentNode, and extension_data::tree_root.

Referenced by dbgBottleneckFromLeafIsDominated(), mstCompLeafGetSDsToAncestors(), mstCompLeafGetSDsToSiblings(), mstCompLeafToAncestorsBiasedRuleOut(), and mstLevelLeafExit().

extreduce_bottleneckIsDominated()

SCIP_Bool extreduce_bottleneckIsDominated	(	SCIP *	scip,
		const GRAPH *	graph,
		int	vertex_pathmarked,
		int	vertex_unmarked,
		SCIP_Real	specialDist,
		int	edge_forbidden,
		EXTDATA *	extdata
	)

Does a special distance approximation dominate the tree bottleneck distance between vertex_pathmarked and vertex_unmarked in the current tree. NOTE: makes additional checks in case of equality

Parameters

scip	SCIP
graph	graph data structure
vertex_pathmarked	vertex for which bottleneck path to root has been marked
vertex_unmarked	second vertex
specialDist	best computed special distance approximation (-1.0 if unknown)
edge_forbidden	forbidden edge
extdata	extension data

Definition at line 464 of file extreduce_bottleneck.c.

References bottleneckGetDist(), bottleneckIsEqualityDominated(), bottleneckMarkEqualityEdges(), EQ, extreduce_extGetSdDouble(), extSdIsNonTrivial(), FALSE, graph_knot_isInRange(), LE, LT, SCIP_Bool, SCIP_Real, SCIPdebugMessage, and TRUE.

Referenced by dbgBottleneckFromLeafIsDominated(), mstCompLeafGetSDsToAncestors(), and mstCompLeafGetSDsToSiblings().

extreduce_bottleneckIsDominatedBiased()

SCIP_Bool extreduce_bottleneckIsDominatedBiased	(	SCIP *	scip,
		const GRAPH *	graph,
		int	vertex_pathmarked,
		int	vertex_unmarked,
		SCIP_Real	specialDistBiased,
		EXTDATA *	extdata
	)

As above, but for biased special distance

Parameters

scip	SCIP
graph	graph data structure
vertex_pathmarked	vertex for which bottleneck path to root has been marked
vertex_unmarked	second vertex
specialDistBiased	best computed special distance approximation (-1.0 if unknown)
extdata	extension data

Definition at line 520 of file extreduce_bottleneck.c.

References bottleneckGetDist(), extSdIsNonTrivial(), FALSE, graph_knot_isInRange(), LT, SCIP_Bool, SCIP_Real, SCIPdebugMessage, and TRUE.

Referenced by mstCompLeafToAncestorsBiasedRuleOut().

extreduce_bottleneckWithExtedgeIsDominated()

SCIP_Bool extreduce_bottleneckWithExtedgeIsDominated	(	SCIP *	scip,
		const GRAPH *	graph,
		int	extedge,
		int	vertex_pathmarked,
		int	vertex_unmarked,
		SCIP_Real	specialDist,
		EXTDATA *	extdata
	)

Does a special distance approximation dominate the tree bottleneck distance of extension edge (i.e. its edge cost) or bottleneck distance between vertex_pathmarked and vertex_unmarked in the current tree. NOTE: makes additional checks in case of equality

Parameters

scip	SCIP
graph	graph data structure
extedge	edge along which we want to extend the tree
vertex_pathmarked	vertex for which bottleneck path to root has been marked
vertex_unmarked	second vertex
specialDist	best computed special distance approximation (-1.0 if unknown)
extdata	extension data

Definition at line 561 of file extreduce_bottleneck.c.

References bottleneckGetDist(), bottleneckIsEqualityDominated(), bottleneckMarkEqualityEdge(), bottleneckMarkEqualityEdges(), GRAPH::cost, EQ, extreduce_extGetSdDouble(), extSdIsNonTrivial(), FALSE, graph_edge_isInRange(), GRAPH::head, LE, LT, SCIP_Bool, SCIP_Real, SCIPdebugMessage, GRAPH::tail, and TRUE.

Referenced by extreduce_bottleneckCheckNonLeaves(), extreduce_bottleneckCheckNonLeaves_pc(), and mstLevelLeafSetVerticalSDsBoth().

extreduce_bottleneckWithExtedgeIsDominatedBiased()

SCIP_Bool extreduce_bottleneckWithExtedgeIsDominatedBiased	(	SCIP *	scip,
		const GRAPH *	graph,
		int	extedge,
		int	vertex_pathmarked,
		int	vertex_unmarked,
		SCIP_Real	specialDistBiased,
		EXTDATA *	extdata
	)

as above, but for biased special distance

Parameters

scip	SCIP
graph	graph data structure
extedge	edge along which we want to extend the tree
vertex_pathmarked	vertex for which bottleneck path to root has been marked
vertex_unmarked	second vertex
specialDistBiased	best computed biased special distance approximation (-1.0 if unknown)
extdata	extension data

Definition at line 640 of file extreduce_bottleneck.c.

References bottleneckGetDist(), GRAPH::cost, extSdIsNonTrivial(), FALSE, graph_edge_isInRange(), LT, SCIP_Bool, SCIP_Real, SCIPdebugMessage, GRAPH::tail, and TRUE.

Referenced by mstLevelLeafSetVerticalSDsBoth().

extreduce_bottleneckToSiblingIsDominated()

SCIP_Bool extreduce_bottleneckToSiblingIsDominated	(	SCIP *	scip,
		const GRAPH *	graph,
		int	extedge,
		int	edge2sibling,
		SCIP_Real	specialDist,
		EXTDATA *	extdata
	)

Does a special distance approximation dominate the tree bottleneck distance between vertex_pathmarked and vertex_unmarked in the current tree? NOTE: makes additional checks in case of equality

Parameters

scip	SCIP
graph	graph data structure
extedge	edge for extension
edge2sibling	edge to sibling of extedge head
specialDist	best computed special distance approximation (FARAWAY if unknown)
extdata	extension data

Definition at line 683 of file extreduce_bottleneck.c.

References bottleneckIsEqualityDominated(), bottleneckMarkEqualityEdge(), GRAPH::cost, FALSE, FARAWAY, GE, GRAPH::head, LE, LT, SCIP_Bool, SCIP_Real, SCIPdebugMessage, GRAPH::tail, and TRUE.

Referenced by mstCompLeafGetSDsToSiblings().

extreduce_bottleneckToSiblingIsDominatedBiased()

SCIP_Bool extreduce_bottleneckToSiblingIsDominatedBiased	(	SCIP *	scip,
		const GRAPH *	graph,
		int	extedge,
		int	edge2sibling,
		SCIP_Real	specialDistBiased,
		EXTDATA *	extdata
	)

as above, but for biased special distance

Parameters

scip	SCIP
graph	graph data structure
extedge	edge for extension
edge2sibling	edge to sibling of extedge head
specialDistBiased	best computed special distance approximation (FARAWAY if unknown)
extdata	extension data

Definition at line 751 of file extreduce_bottleneck.c.

References GRAPH::cost, FALSE, FARAWAY, GE, LT, SCIP_Bool, SCIP_Real, GRAPH::tail, and TRUE.

Referenced by mstCompLeafToSiblingsBiasedRuleOut().

extreduce_bottleneckCheckNonLeaves_pc()

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

checks tree bottleneck distances to non-leaves of the tree that were marked before

Parameters

scip	SCIP
graph	graph data structure
edge2neighbor	the edge from the tree to the neighbor
extdata	extension data
ruledOut	could the extension be ruled out

Definition at line 787 of file extreduce_bottleneck.c.

References extreduce_bottleneckWithExtedgeIsDominated(), extreduce_extGetSd(), GRAPH::head, pcmw_specific_data::nPcSdCands, extension_data::pcdata, pcmw_specific_data::pcSdCands, SCIP_Real, SCIPdebugMessage, GRAPH::tail, extension_data::tree_deg, and TRUE.

Referenced by extreduce_mstLevelVerticalAddLeaf().

extreduce_bottleneckCheckNonLeaves()

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

checks tree bottleneck distances to non-leaves of the tree

Parameters

scip	SCIP
graph	graph data structure
edge2neighbor	the edge from the tree to the neighbor
extdata	extension data
ruledOut	could the extension be ruled out

Definition at line 833 of file extreduce_bottleneck.c.

References extreduce_bottleneckWithExtedgeIsDominated(), extreduce_extGetSd(), graph_knot_isInRange(), GRAPH::head, SCIP_Real, SCIPdebugMessage, GRAPH::tail, extension_data::tree_deg, extension_data::tree_innerNodes, extension_data::tree_ninnerNodes, and TRUE.

Referenced by extreduce_mstLevelVerticalAddLeaf().

extreduce_redcostAddEdge()

void extreduce_redcostAddEdge	(	const GRAPH *	graph,
		int	edge,
		REDDATA *	reddata,
		EXTDATA *	extdata
	)

Updates reduced cost for added edge. NOTE: call extreduce_redcostInitExpansion before each new expansion!

Parameters

graph	graph data structure
edge	edge to be added
reddata	reduction data
extdata	extension data

Definition at line 571 of file extreduce_redcosts.c.

References reduction_data::edgedeleted, GRAPH::edges, extIsAtInitialGenStar(), extIsAtInitialStar(), FARAWAY, flipedge, GRAPH::head, GRAPH::knots, LT, nnodes, reduction_data::redcost_nlevels, reduction_data::redcost_noReversedTree, reduction_data::redcost_treecosts, reduction_data::redcost_treenodeswaps, extension_data::redcostdata, redcosts_getEdgeCosts(), redcosts_getNedges(), redcosts_getNnodes(), SCIP_Bool, SCIP_Real, GRAPH::tail, extension_data::tree_nDelUpArcs, extension_data::tree_starcenter, and TRUE.

Referenced by extTreeStackTopAdd().

extreduce_redcostRemoveEdge()

void extreduce_redcostRemoveEdge	(	int	edge,
		const REDDATA *	reddata,
		EXTDATA *	extdata
	)

update reduced cost for removed edge

Parameters

edge	edge to be added
reddata	reduction data
extdata	extension data

Definition at line 635 of file extreduce_redcosts.c.

References reduction_data::edgedeleted, FARAWAY, LT, reduction_data::redcost_nlevels, reduction_data::redcost_treecosts, extension_data::redcostdata, redcosts_getEdgeCosts(), redcosts_getNedges(), SCIP_Bool, SCIP_Real, and extension_data::tree_nDelUpArcs.

Referenced by extTreeStackTopRemove().

extreduce_redcostTreeRecompute()

void extreduce_redcostTreeRecompute	(	SCIP *	scip,
		const GRAPH *	graph,
		EXTDATA *	extdata
	)

recomputes reduced cost tree information

Parameters

scip	SCIP
graph	graph data structure
extdata	extension data

Definition at line 495 of file extreduce_redcosts.c.

References reduction_data::edgedeleted, GRAPH::edges, extreduce_treeIsFlawed(), FARAWAY, graph_edge_isInRange(), LT, reduction_data::redcost_nlevels, reduction_data::redcost_treecosts, extension_data::redcostdata, redcosts_getEdgeCosts(), redcosts_getNedges(), extension_data::reddata, SCIP_Bool, SCIP_CALL_ABORT, SCIP_Real, SCIPallocBlockMemoryArray, SCIPfreeBlockMemoryArray, SCIPisEQ(), extension_data::tree_edges, and extension_data::tree_nedges.

Referenced by extreduce_treeRecompCosts().

extreduce_redcostInitExpansion()

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

NOTE: call before adding edges for new expansion!

Parameters

graph	graph data structure
extdata	extension data

Definition at line 548 of file extreduce_redcosts.c.

References extStackGetTopRoot(), FARAWAY, GE, GRAPH::knots, nnodes, reduction_data::redcost_nlevels, reduction_data::redcost_noReversedTree, reduction_data::redcost_treenodeswaps, extension_data::redcostdata, redcosts_getRoot(), extension_data::reddata, SCIP_Bool, SCIP_Real, and extension_data::tree_root.

Referenced by extTreeStackTopAdd().

extreduce_redcostRuleOutPeriph()

SCIP_Bool extreduce_redcostRuleOutPeriph	(	const GRAPH *	graph,
		EXTDATA *	extdata
	)

Can current tree be peripherally ruled out by using reduced costs arguments?

Parameters

graph	graph data structure
extdata	extension data

Definition at line 665 of file extreduce_redcosts.c.

References extTreeRedcostCutoff(), FALSE, reduction_data::redcost_nlevels, extension_data::reddata, extension_data::tree_leaves, extension_data::tree_nleaves, extension_data::tree_root, and TRUE.

Referenced by extTreeRuleOutPeriph().

extreduce_extCompClean()

void extreduce_extCompClean	(	SCIP *	scip,
		const GRAPH *	graph,
		const EXTCOMP *	extcomp,
		SCIP_Bool	unhash,
		EXTDATA *	extdata
	)

cleans-up after trying to rule out a component

Parameters

scip	SCIP
graph	graph data structure
extcomp	component to be cleaned for
unhash	unhash component?
extdata	extension data

Definition at line 76 of file extreduce_data.c.

References initial_extension_component::compedges, extInitialCompIsGenStar(), extReddataHasBiasedSds(), extreduce_extdataClean(), extreduce_extdataIsClean(), extreduce_pcdataClean(), extreduce_pcdataIsClean(), extreduce_reddataClean(), extreduce_reddataIsClean(), FALSE, initial_extension_component::genstar_centeredge, graph_edge_isInRange(), graph_pseudoAncestors_unhashEdge(), GRAPH::head, reduction_data::msts_comp, reduction_data::msts_levelbase, initial_extension_component::ncompedges, extension_data::pcdata, postCleanMSTs(), postCleanSDs(), reduction_data::pseudoancestor_mark, GRAPH::pseudoancestors, extension_data::reddata, SCIP_Bool, extension_data::sdeq_edgesIsForbidden, extension_data::sdeq_hasForbiddenEdges, reduction_data::sds_horizontal, reduction_data::sds_vertical, reduction_data::sdsbias_horizontal, reduction_data::sdsbias_vertical, STP_Vectype, StpVecFree, StpVecGetSize, GRAPH::tail, and extension_data::tree_deg.

Referenced by extProcessComponent().

extreduce_extPermaInit()

SCIP_RETCODE extreduce_extPermaInit	(	SCIP *	scip,
		enum EXTRED_MODE	mode,
		const GRAPH *	graph,
		STP_Bool *	edgedeleted,
		EXTPERMA **	extpermanent
	)

initialize permanent extension data struct NOTE: Sets distdata and reddata entries to NULL, since non-owned

Parameters

scip	SCIP
mode	mode
graph	graph data structure
edgedeleted	edge array to mark which directed edge can be removed
extpermanent	(uninitialized) extension data

Definition at line 162 of file extreduce_data.c.

References extension_data_permanent::bottleneckDistNode, extension_data_permanent::contration, extension_data_permanent::dcmst, extension_data_permanent::distdata_biased, extension_data_permanent::distdata_default, extension_data_permanent::edgedeleted, extred_fast, extred_full, extreduce_contractionInit(), extreduce_extPermaIsClean(), extreduce_getMaxTreeDepth(), extreduce_mldistsInit(), FALSE, graph_csrdepo_init(), graph_get_nNodes(), graph_getIsTermArray(), graph_pc_isPcMw(), extension_data_permanent::isterm, GRAPH::mark, extension_data_permanent::mode, extension_data_permanent::msts_comp, extension_data_permanent::msts_levelbase, nnodes, extension_data_permanent::nnodes, NULL, extension_data_permanent::pcSdToNode, extension_data_permanent::randnumgen, extension_data_permanent::redcostdata, extension_data_permanent::redcostEqualAllow, reduce_dcmstInit(), reduce_impliedNodesGet(), extension_data_permanent::result, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemory, SCIPallocMemoryArray, extension_data_permanent::sds_horizontal, extension_data_permanent::sds_vertical, extension_data_permanent::sdsbias_horizontal, extension_data_permanent::sdsbias_vertical, extension_data_permanent::solIsValid, STP_EXT_MAXDFSDEPTH, STP_EXT_MAXDFSDEPTH_GUARD, STP_EXT_MAXGRAD, STP_EXTTREE_MAXNEDGES, STP_EXTTREE_MAXNLEAVES, STP_EXTTREE_MAXNLEAVES_GUARD, STP_Vectype, extension_data_permanent::tree_deg, extension_data_permanent::tree_maxdepth, extension_data_permanent::tree_maxnedges, extension_data_permanent::tree_maxnleaves, TRUE, and extension_data_permanent::useSdBias.

Referenced by extCheckArc(), extCheckEdge(), extCheckNode(), extDeleteNodes(), extInit(), extreduce_init(), fixVarsRedbased(), and reduce_termsepaDa().

extreduce_extPermaAddRandnumgen()

void extreduce_extPermaAddRandnumgen	(	SCIP_RANDNUMGEN *	randnumgen,
		EXTPERMA *	extpermanent
	)

adds random number generator

Parameters

randnumgen	random number generator to add (NON-OWNED!)
extpermanent	(initialized) extension data

Definition at line 267 of file extreduce_data.c.

References extension_data_permanent::randnumgen.

Referenced by reduce_da().

extreduce_extPermaAddMLdistsbiased()

SCIP_RETCODE extreduce_extPermaAddMLdistsbiased	(	SCIP *	scip,
		EXTPERMA *	extpermanent
	)

adds biased ML distances containers

Parameters

scip	SCIP
extpermanent	(initialized) extension data

Definition at line 279 of file extreduce_data.c.

References extreduce_mldistsInit(), FALSE, SCIP_Bool, SCIP_CALL, SCIP_OKAY, extension_data_permanent::sdsbias_horizontal, extension_data_permanent::sdsbias_vertical, STP_EXT_MAXDFSDEPTH_GUARD, STP_EXT_MAXGRAD, STP_EXTTREE_MAXNLEAVES_GUARD, and TRUE.

Referenced by extreduce_pseudoDeleteNodes().

extreduce_extPermaIsClean()

SCIP_Bool extreduce_extPermaIsClean	(	const GRAPH *	graph,
		const EXTPERMA *	extperm
	)

initialize permanent extension data struct

Parameters

graph	graph data structure
extperm	extension data

Definition at line 305 of file extreduce_data.c.

References extension_data_permanent::bottleneckDistNode, extension_data_permanent::edgedeleted, EQ, extreduce_mldistsIsEmpty(), extreduce_mldistsNlevels(), FALSE, graph_csrdepo_isEmpty(), graph_get_nNodes(), extension_data_permanent::msts_comp, extension_data_permanent::msts_levelbase, nnodes, extension_data_permanent::nnodes, NULL, extension_data_permanent::pcSdToNode, SCIP_Real, SCIPdebugMessage, extension_data_permanent::sds_horizontal, extension_data_permanent::sds_vertical, extension_data_permanent::sdsbias_horizontal, extension_data_permanent::sdsbias_vertical, extension_data_permanent::tree_deg, and TRUE.

Referenced by extreduce_checkArc(), extreduce_checkComponent(), extreduce_checkEdge(), and extreduce_extPermaInit().

extreduce_extPermaFree()

void extreduce_extPermaFree	(	SCIP *	scip,
		EXTPERMA **	extpermanent
	)

frees extension data

Parameters

scip	SCIP
extpermanent	extension data

Definition at line 386 of file extreduce_data.c.

References extension_data_permanent::bottleneckDistNode, extension_data_permanent::contration, extension_data_permanent::dcmst, extreduce_contractionFree(), extreduce_mldistsFree(), graph_csrdepo_free(), extension_data_permanent::isterm, extension_data_permanent::msts_comp, extension_data_permanent::msts_levelbase, extension_data_permanent::nnodes, extension_data_permanent::pcSdToNode, reduce_dcmstFree(), SCIPfreeMemory, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, extension_data_permanent::sds_horizontal, extension_data_permanent::sds_vertical, extension_data_permanent::sdsbias_horizontal, extension_data_permanent::sdsbias_vertical, StpVecFree, and extension_data_permanent::tree_deg.

Referenced by extCheckArc(), extCheckEdge(), extCheckNode(), extDeleteNodes(), extFree(), extreduce_exit(), and fixVarsRedbased().

extreduce_extdataClean()

void extreduce_extdataClean

(

EXTDATA *

extdata

)

cleans extension data

Parameters

extdata

extension data

Definition at line 426 of file extreduce_data.c.

References extension_data::extstack_ncomponents, extension_data::ncostupdatestalls, extension_data::tree_cost, extension_data::tree_depth, extension_data::tree_nDelUpArcs, extension_data::tree_nedges, extension_data::tree_ninnerNodes, extension_data::tree_nleaves, extension_data::tree_root, and extension_data::tree_starcenter.

Referenced by extreduce_extCompClean().

extreduce_extdataIsClean()

SCIP_Bool extreduce_extdataIsClean	(	const GRAPH *	graph,
		const EXTDATA *	extdata
	)

is the extension data clean?

Parameters

graph	graph data structure
extdata	extension data

Definition at line 475 of file extreduce_data.c.

References EQ, extension_data::extstack_ncomponents, FALSE, graph_get_nEdges(), graph_get_nNodes(), extension_data::ncostupdatestalls, nnodes, extension_data::sdeq_edgesIsForbidden, extension_data::tree_bottleneckDistNode, extension_data::tree_cost, extension_data::tree_deg, extension_data::tree_depth, extension_data::tree_nDelUpArcs, extension_data::tree_nedges, extension_data::tree_ninnerNodes, extension_data::tree_nleaves, extension_data::tree_root, extension_data::tree_starcenter, and TRUE.

Referenced by extProcessComponent(), and extreduce_extCompClean().

extreduce_reddataClean()

void extreduce_reddataClean

(

REDDATA *

reddata

)

cleans reduction data

Parameters

reddata

reduction data

Definition at line 446 of file extreduce_data.c.

References reduction_data::contration, reduction_data::redcost_nlevels, reduction_data::redcost_treecosts, and SCIP_Real.

Referenced by extreduce_checkComponent(), and extreduce_extCompClean().

extreduce_reddataIsClean()

SCIP_Bool extreduce_reddataIsClean	(	const GRAPH *	graph,
		const REDDATA *	reddata
	)

is the reduction data clean?

Parameters

graph	graph data structure
reddata	reduction data

Definition at line 572 of file extreduce_data.c.

References EQ, FALSE, graph_pseudoAncestorsGetHashArraySize(), reduction_data::pseudoancestor_mark, GRAPH::pseudoancestors, reduction_data::redcost_nlevels, reduction_data::redcost_treecosts, SCIP_Real, and TRUE.

Referenced by extProcessComponent(), and extreduce_extCompClean().

extreduce_pcdataClean()

void extreduce_pcdataClean

(

PCDATA *

pcdata

)

cleans PC data

Parameters

pcdata

PC data

Definition at line 464 of file extreduce_data.c.

References pcmw_specific_data::tree_innerPrize.

Referenced by extreduce_extCompClean().

extreduce_pcdataIsClean()

SCIP_Bool extreduce_pcdataIsClean	(	const GRAPH *	graph,
		const PCDATA *	pcdata
	)

is the reduction data clean?

Parameters

graph	graph data structure
pcdata	PC data

Definition at line 605 of file extreduce_data.c.

References EQ, FALSE, graph_get_nNodes(), graph_pc_isPc(), nnodes, pcmw_specific_data::nPcSdCands, pcmw_specific_data::pcSdStart, pcmw_specific_data::pcSdToNode, pcmw_specific_data::tree_innerPrize, and TRUE.

Referenced by extProcessComponent(), and extreduce_extCompClean().

extreduce_extStackCompNOutedges()

int extreduce_extStackCompNOutedges	(	const EXTDATA *	extdata,
		int	stackpos
	)

returns size of component on the stack

Parameters

extdata	extension data
stackpos	position on the stack

Definition at line 1645 of file extreduce_dbg.c.

References EXT_STATE_NONE, extInitialCompIsGenStar(), extInitialCompIsStar(), extension_data::extstack_start, extension_data::extstack_state, SCIP_Bool, and STP_EXT_MAXGRAD.

Referenced by baseMstGetOrderedParentNodes(), and baseMstInitMsts().

extreduce_stackTopIsHashed()

SCIP_Bool extreduce_stackTopIsHashed	(	const GRAPH *	graph,
		const EXTDATA *	extdata
	)

is that complete current stack hashed?

Parameters

graph	graph data structure
extdata	extension data

Definition at line 1615 of file extreduce_dbg.c.

References extension_data::extstack_data, extension_data::extstack_start, extStackGetPosition(), FALSE, graph_edge_nPseudoAncestors(), graph_pseudoAncestors_edgeIsHashed(), reduction_data::pseudoancestor_mark, GRAPH::pseudoancestors, extension_data::reddata, SCIPdebugMessage, and TRUE.

Referenced by extreduce_mstRuleOutPeriph().

extreduce_extdataCleanArraysDbg()

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

cleans extension data extensively for debugging

Parameters

graph	graph data structure
extdata	extension data

Definition at line 881 of file extreduce_dbg.c.

References extreduce_getMaxStackNcomponents(), extreduce_getMaxStackSize(), extension_data::extstack_data, extension_data::extstack_start, extension_data::extstack_state, FARAWAY, graph_get_nNodes(), nnodes, reduction_data::redcost_nlevels, reduction_data::redcost_treenodeswaps, extension_data::reddata, SCIP_Real, extension_data::tree_edges, extension_data::tree_innerNodes, extension_data::tree_leaves, extension_data::tree_parentEdgeCost, and extension_data::tree_parentNode.

Referenced by extreduce_checkComponent().

extreduce_treeIsFlawed()

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

is current tree flawed?

Parameters

scip	SCIP
graph	graph data structure
extdata	extension data

Definition at line 939 of file extreduce_dbg.c.

References FALSE, graph_get_nEdges(), graph_get_nNodes(), nnodes, SCIP_Bool, SCIP_CALL_ABORT, SCIPallocCleanBufferArray, SCIPfreeCleanBufferArray, treeDegreesAreFlawed(), treeDistsAreFlawed(), treeGetCounters(), treeInnerNodesAreFlawed(), treeLeavesAreFlawed(), treeResetCounters(), and TRUE.

Referenced by extBacktrack(), extreduce_redcostTreeRecompute(), extreduce_treeRecompCosts(), and extTreeStackTopAdd().

extreduce_treeIsHashed()

SCIP_Bool extreduce_treeIsHashed	(	const GRAPH *	graph,
		const EXTDATA *	extdata
	)

is current tree completely hashed?

Parameters

graph	graph data structure
extdata	extension data

Definition at line 987 of file extreduce_dbg.c.

References FALSE, graph_edge_nPseudoAncestors(), graph_pseudoAncestors_edgeIsHashed(), reduction_data::pseudoancestor_mark, GRAPH::pseudoancestors, extension_data::reddata, extension_data::tree_edges, extension_data::tree_nedges, and TRUE.

Referenced by extTreeSyncWithStack().

extreduce_nodeIsInStackTop()

SCIP_Bool extreduce_nodeIsInStackTop	(	const GRAPH *	graph,
		const EXTDATA *	extdata,
		int	node
	)

is the node in the current top component of the stack?

Parameters

graph	graph data structure
extdata	extension data
node	the node

Definition at line 1094 of file extreduce_dbg.c.

References EXT_STATE_EXPANDED, EXT_STATE_MARKED, extension_data::extstack_data, extension_data::extstack_start, extension_data::extstack_state, extStackGetPosition(), FALSE, GRAPH::head, and TRUE.

Referenced by extreduce_sdshorizontalInSync(), extreduce_sdsverticalInSync(), mstCompLeafGetSDsToSiblings(), and mstCompLeafToSiblingsBiasedRuleOut().

extreduce_distCloseNodesAreValid()

SCIP_Bool extreduce_distCloseNodesAreValid	(	SCIP *	scip,
		const GRAPH *	g,
		const DISTDATA *	distdata
	)

Are the close-nodes still valid? NOTE: expensive method, just designed for debugging!

Parameters

scip	SCIP
g	graph data structure
distdata	distance data

Definition at line 1125 of file extreduce_dbg.c.

References distCloseNodesCompute(), distCloseNodesIncluded(), FALSE, graph_get_nNodes(), graph_knot_printInfo(), nnodes, distance_data::pathroot_isdirty, SCIP_Bool, SCIP_CALL_ABORT, SCIP_Real, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeMemoryArray, and TRUE.

Referenced by extreduce_distDataInit(), removeEdge(), replaceEdgeByPath(), and testDistCloseNodesPcAreValidAfterDeletion().

extreduce_distComputeRestrictedDist()

SCIP_Real extreduce_distComputeRestrictedDist	(	SCIP *	scip,
		const GRAPH *	g,
		int	vertexBlocked,
		const DISTDATA *	distdata,
		int	vertex1,
		int	vertex2
	)

Computes actual distance between two nodes. NOTE: expensive method, just designed for debugging!

Parameters

scip	SCIP
g	graph data structure
vertexBlocked	forbidden vertex
distdata	distance data
vertex1	first vertex
vertex2	second vertex

Definition at line 1172 of file extreduce_dbg.c.

References distGetRestricted(), graph_knot_isInRange(), and SCIP_Real.

extreduce_printStack()

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

prints the current stack

Parameters

graph	graph data structure
extdata	extension data

Definition at line 1031 of file extreduce_dbg.c.

References EXT_EDGE_WRAPPED, EXT_STATE_EXPANDED, EXT_STATE_MARKED, EXT_STATE_NONE, extension_data::extstack_data, extension_data::extstack_ncomponents, extension_data::extstack_start, extension_data::extstack_state, and graph_edge_printInfo().

Referenced by extTreeSyncWithStack().

extreduce_printLeaves()

void extreduce_printLeaves

(

const EXTDATA *

extdata

)

prints the leaves of the tree

Parameters

extdata

extension data

Definition at line 1013 of file extreduce_dbg.c.

References extension_data::tree_leaves, and extension_data::tree_nleaves.

extreduce_printTopLevel()

void extreduce_printTopLevel

(

const EXTDATA *

extdata

)

Prints top horizontal level

Parameters

extdata

extension data

Definition at line 1073 of file extreduce_dbg.c.

References extreduce_mldistsTopLevelBases(), extreduce_mldistsTopLevelNSlots(), extension_data::reddata, and reduction_data::sds_horizontal.

Referenced by extreduce_mstLevelClose().

extreduce_extendInitDebug()

void extreduce_extendInitDebug	(	int *	extedgesstart,
		int *	extedges
	)

debug initialization

Parameters

extedgesstart	array
extedges	array

Definition at line 1196 of file extreduce_dbg.c.

References STP_EXT_MAXGRAD.

Referenced by extTreeFindExtensions().

extreduce_sdsverticalInSync()

SCIP_Bool extreduce_sdsverticalInSync	(	SCIP *	scip,
		const GRAPH *	graph,
		int	compsize,
		int	nleaves_ancestors,
		int	topleaf,
		EXTDATA *	extdata
	)

check whether vertical SDs are up to date for given leaf of component

Parameters

scip	SCIP
graph	graph data structure
compsize	size of component
nleaves_ancestors	number of leaves to ancestors
topleaf	component leaf to check for
extdata	extension data

Definition at line 1212 of file extreduce_dbg.c.

References EQ, extIsAtInitialComp(), extreduce_extGetSd(), extreduce_mldistsTopTargetDists(), extreduce_mldistsTopTargetIds(), extreduce_nodeIsInStackTop(), FALSE, FARAWAY, graph_pc_isPc(), extension_data::reddata, SCIP_Bool, SCIP_Real, SCIPdebugMessage, reduction_data::sds_vertical, extension_data::tree_deg, extension_data::tree_leaves, extension_data::tree_nleaves, and TRUE.

Referenced by mstCompLeafGetSDsToAncestors().

extreduce_sdshorizontalInSync()

SCIP_Bool extreduce_sdshorizontalInSync	(	SCIP *	scip,
		const GRAPH *	graph,
		int	topleaf,
		EXTDATA *	extdata
	)

check whether horizontal SDs are up to date for given leaf of component

Parameters

scip	SCIP
graph	graph data structure
topleaf	component leaf to check for
extdata	extension data

Definition at line 1269 of file extreduce_dbg.c.

References EQ, extreduce_extGetSdProperDouble(), extreduce_mldistsTopTargetDist(), extreduce_nodeIsInStackTop(), extension_data::extstack_data, extStackGetPosition(), extStackGetTopOutEdgesEnd(), extStackGetTopOutEdgesStart(), FALSE, graph_pc_isPc(), GRAPH::head, extension_data::reddata, SCIP_Bool, SCIP_Real, SCIPdebugMessage, reduction_data::sds_horizontal, extension_data::tree_deg, and TRUE.

Referenced by mstCompLeafGetSDsToSiblings(), and mstCompLeafToSiblingsBiasedRuleOut().

extreduce_sdsTopInSync()

SCIP_Bool extreduce_sdsTopInSync	(	SCIP *	scip,
		const GRAPH *	graph,
		const SCIP_Real	sds[],
		int	topleaf,
		EXTDATA *	extdata
	)

are sds from top component leaf corresponding to current tree?

Parameters

scip	SCIP
graph	graph data structure
sds	SDs from top leaf
topleaf	component leaf to check for
extdata	extension data

Definition at line 1329 of file extreduce_dbg.c.

References EQ, extreduce_extGetSdProper(), extreduce_extGetSdProperDouble(), FALSE, FARAWAY, graph_pc_isPc(), SCIP_Bool, SCIP_Real, SCIPdebugMessage, extension_data::tree_leaves, extension_data::tree_nleaves, and TRUE.

Referenced by mstCompLeafGetSDs().

extreduce_mstTopCompInSync()

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

is the top MST sync with the tree? (does not check objective)

Parameters

scip	SCIP
graph	graph data structure
extdata	extension data

Definition at line 1505 of file extreduce_dbg.c.

References csr_storage::cost, extreduce_extGetSdProper(), extreduce_extGetSdProperDouble(), FALSE, graph_csrdepo_getTopCSR(), graph_pc_isPcMw(), GT, csr_storage::head, LT, MAX, reduction_data::msts_comp, csr_storage::nnodes, extension_data::reddata, SCIP_Real, SCIPdebugMessage, csr_storage::start, extension_data::tree_leaves, extension_data::tree_nleaves, and TRUE.

Referenced by extStackTopCollectExtEdges(), extStackTopCollectExtEdgesSing(), extStackTopProcessInitialEdges(), and mstCompBuildMst().

extreduce_mstTopCompExtObjValid()

SCIP_Bool extreduce_mstTopCompExtObjValid	(	SCIP *	scip,
		const GRAPH *	graph,
		int	extvert,
		SCIP_Real	extobj,
		EXTDATA *	extdata
	)

is the objective of the top MST extension valid for the tree?

does currently not work because of weird SD computation

Parameters

scip	SCIP
graph	graph data structure
extvert	extended vertex
extobj	objective of extension
extdata	extension data

Definition at line 1427 of file extreduce_dbg.c.

References FALSE, graph_pc_isPcMw(), GT, LT, SCIP_Bool, SCIP_Real, SCIPdebugMessage, sdmstGetExtWeight(), and TRUE.

Referenced by mstLevelLeafTryExtMst().

extreduce_mstTopCompObjValid()

SCIP_Bool extreduce_mstTopCompObjValid	(	SCIP *	scip,
		const GRAPH *	graph,
		SCIP_Real	compobj,
		EXTDATA *	extdata
	)

is the objective of the top MST sync with the tree?

Parameters

scip	SCIP
graph	graph data structure
compobj	alleged objective of component
extdata	extension data

Definition at line 1468 of file extreduce_dbg.c.

References FALSE, graph_pc_isPcMw(), GT, LT, SCIP_Bool, SCIP_Real, SCIPdebugMessage, sdmstGetWeight(), extension_data::tree_leaves, extension_data::tree_nleaves, and TRUE.

Referenced by mstCompRuleOut().

extreduce_mstInternalsInSync()

SCIP_Bool extreduce_mstInternalsInSync

(

const EXTDATA *

extdata

)

are the internal data MST structures in sync. with each other?

Parameters

extdata

extension data

Definition at line 1573 of file extreduce_dbg.c.

References extreduce_mldistsEmptySlotExists(), extreduce_mldistsNlevels(), extreduce_mldistsTopLevelNSlots(), FALSE, graph_csrdepo_getNcsrs(), reduction_data::msts_comp, reduction_data::msts_levelbase, extension_data::reddata, SCIPdebugMessage, reduction_data::sds_horizontal, reduction_data::sds_vertical, and TRUE.

Referenced by extreduce_mstLevelClose().

extreduce_mstTopLevelBaseObjValid()

SCIP_Bool extreduce_mstTopLevelBaseObjValid	(	SCIP *	scip,
		const GRAPH *	graph,
		int	extnode,
		EXTDATA *	extdata
	)

is the top level base MST objective in sync with the current tree?

Parameters

scip	SCIP
graph	graph data structure
extnode	node from which the level was extended
extdata	extension data

Definition at line 1381 of file extreduce_dbg.c.

References FALSE, graph_csrdepo_getTopCSR(), graph_pc_isPcMw(), reduction_data::msts_levelbase, mstTopLevelBaseGetNodes(), mstTopLevelBaseValidWeight(), nnodes, csr_storage::nnodes, extension_data::reddata, reduce_dcmstMstIsValid(), SCIP_Bool, SCIP_CALL_ABORT, SCIPallocMemoryArray, SCIPfreeMemoryArray, extension_data::tree_deg, extension_data::tree_nleaves, and TRUE.

Referenced by baseMstFinalizeNew().