Detailed Description

Transformation algorithms for Steiner problems.

Author: Daniel Rehfeldt

This includes method for transformations (or reductions) between the different Steiner problem classes.

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

Definition in file graph_trans.c.

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

Macros
#define	TRANS_MAXPRIZESUM 1e09

Functions
static SCIP_RETCODE	initCostOrgPc (SCIP scip, GRAPH g)

static SCIP_Bool	isNonLeaf_pretransPc (SCIP scip, const GRAPH g, int vertex)

static void	markNonLeafTerms_pretransPc (SCIP scip, GRAPH g)

static void	nwptstpSetRoot (GRAPH *g)

SCIP_RETCODE	graph_transPc (SCIP scip, GRAPH graph)

SCIP_RETCODE	graph_transPc2Spg (SCIP scip, PRESOL presol, GRAPH *graph)

SCIP_RETCODE	graph_transRpc (SCIP scip, GRAPH graph)

SCIP_RETCODE	graph_transRpc2SpgTrivial (SCIP scip, GRAPH g)

SCIP_RETCODE	graph_transRpc2FixedProper (SCIP scip, PRESOL presol, GRAPH *graph)

SCIP_RETCODE	graph_transMw (SCIP scip, GRAPH graph)

SCIP_RETCODE	graph_transRmw (SCIP scip, GRAPH graph)

SCIP_RETCODE	graph_transPcmw2rooted (SCIP scip, GRAPH graph, SCIP_Real fixprize, SCIP_Bool verbose)

SCIP_RETCODE	graph_transPcGetSap (SCIP scip, GRAPH graph, GRAPH *newgraph, SCIP_Real offset)

SCIP_RETCODE	graph_transPcGetRsap (SCIP scip, GRAPH graph, GRAPH *newgraph, const int rootcands, int nrootcands, int saproot)

SCIP_Bool	graph_transRpcToSpgIsStable (const GRAPH *graph, SCIP_Real primalbound)

SCIP_RETCODE	graph_transRpcGetSpg (SCIP scip, const GRAPH graph, SCIP_Real primalbound, SCIP_Real offset, int edgemap_new2org, GRAPH *newgraph)

void	graph_transGstpClean (PRESOL presol, GRAPH graph)

SCIP_RETCODE	graph_transNw2pc (SCIP scip, PRESOL presol, GRAPH *g)

SCIP_RETCODE	graph_transNw2sap (SCIP scip, PRESOL presol, GRAPH *g)

SCIP_RETCODE	graph_transNw (SCIP scip, PRESOL presol, GRAPH *g)

Macro Definition Documentation

◆ TRANS_MAXPRIZESUM

#define TRANS_MAXPRIZESUM 1e09

Definition at line 35 of file graph_trans.c.

Referenced by graph_transRpcToSpgIsStable().

Function Documentation

◆ initCostOrgPc()

static SCIP_RETCODE initCostOrgPc	(	SCIP *	scip,
		GRAPH *	g
	)

static

initializes cost_org_pc array (call right after transformation to extended has been performed)

Parameters

scip	SCIP
g	the graph

Definition at line 40 of file graph_trans.c.

References BMScopyMemoryArray, GRAPH::cost, GRAPH::cost_org_pc, GRAPH::edges, GRAPH::extended, graph_pc_isPc(), SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIPallocMemoryArray.

Referenced by graph_transPc(), and graph_transRpc().

◆ isNonLeaf_pretransPc()

static SCIP_Bool isNonLeaf_pretransPc	(	SCIP *	scip,
		const GRAPH *	g,
		int	vertex
	)

inlinestatic

is vertex a non-leaf (call before graph transformation was performed)

Parameters

scip	SCIP
g	the graph
vertex	node check

Definition at line 61 of file graph_trans.c.

References GRAPH::cost, EAT_LAST, FALSE, GRAPH::ieat, GRAPH::inpbeg, GRAPH::prize, SCIP_Real, SCIPisGT(), and TRUE.

Referenced by graph_transRpc2FixedProper(), and markNonLeafTerms_pretransPc().

◆ markNonLeafTerms_pretransPc()

static void markNonLeafTerms_pretransPc	(	SCIP *	scip,
		GRAPH *	g
	)

static

remove non-leaf terminals by edge weight shifting (call before graph transformation was performed, call only from graph transformation method!)

