Detailed Description

several basic reductions for Steiner tree problems

Author: Daniel Rehfeldt

This file implements simple reduction techniques for several Steiner problems. Mosts tests are described in "A Generic Approach to Solving the Steiner Tree Problem and Variants" by Daniel Rehfeldt.

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

Definition in file reduce_simple.c.

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

Go to the source code of this file.

Functions
static SCIP_RETCODE	cutEdgePrune (SCIP scip, int start, int end, int cutedge, GRAPH g)

static SCIP_RETCODE	cutEdgeProbe (SCIP scip, const GRAPH g, int start, int end, SCIP_Bool RESTRICT nodes_visited, SCIP_Bool terminalFound)

void	reduce_nodesDeg1 (SCIP scip, GRAPH graph)

SCIP_RETCODE	reduce_simple (SCIP scip, GRAPH g, SCIP_Real fixed, int solnode, int nelims, int edgestate)

SCIP_RETCODE	reduce_simple_sap (SCIP scip, GRAPH g, SCIP_Real fixed, int count)

void	reduce_simple_dc (SCIP scip, GRAPH g)

SCIP_RETCODE	reduce_simple_hc (SCIP scip, GRAPH g, SCIP_Real fixed, int count)

SCIP_RETCODE	reduce_contract0Edges (SCIP scip, GRAPH g, int *solnode, SCIP_Bool savehistory)

SCIP_RETCODE	reduce_deleteMultiedges (SCIP scip, GRAPH g)

SCIP_RETCODE	reduce_fixedConflicts (SCIP scip, const int edgestate, GRAPH g, int countnew)

SCIP_RETCODE	reduce_rpt (SCIP scip, GRAPH g, SCIP_Real fixed, int count)

SCIP_RETCODE	reduce_cutEdgeTryPrune (SCIP scip, int cutedge, GRAPH g, SCIP_Bool *success)

void	reduce_identifyNonLeafTerms (SCIP scip, GRAPH g)

SCIP_RETCODE	reduce_unconnected (SCIP scip, GRAPH g)

SCIP_RETCODE	reduce_unconnectedForDirected (SCIP scip, GRAPH g)

SCIP_RETCODE	reduce_unconnectedInfeas (SCIP scip, SCIP_Bool beVerbose, GRAPH g, SCIP_Bool *infeas)

Function Documentation

◆ cutEdgePrune()

static SCIP_RETCODE cutEdgePrune	(	SCIP *	scip,
		int	start,
		int	end,
		int	cutedge,
		GRAPH *	g
	)

static

prune

Parameters

scip	SCIP data structure
start	the node to start from
end	note to ignore
cutedge	the edge
g	graph data structure

Definition at line 61 of file reduce_simple.c.

References graph_edge_del(), GRAPH::head, Is_term, GRAPH::oeat, GRAPH::outbeg, reduce_unconnected(), SCIP_CALL, SCIP_OKAY, GRAPH::term, and TRUE.

Referenced by reduce_cutEdgeTryPrune().

◆ cutEdgeProbe()

static SCIP_RETCODE cutEdgeProbe	(	SCIP *	scip,
		const GRAPH *	g,
		int	start,
		int	end,
		SCIP_Bool *RESTRICT	nodes_visited,
		SCIP_Bool *	terminalFound
	)

static

probe

Parameters

scip	SCIP data structure
g	graph data structure
start	the node to start from
end	note to ignore
nodes_visited	marks for each node whether visited or not
terminalFound	found?

Definition at line 99 of file reduce_simple.c.

References EAT_LAST, FALSE, graph_get_nNodes(), GRAPH::head, Is_term, nnodes, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBuffer, GRAPH::term, and TRUE.

Referenced by reduce_cutEdgeTryPrune().

◆ reduce_nodesDeg1()

void reduce_nodesDeg1	(	SCIP *	scip,
		GRAPH *	graph
	)

removes nodes of degree one and unmarks

Parameters

scip	SCIP
graph	graph data structure (in/out)

Definition at line 149 of file reduce_simple.c.

References FALSE, GRAPH::grad, graph_get_nNodes(), graph_knot_del(), graph_knot_isInRange(), GRAPH::head, Is_term, GRAPH::mark, nnodes, GRAPH::outbeg, SCIP_Bool, GRAPH::term, and TRUE.

Referenced by pseudodeleteExecute(), and reduce_pathreplace().

◆ reduce_simple()

SCIP_RETCODE reduce_simple	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	solnode,
		int *	nelims,
		int *	edgestate
	)

basic reduction tests for the STP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offset value
solnode	node array to mark whether an node is part of a given solution (CONNECT), or NULL
nelims	pointer to number of reductions
edgestate	array to store status of (directed) edge (for propagation, can otherwise be set to NULL)

Definition at line 184 of file reduce_simple.c.

