mincut.c 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.c.

#include "mincut.h"
#include "probdata_stp.h"
#include "misc_stp.h"
#include "stpvector.h"
#include "reduce.h"
#include "portab.h"

Go to the source code of this file.

Data Structures
struct	minimum_cut_helper
struct	terminal_separator
struct	terminal_separator_storage

Macros
#define	Q_NULL   -1 /* NULL element of queue/list */
#define	ADDCUTSTOPOOL   FALSE
#define	TERMSEPA_SPARSE_MAXRATIO   4
#define	TERMSEPA_MAXCUTSIZE_DEFAULT   5
#define	TERMSEPA_MAXNCUTS_DEFAULT   100
#define	TERMSEPA_NROOTCANDS   3
#define	FLOW_FACTOR   1000000
#define	CREEP_VALUE   10

Typedefs
typedef struct minimum_cut_helper	MINCUT
typedef struct terminal_separator	TSEPA

Functions
static SCIP_Bool	csrFlipedgesAreValid (const GRAPH *g, const MINCUT *mincut)
static SCIP_Bool	termsepaCutIsCorrect (SCIP *scip, const GRAPH *g, int ncutterms, const int *cutterms, int sinkterm, const MINCUT *mincut)
static int	termsepaGetCapaInf (const GRAPH *g, const MINCUT *mincut)
static void	updateTerminalSource (SCIP *scip, int rootcand, const GRAPH *g, int *root, int *rootcompsize)
static int	termsepaFindTerminalSource (SCIP *scip, const GRAPH *g, const MINCUT *mincut)
static void	termsepaCollectCutNodes (const GRAPH *g, const TERMSEPAS *termsepas, const MINCUT *mincut, int sinkterm, int *cutterms, int *ncutterms, SCIP_Bool *cutIsGood)
static SCIP_RETCODE	termsepaTraverseSinkComp (SCIP *scip, const GRAPH *g, SCIP_Bool removeTerms, SCIP_Bool updateVisitedTerms, int ncutterms, const int *cutterms, int sinkterm, MINCUT *mincut, int *ncompnodes)
static SCIP_RETCODE	termsepaRemoveCutTerminals (SCIP *scip, const GRAPH *g, int ncutterms, const int *cutterms, int sinkterm, MINCUT *mincut)
static SCIP_RETCODE	termsepaGetCompNnodes (SCIP *scip, const GRAPH *g, int ncutterms, const int *cutterms, int sinkterm, MINCUT *mincut, int *ncompnodes)
static SCIP_RETCODE	termsepaStoreCutFinalize (SCIP *scip, const GRAPH *g, int sinkterm, MINCUT *mincut, int ncutterms, const int *cutterms, TERMSEPAS *termsepas, SCIP_Bool *success)
static SCIP_RETCODE	termsepaStoreCutTry (SCIP *scip, const GRAPH *g, int sinkterm, MINCUT *mincut, TERMSEPAS *termsepas)
static SCIP_RETCODE	termsepaCsrInit (const GRAPH *g, MINCUT *mincut)
static void	termsepaCsrAddTermCopies (const GRAPH *g, MINCUT *mincut)
static void	termsepaCsrAddEdges (const GRAPH *g, MINCUT *mincut)
static void	termsepaCsrAddReverseEdges (const GRAPH *g, MINCUT *mincut)
static int	termsepaCsrGetMaxNnodes (const GRAPH *g)
static int	termsepaCsrGetMaxNedges (int root, const GRAPH *g)
static void	termsepaBuildRootcomp (const GRAPH *g, MINCUT *mincut)
static SCIP_RETCODE	termsepaBuildCsr (const GRAPH *g, MINCUT *mincut)
static SCIP_RETCODE	mincutInitForLp (SCIP *scip, const GRAPH *g, MINCUT *mincut)
static SCIP_RETCODE	mincutInitForTermSepa (SCIP *scip, GRAPH *g, MINCUT *mincut)
static SCIP_RETCODE	mincutInit (SCIP *scip, SCIP_RANDNUMGEN *randnumgen, SCIP_Bool isLpcut, GRAPH *g, MINCUT **mincut)
static SCIP_RETCODE	mincutPrepareForLp (SCIP *scip, const GRAPH *g, MINCUT *mincut)
static SCIP_RETCODE	mincutPrepareForTermSepa (SCIP *scip, GRAPH *g, MINCUT *mincut)
static int	mincutGetNextSinkTerm (const GRAPH *g, SCIP_Bool firstrun, MINCUT *mincut)
static void	mincutExec (const GRAPH *g, int sinkterm, SCIP_Bool wasRerun, MINCUT *mincut)
static void	mincutFree (SCIP *scip, MINCUT **mincut)
static SCIP_RETCODE	lpcutAdd (SCIP *scip, SCIP_CONSHDLR *conshdlr, const GRAPH *g, const int *nodes_inRootComp, const STP_Bool *edges_isRemoved, const SCIP_Real *xvals, int *capa, const int updatecapa, SCIP_Bool local, SCIP_Bool *success)
static void	lpcutSetEdgeCapacity (const GRAPH *g, const SCIP_Real *xval, SCIP_Bool creep_flow, SCIP_Bool flip, int *RESTRICT capa)
SCIP_RETCODE	mincut_termsepasInit (SCIP *scip, const GRAPH *g, int maxnsepas, int maxsepasize, TERMSEPAS **termsepas)
void	mincut_termsepasFree (SCIP *scip, TERMSEPAS **termsepas)
int	mincut_termsepasGetNall (const TERMSEPAS *termsepas)
int	mincut_termsepasGetN (const TERMSEPAS *termsepas, int sepasize)
const int *	mincut_termsepasGetFirst (int sepasize, TERMSEPAS *termsepas, int *sinkterm, int *nsinknodes)
const int *	mincut_termsepasGetNext (int sepasize, TERMSEPAS *termsepas, int *sinkterm, int *nsinknodes)
int	mincut_termsepasGetSource (const TERMSEPAS *termsepas)
SCIP_Bool	mincut_findTerminalSeparatorsIsPromising (const GRAPH *g)
SCIP_RETCODE	mincut_findTerminalSeparators (SCIP *scip, SCIP_RANDNUMGEN *randnumgen, GRAPH *g, TERMSEPAS *termsepas)
SCIP_RETCODE	mincut_separateLp (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_RANDNUMGEN *randnumgen, const int *termorg, GRAPH *g, int maxncuts, int *ncuts)

