Detailed Description

extended-reduction specific tree bottleneck algorithms for Steiner tree problems

Author: Daniel Rehfeldt

This file implements tree bottleneck algorithms for extended reduction techniques for Steiner problems.

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

Definition in file extreduce_bottleneck.c.

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

Go to the source code of this file.

Functions
Local methods
static SCIP_Real	bottleneckGetDist (const GRAPH graph, const EXTDATA extdata, int vertex_pathmarked, int vertex_unmarked)

static void	bottleneckMarkEqualityPath (SCIP scip, const GRAPH graph, int path_start, int path_end, EXTDATA *extdata)

static void	bottleneckMarkEqualityEdges (SCIP scip, const GRAPH graph, SCIP_Real dist_eq, int vertex_pathmarked, int vertex_unmarked, EXTDATA *extdata)

static void	bottleneckMarkEqualityEdge (SCIP scip, const GRAPH g, int edge, EXTDATA *extdata)

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

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

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

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

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

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

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

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

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

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

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

Function Documentation

◆ bottleneckGetDist()

static SCIP_Real bottleneckGetDist	(	const GRAPH *	graph,
		const EXTDATA *	extdata,
		int	vertex_pathmarked,
		int	vertex_unmarked
	)

static

computes the tree bottleneck between vertices in the current tree, for which vertex_pathmarked root path has been marked already

Parameters

graph	graph data structure
extdata	extension data
vertex_pathmarked	vertex with marked rootpath
vertex_unmarked	second vertex

Definition at line 48 of file extreduce_bottleneck.c.

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

Referenced by extreduce_bottleneckIsDominated(), extreduce_bottleneckIsDominatedBiased(), extreduce_bottleneckWithExtedgeIsDominated(), and extreduce_bottleneckWithExtedgeIsDominatedBiased().

◆ bottleneckMarkEqualityPath()

static void bottleneckMarkEqualityPath	(	SCIP *	scip,
		const GRAPH *	graph,
		int	path_start,
		int	path_end,
		EXTDATA *	extdata
	)

inlinestatic

helper

Parameters

scip	SCIP
graph	graph data structure
path_start	vertex to start from
path_end	vertex to end at
extdata	extension data

Definition at line 118 of file extreduce_bottleneck.c.

References GRAPH::cost, EAT_LAST, EQ, graph_edge_printInfo(), graph_knot_isInRange(), GRAPH::head, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIPdebugMessage, extension_data::sdeq_edgesIsForbidden, extension_data::sdeq_hasForbiddenEdges, StpVecPushBack, extension_data::tree_parentEdgeCost, extension_data::tree_parentNode, and TRUE.

Referenced by bottleneckMarkEqualityEdges().

◆ bottleneckMarkEqualityEdges()

static void bottleneckMarkEqualityEdges	(	SCIP *	scip,
		const GRAPH *	graph,
		SCIP_Real	dist_eq,
		int	vertex_pathmarked,
		int	vertex_unmarked,
		EXTDATA *	extdata
	)

inlinestatic

markes bottleneck edges used for equality rule-out

Parameters

scip	SCIP
graph	graph data structure
dist_eq	distance that was used for equality rule-out
vertex_pathmarked	vertex with marked rootpath
vertex_unmarked	second vertex
extdata	extension data

Definition at line 167 of file extreduce_bottleneck.c.

References bottleneckMarkEqualityPath(), EQ, extIsAtInitialGenStar(), GE, graph_pc_isPc(), 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 UNKNOWN.

Referenced by extreduce_bottleneckIsDominated(), and extreduce_bottleneckWithExtedgeIsDominated().

◆ bottleneckMarkEqualityEdge()

static void bottleneckMarkEqualityEdge	(	SCIP *	scip,
		const GRAPH *	g,
		int	edge,
		EXTDATA *	extdata
	)

inlinestatic

markes single bottleneck edge used for equality rule-out

Parameters

scip	SCIP
g	graph data structure
edge	the edge to mark
extdata	extension data

Definition at line 293 of file extreduce_bottleneck.c.

References graph_edge_isInRange(), SCIP_Bool, extension_data::sdeq_edgesIsForbidden, extension_data::sdeq_hasForbiddenEdges, StpVecPushBack, and TRUE.

Referenced by extreduce_bottleneckToSiblingIsDominated(), and extreduce_bottleneckWithExtedgeIsDominated().

◆ bottleneckIsEqualityDominated()

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

inlinestatic

helper to check the case of quality

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 316 of file extreduce_bottleneck.c.

References EQ, extreduce_distDataGetSdDoubleForbiddenEq(), FALSE, GE, LE, SCIP_Real, and TRUE.

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

◆ 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