extreduce_extmstbiased.c File Reference

Detailed Description

extended-reduction specific biased bottleneck distance MST algorithms for Steiner tree problems

Author

Daniel Rehfeldt

This file implements MST algorithms for extended reduction techniques for Steiner problems, using the implied bottleneck Steiner distance Furthermore, one can check for tree bottlenecks.

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

Definition in file extreduce_extmstbiased.c.

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

Go to the source code of this file.

Functions
Local methods
static SCIP_Bool	mst3StarNeighborRuleOut (SCIP *scip, const SCIP_Real dists_def[3], const SCIP_Real dists_bias[3], SCIP_Real starcost, SCIP_Bool allowEquality)
static void	mst3LeafTreeGetSds (SCIP *scip, const GRAPH *graph, EXTDATA *extdata, SCIP_Real sds_def[3], SCIP_Real sds_bias[3])
Interface methods
SCIP_Bool	extreduce_mstbiased3LeafTreeRuleOut (SCIP *scip, const GRAPH *graph, SCIP_Real tree_cost, EXTDATA *extdata)
SCIP_RETCODE	extreduce_mstbiasedCheck3NodeSimple (SCIP *scip, const GRAPH *graph, int node, DISTDATA *distdata_default, DISTDATA *distdata_biased, SCIP_Bool *isPseudoDeletable)

Function Documentation

mst3StarNeighborRuleOut()

static SCIP_Bool mst3StarNeighborRuleOut ( SCIP *  scip, const SCIP_Real  dists_def[3], const SCIP_Real  dists_bias[3], SCIP_Real  starcost, SCIP_Bool  allowEquality  )

static

Can we (peripherally) rule out simple star of degree 3? Works by using biased distance

Parameters

scip	SCIP data structure
dists_def	distances between adjacent nodes
dists_bias	biased distances between adjacent nodes
starcost	cost of the star
allowEquality	allow equality?

Definition at line 55 of file extreduce_extmstbiased.c.

References FALSE, SCIPisLE(), SCIPisLT(), and TRUE.

Referenced by extreduce_mstbiased3LeafTreeRuleOut(), and extreduce_mstbiasedCheck3NodeSimple().

mst3LeafTreeGetSds()

static void mst3LeafTreeGetSds ( SCIP *  scip, const GRAPH *  graph, EXTDATA *  extdata, SCIP_Real  sds_def[3], SCIP_Real  sds_bias[3]  )

inlinestatic

gets biased SDs between leaves

Parameters

scip	SCIP
graph	graph data structure
extdata	extension data
sds_def	array to store the SDs
sds_bias	array to store the SDs

Definition at line 104 of file extreduce_extmstbiased.c.

References extension_data::distdata, extension_data::distdata_biased, extreduce_distDataGetSdDouble(), extreduce_mldistsTopTargetDist(), extreduce_mldistsTopTargetDists(), extension_data::extstack_data, extStackGetPosition(), extStackGetTopOutEdgesEnd(), extStackGetTopOutEdgesStart(), GRAPH::head, extension_data::reddata, reduction_data::sds_horizontal, reduction_data::sds_vertical, reduction_data::sdsbias_horizontal, reduction_data::sdsbias_vertical, SWAP_INTS, GRAPH::tail, and extension_data::tree_leaves.

Referenced by extreduce_mstbiased3LeafTreeRuleOut().

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