mincut.h File Reference

Detailed Description

Minimum cut routines for Steiner problems.

Author

Daniel Rehfeldt

This file encompasses minimum cut routines for Steiner tree problems.

Definition in file mincut.h.

#include "graph.h"

Go to the source code of this file.

Typedefs
typedef struct terminal_separator_storage	TERMSEPAS

Functions
SCIP_RETCODE	mincut_termsepasInit (SCIP *, const GRAPH *, int, int, TERMSEPAS **)
void	mincut_termsepasFree (SCIP *, TERMSEPAS **)
int	mincut_termsepasGetNall (const TERMSEPAS *)
int	mincut_termsepasGetN (const TERMSEPAS *, int)
const int *	mincut_termsepasGetFirst (int, TERMSEPAS *, int *, int *)
const int *	mincut_termsepasGetNext (int, TERMSEPAS *, int *, int *)
int	mincut_termsepasGetSource (const TERMSEPAS *)
SCIP_Bool	mincut_findTerminalSeparatorsIsPromising (const GRAPH *)
SCIP_RETCODE	mincut_findTerminalSeparators (SCIP *, SCIP_RANDNUMGEN *, GRAPH *, TERMSEPAS *)
SCIP_RETCODE	mincut_separateLp (SCIP *, SCIP_CONSHDLR *, SCIP_RANDNUMGEN *, const int *, GRAPH *, int, int *)

Typedef Documentation

TERMSEPAS

typedef struct terminal_separator_storage TERMSEPAS

Definition at line 33 of file mincut.h.

Function Documentation

mincut_termsepasInit()

SCIP_RETCODE mincut_termsepasInit	(	SCIP *	scip,
		const GRAPH *	g,
		int	maxnsepas,
		int	maxsepasize,
		TERMSEPAS **	termsepas
	)

initializes

Parameters

scip	SCIP
g	graph
maxnsepas	maximum number of separators to compute
maxsepasize	maximum size of separator
termsepas	to initialize

Definition at line 2074 of file mincut.c.

References terminal_separator_storage::currsepa_n, terminal_separator_storage::maxnsepas, terminal_separator_storage::maxsepasize, terminal_separator_storage::nsepas, terminal_separator_storage::nsepas_all, terminal_separator_storage::nsepaterms_csr, terminal_separator_storage::root, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, terminal_separator_storage::sepas, terminal_separator_storage::sepastarts_csr, and terminal_separator_storage::sepaterms_csr.

Referenced by initHelpers(), testTerminalSeparatorsAreFound(), testTerminalSeparatorsAreFound2(), and testTerminalSeparatorsAreFound3().

mincut_termsepasFree()

void mincut_termsepasFree	(	SCIP *	scip,
		TERMSEPAS **	termsepas
	)

frees

Parameters

scip	SCIP
termsepas	to free

Definition at line 2113 of file mincut.c.

References terminal_separator_storage::currsepa_n, terminal_separator_storage::nsepas, SCIPfreeMemory, SCIPfreeMemoryArray, terminal_separator_storage::sepas, terminal_separator_storage::sepastarts_csr, and terminal_separator_storage::sepaterms_csr.

Referenced by freeHelpers(), testTerminalSeparatorsAreFound(), testTerminalSeparatorsAreFound2(), and testTerminalSeparatorsAreFound3().

mincut_termsepasGetNall()

int mincut_termsepasGetNall

(

const TERMSEPAS *

termsepas

)

returns number of all separators

Parameters

termsepas

terminal separators

Definition at line 2135 of file mincut.c.

References terminal_separator_storage::nsepas_all.

Referenced by mincut_findTerminalSeparators(), reduce_termsepaFull(), and testTerminalSeparatorsAreFound().

mincut_termsepasGetN()

int mincut_termsepasGetN	(	const TERMSEPAS *	termsepas,
		int	sepasize
	)

returns number of separators per given size

Parameters

termsepas	terminal separators
sepasize	size

Definition at line 2147 of file mincut.c.

References terminal_separator_storage::maxnsepas, and terminal_separator_storage::nsepas.

mincut_termsepasGetFirst()

const int* mincut_termsepasGetFirst	(	int	sepasize,
		TERMSEPAS *	termsepas,
		int *	sinkterm,
		int *	nsinknodes
	)

Returns first separator of given size. Returns NULL if none is available.

Parameters

sepasize	size
termsepas	terminal separators
sinkterm	the sink
nsinknodes	number of sink-side nodes

Definition at line 2162 of file mincut.c.

References terminal_separator_storage::currsepa_n, and mincut_termsepasGetNext().

Referenced by testTerminalSeparatorsAreFound(), and testTerminalSeparatorsAreFound2().

