# SCIP

Solving Constraint Integer Programs

grphmcut.c File Reference

## Detailed Description

Minimum cut routine for Steiner problems.

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 listinsert(node, nodedist, next, headactive, actmin, actmax)

#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)

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

 #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);\
}
#define NULL
Definition: lpi_spx1.cpp:155

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(nodedist >= 0);\
if( nodedist < (actmin) )\
actmin = nodedist;\
if( nodedist > (actmax) )\
actmax = nodedist;\
}
#define NULL
Definition: lpi_spx1.cpp:155

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);\
}
#define NULL
Definition: lpi_spx1.cpp:155

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(nodedist >= 0);\
if( nodedist < (actmin) )\
actmin = nodedist;\
if( nodedist > (actmax) )\
actmax = nodedist;\
if( (actmax) > (glbmax) )\
glbmax = (actmax);\
}
#define NULL
Definition: lpi_spx1.cpp:155

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);\
nextnode = next[node];\
{\
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;\
}\
}
#define Q_NULL
Definition: grphmcut.c:55
#define NULL
Definition: lpi_spx1.cpp:155

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);\
next[node] = nextnode;\
prev[node] = Q_NULL;\
if( nextnode >= 0 )\
prev[nextnode] = node;\
}
#define Q_NULL
Definition: grphmcut.c:55
#define NULL
Definition: lpi_spx1.cpp:155

Definition at line 153 of file grphmcut.c.

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

## ◆ 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.

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.

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.