References GRAPH::cost, EAT_LAST, Edge_anti, EDGE_BLOCKED, FALSE, FARAWAY, GRAPH::grad, graph_edge_del(), graph_fixed_addEdge(), graph_knot_contract(), graph_knot_contractLowdeg2High(), graph_knot_replaceDeg2(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_unconnected(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisLE(), SCIPisLT(), GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by execNvSl(), redLoopInnerStp(), and reduce_redLoopStp().

◆ reduce_simple_sap()

SCIP_RETCODE reduce_simple_sap	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	count
	)

basic reduction tests for the SAP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offfset value
count	pointer to number of reductions

Definition at line 397 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, Edge_anti, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_edge_printInfo(), graph_get_nNodes(), graph_knot_contract(), graph_knot_contractFixed(), graph_knot_del(), graph_knot_printInfo(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, LT, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPintListNodeAppendCopy(), SCIPisGT(), SCIPqueueCreate(), SCIPqueueFree(), SCIPqueueInsert(), SCIPqueueIsEmpty(), SCIPqueueRemove(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by reduce_sap().

◆ reduce_simple_dc()

void reduce_simple_dc	(	SCIP *	scip,
		GRAPH *	g
	)

basic reduction tests for the DCSTP...call only once!

Parameters

scip	SCIP data structure
g	graph data structure

Definition at line 619 of file reduce_simple.c.

References EAT_LAST, graph_edge_del(), graph_get_nNodes(), GRAPH::head, GRAPH::maxdeg, nnodes, GRAPH::oeat, GRAPH::outbeg, STP_DCSTP, GRAPH::stp_type, GRAPH::terms, and TRUE.

Referenced by reduce_dc().

◆ reduce_simple_hc()

SCIP_RETCODE reduce_simple_hc	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	count
	)

basic reduction tests for the HCDSTP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offfset value
count	pointer to number of reductions

Definition at line 655 of file reduce_simple.c.

References GRAPH::cost, EAT_LAST, FALSE, FARAWAY, flipedge, graph_edge_del(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_OKAY, SCIPdebugMessage, SCIPisGE(), SCIPisLT(), GRAPH::source, STP_DHCSTP, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by reduce_hc().

◆ reduce_contract0Edges()

SCIP_RETCODE reduce_contract0Edges	(	SCIP *	scip,
		GRAPH *	g,
		int *	solnode,
		SCIP_Bool	savehistory
	)

contract edges of weight zero

Parameters

scip	SCIP data structure
g	graph data structure
solnode	solution node mark or NULL
savehistory	save the history?

Definition at line 733 of file reduce_simple.c.

References GRAPH::cost, EAT_FREE, GRAPH::edges, flipedge, graph_edge_getAncestors(), graph_fixed_addEdge(), graph_knot_contract(), graph_pc_isPcMw(), GRAPH::head, NULL, GRAPH::oeat, GRAPH::pcancestors, SCIP_CALL, SCIP_OKAY, SCIPintListNodeAppendCopy(), SCIPisZero(), and GRAPH::tail.

Referenced by decomposePartialExact(), reduce_redLoopStp(), and reduce_termsepaFull().

◆ reduce_deleteMultiedges()

SCIP_RETCODE reduce_deleteMultiedges	(	SCIP *	scip,
		GRAPH *	g
	)

Parameters

scip	SCIP data structure
g	graph data structure

Definition at line 782 of file reduce_simple.c.

References EAT_LAST, graph_edge_del(), GRAPH::head, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and TRUE.

◆ reduce_fixedConflicts()

SCIP_RETCODE reduce_fixedConflicts	(	SCIP *	scip,
		const int *	edgestate,
		GRAPH *	g,
		int *	countnew
	)

basic reductions

Parameters

scip	SCIP data structure
edgestate	for propagation or NULL
g	graph data structure
countnew	pointer to number of new reductions (will be initially set to 0)

Definition at line 832 of file reduce_simple.c.

References EAT_FREE, EDGE_BLOCKED, graph_edge_del(), graph_edge_getPseudoAncestors(), graph_edge_nPseudoAncestors(), graph_get_nEdges(), graph_getFixpseudonodes(), graph_getNfixpseudonodes(), graph_pseudoAncestorsGetHashArraySize(), GRAPH::is_packed, NULL, GRAPH::oeat, GRAPH::pseudoancestors, SCIP_CALL, SCIP_OKAY, SCIPallocCleanBufferArray, SCIPdebugMessage, SCIPfreeCleanBufferArray, and TRUE.

Referenced by reduce_redLoopStp().

◆ reduce_rpt()

SCIP_RETCODE reduce_rpt	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	count
	)

root proximity terminal test (SAP)

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offset value
count	pointer to number of reductions

Definition at line 916 of file reduce_simple.c.

References GRAPH::cost, EAT_LAST, FALSE, GRAPH::grad, graph_edge_printInfo(), graph_get_nNodes(), graph_knot_contractFixed(), graph_knot_printInfo(), graph_knotIsNWLeaf(), graph_path_execX(), graph_typeIsUndirected(), GT, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, GRAPH::source, STP_NWPTSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by reduce_sap().

◆ reduce_cutEdgeTryPrune()

SCIP_RETCODE reduce_cutEdgeTryPrune	(	SCIP *	scip,
		int	cutedge,
		GRAPH *	g,
		SCIP_Bool *	success
	)

try to remove cute edge and prune one side of the graph

Parameters

scip	SCIP data structure
cutedge	the edge
g	graph data structure
success	could we prune the edge?

Definition at line 1001 of file reduce_simple.c.

References cutEdgeProbe(), cutEdgePrune(), FALSE, GRAPH::grad, graph_edge_isInRange(), graph_get_nNodes(), GRAPH::head, Is_term, nnodes, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by nsvExec().

◆ reduce_identifyNonLeafTerms()

void reduce_identifyNonLeafTerms	(	SCIP *	scip,
		GRAPH *	g
	)

identify non-leaf terminals and remove extensions

Parameters

scip	SCIP data structure
g	graph data structure

Definition at line 1052 of file reduce_simple.c.

References GRAPH::extended, FALSE, GRAPH::grad, graph_get_nNodes(), graph_pc_evalTermIsNonLeaf(), graph_pc_isPc(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsNonLeafTerm(), graph_pc_term2edgeIsConsistent(), graph_pc_termIsNonLeafTerm(), graph_pc_termToNonLeafTerm(), graph_valid(), Is_term, nnodes, GRAPH::prize, SCIPdebugMessage, SCIPisGE(), GRAPH::source, STP_PCSPG, GRAPH::stp_type, GRAPH::term, and GRAPH::term2edge.

Referenced by reduce_da(), reduce_daPcMw(), and reduce_simple_pc().

◆ reduce_unconnected()

SCIP_RETCODE reduce_unconnected	(	SCIP *	scip,
		GRAPH *	g
	)

Parameters

scip	SCIP data structure
g	graph data structure

Definition at line 1097 of file reduce_simple.c.

References GRAPH::grad, graph_knot_del(), graph_pc_isPc(), graph_pc_termIsNonLeafTerm(), graph_trail_arr(), Is_term, GRAPH::knots, nnodes, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::source, GRAPH::term, and TRUE.

Referenced by cutEdgePrune(), daRoundExit(), extreduce_pseudoDeleteNodes(), fixVarsRedbased(), ledgeFromNetgraph(), mincut_findTerminalSeparators(), redcostGraphComputeSteinerTree(), redcostGraphComputeSteinerTreeDegCons(), redLoopInnerStp(), reduce_bd34WithSd(), reduce_bdkWithSd(), reduce_dapaths(), reduce_exec(), reduce_impliedProfitBased(), reduce_redLoopMw(), reduce_sdImpLongEdge(), reduce_simple(), reduce_simple_mw(), reduce_simple_pc(), reduceLurk(), SCIPStpHeurPruneRun(), and SCIPStpHeurSlackPruneRun().

◆ reduce_unconnectedForDirected()

SCIP_RETCODE reduce_unconnectedForDirected	(	SCIP *	scip,
		GRAPH *	g
	)

Parameters

scip	SCIP data structure
g	graph data structure

Definition at line 1134 of file reduce_simple.c.

References GRAPH::grad, graph_get_nNodes(), graph_knot_del(), graph_trail_costAware(), graph_typeIsUndirected(), Is_term, nnodes, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::source, GRAPH::term, and TRUE.

Referenced by daRoundExit(), redcostGraphComputeSteinerTreeDirected(), reduce_boundHopDa(), and reduce_hc().

◆ reduce_unconnectedInfeas()

SCIP_RETCODE reduce_unconnectedInfeas	(	SCIP *	scip,
		SCIP_Bool	beVerbose,
		GRAPH *	g,
		SCIP_Bool *	infeas
	)

remove unconnected vertices and checks whether problem is infeasible

Parameters

scip	SCIP data structure
beVerbose	be verbose?
g	graph data structure
infeas	is problem infeasible?

Definition at line 1164 of file reduce_simple.c.

References EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), graph_get_nNodes(), graph_trail_arr(), GRAPH::inpbeg, Is_term, nnodes, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::source, GRAPH::term, and TRUE.

Referenced by check_inputgraph(), and propgraphPruneUnconnected().

SCIP

Detailed Description

Functions

Function Documentation

◆ cutEdgePrune()

◆ cutEdgeProbe()

◆ reduce_nodesDeg1()

◆ reduce_simple()

◆ reduce_simple_sap()

◆ reduce_simple_dc()

◆ reduce_simple_hc()

◆ reduce_contract0Edges()

◆ reduce_deleteMultiedges()

◆ reduce_fixedConflicts()

◆ reduce_rpt()

◆ reduce_cutEdgeTryPrune()

◆ reduce_identifyNonLeafTerms()

◆ reduce_unconnected()

◆ reduce_unconnectedForDirected()

◆ reduce_unconnectedInfeas()