Detailed Description

Minimum cut routine for Steiner problems.

Author: Gerald Gamrath; Thorsten Koch; Daniel Rehfeldt

This file implements a graph minimum cut routine for Steiner problems. For more details see Graph minimum cut routine page.

Definition in file graph_mcut.c.

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include "portab.h"
#include "graph.h"

Go to the source code of this file.

Macros
#define	DEBUG 0 /* 0 = No, 1 = Validation, 2 = Show flow */

#define	STATIST 0

#define	CHECK 0

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

#define	GLOBALRELABEL_ADD 10 /* constant for global relabel heuristic */

#define	GLOBALRELABEL_MULT 10 /* constant for global relabel heuristic */

#define	listdelete(node, nodedist, next, headactive)

#define	listinsert(node, nodedist, next, headactive, actmin, actmax)

#define	activedelete(node, nodedist, next, headactive)

#define	activeinsert(node, nodedist, next, headactive, actmin, actmax, glbmax)

#define	inactivedelete(node, nodedist, next, prev, headinactive, nextnode, prevnode)

#define	inactiveinsert(node, nodedist, next, prev, headinactive, nextnode)

Functions
static SCIP_RETCODE	mincutInit (SCIP scip, int nnodes, int nedges, GRAPH p)

static void	globalrelabel (const int s, const int t, const int nnodesreal, int RESTRICT dist, int RESTRICT headactive, int RESTRICT headinactive, int RESTRICT edgecurr, int RESTRICT next, int RESTRICT prev, int RESTRICT excess, int RESTRICT residual, int RESTRICT w, const int edgestart, const int edgearr, const int headarr, int actmin, int actmax, int glbmax, int dormmax)

static void	initialise (const int s, const int t, const int nnodesreal, const int rootcutsize, const int rootcut, const int capa, int RESTRICT dist, int RESTRICT headactive, int RESTRICT headinactive, int RESTRICT edgecurr, int RESTRICT next, int RESTRICT prev, int RESTRICT temp, int RESTRICT excess, int RESTRICT residual, int RESTRICT w, const int edgestart, const int edgearr, const int headarr, int dormmax, int actmin, int actmax, int *glbmax)

static void	reinitialise (const int s, const int t, const int nnodesreal, const int rootcutsize, const int rootcut, const int capa, int RESTRICT dist, int RESTRICT headactive, int RESTRICT headinactive, int RESTRICT edgecurr, int RESTRICT next, int RESTRICT prev, int RESTRICT temp, int RESTRICT excess, int RESTRICT residual, int RESTRICT w, const int edgestart, const int edgearr, const int headarr, int dormmax, int actmin, int actmax, int *glbmax)

void	graph_mincut_setDefaultVals (GRAPH *g)

SCIP_RETCODE	graph_mincut_init (SCIP scip, GRAPH p)

SCIP_RETCODE	graph_mincut_reInit (SCIP scip, int nnodes, int nedges, GRAPH p)

SCIP_Bool	graph_mincut_isInitialized (const GRAPH *p)

void	graph_mincut_exit (SCIP scip, GRAPH p)

void	graph_mincut_exec (const GRAPH p, const int s, const int t, const int nnodesreal, const int nedgesreal, const int rootcutsize, const int rootcut, const int capa, int RESTRICT w, const int edgestart, const int edgearr, const int *headarr, const SCIP_Bool isRerun)

Macro Definition Documentation

◆ DEBUG

#define DEBUG 0 /* 0 = No, 1 = Validation, 2 = Show flow */

Definition at line 40 of file graph_mcut.c.

◆ STATIST

#define STATIST 0

Definition at line 41 of file graph_mcut.c.

◆ CHECK

#define CHECK 0

Definition at line 42 of file graph_mcut.c.

Referenced by SCIPreoptCheckCutoff().

◆ Q_NULL

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

Definition at line 55 of file graph_mcut.c.

Referenced by globalrelabel(), graph_mincut_exec(), graph_mincut_setDefaultVals(), initialise(), and reinitialise().

◆ GLOBALRELABEL_ADD

#define GLOBALRELABEL_ADD 10 /* constant for global relabel heuristic */

Definition at line 56 of file graph_mcut.c.

Referenced by graph_mincut_exec().

◆ GLOBALRELABEL_MULT

#define GLOBALRELABEL_MULT 10 /* constant for global relabel heuristic */