Macro Definition Documentation

Q_NULL

#define Q_NULL   -1 /* NULL element of queue/list */

Definition at line 37 of file mincut.c.

ADDCUTSTOPOOL

#define ADDCUTSTOPOOL   FALSE

Definition at line 38 of file mincut.c.

TERMSEPA_SPARSE_MAXRATIO

#define TERMSEPA_SPARSE_MAXRATIO   4

Definition at line 39 of file mincut.c.

Referenced by mincut_findTerminalSeparatorsIsPromising().

TERMSEPA_MAXCUTSIZE_DEFAULT

#define TERMSEPA_MAXCUTSIZE_DEFAULT   5

Definition at line 40 of file mincut.c.

TERMSEPA_MAXNCUTS_DEFAULT

#define TERMSEPA_MAXNCUTS_DEFAULT   100

Definition at line 41 of file mincut.c.

TERMSEPA_NROOTCANDS

#define TERMSEPA_NROOTCANDS   3

Definition at line 42 of file mincut.c.

Referenced by termsepaFindTerminalSource().

FLOW_FACTOR

#define FLOW_FACTOR   1000000

Definition at line 49 of file mincut.c.

Referenced by lpcutAdd(), lpcutSetEdgeCapacity(), mincut_separateLp(), and mincutPrepareForLp().

CREEP_VALUE

#define CREEP_VALUE   10

Definition at line 50 of file mincut.c.

Referenced by lpcutSetEdgeCapacity(), and mincutPrepareForLp().

Typedef Documentation

MINCUT

typedef struct minimum_cut_helper MINCUT

minimum cut helper

TSEPA

typedef struct terminal_separator TSEPA

single separator info

Function Documentation

csrFlipedgesAreValid()

static SCIP_Bool csrFlipedgesAreValid ( const GRAPH *  g, const MINCUT *  mincut  )

inlinestatic

valid flip-edges?

Parameters

g	the graph
mincut	minimum cut

