Detailed Description

special distance (bottleneck distance) reduction methods for Steiner problems

Author: Daniel Rehfeldt

This file encompasses various special distance (aka bottleneck distance) based reduction methods for Steiner problems.

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

Definition in file reduce_sd.c.

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

Go to the source code of this file.

Macros
#define	STP_BD_MAXDEGREE 4

#define	STP_BD_MAXDNEDGES 6

#define	STP_SDWALK_MAXNPREVS 8

Functions
static SCIP_RETCODE	sdStarInit (SCIP scip, const GRAPH g, int edgelimit, DIJK *dijkdata, int RESTRICT star_base, SCIP_Bool RESTRICT *edge_deletable)

static void	sdStarFinalize (SCIP scip, GRAPH g, DIJK *dijkdata, int RESTRICT star_base, SCIP_Bool RESTRICT *edge_deletable)

static void	sdStarReset (int nnodes, int nvisits, const int visitlist, int RESTRICT star_base, SCIP_Real RESTRICT dist, STP_Bool RESTRICT visited, DHEAP *RESTRICT dheap)

static SCIP_RETCODE	sdStarBiasedProcessNode (SCIP scip, int node, SCIP_Bool usestrongreds, const SDPROFIT sdprofit, GRAPH g, DIJK dijkdata, int RESTRICT star_base, SCIP_Bool RESTRICT edge_deletable, int *nelims)

static void	sdwalkReset (int nnodes, int nvisits, const int visitlist, SCIP_Real RESTRICT dist, int RESTRICT state, STP_Bool RESTRICT visited)

static void	sdwalkResetExt (int nnodes, int nvisits, const int visitlist, SCIP_Real RESTRICT dist, int RESTRICT nprevterms, int RESTRICT state, STP_Bool *RESTRICT visited)

static void	sdwalkResetExt2 (int nnodes, int nvisits, const int visitlist, SCIP_Real dist, int nprevterms, int nprevNPterms, int nprevedges, int state, STP_Bool *visited)

static SCIP_Bool	sddeltable (SCIP scip, GRAPH g, PATH path, int vbase, int *forbidden, int tpos, int hpos, int tail, int head, int edge, int nnodes)

static int	getcloseterms (SCIP scip, const PATH vnoi, SCIP_Real termdist, SCIP_Real ecost, const int vbase, int *neighbterms, int i, int nnodes)

static int	getcloseterms2term (SCIP scip, const GRAPH g, const GRAPH netgraph, SCIP_Real termdist, SCIP_Real ecost, int neighbterms, int nodesid, int *nodesorg, int i)

static int	getlecloseterms (SCIP scip, PATH vnoi, SCIP_Real termdist, SCIP_Real ecost, int vbase, int *neighbterms, int i, int nnodes)

static void	pcBiasCostsDCSR (SCIP scip, const GRAPH g, SCIP_Bool biasreversed, SCIP_Real costbiased, SCIP_Real mincost_in)

static SCIP_Real	getSd (SCIP scip, GRAPH g, SDGRAPH sdgraph, PATH vnoi, SCIP_Real sd_initial, int *vbase, int i, int i2, int limit)

static SCIP_Real	sdGetSd (const GRAPH g, int i, int i2, SCIP_Real sd_upper, SCIP_Real sd_sufficient, SCIP_Bool onlyIntermedTerms, SD sddata)

static SCIP_Real	sdGetSdNeighbor (const GRAPH g, int i, int i2, SCIP_Real sd_upper, SCIP_Real sd_sufficient, SD sddata)

static SCIP_Bool	isPseudoDeletableDeg3 (SCIP scip, const GRAPH g, const SCIP_Real sdsK3, const int edgesK3, SCIP_Real costK3, SCIP_Bool allowEquality)

static SCIP_Bool	isPseudoDeletable (SCIP scip, const GRAPH g, const GRAPH auxg, const SCIP_Real ecost, const int *edges, int degree)

static SCIP_RETCODE	sdCliqueInitData (SCIP scip, const GRAPH g, int centernode, const GRAPH cliquegraph, const int cliqueNodeMap, DIJK dijkdata, SDCLIQUE sdclique)

static void	sdCliqueFreeData (SCIP scip, SDCLIQUE sdclique)

static SCIP_RETCODE	sdCliqueUpdateGraphWithStarWalks (SCIP scip, const GRAPH g, const SDPROFIT sdprofit, GRAPH cliquegraph, SDCLIQUE *sdclique)

static void	sdGetSdsCliqueTermWalks (const GRAPH g, SD RESTRICT sddata, GRAPH RESTRICT cliquegraph, SDCLIQUE RESTRICT sdclique)

static SCIP_RETCODE	ledgeFromNetgraph (SCIP scip, const GRAPH netgraph, const PATH mst, const int edgeorg, const PATH vnoi, const int vbase, GRAPH g, int nelims)

SCIP_RETCODE	reduce_sdGetSdsCliquegraph (SCIP scip, const GRAPH g, int centernode, const int cliqueNodeMap, DIJK dijkdata, SD sddata, GRAPH cliquegraph)

SCIP_RETCODE	reduce_sdImpLongEdge (SCIP scip, const int edgestate, GRAPH g, SD sdistance, int *nelims)

SCIP_RETCODE	reduce_sd (SCIP scip, GRAPH g, REDBASE redbase, int nelims)

SCIP_RETCODE	reduce_sdBiased (SCIP scip, SD sdistance, GRAPH g, int nelims)

SCIP_RETCODE	reduce_sdBiasedNeighbor (SCIP scip, SD sdistance, GRAPH g, int nelims)

SCIP_RETCODE	reduce_sdPc (SCIP scip, GRAPH g, PATH vnoi, int heap, int state, int vbase, int nodesid, int nodesorg, int *nelims)

SCIP_RETCODE	reduce_getSdByPaths (SCIP scip, GRAPH g, PATH pathtail, PATH pathhead, SCIP_Real sdist, SCIP_Real distlimit, int heap, int statetail, int statehead, int memlbltail, int memlblhead, int i, int i2, int limit, SCIP_Bool pc, SCIP_Bool mw)

SCIP_Real	reduce_sdGetSd (const GRAPH g, int i, int i2, SCIP_Real sd_upper, SCIP_Real sd_sufficient, SD sddata)

SCIP_Real	reduce_sdGetSdIntermedTerms (const GRAPH g, int i, int i2, SCIP_Real sd_upper, SCIP_Real sd_sufficient, SD sddata)

static SCIP_Real	sdGetSdPcMw (SCIP scip, const GRAPH g, SCIP_Real distlimit, int i, int i2, int edgelimit, SD1PC *sd1pc)

SCIP_RETCODE	reduce_sdspSap (SCIP scip, GRAPH g, PATH pathtail, PATH pathhead, int heap, int statetail, int statehead, int memlbltail, int memlblhead, int nelims, int limit)

SCIP_RETCODE	reduce_sdWalk_csr (SCIP scip, int edgelimit, const int edgestate, GRAPH g, int termmark, SCIP_Real dist, int visitlist, STP_Bool visited, DHEAP dheap, int *nelims)

