Detailed Description

extended reductions for Steiner tree problems

Author: Daniel Rehfeldt

This file implements interface methods for extended reduction techniques for several Steiner problems.

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

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "graph.h"
#include "solstp.h"
#include "extreduce.h"

Go to the source code of this file.

Data Structures
struct	general_star

struct	extension_pseudo_deletion

Macros
#define	EXT_PSEUDO_DEGREE_MIN 3

#define	EXT_PSEUDO_DEGREE_MAX 5

#define	STP_GENSTAR_MAXDEG 6

#define	STP_GENSTAR_MAXENDDEG 4

#define	GENSTAR_NODE_OTHER 0

#define	GENSTAR_NODE_TAIL 1

#define	GENSTAR_NODE_HEAD 2

#define	GENSTAR_NODE_COMBI 3

#define	EXT_PROFIT_MINRATIO 0.05

Typedefs
typedef struct general_star	GENSTAR

typedef struct extension_pseudo_deletion	EXTPSEUDO

Enumerations
enum	EXTPSEUDO_MODE { delete_all = 0, delete_profits = 1, delete_nonprofits = 2 }

Functions
static SCIP_Bool	graphmarkIsClean (const REDCOST redcostdata, const GRAPH graph)

static SCIP_RETCODE	replaceEdgeByPath (SCIP scip, int edge, const GENSTAR genstar, GRAPH graph, REDCOST redcostdata, DISTDATA distdata, EXTPERMA extpermanent)

static void	removeEdge (SCIP scip, int edge, GRAPH graph, DISTDATA distdata, EXTPERMA extpermanent)

static SCIP_RETCODE	extInit (SCIP scip, SCIP_Bool useSd, GRAPH graph, STP_Bool edgedeletable, DISTDATA distdata, EXTPERMA *extpermanent)

static void	extFree (SCIP scip, GRAPH graph, DISTDATA distdata, EXTPERMA extpermanent)

static void	generalStarCheckInit (SCIP scip, const GRAPH g, GENSTAR *genstar)

static void	generalStarCheckExit (SCIP scip, const GRAPH g, GENSTAR *genstar)

static void	generalStarCheckGetNextStar (const GRAPH g, GENSTAR genstar, EXTCOMP extcomp, SCIP_Bool allVisited)

static SCIP_RETCODE	generalStarCheck (SCIP scip, const GRAPH graph, const REDCOST redcostdata, GENSTAR genstar, EXTPERMA extpermanent, SCIP_Bool isDeletable)

static void	generalStarSetUp (SCIP scip, const GRAPH graph, int edge, GENSTAR genstar, SCIP_Bool isPromising, DISTDATA *distdata)

static SCIP_RETCODE	generalStarInit (SCIP scip, const GRAPH graph, GENSTAR *genstar)

static void	generalStarExit (SCIP scip, const GRAPH graph, GENSTAR *genstar)

static SCIP_RETCODE	generalStarDeleteEdges (SCIP scip, REDCOST redcostdata, EXTPERMA extpermanent, GRAPH graph, DISTDATA distdata, int nelims)

static SCIP_RETCODE	pseudodeleteInit (SCIP scip, const int result, const GRAPH g, SCIP_Real offsetp, EXTPSEUDO *extpseudo)

static void	pseudodeleteExit (SCIP scip, EXTPSEUDO extpseudo, int *nelimsp)

static SCIP_RETCODE	pseudodeleteInitStar (SCIP scip, const GRAPH g, int node, STAR stardata, int compedges, int *extleaves)

static void	pseudodeleteFreeStar (SCIP scip, int compedges, int *extleaves)

static void	pseudodeleteGetNextStar (const GRAPH g, STAR stardata, EXTCOMP *extcomp)

static SCIP_Bool	pseudodeleteAllStarsChecked (const STAR *stardata)

static SCIP_Bool	pseudodeleteBiasedIsPromising (SCIP scip, const EXTPERMA extperma, const GRAPH *g)

static SCIP_Bool	pseudodeleteNodeIsPromising (const GRAPH g, const EXTPERMA extperma, const EXTPSEUDO *extpseudo, int node)

static SCIP_RETCODE	pseudodeleteDeleteComputeCutoffs (SCIP scip, SCIP_Bool checkpromising, SCIP_Bool abortDeg3, DISTDATA distdata, int node, GRAPH graph, EXTPSEUDO extpseudo)

static SCIP_RETCODE	pseudodeleteDeleteNode (SCIP scip, int node, REDCOST redcostdata, DISTDATA distdata, GRAPH graph, EXTPSEUDO extpseudo, SCIP_Bool success)

static SCIP_RETCODE	pseudodeleteDeleteMarkedNodes (SCIP scip, const SCIP_Bool pseudoDelNodes, REDCOST redcostdata, DISTDATA distdata, GRAPH graph, EXTPSEUDO extpseudo)

static SCIP_RETCODE	pseudodeleteExecute (SCIP scip, const int result, const SCIP_Bool pseudoDelNodes, EXTPERMA extperma, EXTPSEUDO extpseudo, GRAPH graph)

SCIP_RETCODE	extreduce_init (SCIP scip, SCIP_Bool useSd, enum EXTRED_MODE mode, GRAPH graph, REDCOST redcostdata, EXTPERMA *extpermanent)

void	extreduce_exit (SCIP scip, GRAPH graph, EXTPERMA **extpermanent)

SCIP_RETCODE	extreduce_deleteArcs (SCIP scip, REDCOST redcostdata, const int result, GRAPH graph, STP_Bool edgedeletable, int nelims)

SCIP_RETCODE	extreduce_deleteEdges (SCIP scip, EXTPERMA extperma, GRAPH graph, int nelims)

SCIP_RETCODE	extreduce_pseudoDeleteNodes (SCIP scip, const SCIP_Bool pseudoDelNodes, EXTPERMA extperma, GRAPH graph, SCIP_Real offsetp, int nelims)

SCIP_RETCODE	extreduce_deleteGeneralStars (SCIP scip, REDCOST redcostdata, const int result, GRAPH graph, STP_Bool edgedeletable, int nelims)

SCIP_RETCODE	extreduce_checkArc (SCIP scip, const GRAPH graph, REDCOST redcostdata, int edge, EXTPERMA extpermanent, SCIP_Bool *edgeIsDeletable)