Definition at line 273 of file mincut.c.

References minimum_cut_helper::csr_edgeflipped, minimum_cut_helper::csr_headarr, minimum_cut_helper::csr_start, FALSE, minimum_cut_helper::isLpcut, GRAPH::mincut_r, minimum_cut_helper::termsepa_nnodes, and TRUE.

Referenced by termsepaCsrAddReverseEdges().

termsepaCutIsCorrect()

static SCIP_Bool termsepaCutIsCorrect ( SCIP *  scip, const GRAPH *  g, int  ncutterms, const int *  cutterms, int  sinkterm, const MINCUT *  mincut  )

static

checks cut

Parameters

scip	SCIP data structure
g	the graph
ncutterms	number of cut terminals
cutterms	stores cut terminals
sinkterm	sink terminal
mincut	minimum cut

Definition at line 310 of file mincut.c.

References EAT_LAST, FALSE, graph_get_nNodes(), graph_knot_isInRange(), GRAPH::head, nnodes, minimum_cut_helper::nodes_wakeState, NULL, GRAPH::oeat, GRAPH::outbeg, minimum_cut_helper::root, SCIP_Bool, SCIP_CALL_ABORT, SCIPallocMemoryArray, SCIPerrorMessage, SCIPfreeMemoryArray, STP_Vectype, StpVecFree, StpVecGetSize, StpVecPopBack, StpVecPushBack, StpVecReserve, and TRUE.

Referenced by termsepaStoreCutTry().

termsepaGetCapaInf()

static int termsepaGetCapaInf ( const GRAPH *  g, const MINCUT *  mincut  )

static

gets infinity

Parameters

g	the graph
mincut	minimum cut

Definition at line 408 of file mincut.c.

References GRAPH::terms.

Referenced by termsepaCollectCutNodes(), and termsepaCsrAddEdges().

updateTerminalSource()

static void updateTerminalSource ( SCIP *  scip, int  rootcand, const GRAPH *  g, int *  root, int *  rootcompsize  )

static

updates; takes root candidate if greater than current

Parameters

scip	SCIP data structure
rootcand	new root candidate
g	the graph
root	incumbent (IN/OUT)
rootcompsize	size of component (IN/OUT)

Definition at line 419 of file mincut.c.

References FALSE, graph_get_nNodes(), graph_knot_isInRange(), GRAPH::head, Is_term, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL_ABORT, SCIPallocCleanBufferArray, SCIPfreeCleanBufferArray, STP_Vectype, StpVecFree, StpVecGetSize, StpVecPushBack, StpVecReserve, GRAPH::term, and TRUE.

Referenced by termsepaFindTerminalSource().

termsepaFindTerminalSource()

static int termsepaFindTerminalSource ( SCIP *  scip, const GRAPH *  g, const MINCUT *  mincut  )

static

finds a root terminal

Parameters

scip	SCIP data structure
g	the graph
mincut	minimum cut

Definition at line 489 of file mincut.c.

References graph_getTerms(), Is_term, minimum_cut_helper::randnumgen, SCIP_CALL_ABORT, SCIPallocMemoryArray, SCIPfreeMemoryArray, SCIPrandomGetInt(), GRAPH::source, GRAPH::term, minimum_cut_helper::terms, GRAPH::terms, TERMSEPA_NROOTCANDS, and updateTerminalSource().

Referenced by mincutInitForTermSepa().

termsepaCollectCutNodes()

static void termsepaCollectCutNodes ( const GRAPH *  g, const TERMSEPAS *  termsepas, const MINCUT *  mincut, int  sinkterm, int *  cutterms, int *  ncutterms, SCIP_Bool *  cutIsGood  )

static

collect cut nodes

Parameters

g	the graph
termsepas	terminal separator storage
mincut	minimum cut
sinkterm	sink terminal
cutterms	terminals
ncutterms	number of terminals
cutIsGood	is cut nodes

Definition at line 533 of file mincut.c.

References minimum_cut_helper::csr_headarr, minimum_cut_helper::csr_start, minimum_cut_helper::edges_capa, FALSE, Is_term, terminal_separator_storage::maxsepasize, minimum_cut_helper::nodes_wakeState, SCIP_Bool, GRAPH::term, minimum_cut_helper::termsepa_nnodes, termsepaGetCapaInf(), and TRUE.