Parameters

scip	SCIP
g	the graph

Definition at line 84 of file graph_trans.c.

References graph_knot_chg(), Is_term, isNonLeaf_pretransPc(), GRAPH::knots, nnodes, STP_TERM_NONLEAF, and GRAPH::term.

Referenced by graph_transPc(), and graph_transRpc().

◆ nwptstpSetRoot()

static void nwptstpSetRoot ( GRAPH * g )

static

sets root

Parameters

g the graph

Definition at line 106 of file graph_trans.c.

References GRAPH::grad, graph_get_nNodes(), graph_knotIsNWLeaf(), Is_term, nnodes, GRAPH::source, STP_NWPTSPG, GRAPH::stp_type, GRAPH::term, GRAPH::terms, and UNKNOWN.

Referenced by graph_transNw().

◆ graph_transPc()

SCIP_RETCODE graph_transPc	(	SCIP *	scip,
		GRAPH *	graph
	)

alters the graph for prize collecting problems

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 154 of file graph_trans.c.

References GRAPH::edges, GRAPH::esize, GRAPH::extended, FARAWAY, flipedge, graph_edge_add(), graph_knot_add(), graph_knot_chg(), graph_pc_initTerm2Edge(), graph_pc_shiftNonLeafCosts(), graph_pc_term2edgeIsConsistent(), graph_resize(), graph_valid(), GRAPH::head, initCostOrgPc(), Is_nonleafTerm, Is_term, GRAPH::knots, GRAPH::ksize, markNonLeafTerms_pretransPc(), nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, GRAPH::orgsource, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisGE(), GRAPH::source, STP_MWCSP, STP_PCSPG, STP_TERM, STP_TERM_PSEUDO, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, TERM2EDGE_FIXEDTERM, TERM2EDGE_NONLEAFTERM, GRAPH::terms, and TRUE.

Referenced by checkSdWalk(), graph_load(), graph_transMw(), graphBuildV5E5(), localExtendPc(), localInsertion2pc(), localKeyPathExchangePc(), localKeyPathExchangePc2(), localKeyVertexPc(), localKeyVertexPc2(), and stptest_graphSetUpPcExtended().

◆ graph_transPc2Spg()

SCIP_RETCODE graph_transPc2Spg	(	SCIP *	scip,
		PRESOL *	presol,
		GRAPH *	graph
	)

alters the graph for prize collecting problems and transforms it to an SPG

Parameters

scip	SCIP data structure
presol	presolving struct
graph	the graph

Definition at line 257 of file graph_trans.c.

References BLOCKED, GRAPH::edges, EQ, GRAPH::esize, GRAPH::extended, FALSE, FARAWAY, presolve_info::fixed, graph_edge_addBi(), graph_knot_add(), graph_knot_chg(), graph_resize(), Is_term, GRAPH::knots, GRAPH::ksize, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPfreeMemoryArrayNull, SCIPisGE(), SCIPisLT(), GRAPH::source, STP_SPG, STP_TERM, STP_TERM_NONE, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, and GRAPH::terms.

Referenced by graph_load().

◆ graph_transRpc()

SCIP_RETCODE graph_transRpc	(	SCIP *	scip,
		GRAPH *	graph
	)

alters the graph for rooted prize collecting problems

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 373 of file graph_trans.c.

References GRAPH::edges, EQ, GRAPH::esize, GRAPH::extended, FARAWAY, flipedge, graph_edge_add(), graph_knot_add(), graph_knot_chg(), graph_pc_initTerm2Edge(), graph_pc_knotToFixedTermProperty(), graph_pc_shiftNonLeafCosts(), graph_resize(), GRAPH::head, initCostOrgPc(), Is_nonleafTerm, Is_term, GRAPH::knots, GRAPH::ksize, markNonLeafTerms_pretransPc(), nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, nterms, GRAPH::orgsource, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisLT(), GRAPH::source, STP_RPCSPG, STP_TERM, STP_TERM_NONE, STP_TERM_PSEUDO, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, TERM2EDGE_NONLEAFTERM, GRAPH::terms, and TRUE.

Referenced by graph_load(), graph_transNw2pc(), graph_transRpc2FixedProper(), and stptest_graphSetUpRpcExtended().

