Detailed Description

includes graph pseudo deletion methods for Steiner problems

Author: Daniel Rehfeldt

Graph node or edge pseudo-deletion methods (aka replacement methods) for Steiner problems

#include "graph.h"
#include "portab.h"

Data Structures
struct	pseudo_deletion

Macros
#define	STP_DELPSEUDO_NOEDGE -1

#define	STP_DELPSEUDO_SKIPEDGE -2

Typedefs
typedef struct pseudo_deletion	DELPSEUDO

Functions
static SCIP_Bool	isCutoffEdge (SCIP scip, const SCIP_Real cutoffs, const SCIP_Real cutoffsrev, const SCIP_Real ecost, const SCIP_Real *ecostrev, SCIP_Real prize, int edgeidx1, int edgeidx2, int cutoffidx)

static SCIP_Bool	delPseudoIsEdgeDeletionMode (const DELPSEUDO *delpseudo)

static int	delPseudoGetEdgePosition (const DELPSEUDO *delpseudo)

static SCIP_RETCODE	delPseudoInit (SCIP scip, const SCIP_Real edgecosts, const REDCOST redcostdata, int vertex, GRAPH g, DELPSEUDO *delpseudo)

static SCIP_RETCODE	delPseudoInitForCheck (SCIP scip, const GRAPH g, const SCIP_Real edgecosts, int vertex, DELPSEUDO delpseudo)

static SCIP_RETCODE	delPseudoDeleteVertex (SCIP scip, int vertex, GRAPH g, REDCOST redcostdata, DELPSEUDO delpseudo)

static SCIP_RETCODE	delPseudoGetReplaceEdges (SCIP scip, const GRAPH g, const SCIP_Real cutoffs, const SCIP_Real cutoffsrev, DELPSEUDO delpseudo, SCIP_Bool success)

static SCIP_RETCODE	delPseudoCheckReplacement (SCIP scip, const GRAPH g, const SCIP_Real cutoffs, const SCIP_Real cutoffsrev, DELPSEUDO delpseudo, SCIP_Bool success)

static SCIP_RETCODE	delPseudoEdgeInit (SCIP scip, const SCIP_Real edgecosts, const SCIP_Real edgecosts_adapt, GRAPH g, DELPSEUDO *delpseudo)

static SCIP_RETCODE	delPseudoEdgeGetReplaceEdges (SCIP scip, const GRAPH g, const SCIP_Real cutoffs, const SCIP_Real cutoffsrev, DELPSEUDO delpseudo, SCIP_Bool success)

static SCIP_RETCODE	delPseudoEdgeDeleteEdge (SCIP scip, GRAPH g, SCIP_Real edgecosts_adapt, DELPSEUDO delpseudo)

static void	delPseudoFreeData (SCIP scip, DELPSEUDO delpseudo)

static void	delPseudoFreeDataForCheck (SCIP scip, DELPSEUDO delpseudo)

static SCIP_RETCODE	delPseudoPathCreatePseudoAncestorTuple (SCIP scip, GRAPH g, int edge1, int edge2)

static SCIP_RETCODE	delPseudoPath (SCIP scip, GRAPH g, int edge, int edge_pathtail, int edge_pathhead, SCIP_Real *edgecosts_adapt)

SCIP_RETCODE	graph_knot_delPseudo (SCIP scip, GRAPH g, const SCIP_Real cutoffcosts, const SCIP_Real cutoffs, const SCIP_Real cutoffsrev, int vertex, REDCOST redcostdata, SCIP_Bool *success)

SCIP_RETCODE	graph_knot_delPseudoCheckIfPossible (SCIP scip, const GRAPH g, const SCIP_Real cutoffcosts, const SCIP_Real cutoffs, const SCIP_Real cutoffsrev, int vertex, SCIP_Bool isPossible)

SCIP_RETCODE	graph_edge_delPseudo (SCIP scip, GRAPH g, const SCIP_Real cutoffcosts, const SCIP_Real cutoffs, const SCIP_Real cutoffsrev, int edge, SCIP_Real edgecosts_adapt, SCIP_Bool *success)

