Detailed Description

extended reductions for Steiner tree problems

Author: Daniel Rehfeldt

This file implements extended reduction debugging routines for several Steiner problems.

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

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

Go to the source code of this file.

Functions
static SCIP_Real	sdmstGetWeight (SCIP scip, const GRAPH graph, int nnodes, const int nodes[], SCIP_Bool computeLower, EXTDATA *extdata)

static SCIP_Real	sdmstGetExtWeight (SCIP scip, const GRAPH graph, int extvert, SCIP_Bool computeLower, EXTDATA *extdata)

static void	mstTopLevelBaseGetNodes (int extnode, int nnodes, int nodes[], const EXTDATA *extdata)

static SCIP_Bool	mstTopLevelBaseValidWeight (SCIP scip, const GRAPH graph, int base_nnodes, int base_nodes[], const CSR mst_base, EXTDATA extdata)

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

static SCIP_Real	distCloseNodesGetMaxCost (int vertex, const DISTDATA *distdata)

static SCIP_RETCODE	distCloseNodesCompute (SCIP scip, const GRAPH g, const DISTDATA distdata, int startvertex, int closenodes_indices, SCIP_Real closenodes_dists, int nclosenodes)

static void	distCloseNodesPrintLostNodeInfo (const GRAPH g, const DISTDATA distdata, int vertex_base, int index_lost, const int closenodes_indices, const SCIP_Real closenodes_dists, int nclosenodes)

static SCIP_Bool	distCloseNodesIncluded (SCIP scip, const GRAPH g, const DISTDATA distdata, int vertex, const int closenodes_indices, const SCIP_Real *closenodes_dists, int nclosenodes)

static void	treeGetCounters (const GRAPH graph, const EXTDATA extdata, int edgecount[], int degreecount[], SCIP_Bool *treeIsFlawed)

static void	treeResetCounters (const GRAPH graph, const EXTDATA extdata, int edgecount[], int degreecount[])

static SCIP_Bool	treeDegreesAreFlawed (const GRAPH graph, const EXTDATA extdata, const int degreecount[])

static SCIP_Bool	treeLeavesAreFlawed (const GRAPH graph, const EXTDATA extdata, const int degreecount[])

static SCIP_Bool	treeInnerNodesAreFlawed (const GRAPH graph, const EXTDATA extdata, const int degreecount[])

static SCIP_Bool	treeDistsAreFlawed (const GRAPH graph, const EXTDATA extdata)

void	extreduce_extdataCleanArraysDbg (const GRAPH graph, EXTDATA extdata)

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

SCIP_Bool	extreduce_treeIsHashed (const GRAPH graph, const EXTDATA extdata)

void	extreduce_printLeaves (const EXTDATA *extdata)

void	extreduce_printStack (const GRAPH graph, const EXTDATA extdata)

void	extreduce_printTopLevel (const EXTDATA *extdata)

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

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

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

void	extreduce_extendInitDebug (int extedgesstart, int extedges)

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

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

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

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

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

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

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

SCIP_Bool	extreduce_mstInternalsInSync (const EXTDATA *extdata)

SCIP_Bool	extreduce_stackTopIsHashed (const GRAPH graph, const EXTDATA extdata)

int	extreduce_extStackCompNOutedges (const EXTDATA *extdata, int stackpos)

Function Documentation

◆ sdmstGetWeight()

static SCIP_Real sdmstGetWeight	(	SCIP *	scip,
		const GRAPH *	graph,
		int	nnodes,
		const int	nodes[],
		SCIP_Bool	computeLower,
		EXTDATA *	extdata
	)

static

get SD MST weight NOTE: might deviate because only getSd is used...maybe only use double in the code?

Parameters

scip	SCIP
graph	graph data structure
nnodes	number of nodes for MST computation
nodes	nodes (from graph) for MST computation
computeLower	compute lower bound? (otherwise upper)
extdata	extension data