◆ graph_transRpc2SpgTrivial()

SCIP_RETCODE graph_transRpc2SpgTrivial	(	SCIP *	scip,
		GRAPH *	g
	)

alters the graph from rooted prize collecting problems to SPG if there are not potential terminals. NOTE: deletes some PC data, but keeps history, in order to be able to reconstruct original optimal solution.

Parameters

scip	SCIP data structure
g	the graph

Definition at line 505 of file graph_trans.c.

References GRAPH::costbudget, graph_pc_2orgcheck(), graph_pc_nNonLeafTerms(), graph_pc_nProperPotentialTerms(), GRAPH::prize, SCIP_ERROR, SCIP_OKAY, SCIPerrorMessage, SCIPfreeMemoryArrayNull, STP_RPCSPG, STP_SPG, GRAPH::stp_type, and GRAPH::term2edge.

Referenced by reduce_redLoopPc().

◆ graph_transRpc2FixedProper()

SCIP_RETCODE graph_transRpc2FixedProper	(	SCIP *	scip,
		PRESOL *	presol,
		GRAPH *	graph
	)

changes the graph for rooted prize collecting problems such that no proper potential terminal are fixed

Parameters

scip	SCIP data structure
presol	presolving struct
graph	the graph

Definition at line 531 of file graph_trans.c.

References BLOCKED, GRAPH::edges, GRAPH::esize, GRAPH::extended, FARAWAY, presolve_info::fixed, graph_edge_addBi(), graph_knot_add(), graph_knot_chg(), graph_resize(), graph_transRpc(), Is_term, isNonLeaf_pretransPc(), GRAPH::knots, GRAPH::ksize, nnodes, nterms, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisLT(), GRAPH::source, STP_TERM, STP_TERM_NONE, and GRAPH::term.

Referenced by graph_load().

◆ graph_transMw()

SCIP_RETCODE graph_transMw	(	SCIP *	scip,
		GRAPH *	graph
	)

alters the graph for MWCS problems

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 632 of file graph_trans.c.

References GRAPH::cost, EAT_LAST, graph_get_nNodes(), graph_knot_chg(), graph_transPc(), GRAPH::ieat, GRAPH::inpbeg, Is_term, nnodes, nterms, NULL, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), STP_MWCSP, GRAPH::stp_type, GRAPH::term, and GRAPH::terms.

Referenced by graph_load(), and localKeyPathExchangeMw().

◆ graph_transRmw()

SCIP_RETCODE graph_transRmw	(	SCIP *	scip,
		GRAPH *	graph
	)

alters the graph for RMWCS problems

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 687 of file graph_trans.c.

References GRAPH::cost, EAT_LAST, GRAPH::edges, EQ, GRAPH::esize, GRAPH::extended, FARAWAY, flipedge, GRAPH::grad, graph_edge_add(), graph_knot_add(), graph_knot_chg(), graph_pc_initTerm2Edge(), graph_pc_knotToFixedTermProperty(), graph_resize(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::ksize, LE, nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, NULL, GRAPH::orgsource, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), SCIPisGT(), SCIPisLT(), GRAPH::source, STP_RMWCSP, STP_TERM, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, GRAPH::terms, and TRUE.

Referenced by graph_load(), and stptest_graphSetUpRmwExtended().

◆ graph_transPcmw2rooted()

SCIP_RETCODE graph_transPcmw2rooted	(	SCIP *	scip,
		GRAPH *	graph,
		SCIP_Real	fixprize,
		SCIP_Bool	verbose
	)

transforms PCSPG or MWCSP to RPCSPG or RMWCSP if possible

Parameters

scip	SCIP data structure
graph	the graph
fixprize	prize at which to make terminals
verbose	be verbose?

Definition at line 809 of file graph_trans.c.

References GRAPH::cost, EAT_LAST, GRAPH::extended, FARAWAY, flipedge, GRAPH::grad, graph_edge_redirect(), graph_knot_chg(), graph_knot_del(), graph_pc_getTwinTerm(), graph_pc_isRootedPcMw(), graph_pc_knotToFixedTermProperty(), graph_pc_knotToNonTermProperty(), graph_pc_presolExit(), graph_valid(), GRAPH::head, Is_pseudoTerm, Is_term, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, GRAPH::rootedgeprevs, SCIP_OKAY, SCIPdebugMessage, SCIPisGE(), GRAPH::source, STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_TERM_NONE, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, TERM2EDGE_NOTERM, GRAPH::terms, and TRUE.

