extreduce_data.c File Reference

Detailed Description

plain data storages for extended reduction techniques for Steiner tree problems

Author

Daniel Rehfeldt

This file implements several (relatively) plain data storages needed for extended reduction techniques. Basically data transfer objects with additional setup, free, and cleaning methods.

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

Definition in file extreduce_data.c.

#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
static void	postCleanSDs (MLDISTS *sds)
static void	postCleanMSTs (CSRDEPO *msts)
void	extreduce_extCompClean (SCIP *scip, const GRAPH *graph, const EXTCOMP *extcomp, SCIP_Bool unhash, EXTDATA *extdata)
SCIP_RETCODE	extreduce_extPermaInit (SCIP *scip, enum EXTRED_MODE mode, const GRAPH *graph, STP_Bool *edgedeleted, EXTPERMA **extpermanent)
void	extreduce_extPermaAddRandnumgen (SCIP_RANDNUMGEN *randnumgen, EXTPERMA *extpermanent)
SCIP_RETCODE	extreduce_extPermaAddMLdistsbiased (SCIP *scip, EXTPERMA *extpermanent)
SCIP_Bool	extreduce_extPermaIsClean (const GRAPH *graph, const EXTPERMA *extperm)
void	extreduce_extPermaFree (SCIP *scip, EXTPERMA **extpermanent)
void	extreduce_extdataClean (EXTDATA *extdata)
void	extreduce_reddataClean (REDDATA *reddata)
void	extreduce_pcdataClean (PCDATA *pcdata)
SCIP_Bool	extreduce_extdataIsClean (const GRAPH *graph, const EXTDATA *extdata)
SCIP_Bool	extreduce_reddataIsClean (const GRAPH *graph, const REDDATA *reddata)
SCIP_Bool	extreduce_pcdataIsClean (const GRAPH *graph, const PCDATA *pcdata)

Function Documentation

postCleanSDs()

static void postCleanSDs ( MLDISTS *  sds )

inlinestatic

helper function

Parameters

sds	distance structure

Definition at line 44 of file extreduce_data.c.

References extreduce_mldistsLevelRemoveTop(), and extreduce_mldistsNlevels().

Referenced by extreduce_extCompClean().

postCleanMSTs()

static void postCleanMSTs ( CSRDEPO *  msts )

inlinestatic

helper function

Parameters

msts	CSR depository containing MSTs

Definition at line 61 of file extreduce_data.c.

References graph_csrdepo_clean(), and graph_csrdepo_getNcsrs().

Referenced by extreduce_extCompClean().

extreduce_extCompClean()

void extreduce_extCompClean	(	SCIP *	scip,
		const GRAPH *	graph,
		const EXTCOMP *	extcomp,
		SCIP_Bool	unhash,
		EXTDATA *	extdata
	)

cleans-up after trying to rule out a component

Parameters

scip	SCIP
graph	graph data structure
extcomp	component to be cleaned for
unhash	unhash component?
extdata	extension data

Definition at line 76 of file extreduce_data.c.

References initial_extension_component::compedges, extInitialCompIsGenStar(), extReddataHasBiasedSds(), extreduce_extdataClean(), extreduce_extdataIsClean(), extreduce_pcdataClean(), extreduce_pcdataIsClean(), extreduce_reddataClean(), extreduce_reddataIsClean(), FALSE, initial_extension_component::genstar_centeredge, graph_edge_isInRange(), graph_pseudoAncestors_unhashEdge(), GRAPH::head, reduction_data::msts_comp, reduction_data::msts_levelbase, initial_extension_component::ncompedges, extension_data::pcdata, postCleanMSTs(), postCleanSDs(), reduction_data::pseudoancestor_mark, GRAPH::pseudoancestors, extension_data::reddata, SCIP_Bool, extension_data::sdeq_edgesIsForbidden, extension_data::sdeq_hasForbiddenEdges, reduction_data::sds_horizontal, reduction_data::sds_vertical, reduction_data::sdsbias_horizontal, reduction_data::sdsbias_vertical, STP_Vectype, StpVecFree, StpVecGetSize, GRAPH::tail, and extension_data::tree_deg.

Referenced by extProcessComponent().

extreduce_extPermaInit()

SCIP_RETCODE extreduce_extPermaInit	(	SCIP *	scip,
		enum EXTRED_MODE	mode,
		const GRAPH *	graph,
		STP_Bool *	edgedeleted,
		EXTPERMA **	extpermanent
	)

initialize permanent extension data struct NOTE: Sets distdata and reddata entries to NULL, since non-owned

Parameters