Referenced by termsepaStoreCutTry().

termsepaTraverseSinkComp()

static SCIP_RETCODE termsepaTraverseSinkComp ( SCIP *  scip, const GRAPH *  g, SCIP_Bool  removeTerms, SCIP_Bool  updateVisitedTerms, int  ncutterms, const int *  cutterms, int  sinkterm, MINCUT *  mincut, int *  ncompnodes  )

static

helper; traverses and does additional optional stuff

Parameters

scip	SCIP data structure
g	the graph
removeTerms	remove terminals reachable from sink via non-terminal paths?
updateVisitedTerms	do update?
ncutterms	size of the separator
cutterms	the separator nodes (all terminals)
sinkterm	sink terminal of current cut
mincut	minimum cut
ncompnodes	number of nodes in component (OUT)

Definition at line 590 of file mincut.c.

References FALSE, graph_get_nNodes(), graph_knot_isInRange(), GRAPH::head, Is_term, nnodes, minimum_cut_helper::nodes_wakeState, minimum_cut_helper::ntermcands, NULL, GRAPH::oeat, GRAPH::outbeg, minimum_cut_helper::root, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocCleanBufferArray, SCIPfreeCleanBufferArray, STP_Vectype, StpVecFree, StpVecGetSize, StpVecPushBack, StpVecReserve, SWAP_INTS, GRAPH::term, minimum_cut_helper::terms, minimum_cut_helper::terms_mincompsize, minimum_cut_helper::terms_minsepasize, and TRUE.

Referenced by termsepaGetCompNnodes(), and termsepaRemoveCutTerminals().

termsepaRemoveCutTerminals()

static SCIP_RETCODE termsepaRemoveCutTerminals ( SCIP *  scip, const GRAPH *  g, int  ncutterms, const int *  cutterms, int  sinkterm, MINCUT *  mincut  )

static

removes terminals in current cut

Parameters

scip	SCIP data structure
g	the graph
ncutterms	size of the separator
cutterms	the separator nodes (all terminals)
sinkterm	sink terminal of current cut
mincut	minimum cut

Definition at line 710 of file mincut.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, termsepaTraverseSinkComp(), and TRUE.

Referenced by termsepaStoreCutTry().

termsepaGetCompNnodes()

static SCIP_RETCODE termsepaGetCompNnodes ( SCIP *  scip, const GRAPH *  g, int  ncutterms, const int *  cutterms, int  sinkterm, MINCUT *  mincut, int *  ncompnodes  )

static

gets number of nodes

Parameters

scip	SCIP data structure
g	the graph
ncutterms	size of the separator
cutterms	the separator nodes (all terminals)
sinkterm	sink terminal of current cut
mincut	minimum cut
ncompnodes	number of nodes in component

Definition at line 730 of file mincut.c.

References FALSE, SCIP_Bool, SCIP_CALL, SCIP_OKAY, termsepaTraverseSinkComp(), and TRUE.

Referenced by termsepaStoreCutFinalize().

termsepaStoreCutFinalize()

static SCIP_RETCODE termsepaStoreCutFinalize ( SCIP *  scip, const GRAPH *  g, int  sinkterm, MINCUT *  mincut, int  ncutterms, const int *  cutterms, TERMSEPAS *  termsepas, SCIP_Bool *  success  )

static

stores cut NOTE: this methods is call once the cut vertices are already stored in the CSR array

Parameters

scip	SCIP data structure
g	the graph
sinkterm	sink terminal
mincut	minimum cut
ncutterms	number of cut terminals
cutterms	cut terminals
termsepas	terminal separator storage
success	success?

Definition at line 752 of file mincut.c.

References FALSE, graph_get_nNodes(), terminal_separator_storage::maxsepasize, nnodes, minimum_cut_helper::nodes_wakeState, terminal_separator_storage::nsepas, terminal_separator_storage::nsepas_all, terminal_separator_storage::nsepaterms_csr, terminal_separator::nsinknodes, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, terminal_separator_storage::sepas, terminal_separator_storage::sepastarts_csr, terminal_separator::sinkterm, minimum_cut_helper::terms_mincompsize, minimum_cut_helper::terms_minsepasize, termsepaGetCompNnodes(), and TRUE.