Referenced by propgraphApplyBoundchanges(), reduce_redLoopMw(), and reduce_redLoopPc().

◆ graph_transPcGetSap()

SCIP_RETCODE graph_transPcGetSap	(	SCIP *	scip,
		GRAPH *	graph,
		GRAPH **	newgraph,
		SCIP_Real *	offset
	)

obtains an SAP from prize collecting problems

Parameters

scip	SCIP data structure
graph	the graph
newgraph	the new graph
offset	offset (in/out)

Definition at line 931 of file graph_trans.c.

References GRAPH::cost, EAT_LAST, GRAPH::edges, GRAPH::esize, GRAPH::extended, FALSE, FARAWAY, flipedge, graph_copy(), graph_edge_add(), graph_edge_redirect(), graph_knot_add(), graph_pc_getNonLeafTermOffset(), graph_pc_isPc(), graph_pc_knotIsDummyTerm(), graph_pc_presolExit(), graph_pc_presolInit(), graph_resize(), GRAPH::ieat, GRAPH::inpbeg, Is_pseudoTerm, Is_term, GRAPH::knots, GRAPH::ksize, nnodes, nterms, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisLT(), SCIPisZero(), GRAPH::source, STP_PCSPG, STP_SAP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by dualascent_execPcMw(), reduce_daPcMw(), and testDaPathsPcMw3EdgesWorks().

◆ graph_transPcGetRsap()

SCIP_RETCODE graph_transPcGetRsap	(	SCIP *	scip,
		GRAPH *	graph,
		GRAPH **	newgraph,
		const int *	rootcands,
		int	nrootcands,
		int	saproot
	)

builds new rooted SAP graph for prize-collecting problems (with given root for SAP)

Parameters

scip	SCIP data structure
graph	the graph
newgraph	the new graph
rootcands	array containing all vertices that could be used as root
nrootcands	number of all vertices that could be used as root
saproot	the root of the new SAP

Definition at line 1043 of file graph_trans.c.