SCIP_RETCODE	extreduce_checkEdge (SCIP scip, const GRAPH graph, const REDCOST redcostdata, int edge, EXTPERMA extpermanent, SCIP_Bool *edgeIsDeletable)

SCIP_RETCODE	extreduce_checkNode (SCIP scip, const GRAPH graph, const REDCOST redcostdata, int node, STAR stardata, EXTPERMA extpermanent, SCIP_Bool isPseudoDeletable)

void	extreduce_edgeRemove (SCIP scip, int edge, GRAPH graph, DISTDATA distdata, EXTPERMA extpermanent)

SCIP_Bool	extreduce_edgeIsValid (const GRAPH graph, const REDCOST redcostdata, int e)

void	extreduce_treeRecompCosts (SCIP scip, const GRAPH graph, EXTDATA *extdata)

int	extreduce_getMaxStackSize (void)

int	extreduce_getMaxStackNcomponents (const GRAPH *graph)

int	extreduce_getMaxTreeDepth (const GRAPH graph, const EXTPERMA extpermanent)

Macro Definition Documentation

◆ EXT_PSEUDO_DEGREE_MIN

#define EXT_PSEUDO_DEGREE_MIN 3

Definition at line 35 of file extreduce_base.c.

Referenced by pseudodeleteExecute().

◆ EXT_PSEUDO_DEGREE_MAX

#define EXT_PSEUDO_DEGREE_MAX 5

Definition at line 36 of file extreduce_base.c.

Referenced by pseudodeleteExecute(), and pseudodeleteNodeIsPromising().

◆ STP_GENSTAR_MAXDEG

#define STP_GENSTAR_MAXDEG 6

Definition at line 38 of file extreduce_base.c.

Referenced by generalStarCheck(), generalStarInit(), and generalStarSetUp().

◆ STP_GENSTAR_MAXENDDEG

#define STP_GENSTAR_MAXENDDEG 4

Definition at line 39 of file extreduce_base.c.

Referenced by generalStarInit().

◆ GENSTAR_NODE_OTHER

#define GENSTAR_NODE_OTHER 0

Definition at line 41 of file extreduce_base.c.

Referenced by generalStarCheckExit(), generalStarCheckGetNextStar(), and generalStarCheckInit().

◆ GENSTAR_NODE_TAIL

#define GENSTAR_NODE_TAIL 1

Definition at line 42 of file extreduce_base.c.

Referenced by generalStarCheckGetNextStar(), and generalStarCheckInit().

◆ GENSTAR_NODE_HEAD

#define GENSTAR_NODE_HEAD 2

Definition at line 43 of file extreduce_base.c.

Referenced by generalStarCheckGetNextStar(), and generalStarCheckInit().

◆ GENSTAR_NODE_COMBI

#define GENSTAR_NODE_COMBI 3

Definition at line 44 of file extreduce_base.c.

Referenced by generalStarCheckGetNextStar(), and generalStarCheckInit().

◆ EXT_PROFIT_MINRATIO

#define EXT_PROFIT_MINRATIO 0.05

Definition at line 46 of file extreduce_base.c.

Referenced by pseudodeleteBiasedIsPromising().

Typedef Documentation

◆ GENSTAR

typedef struct general_star GENSTAR

generalized star

◆ EXTPSEUDO

typedef struct extension_pseudo_deletion EXTPSEUDO

helper

Enumeration Type Documentation

◆ EXTPSEUDO_MODE

enum EXTPSEUDO_MODE

Enumerator
delete_all
delete_profits
delete_nonprofits

Definition at line 49 of file extreduce_base.c.

Function Documentation

◆ graphmarkIsClean()

static SCIP_Bool graphmarkIsClean	(	const REDCOST *	redcostdata,
		const GRAPH *	graph
	)

static

all good with the graph->mark array?

Parameters

redcostdata	reduced cost data
graph	graph data structure

Definition at line 89 of file extreduce_base.c.

References FALSE, GRAPH::grad, graph_get_nNodes(), graph_knot_isInRange(), graph_knot_printInfo(), Is_term, GRAPH::mark, nnodes, redcosts_getRootTop(), GRAPH::term, and TRUE.

Referenced by extreduce_deleteArcs(), extreduce_deleteEdges(), extreduce_deleteGeneralStars(), and pseudodeleteExecute().

◆ replaceEdgeByPath()

static SCIP_RETCODE replaceEdgeByPath	(	SCIP *	scip,
		int	edge,
		const GENSTAR *	genstar,
		GRAPH *	graph,
		REDCOST *	redcostdata,
		DISTDATA *	distdata,
		EXTPERMA *	extpermanent
	)

inlinestatic

replaces edge by a path

Parameters

scip	SCIP
edge	edge to replace
genstar	star
graph	graph data structure (in/out)
redcostdata	reduced cost data structures
distdata	distance data (in/out)
extpermanent	(in/out)

Definition at line 118 of file extreduce_base.c.

References GRAPH::dcsr_storage, extreduce_distCloseNodesAreValid(), extreduce_distDataDeleteEdge(), FALSE, flipedge, GRAPH::grad, graph_dcsr_deleteEdgeBi(), graph_edge_delPseudoPath(), graph_edge_printInfo(), graph_pc_isPcMw(), graph_valid_dcsr(), distance_data::hasPathReplacement, GRAPH::head, dynamic_csr_storage::id2csredge, Is_term, GRAPH::mark, redcosts_getEdgeCostsTop(), reduce_impliedNodesIsValid(), reduce_impliedNodesRepair(), reduce_sdRepair(), SCIP_CALL, SCIP_CALL_ABORT, SCIP_OKAY, SCIPdebugMessage, distance_data::sdistdata, GRAPH::source, STP_Vectype, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by generalStarDeleteEdges().

◆ removeEdge()

static void removeEdge	(	SCIP *	scip,
		int	edge,
		GRAPH *	graph,
		DISTDATA *	distdata,
		EXTPERMA *	extpermanent
	)

inlinestatic

deletes an edge and makes corresponding adaptations

Parameters

scip	SCIP
edge	edge to delete
graph	graph data structure (in/out)
distdata	distance data (in/out)
extpermanent	(in/out)