SCIP_RETCODE	graph_edge_delPseudoPath (SCIP scip, GRAPH g, int edge, int edge_pathtail, int edge_pathhead, SCIP_Real *edgecosts_adapt)

Macro Definition Documentation

◆ STP_DELPSEUDO_NOEDGE

#define STP_DELPSEUDO_NOEDGE -1

Definition at line 33 of file graph_delpseudo.c.

Referenced by delPseudoDeleteVertex(), delPseudoEdgeDeleteEdge(), delPseudoEdgeGetReplaceEdges(), and delPseudoGetReplaceEdges().

◆ STP_DELPSEUDO_SKIPEDGE

#define STP_DELPSEUDO_SKIPEDGE -2

Definition at line 34 of file graph_delpseudo.c.

Referenced by delPseudoDeleteVertex(), delPseudoEdgeDeleteEdge(), delPseudoEdgeGetReplaceEdges(), and delPseudoGetReplaceEdges().

Typedef Documentation

◆ DELPSEUDO

typedef struct pseudo_deletion DELPSEUDO

Internal data for pseudo-deletion. Is used for both pseudo-elimination of vertex and edge. In the latter case, the adjacency information is w.r.t. the head of the edge.

Function Documentation

◆ isCutoffEdge()

static SCIP_Bool isCutoffEdge	(	SCIP *	scip,
		const SCIP_Real *	cutoffs,
		const SCIP_Real *	cutoffsrev,
		const SCIP_Real *	ecost,
		const SCIP_Real *	ecostrev,
		SCIP_Real	prize,
		int	edgeidx1,
		int	edgeidx2,
		int	cutoffidx
	)

inlinestatic

can edge in pseudo-elimination method be cut off?

Parameters

scip	SCIP data
cutoffs	cutoff values for each incident edge
cutoffsrev	revere cutoff values (or NULL if undirected)
ecost	edge cost
ecostrev	reverse edge cost
prize	prize if PcMw, 0.0 otherwise
edgeidx1	index of first edge to be checked (wrt provided arrays)
edgeidx2	index of second edge to be checked (wrt provided arrays)
cutoffidx	index for cutoff array

Definition at line 65 of file graph_delpseudo.c.

References FALSE, NULL, SCIP_Real, SCIPisGT(), and TRUE.

Referenced by delPseudoCheckReplacement(), delPseudoEdgeGetReplaceEdges(), and delPseudoGetReplaceEdges().

◆ delPseudoIsEdgeDeletionMode()

static SCIP_Bool delPseudoIsEdgeDeletionMode ( const DELPSEUDO * delpseudo )

static

in edge deletion mode?

Parameters

delpseudo data

Definition at line 104 of file graph_delpseudo.c.

References pseudo_deletion::edge, and UNKNOWN.

Referenced by delPseudoEdgeGetReplaceEdges(), delPseudoEdgeInit(), delPseudoGetEdgePosition(), delPseudoInit(), delPseudoInitForCheck(), graph_edge_delPseudo(), graph_knot_delPseudo(), and graph_knot_delPseudoCheckIfPossible().

◆ delPseudoGetEdgePosition()

static int delPseudoGetEdgePosition ( const DELPSEUDO * delpseudo )

inlinestatic

gets position of deletion edge in replacement arrays

Parameters

delpseudo data

Definition at line 118 of file graph_delpseudo.c.

References pseudo_deletion::degree, delPseudoIsEdgeDeletionMode(), pseudo_deletion::edge, flipedge, and pseudo_deletion::incedge.

Referenced by delPseudoEdgeDeleteEdge(), and delPseudoEdgeGetReplaceEdges().

◆ delPseudoInit()

static SCIP_RETCODE delPseudoInit	(	SCIP *	scip,
		const SCIP_Real *	edgecosts,
		const REDCOST *	redcostdata,
		int	vertex,
		GRAPH *	g,
		DELPSEUDO *	delpseudo
	)

static

initializes

Parameters

scip	SCIP data
edgecosts	edge costs for cutoff
redcostdata	reduced cost data for adaptation or NULL
vertex	the vertex
g	graph
delpseudo	data

Definition at line 147 of file graph_delpseudo.c.