Referenced by termsepaStoreCutTry().

termsepaStoreCutTry()

static SCIP_RETCODE termsepaStoreCutTry ( SCIP *  scip, const GRAPH *  g, int  sinkterm, MINCUT *  mincut, TERMSEPAS *  termsepas  )

static

tries to add cut

Parameters

scip	SCIP data structure
g	the graph
sinkterm	sink terminal
mincut	minimum cut
termsepas	terminal separator storage

Definition at line 829 of file mincut.c.

References graph_knot_isInRange(), Is_term, minimum_cut_helper::isLpcut, minimum_cut_helper::nodes_wakeState, terminal_separator_storage::nsepaterms_csr, SCIP_Bool, SCIP_CALL, SCIP_OKAY, terminal_separator_storage::sepaterms_csr, GRAPH::term, termsepaCollectCutNodes(), termsepaCutIsCorrect(), termsepaRemoveCutTerminals(), and termsepaStoreCutFinalize().

Referenced by mincut_findTerminalSeparators().

termsepaCsrInit()

static SCIP_RETCODE termsepaCsrInit ( const GRAPH *  g, MINCUT *  mincut  )

static

initializes

Parameters

g	the graph
mincut	minimum cut

Definition at line 865 of file mincut.c.

References minimum_cut_helper::csr_edgeDefaultToCsr, graph_get_nEdges(), and SCIP_OKAY.

Referenced by termsepaBuildCsr().

termsepaCsrAddTermCopies()

static void termsepaCsrAddTermCopies ( const GRAPH *  g, MINCUT *  mincut  )

static

creates copies of potential separator terminals

Parameters

g	the graph
mincut	minimum cut

Definition at line 884 of file mincut.c.

References EAT_LAST, FALSE, graph_get_nNodes(), GRAPH::head, Is_term, GRAPH::mincut_e, minimum_cut_helper::nodes_wakeState, minimum_cut_helper::ntermcands, GRAPH::oeat, GRAPH::outbeg, minimum_cut_helper::randnumgen, minimum_cut_helper::root, SCIP_Bool, SCIPdebugMessage, SCIPrandomPermuteIntArray(), GRAPH::term, minimum_cut_helper::terms, minimum_cut_helper::termsepa_nnodes, minimum_cut_helper::termsepa_termToCopy, and TRUE.

Referenced by termsepaBuildCsr().

termsepaCsrAddEdges()

static void termsepaCsrAddEdges ( const GRAPH *  g, MINCUT *  mincut  )

static

adds CSR edges

Parameters

g	the graph
mincut	minimum cut

Definition at line 966 of file mincut.c.

References BMScopyMemoryArray, minimum_cut_helper::csr_edgeDefaultToCsr, minimum_cut_helper::csr_headarr, minimum_cut_helper::csr_nedges, minimum_cut_helper::csr_start, EAT_LAST, minimum_cut_helper::edges_capa, GRAPH::grad, graph_get_nNodes(), GRAPH::head, Is_term, GRAPH::mincut_numb, GRAPH::mincut_r, minimum_cut_helper::nodes_wakeState, GRAPH::oeat, GRAPH::outbeg, minimum_cut_helper::root, SCIP_Bool, GRAPH::term, minimum_cut_helper::termsepa_nedges, minimum_cut_helper::termsepa_nnodes, minimum_cut_helper::termsepa_termToCopy, and termsepaGetCapaInf().

Referenced by termsepaBuildCsr().

termsepaCsrAddReverseEdges()

static void termsepaCsrAddReverseEdges ( const GRAPH *  g, MINCUT *  mincut  )

static

adds CSR reverse edges

Parameters

g	the graph
mincut	minimum cut

Definition at line 1121 of file mincut.c.

References minimum_cut_helper::csr_edgeDefaultToCsr, minimum_cut_helper::csr_edgeflipped, minimum_cut_helper::csr_headarr, minimum_cut_helper::csr_start, csrFlipedgesAreValid(), flipedge, graph_get_nEdges(), graph_get_nNodes(), and minimum_cut_helper::termsepa_nnodes.

Referenced by termsepaBuildCsr().