SCIP_RETCODE	reduce_sdEdgeCliqueStar (SCIP scip, int edgelimit, GRAPH g, int *nelims)

SCIP_RETCODE	reduce_sdWalkTriangle (SCIP scip, int edgelimit, SCIP_Bool usestrongreds, GRAPH g, int termmark, SCIP_Real dist, int visitlist, STP_Bool visited, DHEAP dheap, int nelims)

SCIP_RETCODE	reduce_sdStar (SCIP scip, int edgelimit, SCIP_Bool usestrongreds, GRAPH g, SCIP_Real dist, int star_base, int visitlist, STP_Bool visited, DHEAP dheap, int nelims)

SCIP_RETCODE	reduce_sdStarBiased (SCIP scip, int edgelimit, SCIP_Bool usestrongreds, GRAPH g, int *nelims)

SCIP_RETCODE	reduce_sdStarBiasedWithProfit (SCIP scip, int edgelimit, const SDPROFIT sdprofit, SCIP_Bool usestrongreds, GRAPH g, int nelims)

SCIP_RETCODE	reduce_sdStarPc2 (SCIP scip, int edgelimit, SCIP_Bool usestrongreds, GRAPH g, SCIP_Real dist, int star_base, int visitlist, STP_Bool visited, DHEAP dheap, int nelims)

SCIP_RETCODE	reduce_sdStarPc (SCIP scip, int edgelimit, const int edgestate, GRAPH g, SCIP_Real dist, int star_base, int visitlist, STP_Bool visited, DHEAP dheap, int *nelims)

SCIP_RETCODE	reduce_sdWalk (SCIP scip, int edgelimit, const int edgestate, GRAPH g, int termmark, SCIP_Real dist, int heap, int state, int visitlist, STP_Bool visited, int nelims)

SCIP_RETCODE	reduce_sdWalkExt (SCIP scip, int edgelimit, SCIP_Bool usestrongreds, GRAPH g, SCIP_Real dist, int heap, int state, int visitlist, STP_Bool visited, int nelims)

SCIP_RETCODE	reduce_sdWalkExt2 (SCIP scip, int edgelimit, const int edgestate, GRAPH g, int termmark, SCIP_Real dist, int heap, int state, int visitlist, STP_Bool visited, int nelims)

SCIP_RETCODE	reduce_sdsp (SCIP scip, GRAPH g, PATH pathtail, int heap, int statetail, int statehead, int memlbltail, int memlblhead, int *nelims, int limit, SCIP_Bool usestrongreds)

SCIP_RETCODE	reduce_bd34WithSd (SCIP scip, GRAPH g, SDGRAPH sdgraph, PATH vnoi, int vbase, int nelims)

SCIP_RETCODE	reduce_bd34 (SCIP scip, GRAPH g, PATH pathtail, PATH pathhead, int heap, int statetail, int statehead, int memlbltail, int memlblhead, int nelims, int limit, SCIP_Real *offset)

Macro Definition Documentation

◆ STP_BD_MAXDEGREE

#define STP_BD_MAXDEGREE 4

Definition at line 42 of file reduce_sd.c.

Referenced by isPseudoDeletable(), reduce_bd34(), and reduce_bd34WithSd().

◆ STP_BD_MAXDNEDGES

#define STP_BD_MAXDNEDGES 6

Definition at line 43 of file reduce_sd.c.

Referenced by reduce_bd34(), and reduce_bd34WithSd().

◆ STP_SDWALK_MAXNPREVS

#define STP_SDWALK_MAXNPREVS 8

Definition at line 44 of file reduce_sd.c.

Referenced by reduce_sdWalkExt(), and reduce_sdWalkExt2().

Function Documentation

◆ sdStarInit()

static SCIP_RETCODE sdStarInit	(	SCIP *	scip,
		const GRAPH *	g,
		int	edgelimit,
		DIJK **	dijkdata,
		int RESTRICT	star_base,
		SCIP_Bool RESTRICT	edge_deletable
	)

static

initializes data needed for SD star tests

Parameters

scip	SCIP data structure
g	graph data structure
edgelimit	limit
dijkdata	data to be allocated
star_base	data to be allocated
edge_deletable	data to be allocated

Definition at line 53 of file reduce_sd.c.

References EQ, GRAPH::extended, FALSE, FARAWAY, graph_dijkLimited_init(), graph_get_nEdges(), graph_get_nNodes(), graph_heap_isClean(), graph_pc_isPcMw(), nnodes, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, and SDSTAR_BASE_UNSET.

Referenced by reduce_sdStarBiasedWithProfit().

◆ sdStarFinalize()

static void sdStarFinalize	(	SCIP *	scip,
		GRAPH *	g,
		DIJK **	dijkdata,
		int RESTRICT	star_base,
		SCIP_Bool RESTRICT	edge_deletable
	)

static

finalizes SD star tests

Parameters

scip	SCIP data structure
g	graph data structure
dijkdata	data to be freed
star_base	data to be freed
edge_deletable	data to be freed

Definition at line 103 of file reduce_sd.c.

References GRAPH::dcsr_storage, EAT_FREE, graph_dijkLimited_free(), graph_edge_delBlocked(), graph_get_nEdges(), GRAPH::head, dynamic_csr_storage::id2csredge, GRAPH::mark, GRAPH::oeat, SCIP_Bool, SCIPfreeBufferArray, GRAPH::tail, and TRUE.

Referenced by reduce_sdStarBiasedWithProfit().

◆ sdStarReset()

static void sdStarReset	(	int	nnodes,
		int	nvisits,
		const int *	visitlist,
		int *RESTRICT	star_base,
		SCIP_Real *RESTRICT	dist,
		STP_Bool *RESTRICT	visited,
		DHEAP *RESTRICT	dheap
	)

inlinestatic

resets data needed for SD star tests

Parameters

nnodes	number of nodes
nvisits	number of visits
visitlist	array of visited nodes
star_base	star-bases
dist	node distances
visited	visit mark
dheap	Dijkstra heap

Definition at line 135 of file reduce_sd.c.

References FALSE, FARAWAY, graph_heap_clean(), nnodes, SDSTAR_BASE_UNSET, and UNKNOWN.

Referenced by reduce_sdStar(), reduce_sdStarPc(), reduce_sdStarPc2(), and sdStarBiasedProcessNode().

◆ sdStarBiasedProcessNode()

static SCIP_RETCODE sdStarBiasedProcessNode	(	SCIP *	scip,
		int	node,
		SCIP_Bool	usestrongreds,
		const SDPROFIT *	sdprofit,
		GRAPH *	g,
		DIJK *	dijkdata,
		int *RESTRICT	star_base,
		SCIP_Bool *RESTRICT	edge_deletable,
		int *	nelims
	)

static

checks node

Parameters

scip	SCIP data structure
node	node to process
usestrongreds	allow strong reductions?
sdprofit	SD profit
g	graph data structure
dijkdata	data
star_base	data to be freed
edge_deletable	data to be freed
nelims	point to store number of deleted edges

Definition at line 172 of file reduce_sd.c.

