Detailed Description

extended-reduction tree contraction algorithms for Steiner tree problems

Author: Daniel Rehfeldt

This file implements rule-out algorithms for extended reduction techniques for Steiner problems. Allows to compute and store special distance (SD) MSTs / SPGs between the leaves of extension tree, after the contraction of certain parts of the tree.

Similarly to the extmst methods, we keep two distance storages: One from all component vertices to the lower leaves. One from the component root to the lower leafs and to the siblings.

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

Definition in file extreduce_contract.c.

#include "extreduce.h"
#include "extreducedefs.h"

Go to the source code of this file.

Data Structures
struct	extension_tree_contraction

Functions
Local methods
static int	compDistGetPosition (int leaf_id, int level, const CONTRACT *contraction)

static void	compUpDistAddLeaf (int leaf_id, SCIP_Real dist, SCIP_Bool override, EXTDATA extdata, CONTRACT contraction)

static void	compUpDistUpdateLeavesDists (const GRAPH graph, EXTDATA extdata, CONTRACT *contraction)

static void	compRootDistAddLeaf (int leaf_id, SCIP_Real dist, EXTDATA extdata, CONTRACT contraction)

static void	compRootDistsUpdateLeavesDists (const GRAPH graph, EXTDATA extdata, CONTRACT *contraction)

static void	compUpDistInitMindists (int level, EXTDATA extdata, CONTRACT contraction)

static void	compUpDistUpdateMindists (int level, EXTDATA extdata, CONTRACT contraction)

static void	compRootDistUpdateMindists (int level, EXTDATA extdata, CONTRACT contraction)

static void	addComponentUpdateTreeCosts (const GRAPH graph, EXTDATA extdata, CONTRACT *contraction)

static void	addComponentUpdateLeavesStarts (const GRAPH graph, EXTDATA extdata, CONTRACT *contraction)

static void	addComponentUpdateLeavesToCompDists (const GRAPH graph, EXTDATA extdata, CONTRACT *contraction)

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

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

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

void	extreduce_contractionFree (SCIP scip, CONTRACT *contraction)

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

Function Documentation

◆ compDistGetPosition()

static int compDistGetPosition	(	int	leaf_id,
		int	level,
		const CONTRACT *	contraction
	)

inlinestatic

gets position of distance value

Parameters

leaf_id	id
level	level
contraction	contraction data

Definition at line 68 of file extreduce_contract.c.

References extension_tree_contraction::leaves_maxn, and extension_tree_contraction::level_maxn.

Referenced by compRootDistAddLeaf(), compRootDistUpdateMindists(), compUpDistAddLeaf(), compUpDistInitMindists(), and compUpDistUpdateMindists().

◆ compUpDistAddLeaf()

static void compUpDistAddLeaf	(	int	leaf_id,
		SCIP_Real	dist,
		SCIP_Bool	override,
		EXTDATA *	extdata,
		CONTRACT *	contraction
	)

inlinestatic

adds distance

Parameters

leaf_id	id
dist	distance
override	override distance? (take in otherwise)
extdata	extension data
contraction	contraction data

Definition at line 88 of file extreduce_contract.c.

References compDistGetPosition(), GE, extension_tree_contraction::leafToCompLeaves, extension_tree_contraction::leafToCompUpDists, extension_tree_contraction::level_n, LT, and extension_data::tree_leaves.

Referenced by compUpDistUpdateLeavesDists().

◆ compUpDistUpdateLeavesDists()

static void compUpDistUpdateLeavesDists	(	const GRAPH *	graph,
		EXTDATA *	extdata,
		CONTRACT *	contraction
	)

inlinestatic

updates distances from lower leafs to top component

Parameters

graph	graph data structure
extdata	extension data
contraction	contraction data

Definition at line 119 of file extreduce_contract.c.

References compUpDistAddLeaf(), extreduce_mldistsLevelNTopTargets(), extreduce_mldistsTopTargetDists(), extreduce_mldistsTopTargetIds(), extension_data::extstack_data, extStackGetPosition(), extStackGetTopOutEdgesEnd(), extStackGetTopOutEdgesStart(), GRAPH::head, extension_tree_contraction::leaves_start, extension_tree_contraction::level_n, extension_data::reddata, SCIP_Bool, SCIP_Real, SCIPdebugMessage, reduction_data::sds_vertical, and extension_data::tree_leaves.