Definition at line 205 of file extreduce_base.c.

References extreduce_distCloseNodesAreValid(), extreduce_distDataDeleteEdge(), FALSE, GRAPH::grad, graph_edge_delFull(), graph_edge_printInfo(), graph_pc_isPcMw(), distance_data::hasPathReplacement, GRAPH::head, Is_term, GRAPH::mark, reduce_impliedNodesIsValid(), reduce_impliedNodesRepair(), reduce_sdRepair(), SCIP_CALL_ABORT, SCIPdebugMessage, distance_data::sdistdata, GRAPH::source, STP_Vectype, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by extreduce_deleteArcs(), extreduce_deleteEdges(), extreduce_edgeRemove(), and generalStarDeleteEdges().

◆ extInit()

static SCIP_RETCODE extInit	(	SCIP *	scip,
		SCIP_Bool	useSd,
		GRAPH *	graph,
		STP_Bool *	edgedeletable,
		DISTDATA **	distdata,
		EXTPERMA **	extpermanent
	)

inlinestatic

initialize

Parameters

scip	SCIP data structure
useSd	use special distance?
graph	graph data structure
edgedeletable	edge array to mark which (directed) edge can be removed
distdata	distance data (out)
extpermanent	permanent extension data (out)

Definition at line 275 of file extreduce_base.c.

References GRAPH::extended, extred_full, extreduce_distDataInit(), extreduce_extPermaInit(), FALSE, graph_init_dcsr(), graph_mark(), graph_pc_isPcMw(), SCIP_CALL, SCIP_OKAY, and STP_EXT_CLOSENODES_MAXN.

Referenced by extreduce_deleteArcs(), and extreduce_deleteGeneralStars().

◆ extFree()

static void extFree	(	SCIP *	scip,
		GRAPH *	graph,
		DISTDATA **	distdata,
		EXTPERMA **	extpermanent
	)

inlinestatic

free

Parameters

scip	SCIP data structure
graph	graph data structure
distdata	distance data (in/out)
extpermanent	permanent extension data (in/out)

Definition at line 298 of file extreduce_base.c.

References extreduce_distDataFree(), extreduce_extPermaFree(), and graph_free_dcsr().

Referenced by extreduce_deleteArcs(), and extreduce_deleteGeneralStars().

◆ generalStarCheckInit()

static void generalStarCheckInit	(	SCIP *	scip,
		const GRAPH *	g,
		GENSTAR *	genstar
	)

inlinestatic

initializes for check

Parameters

scip	SCIP data structure
g	graph data structure
genstar	general star

Definition at line 313 of file extreduce_base.c.

References GENSTAR_NODE_COMBI, GENSTAR_NODE_HEAD, GENSTAR_NODE_OTHER, GENSTAR_NODE_TAIL, graph_edge_isInRange(), graph_edge_printInfo(), GRAPH::head, reduce_starResetWithEdges(), SCIPdebugMessage, general_star::star, StpVecClear, StpVecGetSize, and StpVecPushBack.

Referenced by generalStarCheck().

◆ generalStarCheckExit()

static void generalStarCheckExit	(	SCIP *	scip,
		const GRAPH *	g,
		GENSTAR *	genstar
	)

inlinestatic

exits from check

Parameters

scip	SCIP data structure
g	graph data structure
genstar	general star

Definition at line 375 of file extreduce_base.c.

References GENSTAR_NODE_OTHER, graph_edge_isInRange(), GRAPH::head, and StpVecGetSize.

Referenced by generalStarCheck().

◆ generalStarCheckGetNextStar()

static void generalStarCheckGetNextStar	(	const GRAPH *	g,
		GENSTAR *	genstar,
		EXTCOMP *	extcomp,
		SCIP_Bool *	allVisited
	)

inlinestatic

gets next star

Parameters

g	graph data structure
genstar	general star
extcomp	to be filled
allVisited	all stars visited?

Definition at line 399 of file extreduce_base.c.

References initial_extension_component::compedges, initial_extension_component::comproot, initial_extension_component::extleaves, FALSE, flipedge, GENSTAR_NODE_COMBI, GENSTAR_NODE_HEAD, GENSTAR_NODE_OTHER, GENSTAR_NODE_TAIL, graph_edge_isInRange(), graph_edge_printInfo(), GRAPH::head, initial_extension_component::ncompedges, initial_extension_component::nextleaves, reduce_starAllAreChecked(), reduce_starGetNext(), SCIP_Bool, SCIPdebugMessage, general_star::star, GRAPH::tail, and TRUE.

Referenced by generalStarCheck().

◆ generalStarCheck()

static SCIP_RETCODE generalStarCheck	(	SCIP *	scip,
		const GRAPH *	graph,
		const REDCOST *	redcostdata,
		GENSTAR *	genstar,
		EXTPERMA *	extpermanent,
		SCIP_Bool *	isDeletable
	)

inlinestatic

check for elimination

Parameters

scip	SCIP data structure
graph	graph data structure
redcostdata	reduced cost data structures
genstar	general star
extpermanent	data
isDeletable	deletable?

Definition at line 544 of file extreduce_base.c.

References initial_extension_component::compedges, CONNECT, extreduce_checkComponent(), FALSE, flipedge, generalStarCheckExit(), generalStarCheckGetNextStar(), generalStarCheckInit(), GRAPH::grad, graph_edge_isInRange(), graph_edge_printInfo(), GRAPH::head, extension_data_permanent::redcostEqualAllow, reduce_starAllAreChecked(), extension_data_permanent::result, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, extension_data_permanent::solIsValid, general_star::star, STP_GENSTAR_MAXDEG, GRAPH::tail, extension_data_permanent::tree_maxdepth, and TRUE.

Referenced by generalStarDeleteEdges().

◆ generalStarSetUp()

static void generalStarSetUp	(	SCIP *	scip,
		const GRAPH *	graph,
		int	edge,
		GENSTAR *	genstar,
		SCIP_Bool *	isPromising,
		DISTDATA *	distdata
	)

inlinestatic

sets up the general star (especially edges_tail and edges_head) and checks whether deletion attempt makes sense

Parameters

scip	SCIP data structure
graph	graph data structure
edge	inducing edge
genstar	general star
isPromising	promising?
distdata	distance data