References dynamic_csr_storage::cost, GRAPH::dcsr_storage, dijkstra_data::dheap, dynamic_csr_storage::edgeid, FALSE, graph_dcsr_deleteEdgeBi(), graph_get_nNodes(), graph_sdStarBiased(), dynamic_csr_storage::head, GRAPH::mark, nnodes, dijkstra_data::node_distance, dijkstra_data::node_visited, dijkstra_data::nvisits, dynamic_csr_storage::range, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPisEQ(), SCIPisLE(), SDSTAR_BASE_KILLED, SDSTAR_BASE_UNSET, sdStarReset(), TRUE, and dijkstra_data::visitlist.

Referenced by reduce_sdStarBiasedWithProfit().

◆ sdwalkReset()

static void sdwalkReset	(	int	nnodes,
		int	nvisits,
		const int *	visitlist,
		SCIP_Real *RESTRICT	dist,
		int *RESTRICT	state,
		STP_Bool *RESTRICT	visited
	)

inlinestatic

resets data needed for SD walk tests

Definition at line 253 of file reduce_sd.c.

References FALSE, FARAWAY, nnodes, and UNKNOWN.

Referenced by reduce_sdWalk(), reduce_sdWalk_csr(), and reduce_sdWalkTriangle().

◆ sdwalkResetExt()

static void sdwalkResetExt	(	int	nnodes,
		int	nvisits,
		const int *	visitlist,
		SCIP_Real *RESTRICT	dist,
		int *RESTRICT	nprevterms,
		int *RESTRICT	state,
		STP_Bool *RESTRICT	visited
	)

inlinestatic

Definition at line 281 of file reduce_sd.c.

References FALSE, FARAWAY, nnodes, and UNKNOWN.

Referenced by reduce_sdWalkExt().

◆ sdwalkResetExt2()

static void sdwalkResetExt2	(	int	nnodes,
		int	nvisits,
		const int *	visitlist,
		SCIP_Real *	dist,
		int *	nprevterms,
		int *	nprevNPterms,
		int *	nprevedges,
		int *	state,
		STP_Bool *	visited
	)

inlinestatic

Definition at line 312 of file reduce_sd.c.

References FALSE, FARAWAY, nnodes, and UNKNOWN.

Referenced by reduce_sdWalkExt2().

◆ sddeltable()

static SCIP_Bool sddeltable	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	path,
		int *	vbase,
		int *	forbidden,
		int	tpos,
		int	hpos,
		int	tail,
		int	head,
		int	edge,
		int	nnodes
	)

static

Definition at line 351 of file reduce_sd.c.

References GRAPH::cost, EAT_FREE, EAT_LAST, shortest_path::edge, FALSE, flipedge, GRAPH::head, GRAPH::ieat, Is_term, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Real, SCIPisEQ(), GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reduce_sd().

◆ getcloseterms()

static int getcloseterms	(	SCIP *	scip,
		const PATH *	vnoi,
		SCIP_Real *	termdist,
		SCIP_Real	ecost,
		const int *	vbase,
		int *	neighbterms,
		int	i,
		int	nnodes
	)

static

gets distances to close terminals

Definition at line 464 of file reduce_sd.c.

References shortest_path::dist, nnodes, NULL, and SCIPisLT().

Referenced by getSd(), and reduce_sdPc().

◆ getcloseterms2term()

static int getcloseterms2term	(	SCIP *	scip,
		const GRAPH *	g,
		const GRAPH *	netgraph,
		SCIP_Real *	termdist,
		SCIP_Real	ecost,
		int *	neighbterms,
		int *	nodesid,
		int *	nodesorg,
		int	i
	)

static

Definition at line 503 of file reduce_sd.c.

References GRAPH::cost, EAT_LAST, GRAPH::head, Is_term, GRAPH::oeat, GRAPH::outbeg, SCIP_Real, SCIPisGT(), SCIPisLT(), GRAPH::term, and UNKNOWN.

Referenced by reduce_sdPc().

◆ getlecloseterms()

static int getlecloseterms	(	SCIP *	scip,
		PATH *	vnoi,
		SCIP_Real *	termdist,
		SCIP_Real	ecost,
		int *	vbase,
		int *	neighbterms,
		int	i,
		int	nnodes
	)

static

Definition at line 554 of file reduce_sd.c.

References shortest_path::dist, nnodes, NULL, and SCIPisLE().

Referenced by reduce_sd().

◆ pcBiasCostsDCSR()

static void pcBiasCostsDCSR	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Bool	biasreversed,
		SCIP_Real *	costbiased,
		SCIP_Real *	mincost_in
	)

static

bias DCSR costs for PCMW

Parameters

scip	SCIP data structure
g	graph data structure
biasreversed	bias reversed
costbiased	biased edge cost
mincost_in	vertex distances

Definition at line 595 of file reduce_sd.c.

References BMScopyMemoryArray, dynamic_csr_storage::cost, GRAPH::dcsr_storage, GRAPH::edges, csr_range::end, GRAPH::extended, FARAWAY, graph_pc_isPcMw(), dynamic_csr_storage::head, Is_term, GRAPH::knots, LT, GRAPH::mark, dynamic_csr_storage::nedges, nnodes, GRAPH::prize, dynamic_csr_storage::range, SCIP_Real, SCIPisNegative(), and GRAPH::term.

Referenced by reduce_sdStarPc(), and reduce_sdStarPc2().

◆ getSd()

static SCIP_Real getSd	(	SCIP *	scip,
		GRAPH *	g,
		SDGRAPH *	sdgraph,
		PATH *	vnoi,
		SCIP_Real	sd_initial,
		int *	vbase,
		int	i,
		int	i2,
		int	limit
	)

static

get special distance to a single edge

Parameters

scip	SCIP data structure
g	graph structure
sdgraph	special distance graph
vnoi	path structure
sd_initial	initial sd or -1.0
vbase	bases for nearest terminals
i	first vertex
i2	second vertex
limit	limit for incident edges to consider

Definition at line 703 of file reduce_sd.c.

References GRAPH::cost, EAT_LAST, FARAWAY, GE, getcloseterms(), graph_get_nNodes(), GT, GRAPH::head, Is_term, LT, MAX, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_sdgraphGetSd(), SCIP_Real, SCIPisGT(), and GRAPH::term.

Referenced by reduce_bd34WithSd().

◆ sdGetSd()

static SCIP_Real sdGetSd	(	const GRAPH *	g,
		int	i,
		int	i2,
		SCIP_Real	sd_upper,
		SCIP_Real	sd_sufficient,
		SCIP_Bool	onlyIntermedTerms,
		SD *	sddata
	)

inlinestatic

gets special distance to a pair of nodes

Parameters

g	graph structure
i	first vertex
i2	second vertex
sd_upper	upper bound on special distance that is accepted (can be FARAWAY)
sd_sufficient	bound below which to terminate (can be 0.0)
onlyIntermedTerms	allow only paths with intermediate terms
sddata	SD

Definition at line 815 of file reduce_sd.c.

References EQ, GE, graph_tpathsGet4CloseTerms(), GT, Is_term, LT, MAX, NULL, reduce_sdgraphGetSd(), SCIP_Bool, SCIP_Real, special_distance_storage::sdgraph, GRAPH::term, and special_distance_storage::terminalpaths.