Definition at line 42 of file extreduce_dbg.c.

References complete_graph::adjedgecosts, BLOCKED, cgraph_free(), cgraph_init(), cgraph_node_append(), cgraph_node_applyMinAdjCosts(), cmst_computeMst(), cmst_free(), cmst_init(), EQ, extreduce_extGetSd(), extreduce_extGetSdDouble(), FARAWAY, GE, MAX, complete_mst::mstobj, nnodes, SCIP_CALL_ABORT, SCIP_Real, and STP_EXTTREE_MAXNLEAVES_GUARD.

Referenced by extreduce_mstTopCompObjValid(), mstTopLevelBaseValidWeight(), and sdmstGetExtWeight().

◆ sdmstGetExtWeight()

static SCIP_Real sdmstGetExtWeight	(	SCIP *	scip,
		const GRAPH *	graph,
		int	extvert,
		SCIP_Bool	computeLower,
		EXTDATA *	extdata
	)

static

gets MST weight for SD MST spanning all leaves and extension vertex NOTE: only for debugging! very slow!

Parameters

scip	SCIP
graph	graph data structure
extvert	extended vertex
computeLower	compute lower bound? (otherwise upper)
extdata	extension data

Definition at line 143 of file extreduce_dbg.c.

References SCIP_CALL_ABORT, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, sdmstGetWeight(), STP_EXTTREE_MAXNLEAVES_GUARD, extension_data::tree_leaves, and extension_data::tree_nleaves.

Referenced by extreduce_mstTopCompExtObjValid().

◆ mstTopLevelBaseGetNodes()

static void mstTopLevelBaseGetNodes	(	int	extnode,
		int	nnodes,
		int	nodes[],
		const EXTDATA *	extdata
	)

static

gets nodes of top levelbase MST

Parameters

extnode	extension nodes
nnodes	number of nodes
nodes	nodes (from graph) to be filled in
extdata	extension data

Definition at line 182 of file extreduce_dbg.c.

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

Referenced by extreduce_mstTopLevelBaseObjValid().

◆ mstTopLevelBaseValidWeight()

static SCIP_Bool mstTopLevelBaseValidWeight	(	SCIP *	scip,
		const GRAPH *	graph,
		int	base_nnodes,
		int	base_nodes[],
		const CSR *	mst_base,
		EXTDATA *	extdata
	)

static

is the weight of the top levelbase MST valid?

Parameters

scip	SCIP
graph	graph data structure
base_nnodes	number of nodes
base_nodes	MST nodes (from graph)
mst_base	the stored MST
extdata	extension data

Definition at line 217 of file extreduce_dbg.c.

References FALSE, GT, LT, csr_storage::nnodes, reduce_dcmstGetWeight(), SCIP_Bool, SCIP_Real, SCIPdebugMessage, sdmstGetWeight(), and TRUE.

Referenced by extreduce_mstTopLevelBaseObjValid().

◆ distGetRestricted()

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

static

returns shortest distance between given vertices

Parameters

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

Definition at line 259 of file extreduce_dbg.c.

References CONNECT, GRAPH::cost, distance_data::dijkdata, EAT_LAST, FARAWAY, graph_heap_correct(), graph_heap_create(), graph_heap_deleteMinReturnNode(), graph_heap_free(), graph_pc_isPc(), GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, dijkstra_data::node_bias, NULL, GRAPH::oeat, GRAPH::outbeg, dijkstra_heap::position, SCIP_Bool, SCIP_CALL_ABORT, SCIP_Real, SCIPallocMemoryArray, SCIPfreeMemoryArray, dijkstra_heap::size, TRUE, and UNKNOWN.

Referenced by extreduce_distComputeRestrictedDist().

◆ distCloseNodesGetMaxCost()

static SCIP_Real distCloseNodesGetMaxCost	(	int	vertex,
		const DISTDATA *	distdata
	)

inlinestatic

Helper. Gives maximum cost among all close nodes.