Definition at line 57 of file graph_mcut.c.

Referenced by graph_mincut_exec().

◆ listdelete

#define listdelete	(	node,
		nodedist,
		next,
		headactive
	)

Value:

{\
   assert(node >= 0);\
   assert(nodedist >= 0);\
   assert(headactive != NULL);\
   headactive[nodedist] = next[node];\
}

remove first element from active (singly-linked) list

Definition at line 60 of file graph_mcut.c.

Referenced by graph_mincut_exec().

◆ listinsert

#define listinsert	(	node,
		nodedist,
		next,
		headactive,
		actmin,
		actmax
	)

Value:

{\
   assert(node >= 0);\
   assert(next != NULL);\
   assert(headactive != NULL);\
   assert(nodedist >= 0);\
   next[node] = headactive[nodedist];\
   headactive[nodedist] = node;\
   if( nodedist < (actmin) )\
      actmin = nodedist;\
   if( nodedist > (actmax) )\
      actmax = nodedist;\
}

add element to active (singly-linked) list

Definition at line 69 of file graph_mcut.c.

Referenced by graph_mincut_exec().

◆ activedelete

#define activedelete	(	node,
		nodedist,
		next,
		headactive
	)

Value:

{\
   assert(node >= 0);\
   assert(nodedist >= 0);\
   assert(headactive != NULL);\
   headactive[nodedist] = next[node];\
}

remove first element from active (singly-linked) list

Definition at line 101 of file graph_mcut.c.

Referenced by graph_mincut_exec().

◆ activeinsert

#define activeinsert	(	node,
		nodedist,
		next,
		headactive,
		actmin,
		actmax,
		glbmax
	)

Value:

{\
   assert(node >= 0);\
   assert(next != NULL);\
   assert(headactive != NULL);\
   assert(nodedist >= 0);\
   next[node] = headactive[nodedist];\
   headactive[nodedist] = node;\
   if( nodedist < (actmin) )\
      actmin = nodedist;\
   if( nodedist > (actmax) )\
      actmax = nodedist;\
   if( (actmax) > (glbmax) )\
      glbmax = (actmax);\
}

add element to active (singly-linked) list

Definition at line 110 of file graph_mcut.c.

Referenced by globalrelabel(), graph_mincut_exec(), initialise(), and reinitialise().

◆ inactivedelete

#define inactivedelete	(	node,
		nodedist,
		next,
		prev,
		headinactive,
		nextnode,
		prevnode
	)

Value:

{\
   assert(node >= 0);\
   assert(nodedist >= 0);\
   assert(next != NULL);\
   assert(prev != NULL);\
   assert(headinactive != NULL);\
   nextnode = next[node];\
   if( headinactive[nodedist] == node )\
   {\
      headinactive[nodedist] = nextnode;\
      if( nextnode >= 0 )\
         prev[nextnode] = Q_NULL;\
   }\
   else\
   {\
      prevnode = prev[node];\
      assert(prevnode >= 0);\
      assert(next[prevnode] == node);\
      next[prevnode] = nextnode;\
      if( nextnode >= 0 )\
         prev[nextnode] = prevnode;\
   }\
}

remove element from inactive (doubly-linked) list

Definition at line 127 of file graph_mcut.c.

Referenced by graph_mincut_exec().

◆ inactiveinsert

#define inactiveinsert	(	node,
		nodedist,
		next,
		prev,
		headinactive,
		nextnode
	)

Value:

{\
   assert(node >= 0);\
   assert(nodedist >= 0);\
   assert(next != NULL);\
   assert(prev != NULL);\
   assert(headinactive != NULL);\
   nextnode = headinactive[nodedist];\
   next[node] = nextnode;\
   prev[node] = Q_NULL;\
   if( nextnode >= 0 )\
      prev[nextnode] = node;\
   headinactive[nodedist] = node;\
}

add element to inactive (doubly-linked) list

Definition at line 153 of file graph_mcut.c.

Referenced by globalrelabel(), graph_mincut_exec(), initialise(), and reinitialise().

Function Documentation

◆ mincutInit()

static SCIP_RETCODE mincutInit	(	SCIP *	scip,
		int	nnodes,
		int	nedges,
		GRAPH *	p
	)

static

initializes minimum cut arrays

Parameters

scip	SCIP data structure
nnodes	number of nodes
nedges	number of edges
p	graph data structure