scip	SCIP
mode	mode
graph	graph data structure
edgedeleted	edge array to mark which directed edge can be removed
extpermanent	(uninitialized) extension data

Definition at line 162 of file extreduce_data.c.

References extension_data_permanent::bottleneckDistNode, extension_data_permanent::contration, extension_data_permanent::dcmst, extension_data_permanent::distdata_biased, extension_data_permanent::distdata_default, extension_data_permanent::edgedeleted, extred_fast, extred_full, extreduce_contractionInit(), extreduce_extPermaIsClean(), extreduce_getMaxTreeDepth(), extreduce_mldistsInit(), FALSE, graph_csrdepo_init(), graph_get_nNodes(), graph_getIsTermArray(), graph_pc_isPcMw(), extension_data_permanent::isterm, GRAPH::mark, extension_data_permanent::mode, extension_data_permanent::msts_comp, extension_data_permanent::msts_levelbase, nnodes, extension_data_permanent::nnodes, NULL, extension_data_permanent::pcSdToNode, extension_data_permanent::randnumgen, extension_data_permanent::redcostdata, extension_data_permanent::redcostEqualAllow, reduce_dcmstInit(), reduce_impliedNodesGet(), extension_data_permanent::result, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemory, SCIPallocMemoryArray, extension_data_permanent::sds_horizontal, extension_data_permanent::sds_vertical, extension_data_permanent::sdsbias_horizontal, extension_data_permanent::sdsbias_vertical, extension_data_permanent::solIsValid, STP_EXT_MAXDFSDEPTH, STP_EXT_MAXDFSDEPTH_GUARD, STP_EXT_MAXGRAD, STP_EXTTREE_MAXNEDGES, STP_EXTTREE_MAXNLEAVES, STP_EXTTREE_MAXNLEAVES_GUARD, STP_Vectype, extension_data_permanent::tree_deg, extension_data_permanent::tree_maxdepth, extension_data_permanent::tree_maxnedges, extension_data_permanent::tree_maxnleaves, TRUE, and extension_data_permanent::useSdBias.

Referenced by extCheckArc(), extCheckEdge(), extCheckNode(), extDeleteNodes(), extInit(), extreduce_init(), fixVarsRedbased(), and reduce_termsepaDa().

extreduce_extPermaAddRandnumgen()

void extreduce_extPermaAddRandnumgen	(	SCIP_RANDNUMGEN *	randnumgen,
		EXTPERMA *	extpermanent
	)

adds random number generator

Parameters

randnumgen	random number generator to add (NON-OWNED!)
extpermanent	(initialized) extension data

Definition at line 267 of file extreduce_data.c.

References extension_data_permanent::randnumgen.

Referenced by reduce_da().

extreduce_extPermaAddMLdistsbiased()

SCIP_RETCODE extreduce_extPermaAddMLdistsbiased	(	SCIP *	scip,
		EXTPERMA *	extpermanent
	)

adds biased ML distances containers

Parameters

scip	SCIP
extpermanent	(initialized) extension data

Definition at line 279 of file extreduce_data.c.

References extreduce_mldistsInit(), FALSE, SCIP_Bool, SCIP_CALL, SCIP_OKAY, extension_data_permanent::sdsbias_horizontal, extension_data_permanent::sdsbias_vertical, STP_EXT_MAXDFSDEPTH_GUARD, STP_EXT_MAXGRAD, STP_EXTTREE_MAXNLEAVES_GUARD, and TRUE.

Referenced by extreduce_pseudoDeleteNodes().

extreduce_extPermaIsClean()

SCIP_Bool extreduce_extPermaIsClean	(	const GRAPH *	graph,
		const EXTPERMA *	extperm
	)

initialize permanent extension data struct

Parameters

graph	graph data structure
extperm	extension data

Definition at line 305 of file extreduce_data.c.

References extension_data_permanent::bottleneckDistNode, extension_data_permanent::edgedeleted, EQ, extreduce_mldistsIsEmpty(), extreduce_mldistsNlevels(), FALSE, graph_csrdepo_isEmpty(), graph_get_nNodes(), extension_data_permanent::msts_comp, extension_data_permanent::msts_levelbase, nnodes, extension_data_permanent::nnodes, NULL, extension_data_permanent::pcSdToNode, SCIP_Real, SCIPdebugMessage, extension_data_permanent::sds_horizontal, extension_data_permanent::sds_vertical, extension_data_permanent::sdsbias_horizontal, extension_data_permanent::sdsbias_vertical, extension_data_permanent::tree_deg, and TRUE.

Referenced by extreduce_checkArc(), extreduce_checkComponent(), extreduce_checkEdge(), and extreduce_extPermaInit().

extreduce_extPermaFree()

