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

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include "portab.h"
#include "grph.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
SCIP_RETCODE	graph_mincut_init (SCIP scip, GRAPH p)

void	graph_mincut_exit (SCIP scip, GRAPH p)

static void	globalrelabel (const GRAPH p, const int s, const int t, 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 GRAPH p, const int s, const int t, 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 GRAPH p, const int s, const int t, 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_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 rerun)

Macro Definition Documentation

◆ DEBUG

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

Definition at line 40 of file grphmcut.c.

◆ STATIST

#define STATIST 0

Definition at line 41 of file grphmcut.c.

◆ CHECK

#define CHECK 0

Definition at line 42 of file grphmcut.c.

Referenced by SCIPreoptCheckCutoff().

◆ Q_NULL

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

Definition at line 55 of file grphmcut.c.

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

◆ GLOBALRELABEL_ADD

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

Definition at line 56 of file grphmcut.c.

Referenced by graph_mincut_exec().

◆ GLOBALRELABEL_MULT

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

Definition at line 57 of file grphmcut.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 grphmcut.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 grphmcut.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 grphmcut.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 grphmcut.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 grphmcut.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 grphmcut.c.

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

Function Documentation

◆ 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 275 of file grphmcut.c.

References GRAPH::edges, GRAPH::knots, 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, NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.

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

◆ 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 305 of file grphmcut.c.

References GRAPH::knots, 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, nnodes, NULL, and SCIPfreeMemoryArray.

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

◆ globalrelabel()

static void globalrelabel	(	const GRAPH *	p,
		const int	s,
		const int	t,
		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 407 of file grphmcut.c.

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

Referenced by graph_mincut_exec().

◆ initialise()

static void initialise	(	const GRAPH *	p,
		const int	s,
		const int	t,
		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 599 of file grphmcut.c.

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

Referenced by graph_mincut_exec().

◆ reinitialise()

static void reinitialise	(	const GRAPH *	p,
		const int	s,
		const int	t,
		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 869 of file grphmcut.c.

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

Referenced by graph_mincut_exec().

◆ 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	rerun
	)

finds a minimum s-t cut

Definition at line 1125 of file grphmcut.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

◆ graph_mincut_init()

◆ graph_mincut_exit()

◆ globalrelabel()

◆ initialise()

◆ reinitialise()

◆ graph_mincut_exec()