Parameters

vertex	vertex for which to get the maximum cost
distdata	distance data

Definition at line 346 of file extreduce_dbg.c.

References distance_data::closenodes_distances, distance_data::closenodes_range, csr_range::end, FARAWAY, GE, SCIP_Real, and csr_range::start.

Referenced by distCloseNodesCompute().

◆ distCloseNodesCompute()

static SCIP_RETCODE distCloseNodesCompute	(	SCIP *	scip,
		const GRAPH *	g,
		const DISTDATA *	distdata,
		int	startvertex,
		int *	closenodes_indices,
		SCIP_Real *	closenodes_dists,
		int *	nclosenodes
	)

static

Gets close nodes and corresponding distances. NOTE: needs to correspond to 'distDataComputeCloseNodes' in 'extreduce_dbg.c'

Parameters

scip	SCIP
g	graph data structure
distdata	distance data
startvertex	start vertex
closenodes_indices	indices of close nodes
closenodes_dists	distances of close nodes
nclosenodes	number of added close nodes

Definition at line 374 of file extreduce_dbg.c.

References CONNECT, dynamic_csr_storage::cost, GRAPH::dcsr_storage, distance_data::dijkdata, distCloseNodesGetMaxCost(), FARAWAY, graph_heap_correct(), graph_heap_create(), graph_heap_deleteMinReturnNode(), graph_heap_free(), graph_pc_isPc(), GT, dynamic_csr_storage::head, GRAPH::knots, GRAPH::mark, nnodes, dijkstra_data::node_bias, NULL, dijkstra_heap::position, dynamic_csr_storage::range, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, SCIPfreeMemoryArray, dijkstra_heap::size, TRUE, and UNKNOWN.

Referenced by extreduce_distCloseNodesAreValid().

◆ distCloseNodesPrintLostNodeInfo()

static void distCloseNodesPrintLostNodeInfo	(	const GRAPH *	g,
		const DISTDATA *	distdata,
		int	vertex_base,
		int	index_lost,
		const int *	closenodes_indices,
		const SCIP_Real *	closenodes_dists,
		int	nclosenodes
	)

static

Parameters

g	graph data structure
distdata	distance data
vertex_base	vertex for check
index_lost	vertex that is lost
closenodes_indices	indices of newly found close nodes
closenodes_dists	distances of newly found close nodes
nclosenodes	number of newly found close nodes

Definition at line 474 of file extreduce_dbg.c.

References distance_data::closenodes_distances, distance_data::closenodes_indices, distance_data::closenodes_prededges, distance_data::closenodes_range, distance_data::dijkdata, csr_range::end, graph_edge_printInfo(), graph_knot_printInfo(), GRAPH::head, dijkstra_data::node_bias, SCIP_Real, SCIPdebugMessage, csr_range::start, and GRAPH::tail.

Referenced by distCloseNodesIncluded().

◆ distCloseNodesIncluded()

static SCIP_Bool distCloseNodesIncluded	(	SCIP *	scip,
		const GRAPH *	g,
		const DISTDATA *	distdata,
		int	vertex,
		const int *	closenodes_indices,
		const SCIP_Real *	closenodes_dists,
		int	nclosenodes
	)

static

Parameters

scip	SCIP
g	graph data structure
distdata	distance data
vertex	vertex for check
closenodes_indices	indices of newly found close nodes
closenodes_dists	distances of newly found close nodes
nclosenodes	number of newly found close nodes

Definition at line 559 of file extreduce_dbg.c.

References distance_data::closenodes_distances, distance_data::closenodes_indices, distance_data::closenodes_prededges, distance_data::closenodes_range, distCloseNodesPrintLostNodeInfo(), csr_range::end, EQ, FALSE, graph_get_nNodes(), GRAPH::head, nnodes, SCIP_Bool, SCIP_CALL_ABORT, SCIP_Real, SCIPallocCleanBufferArray, SCIPdebugMessage, SCIPfreeCleanBufferArray, csr_range::start, GRAPH::tail, and TRUE.