Referenced by addComponentUpdateLeavesToCompDists().

◆ compRootDistAddLeaf()

static void compRootDistAddLeaf	(	int	leaf_id,
		SCIP_Real	dist,
		EXTDATA *	extdata,
		CONTRACT *	contraction
	)

inlinestatic

adds distance

Parameters

leaf_id	id
dist	distance
extdata	extension data
contraction	contraction data

Definition at line 161 of file extreduce_contract.c.

References compDistGetPosition(), GE, extension_tree_contraction::leafToCompLeaves, extension_tree_contraction::leafToCompRootDists, extension_tree_contraction::level_n, and extension_data::tree_leaves.

Referenced by compRootDistsUpdateLeavesDists().

◆ compRootDistsUpdateLeavesDists()

static void compRootDistsUpdateLeavesDists	(	const GRAPH *	graph,
		EXTDATA *	extdata,
		CONTRACT *	contraction
	)

inlinestatic

updates distances from lower leafs (w.r.t top component) to top component root

Parameters

graph	graph data structure
extdata	extension data
contraction	contraction data

Definition at line 182 of file extreduce_contract.c.

References compRootDistAddLeaf(), extreduce_mldistsLevelNTargets(), extreduce_mldistsTargetDists(), extreduce_mldistsTargetIds(), extStackGetTopRoot(), extension_tree_contraction::leaves_start, extension_tree_contraction::level_n, NULL, extension_data::reddata, SCIP_Bool, SCIP_Real, SCIPdebugMessage, reduction_data::sds_horizontal, reduction_data::sds_vertical, and extension_data::tree_leaves.

Referenced by addComponentUpdateLeavesToCompDists().

◆ compUpDistInitMindists()

static void compUpDistInitMindists	(	int	level,
		EXTDATA *	extdata,
		CONTRACT *	contraction
	)

inlinestatic

initializes distances from component to lower leaves

Parameters

level	level from which to initialize
extdata	extension data
contraction	contraction data

Definition at line 248 of file extreduce_contract.c.

References compDistGetPosition(), FARAWAY, extension_tree_contraction::leafToCompUpDists, extension_tree_contraction::leaves_maxn, extension_tree_contraction::leaves_mindists, extension_tree_contraction::leaves_start, extension_tree_contraction::level_n, and SCIP_Real.

Referenced by ruledOut().

◆ compUpDistUpdateMindists()

static void compUpDistUpdateMindists	(	int	level,
		EXTDATA *	extdata,
		CONTRACT *	contraction
	)

inlinestatic

updates distances from component to lower leaves

Parameters

level	level from which to initialize
extdata	extension data
contraction	contraction data

Definition at line 276 of file extreduce_contract.c.

References compDistGetPosition(), GE, extension_tree_contraction::leafToCompUpDists, extension_tree_contraction::leaves_mindists, extension_tree_contraction::leaves_start, extension_tree_contraction::level_n, LT, and SCIP_Real.

Referenced by ruledOut().

◆ compRootDistUpdateMindists()

static void compRootDistUpdateMindists	(	int	level,
		EXTDATA *	extdata,
		CONTRACT *	contraction
	)

inlinestatic

updates leaf distances from component root to lower leaves

Parameters

level	level from which to initialize
extdata	extension data
contraction	contraction data

Definition at line 303 of file extreduce_contract.c.

References compDistGetPosition(), GE, extension_tree_contraction::leafToCompRootDists, extension_tree_contraction::leaves_mindists, extension_tree_contraction::leaves_start, extension_tree_contraction::level_n, LT, and SCIP_Real.

Referenced by ruledOut().

◆ addComponentUpdateTreeCosts()

static void addComponentUpdateTreeCosts	(	const GRAPH *	graph,
		EXTDATA *	extdata,
		CONTRACT *	contraction
	)

inlinestatic

helper

Parameters

graph	graph data structure
extdata	extension data
contraction	contraction data

Definition at line 330 of file extreduce_contract.c.

