Detailed Description

includes several methods for Steiner problem graphs

Author: Thorsten Koch; Daniel Rehfeldt

This file contains several basic methods to process Steiner problem graphs. A graph can not be reduced in terms of edge or node size, but edges can be marked as EAT_FREE (to not be used anymore) and nodes may have degree one. The method 'graph_pack()' can be used to build a new graph that discards these nodes and edges.

Definition in file graph_base.c.

#include "scip/misc.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "portab.h"
#include "misc_stp.h"
#include "graph.h"
#include "reduce.h"
#include "stpvector.h"
#include "heur_tm.h"

Go to the source code of this file.

Functions
static SCIP_Bool	graphisValidPcMw (SCIP scip, const GRAPH g, SCIP_Bool *nodevisited)

static SCIP_RETCODE	packPcMwVanished (SCIP scip, GRAPH g_old)

static SCIP_RETCODE	packPcMwInit (SCIP scip, int nnodes_new, GRAPH g_old, GRAPH *g_new)

static void	packNodes (SCIP scip, GRAPH g_old, GRAPH *g_new)

static SCIP_RETCODE	packPseudoAncestors (SCIP scip, const GRAPH g_old, GRAPH *g_new)

static SCIP_RETCODE	packEdges (SCIP scip, const int old2newNode, GRAPH g_old, int nnodes, int nedges, GRAPH g_new)

SCIP_RETCODE	graph_buildCompleteGraph (SCIP scip, GRAPH *g, int nnodes)

void	graph_getCsr (const GRAPH g, int RESTRICT edgearr, int RESTRICT tailarr, int RESTRICT start, int *nnewedges)

void	graph_getEdgeCosts (const GRAPH graph, SCIP_Real RESTRICT cost, SCIP_Real *RESTRICT costrev)

void	graph_getEdgeRevCosts (const GRAPH graph, SCIP_Real RESTRICT costrev)

void	graph_getIsTermArray (const GRAPH g, SCIP_Bool isterm)

void	graph_getTerms (const GRAPH g, int terms)

SCIP_RETCODE	graph_getTermsRandom (SCIP scip, const GRAPH g, int *terms)

SCIP_RETCODE	graph_init (SCIP scip, GRAPH *g, int ksize, int esize, int layers)

SCIP_RETCODE	graph_initHistory (SCIP scip, GRAPH graph)

SCIP_RETCODE	graph_resize (SCIP scip, GRAPH g, int ksize, int esize, int layers)

void	graph_free (SCIP scip, GRAPH *graph, SCIP_Bool final)

void	graph_freeHistory (SCIP scip, GRAPH p)

void	graph_freeHistoryDeep (SCIP scip, GRAPH p)

SCIP_RETCODE	graph_copy (SCIP scip, const GRAPH orggraph, GRAPH **copygraph)

SCIP_RETCODE	graph_copyData (SCIP scip, const GRAPH orgraph, GRAPH *copygraph)

SCIP_RETCODE	graph_copyPseudoAncestors (SCIP scip, const GRAPH orggraph, GRAPH *copygraph)

void	graph_mark (GRAPH *g)

SCIP_Bool	graph_isMarked (const GRAPH *g)

SCIP_Bool	graph_isSetUp (const GRAPH *g)

void	graph_show (const GRAPH *p)

void	graph_uncover (GRAPH *g)

SCIP_RETCODE	graph_pack (SCIP scip, GRAPH graph, GRAPH *newgraph, REDSOL redsol, SCIP_Bool verbose)

SCIP_Bool	graph_valid (SCIP scip, const GRAPH g)

SCIP_Bool	graph_validInput (SCIP scip, const GRAPH g)

Function Documentation

◆ graphisValidPcMw()

static SCIP_Bool graphisValidPcMw	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Bool *	nodevisited
	)

static

is the PC/MW part of the given graph valid?

Parameters

scip	SCIP
g	the graph
nodevisited	array

Definition at line 49 of file graph_base.c.