Referenced by reduce_sdBiased(), reduce_sdBiasedNeighbor(), reduce_sdGetSd(), reduce_sdGetSdIntermedTerms(), and sdGetSdsCliqueTermWalks().

◆ sdGetSdNeighbor()

static SCIP_Real sdGetSdNeighbor	(	const GRAPH *	g,
		int	i,
		int	i2,
		SCIP_Real	sd_upper,
		SCIP_Real	sd_sufficient,
		SD *	sddata
	)

static

gets special distance to a pair of nodes

Parameters

g	graph structure
i	first vertex
i2	second vertex
sd_upper	upper bound on special distance that is accepted (can be FARAWAY)
sd_sufficient	bound below which to terminate (can be 0.0)
sddata	SD

Definition at line 912 of file reduce_sd.c.

References GT, Is_term, LT, MAX, reduce_sdgraphGetSd(), reduce_sdneighborGetCloseTerms(), SCIP_Bool, SCIP_Real, special_distance_storage::sdgraph, special_distance_storage::sdneighbors, and GRAPH::term.

Referenced by reduce_sdBiasedNeighbor().

◆ isPseudoDeletableDeg3()

static SCIP_Bool isPseudoDeletableDeg3	(	SCIP *	scip,
		const GRAPH *	g,
		const SCIP_Real *	sdsK3,
		const int *	edgesK3,
		SCIP_Real	costK3,
		SCIP_Bool	allowEquality
	)

inlinestatic

is node of degree 3 pseudo-deletable?

Parameters

scip	SCIP data structure
g	graph structure
sdsK3	(unordered) special distances of K3
edgesK3	(unordered) edges of K3
costK3	total edge cost
allowEquality	allow equality?

Definition at line 989 of file reduce_sd.c.

References FALSE, graph_pseudoAncestors_edgesInConflict(), SCIPisLE(), SCIPisLT(), and TRUE.

Referenced by isPseudoDeletable(), reduce_bd34(), and reduce_bd34WithSd().

◆ isPseudoDeletable()

static SCIP_Bool isPseudoDeletable	(	SCIP *	scip,
		const GRAPH *	g,
		const GRAPH *	auxg,
		const SCIP_Real *	ecost,
		const int *	edges,
		int	degree
	)

static

is given graph not part of at least one optimal solution?

Parameters

scip	SCIP data structure
g	graph structure
auxg	auxiliary graph structure
ecost	adjacent edges costs
edges	adjacent edges of node
degree	degree of the node to be checked

Definition at line 1033 of file reduce_sd.c.

References GRAPH::cost, EAT_LAST, EQ, FALSE, graph_isMarked(), graph_path_exec(), graph_pseudoAncestors_edgesInConflict(), GRAPH::head, isPseudoDeletableDeg3(), MST_MODE, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_Real, SCIPisGT(), STP_BD_MAXDEGREE, TRUE, and UNKNOWN.

Referenced by bdkTryDegGe4(), reduce_bd34(), reduce_bd34WithSd(), and spg3StarNeighborRuleOut().

◆ sdCliqueInitData()

static SCIP_RETCODE sdCliqueInitData	(	SCIP *	scip,
		const GRAPH *	g,
		int	centernode,
		const GRAPH *	cliquegraph,
		const int *	cliqueNodeMap,
		DIJK *	dijkdata,
		SDCLIQUE *	sdclique
	)

inlinestatic

initializes data

Parameters

scip	SCIP
g	the graph
centernode	center node or - 1
cliquegraph	clique graph
cliqueNodeMap	maps clique graph vertices to original ones
dijkdata	data for repeated path computations
sdclique	clique

Definition at line 1122 of file reduce_sd.c.

References special_distance_clique::centernode, special_distance_clique::cliquenodes, special_distance_clique::cliqueToNodeMap, special_distance_clique::dijkdata, GRAPH::edges, graph_get_nNodes(), GRAPH::mark, special_distance_clique::ncliquenodes, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, and special_distance_clique::sds.

Referenced by reduce_sdGetSdsCliquegraph().

◆ sdCliqueFreeData()

static void sdCliqueFreeData	(	SCIP *	scip,
		SDCLIQUE *	sdclique
	)

inlinestatic

frees data

Parameters

scip	SCIP
sdclique	clique

Definition at line 1166 of file reduce_sd.c.

References special_distance_clique::cliquenodes, SCIPfreeBufferArray, and special_distance_clique::sds.

Referenced by reduce_sdGetSdsCliquegraph().

◆ sdCliqueUpdateGraphWithStarWalks()

static SCIP_RETCODE sdCliqueUpdateGraphWithStarWalks	(	SCIP *	scip,
		const GRAPH *	g,
		const SDPROFIT *	sdprofit,
		GRAPH *	cliquegraph,
		SDCLIQUE *	sdclique
	)

inlinestatic

tries to improve SDs of clique-graph by using the star SD clique algorithm

Parameters

scip	SCIP
g	the graph
sdprofit	profit or NULL
cliquegraph	clique graph
sdclique	clique

Definition at line 1179 of file reduce_sd.c.

References special_distance_clique::cliqueToNodeMap, GRAPH::cost, EAT_LAST, EQ, flipedge, graph_get_nNodes(), graph_sdComputeCliqueStar(), GT, GRAPH::head, LE, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIP_Real, and special_distance_clique::sds.

Referenced by reduce_sdGetSdsCliquegraph().

◆ sdGetSdsCliqueTermWalks()

static void sdGetSdsCliqueTermWalks	(	const GRAPH *	g,
		SD *RESTRICT	sddata,
		GRAPH *RESTRICT	cliquegraph,
		SDCLIQUE *RESTRICT	sdclique
	)

static

get SDs between all pairs of marked vertices of given clique graph by using terminal-to-terminal special distances

Parameters

g	the graph
sddata	SD
cliquegraph	clique graph to be filled
sdclique	clique

Definition at line 1242 of file reduce_sd.c.

References EAT_LAST, FALSE, FARAWAY, flipedge, graph_get_nNodes(), reduce_sdgraphGetMaxCost(), SCIP_Real, and sdGetSd().

Referenced by reduce_sdGetSdsCliquegraph().

◆ ledgeFromNetgraph()

static SCIP_RETCODE ledgeFromNetgraph	(	SCIP *	scip,
		const GRAPH *	netgraph,
		const PATH *	mst,
		const int *	edgeorg,
		const PATH *	vnoi,
		const int *	vbase,
		GRAPH *	g,
		int *	nelims
	)

static

longest edge reduction test from T. Polzin's "Algorithms for the Steiner problem in networks"

Definition at line 1301 of file reduce_sd.c.

References CONNECT, GRAPH::cost, EAT_LAST, shortest_path::edge, FALSE, graph_edge_del(), graph_get_nEdges(), graph_get_nNodes(), graph_valid(), GRAPH::head, nnodes, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, reduce_unconnected(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), GRAPH::tail, and TRUE.

Referenced by reduce_sd().

◆ reduce_sdGetSdsCliquegraph()

SCIP_RETCODE reduce_sdGetSdsCliquegraph	(	SCIP *	scip,
		const GRAPH *	g,
		int	centernode,
		const int *	cliqueNodeMap,
		DIJK *	dijkdata,
		SD *	sddata,
		GRAPH *	cliquegraph
	)