References GRAPH::cost, extProbIsPc(), extension_data::extstack_data, extStackGetPosition(), extStackGetTopOutEdgesEnd(), extStackGetTopOutEdgesStart(), GE, graph_edge_isInRange(), extension_tree_contraction::level_n, extension_tree_contraction::level_treecost, extension_data::pcdata, SCIP_Real, SCIPdebugMessage, extension_data::tree_cost, and pcmw_specific_data::tree_innerPrize.

Referenced by addComponent().

◆ addComponentUpdateLeavesStarts()

static void addComponentUpdateLeavesStarts	(	const GRAPH *	graph,
		EXTDATA *	extdata,
		CONTRACT *	contraction
	)

inlinestatic

helper

Parameters

graph	graph data structure
extdata	extension data
contraction	contraction data

Definition at line 367 of file extreduce_contract.c.

References extStackGetPosition(), extStackGetTopOutEdgesEnd(), extStackGetTopOutEdgesStart(), graph_knot_printInfo(), extension_tree_contraction::leafToCompLeaves, extension_tree_contraction::leaves_start, extension_tree_contraction::level_n, SCIPdebugMessage, extension_data::tree_leaves, and extension_data::tree_nleaves.

Referenced by addComponent().

◆ addComponentUpdateLeavesToCompDists()

static void addComponentUpdateLeavesToCompDists	(	const GRAPH *	graph,
		EXTDATA *	extdata,
		CONTRACT *	contraction
	)

inlinestatic

helper

Parameters

graph	graph data structure
extdata	extension data
contraction	contraction data

Definition at line 406 of file extreduce_contract.c.

References compRootDistsUpdateLeavesDists(), compUpDistUpdateLeavesDists(), and extension_tree_contraction::level_n.

Referenced by addComponent().

◆ addComponent()

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

static

adds top component

Parameters

scip	SCIP
graph	graph data structure
extdata	extension data

Definition at line 424 of file extreduce_contract.c.

References addComponentUpdateLeavesStarts(), addComponentUpdateLeavesToCompDists(), addComponentUpdateTreeCosts(), reduction_data::contration, extension_tree_contraction::level_maxn, extension_tree_contraction::level_n, extension_data::reddata, SCIPdebugMessage, and extension_data::tree_depth.

Referenced by extreduce_contractionRuleOutPeriph().

◆ ruledOut()

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

static

can the current tree be ruled out?

Parameters

scip	SCIP
graph	graph data structure
extdata	extension data

Definition at line 446 of file extreduce_contract.c.

References compRootDistUpdateMindists(), compUpDistInitMindists(), compUpDistUpdateMindists(), reduction_data::contration, reduction_data::dcmst, EQ, FALSE, graph_csrdepo_getCSR(), extension_tree_contraction::leaves_mindists, extension_tree_contraction::leaves_start, extension_tree_contraction::level_n, extension_tree_contraction::level_treecost, LT, extension_tree_contraction::mst_buffer, reduction_data::msts_levelbase, csr_storage::nedges_max, csr_storage::nnodes, extension_data::reddata, reduce_dcmstAddNode(), reduce_dcmstGetWeight(), SCIP_Bool, SCIP_Real, SCIPdebugMessage, extension_data::tree_leaves, and TRUE.

Referenced by extreduce_contractionRuleOutPeriph(), extreduce_mstbiased3LeafTreeRuleOut(), extreduce_mstRuleOutPeriph(), extStackTopExpandSingletons(), extStackTopExpandWrapped(), and mstCompRuleOut().

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

SCIP

Detailed Description

Data Structures

Functions

Function Documentation

◆ compDistGetPosition()

◆ compUpDistAddLeaf()

◆ compUpDistUpdateLeavesDists()

◆ compRootDistAddLeaf()

◆ compRootDistsUpdateLeavesDists()

◆ compUpDistInitMindists()

◆ compUpDistUpdateMindists()

◆ compRootDistUpdateMindists()

◆ addComponentUpdateTreeCosts()

◆ addComponentUpdateLeavesStarts()

◆ addComponentUpdateLeavesToCompDists()

◆ addComponent()

◆ ruledOut()

◆ extreduce_contractionInit()

◆ extreduce_contractionFree()

◆ extreduce_contractionRuleOutPeriph()