termsepaCsrGetMaxNnodes()

static int termsepaCsrGetMaxNnodes ( const GRAPH *  g )

static

gets maximum number of nodes for extended terminal separation graph

Parameters

g

the graph

Definition at line 1186 of file mincut.c.

References graph_get_nNodes(), graph_get_nTerms(), nnodes, and nterms.

Referenced by mincutInitForTermSepa().

termsepaCsrGetMaxNedges()

static int termsepaCsrGetMaxNedges ( int  root, const GRAPH *  g  )

static

gets maximum number of edges for extended terminal separation graph

Parameters

root	root of enlarged graph
g	the graph

Definition at line 1201 of file mincut.c.

References GRAPH::grad, graph_get_nEdges(), graph_get_nNodes(), graph_knot_isInRange(), Is_term, nnodes, and GRAPH::term.

Referenced by mincutInitForTermSepa().

termsepaBuildRootcomp()

static void termsepaBuildRootcomp ( const GRAPH *  g, MINCUT *  mincut  )

static

builds and marks root component (nodes reachable from root via non-terminal paths)

Parameters

g	the graph
mincut	minimum cut

Definition at line 1229 of file mincut.c.

References EAT_LAST, GRAPH::head, Is_term, minimum_cut_helper::nodes_wakeState, GRAPH::oeat, GRAPH::outbeg, minimum_cut_helper::root, minimum_cut_helper::rootcut, minimum_cut_helper::rootcutsize, SCIPdebugMessage, and GRAPH::term.

Referenced by mincutPrepareForTermSepa().

termsepaBuildCsr()

static SCIP_RETCODE termsepaBuildCsr ( const GRAPH *  g, MINCUT *  mincut  )

static

builds CSR representation of enlarged graph; also build terminal candidates

Parameters

g	the graph
mincut	minimum cut

Definition at line 1275 of file mincut.c.

References SCIP_CALL, SCIP_OKAY, termsepaCsrAddEdges(), termsepaCsrAddReverseEdges(), termsepaCsrAddTermCopies(), and termsepaCsrInit().

Referenced by mincutPrepareForTermSepa().

mincutInitForLp()

static SCIP_RETCODE mincutInitForLp ( SCIP *  scip, const GRAPH *  g, MINCUT *  mincut  )

static

initializes for LP

Parameters

scip	SCIP data structure
g	the graph
mincut	minimum cut

Definition at line 1299 of file mincut.c.

References minimum_cut_helper::csr_edgeDefaultToCsr, minimum_cut_helper::csr_edgeflipped, minimum_cut_helper::csr_headarr, minimum_cut_helper::csr_start, minimum_cut_helper::edges_capa, minimum_cut_helper::edges_isRemoved, graph_get_nEdges(), graph_get_nNodes(), minimum_cut_helper::isLpcut, nnodes, minimum_cut_helper::nodes_wakeState, NULL, minimum_cut_helper::rootcut, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPprobdataGetVars(), SCIPprobdataGetXval(), SCIPvarGetUbGlobal(), minimum_cut_helper::terms, GRAPH::terms, and minimum_cut_helper::xval.

Referenced by mincutInit().

mincutInitForTermSepa()

static SCIP_RETCODE mincutInitForTermSepa ( SCIP *  scip, GRAPH *  g, MINCUT *  mincut  )

static

initializes for terminal separation

Parameters

scip	SCIP data structure
g	the graph
mincut	minimum cut

Definition at line 1353 of file mincut.c.

References minimum_cut_helper::csr_edgeDefaultToCsr, minimum_cut_helper::csr_edgeflipped, minimum_cut_helper::csr_headarr, minimum_cut_helper::csr_start, minimum_cut_helper::edges_capa, minimum_cut_helper::edges_isRemoved, graph_get_nEdges(), graph_get_nNodes(), graph_mincut_reInit(), minimum_cut_helper::isLpcut, nnodes, minimum_cut_helper::nodes_wakeState, minimum_cut_helper::root, minimum_cut_helper::rootcut, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMessage, minimum_cut_helper::terms, GRAPH::terms, minimum_cut_helper::terms_mincompsize, minimum_cut_helper::terms_minsepasize, minimum_cut_helper::termsepa_nedges, minimum_cut_helper::termsepa_nnodes, minimum_cut_helper::termsepa_termToCopy, termsepaCsrGetMaxNedges(), termsepaCsrGetMaxNnodes(), and termsepaFindTerminalSource().