Definition at line 624 of file extreduce_base.c.

References GRAPH::cost, EAT_LAST, extreduce_distDataGetSdDoubleForbiddenSingle(), FALSE, GE, GRAPH::grad, graph_pseudoAncestors_hashEdge(), graph_pseudoAncestors_hashEdgeDirty(), graph_pseudoAncestors_unhashEdge(), graph_pseudoAncestorsGetHashArraySize(), GT, GRAPH::head, Is_term, GRAPH::oeat, GRAPH::outbeg, GRAPH::pseudoancestors, reduce_sdgraphEdgeIsInMst(), reduce_sdgraphGetMaxCost(), reduce_sdgraphGetMstHalfMark(), SCIP_Bool, SCIP_CALL_ABORT, SCIP_Real, SCIPallocCleanBufferArray, SCIPdebugMessage, SCIPfreeCleanBufferArray, special_distance_storage::sdgraph, distance_data::sdistdata, STP_GENSTAR_MAXDEG, STP_Vectype, StpVecClear, StpVecGetSize, StpVecPushBack, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by generalStarDeleteEdges().

◆ generalStarInit()

static SCIP_RETCODE generalStarInit	(	SCIP *	scip,
		const GRAPH *	graph,
		GENSTAR *	genstar
	)

static

initializes

Parameters

scip	SCIP data structure
graph	graph data structure
genstar	general star

Definition at line 768 of file extreduce_base.c.