References GRAPH::cost, EAT_LAST, EQ, GRAPH::extended, FALSE, GRAPH::grad, graph_pc_isMw(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsNonLeafTerm(), graph_pc_term2edgeIsConsistent(), graph_trail_costAware(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pseudoTerm, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL_ABORT, SCIPdebugMessage, GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::term2edge, GRAPH::terms, and TRUE.

Referenced by graph_valid(), and graph_validInput().

◆ packPcMwVanished()

static SCIP_RETCODE packPcMwVanished	(	SCIP *	scip,
		GRAPH *	g_old
	)

static

do changes for Pc/Mw variants for vanished graph

Parameters

scip	SCIP data structure
g_old	the old graph

Definition at line 216 of file graph_base.c.

References graph_fixed_addNodePc(), graph_pc_isRootedPcMw(), graph_pc_knotIsNonLeafTerm(), graph_pc_termIsNonLeafTerm(), GRAPH::knots, SCIP_CALL, SCIP_OKAY, and GRAPH::source.

Referenced by graph_pack().

◆ packPcMwInit()

static SCIP_RETCODE packPcMwInit	(	SCIP *	scip,
		int	nnodes_new,
		GRAPH *	g_old,
		GRAPH *	g_new
	)

static

do changes for Pc/Mw variants

Parameters

scip	SCIP data structure
nnodes_new	number of nodes
g_old	the old graph
g_new	the new graph

Definition at line 250 of file graph_base.c.

References GRAPH::costbudget, graph_pc_initSubgraph(), graph_pc_isPcMw(), GRAPH::ksize, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, STP_BRMWCSP, and GRAPH::stp_type.

Referenced by graph_pack().

◆ packNodes()

static void packNodes	(	SCIP *	scip,
		GRAPH *	g_old,
		GRAPH *	g_new
	)

static

add nodes to new graph during graph packing

Parameters

scip	SCIP data structure
g_old	the old graph
g_new	the new graph

Definition at line 272 of file graph_base.c.

References GRAPH::cost, GRAPH::costbudget, EAT_LAST, FALSE, GRAPH::grad, graph_get_nNodes(), graph_knot_add(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIPisGT(), GRAPH::source, STP_BRMWCSP, GRAPH::stp_type, GRAPH::term, and GRAPH::term2edge.

Referenced by graph_pack().

◆ packPseudoAncestors()

static SCIP_RETCODE packPseudoAncestors	(	SCIP *	scip,
		const GRAPH *	g_old,
		GRAPH *	g_new
	)

static

adds pseudo-ancestor to new graph during graph packing

Parameters

scip	SCIP data structure
g_old	the old graph
g_new	the new graph

Definition at line 328 of file graph_base.c.

References EAT_FREE, GRAPH::edges, FALSE, graph_addPseudoAncestors(), graph_edge_getPseudoAncestors(), graph_edge_nPseudoAncestors(), graph_get_nEdges(), graph_getNpseudoAncestors(), graph_initPseudoAncestors(), graph_pseudoAncestors_appendCopyArrayToEdge(), GRAPH::ieat, SCIP_Bool, SCIP_CALL, and SCIP_OKAY.

Referenced by packEdges().

◆ packEdges()

static SCIP_RETCODE packEdges	(	SCIP *	scip,
		const int *	old2newNode,
		GRAPH *	g_old,
		int	nnodes,
		int	nedges,
		GRAPH *	g_new
	)

static

adds edges to new graph during graph packing

Parameters

scip	SCIP data structure
old2newNode	node mapping
g_old	the old graph
nnodes	number of nodes for new graph
nedges	number of edges for new graph
g_new	the new graph

Definition at line 381 of file graph_base.c.

References GRAPH::ancestors, EAT_FREE, GRAPH::edges, graph_edge_addSubgraph(), graph_edge_delHistory(), graph_get_nEdges(), GRAPH::head, GRAPH::ieat, NULL, GRAPH::oeat, packPseudoAncestors(), SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, and GRAPH::tail.

Referenced by graph_pack().

◆ graph_buildCompleteGraph()

SCIP_RETCODE graph_buildCompleteGraph	(	SCIP *	scip,
		GRAPH **	g,
		int	nnodes
	)

builds complete graph (Kn) with unit edge weights and no terminals

Parameters

scip	SCIP data structure
g	new graph
nnodes	number of nodes

Definition at line 440 of file graph_base.c.

References graph_edge_add(), graph_init(), graph_knot_add(), nnodes, SCIP_CALL, and SCIP_OKAY.

Referenced by bdkInit(), reduce_bd34(), reduce_bd34WithSd(), and testSdGetterReturnsCorrectSds().

◆ graph_getCsr()

void graph_getCsr	(	const GRAPH *	g,
		int *RESTRICT	edgearr,
		int *RESTRICT	tailarr,
		int *RESTRICT	start,
		int *	nnewedges
	)

Parameters

g	the graph
edgearr	original edge array [0,...,nedges - 1]
tailarr	tail of csr edge [0,...,nedges - 1]
start	start array [0,...,nnodes]
nnewedges	pointer to store number of new edges

Definition at line 468 of file graph_base.c.

References GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, nnodes, NULL, and GRAPH::tail.

◆ graph_getEdgeCosts()

void graph_getEdgeCosts	(	const GRAPH *	graph,
		SCIP_Real *RESTRICT	cost,
		SCIP_Real *RESTRICT	costrev
	)

get edge costs

Parameters

graph	the graph
cost	reduced edge costs
costrev	reduced reverse edge costs

Definition at line 500 of file graph_base.c.

References GRAPH::cost, flipedge, GE, graph_get_nEdges(), and SCIP_Real.

◆ graph_getEdgeRevCosts()

void graph_getEdgeRevCosts	(	const GRAPH *	graph,
		SCIP_Real *RESTRICT	costrev
	)

gets reversed edge costs

Parameters

graph	the graph
costrev	reduced reverse edge costs

Definition at line 521 of file graph_base.c.

References GRAPH::cost, flipedge, GE, graph_get_nEdges(), and SCIP_Real.

◆ graph_getIsTermArray()

void graph_getIsTermArray	(	const GRAPH *	g,
		SCIP_Bool *	isterm
	)

Parameters

g	the graph
isterm	marks whether node is a terminal (or proper terminal for PC)

Definition at line 540 of file graph_base.c.

References GRAPH::extended, FALSE, graph_pc_isPcMw(), graph_pc_termIsNonLeafTerm(), Is_term, GRAPH::knots, nnodes, SCIP_Bool, GRAPH::term, and TRUE.

Referenced by checkSdWalk(), extreduce_extPermaInit(), prInit(), reduce_nvAdv(), and reduce_sl().

◆ graph_getTerms()

void graph_getTerms	(	const GRAPH *	g,
		int *	terms
	)

gets terminals

Parameters

g	the graph
terms	array of size g->terms

Definition at line 567 of file graph_base.c.

References graph_get_nNodes(), Is_term, nnodes, nterms, GRAPH::term, and GRAPH::terms.

Referenced by graph_getTermsRandom(), and termsepaFindTerminalSource().

◆ graph_getTermsRandom()

SCIP_RETCODE graph_getTermsRandom	(	SCIP *	scip,
		const GRAPH *	g,
		int *	terms
	)

gets randomly permuted terminals

Parameters

scip	SCIP data structure
g	the graph
terms	array of size g->terms

Definition at line 588 of file graph_base.c.

References graph_getTerms(), SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPfreeRandom(), SCIPrandomPermuteIntArray(), GRAPH::terms, and TRUE.

Referenced by dpborder_coreUpdateOrdering().

◆ graph_init()

SCIP_RETCODE graph_init	(	SCIP *	scip,
		GRAPH **	g,
		int	ksize,
		int	esize,
		int	layers
	)

initialize graph

Parameters

scip	SCIP data structure
g	new graph
ksize	slots for nodes
esize	slots for edges
layers	number of layers (only needed for packing, otherwise 1)

Definition at line 607 of file graph_base.c.

References GRAPH::ancestors, GRAPH::budget, GRAPH::contracttrace, GRAPH::cost, GRAPH::cost_org_pc, GRAPH::costbudget, GRAPH::csr_storage, GRAPH::dcsr_storage, GRAPH::edges, GRAPH::esize, GRAPH::extended, FALSE, GRAPH::fixedcomponents, GRAPH::grad, GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, GRAPH::head, GRAPH::hoplimit, GRAPH::ieat, GRAPH::inpbeg, GRAPH::is_packed, GRAPH::knots, GRAPH::ksize, GRAPH::layers, GRAPH::mark, GRAPH::maxdeg, GRAPH::mincut_dist, GRAPH::mincut_e, GRAPH::mincut_head, GRAPH::mincut_nedges, GRAPH::mincut_next, GRAPH::mincut_nnodes, GRAPH::mincut_numb, GRAPH::mincut_prev, GRAPH::mincut_r, GRAPH::mincut_temp, GRAPH::mincut_x, GRAPH::norgmodeledges, GRAPH::norgmodelknots, GRAPH::norgmodelterms, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::orghead, GRAPH::orgknots, GRAPH::orgsource, GRAPH::orgtail, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::pcancestors, GRAPH::prize, GRAPH::pseudoancestors, GRAPH::rootedgeprevs, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, GRAPH::source, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::term2edge, GRAPH::terms, UNKNOWN, and GRAPH::withInexactReductions.

Referenced by boundPruneHeur(), buildsolgraph(), computeHistory(), extractSubgraphBuild(), graph_buildCompleteGraph(), graph_copy(), graph_grid_create(), graph_load(), graph_obstgrid_create(), graph_pack(), graph_transRpcGetSpg(), graphBuildV5E5(), localExtendPc(), localInsertion(), localInsertion2(), localInsertion2pc(), localKeyPathExchange(), localKeyPathExchangeMw(), localKeyPathExchangePc(), localKeyPathExchangePc2(), localKeyVertex(), localKeyVertexPc(), localKeyVertexPc2(), pseudoDelDouble(), pseudoDelSingle(), redcostGraphBuild(), reduce_bound(), reduce_boundHop(), reduce_npv(), reduce_sd(), reduce_sdPc(), SCIPStpHeurRecExclude(), sdgraphBuildDistgraph(), sdgraphBuildDistgraphFromTpaths(), subgraphBuild(), supergraphComputeMst(), testBdkSdMstDeletesNodeDeg3(), testBdkSdMstDeletesNodeDeg4(), testBdkSdMstStarDeletesNodeDeg4(), testBdkTreeDistDeletesNodeDeg4(), testBiasedTerminalPathsTo4NextFound(), testBiconnectedComponentsAreFound(), testBiconnectedComponentsAreFound2(), testBiconnectedComponentsAreFound3(), testBiconnectedDecomposition(), testBiconnectedDecomposition2(), testBiconnectedDecomposition3(), testBLCworksFor3Star(), testBLCworksFor3StarAfterReduction(), testBLCworksFor5Tree(), testDaPathsPcMw3EdgesWorks(), testDistCloseNodesAreValid(), testDistCloseNodesPcAreValid1(), testDistCloseNodesPcAreValid2(), testDistCloseNodesPcAreValidAfterDeletion(), testDistDistancesAreValid(), testDistRootPathsAreValid(), testEdgeDeletedBy3LeafSpg(), testEdgeDeletedByCommonRedCostsTargets(), testEdgeDeletedByEqBottleneck(), testEdgeDeletedByEqBottleneck2(), testEdgeDeletedByMst1(), testEdgeDeletedByMst2(), testEdgeDeletedByMultiRedCosts(), testEdgeDeletion1_deprecated(), testEdgeDeletion2_deprecated(), testEdgeDeletion3_deprecated(), testEdgeDeletion4_deprecated(), testEdgeDeletion5_deprecated(), testEdgeNotDeleted1(), testGeneralStarDeletedEdge1(), testGeneralStarDeletedEdge2(), testGeneralStarDeletedEdge3(), testNode3PseudoDeletedByContraction(), testNode3PseudoDeletedByRedCosts1(), testNode3PseudoDeletedBySd1(), testNode3PseudoDeletedBySd2(), testNode3PseudoDeletedBySd3(), testNode3PseudoDeletedBySdBiased(), testNode3PseudoDeletedBySdBiasedSimple(), testNode4PseudoDeletedBySd1(), testNode4PseudoNotDeletedBySd1(), testNsvImpliedContractsCutDistEdge(), testNsvImpliedContractsCutDistMiddleEdge(), testNsvImpliedContractsEdge(), testNsvImpliedContractsEdge2(), testNsvImpliedContractsImpliedToTermEdge(), testPathReplaceDeletesEdge(), testPathReplaceDeletesEdge2(), testPcEdgeDeletedByMst1(), testPcEdgeNotDeleted(), testPcNode3PseudoDeletedBySd1(), testPcNode4PseudoDeletedBySd1(), testPrunedSolIsImprovedPc1(), testPrunedSolIsImprovedPc2(), testRmwAnsDeletesOneEdge(), testRmwAnsDeletesOneNode(), testRmwAnsDeletesTwoNodes(), testRmwChain2DeletesNode(), testRmwNpv3DeletesNode(), testRmwTerminalContraction(), testRmwTerminalDeg1Contraction1(), testRmwTerminalDeg1Contraction2(), testRmwTerminalDeg1Contraction3(), testSdBiasedBottleneckDeletesEdge(), testSdBiasedBottleneckTermPathDeletesEdge(), testSdBiasedDeletesEdge(), testSdCliqueStarDeg3AdjacencyIsCorrect(), testSdCliqueStarDeg3IsCorrect(), testSdCliqueStarDeg3IsCorrect2(), testSdCliqueStarDeg4IsCorrect(), testSdCliqueStarDeletesEdge(), testSdGetterReturnsCorrectSds(), testSdGraphDistsAreValid(), testSdGraphDistsAreValid2(), testSdGraphQueriesAreValid(), testSdGraphStrongBiasedDistsAreValid(), testSdPcKillsEdge1(), testSdPcKillsEdge2(), testSdPcKillsTwoEdges(), testSdRepair(), testSdStarBiasedDeletesEdge(), testSdStarBiasedDeletesEdge2(), testSdStarBiasedDeletesEdge3(), testSdStarPcKillsEdge(), testStar3IsCorrect(), testStar4EdgeIsCorrect(), testStar4IsCorrect(), testStar5IsCorrect(), testTerminalPathsRepair(), testTerminalPathsRepair2(), testTerminalPathsRepair3(), testTerminalPathsTo3NextFound(), testTerminalSeparatorsAreFound(), testTerminalSeparatorsAreFound2(), testTerminalSeparatorsAreFound3(), testTmGivesExpectedTreePcFull1(), testTmGivesExpectedTreePcFull2(), and testTmGivesExpectedTreePcFull3().

◆ graph_initHistory()

SCIP_RETCODE graph_initHistory	(	SCIP *	scip,
		GRAPH *	graph
	)

initialize data structures required to keep track of reductions

Parameters

scip	SCIP data structure
graph	graph

Definition at line 695 of file graph_base.c.

References GRAPH::ancestors, BMScopyMemoryArray, graph_get_nEdges(), graph_initAncestors(), graph_initPseudoAncestors(), graph_pc_isPcMw(), GRAPH::head, GRAPH::knots, nnodes, NULL, GRAPH::orghead, GRAPH::orgtail, GRAPH::pcancestors, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, and GRAPH::tail.

Referenced by checkSdWalk(), graphBuildV5E5(), initPropgraph(), localExtendPc(), localInsertion(), localInsertion2(), localInsertion2pc(), localKeyPathExchange(), localKeyPathExchangeMw(), localKeyPathExchangePc(), localKeyPathExchangePc2(), localKeyVertex(), localKeyVertexPc(), localKeyVertexPc2(), prunegraphInit(), pseudoDelDouble(), pseudoDelSingle(), redcostGraphBuild(), reduce_exec(), SCIPStpHeurPruneRun(), SCIPStpHeurSlackPruneRun(), stptest_graphSetUp(), substpsolver_initHistory(), testDistCloseNodesAreValid(), testDistDistancesAreValid(), testDistRootPathsAreValid(), testEdgeDeletion1_deprecated(), testEdgeDeletion2_deprecated(), testEdgeDeletion3_deprecated(), testEdgeDeletion4_deprecated(), and updatePropgraph().

◆ graph_resize()

SCIP_RETCODE graph_resize	(	SCIP *	scip,
		GRAPH *	g,
		int	ksize,
		int	esize,
		int	layers
	)

enlarge given graph

Parameters

scip	SCIP data structure
g	graph to be resized
ksize	new node slots
esize	new edge slots
layers	layers (set to -1 by default)

Definition at line 744 of file graph_base.c.

References GRAPH::cost, GRAPH::costbudget, GRAPH::edges, GRAPH::esize, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, GRAPH::ksize, GRAPH::layers, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPreallocMemoryArray, GRAPH::tail, GRAPH::term, and GRAPH::term2edge.

Referenced by getBiasedMw(), graph_transPc(), graph_transPc2Spg(), graph_transPcGetSap(), graph_transRmw(), graph_transRpc(), and graph_transRpc2FixedProper().

◆ graph_free()

void graph_free	(	SCIP *	scip,
		GRAPH **	graph,
		SCIP_Bool	final
	)

free the graph

Parameters

scip	SCIP data structure
graph	graph to be freed
final	delete ancestor data structures?

Definition at line 796 of file graph_base.c.

References GRAPH::cost, GRAPH::cost_org_pc, GRAPH::costbudget, GRAPH::csr_storage, GRAPH::dcsr_storage, GRAPH::grad, graph_free_csr(), graph_free_dcsr(), graph_freeHistory(), graph_freeHistoryDeep(), graph_mincut_exit(), graph_mincut_isInitialized(), graph_path_exists(), graph_path_exit(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, GRAPH::mark, GRAPH::maxdeg, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, GRAPH::rootedgeprevs, SCIPfreeMemory, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, STP_DCSTP, STP_RSMT, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and GRAPH::term2edge.

Referenced by bdkFree(), boundPruneHeur(), buildsolgraph(), checkSdWalk(), computeHistory(), dualascent_execPcMw(), graph_pack(), graph_subgraphFree(), graph_subgraphReinsert(), initReceivedSubproblem(), localExtendPc(), localInsertion(), localInsertion2(), localInsertion2pc(), localKeyPathExchange(), localKeyPathExchangeMw(), localKeyPathExchangePc(), localKeyPathExchangePc2(), localKeyVertex(), localKeyVertexPc(), localKeyVertexPc2(), lurkpruneFinalize(), pseudoAncestorsCreation(), pseudoAncestorsHash(), pseudoAncestorsHashPc(), pseudoAncestorsMerge(), pseudoAncestorsMergePc(), pseudoDelDouble(), pseudoDelSingle(), redcostGraphFree(), reduce_bd34(), reduce_bd34WithSd(), reduce_bound(), reduce_boundHop(), reduce_daPcMw(), reduce_impliedProfitBasedRpc(), reduce_npv(), reduce_sd(), reduce_sdgraphFree(), reduce_sdPc(), reduce_termcompFree(), SCIP_DECL_PROBDELORIG(), SCIP_DECL_PROPEXITSOL(), SCIPStpHeurPruneRun(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), stptest_graphTearDown(), substpsolver_solve(), supergraphComputeMst(), testDaPathsPcMw3EdgesWorks(), testDistCloseNodesAreValid(), testDistDistancesAreValid(), and testDistRootPathsAreValid().

◆ graph_freeHistory()

void graph_freeHistory	(	SCIP *	scip,
		GRAPH *	p
	)

frees the history

Parameters

scip	SCIP data
p	graph data

Definition at line 868 of file graph_base.c.

References GRAPH::ancestors, GRAPH::contracttrace, GRAPH::edges, graph_freePseudoAncestors(), NULL, Int_List_Node::parent, GRAPH::pseudoancestors, SCIPfreeBlockMemory, SCIPfreeMemoryArray, and SCIPfreeMemoryArrayNull.

Referenced by graph_free(), and updatePropgraph().

◆ graph_freeHistoryDeep()

void graph_freeHistoryDeep	(	SCIP *	scip,
		GRAPH *	p
	)

frees the deep history

Parameters

scip	SCIP data
p	graph data

Definition at line 900 of file graph_base.c.

References GRAPH::fixedcomponents, graph_free_fixed(), GRAPH::norgmodelknots, NULL, GRAPH::orghead, GRAPH::orgtail, Int_List_Node::parent, GRAPH::path_heap, GRAPH::path_state, GRAPH::pcancestors, SCIPfreeBlockMemory, and SCIPfreeMemoryArray.

Referenced by graph_free(), and updatePropgraph().

◆ graph_copy()

SCIP_RETCODE graph_copy	(	SCIP *	scip,
		const GRAPH *	orggraph,
		GRAPH **	copygraph
	)

copy the graph

Parameters

scip	SCIP data structure
orggraph	original graph
copygraph	graph to be created

Definition at line 939 of file graph_base.c.

References GRAPH::esize, graph_copyData(), graph_init(), GRAPH::ksize, GRAPH::layers, NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by graph_transPcGetRsap(), graph_transPcGetSap(), initPropgraph(), initReceivedSubproblem(), prunegraphInit(), SCIP_DECL_PROBCOPY(), SCIPprobdataCreateFromGraph(), SCIPStpHeurPruneRun(), SCIPStpHeurSlackPruneRun(), solveSub(), and substpsolver_getObjFromGraph().

◆ graph_copyData()

SCIP_RETCODE graph_copyData	(	SCIP *	scip,
		const GRAPH *	orgraph,
		GRAPH *	copygraph
	)

copy the data of the graph

Parameters

scip	SCIP data structure
orgraph	original graph
copygraph	graph to be copied to

Definition at line 957 of file graph_base.c.

References BMScopyMemoryArray, GRAPH::budget, GRAPH::cost, GRAPH::cost_org_pc, GRAPH::costbudget, GRAPH::csr_storage, GRAPH::dcsr_storage, GRAPH::edges, EQ, GRAPH::esize, GRAPH::extended, GRAPH::grad, graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), graph_valid(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, GRAPH::head, GRAPH::hoplimit, GRAPH::ieat, GRAPH::inpbeg, GRAPH::is_packed, Is_term, GRAPH::knots, GRAPH::ksize, GRAPH::mark, GRAPH::maxdeg, GRAPH::norgmodeledges, GRAPH::norgmodelknots, GRAPH::norgmodelterms, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::orgknots, GRAPH::orgsource, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, GRAPH::source, STP_BRMWCSP, STP_DCSTP, STP_RSMT, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::term2edge, GRAPH::terms, and GRAPH::withInexactReductions.

Referenced by graph_copy(), and updatePropgraph().

◆ graph_copyPseudoAncestors()

SCIP_RETCODE graph_copyPseudoAncestors	(	SCIP *	scip,
		const GRAPH *	orggraph,
		GRAPH *	copygraph
	)

copies the pseudo-ancestors

Parameters

scip	SCIP data structure
orggraph	original graph
copygraph	graph to be created

Definition at line 1088 of file graph_base.c.

References EAT_FREE, GRAPH::edges, FALSE, graph_addPseudoAncestors(), graph_edge_getPseudoAncestors(), graph_edge_nPseudoAncestors(), graph_get_nEdges(), graph_getNpseudoAncestors(), graph_pseudoAncestors_appendCopyArrayToEdge(), GRAPH::ieat, SCIP_Bool, SCIP_CALL, and SCIP_OKAY.

Referenced by initPropgraph(), SCIP_DECL_PROBCOPY(), and SCIPprobdataCreateFromGraph().

◆ graph_mark()

void graph_mark ( GRAPH * g )

marks the current graph

Parameters

g the graph

Definition at line 1130 of file graph_base.c.

References GRAPH::extended, FALSE, GRAPH::grad, graph_get_nNodes(), graph_isMarked(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), Is_pseudoTerm, Is_term, GRAPH::mark, nnodes, GRAPH::source, GRAPH::term, and TRUE.

Referenced by checkSdWalk(), computeSteinerTreeDijk(), daRoundExit(), daRoundInit(), divideAndConquer(), enumeration_findSolPcMw(), extInit(), extreduce_deleteEdges(), extreduce_init(), extreduce_pseudoDeleteNodes(), fixVarsDualcost(), fixVarsExtendedRed(), graph_get4nextTTerms(), graph_init_dcsr(), graph_pc_2org(), graph_pc_2trans(), graph_tpathsSetAll2(), graph_tpathsSetAll3(), graph_tpathsSetAll4(), initDecompose(), localExtendPc(), localInsertion(), localInsertion2(), localInsertion2pc(), localKeyPathExchange(), localKeyPathExchangeMw(), localKeyPathExchangePc(), localKeyPathExchangePc2(), localKeyVertex(), localKeyVertexPc(), localKeyVertexPc2(), pcmwDeleteNonSolEdges(), prunegraphInit(), redcosts_initializeDistances(), reduce_ans(), reduce_articulations(), reduce_bd34(), reduce_bd34WithSd(), reduce_bdkWithSd(), reduce_bidecomposition(), reduce_bidecompositionExact(), reduce_blctreeInit(), reduce_bound(), reduce_da(), reduce_dapaths(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_impliedProfitBasedRpc(), reduce_npv(), reduce_nvAdv(), reduce_sdBiased(), reduce_sdBiasedNeighbor(), reduce_sdEdgeCliqueStar(), reduce_sdStarPc2(), reduce_simple_mw(), reduce_sl(), reduce_termcompChangeSubgraphToBottleneck(), reduceWithNodeFixingBounds(), SCIPStpHeurPruneUpdateSols(), stptest_graphSetUp(), termcompReduceWithParams(), testDistCloseNodesAreValid(), testDistDistancesAreValid(), testDistRootPathsAreValid(), testEdgeDeletion1_deprecated(), testEdgeDeletion2_deprecated(), testEdgeDeletion3_deprecated(), and testEdgeDeletion4_deprecated().

◆ graph_isMarked()

SCIP_Bool graph_isMarked ( const GRAPH * g )

is the current graph properly marked?

Parameters

g the graph

Definition at line 1165 of file graph_base.c.

References GRAPH::extended, FALSE, GRAPH::grad, graph_knot_printInfo(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), Is_pseudoTerm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, GRAPH::source, GRAPH::term, and TRUE.

Referenced by bidecomposition_isPossible(), blctreeComputeBottlenecks(), blctreeComputeEdgesState(), extCheckArc(), extreduce_checkArc(), extreduce_checkEdge(), extreduce_deleteEdges(), extreduce_distDataRecomputeDirtyPaths(), findSolPcMw(), findSolRPcMw(), getRedCost2ndNextDistances(), graph_mark(), graph_tpathsRepair(), graph_transRpcGetSpg(), isPseudoDeletable(), pseudodeleteExecute(), redcosts_initializeDistances(), reduce_dapaths(), and termcompDeleteEdges().

◆ graph_isSetUp()

SCIP_Bool graph_isSetUp ( const GRAPH * g )

is the current graph already set up? (with history and path)

Parameters

g the graph

Definition at line 1240 of file graph_base.c.

References GRAPH::ancestors, NULL, and GRAPH::orgtail.

Referenced by reduce_exec().

◆ graph_show()

void graph_show ( const GRAPH * p )

Parameters

p the graph

Definition at line 1251 of file graph_base.c.

References GRAPH::cost, EAT_FREE, GRAPH::edges, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::tail, and GRAPH::term.

◆ graph_uncover()

void graph_uncover ( GRAPH * g )

reinsert all hidden edges

Parameters

g the graph

Definition at line 1276 of file graph_base.c.

References EAT_HIDE, GRAPH::edges, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, NULL, GRAPH::oeat, GRAPH::outbeg, and GRAPH::tail.

◆ graph_pack()

SCIP_RETCODE graph_pack	(	SCIP *	scip,
		GRAPH *	graph,
		GRAPH **	newgraph,
		REDSOL *	redsol,
		SCIP_Bool	verbose
	)

Packs the graph, i.e. builds a new graph that discards deleted edges and nodes. The original graph is deleted.

Parameters

scip	SCIP data structure
graph	the graph
newgraph	the new graph
redsol	reduce solution or NULL
verbose	verbose?

Definition at line 1324 of file graph_base.c.

References GRAPH::ancestors, GRAPH::budget, EAT_FREE, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, GRAPH::fixedcomponents, GRAPH::grad, graph_free(), graph_get_nEdges(), graph_get_nNodes(), graph_init(), graph_knot_add(), graph_path_exit(), graph_pc_finalizeSubgraph(), graph_pc_getNonLeafTermOffset(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_valid(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, GRAPH::hoplimit, GRAPH::ieat, GRAPH::is_packed, Is_term, GRAPH::knots, GRAPH::layers, GRAPH::maxdeg, nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, GRAPH::norgmodelterms, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::orghead, GRAPH::orgknots, GRAPH::orgsource, GRAPH::orgtail, packEdges(), packNodes(), packPcMwInit(), packPcMwVanished(), GRAPH::path_heap, GRAPH::pcancestors, GRAPH::prize, reduce_solGetOffsetPointer(), reduce_solPack(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::source, STP_RSMT, GRAPH::stp_type, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by graph_obstgrid_create(), presolveStp(), and SCIPStpHeurRecRun().

◆ graph_valid()

SCIP_Bool graph_valid	(	SCIP *	scip,
		const GRAPH *	g
	)

is the given graph valid?

Parameters

scip	scip struct
g	the graph

Definition at line 1480 of file graph_base.c.

References EAT_FREE, EAT_LAST, GRAPH::edges, FALSE, GRAPH::grad, graph_knot_printInfo(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_trail_arr(), graphisValidPcMw(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArrayNull, GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by boundPruneHeur(), boundPruneHeurMw(), buildsolgraph(), computeNewSols(), computePertubedSol(), computeReducedProbSolution(), computeSteinerTree(), daRoundExit(), decomposeExec(), decomposeExecExact(), decomposeGetSubgraph(), decomposeReduceSubDoIt(), execNvSl(), fixVarsRedbased(), graph_copyData(), graph_load(), graph_pack(), graph_save(), graph_subgraphReinsert(), graph_transPc(), graph_transPcmw2rooted(), graph_transRmw(), ledgeFromNetgraph(), localRun(), nsvExec(), redcostGraphBuild(), redcostGraphComputeSteinerTree(), redcostGraphComputeSteinerTreeDegCons(), redcostGraphComputeSteinerTreeDirected(), reduce_ans(), reduce_ansAdv(), reduce_ansAdv2(), reduce_applyPseudoDeletions(), reduce_bd34(), reduce_bd34WithSd(), reduce_bound(), reduce_boundHop(), reduce_boundHopDa(), reduce_boundHopR(), reduce_boundHopRc(), reduce_boundPruneHeur(), reduce_da(), reduce_dapaths(), reduce_daPcMw(), reduce_exec(), reduce_identifyNonLeafTerms(), reduce_impliedProfitBasedRpc(), reduce_nnp(), reduce_pathreplace(), reduce_pathreplaceExt(), reduce_redLoopStp(), reduce_sd(), reduce_sdBiased(), reduce_sdBiasedNeighbor(), reduce_sdPc(), reduce_sdsp(), reduce_simple(), reduce_simple_mw(), reduce_simple_pc(), reduce_simple_sap(), reduceLurk(), runTmPcMW_mode(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurPruneRun(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), SCIPStpPropGetGraph(), SCIPStpValidateSol(), sdgraphBuildDistgraph(), sdgraphBuildDistgraphFromTpaths(), selectBranchingVertexBySol(), and termcompDeleteEdges().

◆ graph_validInput()

SCIP_Bool graph_validInput	(	SCIP *	scip,
		const GRAPH *	g
	)

is the given input graph valid?

Parameters

scip	scip struct
g	the graph

Definition at line 1619 of file graph_base.c.

References EAT_LAST, FALSE, GRAPH::grad, graph_get_nNodes(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_trail_arr(), graphisValidPcMw(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPerrorMessage, SCIPfreeBufferArrayNull, GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by check_inputgraph().

SCIP

Detailed Description

Functions

Function Documentation

◆ graphisValidPcMw()

◆ packPcMwVanished()

◆ packPcMwInit()

◆ packNodes()

◆ packPseudoAncestors()

◆ packEdges()

◆ graph_buildCompleteGraph()

◆ graph_getCsr()

◆ graph_getEdgeCosts()

◆ graph_getEdgeRevCosts()

◆ graph_getIsTermArray()

◆ graph_getTerms()

◆ graph_getTermsRandom()

◆ graph_init()

◆ graph_initHistory()

◆ graph_resize()

◆ graph_free()

◆ graph_freeHistory()

◆ graph_freeHistoryDeep()

◆ graph_copy()

◆ graph_copyData()

◆ graph_copyPseudoAncestors()

◆ graph_mark()

◆ graph_isMarked()

◆ graph_isSetUp()

◆ graph_show()

◆ graph_uncover()

◆ graph_pack()

◆ graph_valid()

◆ graph_validInput()