get SDs between all pairs of marked vertices of given clique graph

Parameters

scip	SCIP
g	the graph
centernode	center node or - 1
cliqueNodeMap	maps clique graph vertices to original ones
dijkdata	data for repeated path computations
sddata	SD
cliquegraph	clique graph to be filled

Definition at line 1394 of file reduce_sd.c.

References GRAPH::edges, GRAPH::knots, SCIP_CALL, SCIP_OKAY, sdCliqueFreeData(), sdCliqueInitData(), sdCliqueUpdateGraphWithStarWalks(), sdGetSdsCliqueTermWalks(), and special_distance_storage::sdprofit.

Referenced by bdkGetCliqueSds(), and testSdGetterReturnsCorrectSds().

◆ reduce_sdImpLongEdge()

SCIP_RETCODE reduce_sdImpLongEdge	(	SCIP *	scip,
		const int *	edgestate,
		GRAPH *	g,
		SD *	sdistance,
		int *	nelims
	)

long edge implied special distance test

Parameters

scip	SCIP data structure
edgestate	array to store status of (directed) edge (for propagation, can otherwise be set to NULL)
g	graph data structure
sdistance	special distances storage
nelims	point to store number of deleted edges

Definition at line 1421 of file reduce_sd.c.

References GRAPH::cost, deleteEdge(), EAT_LAST, EDGE_BLOCKED, FALSE, graph_edge_del(), graph_edge_printInfo(), graph_get_nNodes(), special_distance_storage::hasNeigborUpdate, GRAPH::head, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_sdgraphGetMaxCost(), reduce_sdgraphGetMstHalfMark(), reduce_sdgraphHasMstHalfMark(), reduce_sdneighborGetBlocked(), reduce_unconnected(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), SCIPisGT(), special_distance_storage::sdgraph, special_distance_storage::sdneighbors, and TRUE.

Referenced by reduce_sdBiased(), and reduce_sdBiasedNeighbor().

◆ reduce_sd()

SCIP_RETCODE reduce_sd	(	SCIP *	scip,
		GRAPH *	g,
		REDBASE *	redbase,
		int *	nelims
	)

Special distance test

Parameters

scip	SCIP data structure
g	graph data structure
redbase	reduction data
nelims	point to store number of deleted edges

Definition at line 1517 of file reduce_sd.c.