References pseudo_deletion::adjvert, pseudo_deletion::ancestorsnode, GRAPH::cost, pseudo_deletion::degree, delPseudoIsEdgeDeletionMode(), EAT_LAST, pseudo_deletion::ecost, pseudo_deletion::ecost_adapt, pseudo_deletion::ecost_adaptrev, pseudo_deletion::ecostreal, pseudo_deletion::ecostrev, flipedge, GRAPH::grad, graph_pc_isPcMw(), graph_pc_knotHasMaxPrize(), graph_pc_termToNonTerm(), GRAPH::head, pseudo_deletion::incedge, Is_term, pseudo_deletion::neigbedge, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::pcancestors, GRAPH::prize, redcosts_getEdgeCosts(), redcosts_getNlevels(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPisZero(), STP_DELPSEUDO_MAXGRAD, STP_DELPSEUDO_MAXNEDGES, GRAPH::term, and pseudo_deletion::vertexprize.

Referenced by delPseudoEdgeInit(), and graph_knot_delPseudo().

◆ delPseudoInitForCheck()

static SCIP_RETCODE delPseudoInitForCheck	(	SCIP *	scip,
		const GRAPH *	g,
		const SCIP_Real *	edgecosts,
		int	vertex,
		DELPSEUDO *	delpseudo
	)

static

initializes for check

Parameters

scip	SCIP data
g	graph
edgecosts	edge costs for cutoff
vertex	the vertex
delpseudo	data

Definition at line 256 of file graph_delpseudo.c.

References pseudo_deletion::adjvert, pseudo_deletion::ancestorsnode, GRAPH::cost, pseudo_deletion::degree, delPseudoIsEdgeDeletionMode(), EAT_LAST, pseudo_deletion::ecost, pseudo_deletion::ecost_adapt, pseudo_deletion::ecost_adaptrev, pseudo_deletion::ecostreal, pseudo_deletion::ecostrev, FALSE, flipedge, GRAPH::grad, graph_pc_isPcMw(), graph_pc_knotHasMaxPrize(), graph_pc_realDegree(), GRAPH::head, pseudo_deletion::incedge, Is_term, pseudo_deletion::neigbedge, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::pcancestors, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPisZero(), STP_DELPSEUDO_MAXGRAD, GRAPH::term, and pseudo_deletion::vertexprize.

Referenced by graph_knot_delPseudoCheckIfPossible().

◆ delPseudoDeleteVertex()

static SCIP_RETCODE delPseudoDeleteVertex	(	SCIP *	scip,
		int	vertex,
		GRAPH *	g,
		REDCOST *	redcostdata,
		DELPSEUDO *	delpseudo
	)

static

pseudo-eliminates vertex

Parameters

scip	SCIP data
vertex	the vertex
g	graph
redcostdata	reduced cost data for adaptation or NULL
delpseudo	data

Definition at line 338 of file graph_delpseudo.c.

References pseudo_deletion::adjvert, pseudo_deletion::ancestorsnode, pseudo_deletion::degree, pseudo_deletion::ecost_adapt, pseudo_deletion::ecost_adaptrev, pseudo_deletion::ecostreal, EQ, flipedge, graph_addPseudoAncestor(), graph_edge_reinsert(), graph_knot_del(), graph_pc_isPc(), graph_pseudoAncestors_addToEdge(), graph_singletonAncestors_freeMembers(), graph_singletonAncestors_init(), GRAPH::head, pseudo_deletion::incedge, pseudo_deletion::neigbedge, redcosts_getEdgeCosts(), redcosts_getNlevels(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, STP_DELPSEUDO_MAXGRAD, STP_DELPSEUDO_MAXNEDGES, STP_DELPSEUDO_NOEDGE, STP_DELPSEUDO_SKIPEDGE, GRAPH::tail, TRUE, and pseudo_deletion::vertexprize.

Referenced by graph_knot_delPseudo().

◆ delPseudoGetReplaceEdges()

static SCIP_RETCODE delPseudoGetReplaceEdges	(	SCIP *	scip,
		const GRAPH *	g,
		const SCIP_Real *	cutoffs,
		const SCIP_Real *	cutoffsrev,
		DELPSEUDO *	delpseudo,
		SCIP_Bool *	success
	)

static

gets replacement edges; helper function for pseudo-elimination

Parameters

scip	SCIP data
g	graph
cutoffs	cutoff values for each incident edge (or NULL)
cutoffsrev	reverse edge cutoff values (or NULL if undirected or non-existent)
delpseudo	data
success	enough replace edges available?

Definition at line 458 of file graph_delpseudo.c.

References pseudo_deletion::adjvert, pseudo_deletion::degree, EAT_LAST, pseudo_deletion::ecost, pseudo_deletion::ecostrev, FALSE, graph_pseudoAncestors_edgeIsHashed(), graph_pseudoAncestors_hashEdge(), graph_pseudoAncestors_unhashEdge(), graph_pseudoAncestorsGetHashArraySize(), GRAPH::head, pseudo_deletion::incedge, isCutoffEdge(), pseudo_deletion::neigbedge, GRAPH::oeat, GRAPH::outbeg, GRAPH::pseudoancestors, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocCleanBufferArray, SCIPfreeCleanBufferArray, STP_DELPSEUDO_MAXGRAD, STP_DELPSEUDO_MAXNEDGES, STP_DELPSEUDO_NOEDGE, STP_DELPSEUDO_SKIPEDGE, TRUE, and pseudo_deletion::vertexprize.

Referenced by graph_knot_delPseudo().

◆ delPseudoCheckReplacement()

static SCIP_RETCODE delPseudoCheckReplacement	(	SCIP *	scip,
		const GRAPH *	g,
		const SCIP_Real *	cutoffs,
		const SCIP_Real *	cutoffsrev,
		DELPSEUDO *	delpseudo,
		SCIP_Bool *	success
	)

static

checks whether replacement is possible

Parameters

scip	SCIP data
g	graph
cutoffs	cutoff values for each incident edge (or NULL)
cutoffsrev	reverse edge cutoff values (or NULL if undirected or non-existent)
delpseudo	data
success	enough replace edges available?

Definition at line 552 of file graph_delpseudo.c.

References pseudo_deletion::adjvert, pseudo_deletion::degree, EAT_LAST, pseudo_deletion::ecost, pseudo_deletion::ecostrev, FALSE, graph_pseudoAncestors_edgeIsHashed(), graph_pseudoAncestors_hashEdge(), graph_pseudoAncestors_unhashEdge(), graph_pseudoAncestorsGetHashArraySize(), GRAPH::head, pseudo_deletion::incedge, isCutoffEdge(), GRAPH::oeat, GRAPH::outbeg, GRAPH::pseudoancestors, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocCleanBufferArray, SCIPfreeCleanBufferArray, STP_DELPSEUDO_MAXGRAD, STP_DELPSEUDO_MAXNEDGES, TRUE, and pseudo_deletion::vertexprize.

Referenced by graph_knot_delPseudoCheckIfPossible().

◆ delPseudoEdgeInit()

static SCIP_RETCODE delPseudoEdgeInit	(	SCIP *	scip,
		const SCIP_Real *	edgecosts,
		const SCIP_Real *	edgecosts_adapt,
		GRAPH *	g,
		DELPSEUDO *	delpseudo
	)

static

initializes for edge elimination

Parameters

scip	SCIP data
edgecosts	edge costs for cutoff
edgecosts_adapt	edge costs that should be adapted
g	graph
delpseudo	data

Definition at line 639 of file graph_delpseudo.c.

References delPseudoInit(), delPseudoIsEdgeDeletionMode(), pseudo_deletion::edge, GRAPH::head, NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by graph_edge_delPseudo().

◆ delPseudoEdgeGetReplaceEdges()

static SCIP_RETCODE delPseudoEdgeGetReplaceEdges	(	SCIP *	scip,
		const GRAPH *	g,
		const SCIP_Real *	cutoffs,
		const SCIP_Real *	cutoffsrev,
		DELPSEUDO *	delpseudo,
		SCIP_Bool *	success
	)

static

gets replacement edges for edge elimination; helper function for pseudo-elimination

Parameters

scip	SCIP data
g	graph
cutoffs	cutoff values for each incident edge (or NULL)
cutoffsrev	reverse edge cutoff values (or NULL if undirected or non-existent)
delpseudo	data
success	enough replace edges available?

Definition at line 662 of file graph_delpseudo.c.

References pseudo_deletion::adjvert, GRAPH::cost, pseudo_deletion::degree, delPseudoGetEdgePosition(), delPseudoIsEdgeDeletionMode(), EAT_LAST, pseudo_deletion::ecost, pseudo_deletion::ecostrev, pseudo_deletion::edge, EQ, FALSE, flipedge, graph_pseudoAncestors_edgeIsHashed(), graph_pseudoAncestors_hashEdge(), graph_pseudoAncestors_unhashEdge(), graph_pseudoAncestorsGetHashArraySize(), GRAPH::head, pseudo_deletion::incedge, isCutoffEdge(), pseudo_deletion::neigbedge, GRAPH::oeat, GRAPH::outbeg, GRAPH::pseudoancestors, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocCleanBufferArray, SCIPdebugMessage, SCIPfreeCleanBufferArray, STP_DELPSEUDO_MAXGRAD, STP_DELPSEUDO_NOEDGE, STP_DELPSEUDO_SKIPEDGE, GRAPH::tail, TRUE, and pseudo_deletion::vertexprize.

Referenced by graph_edge_delPseudo().

◆ delPseudoEdgeDeleteEdge()

static SCIP_RETCODE delPseudoEdgeDeleteEdge	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	edgecosts_adapt,
		DELPSEUDO *	delpseudo
	)

static

pseudo-eliminates edge

Parameters

scip	SCIP data
g	graph
edgecosts_adapt	edge costs that should be adapted
delpseudo	data

Definition at line 762 of file graph_delpseudo.c.

References pseudo_deletion::adjvert, pseudo_deletion::ancestorsnode, pseudo_deletion::degree, delPseudoGetEdgePosition(), pseudo_deletion::ecost_adapt, pseudo_deletion::ecost_adaptrev, pseudo_deletion::ecostreal, pseudo_deletion::edge, EQ, flipedge, graph_edge_del(), graph_edge_printInfo(), graph_edge_reinsert(), graph_singletonAncestors_freeMembers(), graph_singletonAncestors_init(), GRAPH::head, pseudo_deletion::incedge, pseudo_deletion::neigbedge, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, STP_DELPSEUDO_MAXGRAD, STP_DELPSEUDO_NOEDGE, STP_DELPSEUDO_SKIPEDGE, GRAPH::tail, TRUE, and pseudo_deletion::vertexprize.

Referenced by graph_edge_delPseudo().

◆ delPseudoFreeData()

static void delPseudoFreeData	(	SCIP *	scip,
		DELPSEUDO *	delpseudo
	)

static

frees data

Parameters

scip	SCIP data
delpseudo	data

Definition at line 874 of file graph_delpseudo.c.

References pseudo_deletion::adjvert, pseudo_deletion::ecost, pseudo_deletion::ecost_adapt, pseudo_deletion::ecost_adaptrev, pseudo_deletion::ecostreal, pseudo_deletion::ecostrev, pseudo_deletion::incedge, pseudo_deletion::neigbedge, SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, STP_DELPSEUDO_MAXGRAD, and STP_DELPSEUDO_MAXNEDGES.

Referenced by graph_edge_delPseudo(), and graph_knot_delPseudo().

◆ delPseudoFreeDataForCheck()

static void delPseudoFreeDataForCheck	(	SCIP *	scip,
		DELPSEUDO *	delpseudo
	)

static

frees data from check

Parameters

scip	SCIP data
delpseudo	data

Definition at line 897 of file graph_delpseudo.c.

References pseudo_deletion::adjvert, pseudo_deletion::ecost, pseudo_deletion::ecost_adapt, pseudo_deletion::ecost_adaptrev, pseudo_deletion::ecostreal, pseudo_deletion::ecostrev, pseudo_deletion::incedge, pseudo_deletion::neigbedge, SCIPfreeBlockMemoryArray, and STP_DELPSEUDO_MAXGRAD.

Referenced by graph_knot_delPseudoCheckIfPossible().

◆ delPseudoPathCreatePseudoAncestorTuple()

static SCIP_RETCODE delPseudoPathCreatePseudoAncestorTuple	(	SCIP *	scip,
		GRAPH *	g,
		int	edge1,
		int	edge2
	)

inlinestatic

does the path replacement

Parameters

scip	SCIP data structure
g	the graph
edge1	first edge
edge2	second edge

Definition at line 914 of file graph_delpseudo.c.

References graph_addPseudoAncestor(), graph_edge_isInRange(), graph_pseudoAncestors_addToEdge(), SCIP_CALL, and SCIP_OKAY.

Referenced by delPseudoPath().

◆ delPseudoPath()

static SCIP_RETCODE delPseudoPath	(	SCIP *	scip,
		GRAPH *	g,
		int	edge,
		int	edge_pathtail,
		int	edge_pathhead,
		SCIP_Real *	edgecosts_adapt
	)

static

does the path replacement

Parameters

scip	SCIP data structure
g	the graph
edge	the edge to be replaced, mind the orientation!
edge_pathtail	tail edge of path
edge_pathhead	head edge of path
edgecosts_adapt	costs to adapt or NULL

Definition at line 936 of file graph_delpseudo.c.

References GRAPH::ancestors, GRAPH::cost, delPseudoPathCreatePseudoAncestorTuple(), EAT_LAST, pseudo_deletion::edge, Edge_even, FALSE, flipedge, graph_edge_getAncestors(), graph_edge_printInfo(), graph_edge_redirect(), graph_pseudoAncestors_appendCopyEdge(), graph_typeIsUndirected(), GRAPH::head, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPintListNodeAppendCopy(), GRAPH::tail, and TRUE.

Referenced by graph_edge_delPseudoPath().

◆ graph_knot_delPseudo()

SCIP_RETCODE graph_knot_delPseudo	(	SCIP *	scip,
		GRAPH *	g,
		const SCIP_Real *	cutoffcosts,
		const SCIP_Real *	cutoffs,
		const SCIP_Real *	cutoffsrev,
		int	vertex,
		REDCOST *	redcostdata,
		SCIP_Bool *	success
	)

pseudo delete node, i.e. reconnect neighbors; maximum degree of STP_DELPSEUDO_MAXGRAD!

Parameters

scip	SCIP data structure
g	the graph
cutoffcosts	edge costs for cutoff
cutoffs	cutoff values for each incident edge (or NULL)
cutoffsrev	reverse edge cutoff values (or NULL if undirected or non-existent)
vertex	the vertex
redcostdata	reduced cost data for adaptation or NULL
success	has node been pseudo-eliminated?

Definition at line 1015 of file graph_delpseudo.c.

References delPseudoDeleteVertex(), delPseudoFreeData(), delPseudoGetReplaceEdges(), delPseudoInit(), delPseudoIsEdgeDeletionMode(), GRAPH::grad, NULL, SCIP_CALL, SCIP_OKAY, STP_DELPSEUDO_MAXGRAD, STP_DELPSEUDO_MAXNEDGES, TRUE, and UNKNOWN.

Referenced by bdkTryDeg3(), bdkTryDegGe4(), boundPruneHeur(), pseudoDelDouble(), pseudodeleteDeleteNode(), pseudoDelSingle(), reduce_applyPseudoDeletions(), reduce_bd34(), reduce_bd34WithSd(), and reduce_bound().

◆ graph_knot_delPseudoCheckIfPossible()

SCIP_RETCODE graph_knot_delPseudoCheckIfPossible	(	SCIP *	scip,
		const GRAPH *	g,
		const SCIP_Real *	cutoffcosts,
		const SCIP_Real *	cutoffs,
		const SCIP_Real *	cutoffsrev,
		int	vertex,
		SCIP_Bool *	isPossible
	)

checks whether pseudo-deletion is possible; maximum degree of STP_DELPSEUDO_MAXGRAD!

Parameters

scip	SCIP data structure
g	the graph
cutoffcosts	edge costs for cutoff
cutoffs	cutoff values for each incident edge (or NULL)
cutoffsrev	reverse edge cutoff values (or NULL if undirected or non-existent)
vertex	the vertex
isPossible	can vertex pseudo-eliminated?

Definition at line 1063 of file graph_delpseudo.c.

References delPseudoCheckReplacement(), delPseudoFreeDataForCheck(), delPseudoInitForCheck(), delPseudoIsEdgeDeletionMode(), GRAPH::grad, NULL, SCIP_CALL, SCIP_OKAY, STP_DELPSEUDO_MAXGRAD, TRUE, and UNKNOWN.

Referenced by pseudodeleteDeleteComputeCutoffs().

◆ graph_edge_delPseudo()

SCIP_RETCODE graph_edge_delPseudo	(	SCIP *	scip,
		GRAPH *	g,
		const SCIP_Real *	cutoffcosts,
		const SCIP_Real *	cutoffs,
		const SCIP_Real *	cutoffsrev,
		int	edge,
		SCIP_Real *	edgecosts_adapt,
		SCIP_Bool *	success
	)

Pseudo deletes edge, i.e. reconnects tail of edge with neighbors of head; maximum degree of STP_DELPSEUDO_MAXGRAD! The orientation of the edge is important!

Parameters

scip	SCIP data structure
g	the graph
cutoffcosts	edge costs for cutoff
cutoffs	cutoff values for each incident edge (or NULL)
cutoffsrev	reverse edge cutoff values (or NULL if undirected or non-existent)
edge	the edge, mind the orientation!
edgecosts_adapt	costs to adapt or NULL
success	has node been pseudo-eliminated?

Definition at line 1097 of file graph_delpseudo.c.

References delPseudoEdgeDeleteEdge(), delPseudoEdgeGetReplaceEdges(), delPseudoEdgeInit(), delPseudoFreeData(), delPseudoIsEdgeDeletionMode(), GRAPH::grad, graph_edge_isInRange(), GRAPH::head, NULL, SCIP_CALL, SCIP_OKAY, STP_DELPSEUDO_MAXGRAD, and TRUE.

Referenced by bdkTryDegGe4().

◆ graph_edge_delPseudoPath()

SCIP_RETCODE graph_edge_delPseudoPath	(	SCIP *	scip,
		GRAPH *	g,
		int	edge,
		int	edge_pathtail,
		int	edge_pathhead,
		SCIP_Real *	edgecosts_adapt
	)

Path replacement of edge; path is given by three oriented edges: edge_pathtail -> edge -> edge_pathhead. Middle edges is replaced.

Parameters

scip	SCIP data structure
g	the graph
edge	the edge to be replaced, mind the orientation!
edge_pathtail	tail edge of path
edge_pathhead	head edge of path
edgecosts_adapt	costs to adapt or NULL

Definition at line 1136 of file graph_delpseudo.c.

References delPseudoPath(), graph_edge_isInRange(), GRAPH::head, SCIP_CALL, SCIP_OKAY, and GRAPH::tail.

Referenced by replaceEdgeByPath().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ STP_DELPSEUDO_NOEDGE

◆ STP_DELPSEUDO_SKIPEDGE

Typedef Documentation

◆ DELPSEUDO

Function Documentation

◆ isCutoffEdge()

◆ delPseudoIsEdgeDeletionMode()

◆ delPseudoGetEdgePosition()

◆ delPseudoInit()

◆ delPseudoInitForCheck()

◆ delPseudoDeleteVertex()

◆ delPseudoGetReplaceEdges()

◆ delPseudoCheckReplacement()

◆ delPseudoEdgeInit()

◆ delPseudoEdgeGetReplaceEdges()

◆ delPseudoEdgeDeleteEdge()

◆ delPseudoFreeData()

◆ delPseudoFreeDataForCheck()

◆ delPseudoPathCreatePseudoAncestorTuple()

◆ delPseudoPath()

◆ graph_knot_delPseudo()

◆ graph_knot_delPseudoCheckIfPossible()

◆ graph_edge_delPseudo()

◆ graph_edge_delPseudoPath()