extreduce_contract.c File Reference

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