References GRAPH::cost, EAT_FREE, EAT_LAST, shortest_path::edge, reduction_base::edgearrint, GRAPH::edges, FALSE, flipedge, GE, getlecloseterms(), GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_free(), graph_get4nextTermPaths(), graph_get_nEdges(), graph_get_nNodes(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_valid(), GT, GRAPH::head, Is_term, GRAPH::knots, ledgeFromNetgraph(), LT, GRAPH::mark, MST_MODE, nnodes, reduction_base::nodearrint, reduction_base::nodearrint2, reduction_parameters::nodereplacing, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, reduction_base::redparameters, reduce_bd34WithSd(), reduce_sdgraphFreeFromDistGraph(), reduce_sdgraphGetSd(), reduce_sdgraphInitFromDistGraph(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPisGE(), sddeltable(), GRAPH::source, reduction_base::state, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, UNKNOWN, reduction_parameters::usestrongreds, reduction_base::vbase, and reduction_base::vnoi.

Referenced by redLoopInnerStp().

◆ reduce_sdBiased()

SCIP_RETCODE reduce_sdBiased	(	SCIP *	scip,
		SD *	sdistance,
		GRAPH *	g,
		int *	nelims
	)

implied-profit special distance test

Parameters

scip	SCIP data structure
sdistance	special distances storage
g	graph structure
nelims	number of eliminations

Definition at line 1845 of file reduce_sd.c.

References GRAPH::cost, deleteEdge(), EAT_LAST, EQ, FALSE, FARAWAY, graph_edge_del(), graph_edge_printInfo(), graph_get_nNodes(), graph_mark(), graph_valid(), special_distance_storage::hasNeigborUpdate, GRAPH::head, Is_term, LT, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_sdgraphGetMaxCost(), reduce_sdImpLongEdge(), reduce_sdprofitGetProfit(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisEQ(), SCIPisLT(), sdGetSd(), special_distance_storage::sdgraph, special_distance_storage::sdprofit, GRAPH::term, and TRUE.

Referenced by reduce_impliedProfitBased(), reduce_impliedProfitBasedRpc(), testSdBiasedBottleneckDeletesEdge(), testSdBiasedBottleneckTermPathDeletesEdge(), and testSdBiasedDeletesEdge().

◆ reduce_sdBiasedNeighbor()

SCIP_RETCODE reduce_sdBiasedNeighbor	(	SCIP *	scip,
		SD *	sdistance,
		GRAPH *	g,
		int *	nelims
	)

implied-profit neighbor special distance test NOTE: invalidates SD for other methods!

Parameters

scip	SCIP data structure
sdistance	special distances storage
g	graph structure
nelims	number of eliminations

Definition at line 1927 of file reduce_sd.c.

References GRAPH::cost, deleteEdge(), EAT_LAST, FALSE, graph_edge_del(), graph_edge_printInfo(), graph_get_nNodes(), graph_mark(), graph_valid(), special_distance_storage::hasNeigborUpdate, GRAPH::head, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_sdgraphGetMaxCost(), reduce_sdgraphHasMstHalfMark(), reduce_sdImpLongEdge(), reduce_sdneighborGetBlocked(), reduce_sdUpdateWithSdNeighbors(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisLT(), sdGetSd(), sdGetSdNeighbor(), special_distance_storage::sdgraph, special_distance_storage::sdneighbors, GRAPH::terms, and TRUE.

Referenced by testSdBiasedDeletesEdge().

◆ reduce_sdPc()

SCIP_RETCODE reduce_sdPc	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	vnoi,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nodesid,
		int *	nodesorg,
		int *	nelims
	)

SD test for PC

Parameters

scip	SCIP data structure
g	graph data structure
vnoi	Voronoi data structure
heap	heap array
state	array to store state of a node during Voronoi computation
vbase	Voronoi base to each node
nodesid	array
nodesorg	array
nelims	pointer to store number of eliminated edges

Definition at line 2023 of file reduce_sd.c.

References GRAPH::cost, shortest_path::dist, EAT_FREE, EAT_LAST, GRAPH::edges, GRAPH::extended, FARAWAY, flipedge, getcloseterms(), getcloseterms2term(), graph_edge_add(), graph_edge_del(), graph_free(), graph_get4nextTermPaths(), graph_get4nextTTerms(), graph_init(), graph_knot_add(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGT(), SCIPisLT(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by execPc_SD().

◆ reduce_getSdByPaths()

SCIP_RETCODE reduce_getSdByPaths	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		PATH *	pathhead,
		SCIP_Real *	sdist,
		SCIP_Real	distlimit,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	memlbltail,
		int *	memlblhead,
		int	i,
		int	i2,
		int	limit,
		SCIP_Bool	pc,
		SCIP_Bool	mw
	)

get SD to a single edge by using path computations

Definition at line 2304 of file reduce_sd.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, graph_sdPaths(), GRAPH::head, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPisGT(), SCIPisLE(), SCIPisLT(), GRAPH::term, and UNKNOWN.

Referenced by reduce_chain2(), and reduce_npv().

◆ reduce_sdGetSd()

SCIP_Real reduce_sdGetSd	(	const GRAPH *	g,
		int	i,
		int	i2,
		SCIP_Real	sd_upper,
		SCIP_Real	sd_sufficient,
		SD *	sddata
	)

gets special distance to a pair of nodes

Parameters

g	graph structure
i	first vertex
i2	second vertex
sd_upper	upper bound on special distance that is accepted (can be FARAWAY)
sd_sufficient	bound below which to terminate (can be 0.0)
sddata	SD

Definition at line 2433 of file reduce_sd.c.

References FALSE, and sdGetSd().

Referenced by distDataGetSpecialDist(), and testSdRepair().

◆ reduce_sdGetSdIntermedTerms()

SCIP_Real reduce_sdGetSdIntermedTerms	(	const GRAPH *	g,
		int	i,
		int	i2,
		SCIP_Real	sd_upper,
		SCIP_Real	sd_sufficient,
		SD *	sddata
	)

gets special distance to a pair of nodes, but only allows SDs with intermediate terminals

Parameters

g	graph structure
i	first vertex
i2	second vertex
sd_upper	upper bound on special distance that is accepted (can be FARAWAY)
sd_sufficient	bound below which to terminate (can be 0.0)
sddata	SD

Definition at line 2449 of file reduce_sd.c.

References sdGetSd(), and TRUE.

Referenced by distDataGetSpecialDistIntermedTerms().

◆ sdGetSdPcMw()

static SCIP_Real sdGetSdPcMw	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Real	distlimit,
		int	i,
		int	i2,
		int	edgelimit,
		SD1PC *	sd1pc
	)

static

get SD to a single edge

Definition at line 2466 of file reduce_sd.c.

Referenced by reduce_bd34().

◆ reduce_sdspSap()

SCIP_RETCODE reduce_sdspSap	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		PATH *	pathhead,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	memlbltail,
		int *	memlblhead,
		int *	nelims,
		int	limit
	)

SDC test for the SAP using a limited version of Dijkstra's algorithm from both endpoints of an arc

Parameters

scip	SCIP data structure
g	graph data structure
pathtail	path tails
pathhead	path heads
heap	heap
statetail	states of tails
statehead	states of heads
memlbltail	storage for tails
memlblhead	storage for heads
nelims	number of eliminations
limit	limit for number of visits

Definition at line 2661 of file reduce_sd.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_sdPaths(), GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), SCIPisLT(), TRUE, and UNKNOWN.

Referenced by reduce_sap().

◆ reduce_sdWalk_csr()

SCIP_RETCODE reduce_sdWalk_csr	(	SCIP *	scip,
		int	edgelimit,
		const int *	edgestate,
		GRAPH *	g,
		int *	termmark,
		SCIP_Real *	dist,
		int *	visitlist,
		STP_Bool *	visited,
		DHEAP *	dheap,
		int *	nelims
	)

SD test for PcMw using only limited Dijkstra-like walk from both endpoints of an edge

Parameters

scip	SCIP data structure
edgelimit	edge limit
edgestate	per edge: state
g	graph data structure
termmark	per node: terminal property
dist	per node: distance
visitlist	array to store visited nodes
visited	per node: was visited?
dheap	head data structure
nelims	pointer to store number of eliminations

Definition at line 2818 of file reduce_sd.c.

References dynamic_csr_storage::cost, GRAPH::dcsr_storage, EAT_FREE, EDGE_BLOCKED, dynamic_csr_storage::edgeid, GRAPH::edges, csr_range::end, GRAPH::extended, FALSE, FARAWAY, graph_dcsr_deleteEdgeBi(), graph_edge_delBlocked(), graph_free_dcsr(), graph_heap_clean(), graph_init_dcsr(), graph_pc_isPcMw(), graph_pc_termMarkProper(), graph_sdWalks_csr(), dynamic_csr_storage::head, GRAPH::head, dynamic_csr_storage::id2csredge, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, dijkstra_heap::position, dynamic_csr_storage::range, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, sdwalkReset(), csr_range::start, GRAPH::tail, and TRUE.

◆ reduce_sdEdgeCliqueStar()

SCIP_RETCODE reduce_sdEdgeCliqueStar	(	SCIP *	scip,
		int	edgelimit,
		GRAPH *	g,
		int *	nelims
	)

SD test

Parameters

scip	SCIP data structure
edgelimit	edge limit
g	graph data structure
nelims	number of eliminations

Definition at line 2939 of file reduce_sd.c.

References GRAPH::cost, special_distance_clique::dijkdata, EAT_LAST, dijkstra_data::edgelimit, FARAWAY, graph_dijkLimited_clean(), graph_dijkLimited_free(), graph_dijkLimited_init(), graph_dijkLimited_reset(), graph_edge_del(), graph_edge_printInfo(), graph_get_nNodes(), graph_mark(), graph_sdComputeCliqueStar(), GRAPH::head, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_sdprofitFree(), reduce_sdprofitInit(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisLT(), and TRUE.

Referenced by testSdCliqueStarDeletesEdge().

◆ reduce_sdWalkTriangle()

SCIP_RETCODE reduce_sdWalkTriangle	(	SCIP *	scip,
		int	edgelimit,
		SCIP_Bool	usestrongreds,
		GRAPH *	g,
		int *	termmark,
		SCIP_Real *	dist,
		int *	visitlist,
		STP_Bool *	visited,
		DHEAP *	dheap,
		int *	nelims
	)

SD test for PcMw using limited Dijkstra-like walk from both endpoints of an edge

Parameters

scip	SCIP data structure
edgelimit	edge limit
usestrongreds	allow strong reductions?
g	graph data structure
termmark	terminal mark
dist	distances
visitlist	array to store visited nodes
visited	per node: was visited?
dheap	heap data structure
nelims	number of eliminations

Definition at line 3011 of file reduce_sd.c.

References dynamic_csr_storage::cost, GRAPH::dcsr_storage, EAT_FREE, dynamic_csr_storage::edgeid, GRAPH::edges, csr_range::end, GRAPH::extended, FALSE, FARAWAY, graph_dcsr_deleteEdgeBi(), graph_edge_delBlocked(), graph_free_dcsr(), graph_heap_clean(), graph_init_dcsr(), graph_pc_isPcMw(), graph_pc_termMarkProper(), graph_sdWalksTriangle(), dynamic_csr_storage::head, GRAPH::head, dynamic_csr_storage::id2csredge, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, dijkstra_heap::position, dynamic_csr_storage::range, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisLE(), sdwalkReset(), csr_range::start, GRAPH::tail, TRUE, and UNKNOWN.

Referenced by checkSdWalk(), and redLoopInnerPc().

◆ reduce_sdStar()

SCIP_RETCODE reduce_sdStar	(	SCIP *	scip,
		int	edgelimit,
		SCIP_Bool	usestrongreds,
		GRAPH *	g,
		SCIP_Real *	dist,
		int *	star_base,
		int *	visitlist,
		STP_Bool *	visited,
		DHEAP *	dheap,
		int *	nelims
	)

SD star test for PcMw and SPG

Parameters

scip	SCIP data structure
edgelimit	limit
usestrongreds	allow strong reductions?
g	graph data structure
dist	vertex distances
star_base	array of size nnodes
visitlist	array of size nnodes
visited	array of size nnodes
dheap	Dijkstra heap
nelims	point to store number of deleted edges

Definition at line 3202 of file reduce_sd.c.

References dynamic_csr_storage::cost, GRAPH::dcsr_storage, EAT_FREE, dynamic_csr_storage::edgeid, GRAPH::edges, csr_range::end, GRAPH::extended, FALSE, FARAWAY, GRAPH::grad, graph_dcsr_deleteEdgeBi(), graph_edge_delBlocked(), graph_free_dcsr(), graph_heap_clean(), graph_init_dcsr(), graph_pc_isPcMw(), graph_sdStar(), dynamic_csr_storage::head, GRAPH::head, dynamic_csr_storage::id2csredge, GRAPH::knots, GRAPH::mark, nnodes, GRAPH::oeat, dynamic_csr_storage::range, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisLE(), SDSTAR_BASE_KILLED, SDSTAR_BASE_UNSET, sdStarReset(), GRAPH::source, csr_range::start, GRAPH::tail, and TRUE.

◆ reduce_sdStarBiased()

SCIP_RETCODE reduce_sdStarBiased	(	SCIP *	scip,
		int	edgelimit,
		SCIP_Bool	usestrongreds,
		GRAPH *	g,
		int *	nelims
	)

SD star test for PcMw and SPG

Parameters

scip	SCIP data structure
edgelimit	limit
usestrongreds	allow strong reductions?
g	graph data structure
nelims	point to store number of deleted edges

Definition at line 3332 of file reduce_sd.c.

References reduce_sdprofitFree(), reduce_sdprofitInit(), reduce_sdStarBiasedWithProfit(), SCIP_CALL, and SCIP_OKAY.

Referenced by redLoopInnerPc(), redLoopInnerStp(), testSdStarBiasedDeletesEdge(), testSdStarBiasedDeletesEdge2(), and testSdStarBiasedDeletesEdge3().

◆ reduce_sdStarBiasedWithProfit()

SCIP_RETCODE reduce_sdStarBiasedWithProfit	(	SCIP *	scip,
		int	edgelimit,
		const SDPROFIT *	sdprofit,
		SCIP_Bool	usestrongreds,
		GRAPH *	g,
		int *	nelims
	)

SD star test for PcMw and SPG

Parameters

scip	SCIP data structure
edgelimit	limit
sdprofit	with profit given
usestrongreds	allow strong reductions?
g	graph data structure
nelims	point to store number of deleted edges

Definition at line 3353 of file reduce_sd.c.

References GRAPH::grad, graph_free_dcsr(), graph_get_nNodes(), graph_init_dcsr(), GRAPH::mark, nnodes, SCIP_Bool, SCIP_CALL, SCIP_OKAY, sdStarBiasedProcessNode(), sdStarFinalize(), sdStarInit(), and GRAPH::source.

Referenced by reduce_impliedProfitBased(), and reduce_sdStarBiased().

◆ reduce_sdStarPc2()

SCIP_RETCODE reduce_sdStarPc2	(	SCIP *	scip,
		int	edgelimit,
		SCIP_Bool	usestrongreds,
		GRAPH *	g,
		SCIP_Real *	dist,
		int *	star_base,
		int *	visitlist,
		STP_Bool *	visited,
		DHEAP *	dheap,
		int *	nelims
	)

SD star test for PcMw

Parameters

scip	SCIP data structure
edgelimit	limit
usestrongreds	allow strong reductions?
g	graph data structure
dist	vertex distances
star_base	array of size nnodes
visitlist	array of size nnodes
visited	array of size nnodes
dheap	Dijkstra heap
nelims	point to store number of deleted edges

Definition at line 3394 of file reduce_sd.c.

References dynamic_csr_storage::cost, dynamic_csr_storage::cost2, GRAPH::dcsr_storage, EAT_FREE, dynamic_csr_storage::edgeid, GRAPH::edges, csr_range::end, EQ, GRAPH::extended, FALSE, FARAWAY, GRAPH::grad, graph_dcsr_deleteEdgeBi(), graph_edge_delBlocked(), graph_free_dcsr(), graph_heap_clean(), graph_init_dcsr(), graph_mark(), graph_pc_isPcMw(), graph_sdStar(), dynamic_csr_storage::head, GRAPH::head, dynamic_csr_storage::id2csredge, GRAPH::knots, GRAPH::mark, dynamic_csr_storage::nedges, nnodes, NULL, GRAPH::oeat, pcBiasCostsDCSR(), dynamic_csr_storage::range, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisLE(), SDSTAR_BASE_KILLED, SDSTAR_BASE_UNSET, sdStarReset(), GRAPH::source, csr_range::start, GRAPH::tail, and TRUE.

Referenced by redLoopInnerPc(), and testSdStarPcKillsEdge().

◆ reduce_sdStarPc()

SCIP_RETCODE reduce_sdStarPc	(	SCIP *	scip,
		int	edgelimit,
		const int *	edgestate,
		GRAPH *	g,
		SCIP_Real *	dist,
		int *	star_base,
		int *	visitlist,
		STP_Bool *	visited,
		DHEAP *	dheap,
		int *	nelims
	)

SD star test for PcMw NOTE: deprecated

Parameters

scip	SCIP data structure
edgelimit	limit
edgestate	state array or NULL
g	graph data structure
dist	vertex distances
star_base	array of size nnodes
visitlist	array of size nnodes
visited	array of size nnodes
dheap	Dijkstra heap
nelims	point to store number of deleted edges

Definition at line 3546 of file reduce_sd.c.

◆ reduce_sdWalk()

SCIP_RETCODE reduce_sdWalk	(	SCIP *	scip,
		int	edgelimit,
		const int *	edgestate,
		GRAPH *	g,
		int *	termmark,
		SCIP_Real *	dist,
		int *	heap,
		int *	state,
		int *	visitlist,
		STP_Bool *	visited,
		int *	nelims
	)

SD test for PcMw using only limited Dijkstra-like walk from both endpoints of an edge

Definition at line 3743 of file reduce_sd.c.

References GRAPH::cost, EAT_LAST, EDGE_BLOCKED, GRAPH::extended, FALSE, FARAWAY, graph_edge_del(), graph_pc_isPcMw(), graph_pc_termMarkProper(), graph_sdWalks(), GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_OKAY, SCIP_Real, sdwalkReset(), TRUE, and UNKNOWN.

◆ reduce_sdWalkExt()

SCIP_RETCODE reduce_sdWalkExt	(	SCIP *	scip,
		int	edgelimit,
		SCIP_Bool	usestrongreds,
		GRAPH *	g,
		SCIP_Real *	dist,
		int *	heap,
		int *	state,
		int *	visitlist,
		STP_Bool *	visited,
		int *	nelims
	)

SD test for PcMw using only limited Dijkstra-like walk from both endpoints of an edge

Parameters

scip	SCIP data structure
edgelimit	edge limit
usestrongreds	allow strong reductions?
g	graph data structure
dist	per node: distances
heap	heap
state	state
visitlist	array to store visited nodes
visited	number of visited nodes
nelims	number of eliminations

Definition at line 3827 of file reduce_sd.c.

References GRAPH::cost, EAT_LAST, GRAPH::extended, FALSE, FARAWAY, graph_edge_del(), graph_pc_isPcMw(), graph_sdWalksExt(), GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, sdwalkResetExt(), STP_SDWALK_MAXNPREVS, TRUE, and UNKNOWN.

Referenced by checkSdWalk(), and redLoopInnerPc().

◆ reduce_sdWalkExt2()

SCIP_RETCODE reduce_sdWalkExt2	(	SCIP *	scip,
		int	edgelimit,
		const int *	edgestate,
		GRAPH *	g,
		int *	termmark,
		SCIP_Real *	dist,
		int *	heap,
		int *	state,
		int *	visitlist,
		STP_Bool *	visited,
		int *	nelims
	)

SD test for PcMw using only limited Dijkstra-like walk from both endpoints of an edge

Parameters

scip	SCIP data structure
edgelimit	edge limit
edgestate	per edge: state
g	graph data structure
termmark	per node: terminal state
dist	per node: distance
heap	heap
state	state
visitlist	visited nodes
visited	number of visited nodes
nelims	number of eliminations

Definition at line 3910 of file reduce_sd.c.

References GRAPH::cost, EAT_LAST, EDGE_BLOCKED, GRAPH::extended, FALSE, FARAWAY, graph_edge_del(), graph_pc_isPcMw(), graph_pc_termMarkProper(), graph_sdWalksExt2(), GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, sdwalkResetExt2(), STP_SDWALK_MAXNPREVS, TRUE, and UNKNOWN.

◆ reduce_sdsp()

SCIP_RETCODE reduce_sdsp	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	memlbltail,
		int *	memlblhead,
		int *	nelims,
		int	limit,
		SCIP_Bool	usestrongreds
	)

SD test using only limited Dijkstra from both endpoints of an edge

Parameters

scip	SCIP data structure
g	graph data structure
pathtail	path tails
heap	heap
statetail	tails
statehead	heads
memlbltail	to save changed tails
memlblhead	to save changed heads
nelims	number of eliminations
limit	limit for number checks
usestrongreds	allow strong reductions?

Definition at line 4020 of file reduce_sd.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::extended, FALSE, FARAWAY, GRAPH::grad, graph_edge_del(), graph_get_nNodes(), graph_path_PcMwSd(), graph_sdPaths(), graph_valid(), GRAPH::head, Is_term, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisNegative(), SCIPisPositive(), STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by redLoopInnerStp().

◆ reduce_bd34WithSd()

SCIP_RETCODE reduce_bd34WithSd	(	SCIP *	scip,
		GRAPH *	g,
		SDGRAPH *	sdgraph,
		PATH *	vnoi,
		int *	vbase,
		int *	nelims
	)

bd_k test for given Steiner bottleneck distances

Parameters

scip	SCIP data structure
g	graph structure
sdgraph	auxiliary graph structure
vnoi	path structure
vbase	bases for nearest terminals
nelims	number of eliminations

Definition at line 4310 of file reduce_sd.c.

References GRAPH::cost, EAT_LAST, GRAPH::edges, EQ, flipedge, getSd(), GRAPH::grad, graph_buildCompleteGraph(), graph_free(), graph_knot_delPseudo(), graph_mark(), graph_path_exit(), graph_path_init(), graph_pc_isPcMw(), graph_valid(), GRAPH::head, Is_term, isPseudoDeletable(), isPseudoDeletableDeg3(), GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_unconnected(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, STP_BD_MAXDEGREE, STP_BD_MAXDNEDGES, GRAPH::term, and TRUE.

Referenced by reduce_sd().

◆ reduce_bd34()

SCIP_RETCODE reduce_bd34	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		PATH *	pathhead,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	memlbltail,
		int *	memlblhead,
		int *	nelims,
		int	limit,
		SCIP_Real *	offset
	)

Parameters

scip	SCIP data structure
g	graph structure
pathtail	array for internal use
pathhead	array for internal use
heap	array for internal use
statetail	array for internal use
statehead	array for internal use
memlbltail	array for internal use
memlblhead	array for internal use
nelims	point to return number of eliminations
limit	limit for edges to consider for each vertex
offset	offset

Definition at line 4516 of file reduce_sd.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, EQ, GRAPH::extended, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_buildCompleteGraph(), graph_free(), graph_knot_delPseudo(), graph_mark(), graph_path_exit(), graph_path_init(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_realDegree(), graph_pc_termIsNonLeafTerm(), graph_valid(), GRAPH::head, Is_term, isPseudoDeletable(), isPseudoDeletableDeg3(), GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, single_special_distance_pc::pathtail, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArrayNull, sdGetSdPcMw(), STP_BD_MAXDEGREE, STP_BD_MAXDNEDGES, GRAPH::term, TRUE, and UNKNOWN.

Referenced by execPc_BDk().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ STP_BD_MAXDEGREE

◆ STP_BD_MAXDNEDGES

◆ STP_SDWALK_MAXNPREVS

Function Documentation

◆ sdStarInit()

◆ sdStarFinalize()

◆ sdStarReset()

◆ sdStarBiasedProcessNode()

◆ sdwalkReset()

◆ sdwalkResetExt()

◆ sdwalkResetExt2()

◆ sddeltable()

◆ getcloseterms()

◆ getcloseterms2term()

◆ getlecloseterms()

◆ pcBiasCostsDCSR()

◆ getSd()

◆ sdGetSd()

◆ sdGetSdNeighbor()

◆ isPseudoDeletableDeg3()

◆ isPseudoDeletable()

◆ sdCliqueInitData()

◆ sdCliqueFreeData()

◆ sdCliqueUpdateGraphWithStarWalks()

◆ sdGetSdsCliqueTermWalks()

◆ ledgeFromNetgraph()

◆ reduce_sdGetSdsCliquegraph()

◆ reduce_sdImpLongEdge()

◆ reduce_sd()

◆ reduce_sdBiased()

◆ reduce_sdBiasedNeighbor()

◆ reduce_sdPc()

◆ reduce_getSdByPaths()

◆ reduce_sdGetSd()

◆ reduce_sdGetSdIntermedTerms()

◆ sdGetSdPcMw()

◆ reduce_sdspSap()

◆ reduce_sdWalk_csr()

◆ reduce_sdEdgeCliqueStar()

◆ reduce_sdWalkTriangle()

◆ reduce_sdStar()

◆ reduce_sdStarBiased()

◆ reduce_sdStarBiasedWithProfit()

◆ reduce_sdStarPc2()

◆ reduce_sdStarPc()

◆ reduce_sdWalk()

◆ reduce_sdWalkExt()

◆ reduce_sdWalkExt2()

◆ reduce_sdsp()

◆ reduce_bd34WithSd()

◆ reduce_bd34()