References GRAPH::cost, EAT_LAST, GRAPH::edges, GRAPH::esize, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_copy(), graph_edge_del(), graph_edge_redirect(), graph_knot_chg(), graph_knot_del(), graph_pc_2transcheck(), graph_pc_initPrizes(), graph_pc_initTerm2Edge(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotToFixedTermProperty(), graph_pc_presolExit(), graph_pc_presolInit(), GRAPH::head, Is_pseudoTerm, Is_term, GRAPH::knots, GRAPH::ksize, GRAPH::mark, nnodes, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, GRAPH::source, STP_SAP, STP_TERM, STP_TERM_NONE, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::term2edge, TERM2EDGE_FIXEDTERM, TERM2EDGE_NOTERM, and TRUE.

Referenced by reduce_daPcMw().

◆ graph_transRpcToSpgIsStable()

SCIP_Bool graph_transRpcToSpgIsStable	(	const GRAPH *	graph,
		SCIP_Real	primalbound
	)

is a transformation stable?

Parameters

graph	the graph
primalbound	primal bound for graph

Definition at line 1188 of file graph_trans.c.

References FALSE, FARAWAY, GE, graph_get_nNodes(), GT, LE, LT, nnodes, GRAPH::prize, SCIP_Real, STP_RPCSPG, GRAPH::stp_type, and TRANS_MAXPRIZESUM.

Referenced by graph_transRpcGetSpg(), and reduce_impliedProfitBasedRpc().

◆ graph_transRpcGetSpg()

SCIP_RETCODE graph_transRpcGetSpg	(	SCIP *	scip,
		const GRAPH *	graph,
		SCIP_Real	primalbound,
		SCIP_Real *	offset,
		int **	edgemap_new2org,
		GRAPH **	newgraph
	)

constructs equivalent SPG for given RPC

Parameters

scip	SCIP data structure
graph	the graph
primalbound	primal bound for graph
offset	offset (in/out)
edgemap_new2org	maps edges
newgraph	the new graph

Definition at line 1217 of file graph_trans.c.

References BLOCKED, GRAPH::cost, EAT_LAST, GRAPH::edges, EQ, GRAPH::extended, FARAWAY, flipedge, GRAPH::grad, graph_edge_addBi(), graph_get_nNodes(), graph_init(), graph_isMarked(), graph_knot_add(), graph_knot_isInRange(), graph_knot_printInfo(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsNonLeafTerm(), graph_pc_nNonLeafTerms(), graph_pc_nProperPotentialTerms(), graph_transRpcToSpgIsStable(), GT, GRAPH::head, Is_term, GRAPH::knots, LT, GRAPH::mark, MAX, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeMemoryArray, GRAPH::source, STP_SPG, STP_TERM, STP_TERM_NONE, GRAPH::stp_type, and GRAPH::term.

Referenced by reduce_impliedProfitBasedRpc().

◆ graph_transGstpClean()

void graph_transGstpClean	(	PRESOL *	presol,
		GRAPH *	graph
	)

cleans up GSTP after transformation todo also compute a better big M than just the trivial one, e.g. by building an SAP and computing bound todo move the whole transformation here from graph_load, quite hacky at the moment

Parameters

presol	presolving struct
graph	the graph

Definition at line 1381 of file graph_trans.c.

References BLOCKED, GRAPH::cost, EQ, presolve_info::fixed, graph_get_nEdges(), GRAPH::head, Is_term, GRAPH::knots, LE, GRAPH::norgmodelknots, GRAPH::norgmodelterms, SCIP_Real, STP_GSTP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and GRAPH::terms.

Referenced by graph_load().

◆ graph_transNw2pc()

SCIP_RETCODE graph_transNw2pc	(	SCIP *	scip,
		PRESOL *	presol,
		GRAPH *	g
	)

alters the graph for node-weighted Steiner tree problems

Parameters

scip	SCIP data structure
presol	presolving struct
g	the graph

Definition at line 1420 of file graph_trans.c.

References BLOCKED, GRAPH::cost, EQ, FARAWAY, presolve_info::fixed, GE, graph_get_nEdges(), graph_get_nNodes(), graph_knot_chg(), graph_transRpc(), GT, Is_term, LT, nnodes, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, GRAPH::source, STP_TERM, GRAPH::term, and GRAPH::terms.

Referenced by graph_transNw().

◆ graph_transNw2sap()

SCIP_RETCODE graph_transNw2sap	(	SCIP *	scip,
		PRESOL *	presol,
		GRAPH *	g
	)

alters the graph for node-weighted Steiner tree problems

Parameters

scip	SCIP data structure
presol	presolving struct
g	the graph

Definition at line 1487 of file graph_trans.c.

References GRAPH::cost, EAT_LAST, presolve_info::fixed, graph_get_nNodes(), GRAPH::ieat, GRAPH::inpbeg, Is_term, nnodes, GRAPH::prize, SCIP_OKAY, SCIP_Real, and GRAPH::term.

Referenced by graph_transNw().

◆ graph_transNw()

SCIP_RETCODE graph_transNw	(	SCIP *	scip,
		PRESOL *	presol,
		GRAPH *	g
	)

alters the graph for node-weighted Steiner tree problems

Parameters

scip	SCIP data structure
presol	presolving struct
g	the graph

Definition at line 1519 of file graph_trans.c.

References graph_transNw2pc(), graph_transNw2sap(), nwptstpSetRoot(), SCIP_CALL, SCIP_OKAY, STP_NWPTSPG, and GRAPH::stp_type.

Referenced by graph_load().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ TRANS_MAXPRIZESUM

Function Documentation

◆ initCostOrgPc()

◆ isNonLeaf_pretransPc()

◆ markNonLeafTerms_pretransPc()

◆ nwptstpSetRoot()

◆ graph_transPc()

◆ graph_transPc2Spg()

◆ graph_transRpc()

◆ graph_transRpc2SpgTrivial()

◆ graph_transRpc2FixedProper()

◆ graph_transMw()

◆ graph_transRmw()

◆ graph_transPcmw2rooted()

◆ graph_transPcGetSap()

◆ graph_transPcGetRsap()

◆ graph_transRpcToSpgIsStable()

◆ graph_transRpcGetSpg()

◆ graph_transGstpClean()

◆ graph_transNw2pc()

◆ graph_transNw2sap()

◆ graph_transNw()