References GRAPH::knots, reduce_starInit(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocCleanBufferArray, general_star::star, STP_GENSTAR_MAXDEG, STP_GENSTAR_MAXENDDEG, and StpVecReserve.

Referenced by generalStarDeleteEdges().

◆ generalStarExit()

static void generalStarExit	(	SCIP *	scip,
		const GRAPH *	graph,
		GENSTAR *	genstar
	)

static

exits

Parameters

scip	SCIP data structure
graph	graph data structure
genstar	general star

Definition at line 788 of file extreduce_base.c.

References GRAPH::knots, reduce_starFree(), SCIPfreeBufferArray, SCIPfreeCleanBufferArray, general_star::star, and StpVecFree.

Referenced by generalStarDeleteEdges().

◆ generalStarDeleteEdges()

static SCIP_RETCODE generalStarDeleteEdges	(	SCIP *	scip,
		REDCOST *	redcostdata,
		EXTPERMA *	extpermanent,
		GRAPH *	graph,
		DISTDATA *	distdata,
		int *	nelims
	)

static

deletes center edges of general stars

Parameters

scip	SCIP data structure
redcostdata	reduced cost data structures
extpermanent	extension data
graph	graph data structure
distdata	distance data
nelims	number of eliminations (out)

Definition at line 810 of file extreduce_base.c.

References CONNECT, GRAPH::edges, FALSE, flipedge, generalStarCheck(), generalStarExit(), generalStarInit(), generalStarSetUp(), graph_edge_isDeleted(), NULL, removeEdge(), replaceEdgeByPath(), extension_data_permanent::result, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, and extension_data_permanent::solIsValid.

Referenced by extreduce_deleteEdges(), and extreduce_deleteGeneralStars().

◆ pseudodeleteInit()

static SCIP_RETCODE pseudodeleteInit	(	SCIP *	scip,
		const int *	result,
		const GRAPH *	g,
		SCIP_Real *	offsetp,
		EXTPSEUDO *	extpseudo
	)

inlinestatic

initializes

Parameters

scip	SCIP data structure
result	solution array or NULL
g	graph data structure
offsetp	pointer to store offset
extpseudo	to initialize

Definition at line 875 of file extreduce_base.c.

Referenced by extreduce_pseudoDeleteNodes().

◆ pseudodeleteExit()

static void pseudodeleteExit	(	SCIP *	scip,
		EXTPSEUDO *	extpseudo,
		int *	nelimsp
	)

inlinestatic

frees

Parameters

scip	SCIP data structure
extpseudo	to initialize
nelimsp	pointer: number of eliminations (OUT)

Definition at line 928 of file extreduce_base.c.

References extension_pseudo_deletion::cutoffs, extension_pseudo_deletion::nelims_extended, extension_pseudo_deletion::nelims_simple, extension_pseudo_deletion::nodeInSol, extension_pseudo_deletion::nodestouches, SCIPfreeBufferArray, and SCIPfreeBufferArrayNull.

Referenced by extreduce_pseudoDeleteNodes().

◆ pseudodeleteInitStar()

static SCIP_RETCODE pseudodeleteInitStar	(	SCIP *	scip,
		const GRAPH *	g,
		int	node,
		STAR *	stardata,
		int **	compedges,
		int **	extleaves
	)

inlinestatic

initializes new star

Parameters

scip	SCIP data structure
g	graph data structure
node	node
stardata	star
compedges	to be allocated
extleaves	to be allocated

Definition at line 949 of file extreduce_base.c.

References GRAPH::grad, reduce_starReset(), SCIP_CALL, SCIP_OKAY, and SCIPallocBufferArray.

Referenced by extreduce_checkNode().

◆ pseudodeleteFreeStar()

static void pseudodeleteFreeStar	(	SCIP *	scip,
		int **	compedges,
		int **	extleaves
	)

inlinestatic

frees new star

Parameters

scip	SCIP data structure
compedges	to be freed
extleaves	to be freed

Definition at line 971 of file extreduce_base.c.

References SCIPfreeBufferArray.

Referenced by extreduce_checkNode().

◆ pseudodeleteGetNextStar()

static void pseudodeleteGetNextStar	(	const GRAPH *	g,
		STAR *	stardata,
		EXTCOMP *	extcomp
	)

inlinestatic

gets next star

Parameters

g	graph data structure
stardata	star
extcomp	to be filled

Definition at line 984 of file extreduce_base.c.

References initial_extension_component::compedges, initial_extension_component::comproot, initial_extension_component::extleaves, flipedge, GRAPH::head, initial_extension_component::ncompedges, initial_extension_component::nextleaves, and reduce_starGetNext().

Referenced by extreduce_checkNode().

◆ pseudodeleteAllStarsChecked()

static SCIP_Bool pseudodeleteAllStarsChecked ( const STAR * stardata )

inlinestatic

frees new star

Parameters

stardata star

Definition at line 1014 of file extreduce_base.c.

References reduce_starAllAreChecked().

Referenced by extreduce_checkNode().

◆ pseudodeleteBiasedIsPromising()

static SCIP_Bool pseudodeleteBiasedIsPromising	(	SCIP *	scip,
		const EXTPERMA *	extperma,
		const GRAPH *	g
	)

inlinestatic

is biased SD extension promising?

Parameters

scip	SCIP data structure
extperma	extension data
g	graph data structure

Definition at line 1025 of file extreduce_base.c.

References GRAPH::cost, EXT_PROFIT_MINRATIO, FALSE, graph_get_nNodes(), graph_pc_isPc(), GT, Is_term, nnodes, special_distance_implied_profit::nodes_bias, nterms, reduce_sdprofitFree(), reduce_sdprofitInit1stOnly(), SCIP_CALL_ABORT, SCIPdebugMessage, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by extreduce_pseudoDeleteNodes().

◆ pseudodeleteNodeIsPromising()

static SCIP_Bool pseudodeleteNodeIsPromising	(	const GRAPH *	g,
		const EXTPERMA *	extperma,
		const EXTPSEUDO *	extpseudo,
		int	node
	)

inlinestatic

is node a good candidate for pseudo deletion?

Parameters

g	graph data structure
extperma	extension data
extpseudo	pseudo
node	node

Definition at line 1074 of file extreduce_base.c.

References delete_all, delete_nonprofits, delete_profits, extension_pseudo_deletion::deletionMode, extension_data_permanent::distdata_biased, EXT_PSEUDO_DEGREE_MAX, GRAPH::extended, FALSE, GRAPH::grad, graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_realDegree(), graph_pc_termIsNonLeafTerm(), GT, Is_term, GRAPH::mark, reduce_sdprofitGetProfit(), SCIP_Bool, distance_data::sdistdata, special_distance_storage::sdprofit, GRAPH::term, and TRUE.

Referenced by pseudodeleteExecute().

◆ pseudodeleteDeleteComputeCutoffs()

static SCIP_RETCODE pseudodeleteDeleteComputeCutoffs	(	SCIP *	scip,
		SCIP_Bool	checkpromising,
		SCIP_Bool	abortDeg3,
		DISTDATA *	distdata,
		int	node,
		GRAPH *	graph,
		EXTPSEUDO *	extpseudo
	)

inlinestatic

computes cutoffs for pseudo-deletion of given node

Parameters

scip	SCIP data structure
checkpromising	check whether promising?
abortDeg3	abort for degree 3?
distdata	distance data
node	to be deleted
graph	graph data structure
extpseudo	data

Definition at line 1139 of file extreduce_base.c.

References GRAPH::cost, extension_pseudo_deletion::cutoffIsComputed, extension_pseudo_deletion::cutoffIsPromising, extension_pseudo_deletion::cutoffs, EAT_LAST, eps, EQ, extreduce_distDataGetSdDouble(), extreduce_distDataGetSdDoubleForbiddenLast(), FALSE, FARAWAY, GRAPH::grad, graph_knot_delPseudoCheckIfPossible(), graph_pc_isPc(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsNonLeafTerm(), GRAPH::head, LT, extension_pseudo_deletion::node, extension_pseudo_deletion::nodestouches, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPepsilon(), SCIPisEQ(), SCIPisGT(), SCIPisLE(), STP_DELPSEUDO_MAXGRAD, STP_DELPSEUDO_MAXNEDGES, and TRUE.

Referenced by pseudodeleteDeleteMarkedNodes(), pseudodeleteDeleteNode(), and pseudodeleteExecute().

◆ pseudodeleteDeleteNode()

static SCIP_RETCODE pseudodeleteDeleteNode	(	SCIP *	scip,
		int	node,
		REDCOST *	redcostdata,
		DISTDATA *	distdata,
		GRAPH *	graph,
		EXTPSEUDO *	extpseudo,
		SCIP_Bool *	success
	)

inlinestatic

pseudo-deletes single node

Parameters

scip	SCIP data structure
node	to be deleted
redcostdata	reduced cost data
distdata	distance data
graph	graph data structure
extpseudo	data
success	success?

Definition at line 1232 of file extreduce_base.c.

References GRAPH::cost, extension_pseudo_deletion::cutoffIsComputed, extension_pseudo_deletion::cutoffs, EAT_LAST, FALSE, GE, GRAPH::grad, graph_knot_delPseudo(), graph_pc_isPc(), graph_pc_knotIsNonLeafTerm(), GRAPH::head, GRAPH::mark, extension_pseudo_deletion::node, extension_pseudo_deletion::nodeInSol, extension_pseudo_deletion::nodestouches, NULL, GRAPH::oeat, extension_pseudo_deletion::offsetp, GRAPH::outbeg, GRAPH::prize, pseudodeleteDeleteComputeCutoffs(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, TRUE, and extension_pseudo_deletion::useSolForEq.

Referenced by pseudodeleteDeleteMarkedNodes(), and pseudodeleteExecute().

◆ pseudodeleteDeleteMarkedNodes()

static SCIP_RETCODE pseudodeleteDeleteMarkedNodes	(	SCIP *	scip,
		const SCIP_Bool *	pseudoDelNodes,
		REDCOST *	redcostdata,
		DISTDATA *	distdata,
		GRAPH *	graph,
		EXTPSEUDO *	extpseudo
	)

static

apply pseudo eliminations for marked nodes NOTE: bad design, but useful to reuse the SDs...

Parameters

scip	SCIP data structure
pseudoDelNodes	node with pseudo deletable nodes
redcostdata	reduced cost data
distdata	distance data
graph	graph data structure
extpseudo	data

Definition at line 1304 of file extreduce_base.c.

References FALSE, GRAPH::grad, graph_get_nNodes(), Is_term, extension_pseudo_deletion::nelims_simple, nnodes, pseudodeleteDeleteComputeCutoffs(), pseudodeleteDeleteNode(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, STP_DELPSEUDO_MAXGRAD, and GRAPH::term.

Referenced by pseudodeleteExecute().

◆ pseudodeleteExecute()

static SCIP_RETCODE pseudodeleteExecute	(	SCIP *	scip,
		const int *	result,
		const SCIP_Bool *	pseudoDelNodes,
		EXTPERMA *	extperma,
		EXTPSEUDO *	extpseudo,
		GRAPH *	graph
	)

static

Extended reduction test for pseudo-eliminating nodes. Applies pseudo-elimination if pseudoDelNodes != NULL, or just marks them otherwise

Parameters

scip	SCIP data structure
result	solution array or NULL
pseudoDelNodes	nodes to pseudo-eliminate already
extperma	extension data
extpseudo	pseudo-deletion data
graph	graph data structure (in/out)

Definition at line 1343 of file extreduce_base.c.

References extension_pseudo_deletion::cutoffIsPromising, extension_data_permanent::distdata_biased, extension_data_permanent::distdata_default, EXT_PSEUDO_DEGREE_MAX, EXT_PSEUDO_DEGREE_MIN, extreduce_checkNode(), extreduce_distDataRecomputeDirtyPaths(), extreduce_mstbiasedCheck3NodeSimple(), FALSE, GRAPH::grad, graph_get_nNodes(), graph_isMarked(), graph_knot_del(), graphmarkIsClean(), Is_term, GRAPH::mark, extension_pseudo_deletion::nelims_extended, extension_pseudo_deletion::nelims_simple, nnodes, extension_pseudo_deletion::nodeInSol, pseudodeleteDeleteComputeCutoffs(), pseudodeleteDeleteMarkedNodes(), pseudodeleteDeleteNode(), pseudodeleteNodeIsPromising(), extension_data_permanent::redcostdata, extension_data_permanent::redcostEqualAllow, reduce_nodesDeg1(), reduce_starFree(), reduce_starInit(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, GRAPH::term, TRUE, extension_data_permanent::useSdBias, and extension_pseudo_deletion::useSolForEq.

Referenced by extreduce_pseudoDeleteNodes().

◆ extreduce_init()

SCIP_RETCODE extreduce_init	(	SCIP *	scip,
		SCIP_Bool	useSd,
		enum EXTRED_MODE	mode,
		GRAPH *	graph,
		REDCOST *	redcostdata,
		EXTPERMA **	extpermanent
	)

initializes

Parameters

scip	SCIP data structure
useSd	use special distance?
mode	mode
graph	graph data structure
redcostdata	reduced costs data
extpermanent	permanent extension data (out)

Definition at line 1425 of file extreduce_base.c.

References extension_data_permanent::distdata_default, GRAPH::extended, extreduce_distDataInit(), extreduce_extPermaInit(), FALSE, graph_init_dcsr(), graph_mark(), graph_pc_isPcMw(), NULL, extension_data_permanent::redcostdata, SCIP_CALL, SCIP_OKAY, and STP_EXT_CLOSENODES_MAXN.

Referenced by reduce_da().

◆ extreduce_exit()

void extreduce_exit	(	SCIP *	scip,
		GRAPH *	graph,
		EXTPERMA **	extpermanent
	)

frees

Parameters

scip	SCIP data structure
graph	graph data structure
extpermanent	permanent extension data

Definition at line 1452 of file extreduce_base.c.

References extension_data_permanent::distdata_biased, extension_data_permanent::distdata_default, extreduce_distDataFree(), extreduce_extPermaFree(), and graph_free_dcsr().

Referenced by reduce_da(), and reduce_termsepaDa().

◆ extreduce_deleteArcs()

SCIP_RETCODE extreduce_deleteArcs	(	SCIP *	scip,
		REDCOST *	redcostdata,
		const int *	result,
		GRAPH *	graph,
		STP_Bool *	edgedeletable,
		int *	nelims
	)

Extended reduction test for arcs. This method will also set edgedeletable[a] to TRUE if arc 'a' can be deleted, but its anti-parallel arc not.

Parameters

scip	SCIP data structure
redcostdata	reduced cost data
result	solution array or NULL
graph	graph data structure
edgedeletable	edge array to mark which (directed) edge can be removed
nelims	number of eliminations

Definition at line 1476 of file extreduce_base.c.

References CONNECT, GRAPH::cost, extension_data_permanent::distdata_default, extFree(), extInit(), extreduce_checkArc(), extreduce_edgeIsValid(), FALSE, flipedge, graph_get_nEdges(), graph_pc_isPc(), graphmarkIsClean(), NULL, extension_data_permanent::redcostEqualAllow, redcosts_getCutoffTop(), reduce_sdRepairSetUp(), removeEdge(), extension_data_permanent::result, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPisEQ(), SCIPisZero(), distance_data::sdistdata, and TRUE.

Referenced by fixVarsExtendedRed().

◆ extreduce_deleteEdges()

SCIP_RETCODE extreduce_deleteEdges	(	SCIP *	scip,
		EXTPERMA *	extperma,
		GRAPH *	graph,
		int *	nelims
	)

extended reduction test for edges

Parameters

scip	SCIP data structure
extperma	extension data
graph	graph data structure (in/out)
nelims	number of eliminations (out)

Definition at line 1569 of file extreduce_base.c.

References CONNECT, GRAPH::cost, extension_data_permanent::distdata_default, extred_fast, extred_full, extreduce_checkEdge(), extreduce_edgeIsValid(), FALSE, flipedge, generalStarDeleteEdges(), graph_get_nEdges(), graph_isMarked(), graph_mark(), graph_pc_isMw(), graph_pc_isPc(), graph_typeIsSpgLike(), graphmarkIsClean(), GRAPH::knots, extension_data_permanent::mode, NULL, extension_data_permanent::redcostdata, extension_data_permanent::redcostEqualAllow, redcosts_getCutoffTop(), redcosts_getRootTop(), reduce_pathreplaceExt(), reduce_sdgraphEdgeIsInMst(), reduce_sdRepairSetUp(), reduce_termsepaDaWithExperma(), removeEdge(), extension_data_permanent::result, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisEQ(), SCIPisZero(), special_distance_storage::sdgraph, distance_data::sdistdata, extension_data_permanent::solIsValid, solstp_isUnreduced(), solstp_isValid(), extension_data_permanent::tree_maxdepth, and TRUE.

Referenced by reduceWithEdgeExtReds().

◆ extreduce_pseudoDeleteNodes()

SCIP_RETCODE extreduce_pseudoDeleteNodes	(	SCIP *	scip,
		const SCIP_Bool *	pseudoDelNodes,
		EXTPERMA *	extperma,
		GRAPH *	graph,
		SCIP_Real *	offsetp,
		int *	nelims
	)

extended reduction test for pseudo-eliminating nodes

Parameters

scip	SCIP data structure
pseudoDelNodes	nodes to pseudo-eliminate already
extperma	extension data
graph	graph data structure (in/out)
offsetp	pointer to store offset
nelims	number of eliminations (out)

Definition at line 1668 of file extreduce_base.c.

References delete_all, delete_nonprofits, delete_profits, extension_pseudo_deletion::deletionMode, extension_data_permanent::distdata_biased, extension_data_permanent::distdata_default, GRAPH::extended, extreduce_distDataInit(), extreduce_extPermaAddMLdistsbiased(), FALSE, graph_mark(), graph_pc_2orgcheck(), graph_pc_2trans(), graph_pc_isPc(), distance_data::hasPathReplacement, extension_pseudo_deletion::nelims_extended, NULL, pseudodeleteBiasedIsPromising(), pseudodeleteExecute(), pseudodeleteExit(), pseudodeleteInit(), extension_data_permanent::redcostdata, redcosts_getCutoffTop(), reduce_removeDeg0NonLeafTerms(), reduce_unconnected(), extension_data_permanent::result, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisZero(), extension_data_permanent::solIsValid, solstp_isValid(), STP_EXT_CLOSENODES_MAXN, extension_data_permanent::tree_maxdepth, TRUE, extension_data_permanent::useSdBias, and extension_pseudo_deletion::useSolForEq.

Referenced by extDeleteNodes(), fixVarsRedbased(), reduce_da(), and testPcNode4PseudoDeletedBySd1().

◆ extreduce_deleteGeneralStars()

SCIP_RETCODE extreduce_deleteGeneralStars	(	SCIP *	scip,
		REDCOST *	redcostdata,
		const int *	result,
		GRAPH *	graph,
		STP_Bool *	edgedeletable,
		int *	nelims
	)

deletes center edges of general stars

Parameters

scip	SCIP data structure
redcostdata	reduced cost data
result	solution array or NULL
graph	graph data structure (in/out)
edgedeletable	edge array to mark which (directed) edge can be removed (in/out)
nelims	number of eliminations (out)

Definition at line 1750 of file extreduce_base.c.

References extension_data_permanent::distdata_default, extFree(), extInit(), generalStarDeleteEdges(), graph_pc_isPc(), graphmarkIsClean(), GRAPH::knots, redcosts_getCutoffTop(), redcosts_getRootTop(), reduce_sdRepairSetUp(), extension_data_permanent::result, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPisZero(), and distance_data::sdistdata.

Referenced by testGeneralStarDeletedEdge1(), testGeneralStarDeletedEdge2(), and testGeneralStarDeletedEdge3().

◆ extreduce_checkArc()

SCIP_RETCODE extreduce_checkArc	(	SCIP *	scip,
		const GRAPH *	graph,
		REDCOST *	redcostdata,
		int	edge,
		EXTPERMA *	extpermanent,
		SCIP_Bool *	edgeIsDeletable
	)

check (directed) arc

Parameters

scip	SCIP data structure
graph	graph data structure
redcostdata	reduced cost data structures
edge	edge to be checked
extpermanent	extension data
edgeIsDeletable	is edge deletable?

Definition at line 1794 of file extreduce_base.c.

References initial_extension_component::compedges, shortest_path::dist, GRAPH::extended, extLeafIsExtendable(), extreduce_checkComponent(), extreduce_extPermaIsClean(), FALSE, flipedge, graph_isMarked(), graph_pc_isPcMw(), GRAPH::head, extension_data_permanent::isterm, GRAPH::mark, extension_data_permanent::redcostEqualAllow, redcosts_getCutoffTop(), redcosts_getEdgeCostsTop(), redcosts_getNodeToTermsPathsTop(), redcosts_getRootToNodeDistTop(), redcosts_getRootTop(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisEQ(), SCIPisGT(), GRAPH::tail, and TRUE.

Referenced by extCheckArc(), and extreduce_deleteArcs().

◆ extreduce_checkEdge()

SCIP_RETCODE extreduce_checkEdge	(	SCIP *	scip,
		const GRAPH *	graph,
		const REDCOST *	redcostdata,
		int	edge,
		EXTPERMA *	extpermanent,
		SCIP_Bool *	edgeIsDeletable
	)

check edge

Parameters

scip	SCIP data structure
graph	graph data structure
redcostdata	reduced cost data structures
edge	edge to be checked
extpermanent	extension data
edgeIsDeletable	is edge deletable?

Definition at line 1854 of file extreduce_base.c.

References initial_extension_component::compedges, GRAPH::extended, extLeafIsExtendable(), extreduce_checkComponent(), extreduce_extPermaIsClean(), FALSE, graph_isMarked(), graph_pc_isPcMw(), GRAPH::head, extension_data_permanent::isterm, SCIP_Bool, SCIP_CALL, SCIP_OKAY, GRAPH::tail, and TRUE.

Referenced by extCheckEdge(), and extreduce_deleteEdges().

◆ extreduce_checkNode()

SCIP_RETCODE extreduce_checkNode	(	SCIP *	scip,
		const GRAPH *	graph,
		const REDCOST *	redcostdata,
		int	node,
		STAR *	stardata,
		EXTPERMA *	extpermanent,
		SCIP_Bool *	isPseudoDeletable
	)

check node for possible

Parameters

scip	SCIP data structure
graph	graph data structure
redcostdata	reduced cost data structures
node	the node
stardata	star
extpermanent	extension data
isPseudoDeletable	is node pseudo-deletable?

Definition at line 1890 of file extreduce_base.c.

References initial_extension_component::compedges, extension_data_permanent::distdata_default, extreduce_checkComponent(), extreduce_spgCheck3ComponentSimple(), FALSE, GRAPH::grad, initial_extension_component::ncompedges, pseudodeleteAllStarsChecked(), pseudodeleteFreeStar(), pseudodeleteGetNextStar(), pseudodeleteInitStar(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, extension_data_permanent::tree_maxdepth, and TRUE.

Referenced by extCheckNode(), and pseudodeleteExecute().

◆ extreduce_edgeRemove()

void extreduce_edgeRemove	(	SCIP *	scip,
		int	edge,
		GRAPH *	graph,
		DISTDATA *	distdata,
		EXTPERMA *	extpermanent
	)

deletes an edge and makes corresponding adaptations

Parameters

scip	SCIP
edge	edge to delete
graph	graph data structure (in/out)
distdata	distance data (in/out)
extpermanent	(in/out) can be NULL

Definition at line 1946 of file extreduce_base.c.

References removeEdge().

Referenced by deleteEdge(), deletenodesDeg1(), extCheckArc(), termcompDeleteEdges(), and testDistCloseNodesPcAreValidAfterDeletion().

◆ extreduce_edgeIsValid()

SCIP_Bool extreduce_edgeIsValid	(	const GRAPH *	graph,
		const REDCOST *	redcostdata,
		int	e
	)

is the edge valid?

Parameters

graph	graph data structure
redcostdata	reduced cost data
e	edge to be checked

Definition at line 1959 of file extreduce_base.c.

References EAT_FREE, EQ, FALSE, flipedge, graph_edge_isInRange(), graph_pc_isPcMw(), graph_pc_knotIsDummyTerm(), GRAPH::head, GRAPH::mark, GRAPH::oeat, redcosts_getEdgeCostsTop(), GRAPH::tail, and TRUE.

Referenced by extreduce_deleteArcs(), and extreduce_deleteEdges().

◆ extreduce_treeRecompCosts()

void extreduce_treeRecompCosts	(	SCIP *	scip,
		const GRAPH *	graph,
		EXTDATA *	extdata
	)

recompute costs and reduced costs for current tree

Parameters

scip	SCIP
graph	graph data structure
extdata	extension data

Definition at line 1998 of file extreduce_base.c.

References GRAPH::cost, reduction_data::edgedeleted, EQ, extreduce_redcostTreeRecompute(), extreduce_treeIsFlawed(), graph_pc_isPc(), NULL, extension_data::pcdata, GRAPH::prize, extension_data::reddata, SCIP_Bool, SCIP_Real, SCIPisEQ(), extension_data::tree_cost, extension_data::tree_edges, extension_data::tree_innerNodes, pcmw_specific_data::tree_innerPrize, extension_data::tree_nDelUpArcs, extension_data::tree_nedges, and extension_data::tree_ninnerNodes.

Referenced by extTreeSyncWithStack().

◆ extreduce_getMaxStackSize()

int extreduce_getMaxStackSize ( void )

get maximum allowed stack size

Definition at line 2062 of file extreduce_base.c.

References STP_EXT_MAXSTACKSIZE.

Referenced by extreduce_checkComponent(), and extreduce_extdataCleanArraysDbg().

◆ extreduce_getMaxStackNcomponents()

int extreduce_getMaxStackNcomponents ( const GRAPH * graph )

get maximum allowed number of components

Parameters

graph graph data structure

Definition at line 2069 of file extreduce_base.c.

References STP_EXT_MAXNCOMPS.

Referenced by extreduce_checkComponent(), and extreduce_extdataCleanArraysDbg().

◆ extreduce_getMaxTreeDepth()

int extreduce_getMaxTreeDepth	(	const GRAPH *	graph,
		const EXTPERMA *	extpermanent
	)

get maximum allowed depth for extended tree in given graph

Parameters

graph	graph data structure
extpermanent	extension data

Definition at line 2080 of file extreduce_base.c.

References extred_fast, graph_get_nVET(), extension_data_permanent::mode, NULL, STP_EXT_DEPTH_MAXNEDGES, STP_EXT_DEPTH_MIDNEDGES, STP_EXT_MAXDFSDEPTH, STP_EXT_MIDDFSDEPTH, and STP_EXT_MINDFSDEPTH.

Referenced by extreduce_extPermaInit().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ EXT_PSEUDO_DEGREE_MIN

◆ EXT_PSEUDO_DEGREE_MAX

◆ STP_GENSTAR_MAXDEG

◆ STP_GENSTAR_MAXENDDEG

◆ GENSTAR_NODE_OTHER

◆ GENSTAR_NODE_TAIL

◆ GENSTAR_NODE_HEAD

◆ GENSTAR_NODE_COMBI

◆ EXT_PROFIT_MINRATIO

Typedef Documentation

◆ GENSTAR

◆ EXTPSEUDO

Enumeration Type Documentation

◆ EXTPSEUDO_MODE

Function Documentation

◆ graphmarkIsClean()

◆ replaceEdgeByPath()

◆ removeEdge()

◆ extInit()

◆ extFree()

◆ generalStarCheckInit()

◆ generalStarCheckExit()

◆ generalStarCheckGetNextStar()

◆ generalStarCheck()

◆ generalStarSetUp()

◆ generalStarInit()

◆ generalStarExit()

◆ generalStarDeleteEdges()

◆ pseudodeleteInit()

◆ pseudodeleteExit()

◆ pseudodeleteInitStar()

◆ pseudodeleteFreeStar()

◆ pseudodeleteGetNextStar()

◆ pseudodeleteAllStarsChecked()

◆ pseudodeleteBiasedIsPromising()

◆ pseudodeleteNodeIsPromising()

◆ pseudodeleteDeleteComputeCutoffs()

◆ pseudodeleteDeleteNode()

◆ pseudodeleteDeleteMarkedNodes()

◆ pseudodeleteExecute()

◆ extreduce_init()

◆ extreduce_exit()

◆ extreduce_deleteArcs()

◆ extreduce_deleteEdges()

◆ extreduce_pseudoDeleteNodes()

◆ extreduce_deleteGeneralStars()

◆ extreduce_checkArc()

◆ extreduce_checkEdge()

◆ extreduce_checkNode()

◆ extreduce_edgeRemove()

◆ extreduce_edgeIsValid()

◆ extreduce_treeRecompCosts()

◆ extreduce_getMaxStackSize()

◆ extreduce_getMaxStackNcomponents()

◆ extreduce_getMaxTreeDepth()