Referenced by extreduce_distCloseNodesAreValid().

◆ treeGetCounters()

static void treeGetCounters	(	const GRAPH *	graph,
		const EXTDATA *	extdata,
		int	edgecount[],
		int	degreecount[],
		SCIP_Bool *	treeIsFlawed
	)

static

computes counters for degrees and edges

Parameters

graph	graph data structure
extdata	extension data
edgecount	edge count
degreecount	degree count
treeIsFlawed	is tree flawed?)

Definition at line 648 of file extreduce_dbg.c.

References flipedge, graph_edge_printInfo(), GRAPH::head, GRAPH::tail, extension_data::tree_deg, extension_data::tree_edges, extension_data::tree_nedges, and TRUE.

Referenced by extreduce_treeIsFlawed().

◆ treeResetCounters()

static void treeResetCounters	(	const GRAPH *	graph,
		const EXTDATA *	extdata,
		int	edgecount[],
		int	degreecount[]
	)

static

reset counters

Parameters

graph	graph data structure
extdata	extension data
edgecount	edge count
degreecount	degree count

Definition at line 698 of file extreduce_dbg.c.

References graph_get_nEdges(), graph_get_nNodes(), GRAPH::head, nnodes, GRAPH::tail, extension_data::tree_edges, and extension_data::tree_nedges.

Referenced by extreduce_treeIsFlawed().

◆ treeDegreesAreFlawed()

static SCIP_Bool treeDegreesAreFlawed	(	const GRAPH *	graph,
		const EXTDATA *	extdata,
		const int	degreecount[]
	)

static

are the degrees flawed?

Parameters

graph	graph data structure
extdata	extension data
degreecount	degree count

Definition at line 735 of file extreduce_dbg.c.

References FALSE, GRAPH::head, extension_data::tree_deg, extension_data::tree_edges, extension_data::tree_nedges, and TRUE.

Referenced by extreduce_treeIsFlawed().

◆ treeLeavesAreFlawed()

static SCIP_Bool treeLeavesAreFlawed	(	const GRAPH *	graph,
		const EXTDATA *	extdata,
		const int	degreecount[]
	)

static

flaw with the tree leaves?

Parameters

graph	graph data structure
extdata	extension data
degreecount	degree count

Definition at line 764 of file extreduce_dbg.c.

References FALSE, GRAPH::head, extension_data::tree_edges, extension_data::tree_leaves, extension_data::tree_nedges, extension_data::tree_nleaves, and TRUE.

Referenced by extreduce_treeIsFlawed().

◆ treeInnerNodesAreFlawed()

static SCIP_Bool treeInnerNodesAreFlawed	(	const GRAPH *	graph,
		const EXTDATA *	extdata,
		const int	degreecount[]
	)

static

flaw with the inner nodes?

Parameters

graph	graph data structure
extdata	extension data
degreecount	degree count

Definition at line 810 of file extreduce_dbg.c.

References FALSE, GRAPH::head, extension_data::tree_edges, extension_data::tree_innerNodes, extension_data::tree_nedges, extension_data::tree_ninnerNodes, and TRUE.

Referenced by extreduce_treeIsFlawed().

◆ treeDistsAreFlawed()

static SCIP_Bool treeDistsAreFlawed	(	const GRAPH *	graph,
		const EXTDATA *	extdata
	)

static

are distance values of tree flawed?

Parameters

graph	graph data structure
extdata	extension data

Definition at line 854 of file extreduce_dbg.c.

References FALSE, graph_get_nNodes(), graph_pc_isPcMw(), nnodes, extension_data::pcdata, pcmw_specific_data::pcSdToNode, SCIP_Bool, extension_data::tree_bottleneckDistNode, and TRUE.

Referenced by extreduce_treeIsFlawed().

◆ 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_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_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_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_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_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