Definition at line 349 of file graph_mcut.c.

References GRAPH::mincut_dist, GRAPH::mincut_e, GRAPH::mincut_head, GRAPH::mincut_head_inact, GRAPH::mincut_nedges, GRAPH::mincut_next, GRAPH::mincut_nnodes, GRAPH::mincut_numb, GRAPH::mincut_prev, GRAPH::mincut_r, GRAPH::mincut_temp, nnodes, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.

Referenced by graph_mincut_init(), and graph_mincut_reInit().

◆ globalrelabel()

static void globalrelabel	(	const int	s,
		const int	t,
		const int	nnodesreal,
		int *RESTRICT	dist,
		int *RESTRICT	headactive,
		int *RESTRICT	headinactive,
		int *RESTRICT	edgecurr,
		int *RESTRICT	next,
		int *RESTRICT	prev,
		int *RESTRICT	excess,
		int *RESTRICT	residual,
		int *RESTRICT	w,
		const int *	edgestart,
		const int *	edgearr,
		const int *	headarr,
		int *	actmin,
		int *	actmax,
		int *	glbmax,
		int *	dormmax
	)

static

global relabel heuristic that sets distance of sink to zero and relabels all other nodes using backward bfs on residual graph, starting from the sink.

Definition at line 375 of file graph_mcut.c.

References activeinsert, FALSE, inactiveinsert, nnodes, NULL, Q_NULL, SCIP_Bool, and TRUE.

Referenced by graph_mincut_exec().

◆ initialise()

static void initialise	(	const int	s,
		const int	t,
		const int	nnodesreal,
		const int	rootcutsize,
		const int *	rootcut,
		const int *	capa,
		int *RESTRICT	dist,
		int *RESTRICT	headactive,
		int *RESTRICT	headinactive,
		int *RESTRICT	edgecurr,
		int *RESTRICT	next,
		int *RESTRICT	prev,
		int *RESTRICT	temp,
		int *RESTRICT	excess,
		int *RESTRICT	residual,
		int *RESTRICT	w,
		const int *	edgestart,
		const int *	edgearr,
		const int *	headarr,
		int *	dormmax,
		int *	actmin,
		int *	actmax,
		int *	glbmax
	)

static

initialize data for the first max-flow run

Definition at line 566 of file graph_mcut.c.

References activeinsert, GRAPH::edges, flipedge, inactiveinsert, nnodes, NULL, and Q_NULL.

Referenced by graph_mincut_exec().

◆ reinitialise()

static void reinitialise	(	const int	s,
		const int	t,
		const int	nnodesreal,
		const int	rootcutsize,
		const int *	rootcut,
		const int *	capa,
		int *RESTRICT	dist,
		int *RESTRICT	headactive,
		int *RESTRICT	headinactive,
		int *RESTRICT	edgecurr,
		int *RESTRICT	next,
		int *RESTRICT	prev,
		int *RESTRICT	temp,
		int *RESTRICT	excess,
		int *RESTRICT	residual,
		int *RESTRICT	w,
		const int *	edgestart,
		const int *	edgearr,
		const int *	headarr,
		int *	dormmax,
		int *	actmin,
		int *	actmax,
		int *	glbmax
	)

static

initialize data for the repeated max-flow run

Definition at line 833 of file graph_mcut.c.

References a, activeinsert, FALSE, flipedge, inactiveinsert, nnodes, NULL, Q_NULL, SCIP_Bool, and TRUE.

Referenced by graph_mincut_exec().

◆ graph_mincut_setDefaultVals()

void graph_mincut_setDefaultVals ( GRAPH * g )

sets default values

Parameters

g	graph data structure

Definition at line 1081 of file graph_mcut.c.

References GRAPH::knots, GRAPH::mincut_e, GRAPH::mincut_head, GRAPH::mincut_head_inact, GRAPH::mincut_nnodes, nnodes, and Q_NULL.

Referenced by mincut_findTerminalSeparators(), and mincut_separateLp().

◆ graph_mincut_init()

SCIP_RETCODE graph_mincut_init	(	SCIP *	scip,
		GRAPH *	p
	)

initialize min cut arrays

Parameters

scip	SCIP data structure
p	graph data structure

Definition at line 1105 of file graph_mcut.c.