void extreduce_extPermaFree	(	SCIP *	scip,
		EXTPERMA **	extpermanent
	)

frees extension data

Parameters

scip	SCIP
extpermanent	extension data

Definition at line 386 of file extreduce_data.c.

References extension_data_permanent::bottleneckDistNode, extension_data_permanent::contration, extension_data_permanent::dcmst, extreduce_contractionFree(), extreduce_mldistsFree(), graph_csrdepo_free(), extension_data_permanent::isterm, extension_data_permanent::msts_comp, extension_data_permanent::msts_levelbase, extension_data_permanent::nnodes, extension_data_permanent::pcSdToNode, reduce_dcmstFree(), SCIPfreeMemory, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, extension_data_permanent::sds_horizontal, extension_data_permanent::sds_vertical, extension_data_permanent::sdsbias_horizontal, extension_data_permanent::sdsbias_vertical, StpVecFree, and extension_data_permanent::tree_deg.

Referenced by extCheckArc(), extCheckEdge(), extCheckNode(), extDeleteNodes(), extFree(), extreduce_exit(), and fixVarsRedbased().

extreduce_extdataClean()

void extreduce_extdataClean

(

EXTDATA *

extdata

)

cleans extension data

Parameters

extdata

extension data

Definition at line 426 of file extreduce_data.c.

References extension_data::extstack_ncomponents, extension_data::ncostupdatestalls, extension_data::tree_cost, extension_data::tree_depth, extension_data::tree_nDelUpArcs, extension_data::tree_nedges, extension_data::tree_ninnerNodes, extension_data::tree_nleaves, extension_data::tree_root, and extension_data::tree_starcenter.

Referenced by extreduce_extCompClean().

extreduce_reddataClean()

void extreduce_reddataClean

(

REDDATA *

reddata

)

cleans reduction data

Parameters

reddata

reduction data

Definition at line 446 of file extreduce_data.c.

References reduction_data::contration, reduction_data::redcost_nlevels, reduction_data::redcost_treecosts, and SCIP_Real.

Referenced by extreduce_checkComponent(), and extreduce_extCompClean().

extreduce_pcdataClean()

void extreduce_pcdataClean

(

PCDATA *

pcdata

)

cleans PC data

Parameters

pcdata

PC data

Definition at line 464 of file extreduce_data.c.

References pcmw_specific_data::tree_innerPrize.

Referenced by extreduce_extCompClean().

extreduce_extdataIsClean()

SCIP_Bool extreduce_extdataIsClean	(	const GRAPH *	graph,
		const EXTDATA *	extdata
	)

is the extension data clean?

Parameters

graph	graph data structure
extdata	extension data

Definition at line 475 of file extreduce_data.c.

References EQ, extension_data::extstack_ncomponents, FALSE, graph_get_nEdges(), graph_get_nNodes(), extension_data::ncostupdatestalls, nnodes, extension_data::sdeq_edgesIsForbidden, extension_data::tree_bottleneckDistNode, extension_data::tree_cost, extension_data::tree_deg, extension_data::tree_depth, extension_data::tree_nDelUpArcs, extension_data::tree_nedges, extension_data::tree_ninnerNodes, extension_data::tree_nleaves, extension_data::tree_root, extension_data::tree_starcenter, and TRUE.

Referenced by extProcessComponent(), and extreduce_extCompClean().

extreduce_reddataIsClean()

SCIP_Bool extreduce_reddataIsClean	(	const GRAPH *	graph,
		const REDDATA *	reddata
	)

is the reduction data clean?

Parameters

graph	graph data structure
reddata	reduction data

Definition at line 572 of file extreduce_data.c.

References EQ, FALSE, graph_pseudoAncestorsGetHashArraySize(), reduction_data::pseudoancestor_mark, GRAPH::pseudoancestors, reduction_data::redcost_nlevels, reduction_data::redcost_treecosts, SCIP_Real, and TRUE.

Referenced by extProcessComponent(), and extreduce_extCompClean().

extreduce_pcdataIsClean()

SCIP_Bool extreduce_pcdataIsClean	(	const GRAPH *	graph,
		const PCDATA *	pcdata
	)

is the reduction data clean?

Parameters

graph	graph data structure
pcdata	PC data

Definition at line 605 of file extreduce_data.c.

References EQ, FALSE, graph_get_nNodes(), graph_pc_isPc(), nnodes, pcmw_specific_data::nPcSdCands, pcmw_specific_data::pcSdStart, pcmw_specific_data::pcSdToNode, pcmw_specific_data::tree_innerPrize, and TRUE.

Referenced by extProcessComponent(), and extreduce_extCompClean().