Referenced by mincutInit().

mincutInit()

static SCIP_RETCODE mincutInit ( SCIP *  scip, SCIP_RANDNUMGEN *  randnumgen, SCIP_Bool  isLpcut, GRAPH *  g, MINCUT **  mincut  )

static

initializes

Parameters

scip	SCIP data structure
randnumgen	random number generator or NULL
isLpcut	for LP cut?
g	the graph
mincut	minimum cut

Definition at line 1425 of file mincut.c.

References minimum_cut_helper::csr_nedges, minimum_cut_helper::edges_isRemoved, FALSE, graph_get_nEdges(), graph_get_nNodes(), minimum_cut_helper::isLpcut, mincutInitForLp(), mincutInitForTermSepa(), minimum_cut_helper::ntermcands, NULL, minimum_cut_helper::randnumgen, minimum_cut_helper::root, minimum_cut_helper::rootcutsize, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, GRAPH::source, minimum_cut_helper::terms_mincompsize, minimum_cut_helper::terms_minsepasize, minimum_cut_helper::termsepa_nedges, minimum_cut_helper::termsepa_nnodes, minimum_cut_helper::termsepa_termToCopy, TRUE, and minimum_cut_helper::xval.

Referenced by mincut_findTerminalSeparators(), and mincut_separateLp().

mincutPrepareForLp()

static SCIP_RETCODE mincutPrepareForLp ( SCIP *  scip, const GRAPH *  g, MINCUT *  mincut  )

static

prepares for LP

Parameters

scip	SCIP data structure
g	the graph
mincut	minimum cut

Definition at line 1476 of file mincut.c.

References CREEP_VALUE, minimum_cut_helper::csr_edgeDefaultToCsr, minimum_cut_helper::csr_edgeflipped, minimum_cut_helper::csr_headarr, minimum_cut_helper::csr_nedges, minimum_cut_helper::csr_start, EAT_LAST, minimum_cut_helper::edges_capa, minimum_cut_helper::edges_isRemoved, flipedge, FLOW_FACTOR, graph_get_nEdges(), graph_get_nNodes(), GRAPH::head, Is_term, minimum_cut_helper::isLpcut, GRAPH::mincut_e, GRAPH::mincut_numb, GRAPH::mincut_r, nnodes, minimum_cut_helper::nodes_wakeState, minimum_cut_helper::ntermcands, GRAPH::oeat, GRAPH::outbeg, minimum_cut_helper::root, minimum_cut_helper::rootcut, minimum_cut_helper::rootcutsize, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPgetDepth(), SCIPisFeasGE(), SCIPprobdataGetVars(), SCIPvarGetUbLocal(), GRAPH::source, GRAPH::term, minimum_cut_helper::terms, GRAPH::terms, and minimum_cut_helper::xval.

Referenced by mincut_separateLp().

mincutPrepareForTermSepa()

static SCIP_RETCODE mincutPrepareForTermSepa ( SCIP *  scip, GRAPH *  g, MINCUT *  mincut  )

static

prepares for terminal separator comptation

Parameters

scip	SCIP data structure
g	the graph
mincut	minimum cut

Definition at line 1678 of file mincut.c.

References minimum_cut_helper::isLpcut, SCIP_CALL, SCIP_OKAY, termsepaBuildCsr(), and termsepaBuildRootcomp().

Referenced by mincut_findTerminalSeparators().

mincutGetNextSinkTerm()

static int mincutGetNextSinkTerm ( const GRAPH *  g, SCIP_Bool  firstrun, MINCUT *  mincut  )

static

returns next promising terminal for computing cut

Parameters

g	graph data structure
firstrun	first run?
mincut	minimum cut

Definition at line 1697 of file mincut.c.

References GRAPH::knots, GRAPH::mincut_dist, minimum_cut_helper::nodes_wakeState, minimum_cut_helper::ntermcands, NULL, minimum_cut_helper::randnumgen, SCIPrandomGetInt(), SWAP_INTS, minimum_cut_helper::terms, and w.