References GRAPH::edges, graph_mincut_isInitialized(), GRAPH::knots, mincutInit(), NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by createModel(), graph_mincut_exec(), initReceivedSubproblem(), and SCIP_DECL_PROBCOPY().

◆ graph_mincut_reInit()

SCIP_RETCODE graph_mincut_reInit	(	SCIP *	scip,
		int	nnodes,
		int	nedges,
		GRAPH *	p
	)

reinitializes minimum cut arrays

Parameters

scip	SCIP data structure
nnodes	number of nodes
nedges	number of edges
p	graph data structure

Definition at line 1120 of file graph_mcut.c.

References graph_mincut_exit(), graph_mincut_isInitialized(), mincutInit(), SCIP_CALL, and SCIP_OKAY.

Referenced by mincutInitForTermSepa().

◆ graph_mincut_isInitialized()

SCIP_Bool graph_mincut_isInitialized ( const GRAPH * p )

is the minimum data initialized?

Parameters

p	graph data structure

Definition at line 1139 of file graph_mcut.c.

References FALSE, GRAPH::mincut_dist, GRAPH::mincut_e, GRAPH::mincut_head, GRAPH::mincut_next, GRAPH::mincut_nnodes, GRAPH::mincut_numb, GRAPH::mincut_prev, GRAPH::mincut_r, GRAPH::mincut_temp, GRAPH::mincut_x, NULL, and TRUE.

Referenced by graph_free(), graph_mincut_exit(), graph_mincut_init(), and graph_mincut_reInit().

◆ graph_mincut_exit()

void graph_mincut_exit	(	SCIP *	scip,
		GRAPH *	p
	)

frees min cut arrays

Parameters

scip	SCIP data structure
p	graph data structure

Definition at line 1175 of file graph_mcut.c.

References graph_mincut_isInitialized(), GRAPH::mincut_dist, GRAPH::mincut_e, GRAPH::mincut_head, GRAPH::mincut_head_inact, GRAPH::mincut_nedges, GRAPH::mincut_next, GRAPH::mincut_nnodes, GRAPH::mincut_numb, GRAPH::mincut_prev, GRAPH::mincut_r, GRAPH::mincut_temp, and SCIPfreeMemoryArray.

Referenced by graph_free(), graph_mincut_exec(), graph_mincut_reInit(), initReceivedSubproblem(), and SCIP_DECL_PROBDELORIG().

◆ graph_mincut_exec()

void graph_mincut_exec	(	const GRAPH *	p,
		const int	s,
		const int	t,
		const int	nnodesreal,
		const int	nedgesreal,
		const int	rootcutsize,
		const int *	rootcut,
		const int *	capa,
		int *RESTRICT	w,
		const int *	edgestart,
		const int *	edgearr,
		const int *	headarr,
		const SCIP_Bool	isRerun
	)

finds a minimum s-t cut

Definition at line 1202 of file graph_mcut.c.

References a, activedelete, activeinsert, EAT_LAST, Edge_anti, GRAPH::edges, FALSE, flipedge, globalrelabel(), GLOBALRELABEL_ADD, GLOBALRELABEL_MULT, graph_mincut_exit(), graph_mincut_init(), GRAPH::head, inactivedelete, inactiveinsert, initialise(), GRAPH::knots, listdelete, listinsert, Min, GRAPH::mincut_dist, GRAPH::mincut_e, GRAPH::mincut_head, GRAPH::mincut_head_inact, GRAPH::mincut_next, GRAPH::mincut_numb, GRAPH::mincut_prev, GRAPH::mincut_r, GRAPH::mincut_temp, GRAPH::mincut_x, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, Q_NULL, r, reinitialise(), SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocMemoryArray, SCIPfreeBlockMemoryArray, SCIPfreeMemoryArray, GRAPH::tail, TRUE, and x.

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ DEBUG

◆ STATIST

◆ CHECK

◆ Q_NULL

◆ GLOBALRELABEL_ADD

◆ GLOBALRELABEL_MULT

◆ listdelete

◆ listinsert

◆ activedelete

◆ activeinsert

◆ inactivedelete

◆ inactiveinsert

Function Documentation

◆ mincutInit()

◆ globalrelabel()

◆ initialise()

◆ reinitialise()

◆ graph_mincut_setDefaultVals()

◆ graph_mincut_init()

◆ graph_mincut_reInit()

◆ graph_mincut_isInitialized()

◆ graph_mincut_exit()

◆ graph_mincut_exec()