mincut_termsepasGetNext()

const int* mincut_termsepasGetNext	(	int	sepasize,
		TERMSEPAS *	termsepas,
		int *	sinkterm,
		int *	nsinknodes
	)

Returns next separator of given size. Returns NULL if none is available.

Parameters

sepasize	size
termsepas	terminal separators
sinkterm	the sink
nsinknodes	number of sink-side nodes

Definition at line 2179 of file mincut.c.

References terminal_separator_storage::currsepa_n, terminal_separator_storage::nsepas_all, terminal_separator::nsinknodes, NULL, terminal_separator_storage::sepas, terminal_separator_storage::sepastarts_csr, terminal_separator_storage::sepaterms_csr, terminal_separator::sinkterm, and minimum_cut_helper::terms.

Referenced by mincut_termsepasGetFirst(), reduce_termsepaGetNextComp(), testTerminalSeparatorsAreFound(), testTerminalSeparatorsAreFound2(), and testTerminalSeparatorsAreFound3().

mincut_termsepasGetSource()

int mincut_termsepasGetSource

(

const TERMSEPAS *

termsepas

)

gets terminal separator source

Parameters

termsepas

terminal separators

Definition at line 2232 of file mincut.c.

References terminal_separator_storage::root.

Referenced by reduce_termsepaGetNextComp().

mincut_findTerminalSeparatorsIsPromising()

SCIP_Bool mincut_findTerminalSeparatorsIsPromising

(

const GRAPH *

g

)

is it promising to look for terminal separators?

Parameters

g	graph data structure

Definition at line 2243 of file mincut.c.

References FALSE, graph_get_nVET(), nnodes, NULL, GRAPH::terms, and TERMSEPA_SPARSE_MAXRATIO.

mincut_findTerminalSeparators()

SCIP_RETCODE mincut_findTerminalSeparators	(	SCIP *	scip,
		SCIP_RANDNUMGEN *	randnumgen,
		GRAPH *	g,
		TERMSEPAS *	termsepas
	)

searches for (small) terminal separators

Parameters

scip	SCIP data structure
randnumgen	random number generator or NULL
g	graph data structure
termsepas	terminal separator storage

Definition at line 2274 of file mincut.c.

References FALSE, graph_mincut_setDefaultVals(), graph_printInfoReduced(), Is_term, terminal_separator_storage::maxnsepas, mincut_termsepasGetNall(), mincutExec(), mincutFree(), mincutGetNextSinkTerm(), mincutInit(), mincutPrepareForTermSepa(), minimum_cut_helper::nodes_wakeState, terminal_separator_storage::nsepas_all, minimum_cut_helper::ntermcands, reduce_unconnected(), minimum_cut_helper::root, terminal_separator_storage::root, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisStopped(), GRAPH::term, GRAPH::terms, termsepaStoreCutTry(), and TRUE.

Referenced by reduce_termsepaDaWithExperma(), reduce_termsepaFull(), testTerminalSeparatorsAreFound(), testTerminalSeparatorsAreFound2(), and testTerminalSeparatorsAreFound3().

mincut_separateLp()

SCIP_RETCODE mincut_separateLp	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		SCIP_RANDNUMGEN *	randnumgen,
		const int *	termorg,
		GRAPH *	g,
		int	maxncuts,
		int *	ncuts
	)

separates Steiner cuts for LP

Parameters

scip	SCIP data structure
conshdlr	constraint handler
randnumgen	random number generator or NULL
termorg	original terminals or NULL
g	graph data structure
maxncuts	maximal number of cuts
ncuts	pointer to store number of cuts

Definition at line 2360 of file mincut.c.

References minimum_cut_helper::csr_edgeDefaultToCsr, minimum_cut_helper::csr_headarr, minimum_cut_helper::csr_start, EAT_LAST, minimum_cut_helper::edges_capa, minimum_cut_helper::edges_isRemoved, FALSE, FLOW_FACTOR, graph_get_nNodes(), graph_mincut_exec(), graph_mincut_setDefaultVals(), GRAPH::ieat, GRAPH::inpbeg, Is_term, lpcutAdd(), lpcutSetEdgeCapacity(), GRAPH::mark, mincutExec(), mincutFree(), mincutGetNextSinkTerm(), mincutInit(), mincutPrepareForLp(), nnodes, minimum_cut_helper::nodes_wakeState, minimum_cut_helper::ntermcands, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisFeasGE(), SCIPisStopped(), GRAPH::source, GRAPH::term, minimum_cut_helper::terms, GRAPH::terms, TRUE, and minimum_cut_helper::xval.

Referenced by SCIP_DECL_CONSSEPALP().