Referenced by mincut_findTerminalSeparators(), and mincut_separateLp().

mincutExec()

static void mincutExec ( const GRAPH *  g, int  sinkterm, SCIP_Bool  wasRerun, MINCUT *  mincut  )

static

executes

Parameters

g	the graph
sinkterm	sink terminal
wasRerun	not the first run?
mincut	minimum cut

Definition at line 1779 of file mincut.c.

References minimum_cut_helper::csr_edgeflipped, minimum_cut_helper::csr_headarr, minimum_cut_helper::csr_nedges, minimum_cut_helper::csr_start, minimum_cut_helper::edges_capa, graph_get_nNodes(), graph_mincut_exec(), minimum_cut_helper::isLpcut, nnodes, minimum_cut_helper::nodes_wakeState, NULL, minimum_cut_helper::root, minimum_cut_helper::rootcut, minimum_cut_helper::rootcutsize, GRAPH::source, and minimum_cut_helper::termsepa_nnodes.

Referenced by mincut_findTerminalSeparators(), and mincut_separateLp().

mincutFree()

static void mincutFree ( SCIP *  scip, MINCUT **  mincut  )

static

frees

Parameters

scip	SCIP data structure
mincut	minimum cut

Definition at line 1812 of file mincut.c.

References minimum_cut_helper::csr_edgeDefaultToCsr, minimum_cut_helper::csr_edgeflipped, minimum_cut_helper::csr_headarr, minimum_cut_helper::csr_start, minimum_cut_helper::edges_capa, minimum_cut_helper::edges_isRemoved, FALSE, graph_get_nNodes(), graph_knot_isInRange(), GRAPH::head, Is_term, minimum_cut_helper::isLpcut, nnodes, minimum_cut_helper::nodes_wakeState, minimum_cut_helper::ntermcands, NULL, GRAPH::oeat, GRAPH::outbeg, minimum_cut_helper::rootcut, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPfreeMemory, SCIPisFeasGE(), STP_Vectype, StpVecFree, StpVecGetSize, StpVecPushBack, StpVecReserve, SWAP_INTS, GRAPH::term, minimum_cut_helper::terms, minimum_cut_helper::terms_mincompsize, minimum_cut_helper::terms_minsepasize, minimum_cut_helper::termsepa_termToCopy, TRUE, and minimum_cut_helper::xval.

Referenced by mincut_findTerminalSeparators(), and mincut_separateLp().

lpcutAdd()

static SCIP_RETCODE lpcutAdd ( SCIP *  scip, SCIP_CONSHDLR *  conshdlr, const GRAPH *  g, const int *  nodes_inRootComp, const STP_Bool *  edges_isRemoved, const SCIP_Real *  xvals, int *  capa, const int  updatecapa, SCIP_Bool  local, SCIP_Bool *  success  )

static

add a cut

Parameters

scip	SCIP data structure
conshdlr	constraint handler
g	graph data structure
nodes_inRootComp	for each node: in root component?
edges_isRemoved	for each edge: removed?
xvals	edge values
capa	edges capacities (scaled)
updatecapa	update capacities?
local	is the cut local?
success	pointer to store whether add cut be added

Definition at line 1929 of file mincut.c.

References EQ, FALSE, FLOW_FACTOR, graph_get_nEdges(), GRAPH::head, GRAPH::knots, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowConshdlr(), SCIPdebug, SCIPflushRowExtensions(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisFeasGE(), SCIPprintRow(), SCIPprobdataGetVars(), SCIPreleaseRow(), GRAPH::source, GRAPH::tail, and TRUE.

Referenced by mincut_separateLp().

lpcutSetEdgeCapacity()

static void lpcutSetEdgeCapacity ( const GRAPH *  g, const SCIP_Real *  xval, SCIP_Bool  creep_flow, SCIP_Bool  flip, int *RESTRICT  capa  )

static

sets (integer) capacity for edges

Parameters

g	graph data structure
xval	edge values
creep_flow	creep flow?
flip	reverse the flow?
capa	edges capacities (scaled)

Definition at line 2030 of file mincut.c.

References CREEP_VALUE, GRAPH::edges, FLOW_FACTOR, and NULL.

Referenced by mincut_separateLp().

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().